机器学习篇：（一）决策树

         周末无事，从这一篇开始，总结几个月来学习机器学习算法的收获体会，以后争取每周更新一篇，每一篇介绍一个算法。决策树是我学习的第一个机器学习算法，对于一个菜鸟而言，如此直观的二叉树形结构，想来比较好学，然而事实并非如此，磕磕绊绊总算还是学下来了，现在总结一下！

1. 决策树模型定义：

        决策树模型是一种描述对实例进行分类的树形结构，由结点和有向边组成。结点分为根结点、内部结点以及叶结点。内部结点表示一个特征或属性，叶结点表示一个类或值。决策树模型是一种监督学习模型，既可以用来做分类，也可以用来做回归（本次只讨论分类问题）；另外，决策树还是其他很多其他监督学习的算法模型的基础，如梯度提升决策树(GBDT)、随机森林等，因此还蛮重要的~

 2. 决策树模型的学习过程：

        假设给定训练数据集

        其中，

        为输入特征向量，n为特征个数，为类标记，，N为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型，使其能对训练数据集正确分类，并具有良好的泛化能力。

        用决策树分类，从根结点开始，对训练数据集的所有特征进行筛选，选取出一个最优特征并根据该特征将数据集 、根据测试结果将数据集分配到下一个内部结点，每一个内部结点对应于该特征的一个取值。如此递归地对数据集进行测试、分配，直到被分在一起的数据集类别相同或达到终止条件时，分到叶结点的类当中，整个决策树模型就构建成功了。

模型示意（椭圆和方框分别表示内部结点和叶结点）

        在我看来，决策树的构建主要分为一下三个过程：

             （1）特征选择

    （2）决策树的生成

    （3）决策树的剪枝

下面分别介绍这三个过程：

2.1 特征选择

        决策树模型通常有三种特征选择的准则，分别为信息增益、信息增益比和Gini指数，这三种特征选择的方法分别对应了三种不同的决策树生成的方式。

（1）信息增益：

在说信息增益和信息增益比之前，要先谈一谈熵的概念。

熵（entripy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为

则随机变量X的熵定义为

        从这个公式来看，我们可以发现，如果P(X=xi)越小，则越大，可以理解为xi的信息量，即X = xi发生的概率越小，那么信息量就越大。这个可以试图从日常生活理解：比如足球比赛里，国足踢巴西，输是大概率事件，赢是小概率事件，但是如果比赛结果国足赢了，那么给人带来的惊讶程度远比输了要大得多，这就叫做爆冷，更加吸引人眼球，信息量也就很大。

        那么熵就很好理解了，从这个公式来看，熵就是信息量的期望了，即把每个样本的信息量乘以其概率再加和。另外要注意特殊情况，如果有0概率，则令0log0 = 0.

        与条件概率的思想类似，在概率统计中也有条件熵的概念。条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的数学期望。

        这里， 

        而信息增益（information gain）表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

        这里，特征A对训练数据集D的信息增益g(D,A)，定义为经验熵H(D)与条件熵H(D|A)之差。

        接下来，根据信息增益进行特征选择其实就是在比较各个特征的信息增益的大小，在每次构造内部结点时，信息增益大的特征能使类Y的信息的不确定性减少的更多，具有更强的分类能力，因此就选择其作为最优特征来就行数据集的分割。

        

        （2） 信息增益比

        以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比(information gain ratio)可以对这一问题进行校正。

        定义：特征A对训练数据集D的信息增益比定义为其信息增益g（D,A）与训练数据集D关于特征A的值的熵Ha（D）之比，即：

        其中， ，n是特征A取值的个数。

（3） Gini指数

和熵一样的是，基尼指数同样是表示一个集合不确定性的度量，先看定义：

分类问题中，假设有K个类，样本点属于第k个类的概率为pk，则概率分布的基尼指数定义为

        从这个公式定义可以看出，基尼指数的意义相当于是从数据集中随机抽取两个样本，类别不同的概率。因此，基尼指数同样是来表示数据集的不确定性的。对于二类分类问题，若样本属于第一个类的概率是p，则概率分布的基尼系数为

对于给定的样本集合D，其基尼指数为

