本文共 11640 字，大约阅读时间需要 38 分钟。

      CART又叫分类与回归树，既可以用来分类，也可以用来回归。CART假设决策树是二叉树，内部节点特征取值是“是”和“否”，左分支取值是“是”的分支，右分支取值是“否的分支，这样的决策树等价于递归的二分每个特征，将特征空间划分为有线个单元，并在这些单元上确定预测的概率分布。对回归树用平方误差最小化的准则，对分类树用基尼指数最小化的准则，进行特征选择，生成二叉树。
1、回归树的生成
      假设X和Y分别为输入变量和输出变量，并且Y是连续变量，给定训练数据集：

$$D=\{ (x_1,y_1),(x_2,y_2),..,(x_n,y_n)\}$$

      一个回归树对应特征空间的一个划分以及在划分单元上的输出值。假设将特征空间划分为M个单元，并且每个单元上有一个固定的输出值$c_m$，于是回归树的模型可以表示为：

$$f(x)=\sum_{m=1}^M c_mI(x\in R_m)$$

      当输入空间的划分确定时，可以用平方误差$\sum_{x_i\in R_m} (y_i-f(x_i))^2$来表示回归树对于训练数据的预测误差，可以得出，单元$R_m$上的$c_m$的最优值$\hat{c}_m$是$R_m$上所有输入实例$x_i$对应的输出$y_i$的均值，即;

$$\hat{c}_m=ave(y_i|x_i\in R_m)$$

      如何对输入空间进行划分？采用启发式方法，选择第j个变量$x^{(j)}$和它的取值s，作为切分变量和切分点，并定义两个区域：

$$R_1(j,s)=\{x|x^{(j)}<=s\}和R_2(j,s)=\{x|x^{(j)}>=s\}$$
然后寻找最优切分变量j和最优切分点s，具体的求解：
$$min_{(j,s)}=[min_{c_1} \sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2} \sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$$
对于固定的输入变量j可以找到最优切分点s。
$$\hat{c}_1=ave(y_i|x_i\in R_1(j,s))和\hat{c}_2=ave(y_i|x_i\in R_2(j,s))$$

      遍历所有输入变量，找到最优切分变量和切分点，依次将输入空间划分为两个区域。接着，对每个区域重复上述过程，知道满足停止条件为止，这样就生成了一科回归树，这样的回归树称为最小二乘回归树。

2、分类树的生成
(1)基尼指数：
      分类问题中，假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为：

$$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$
对于给定的样本集合D，其基尼指数为：
$$Gini(D)=1-\sum_{k=1}^K (\frac{|C_k|} {|D|}\quad)^2$$
其中$C_k$是D中属于第k类的样本子集，K是类的个数。
如果样本集合D根据特征A是否取某一可能值a被分割成$D_1和D_2$两部分，即
$$D_1=\{(x,y)\in D|A(x)=a \},D_2=D-D_1$$
则在特征A的条件下，集合D的基尼指数定义为：
$$Gini(D,A)=\frac{|D_1|}{|D|} \quad Gini(D_1)+\frac{|D_2|}{|D|} \quad Gini(D_2)$$
      基尼指数$Gini(D)$表示集合D的不确定性，基尼指数$Gini(D,A)$表示经A=a分割后集合D的不确定性，基尼指数越大，样本的不确定性就越大，这一点和熵相似。
(2)生成分类树
      设节点的训练数据集为D，对每一个特征A，对其可能取得每个值a，根据样本点A=a的测试为“是”或者“否”将D分割为D1和D2两部分，并计算A=a时的基尼指数。在所有可能的特征A以及它所有的切分点a中，选出基尼指数最小的特征及对应的切分点作为最优特征和最优切分点，依最优特征和最优切分点从现节点生成两个子节点，将训练数据集分配到两个子节点中去，对两个自己点递归调用上述步骤，直到满足条件为止，生成CART决策树。
3、实现回归树

