(转)Decision Tree

Decision Tree：Analysis

大家有没有玩过猜猜看(Twenty Questions)的游戏？我在心里想一件物体，你可以用一些问题来确定我心里想的这个物体；如是不是植物？是否会飞？能游泳不？当你问完这些问题后，你就能得到这个物体的特征，然后猜出我心里想象的那个物体，看是否正确。

这个游戏很简单，但是蕴含的思想却是质朴的。每个问题都会将范围减少，直到特征显现，内蕴的思想就是Decision Tree算法。判定树(Decision Tree)算法是机器学习中很重要的一种算法，有文章声称该算法在ML学习中最为常用的算法，你不需要明白高深的知识就能明白算法的运行原理。

Decision Tree包括以下几个部分：

• Root：根节点，Decision Tree使用了树的概念，必然有Root属性。
• Decision Node：判定节点，该节点的数据会继续根据数据属性继续进行判定。
• Branch：从Decision Node迭代生成的子树是子树根节点的一个属性判断
• End Node：也称为Leaf Node，该节点实际上是做出决定的节点，对于样本属性的判断到Leaf Node结束。

Decision Tree分类：

Classification Tree：测试数据经过Classification Tree处理后，看结果归属于那个类别(Class)。

Regression Tree：如果测试数据的输出是数值类型，可以考虑使用Regression Tree。

CART(Classification And Regression Tree)s算法是对上面两种算法的术语涵盖。用来回归的树(Regression Tree)和用来分类的树(classification Tree)具有一定的相似性，不过其不同之处在于决定分裂(Split)的过程。

使用某些技术(Ensemble Methods)，可以构建多个Decision Tree：

Bagging Decision Tree：创建多个Decision Tree，通过替换训练集合，得到多个Decision Tree，最终得到一致的结果。

Random Forest Classification Decision Tree：使用多个Decision Tree，提升分类的准确率。

Boosted Trees：可以使用于回归(Regression)和分类(Classification)的问题。

Rotation Forest：Decision Tree生成是从训练集合特征属性中随机选取，使用PCA分析方法来构建Decision Tree。

Gini Impurity

该Gini度量是指随机选择集合中的元素，根据集合中label的分布将该元素赋予分类，该元素分类错误的几率。Gini度量在CART算法中使用，其定义如下：

其中i为label标签，fi为label为i标签的比例(Fraction)

Information Gain

这个是比较常见的信息度量，在Information Theory中经常使用，基于熵(entropy)的概念。在ID3、C4.5、C5.0中使用。其定义如下：

i为label标签，fi为label标签的比例，和上面的定义一致。Information Gain的定义如下：

Entropy和Information Gain的定义还会在后面章节里用到，确保自己正确理解了Information Gain的定义。 本文最后会有个教程，帮助大家学习下Information Gain的概念。

Decision Tree的优点和缺点：

1：易于理解和解释，简单解释就能明白Decision Tree的模型和运行原理，对于结果也比较容易解释。

2：数据预处理少，其它算法需要处理Data Normalization、Dummy Variable、Blank Value都需要进行预处理。

3：能够处理数值数据和分类数据，能够使用Decision Tree和Regression Tree就是例证。

4：使用白盒(White Box)模型，使用白盒模型能够在给定测试数据下解释测试结果分类，NN(Neural Network)分类就难以解释，至少没有Decision Tree模型明晰。

5：易于使用统计数据验证模型，能够解释模型的可用性和可信赖度

6：健壮，数据假设比较少，该模型仅仅依赖于观察到的数据，归于数据生成模型假设比较少。

7：在大数据量情况下也能很快给出结果，根据Decision Tree抽取出来的规则能够很快的运用于测试数据，运行快速。

缺点：

1：最优Decision Tree是NP难题，所以使用的Decision-Tree算法都是基于启发式(Heuristic)算法，如Greedy Algorithm等，在每个节点判断都是根据局部最优解来进行操作。启发式算法不能保证返回全局最优的Decision Tree。

2：容易产生过于复杂的树，不能很好地获得数据的通用模型，这个实际上是被称为是Overfitting，剪枝技术能够很好的避免这个问题。

