决策树

决策树数据挖掘的典型任务—分类分类(classification)从大量数据中学习(训练)得到对未来数据所属类别的判别准则。特点：（1）数据的类别（label)已知(人工分析标定)；（2）类别标号为离散数据。ClassLabelAttribute训练集测试集(不参加训练）分类器或分类规则训练测试预测Label=？测试分类器推广能力k倍交叉验证（k-foldcross-validation）特殊情况：留一法（leave-one-out)3分类方法KNN决策树贝叶斯分类Logistic回归机器学习：神经网络，支撑向量机，正则化方法等集成学习：Adboost，梯度Boosting等多分类问题数据挖掘的典型任务—分类ID3C4.5CART决策树分类(DecisionTree)从属性-类别事例推理树状规则的分类方法。应用最为广泛，常用的有：ID3，C4.5。叶节点生成决策树步骤：修剪决策树生成决策树的关键:选择合适的属性作为判断依据，信息增益，信息增益比等生成决策树时未考虑噪声影响，出现过拟合，预测效果差：预先剪枝，后剪枝20世纪七、八十年代，J.RossQuilan开发了决策树算法，称作ID3(IterativeDichotomiser,迭代的二分器)，后又提出了C4.5(ID3的后继)。1984年即位统计学家(L.Breiman,J.Friedman,R.Olshen和C.Stonr)出版了分类与回归树(CART),介绍了二叉决策树的产生。决策树分类改进的C5.0算法4.二叉树CART算法3.2.决策树的基本思想1.ID3算法和C4.5算法决策树的基本思想每个内部节点（非叶节点）表示一个属性的测试；每个树叶节点代表一个类（输出）归纳学习buys_computer的决策树，表示AllElectronics顾客是否可能购买计算机ageyouthmiddle_agedseniorYesfairnoyescredit_rating?student?YesNoYesNoexcellentAllElectronics顾客数据库类标记的训练样本属性选择度量增益率信息增益指标纯，即划分后各组中所有样本都属于相同的类。属性选择度量又称分裂规则，根据该准则。分裂后的输出将样本集细化，理性情况下，每个划分是“纯”的Gini信息熵设数据集为，类属性具有个取值，定义个不同的类设是中类的样本的集合,和分别是和中的样本个数.,iDCiC|D|,||iDCDDD,iDC(1,2,...,).iCimmm21()logmiiiInfoDpp数据集D的信息熵:其中,是中任意样本属于类的概率,用估计.使用以2为底的对数函数,是因为信息用二进位编码.ipDiC,||||iDCD应用式子(1),计算AllElectronics顾客数据库分类所需要的信息熵：(1)229955()log()log()0.94014141414InfoD信息增益假设按属性划分中的样本，且属性根据训练数据的观测具有个不同值。如果是离散值，这些值直接对应于的属性。ADAv12{,,...,}vaaaAA可依属性将划分为个子集ADv12{,,...,}.vDDD其中，为中的样本，它们在上具有属性值jDDA.ja这些划分将对应于从该节点出来的分支。A基于按划分对的样本分类所需要的期望信息：AD1()*()vjAjjDInfoDInfoDD其中，充当第个划分的权重。jDDj()AInfoD越小，划分的纯度越高。信息增益信息增益定义式：()()()AGainAInfoDInfoD告诉我们知道的值而导致的信息需求的期望减少。()GainAA()GainA按照能做“最佳分类”的属性划分，使完成样本分类需要的信息量最小。max选择具有最高信息增益的属性作为分裂属性()GainAAA()GainAmin()AInfoD222222()=52233×(loglog)14555544400×(loglog)14444453322×(-log-log)145555=0.694ageInfoD+()()()0.9400.6940.246ageGainageInfoDInfoD信息增益信息增益222222()42222×(-log-log)14444464422×(loglog)14666643311×(loglog)1444440.911incomeInfoD()()()0.9400.9110.029incomeGainincomeInfoDInfoD()()()0.9400.7890.151studentGainstudentInfoDInfoD_(_)()()0.9400.8920.048creditratingGaincreditratingInfoDInfoD信息增益第一次迭代后形成的决策树ageyouthmiddle_agedseniorP1P2P8P9P11P3P7P12P13P4P5P6P10P14属性age具有最高信息增益，成为分裂属性算法终止条件1一个节点的所有样本均属于同一类2若当前数据集没有属性可用于划分时，则按照少数服从多数的原则将当前节点强制为叶节点。3当分到某类时，某个值的比例达到了给定的阈值。buys_computer的决策树，表示AllElectronics顾客是否可能购买计算机最终形成的决策树递归ageyouthmiddle_agedseniorYesfairnoyescredit_rating?student?YesNoYesNoexcellent算法流程优点：(1)原理简单，生成模式便于理解；(2)对噪声数据有很好的强壮性。缺点：(1)只能处理离散值属性；(2)偏袒选择值较多的属性；(3)易产生过拟合（overfitting）后剪枝ID3算法算法优缺点C4.5算法1993年由Quinlan提出，采用信息增益比(信息率)来选择属性。克服偏向选择取值较多属性的缺点用阈值对属性划分，即把训练集中该属性的所有值划分到不同的区间中。用最常见值代替未知值规则存于二维数组中如：视为youth;视为middle_aged;视为senior.30age~[30,40]age40age增益率Why？信息增益度量偏向于有许多输出的测试，即它倾向于选择具有大量值的属性。举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。2()111×(log)14110PIDInfoD()()()0.940PIDGainPIDInfoDInfoD对属性PID划分得到的信息增益最大，显然，这种划分对分类没有用处。增益率What？使用分裂信息(splitinformation)将信息增益规范化。4.5C21()*logvjjAjDDSplitInfoDDD该值表示数据集按属性测试的个划分产生的信息。DAv增益率：()()()AGainAGainRatioASplitInfoD选择具有最大信息率的属性作为分裂属性。增益率income222()44×log141466×log141444×log14141.557incomeSplitInfoD()0.029()0.019()1.557incomeGainincomeGainRatioincomeSplitInfoD其他属性的信息率可类似求出。CART指标(index)在CART中使用。CART生成二叉树。指标GiniGiniGini指标用来度量数据划分或者数据集的不纯度。21()1miiGiniDp其中，是中样本属于类的概率，并用估计。ipDiC,iDCDGini指标考虑每个属性上的二元划分。GiniCARTGini指标21()1miiGiniDp2295()10.4591414GiniD如果属性是离散值，考察的属性值形成的可能子集AS每个子集可以看作属性的形如ASAAAS？的二元测试。给定一个样本，如果该样本的值出现在中，该测试满足。AASAAAllElectronics顾客数据库类标记的训练样本为了找出数据集的分裂准则，需要计算每个属性的指标。Gini指标CART以属性为例。incomeincome有三个属性值{,,}lowmediumhigh子集有个分别是32{,,},{,},lowmediumhighlowmedium{,},{,},{},{},{}lowhighmediumhighlowmediumhigh和{}.由于集合{,,}lowmediumhigh不代表任何分裂，基于属性的二元{}.和income3226划分，存在种划分数据集的方法。GiniGini指标CART如果按照的二元分裂，将划分成和，则给定该划分的1DAD2D指标为：Gini1212()()()ADDGiniDGiniDGiniDDDGini基于该划分计算出的指标值为：数据集中满足的样本共10个，1D考虑属性的子集。income{,}lowmedium其余4个样本被划分到中。D{,}incomelowmedium2D被分到中，对于连续值属性，必须考虑每个可能的分裂点。取排序好的每对相邻值的中点取做可能的分裂点。_intsplitpo1:_int;DAsplitpo2:_int.DAsplitpoD被分成和Gini指标{,}122222{}104()()()141410734221114101014440.443()incomelowmediumincomehighGiniDGiniDGiniDGiniD类似地，对其余子集分裂的指标值是：Gini0.458(子集{}和{})0.450(子集{}和{}),lowhighmedium,mediumhighlow。属性的最好二元划分在因为它最小化指标。income{,}lowmedium{}high和GiniCART生成二叉树同样的办法，评估节点，得到(或)为的最好分裂.ageage{,}youthsenior{_}middleagedCART指标值为0.357；GiniGini属性和都是二元的，分别具有指标值0.367和0.429.{}student{_}creditrating比较可知，属性和分裂子集产生最小age{,}youthsenior指标，因此被选作根节点，产生两个分支。GiniCART生成二叉树对分裂后的子集，递归调用上述流程，即可完成建树。用训练集来评估该二叉树，14个样本中能正确分类12个，正确率85.71%。{,}?ageyouthsenior?student?creditfairyesyesnono是是是否否否决策树剪枝Why？由于数据中存在噪声，许多分支反映的是训练数据中的异常。剪枝来处理这种过分拟合问题。How?先剪枝(prepruning)后剪枝(postpruning)在完全正确分类训练集之前就停止树的生长。由“完全生长”的树剪去子树。决策树剪枝——先剪枝最直接的方法：事先限定树的最大生长高度如果设为3，则如图剪枝{,}?ageyouthsenior?student?creditfairyesyesno剪枝处理{}?incomemediumyesno45311no否否否否是是是是决策树剪枝——后剪枝找出“完全”生长的树树叶用被替换的子树最频繁的类标号。{,}?ageyouthsenior?student?creditfairyesyesno{}?incomemediumyesno41311no?creditfair2{}incomehighyes/no2NO是是是是是是否否否否否否后剪枝降低分类错误率剪枝(ReducedErrorPruning)需要独立于训练集的测