这里，Ck是D中属于第k类的样本子集，K是类的个数。

如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即

则在特征A的条件下，集合D的基尼指数定义为

        根据基尼指数的定义，基尼指数越大，集合的不确定性就越大；而对于决策树的特征选择来讲，就要在每一次分类时总使得集合的不确定性下降得最快。因此，在生成决策树过程中，对于每一个内部结点（包括根结点），可以选择基尼指数最小的特征和对应的切分点来作为最优特征和最优切分点，按照这个准则来构建决策树模型。

2.2 决策树的生成（CART算法）

        在这里只介绍分类与回归树（classification and regression tree, CART）模型中的分类树模型，使用的特征选择准则为基尼指数。

        CART生成算法：

        输入：训练数据集D，停止计算的条件

        输出：CART决策树

        根据训练数据集，从根节点开始，递归地对每个结点进行一下操作，构建二叉决策树。

        （1）设结点处所对应的数据集为D，计算现有特征对数据集的基尼指数。对每一个特征A的每一个可能值a，根据样本点对A=a的测试为”是“或”否“，将数据分割成D1、D2两部分，计算Gini（D，A=a）

        （2）计算所有可能的特征和所有可能的值所对应的基尼指数，选取其中基尼指数最小的特征和对应的值作为最优特征和最优切分点，将数据集分成两部分，分别放入到生成的两个子结点中去。

        （3）对生成的两个子节点重复（1）（2）操作，直到满足停止条件

        （4）生成CART决策树

2.3 决策树的剪枝（CART剪枝）

        决策树生成以后之所以要剪枝，是因为生成的决策树也许对原有训练数据集分类有很高的准确性，但是可能会因此失去一个模型应当具备的泛化能力，即不能够很好地来预测其他数据。通过给决策树的损失函数添加一个正则项，利用损失函数最小原则进行剪枝，从而来得到最优的决策树模型。

        （1）决策树的损失函数

        在剪枝过程中，计算决策树或其子树的损失函数：

        其中，T为任意子树，C（T）为对训练数据的预测误差，在CART分类算法中可以用基尼指数或0-1损失。|T|为子树的叶结点个数，α≥0为参数，为参数是α时的子树T的整体损失。

        我们要做的就是在给定α的情况下，极小化以求得最优子树，设求得的最优子树为Tα。通过不断调整α的值，我们可以得到最优子树序列，再通过交叉验证法在独立的验证数据集上测试，选择最优子树。

        幸运的是，Breiman等人证明（文献[2]）：可以用递归的方法对树进行剪枝，将α从小到大排列，0=α0<α1<⋯<αn<+∞，产生一系列的区间，剪枝得到的子树序列对应着区间α∈[αi,αi+1)，i=0,1,...,n的最优子树序列｛T0,T1,T2,...,Tn｝,序列中的子树是嵌套的（即T1是T0的子树、T2是T1的子树）。

        具体的，从整体树T0开始剪枝，对T0内的任意内部结点t，以t为单结点树的损失函数（此时复杂度|T|=1）是

        以t为根结点的子树Tt的损失函数为

 

        当α=0及α很小的时候，

        当α不断增大，增大到上式左边和右边相等时，由于以t为单结点树的结点数少于Tt的结点树，即复杂度小一些，且两者损失函数值相等，那么就应该对Tt进行剪枝，转化为t。

        因此，对T0中每一个内部结点t，计算

        得到每个内部结点t所对应的αt值，这个值可以理解为剪枝后经验损失项C（T）增多的程度。为了使模型对训练数据有正确的分类，我们肯定不希望这个值很大，所以我们每次计算应选择其中最小的那个αt值所对应的内部结点，对T0进行剪枝，得到子树T1，则T1就是区间[α1,α2)的最优子树。

        然后我们再增加α的值，对T1进行以上操作，以此类推，直到根结点，我们可以得到一个最优子树序列｛T0,T1,T2,...,Tn｝。

        这时候，你可能会想问，为什么要比较C(t)和C(Tt)而不是比较原树和在原树基础上把t作为单结点的树（这句话可能比较拗口……），来对原整体树T0进行剪枝呢？原因是，如果我们只针对特定的某一个内部结点，肯定要保证树的其他部分不变，那么在这种情况下，比较C(t)和C(Tt)，与，比较原树和在原树基础上把t作为单结点的树，这两种情况是等价的，而比较C(t)和C(Tt)更加直接简单，所以这样来比较。

        好！下图即为CART剪枝的算法，来自文献[3]的图片（其实就是《统计学习方法》中的内容）

