《机器学习实战》基于信息论的三种决策树算法(ID3,C4.5,CART)

分析分类回归树的递归建树过程，不难发现它实质上存在着一个数据过度拟合问题。在决策树构造时，由于训练数据中的噪音或孤立点，许多分枝反映的是训练数据中的异常，使用这样的判定树对类别未知的数据进行分类，分类的准确性不高。因此试图检测和减去这样的分支，检测和减去这些分支的过程被称为树剪枝。树剪枝方法用于处理过分适应数据问题。通常，这种方法使用统计度量，减去最不可靠的分支，这将导致较快的分类，提高树独立于训练数据正确分类的能力。

决策树常用的剪枝常用的简直方法有两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。预剪枝是根据一些原则及早的停止树增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、不纯度指标下降的最大幅度小于用户指定的幅度等。预剪枝的核心问题是如何事先指定树的最大深度，如果设置的最大深度不恰当，那么将会导致过于限制树的生长，使决策树的表达式规则趋于一般，不能更好地对新数据集进行分类和预测。除了事先限定决策树的最大深度之外，还有另外一个方法来实现预剪枝操作，那就是采用检验技术对当前结点对应的样本集合进行检验，如果该样本集合的样本数量已小于事先指定的最小允许值，那么停止该结点的继续生长，并将该结点变为叶子结点，否则可以继续扩展该结点。

后剪枝则是通过在完全生长的树上剪去分枝实现的，通过删除节点的分支来剪去树节点，可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。后剪枝操作是一个边修剪边检验的过程，一般规则标准是：在决策树的不断剪枝操作过程中，将原样本集合或新数据集合作为测试数据，检验决策树对测试数据的预测精度，并计算出相应的错误率，如果剪掉某个子树后的决策树对测试数据的预测精度或其他测度不降低，那么剪掉该子树。

关于后剪枝的具体理论可以参考“数据挖掘十大经典算法--CART: 分类与回归树”剪枝部分。
（4）依旧是结合上边的图形进行解释说明

上面的训练集有4个属性，即属性集合A={OUTLOOK, TEMPERATURE, HUMIDITY, WINDY}；而类标签有2个，即类标签集合C={Yes, No}，分别表示适合户外运动和不适合户外运动，其实是一个二分类问题。
我们已经计算过信息增益，这里直接列出来，如下所示：
数据集D包含14个训练样本，其中属于类别“Yes”的有9个，属于类别“No”的有5个，则计算其信息熵：

下面对属性集中每个属性分别计算信息熵，如下所示：

根据上面的数据，我们可以计算选择第一个根结点所依赖的信息增益值，计算如下所示：

接下来，我们计算分裂信息度量H(V)：

属性OUTLOOK有3个取值，其中Sunny有5个样本、Rainy有5个样本、Overcast有4个样本，则

属性TEMPERATURE有3个取值，其中Hot有4个样本、Mild有6个样本、Cool有4个样本，则

属性HUMIDITY有2个取值，其中Normal有7个样本、High有7个样本，则

属性WINDY有2个取值，其中True有6个样本、False有8个样本，则

根据上面计算结果，我们可以计算信息增益率，如下所示：

根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点进行分裂。

4：CART算法

       创建分类树递归过程中，CART每次都选择当前数据集中具有最小Gini信息增益的特征作为结点划分决策树。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支、规模较大，CART算法的二分法可以简化决策树的规模，提高生成决策树的效率。下面是CART算法与C4.5相比的主要差别

        1：CART只能为二叉树，而C4.5可以为多叉树
        2：CART中的输入变量和输出变量可以是分类型也可以是数值型，而C4.5的输出变量只能是分类型

        3：CART 使用GINI系数作为变量的不纯度量，而C4.5采用信息增益率（ID3使用信息增益作为属性选择标准）

        4：如果目标变量是标称的，并且具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别

        5：如果目标变量是连续的，则CART算法找出一组基于树的回归方法来预测目标变量

        6：对于缺失值得处理方法不同，CART采用代理测试来估计测试的输出值，而C4.5直接将其分配到该分支中概率最大的分类

        7：对决策树的剪枝方法不同，CART采用代价复杂度模型，通过交叉验证来估计对预测样本集的误分类损失，产生最小交叉验证误分类估计树。而C4.5启发式的调整在训练集样本上估计出的误差率，使用调整的误差率，以找出评分函数最大化的树

        CART与C4.5的不同之处是节点分裂建立在GINI指数这个概念上，GINI指数主要是度量数据划分或训练数据集D的不纯度为主。GINI值越小，表明样本的纯净度越高（即该样本只属于同一类的概率越高）。衡量出数据集某个特征所有取值的Gini指数后，就可以得到该特征的Gini Split info，也就是GiniGain。不考虑剪枝情况下，分类决策树递归创建过程中就是每次选择GiniGain最小的节点做分叉点，直至子数据集都属于同一类或者所有特征用光了。