3：Decision Tree的表示能力有限，只能表示有限的数据操作，如XOR、Parity、Multiplexer等操作就不易表示；导致Decision Tree变得特别大，解决方法可以使用改变问题域的表示(Propositionalisation)，或者使用更加复杂的表示方法，如Statistical Relational Learning、Inductive Logic Programming等。

4：对于包含分类变量(Categorical Variable)的数据，使用Information Gain分裂会造成较大的偏差

Extension：

Decision Tree使用And或者是Conjunction来在Decision Node进行判断，逐步得到结果；Decision Graph则是使用Or或者Disjunction来连接路径(判断条件)。在Decision Graph中，使用MML(Minimum Message length)来对Path进行处理，更细节的内容请自行查找。

关于Decision Tree的实现比较多，其中Weka中有一部分Decision Tree的经典算法实现，大家可以将weka的源码下载下来，仔细阅读下。

Decision Tree：ID3、C4.5

ID3(Iterative Dichotomiser 3)算法是判定树算法(Decision Tree Learning)的典型代表算法，由Ross Quinlan在1975年提出。ID3是作为C4.5的先驱，在Machine Learning和Natural Language Processing中使用广泛。该分类算法的核心是Entropy理论，属于数学的范畴。Entropy Theory是信息论中的名词，在上篇文章中http://isilic.iteye.com/blog/1841339有介绍，不过关于信息熵还有一些更深一些的东西。

信息熵

信息熵是指：一组数据所包含的信息量，使用概率来度量。数据包含的信息越有序，所包含的信息越低；数据包含的信息越杂，包含的信息越高。例如在极端情况下，如果数据中的信息都是0，或者都是1，那么熵值为0，因为你从这些数据中得不到任何信息，或者说这组数据给出的信息是确定的。如果数据时均匀分布，那么他的熵最大，因为你根据数据不能知晓那种情况发生的可能性比较大。

计算熵的公式为：

熵值和概率的关系如下，这个是二值情况下的概率与熵值关系，其中n=2：

实际上，信息熵表示的是信息的不确定性。当概率相同时，不确定性越大，因为所有的信息概率相同，你不能确定哪个信息出现的可能性更大；当某类别发生的概率为0或者1时，给出的结果是确定的(出现或者不出现、发生或者不发生)。这样的解释会不会更清楚点。

Information Gain(IG)，信息增益和信息熵描述的信息是一致的；描述的是对于数据集合S，将其按照其属性A切分后，获得的信息增益值。注意IG描述的是信息的增益值，当不确定性越大时，信息增益值应该是越小，反之亦然，是负相关的关系。信息增益的公式如下：

在ID3中，使用信息增益(IG)或者熵(Entropy)值来确定使用哪个属性进行判定属性，可以说是ID3算法的关键和精髓所在。ID3算法的伪码如下：

ID3算法的原理还是比较简单的，其理论基础是Entropy理论和Information Gain理论，只要深入理解了这个内容，ID3算法就不是问题。其实Machine Learning的基础是统计、概率、几何知识的考量，数学基础好的话，会在学习过程中感觉轻松些。

在Machine Learning in Action中有个章节是介绍ID3算法的，并且有完整的实现。我将代码拿过来，感兴趣的可以结合理论学习一下。