#coding=utf-8import numpy as np#创建测试数据集'  def createDataSet():         dataSet = [[1.0, 1.0, 1.0],               [1.0, 1.0, 2.0],               [1.0, 0.0, 0.0],               [0.0, 1.0, 2.0],               [0.0, 1.0, 1.0]]        return np.array(dataSet)#功能：将数据集按某特征列的某一取值换分为左右两个子数据集def binarySplitDataSet(dataset,feature,value):    '''    输入：数据集，数据集中某一特征列，该特征列中的某个取值        输出：左右子数据集    '''    # nonzeros(a):返回数组a中值不为零的元素的下标，它的返回值是一个长度为a.ndim(数组a的轴数)的元组，    #            元组的每个元素都是一个整数数组，其值为非零元素的下标在对应轴上的值。    # dataset[:,feature]:返回dataset矩阵的第feature列    #    matLeft = dataset[np.nonzero(dataset[:,feature] <= value)[0],:]    matRight = dataset[np.nonzero(dataset[:,feature] > value)[0],:]    return matLeft,matRight#--------------回归树所需子函数---------------##功能：求数据集输出列的均值# 它负责生成叶节点。当chooseBestSplit()函数确定不再对数据进行切分时，将调用该函数来得到叶节点的模型。# 在回归树中，该模型其实就是目标变量的均值。def regressLeaf(dataset):    '''    输入：数据集        输出：对应数据集的叶节点    '''    return np.mean(dataset[:,-1])#功能：求数据集划分左右子数据集的平方误差# 该函数在给定数据上计算目标变量的平方误差。当然也可以先计算出均值，然后计算每个差值再平方。# 但这里直接调用均方差函数var ()更加方便。因为这里需要返回的是总方差，所以要用均方差乘以数据集中样本的个数。def regressErr(dataset):    '''    输入：数据集(numpy.mat类型)        输出: 数据集划分后的误差平方和    '''    #由于回归树中用输出的均值作为叶节点，所以在这里求误差平方和实质上就是方差    # var()：求方差    return np.var(dataset[:,-1]) * np.shape(dataset)[0]def regressData(filename):    fr = open(filename)    return pickle.load(fr)#--------------回归树子函数  END  --------------##找到数据的最佳二元切分方式，如果找不到一个“好”的二元切分，该函数返回None并同时调用# regressLeaf()方法来产生叶节点，叶节点的值也将返回None。def chooseBestSplit(dataset,leafType=regressLeaf,errType=regressErr,threshold=(0.01,1)):#函数做为参数，挺有意思    thresholdErr = threshold[0]   # 容许的误差下降值，用于控制函数的停止时机    thresholdSamples = threshold[1] # 切分的最少样本数        #当数据中输出值都相等时，feature = None,value = 输出值的均值（叶节点）    if len(set(dataset[:,-1])) == 1:        return None,leafType(dataset)    m,n = np.shape(dataset)        Err = errType(dataset) # 计算没有切分时数据集的平方误差        bestErr = np.inf       # 保存最小的误差，初始值为无穷大的正数    bestFeatureIndex = 0   # 保存最佳特征，即切分变量    bestFeatureValue = 0   # 保存特征的最佳值，即切分点    # 遍历找出最佳切分变量和切分点    for featureindex in range(n-1):        for featurevalue in dataset[:,featureindex]:                        matLeft,matRight = binarySplitDataSet(dataset,featureindex,featurevalue)                       if np.shape(matLeft)[0] > 1 and np.shape(matRight)[0] > 1:                              temErr = errType(matLeft) + errType(matRight)                                                   if temErr < bestErr:                    bestErr = temErr                                    bestFeatureIndex = featureindex                    bestFeatureValue = featurevalue    #检验在所选出的最优划分特征及其取值下，误差平方和与未划分时的差是否小于阈值，若是，则不适合划分    if (Err-bestErr) < thresholdErr:        return None,leafType(dataset)        matLeft,matRight = binarySplitDataSet(dataset,bestFeatureIndex,bestFeatureValue)    #检验在所选出的最优划分特征及其取值下，划分的左右数据集的样本数是否小于阈值，若是，则不适合划分    if (np.shape(matLeft)[0] < thresholdSamples) or (np.shape(matRight)[0] < thresholdSamples):        return None,leafType(dataset)        return bestFeatureIndex,bestFeatureValue#建立回归树或模型树def createCARTtree(dataset,leafType=regressLeaf,errType=regressErr,threshold=(0.01,1)):    '''    输入：数据集dataset，叶子节点形式leafType：regressLeaf（回归树）、modelLeaf（模型树）         损失函数errType:误差平方和也分为regressLeaf和modelLeaf、用户自定义阈值参数：         误差减少的阈值和子样本集应包含的最少样本个数      输出：以字典嵌套数据形式返回子回归树或子模型树或叶结点    '''    feature,value = chooseBestSplit(dataset,leafType,errType,threshold)    #当不满足阈值或某一子数据集下输出全相等时，返回叶节点    if feature == None:         return value    returnTree = {}    returnTree['bestSplitFeature'] = feature    returnTree['bestSplitFeatValue'] = value    leftSet,rightSet = binarySplitDataSet(dataset,feature,value)    returnTree['left'] = createCARTtree(leftSet,leafType,errType,threshold)    returnTree['right'] = createCARTtree(rightSet,leafType,errType,threshold)    return returnTreeif __name__ == '__main__':    dataset=createDataSet()        tree=createCARTtree(dataset,leafType=regressLeaf,errType=regressErr,threshold=(0.01,1))    print tree  

