决 策 树 系 列（一）一一基础知识回顾与总结1.决策树的定义树想必大家都会比较熟悉，是由节点和边两种元素组成的结构理解树，就需要理解几个关键词：根节点、父节点、子节点和叶子节点父节点和子节点是相对的，说白了子节点由父节点根据某一规则分裂而来，然后子节点作为新的父亲节点继续分裂，直至不能分裂为止而根节点是没有父节点的节点，即初始分裂节点，叶子节点是没有子节点的节点，如下图所示：叶子节点 叶子节点 叶子节点图1.1树的结构示意图决策树利用如上图所示的树结构进行决策，每一个非叶子节点是一个判断条件，每一个叶子节点是结论从跟节点开始，经过多次判断得出结论2.决策树如何做决策从一个分类例子说起：银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷款的意向，从而更有针对性地完成工作下表是银行现在能够掌握的信息，我们的目标是通过对下面的数据进行分析建立一个预测用户贷款一下的模型表2.1银行用户信息表职业年龄收入学历是否贷款自由职业285000高中是（注：上表中的数据都由本人捏造，不具有任何实际的意义）工人3 65 5 0 0高中否工人4 22 8 0 0初中是白领4 53 3 0 0小学是白领2 51 0 0 0 0本科是白领3 28 0 0 0硕士否白领2 81 3 0 0 0博士是自由职业2 14 0 0 0本科否自由职业2 23 2 0 0小学否工人3 33 0 0 0高中否工人4 84 2 0 0小学否上边中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够 肯定地 判断出用户的类型或者是上述属性都已经使用完毕。
比如说我们要判断一个客户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判断，这样以此类推，直到可以得出结论为止决策树用树结构实现上述的判断流程，如图2.1所示:无贷款意向 有贷款意向 有贷款意向 无贷款意向图 2.1 银行贷款意向分析决策树示意图通过图2.1的训练数据，我们可以建议图2.1所示的决策树，其输入是用户的信息，输出是用户的贷款意向如果要判断某一客户是否有贷款的意向，直接根据用户的职业、收入、年龄以及学历就可以分析得出用户的类型如某客户的信息为：（职业、年龄，收入,学历 =工人、39,1800,小学）,将信息输入上述决策树，可以得到下列的分析步骤和结论工人第二步：根据客户的年龄进行选择，选择年龄 Entropy4 log (-.)A Entropvt14+4+-14+1212 log(-)=Entropv214+12+)属 性2：Info2=En tropy-En tro p y.=2=128T16-1g（28T16）+2 82 8 +1 6-1g（28T16）=Entropy-（-1g（8T2）+9 .9=log （=）=Entropy!8+2 8+288 +2（2 0一（2 0 +1 4 log（2 0 ）2 0 +1 4）20Tl 4-1g（20T14）=Entropy2=0.7 5由于 Info2,所以属性i与属性2相比是更优的分裂属性，故选择属性1作为分裂的属性。
2)信息增益率使用信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂为了解决这个问题，引入了信息增益率这个概念信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益(听起来很拗口)，其计算公式如下：Info_Ratio=Inf -G a mInstrinsichifo其中In fo-G a ln表示信息增益，成协,表示分裂子节点数据量的信息增益，其计算公式为：Ins trin sicln fo =A其 中m表示子节点的数量，A才表示第i个子节点的数据量，N表示父节点数据量，说白了，其 实/m m nszc/g是分裂节点的琉如果节点的数据链越接近，/何4硫,越大，如果子节点越大，加壮族越大，而/硫-就会越小，能够降低节点分裂时选择子节点多的分裂属性的倾向性信息增益率越高，说明分裂的效果越好还是信息增益中提及的例子为例：图3.3根据属性1分裂 图3.4根据属性2分裂属 性1的信息增益率:类 1:2 0类2:1 4Info _ Gain.=0.81In trinsic In fo.=,1g(1 8 T 2 6)4-26 i/26-log(-18+26 18+26=0.97r_ .Info _ Gain.o.Info _ Ratio.=-l =0.84In trinsiclnfo.属 性2的信息增益率:Info _ Gain2=0.75T+1 F(10 i/1 34 i，34、Intrinsiclnfo.=-(-log(-.)+-log(-)10+34 10+34 10+34 10+34=0.77r-D.Info _ Gai%八Info _ Ratio2=-=-=0.97Intrinsic 工nf%Info _ Ra ti o.Info _ Ra ti o,由于 一 一 ，故选择属性2作为分裂的属性。
3.3停止分裂的条件决策树不可能不限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩下一个数据点时自动结束分裂，但这种情况下树过于复杂，而且预测的经度不高一般情况下为了降低决策树复杂度和提高预测的经度，会适当提前终止节点的分裂以下是决策树节点停止分裂的一般性条件：(1)最小节点数当节点的数据量小于一个指定的数量时，不继续分裂两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性提前结束分裂一定程度上有利于降低过拟合的影响2)焙或者基尼值小于阀值由上述可知，燧和基尼值的大小表示数据的复杂程度，当婚或者基尼值过小时，表示数据的纯度比较大，如果焙或者基尼值小于一定程度数，节点停止分裂3)决策树的深度达到指定的条件节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂4)所有特征已经使用完毕，不能继续进行分裂被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点3.4决策树的构建方法根据决策树的输出结果，决策树可以分为分类树和回归树，分类树输出的结果为具体的类别，而回归树输出的结果为一个确定的数值。
决策树的构建算法主要有ID3、C4.5、CART三种，其中ID3和 C4.5是分类树，CART是分类回归树，将在本系列的山 史、C 4.5和 C A R T 中分别讲述其中ID3是决策树最基本的构建算法，而 C4.5和 CART是在ID3的基础上进行优化的算法4.决策树的优化一棵过于复杂的决策树很可能出现过拟合的情况，如果完全按照3 中生成一个完整的决策树可能会出现预测不准确的情况,因此需要对决策树进行优化，优化的方法主要有两种，一是剪枝，二是组合树，将在本系列的剪 枝和组合树中分别讲述决策树系列(二)剪枝什么是剪枝？剪枝是指将一颗子树的子节点全部删掉，根节点作为叶子节点，以下图为例:为甚么要剪枝？决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策树越复杂，过拟合的程度会越高考虑极端的情况，如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所有的噪声数据都 准确划分”了，强化了噪声数据的作用剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合出现的概率怎样剪枝？两种方案：先剪枝和后剪枝先剪枝说白了就是提前结束决策树的增长，跟上述决策树停止生长的方法一样。
后剪枝是指在决策树生长完成之后再进行剪枝的过程这里介绍三种后剪枝方案：(1)REP一错误率降低剪枝顾名思义，该剪枝方法是根据错误率进行剪枝，如果一棵子树修剪前后错误率没有下降，就可以认为该子树是可以修剪的REP剪枝需要用新的数据集，原因是如果用旧的数据集，不可能出现分裂后的错误率比分裂前错误率要高的情况由于使用新的数据集没有参与决策树的构建，能够降低训练数据的影响，降低过拟合的程度，提高预测的准确率2)PEP一悲观剪枝悲观剪枝认为如果决策树的精度在剪枝前后没有影响的话，则进行剪枝怎样才算是没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果与剪枝前的效果一致，此时要进行剪枝进行剪枝必须满足的条件：石 工 如“-+5（邑%”）其中：E 即表示剪枝前子树的误差；表示剪枝后节点的误差；两者的计算公式如下：石.=3+2+05m令子树误差的经度满足二项分布，根据二项分布的性质，石必，“=3（4 +,_ _ _ _ _ _ _ _ 瓦 加S（耳s）=J p Q-p），其 中0一 N,N为子树的数据量；同样，叶子节点的误差石W=e+0.5上述公式中，0.5表示修正因子由于子节点是父节点进行分裂的结果，从理论上讲，子节点的分类效果总比父节点好，分类的误差更小，如果单纯通过比较子节点和父节点的误差进行剪枝就完全没有意义了，因此对节点的误差计算方法进行修正。
修正的方法是给每一个节点都加上误差修正因子0.5,在计算误差的时候，子节点由于加上了误差修正因子，就无法保证总误差低于父节点算例:m=2+O-5)=(1+O.5)+(4+O.5)+Q+O.5)=7.51-1S(ES3)=J7.5(l-=2.09E=e+0.5=8.5由于心如%+s（4 G,所以应该进行剪枝3）CCP一代价复杂度剪枝代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝可描述如下：令决策树的非叶子节点为 4石，4,a）计算所有非叶子节点的表面误差率增益值b）选择表面误差率增益值最小的非叶子节点（若多个非叶子节点具有相同小的表面误差率增益值，选择节点数最多的非叶子节点）O对选中的非叶子节点进行剪枝表面误差率增益值的计算公式:N(T)-1其中:即）表示叶子节点的误差代价，和）=顶 了（”，心 为 节 点 的 错 误 率，P（）为节点数据量的占比；m火 法 示子树的误差代价，一 斗 S ，力）：为子节点i的错误率，Pi表示节点i的数据节点占比；-（刀:表示子树节点个数。
算例：下图是决策树A的其中一颗子树，决策树的总数据量为4 0该子树的表面误差率增益值可以计算如下：即）=土竺1 8 4 0 5m 1.3 4 9 1 6 6R（T）=2彳（p；=-+-F-=一 T 3 4 0 9 4 0 6 4 0 4 C1 _ 6)-7?(D _ 5 _ 4 0 _ 1(JL=-=-=-N(T-13-1 4 0求出该子树的表面错误覆盖率为1/40,只要求出其他子树的表面误差率增益值就可以对决策树进行剪枝.决策树系列（三）一一ID3初识ID3回顾决策树的基本知识，其构建过程主要有下述三个重要的问题:（1）数据是怎么分裂的（2）如何选择分类的属性（3）什么时候停止分裂从上述三个问题出发，以实际的例子对ID 3算法进行阐述例：通过当天的天气、温度、湿度和季节预测明天的天气表1原始数据当天天气温度湿度季节明天天气晴2550春天晴阴2148春天阴阴1870春天雨晴2841夏天晴雨865冬天阴晴1843夏天晴阴2456秋天晴雨1876秋天阴雨3161夏天晴阴643冬天雨晴1555秋天阴雨458冬天雨1.数据分割对于离散型数据，直接按照离散数据的取值进行分裂，每一个取值对应一个子节点,以 当前天气”为例对数据进行分割，如 图1所示。
310%m:m:121%m:.m:112Hff:叫m:图1按 照“今天天气”属性进行划分对于连续型数据，ID3原本是没有处理能力的，只有通过离散化将连续性数据转化成离散型数据再进行处理。