1. from math import log
2. import operator
3. def createDataSet():
4. dataSet = [[1, 1, 'yes'],
5. [1, 1, 'yes'],
6. [1, 0, 'no'],
7. [0, 1, 'no'],
8. [0, 1, 'no']]
9. labels = ['no surfacing','flippers']
10. #change to discrete values
11. return dataSet, labels
12. def calcShannonEnt(dataSet):
13. numEntries = len(dataSet)
14. labelCounts = {}
15. for featVec in dataSet: #the the number of unique elements and their occurance
16. currentLabel = featVec[-1]
17. if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
18. labelCounts[currentLabel] += 1
19. shannonEnt = 0.0
20. for key in labelCounts:
21. prob = float(labelCounts[key])/numEntries
22. shannonEnt -= prob * log(prob,2) #log base 2
23. return shannonEnt
24. def splitDataSet(dataSet, axis, value):
25. retDataSet = []
26. for featVec in dataSet:
27. if featVec[axis] == value:
28. reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
29. reducedFeatVec.extend(featVec[axis+1:])
30. retDataSet.append(reducedFeatVec)
31. return retDataSet
32. def chooseBestFeatureToSplit(dataSet):
33. numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
34. baseEntropy = calcShannonEnt(dataSet)
35. bestInfoGain = 0.0; bestFeature = -1
36. for i in range(numFeatures):        #iterate over all the features
37. featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
38. uniqueVals = set(featList)       #get a set of unique values
39. newEntropy = 0.0
40. for value in uniqueVals:
41. subDataSet = splitDataSet(dataSet, i, value)
42. prob = len(subDataSet)/float(len(dataSet))
43. newEntropy += prob * calcShannonEnt(subDataSet)
44. infoGain = baseEntropy - newEntropy     #calculate the info gain; ie reduction in entropy
45. if (infoGain > bestInfoGain):       #compare this to the best gain so far
46. bestInfoGain = infoGain         #if better than current best, set to best
47. bestFeature = i
48. return bestFeature                      #returns an integer
49. def majorityCnt(classList):
50. classCount={}
51. for vote in classList:
52. if vote not in classCount.keys(): classCount[vote] = 0
53. classCount[vote] += 1
54. sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
55. return sortedClassCount[0][0]
56. def createTree(dataSet,labels):
57. classList = [example[-1] for example in dataSet]
58. if classList.count(classList[0]) == len(classList):
59. return classList[0]#stop splitting when all of the classes are equal
60. if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
61. return majorityCnt(classList)
62. bestFeat = chooseBestFeatureToSplit(dataSet)
63. bestFeatLabel = labels[bestFeat]
64. myTree = {bestFeatLabel:{}}
65. del(labels[bestFeat])
66. featValues = [example[bestFeat] for example in dataSet]
67. uniqueVals = set(featValues)
68. for value in uniqueVals:
69. subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labels
70. myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
71. return myTree
72. def classify(inputTree,featLabels,testVec):
73. firstStr = inputTree.keys()[0]
74. secondDict = inputTree[firstStr]
75. featIndex = featLabels.index(firstStr)
76. key = testVec[featIndex]
77. valueOfFeat = secondDict[key]
78. if isinstance(valueOfFeat, dict):
79. classLabel = classify(valueOfFeat, featLabels, testVec)
80. else: classLabel = valueOfFeat
81. return classLabel
82. def storeTree(inputTree,filename):
83. import pickle
84. fw = open(filename,'w')
85. pickle.dump(inputTree,fw)
86. fw.close()
87. def grabTree(filename):
88. import pickle
89. fr = open(filename)
90. return pickle.load(fr)

代码还算清晰，chooseBestFeatureToSplit和calcShannonEnt这两个方法是ID3算法的核心，请仔细阅读代码，确定自己真正理解了熵理论和信息增益理论。

ID3算法存在的缺点：

1：ID3算法在选择根节点和内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多是属性在有些情况下这类属性可能不会提供太多有价值的信息。

2：ID3算法只能对描述属性为离散型属性的数据集构造决策树

ID3算法的局限是它的属性只能取离散值,为了使决策树能应用于连续属性值情况，Quinlan给出了ID3的一个扩展算法：即C4.5算法。C4.5算法是ID3的改进，其中离散属性值的选择依据同ID3；它对于实值变量的处理采用多重分支。C4.5算法能实现基于规则的剪枝。因为算法生成的每个叶子都和一条规则相关联，这个规则可以从树的根节点直到叶子节点的路径上以逻辑合取式的形式读出。

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

C4.5算法主要做出了以下方面的改进

1：可以处理连续数值型属性

对于离散值，C4.5和ID3的处理方法相同，对于某个属性的值连续时，假设这这个节点上的数据集合样本为total，C4.5算法进行如下处理：