3. CART树生成与剪枝python代码实现

        说了这么多，岂能不上代码？真正用代码实现了算法，才算真正学会吧感觉。我通过以上的学习和看其他人写得博客，自己用python实现了CART分类树如下：

        3.1 数据

        以上是数据集。第一步要对进行处理，分为训练数据集和验证数据集，代码如下

from pandas import DataFrame,Series
import pandas as pd
import numpy as np
from pylab import *
import treePlotter

def createDataSet():
    '''
    创建数据集
    '''
    dataSet = pd.read_excel(r'data.xlsx',sheetname='Sheet1')
    #print(dataSet)
    total = len(dataSet)
    trainingdata = dataSet.iloc[:int(np.rint(0.7*total))]
    testdata = dataSet.iloc[int(np.rint(0.7*total)):]
    labels = list(dataSet.columns)

    #返回数据集和每个维度的名称
    return dataSet, trainingdata,testdata,labels

        计算基尼指数：

#计算数据集的基尼指数
def calGini(dataSet):
    total_sample = len(dataSet)
    if total_sample == 0:
        return 0
    labelCounts = {}
    #给所有可能分类创建字典
    type_of_dataSet = list(dataSet.iloc[:,-1])
    for label in type_of_dataSet:
        if label not in labelCounts.keys():
            labelCounts[label] = 0
        labelCounts[label]+=1
    gini = 0
    for key in labelCounts:
        gini = gini + pow(labelCounts[key],2)
    gini = 1 - float(gini) / pow(total_sample,2)
    return gini

def label_uniq_cnt(dataSet):
    '''统计数据集中不同的特征分别具有多少个不同的值，且这些值的个数
    input: data(DataFrame):原始数据集
    output: label_uniq_cnt(int):样本中的不同特征的不同值的个数
    '''
    label_uniq_cnt = {}
    dataSet = dataSet.drop(dataSet.columns[-1],axis=1)
    try:
        for x in dataSet.columns:
            fea = {}
            for i in dataSet[x]:
                if i not in fea:
                    fea[i] = 0
                fea[i] = fea[i] + 1
            label_uniq_cnt[x] = fea
    except AttributeError as e:
        if e == "'Series' object has no attribute 'columns'":
            label_uniq_cnt = dict(dataSet.value_counts())      
    finally:
        return label_uniq_cnt

def cal_gini_index(dataSet):
    '''计算给定数据集的不同特征的Gini指数
    input: data(DataFrame):数据集;C为目标类别
    output: gini(float):Gini指数
    '''
    total_sample = len(dataSet)#样本的总个数
    if len(dataSet) == 0:
        return 0
    label_counts = label_uniq_cnt(dataSet) #统计数据集中不同标签的个数
    
    #计算数据集的最小gini指数
    gini = 0;list_gini = [];best_point=None
    for label in label_counts.keys():
        fea = label_counts[label]
        #计算每个特征取不同值时的gini指数
        for i in fea.keys():
            P = fea[i] / total_sample
            g_c1 = calGini(dataSet[dataSet[label] == i])
            g_c2 = calGini(dataSet[dataSet[label] != i])
            #gini指数公式：Gini(D,label=i)
            gini = P*g_c1+(1-P)*g_c2
            list_gini.append(gini)
            #找出最优切分点和最小gini指数
            if list_gini[-1] == min(list_gini):
                best_point = (label,i)
                min_Gini = list_gini[-1]

    return min_Gini,best_point

        创建决策树：其中binary函数用来将特征序列二值化，在createTree中会用到,createTree函数还有个功能就是生成子树,这一部分借鉴了部分来自文献[4].

