ML(4): 决策树分类

决策树（Decision Tree）是用于分类和预测的主要技术，它着眼于从一组无规则的事例推理出决策树表示形式的分类规则，采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根据不同属性判断从该节点向下分支，在决策树的叶节点得到结论。因此，从根节点到叶节点就对应着一条合理规则，整棵树就对应着一组表达式规则。基于决策树算法的一个最大的优点是它在学习过程中不需要使用者了解很多背景知识，只要训练事例能够用属性即结论的方式表达出来，就能使用该算法进行学习。决策树算法在很多方面都有应用，如决策树算法在医学、制造和生产、金融分析、天文学、遥感影像分类和分子生物学、机器学习和知识发现等领域得到了广泛应用。

决策树技术是一种对海量数据集进行分类的非常有效的方法。通过构造决策树模型，提取有价值的分类规则，帮助决策者做出准确的预测已经应用在很多领域。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树的典型算法有ID3、C4.5和CART等，基于决策树的分类模型有如下几个特点：

• 决策树方法结构简单，便于理解；
• 决策树模型效率高，对训练集较大的情况较为适合；
• 决策树方法通常不需要接受训练集数据外的知识；
• 决策树方法具有较高的分类精确度。

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 决策树模型也有一些缺点，比如处理缺失 数据时的困难，过度拟合问题的出现，以及忽略数据集中属性之间的相关性等。 和决策树模型相比，朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以 及稳定的分类效率。同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好

策树是一颗倒长的树，主要由根节点、分支、叶节点组成，每一个分支是一条规则，主要用于分类。针对每一种决策树的算法都要解决两个主要问题：

• ①选择哪个属性来分裂？
• ②什么时候树停止生长？

 现状分析

---

决策树技术是迄今为止发展最为成熟的一种概念学习方法。它最早产生于二十世纪60年代，是由Hunt等人研究人类概念建模时建立的学习系统（CLS，Concept Learning System），到70年代末，J Ross Quinlan提出ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。1975年和1984年，分别有人提出CHAID（Chi-squared Automatic Interaction Detection）和CART（Classification and Regression Tree，亦称BFOS）算法。1986年，J.C.Schlimmer提出ID4算法。1988年，P.E.Utgoff提出ID5R算法。1993年，Quinlan本人以ID3算法为基础研究出C4.5/C5.0算法，C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面作了较大的改进，既适合于分类问题，又适合于回归问题。

决策树算法的优点如下：（1）分类精度高；（2）生成的模式简单；（3）对噪声数据有很好的健壮性。因而是目前应用最为广泛的归纳推理算法之一，在数据挖掘中收到研究者的广泛关注。数据挖掘需要选择复杂度低的算法和并行高效的策略，复杂度低的算法包括尽量把全局最优问题转化成局部最优的问题和近似线性或尽量低阶的多项式复杂度算法等，而高效并行的策略包括需要有高超的递归改为循环的技巧和尽量避免使用全局信息等。

现在研究者们还在继续研究改进的决策树算法，对于C4.5算法研究人员们从不同的角度对其进行了相应的改进，其中有针对C4.5算法处理连续型属性比较耗时的改进，利用数学上的等价无穷小提高信息增益率的计算效率等等方面。本报告时针对C4.5算法本身进行的分析和算法实现，同时会考虑进一步的深入学习。

技术分析

---

决策树构造的输入是一组带有类别标记的例子，构造的结果是一棵二叉树或多叉树。二叉树的内部节点(非叶子节点)一般表示为一个逻辑判断，如形式为a=的逻辑判断，其中a是属性，是该属性的所有取值：树的边是逻辑判断的分支结果。 多叉树(ID3)的内部结点是属性，边是该属性的所有取值，有几个属性值就有几条边。树的叶子节点都是类别标记。由于数据表示不当、有噪声或者由于决策树生成时产生重复的子树等原因，都会造成产生的决策树过大。因此，简化决策树是一个不可缺少的环节。寻找一棵最优决策树，主要应解决以下3个最优化问题：

• ①生成最少数目的叶子节点；
• ②生成的每个叶子节点的深度最小；
• ③生成的决策树叶子节点最少且每个叶子节点的深度最小。