• 将样本数据该属性A上的具体数值按照升序排列，得到属性序列值：{A1,A2,A3,...,Atotal}
• 在上一步生成的序列值中生成total-1个分割点。第i个分割点的取值为Ai和Ai+1的均值，每个分割点都将属性序列划分为两个子集。
• 计算每个分割点的信息增益(Information Gain),得到total-1个信息增益。
• 对分裂点的信息增益进行修正：减去log2(N-1)/|D|，其中N为可能的分裂点个数，D为数据集合大小。
• 选择修正后的信息增益值最大的分类点作为该属性的最佳分类点
• 计算最佳分裂点的信息增益率(Gain Ratio)作为该属性的Gain Ratio
• 选择Gain Ratio最大的属性作为分类属性。

其中第4、5步骤Quinlan在93年的的算法中没有体现，在96年发表文章对该算法进行改进，改进的论文可以参考这里：http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/quinlan96a.pdf。

2：用信息增益率(Information Gain Ratio)来选择属性

克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为：

其中Gain(S,A)和ID3算法中的信息增益计算相同，而SplitInfo(S,A)代表了按照属性A分裂样本集合S的广度和均匀性。

其中Si表示根据属性A分割S而成的样本子集。

3：后剪枝策略

Decision Tree很容易产生Overfitting，剪枝能够避免树高度无限制增长，避免过度拟合数据。剪枝算法比较复杂，我自己还没有学习清楚，希望大家能提供学习这个剪枝策略方法的建议。

4：缺失值处理

对于某些采样数据，可能会缺少属性值。在这种情况下，处理缺少属性值的通常做法是赋予该属性的常见值，或者属性均值。另外一种比较好的方法是为该属性的每个可能值赋予一个概率，即将该属性以概率形式赋值。例如给定Boolean属性B，已知采样数据有12个B=0和88个B=1实例，那么在赋值过程中，B属性的缺失值被赋值为B(0)=0.12、B(1)=0.88；所以属性B的缺失值以12%概率被分到False的分支，以88%概率被分到True的分支。这种处理的目的是计算信息增益，使得这种属性值缺失的样本也能处理。

我们看下C4.5算法的伪码：

1. Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)
2. Begin
3. If S为空,返回一个值为Failure的单个节点;
4. If S是由相同类别属性值的记录组成,
5. 返回一个带有该值的单个节点;
6. If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;
7. [注意未出现错误则意味着是不适合分类的记录]；
8. For 所有的属性R(Ri) Do
9. If 属性Ri为连续属性，则
10. Begin
11. sort(Ri属性值)
12. 将Ri的最小值赋给A1：
13. 将Ri的最大值赋给Am；
14. For j From 1 To m-1 Do Aj=(A1+Aj+1)/2;
15. 将Ri点的基于Aj(1<=j<=m-1划分的最大信息增益属性(Ri,S)赋给A；
16. End；
17. 将R中属性之间具有最大信息增益的属性(D,S)赋给D;
18. 将属性D的值赋给{dj/j=1,2...m}；
19. 将分别由对应于D的值为dj的记录组成的S的子集赋给{sj/j=1,2...m};
20. 返回一棵树，其根标记为D;树枝标记为d1,d2...dm;
21. 再分别构造以下树:
22. C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);
23. End C4.5

该算法流程是我从网上移过来的，对于其中和本文描述不一致的地方做了修改。原文参考这里：http://blog.sina.com.cn/s/blog_73621a3201017g7k.html

C4.5的主要点在于对于ID3的改进，可以说上面提到的四点对于Decision Tree算法来说是非常关键的，理解了这几个改进点就算是掌握了C4.5算法的根本。

C4.5的缺点：

1：算法低效，在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效

2：内存受限，适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

在weka开源软件中有个weka.classifiers.trees.J48实现了C4.5算法，可以结合该代码学习理论知识。

最后提示下C5.0算法，C5.0算法是在C4.5算法基础上的改进，wiki上表示该算法应该归属于商业应用，所以没有C4.5讨论广泛。相比较于C4.5，C5.0算法的改进点在于：