def binary(dataSet,bestFeature,bestvalue):
    """
    将特征序列二值化
    :param dataSet: 数据集
    :param bestFeature: 最优特征
    :param bestvalue: 最优值
    :return: 二值化后的特征序列
    """
    try:
        featurelist = list(dataSet[bestFeature])
        for i in range(len(featurelist)):
            if featurelist[i] != bestvalue:
                featurelist[i] = 'else'
        left_num = featurelist.count(bestvalue)
        right_num = len(featurelist) - left_num
    except Exception as e:
        print(e)
        print(bestFeature,bestvalue)
    finally:
        return featurelist,left_num,right_num

def createTree(dataSet,sub_data=None):
    """
    创建决策树
    :param dataSet: 数据集
    :param labels: 数据集每一维的名称
    :return: 决策树
    """
    classList = dataSet.iloc[:,-1]#标签列
    if len(classList.value_counts())==1:
        return classList[0]#当类别完全相同时停止继续划分

    min_gini,best_point = cal_gini_index(dataSet)
    #最优切分点
    bestFeature = best_point[0]#最优特征
    bestvalue = best_point[1]#最优值

    #将特征子集二值化
    binaryFeature,left_num,right_num = binary(dataSet,bestFeature,bestvalue)
    #print(binaryFeature)
    binarylist = Series(binaryFeature)
    myTree = {bestFeature:{}}
    #构建决策树
    for value in set(binaryFeature):
        binarylist = list(Series(binaryFeature) == value)
        #将新产生的子数据集进行行索引重新排列，以防出错
        subdata = dataSet[binarylist]
        newdata = DataFrame(np.array(subdata),columns=list(subdata))
        #以下两句分别用于生成子树和生成完整的决策树
        try:
            if len(newdata) == len(sub_data):
                myTree[bestFeature][value] = majority(sub_data)[0]#这一句用来生成子树
            else:
                myTree[bestFeature][value] = createTree(newdata,sub_data)
        except Exception:
            myTree[bestFeature][value] = createTree(newdata,sub_data)
    return myTree

        计算预测值，可以预测，在计算预测误差和剪枝时也会用到。

#根据树的某节点找到数据集中所对应的列索引
def treeFeature_dataColumn(tree,labels):
    for key in list(tree.keys()):
        if key in labels:
            return key

#计算预测值
def predict(tree,data,labels):
    #获得决策树的子节点
    node = treeFeature_dataColumn(tree,labels)
    if data[node] not in list(tree[node].keys()):
        tree = tree[node]['else']
    else:
        tree = tree[node][data[node]]
    #判断该树是内部节点还是叶节点
    if not isinstance(tree,dict):
        return int(tree)
    else:
        return predict(tree,data,labels)
        
#计算预测误差
def predict_error_num(data,tree,labels):
    length = len(data)
    count = 0
    for i in range(length):
        if data.iloc[i]['label'] != predict(tree,data.iloc[i],labels):
            count+=1
    return count / length

        CART剪枝，这部分代码当时写的时候比较痛苦，但还是最后写下来并成功实现了。其中还有有待改进的地方，比如在求每一个内部结点所对应的数据集时，只需要求出所对应数据集的索引即可。但是这里求得了所对应的数据集，增加了程序的复杂度。

#生成所有内部节点，放在一个列表之中    
def find_all_node(Tree,node_list=[]):
   labels = ['color', 'root', 'knocks', 'texture', 'navel', 'touch']
   for node,subtree in Tree.items():
       if isinstance(subtree,dict):
           if node in labels:
                node_list.append(dict([(node,subtree)]))
           find_all_node(subtree,node_list)
       else:
           pass
   return node_list[1:]

#得到每个内部节点所对应的数据集
def node_data(Tree,data_training,node_list,data_list,i=0):
    labels = ['color', 'root', 'knocks', 'texture', 'navel', 'touch']
    for k,subtree in Tree.items():
        if k in labels:
            node_data(Tree[k],data_training,node_list,data_list,i)
        elif not isinstance(subtree,dict):
            pass
        elif (subtree in node_list):
            i = node_list.index(subtree)
            min_gini,best_point = cal_gini_index(data_training)
            binaryFeature,left_num,right_num = binary(data_training,best_point[0],best_point[1])
            #寻找符合该子树的子数据集
            binarylist = list(Series(binaryFeature) == k)
            #将新产生的子数据集进行行索引重新排列，以防出错
            subdata = data_training[binarylist]
            newdata = DataFrame(np.array(subdata),columns=list(subdata))
            data_list[i] = newdata
            node_data(Tree[k],newdata,node_list,data_list,i)
    return data_list
            