因为CART二分的特性，当训练数据具有两个以上的类别，CART需考虑将目标类别合并成两个超类别，这个过程称为双化。

        1、Gini指数的概念：

GINI指数是一种不等性度量，通常用来度量收入不平衡，可以用来度量任何不均匀分布，是介于0~1之间的数，0-完全相等，1-完全不相等。分类度量时，总体内包含的类别越杂乱，GINI指数就越大(跟熵的概念很相似)。

对于一个数据集T，其Gini计算方式为：

 （n表示类别数，pj表数据集样本不同类别的概率）

       2、GiniGain

           衡量出某个特征所有取值的Gini指数就可以得到Gini Split Info：

           i表示特征的第i个取值

           ID3算法中的信息增益相似，这个可以称为是Gini信息增益--Gini Gain。对于CART，i=（1,2），得到在Binary Split情况下的Gini信息增益：                                                     

       3、属性选择

            (1)分类树的属性选择

                对于CART分类树的属性选择，针对属性类型分为分类型和数值型，方法有所不同

                    a、对于分类型属性，由于CART只能建立二叉树，对于取多个值的属性变量，需要将多类别合并成两个类别，形成“超类”，然后计算两“超类”下样本测试输出取值的差异性

                   b、对于数值型属性，处理方法如下

                  （1） 对特征的取值进行升序排序

                  （2） 两个特征取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的GiniGain。优化算法就是只计算分类属性发生改变的那些特征取值

                  （3）选择GiniGain最小的分裂点作为该特征的最佳分裂点（注意，若修正则此处需对最佳分裂点的Gini Gain减去log2(N-1)/|D|（N是连续特征的取值个数，D是训练数据数目）

<span style="font-size:18px;">def binSplitDataSet(dataSet, feature, value):   mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]   mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]   return mat0,mat1  </span>

                理想的分组是将两组样本测试输出的取值的差异性总和达到最小，即纯度最大，也就是使两组输出变量取值的差异性下降最快“纯度”增加最快

           (2)回归树的属性选择

                回归树确定当前最佳分组变量的策略与分类树相同，主要不同在于度量节点测试输出值差异性的指标有所不同，由于回归树的测试输出为数值型，因此方差是最理想的指标其定义为：

             正是因为CART树是二叉树，所以对于样本的有N>=3个取值的离散特征的处理时也只能有两个分支，这就要通过组合人为的创建二取值序列并取GiniGain最小者作为树分叉决策点。如某特征值具有['young','middle','old']三个取值,那么二分序列会有如下3种可能性(空集和满集在CART分类中没有意义):

                 [(('young',), ('middle', 'old')), (('middle',), ('young', 'old')), (('old',), ('young', 'middle'))]

            采用CART算法，就需要分别计算按照上述List中的二分序列做分叉时的Gini指数，然后选取产生最小的GINIGain的二分序列做该特征的分叉二值序列参与树构建的递归。如果某特征取值有4个，那么二分序列组合就有7种，5个取值就有15种组合，创建多值离散特征二分序列组合可采用Python的itertools包，程序如下：

<span style="font-size:18px;">from itertools import *   
import pdb   
def featuresplit(features):   count = len(features)   featureind = range(count)   featureind.pop(0) #get value 1~(count-1)  combiList = []   for i in featureind:   com = list(combinations(features, len(features[0:i])))   combiList.extend(com)   combiLen = len(combiList)   featuresplitGroup = zip(combiList[0:combiLen/2], combiList[combiLen-1:combiLen/2-1:-1])   return featuresplitGroup   
if __name__ == '__main__':   test= range(3)   splitGroup = featuresplit(test)   print 'splitGroup', len(splitGroup), splitGroup   test= range(4)   splitGroup = featuresplit(test)   print 'splitGroup', len(splitGroup),splitGroup   test= range(5)   splitGroup = featuresplit(test)   print 'splitGroup', len(splitGroup),splitGroup   test= ['young','middle','old']   splitGroup = featuresplit(test)   print 'splitGroup', len(splitGroup),splitGroup</span>

        因此CART不适用于离散特征有多个取值可能的场景。此时，若定要使用CART，则最好预先人为的将离散特征的取值缩减。

        那么对于二分后的左右分支，如果特征取值tuple中元素多于2个，该特征是否还要继续参与当前子数据集的二分呢？

        我认为需要，因此该特征继续参与分类决策树递归，直至左右分支上该特征的取值都是唯一的（即不再包含该特征）。那么离散特征的datasplit函数就应该：如果按照当前分支特征分叉后，分支上特征取值tuple>=2，则分支子数据集保留该特征，该tuple继续参与上的树构建的递归；否则分支子数据集删除该特征。