1：速度，C5.0有好几个数量级别上的速度提升

2：内存使用，比C4.5使用更加有效

3：生成Decision Tree更小(Occam's Razor)，能避免过度拟合

4：支持Boosting

5：支持权重，对于不同的样本赋予不同的权重值

6：Winnowing：支持自动去除没有帮助的属性

这个是作者的声明。尤其是前两点，刚好是克服了C4.5算法的劣势，是C4.5算法的巨大提升，算法源码在http://rulequest.com/download.html这里有下载，大家可以学习下作者声称的优势都是怎么实现的。在这里http://www.rulequest.com/see5-comparison.html有C5.0和C4.5的比较，大家也可以看下，从文章来看，C5.0确实是在很多方面都超过了C4.5。

本文关于Decision Tree的学习到此，本文介绍了最为简单和基础的ID3算法；随后学习了C4.5相比于ID3的优势及实现思路；最后比较了C5.0的改进；对于Decision Tree算法有了基本的认识，为后面学习Decision Tree算法提供了良好的基础。

Decision Tree：CART、剪枝

决策树的重要性和入门可以参考前面两篇文章，尤其是入门的ID3算法：

http://isilic.iteye.com/blog/1841339、http://isilic.iteye.com/blog/1844097

Classification And Regression Tree(CART)也是决策树的一种，并且是非常重要的决策树。除去上文提到的C4.5外，CART算法也在Top Ten Machine Learning Algorithm中，可见决策树的重要性和CART算法的重要性。

CART的特性主要有下面三个，其实这些特性都不完全算是CART的特性，只是在CART算法中使用，并且作为算法的重要基础：

1：二分(Binary Split)：在每次判断过程中，都是对观察变量进行二分。

2：单变量分割(Split Based on One Variable)：每次最优划分都是针对单个变量。

3：剪枝策略：CART算法的关键点，也是整个Tree-Based算法的关键步骤。

CART能处理Classification Tree和Regression Tree，在建树过程中有不一样的地方，我们分别来看下。

我们先看Classification Tree的建树过程：

ID3,C4.5算法是利用熵理论和信息增益(率)来决定属性分割策略；CART则是利用Gini Index(GINI 指数)来定义衡量划分的好坏。和熵类似，数据内包含的类别越杂乱，GINI指数就越大，有没有感觉跟熵的概念类似。下面我们来学习下Gini Index的内容：

其中Pj是类j在T中的相对频率，当类j在T中是倾斜时，gini(T)才会最小。

比较熵理论和gini指数，让T中各类别出现的概率一致时，熵最大，Gini指数也是最大，但是两者的逼近速度是不一样的，从下图中可以看出来：

其中MisClassification Rate也是一种衡量，感兴趣的同学可以自行学习下。

衡量出某个属性的Gini指数后，可以得到Gini Split数据如下：

这个有没有和信息增益相似，这个可以称为是Gini信息增益，在CART中，选择其中最小的Gini信息增益作为结点划分决策树。

对于CART，i=2，可以得到在Binary Split情况下的Gini信息增益：

在weka中有信息增益weka.attributeSelection.InfoGainAttributeEval和信息增益率 weka.attributeSelection.GainRatioAttributeEval 的实现，可以看下实现原理。

Regression Tree的建树过程。

对于回归树，没有分类数据，只有根据观察数据得出的值，注意观察值取值是连续，在这种情况下Classification Tree的最优划分规则就无能为力。

在这种情况下，回归树可以使用 最小剩余方差(Squared Residuals Minimization)来决定Regression Tree的最优划分，该划分准则是期望划分之后的子树误差方差最小：

决策树停止生长的条件，这个可以看做是预剪枝过程：

树不能无限增长，我们可以设定条件，当树达到某个停止条件时，停止树增长，常用的停止条件（Stopping Criteria）有如下几个：

• 1：子树上的样本数据都归属于同一个类别
• 2：达到最大数深度(Maximum Tree Depth)
• 3：子树节点的样本数量要少于某个门限值，或者小于一定的比例
• 4：子树节点再按照最优划分标准切分，其子树的样本数量小于某个门限值，或者小于一定的比例值
• 5：最优划分(Split)标增益小于某个门限值，如误差值等

这些方法都可以让树提前停止增长，防止树无限制生成，避免一定程度上的过拟合。

剪枝理论，决策树的剪枝在上一节中没有仔细讲，趁这个机会学习了剪枝的基础理论，这里会详细学习。

决策树为什么(WHY)要剪枝？原因是避免决策树过拟合(Overfitting)样本。前面的算法生成的决策树非常详细并且庞大，每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话，你会发现对于训练样本而言，这个树表现完好，误差率极低且能够正确得对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学习，成为决策树的部分，但是对于测试数据的表现就没有想象的那么好，或者极差，这就是所谓的过拟合(Overfitting)问题。Quinlan教授试验，在数据集中，过拟合的决策树的错误率比经过简化的决策树的错误率要高。

现在问题就在于，如何(HOW)在原生的过拟合决策树的基础上，生成简化版的决策树？可以通过剪枝的方法来简化过拟合的决策树。剪枝可以分为两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning),下面我们来详细学习下这两种方法：