4、实现分类树

#coding=utf-8import numpy as npfrom itertools import *# 创建数据集,第一列为样本名称，最后一列为类别，中间为特征# 特征名称如下:# ["temperature","cover","viviparity","egg","fly","water","leg","hibernate"]def createDataSet():      dateset=[["human","constant","hair","true","false","false","false","true","false","mammal"],             ["python","cold_blood","scale","false","true","false","false","false","true","reptile"],             ["salmon","cold_blood","scale","false","true","false","true","false","false","fish"],             ["whale","constant","hair","true","false","false","true","false","false","mammal"],             ["frog","cold_blood","none","false","true","false","sometime","true","true","amphibious"],             ["lizard","cold_blood","scale","false","true","false","false","true","false","reptile"],             ["bat","constant","hair","true","false","true","false","true","false","mammal"],             ["cat","constant","skin","true","false","false","false","true","false","mammal"],             ["shark","cold_blood","scale","true","false","false","true","false","false","fish"],             ["turtle","cold_blood","scale","false","true","false","sometime","true","false","reptile"],             ["pig","constant","bristle","true","false","false","false","true","true","mammal"],             ["eel","cold_blood","scale","false","true","false","true","false","false","fish"],             ["salamander","cold_blood","none","false","true","false","sometime","true","true","amphibious"]]    labels=["temperature","cover","viviparity","egg","fly","water","leg","hibernate"]    return dateset,labels# 计算数据集的基尼系数def calGini(dataSet):    numEntries = len(dataSet)    labelCounts={}    for featVec in dataSet:         currentLabel = featVec[-1]        if currentLabel not in labelCounts.keys():            labelCounts[currentLabel] = 0        labelCounts[currentLabel] += 1    gini=1    for label in labelCounts.keys():        prop=float(labelCounts[label])/numEntries        gini -=prop*prop    return gini'''CART每一个分支都是二分的，当特征值个数大于两个的时候，需要考虑特征值的组合得到两个“超级特征值”作为CART的分支；当然我们也可以偷懒，每次只取多个特征值的一个，挑出最优的一个和剩下的分别作为一个分支，但无疑这得到的cart不是最优的'''# 传入的是一个特征值的列表，返回特征值二分的结果# 比如4个元素可以有4种1+3分发，3种2+2的分法，该函数返回所有可能的二分结果列表，每个元素是一个二元组def featuresplit(features):    count = len(features)  #特征值的个数    if count < 2:                return -1    # 由于需要返回二分结果，所以每个分支至少需要一个特征值，所以要从所有的特征组合中选取1个以上的组合    # itertools的combinations 函数可以返回一个列表选多少个元素的组合结果，例如combinations(list,2)返回的列表    # 元素选2个的组合，我们需要选择1-（count-1）的组合    featureIndex = range(count)    featureIndex.pop(0)   # 弹出第1个元素    combinationsList = []        resList=[]    # 遍历所有的组合    for i in featureIndex:        temp_combination = list(combinations(features, len(features[0:i])))        combinationsList.extend(temp_combination)        combiLen = len(combinationsList)    # 每次组合的顺序都是一致的，并且也是对称的，所以我们取首尾组合集合    # zip函数提供了两个列表对应位置组合的功能    # print combinationsList    resList = zip(combinationsList[0:combiLen/2], combinationsList[combiLen-1:combiLen/2-1:-1])    return resList# 划分数据集，挑选出特征为axis且值为values的样本点values为多个值def splitDataSet(dataSet, axis, values):    retDataSet = []    for featVec in dataSet:        for value in values:            if featVec[axis] == value:                reducedFeatVec = featVec[:axis]     #剔除样本的某个特征                reducedFeatVec.extend(featVec[axis+1:])                retDataSet.append(reducedFeatVec)    return retDataSet# 返回最好的特征以及二分特征值def chooseBestFeatureToSplit(dataSet):    numFeatures = len(dataSet[0]) - 1    #特征个数    bestGiniGain = 1.0    bestFeature = -1    bestBinarySplit=()    for i in range(numFeatures):        #遍历特征        featList = [example[i] for example in dataSet] # 得到特征列的所有值列表        uniqueVals = list(set(featList))       #从特征列获取该特征的特征值的set集合        # featuresplit(uniqueVals)函数计算某个特征的所有值的二分结果，例如三个特征值的二分结果：        # [(('young',), ('old', 'middle')), (('old',), ('young', 'middle')), (('middle',), ('young', 'old'))]        feature_combin=featuresplit(uniqueVals)        if feature_combin!=-1:            for split in feature_combin:                GiniGain = 0.0                if len(split)==1:                    continue                (left,right)=split                # 对于每一个可能的二分结果计算gini增益                # 左增益                left_subDataSet = splitDataSet(dataSet, i, left)                left_prob = len(left_subDataSet)/float(len(dataSet))                GiniGain += left_prob * calGini(left_subDataSet)                # 右增益                right_subDataSet = splitDataSet(dataSet, i, right)                right_prob = len(right_subDataSet)/float(len(dataSet))                GiniGain += right_prob * calGini(right_subDataSet)                if (GiniGain <= bestGiniGain):       #比较是否是最好的结果                    bestGiniGain = GiniGain         #记录最好的结果和最好的特征                    bestFeature = i                    bestBinarySplit=(left,right)    return bestFeature,bestBinarySplitdef 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)    return sortedClassCount[0][0]# 创建分类树def createTree(dataSet,labels):    classList = [example[-1] for example in dataSet]    # print classList    if classList.count(classList[0]) == len(classList):         return classList[0]#所有的类别都一样，就不用再划分了    if len(dataSet) == 1: #如果没有继续可以划分的特征，就多数表决决定分支的类别        # print "here"        return majorityCnt(classList)    bestFeat,bestBinarySplit = chooseBestFeatureToSplit(dataSet)    # print bestFeat,bestBinarySplit,labels    bestFeatLabel = labels[bestFeat]    if bestFeat==-1:        return majorityCnt(classList)    myTree = {bestFeatLabel:{}}    featValues = [example[bestFeat] for example in dataSet]    uniqueVals = list(set(featValues))  # 最优特征的所有取值    for value in bestBinarySplit:        subLabels = labels[:]       # #拷贝防止其他地方修改        if len(value)<2:            del(subLabels[bestFeat])  # 删除某个特征        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)    return myTreeif __name__ == '__main__':    dataset,labels=createDataSet()        tree=createTree(dataset,labels)    print tree