#判断若将该内部节点变为叶节点，则该取何值               
def majority(data):
    #返回众数和众数有多少个
    return list(data.label.mode())[0],list(data.label.value_counts())[0]

#对给定内部子节点计算参数gt
def cal_gt(node,data,N,labels):
    #计算众数
    data_mode,mode_num = majority(data)
    #以node为单节点树的损失函数
    Ct = (len(data) - mode_num) / N
    #以node为根节点的子树的损失函数
    CT = predict_error_num(data,node,labels) * len(data) / N
    #计算叶节点的个数Tt
    Tt = cal_Tt(node,list_=[])
    gt = (Ct - CT) / (Tt - 1)
    return gt
    
#对给定内部子节点计算叶节点的个数Tt：
def cal_Tt(node,list_=[]):
    for k,v in node.items():
        try:
            list_.append(int(v))
        except Exception:
            cal_Tt(v,list_)
    return len(list_)

        最后主函数，实现了最优子树序列的生成，由于数据量实在太少因此就不做最后的交叉验证了。注释应该给的比较清楚了，基本上就是按照CART剪枝算法（上文）的步骤进行的。

if __name__ == '__main__':
    data,trainingdata,testdata,labels = createDataSet()
    #生成整体数
    mytree = createTree(trainingdata)
    node_list = find_all_node(mytree,node_list=[])#返回内部子节点列表
    data_list = [None]*len(node_list)#构建与内部子节点列表长度相同的列表
    #返回与内部子节点顺序对应的子数据列表
    data_list = node_data(mytree,trainingdata,node_list,data_list,i=0)

    treePlotter.createPlot(mytree)
    #CART剪枝
    T = mytree
    gt_list = []
    Tree_list=[mytree]
    alpha_list = [0]
    while True:
        #自下而上计算各个内部节点的gt
        for n in range(len(node_list)-1,-1,-1):
            gt = cal_gt(node_list[n],data_list[n],len(trainingdata),labels)
            gt = float("%.5f" % gt)
            gt_list.append(gt)
        gt_min = min(gt_list)

        gt_list = []
        #自上而下的访问内部节点，进行剪枝
        for m in range(len(node_list)):
            gt = cal_gt(node_list[m],data_list[m],len(trainingdata),labels)
            gt = float("%.5f" % gt)

            if gt == gt_min:
                #剪枝生成子树T
                T = createTree(trainingdata,data_list[m])
                Tree_list.append(T)
                alpha_list.append(gt)
                #print(T)
                break#中断的语句块是自上而下访问内部节点的部分
        #当T为由根节点单独构成的树时，退出循环
        if cal_Tt(T,list_=[]) == 2:
            break
        #根据新生成的子树求得子树的内部节点以及对应的数据集
        node_list = find_all_node(T,node_list=[])
        data_list = [None]*len(node_list)
        data_list = node_data(T,trainingdata,node_list,data_list,i=0)
    
    #打印最优子树列表
    for tree in Tree_list:
        print(tree)

        最后看一下整体树和最优子树列表的结果~~

        整体树：

        最优子树序列：

{'navel': {'even': 0, 'else': {'texture': {'little_blur': {'touch': {'hard_smooth': 0, 'else': 1}}, 'else': {'touch': {'soft_stick': {'color': {'black': 0, 'else': 1}}, 'else': 1}}}}}}
{'navel': {'even': 0, 'else': {'texture': {'little_blur': {'touch': {'hard_smooth': 0, 'else': 1}}, 'else': 1}}}}
{'navel': {'even': 0, 'else': 1}}

        自此，决策树的内容就介绍完毕了（还挺多的……），如有错误还请多多交流！

参考文献：

[1]. 李航，《统计学习方法》

[2]. Breiman L, Friedman J, Store C. Classification and Regression Trees. Wadsworth 

[3]. http://www.cnblogs.com/Wanggcong/p/4670138.html

[4]. http://blog.csdn.net/u014688145/article/details/53326910