PrePrune：预剪枝，及早的停止树增长，方法可以参考见上面树停止增长的方法。

PostPrune：后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。

其实剪枝的准则是如何确定决策树的规模，可以参考的剪枝思路有以下几个：

1：使用训练集合(Training Set）和验证集合(Validation Set)，来评估剪枝方法在修剪结点上的效用

2：使用所有的训练集合进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能，如使用Chi-Square（Quinlan，1986）测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能。

3：使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(Minimum Description Length)准则。

我们先看下使用思路一来解决问题的集中后剪枝方法：

Reduced-Error Pruning(REP,错误率降低剪枝）

该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：

1：删除以此结点为根的子树

2：使其成为叶子结点

3：赋予该结点关联的训练数据的最常见分类

4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点

因为训练集合的过拟合，使得验证集合数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集合的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集合的精度)

REP是最简单的后剪枝方法之一，不过在数据量比较少的情况下，REP方法趋于过拟合而较少使用。这是因为训练数据集合中的特性在剪枝过程中被忽略，所以在验证数据集合比训练数据集合小的多时，要注意这个问题。

尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够解决一定程度的过拟合问题。

Pessimistic Error Pruning(PEP，悲观剪枝）

先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项式分布，并计算它的标准差。对于给定的置信区间，采用下界估计作为规则性能的度量。这样做的结果，是对于大的数据集合，该剪枝策略能够非常接近观察精度，随着数据集合的减小，离观察精度越来越远。该剪枝方法尽管不是统计有效的，但是在实践中有效。

PEP为了提高对测试集合的预测可靠性，PEP对误差估计增加了连续性校正(Continuity Correction)。PEP方法认为，如果： 

成立，则Tt应该被剪枝，上式中：

其中，e(t)为结点t出的误差；i为覆盖Tt的叶子结点；Nt为子树Tt的叶子树；n(t)为在结点t处的训练集合数量。PEP采用自顶向下的方式，如果某个非叶子结点符合上面的不等式，就裁剪掉该叶子结点。该算法被认为是当前决策树后剪枝算法中经度比较高的算法之一，但是饿存在有缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与先剪枝出现同样的问题，将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。

虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度,。两外PEP方法不需要分离训练集合和验证机和，对于数据量比较少的情况比较有利。再者其剪枝策略比其它方法相比效率更高，速度更快。因为在剪枝过程中，树中的每颗子树最多需要访问一次，在最坏的情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。

可能有同学会对上面的那个不等式有疑问，可以参考这篇文章http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html 中关于PEP剪枝部分内容。PEP方法实际上是将结点误差数目看做二项式分布，根据期望和方差得到的结果。

Cost-Complexity Pruning(CCP、代价复杂度)

CCP方法包含两个步骤：

1：从原始决策树T0开始生成一个子树序列{T0、T1、T2、...、Tn},其中Ti+1是从Ti总产生，Tn为根节点

2：从子树序列中，根据树的真实误差估计选择最佳决策树。

在步骤一中，生成子树序列{T0、T1、T2、...、Tn}的基本思想是从T0开始，裁剪Ti中关于训练数据集合误差增加最小的分支来得到Ti+1。实际上当一棵树T在结点t出剪枝时，它的误差增加直观上认为是:

其中R(t)为在结点t的子树被裁剪后结点t的误差，R(Tt)为在结点t的子树没被裁剪时子树T的误差。不过剪枝后T的叶子树减少了|L(Ti)|-1，其中|L(Ti)|为子树Ti的叶子树，也就是说T的复杂性降低。因此考虑到树的复杂性因素，树分支被裁剪后误差增加率可以由下式决定：

Ti+1就是选择Ti中具有最小\alpha值所对应的剪枝树

如何从第一步骤产生的子树序列{T0、T1、T2、...、Tn}中选择出最佳决策树是CCP方法的第二步骤的关键。通常可以采用V-交叉验证(V-fold Cross-Validation)和基于独立剪枝数据集两种方法，这两种方法可以参考(Classification And Regression Trees,Breiman et.al)。当使用基于独立数据集剪枝时，和REP方法相比，CCP选择出来的最有决策树，不是从原始决策树T的所有可能子树中得到，所以有可能会找到到最有决策树。

其它如Minimum Error Pruning(MEP)，Critical Value Pruning(CVP)，Optimal Pruning(OPP)，Cost-Sensitive Decision Tree Pruning(CSDTP)等方法，这些剪枝方法各有利弊，关注不同的优化点，感兴趣的同学可以学习下。

剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够保留最重要的属性划分，差别不大。反而是剪枝方法对于最优树的生成更为关键。重点理解这些剪枝方法的理论，对于最终最优树的生成是有好处的，其中上篇文章http://isilic.iteye.com/blog/1844097中C4.5使用了PEP剪枝方法，本文的CART使用了CCP的剪枝方法，实际上，不应该对于算法使用的剪枝方法过于追根究底，而是应该对于剪枝过程理解透彻，对于在何种场景下对于不同的数据类型使用何种的剪枝方法能够获得最优树的选择，才是真正理解了剪枝的理论和重要性。

下面再回到CART算法，看下算法的优点：

1：没有分布假设、没有数据同质性(Homogeneity)要求

2：观测值属性可以是分类、离散、连续的混合。

4：对异常值(Outlier)值不敏感，异常值一般会被处理掉

5：在面对缺失值、变量多等问题时，CART显得给长稳健(ROBUST)

缺点：

1：非基于概率模型，很难对决策树的结果的准确程度做度量

CART算法的内容就到这里，再扩充下Decision Tree算法的内容。上面的这些决策树算法都是单变量(Univariate)算法，实际上还有多变量(MultiVariate)算法，只是使用比较少。在Machine Learning In Action第九章中有关于Tree-Based Regression，是讲解CART中Regression树的内容。尤其是在文章中间提到了多变量回归树算法，每次的判定点有两个变量组成，对于本文的内容是个非常好的扩充，可以学习下。另外要提一下的是该章节中讲解的CART生成比较简单，尤其是生成最大树的方法；不过树生成和数剪枝(包括预剪枝和后剪枝)都有体现，算是分不错的代码文档；感兴趣的可以直接在这份代码上修改。

后面附加了份关于决策树的概论内容综述，地址参见：http://www.ise.bgu.ac.il/faculty/liorr/hbchap9.pdf 。内容比较全，包括划分标准、剪枝方法，不过不够深入，只有公式和简单的介绍，如果有基础的话话，倒是份不错的文档。如果不能观看的话，文后有附件。

另外在百度文库上有个PPT不错：http://wenku.baidu.com/view/415c3cc19ec3d5bbfd0a7464.html，供参考。

其实本文的重点是剪枝的内容，除去这点，CART算法使用的GINI指数内容也是本文的重点。

本文内容结束。

以上内容转自：http://isilic.iteye.com/blog/1841339

http://isilic.iteye.com/blog/1844097

http://isilic.iteye.com/blog/1846726