ID3算法是一种经典的决策树算法，它从根节点开始，根节点被赋予一个最好的属性。随后对该属性的每个取值都生成相应的分支，在每个分支上又生成新的节点。对于最好的属性的选择标准，ID3采用基于信息熵定义的信息增益来选择内节点的测试属性，熵（Entropy）刻画了任意样本集的纯度。ID3算法存在的缺点：（1）ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多是属性，在有些情况下这类属性可能不会提供太多有价值的信息。（2）ID3算法只能对描述属性为离散型属性的数据集构造决策树。

ID3算法的局限是它的属性只能取离散值，为了使决策树能应用与连续属性值，Quinlan给出了ID3的一个扩展算法，即C4.5算法。C4.5算法是ID3的改进，其中属性的选择依据同ID3。它对于实值变量的处理与接下来论述的CART算法一致，采用多重分支。C4.5算法能实现基于规则的剪枝。因为算法生成的每个叶子都和一条规则相关联，这个规则可以从树的根节点直到叶子节点的路径上以逻辑合取式的形式读出。决策树的分类过程就是把训练集划分为越来越小的子集的过程。理想的结果是决策树的叶子节点的样本都有同类标记。如果是这样，显然决策树的分支应该停止了，因为所以的类别已经被分开了。

C4.5算法之所以是最常用的决策树算法，是因为它继承了ID3算法的所有优点并对ID3算的进行了改进和补充。C4.5算法采用信息增益率作为选择分支属性的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化是处理，还能够对不完整数据进行处理。C4.5算法属于基于信息论（Information Theory）的方法，它是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。C4.5算法主要做出了以下方面的改进：

• 用信息增益率来选择属性：克服了用信息增益来选择属性时偏向选择值多的属性的不足。
• 可以处理连续数值型属性： 4.5算法既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某节点上的分枝属性时，对于离散型描述属性，C4.5算法的处理方法与ID3相同，按照该属性本身的取值个数进行计算
• 采用了一种后剪枝方法：避免树的高度无节制的增长，避免过度拟合数据，该方法是用训练样本本身来估计剪枝前后的误差，从而决定是否真正剪枝。
• 对于缺失值的处理：在某些情况下，可供使用的数据可能缺少某些属性的值。假如<x，c(x)>是样本集S中的一个训练实例，但是其属性A的值A（x）未知。处理缺少属性值的一种策略是赋给它节点n所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺失值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值

C4.5算法

---

• C4.5树生成算法
• 
• 

cART算法

---

• CART（Classification and Regression tree）分类回归树由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出。
• ID3中根据属性值分割数据，之后该特征不会再起作用，这种快速切割的方式会影响算法的准确率。
• CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。
• CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。
• CART中每一次迭代都会降低GINI系数。回归时使用均方差作为loss function
• 

R算法包

---

• c4.5:      partykit::ctree
• c4.5:    RWeka::J48
• c4.5:    C50:C5.0
• cart:     tree::tree
• cart:    rpart::rpart

参考资料

---

• http://blog.csdn.net/john_dw/article/details/25322325
• http://blog.sina.com.cn/s/blog_6934cecb0101a7kc.html
• http://www.cnblogs.com/dudumiaomiao/p/5947369.html
• http://blog.csdn.net/yujunbeta/article/details/14986219
• http://www.cnblogs.com/karlpearson/p/6224148.html
• http://www.cnblogs.com/karlpearson/p/6224148.html
• http://www.17bigdata.com/%E3%80%90%E6%95%B0%E6%8D%AE%E6%8C%96%E6%8E%98%E3%80%91%E5%8D%81%E5%A4%A7%E7%BB%8F%E5%85%B8%E6%95%B0%E6%8D%AE%E6%8C%96%E6%8E%98%E7%AE%97%E6%B3%95r%E8%AF%AD%E8%A8%80%E5%AE%9E%E8%B7%B5.html
• http://www.17bigdata.com/%E5%86%B3%E7%AD%96%E6%A0%91.html
• http://www.17bigdata.com/r%E8%AF%AD%E8%A8%80%E4%B8%8E%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%EF%BC%88%E5%88%86%E7%B1%BB%E7%AE%97%E6%B3%95%EF%BC%89%EF%BC%882%EF%BC%89%E5%86%B3%E7%AD%96%E6%A0%91.html