def splitDataSet(dataSet, axis, valueTuple):   '''return dataset satisfy condition dataSet[i][axis] == valueTuple, and remove dataSet[i][axis] if len(valueTuple)==1'''  retDataSet = []   length = len(valueTuple)   if length ==1:   for featVec in dataSet:   if featVec[axis] == valueTuple[0]:   reducedFeatVec = featVec[:axis]     #chop out axis used for splitting  reducedFeatVec.extend(featVec[axis+1:])   retDataSet.append(reducedFeatVec)   else:   for featVec in dataSet:   if featVec[axis] in valueTuple:   retDataSet.append(featVec)   return retDataSet

       分析分类回归树的递归建树过程，不难发现它实质上存在着一个数据过度拟合问题。在决策树构造时，由于训练数据中的噪音或孤立点，许多分枝反映的是训练数据中的异常，使用这样的判定树对类别未知的数据进行分类，分类的准确性不高。因此试图检测和减去这样的分支，检测和减去这些分支的过程被称为树剪枝。树剪枝方法用于处理过分适应数据问题。通常，这种方法使用统计度量，减去最不可靠的分支，这将导致较快的分类，提高树独立于训练数据正确分类的能力。决策树常用的剪枝常用的简直方法有两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)。预剪枝是根据一些原则及早的停止树增长，如树的深度达到用户所要的深度、节点中样本个数少于用户指定个数、不纯度指标下降的最大幅度小于用户指定的幅度等；后剪枝则是通过在完全生长的树上剪去分枝实现的，通过删除节点的分支来剪去树节点，可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。

CART常采用事后剪枝方法，构建决策树过程中的第二个关键就是用独立的验证数据集对训练集生长的树进行剪枝。

关于后剪枝的具体理论可以参考“数据挖掘十大经典算法--CART: 分类与回归树”剪枝部分。

三种决策树算法的Python实现

       1：ID3算法

#coding=utf-8
'''
'''
from math import log
import operatordef createDataSet():dataSet =[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels = ['no surfacing','flippers'] #分类的属性return dataSet,labels#计算给定数据的香农熵
def calcShannonEnt(dataSet):numEntries = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1] #获得标签#构造存放标签的字典if currentLabel not in labelCounts.keys():labelCounts[currentLabel]=0labelCounts[currentLabel]+=1 #对应的标签数目+1#计算香农熵shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key])/numEntriesshannonEnt -=prob*log(prob,2)return shannonEnt#划分数据集,三个参数为带划分的数据集，划分数据集的特征，特征的返回值
def splitDataSet(dataSet,axis,value):  retDataSet = []for featVec in dataSet:if featVec[axis] ==value:#将相同数据集特征的抽取出来reducedFeatVec = featVec[:axis]reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)return retDataSet #返回一个列表#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):numFeature = len(dataSet[0])-1baseEntropy = calcShannonEnt(dataSet)bestInfoGain = 0.0beatFeature = -1for i in range(numFeature):featureList = [example[i] for example in dataSet] #获取第i个特征所有的可能取值uniqueVals = set(featureList)  #从列表中创建集合，得到不重复的所有可能取值ֵnewEntropy = 0.0for value in uniqueVals:subDataSet = splitDataSet(dataSet,i,value)   #以i为数据集特征，value为返回值，划分数据集prob = len(subDataSet)/float(len(dataSet))   #数据集特征为i的所占的比例newEntropy +=prob * calcShannonEnt(subDataSet)   #计算每种数据集的信息熵infoGain = baseEntropy- newEntropy#计算最好的信息增益，增益越大说明所占决策权越大if (infoGain > bestInfoGain):bestInfoGain = infoGainbestFeature = ireturn bestFeature#递归构建决策树
def majorityCnt(classList):      classCount = {}for vote in classList:if vote not in classCount.keys():classCount[vote]=0classCount[vote]+=1sortedClassCount = sorted(classCount.iteritems(),key =operator.itemgetter(1),reverse=True)#排序，True升序return sortedClassCount[0][0]  #返回出现次数最多的#创建树的函数代码
def createTree(dataSet,labels):     classList = [example[-1]  for example in dataSet]if classList.count(classList[0])==len(classList):#类别完全相同则停止划分return classList[0]if len(dataSet[0]) ==1:             #遍历完所有特征值时返回出现次数最多的return majorityCnt(classList)bestFeat = chooseBestFeatureToSplit(dataSet)   #选择最好的数据集划分方式bestFeatLabel = labels[bestFeat]   #得到对应的标签值myTree = {bestFeatLabel:{}}del(labels[bestFeat])      #清空labels[bestFeat],在下一次使用时清零featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues)for value in uniqueVals:subLabels =labels[:]#递归调用创建决策树函数myTree[bestFeatLabel][value]=createTree(splitDataSet(dataSet,bestFeat,value),subLabels)return myTree  if __name__=="__main__":dataSet,labels = createDataSet()print createTree(dataSet,labels)

     2：C4.5算法

    3：CART算法
待续...............


吐槽一下：博主为了整理这篇博客也是整了好几天，有总结不到位或者错的地方请大家指正，还有C4.5和CART算法的Python代码会在后续更新，哪位网友如果有现成的代码的话也可以留言让博主参考一下，谢谢