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

决策树经常使用的剪枝经常使用的简直方法有两种：预剪枝(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需考虑将目标类别合并成两个超类别，这个过程称为双化。

        一、Gini指数的概念：

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

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

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

       二、GiniGain

           衡量出某个特征全部取值的Gini指数就能够获得Gini Split Info：

           i表示特征的第i个取值

           ID3算法中的信息增益类似，这个能够称为是Gini信息增益--Gini Gain。对于CART，i=（1,2），获得在Binary Split状况下的Gini信息增益：                                                     

       三、属性选择

            (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 operator

def 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]=0
        labelCounts[currentLabel]+=1 #对应的标签数目+1
    #计算香农熵
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -=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])-1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    beatFeature = -1
    for i in range(numFeature):
        featureList = [example[i] for example in dataSet] #获取第i个特征全部的可能取值
        uniqueVals = set(featureList)  #从列表中建立集合，获得不重复的全部可能取值ֵ
        newEntropy = 0.0
        for 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 = infoGain
            bestFeature = i
    return bestFeature

#递归构建决策树
def majorityCnt(classList):      
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=0
        classCount[vote]+=1
    sortedClassCount = 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代码会在后续更新，哪位网友若是有现成的代码的话也能够留言让博主参考一下，谢谢