《机器学习实战》学习笔记（二）之决策树（上）决策树的生成及修剪，ID3,C4.5CART算法

C**转载请注明作者和出处：**http://blog.csdn.net/john_bh/
运行平台： Windows
Python版本： Python2.7
IDE： Sublime text3

• 一 决策树的概述
• 二 决策树的算法框架
• 三决策树的构造
  • 1 特征选择
  • 2 决策树的生成
  • 3 决策树的修剪
  • 4 CART算法
    • 41 CART生成
    • 42 CART剪枝

一、 决策树的概述

1.1 决策树的发展

决策树算法是最早的机器学习算法之一，在1966年，Hunt、Marin和Stone提出的CLS学习系统就有了决策树的算法的概念 。但是直到1979年，J.R.Quinlan才给出了ID3算法的原型。1983年和1986年，他对ID3进行了总结和简化，正式确立了决策树学习的理论。从机器学习的角度来看，这是决策树算法的起点。
1986年，Schimmer和Fisher在此基础上进行改造，引入了节点缓冲区，提出了ID4算法。
1993年，Quinlan进一步发展ID3算法，改进成了C4.5算法，成为机器学的十大算法之一。
ID3的另一个分支是分类回归决策树算法（Classification and Regression Tree，CART）。与C4.5不同的是，CART的决策树主要用于预测，这样决策树理论完整的覆盖了机器学习中的分类和回归两个领域。
k-近邻算法，可以很多分类任务，但是他最大的缺点是无法给出数据的内在含义，而决策树的主要优势就在于数据形式非常容易理解。

1.2 决策树的定义

决策树是什么？决策树(decision tree)是一种基本的分类与回归方法。分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。举个通俗易懂的例子，如图 1.1所示的流程图就是一个决策树，长方形代表判断模块(decision block)，椭圆形成代表终止模块(terminating block)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作为分支(branch)，它可以达到另一个判断模块或者终止模块。长方形和椭圆形都是结点。长方形的结点属于内部结点，椭圆形的结点属于叶结点，从结点引出的左右箭头就是有向边。而最上面的结点就是决策树的根结点(root node)。

图 1.1流程图形式的决策树

1.3 决策树与if-then规则

我们可以把决策树看成一个if-then规则的集合，其中if是条件，then就是选择或决策。
将决策树转换成if-then规则的过程：由决策树的根结点(root node)到叶结点(leaf node)的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

决策树的一般流程：

1. 收集数据：可以使用任何方法；比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。
2. 准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。使用ID3树构造算法无法处理数值型数据，因此数值型数据必须离散化，转换成标称型数据。
3. 分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。
4. 训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。
5. 测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。
6. 使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

决策树的优点：

1. 计算复杂度不高；
2. 输出结果易于理解；
3. 对中间值得缺失不敏感；
4. 可以处理不相关特征数据；

决策树的缺点：

1. 可能会产生过度匹配的问题
2. 处理连续变量不好
3. 类别较多时，错误增加的比较快
4. 可规模性一般

适用数据类型：数值型和标称型

二、 决策树的算法框架

2.1 决策树主函数

各种决策树的主函数都大同小异，本质上是一个递归函数。该函数的主要功能是按照某种规则生长出决策树的各个分支接点，并根据终止条件结束算法。一般来说主函数需要完成如下几个功能：

1. 输入需要分类的数据集和分类标签；
2. 根据某种分类规则的到最优的划分特征，并创建特征的划分节点—计算最优特征子函数；
3. 按照特征的每个取值划分数据集为若干个部分—划分数据集子函数；
4. 根据划分子函数的计算结果构建出新的节点，作为树生长出的新分支；
5. 检验是否符合递归的终止条件；
6. 将划分的新节点包含的数据集和类别标签作为输入，递归执行上述步骤

2.2 计算最优特征子函数

计算最优特征子函数是除了主函数外最重要的函数。每种决策树之所以不同，一般都是因为最优特征选择的标准上有所差异，不用的标准导致不同类型的决策树，例如：ID3的最优特征先择标准是信息增益、C4.5的是信息增益率、CART的是节点方差的大小等。
在算法逻辑上，一般选择最优特征需要遍历整个数据集，评估每个特征，找到最优的那个特征返回。

2.3 划分数据集子函数

划分数据集函数的主要功能是分隔数据集，有需要删除某个特征轴所在的数据列，返回剩余的数据集，有的干脆将数据集一分为二，虽然实现有所不同，但是含义基本都是一致的。

2.4 分类器

所有的机器学习算法都要用于分类或回归预测。决策树的分类器就是通过遍历整个决策树，使测试数据集找到决策树中叶子结点对应的类别标签。这个标签就是返回的结果。

三、决策树的构造

决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和决策树的修剪。

3.1 特征选择

特征选择在于选取时对训练数据具有分类能力的特征。这样可以提高决策树的学习效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则成这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的标准是信息增益或信息增益比。
表3.1 贷款申请样本数据：

ID	年龄	有工作	有自己的房子	信贷情况	类别（是否给贷款）
1	青年	否	否	一般	否
2	青年	否	否	好	否
3	青年	是	否	好	是
4	青年	是	是	一般	是
5	青年	否	否	一般	否
6	中年	否	否	一般	否
7	中年	否	否	好	否
8	中年	是	是	好	是
9	中年	否	是	非常好	是
10	中年	否	是	非常好	是
11	老年	否	是	非常好	是
12	老年	否	否	好	是
13	老年	是	是	好	是
14	老年	是	否	非常好	是
15	老年	否	否	一般	否

希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。
特征选择就是决定用哪个特征来划分特征空间。

图3.1

图3.1 表示从表3.1 数据学习到得两个可能的决策树，分别由两个不同特征值的根节点构成。图1所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图2所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

3.1.1 信息增益(information gain)

划分数据集的大原则是：将无序的数据变得更加有序。组织杂乱无章数据的一种方法就是使用信息论量化度量信息，信息论是量化处理信息的分支学科，我们可以在划分数据之前或之后使用信息论量化度量信息的内容。
在划分数据集之前之后信息发生的变化成为信息增益。知道如何计算信息增益，我们可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
熵（entropy）：
集合信息的度量方式称为香农熵或者简称熵，这个名字来源于信息论之父克劳德·香农。熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为

l(xi)=−log2p(xi)

其中p(xi)是选择该分类的概率。
通过上式，我们可以得到所有类别的信息。为了计算熵。我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

H=−∑i=1np(xi)log2p(xi)

期中n是分类的数目。熵越大，随机变量的不确定性就越大。
条件熵(conditional entropy)：
设有随机变量（X,Y）,其联合概率分布为：

P(X=xi,Y=yj)=pij；其中i=1,2,...,n;j=1,2,...,m;

条件熵H(Y|X)表示已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵（conditional entropy）H(Y|X),定义为X给定条件下的Y的条件概率分布的熵对X的数学期望：

H(Y|X)=∑i=1npiH(Y|X=xi)

这里，pi=P(X=xi),i=1,2,...,n
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵成为经验熵(empirical entropy）和经验条件熵(empirical conditional entropy）.
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。

3.1.2 信息增益的算法

设训练数据集D，|D|表示其样本容量，即样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，∑Kk=1|Ck|=|D|。

设特征A有n个不同的取值{a1,a2,...,an}，根据特征A的取值将D划分为n个子集D1,D2,...,Dn,|Di|为Di的样本个数，∑ni=1|Di|=|D|。记子集Di中属于类Ck的样本的集合为Dik，即Dik=Di⋂Ck，|Dik|为Dik的样本个数。

输入：训练数据集D和特征A:
输出：特征A对训练数据集D的信息增益g(D,A)。
1)计算数据D的经验熵H(D):

H(D)=−∑k=1K|Ck||D|log2|Ck||D|

2)计算特征A对训练数据集D的经验条件熵H(D|A):

H(D|A)=∑i=1n|Di||D|H(Di)=−∑i=1n|Di||D|∑k=1K|Dik||Di|log2|Dik||Di|

3)计算信息增益：

g(D,A)=H(D)−H(D|A)

3.1.3 信息增益比：

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正，这是特征选择的另一准则。
信息增益比算法的定义：
特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值得熵HA(D)之比，即

gR(D,A)=g(D,A)HA(D)

其中，HA(D)=−∑ni=1|Di||D|log2|Di||D|，n是特征A取值的个数。

3.1.4 实例：

对表3.1所给的训练数据集D，根据信息增益准则选择最优特征：
首先计算经验熵，根据公式计算经验熵H(D)，分析样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

H(D)=−915log2915−615log2615=0.971

然后计算各特征对数据集D的信息增益，分别以A1,A2,A3,A4表示年龄、有工作、有自己的房子和信贷情况4个特征。
1)年龄这一列的数据，也就是特征A1，一共有三个类别，分别是：青年、中年和老年。年龄是青年的数据一共有5个，所以年龄是青年的数据在训练数据集出现的概率是十五分之五，也就是三分之一。同理，年龄是中年和老年的数据在训练数据集出现的概率也都是三分之一。年龄是青年的数据的最终得到贷款的概率为五分之二，因为在五个数据中，只有两个数据显示拿到了最终的贷款，同理，年龄是中年和老年的数据最终得到贷款的概率分别为五分之三、五分之四。所以计算年龄的信息增益，过程如下:

g(D，A1)=H(D)−[515H(D1)+515H(D2)+515H(D3)]=0.971−[515(−25log225−35log235)+515(−35log235−25log225)+515(−45log245−15log215)]=0.971−0.888=0.083

2)有工作，特征A2，一共有两个类别，分别是：是、否。有工作为是的数据，一共有5个，所以有工作为是的数据在训练数据集出现的概率是十五分之五，也就是三分之一。则有工作为否的数据在训练数据集出现的概率是十五分之十，也就是三分之二。有工作为是的数据的最终得到贷款的概率为一，因为在五个数据中，全部拿到了最终的贷款，同理，有工作为否的数据最终得到贷款的概率为十分之四。所以计算有工作的信息增益，过程如下：

g(D，A2)=H(D)−[515H(D1)+1015H(D2)]=0.971−[515×0+1015(−410log2410−610log2610)]=0.324

3)有自己的房子，特征A3，一共有两个类别，分别是：是、否。有自己的房子的数据，一共有6个，所以有工作为是的数据在训练数据集出现的概率是十五分之六。则没有自己的房子的数据在训练数据集出现的概率是十五分之九。有自己的房子的数据的最终得到贷款的概率为一，因为在六个数据中，全部拿到了最终的贷款，同理，没有自己的房子的数据最终得到贷款的概率为九分之三。所以计算有自己的房子的信息增益，过程如下：

g(D，A3)=H(D)−[615H(D1)+915H(D2)]=0.971−[615×0+915(−39log239−69log269)]=0.971−0.551=0.420

4)信贷情况，特征A4，一共有三个类别，分别是：一般、好、非常好。信贷情况一般的数据，一共有5个，所以信贷情况一般的数据在训练数据集出现的概率是十五分之五。则信贷情况好和信贷情况非常好的数据在训练数据集出现的概率分别是十五分之六和十五分之四。信贷情况一般的数据的最终得到贷款的概率为五分之一，同理，信贷情况好和信贷情况非常好的数据最终得到贷款的概率分别为六分之四和一。所以计算信贷情况的信息增益，过程如下：

g(D，A4)=H(D)−[515H(D1)+615H(D2)+415H(D3)]=0.971−[515(−15log215−45log245)+615(−46log246−26log226)+415×0]=0.971−0.608=0.363

最后，比较特征的信息增益，由于特征A3(有自己的房子)的信息增益值最大，所以选择A3作为最优特征。

3.1.5 代码实现：

在编写代码之前，我们先对数据集进行属性标注。

• 年龄：0代表青年，1代表中年，2代表老年；
• 有工作：0代表否，1代表是；
• 有自己的房子：0代表否，1代表是；
• 信贷情况：0代表一般，1代表好，2代表非常好；
• 类别(是否给贷款)：no代表否，yes代表是。

1）创建数据集，并计算经验熵了，代码编写如下:

# -*- coding: UTF-8 -*-
from math import log

"""
函数说明:创建测试数据集

Parameters:
    无
Returns:
    dataSet - 数据集
    labels - 分类属性
"""
def createDataSet():
    dataSet = [[0, 0, 0, 0, 'no'],         #数据集
            [0, 0, 0, 1, 'no'],
            [0, 1, 0, 1, 'yes'],
            [0, 1, 1, 0, 'yes'],
            [0, 0, 0, 0, 'no'],
            [1, 0, 0, 0, 'no'],
            [1, 0, 0, 1, 'no'],
            [1, 1, 1, 1, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [2, 0, 1, 2, 'yes'],
            [2, 0, 1, 1, 'yes'],
            [2, 1, 0, 1, 'yes'],
            [2, 1, 0, 2, 'yes'],
            [2, 0, 0, 0, 'no']]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']        #分类属性
    return dataSet, labels                #返回数据集和分类属性

"""
函数说明:计算给定数据集的经验熵(香农熵)

Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 经验熵(香农熵)
"""
def calcShannonEnt(dataSet):
    numEntires = len(dataSet)                        #返回数据集的行数
    labelCounts = {}                                #保存每个标签(Label)出现次数的字典
    for featVec in dataSet:                            #对每组特征向量进行统计
        currentLabel = featVec[-1]                    #提取标签(Label)信息
        if currentLabel not in labelCounts.keys():    #如果标签(Label)没有放入统计次数的字典,添加进去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1                #Label计数
    shannonEnt = 0.0                                #经验熵(香农熵)
    for key in labelCounts:                            #计算香农熵
        prob = float(labelCounts[key]) / numEntires    #选择该标签(Label)的概率
        shannonEnt -= prob * log(prob, 2)            #利用公式计算
    return shannonEnt                                #返回经验熵(香农熵)

if __name__ == '__main__':
    dataSet, features = createDataSet()
    print(dataSet)
    print(calcShannonEnt(dataSet))

代码运行结果如下图所示，代码是先打印训练数据集，然后打印计算的经验熵H(D)，程序计算的结果与我们统计计算的结果是一致的，如图3.2 所示：

图3.1 输出结果

2）计算信息增益，选择最优特征，代码实现：

# -*- coding: UTF-8 -*-
from math import log

"""
函数说明:创建测试数据集

Parameters:
    无
Returns:
    dataSet - 数据集
    labels - 分类属性
"""
def createDataSet():
    dataSet = [[0, 0, 0, 0, 'no'],         #数据集
            [0, 0, 0, 1, 'no'],
            [0, 1, 0, 1, 'yes'],
            [0, 1, 1, 0, 'yes'],
            [0, 0, 0, 0, 'no'],
            [1, 0, 0, 0, 'no'],
            [1, 0, 0, 1, 'no'],
            [1, 1, 1, 1, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [2, 0, 1, 2, 'yes'],
            [2, 0, 1, 1, 'yes'],
            [2, 1, 0, 1, 'yes'],
            [2, 1, 0, 2, 'yes'],
            [2, 0, 0, 0, 'no']]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']        #分类属性
    return dataSet, labels                #返回数据集和分类属性

"""
函数说明:计算给定数据集的经验熵(香农熵)

Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 经验熵(香农熵)
"""
def calcShannonEnt(dataSet):
    numEntires = len(dataSet)                        #返回数据集的行数
    labelCounts = {}                                #保存每个标签(Label)出现次数的字典
    for featVec in dataSet:                            #对每组特征向量进行统计
        currentLabel = featVec[-1]                    #提取标签(Label)信息
        if currentLabel not in labelCounts.keys():    #如果标签(Label)没有放入统计次数的字典,添加进去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1                #Label计数
    shannonEnt = 0.0                                #经验熵(香农熵)
    for key in labelCounts:                            #计算香农熵
        prob = float(labelCounts[key]) / numEntires    #选择该标签(Label)的概率
        shannonEnt -= prob * log(prob, 2)            #利用公式计算
    return shannonEnt                                #返回经验熵(香农熵)

"""
函数说明:按照给定特征划分数据集

Parameters:
    dataSet - 待划分的数据集
    axis - 划分数据集的特征
    value - 需要返回的特征的值
Returns:
    无
"""
def splitDataSet(dataSet, axis, value):       
    retDataSet = []                                        #创建返回的数据集列表
    for featVec in dataSet:                             #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]                #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet                                      #返回划分后的数据集

"""
函数说明:选择最优特征

Parameters:
    dataSet - 数据集
Returns:
    bestFeature - 信息增益最大的(最优)特征的索引值
"""
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1                    #特征数量
    baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
    bestInfoGain = 0.0                                  #信息增益
    bestFeature = -1                                    #最优特征的索引值
    for i in range(numFeatures):                         #遍历所有特征
        #获取dataSet的第i个所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)                         #创建set集合{},元素不可重复
        newEntropy = 0.0                                  #经验条件熵
        for value in uniqueVals:                         #计算信息增益
            subDataSet = splitDataSet(dataSet, i, value)         #subDataSet划分后的子集
            prob = len(subDataSet) / float(len(dataSet))           #计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet)     #根据公式计算经验条件熵
        infoGain = baseEntropy - newEntropy                     #信息增益
        print("第%d个特征的增益为%.3f" % (i, infoGain))            #打印每个特征的信息增益
        if (infoGain > bestInfoGain):                             #计算信息增益
            bestInfoGain = infoGain                             #更新信息增益，找到最大的信息增益
            bestFeature = i                                     #记录信息增益最大的特征的索引值
    return bestFeature                                             #返回信息增益最大的特征的索引值

if __name__ == '__main__':
    dataSet, features = createDataSet()
    #print(dataSet)
    #print(calcShannonEnt(dataSet))
    print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))

代码运行结果如下图所示，代码是先打印训练数据集，然后打印计算的经验熵H(D)，程序计算的结果与我们统计计算的结果是一致的，如图3.3 所示：

图3.2 输出结果

最优特征的索引值为2，也就是特征A3(有自己的房子)。

3.2 决策树的生成

已经知道了从数据集构造决策树算法所需的子功能模块，其工作原理如下：
得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个结点，在这个结点上，我们可以再次化数据，因此可以采用递归的原则处理数据集。
递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例都具有相同的分类，则得到一个叶子结点或者终止块。任何到达叶子结点的数据必然属于叶子结点的分类。

3.2.1 ID3算法

ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。ID3相当于用极大似然法进行概率模型的选择。
输入：训练数据集D，特征集A，阈值ϵ
输出：决策树T

1. 若D中所有实例属于同一类Ck，则T树为单结点树，并将类Ck作为该结点的类标记，返回T；
2. 若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T;
3. 否则，按算法计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
4. 如果Ag的信息增益小于阈值ϵ，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T;
5. 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干个非空子集Di，将Di中的实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
6. 对第i个子结点，以Di为训练集，以A-Ag为特征集，递归调用步(1)~步(5)，得到子树Ti，返回Ti

对表3.1的训练数据集，利用ID3算法建立决策树：
利用上面的结果，由于特征A3(有自己的房子)的信息增益值最大，所以选择特征A3作为根结点的特征。它将训练集D划分为两个子集D1(A3取值为”是”)和D2(A3取值为”否”)。由于D1只有同一类的样本点，所以它成为一个叶结点，结点的类标记为“是”。
对D2则需要从特征A1(年龄)，A2(有工作)和A4(信贷情况)中选择新的特征，计算各个特征的信息增益：

g(D2,A1)=H(D2)−H(D2|A1)=0.918−0.667=0.251
g(D2,A2)=H(D2)−H(D2|A2)=0.918
g(D2,A4)=H(D2)−H(D2|A4)=0.474

根据计算，选择信息增益最大的特征A2(有工作)作为结点的特征。由于A2有两个可能取值，从这一结点引出两个子结点：一个对应”是”(有工作)的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为”是”；另一个是对应”否”(无工作)的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为”否”。
这样就生成了一个决策树，该决策树只用了两个特征(有两个内部结点)，生成的决策树如下图所示。

图3.3 决策树的生成

ID3算法只要树的生成，所以该算法生成的树容易产生过拟合。

3.2.2 C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法，进行了改进，C4.5在生成的过程中，使用信息增益比来选择特征。
输入：训练数据集D，特征集A，阈值ϵ
输出：决策树T

1. 若D中所有实例属于同一类Ck，则T树为单结点树，并将类Ck作为该结点的类标记，返回T；
2. 若A=∅，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T;
3. 否则，按算法计算A中各特征对D的信息增益比，选择信息增益比最大的特征Ag；
4. 如果Ag的信息增益比小于阈值ϵ，则置T为单结点点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T;
5. 否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干个非空子集Di，将Di中的实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
6. 对第i个子结点，以Di为训练集，以A-Ag为特征集，递归调用步(1)~步(5)，得到子树Ti，返回Ti

3.2.3 编写代码构建决策树

添加函数majorityCnt()，该函数使用分类名称的列表，然后创建键值为classList中唯一值得数据字典，字典对象中存储了classList中每个类标签出现的频率，最后利用operator操作键值排序字典，并返回出现次数最多的分类名称。

"""
函数说明:统计classList中出现此处最多的元素(类标签)

Parameters:
    classList - 类标签列表
Returns:
    sortedClassCount[0][0] - 出现此处最多的元素(类标签)
"""
def majorityCnt(classList):
    classCount = {}
    for vote in classList:    #统计classList中每个元素出现的次数
        if vote not in classCount.keys():classCount[vote] = 0   
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)        #根据字典的值降序排序
    return sortedClassCount[0][0]    #返回classList中出现次数最多的元素

添加函数createTree()，创建决策树，传入两个参数：数据集和标签列表，标签列表中包含了数据集中所有特征的标签，递归有两个终止条件：第一个停止条件是所有的类标签完全相同，则直接返回该类标签；第二个停止条件是使用完了所有特征，仍然不能将数据划分仅包含唯一类别的分组，即决策树构建失败，特征不够用。此时说明数据纬度不够，由于第二个停止条件无法简单地返回唯一的类标签，这里使用majorityCnt函数挑选出现数量最多的类别作为返回值。
我们使用字典存储决策树的结构，比如上小节我们分析出来的决策树，用字典可以表示为：

{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

字典变量myTree存储了树的所有信息，当前数据集选取的最好特征存储在变量bestFeat中，得到的列表包含所有属性值。
最后，代码遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数createTree()，得到的返回值将插入到字典变量myTree中，因此函数终止执行时，字典中将会嵌套很多代表叶子节点信息的字典数据

"""
函数说明:创建决策树

Parameters:
    dataSet - 训练数据集
    labels - 分类属性标签
    featLabels - 存储选择的最优特征标签
Returns:
    myTree - 决策树
"""
def createTree(dataSet, labels, featLabels):
    classList = [example[-1] for example in dataSet]            #取分类标签(是否放贷:yes or no)
    if classList.count(classList[0]) == len(classList):            #如果类别完全相同则停止继续划分
        return classList[0]
    if len(dataSet[0]) == 1:                                    #遍历完所有特征时返回出现次数最多的类标签
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)                #选择最优特征
    bestFeatLabel = labels[bestFeat]                            #最优特征的标签
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树
    del(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, featLabels)
    return myTree

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    #print(dataSet)
    #print(calcShannonEnt(dataSet))
    #print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))
    featLabels = []
    myTree = createTree(dataSet, labels, featLabels)
    print(myTree)

运行结果如图3.4 所示：

图3.4 构建决策树运行结果

3.3 决策树的修剪

决策树生成算法递归地产生决策树，知道不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但是对未知的测试数据的分类却没有那么准确，即出现过拟合现象，过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的的决策树，解决这个问题的办法是，考虑决策树的复杂度，对已生成的决策树进行简化。

在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）,具体地，剪枝从已生成的树上裁掉一些树或叶子结点，将其根结点或父结点作为新的叶子结点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。设T树的叶子结点个数为|T|，t是树T的叶子结点，该叶子结点有Nt个样本点，其中k类的样本点有Ntk个，k=1，2，……，K,Ht(T)为叶子结点t上的经验熵，α≥0为参数，则决策树学习的损失函数可以定义为：

Cα(T）=∑t=1|T|NtHt(T)+α|T|

其中经验熵为：

Ht(T)=−∑kNtkNtlogNtkNt

在损失函数中，右端的第一项记作：

C(T)=∑t=1|T|NtHt(T)=−∑t=1|T|Nt∑k=1KNtklogNtkNt

这时有Cα(T)=C(T)+α|T|
C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数α≥0控制两者之间的影响，较大的α促使选择较简单的模型（树），较小的α促使选择较复杂的模型（树），α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

剪枝，就是当α确定时，选择损失函数最小的模型，即损失函数最小的子树，当α确定时，子树越大，往往与训练数据的拟合越好，但是模型的复杂度越高，相反，子树越小，模型的复杂度越低，但是往往与训练数据的拟合不好，损失函数正好表示了两者的平衡。

可以看出决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据更好的拟合，而决策树剪枝通过优化损失函数还考虑了较小模型复杂度。决策树生成学习的局部模型，而决策树剪枝学习整体的模型。利用损失函数最小原则进行剪枝就是用政策化的极大似然估计进行模型选择。

树的剪枝算法：
输入：生成算法产生的整个树T，参数α
输出：修剪后的子树Tα

1. 计算每个结点的经验熵
2. 递归地从树的叶子结点向上回缩
   设一组叶子结点回缩到其父结点之前与之后的整体树分别为TB与TA，其对应的损失函数值分别是Cα(TB)与Cα(TA)，如果
   
   Cα(TA)≤Cα(TB)
   
   则进行剪枝，将其父结点变为新的叶子结点。
3. 返回（2）直至不能继续为止，得到损失函数最小的子树Tα

如图3.5 决策树的剪枝所示：

图3.5 决策树的剪枝

注意，Cα(TA)≤Cα(TB)只考虑两个树的损失函数的差，其计算可以在局部进行，所以决策树的剪枝算法可以由一种动态规划的算法实现。

3.4 CART算法

分类与回归树（classification and regression tree，CART）模型有Breiman等人在1984年提出，是应用广泛的决策树学习方法，CART同样由特征选择，树的生成以及剪枝组成，既可以用于分类也可以用于回归。

CART是在给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支，这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法有一下两步组成：

1. 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
2. 决策树剪枝：用验证数据集对已生成的树进行剪枝并最优子树，这时用损失函数最小作为剪枝的标准。

3.4.1 CART生成

决策树的生成就是递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

3.4.1.1 回归树的生成

假设X与Y分别为输入输出变量，并且Y是连续变量，给定训练数据集：D={(x1,y1),(x2,y2),...,(xN,yN)}，考虑如何生成回归树。

一个回归树对应着输入空间（即特征空间），的一个划分以及在划分单元上的输出值，假设已将输入空间划分为M各单元R,R2..RM,并且在每个单元Rm上有一个固定的输出值Cm，回归树模型可以表示为：

f(x)=∑m=1McmI(x∈Rm)

当输入空间的划分确定时，可以用平法误差∑xi∈Rm(yi−f(xi))2来表示回归树对于训练数据的预测误差，用平方误差最小准则，求解每个单元上的最优输出值。易知，单元Rm上的cm的最优值c^m是Rm上的所有输入实例xi对应的输出yi的均值，即：

c^m=ave(yi|xi∈Rm)

问题是如何对输入空间进行划分？这里采用的是启发式的方法：选择第j个变量x(j)和它取的值s，作为切分变量(splitting variable)和切分点（splitting point），并定义两个区域：

R1(j,s)={x|xj≤s}和R2(j,s)={x|xj>s}

然后寻找最优切分变量j和切分点s，具体的求解:

minj,s⎡⎣minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2⎤⎦

对固定输入变量j可以找到最优切分点s.

c^1=ave(yi|xi∈R1(j,s))和c^2=ave(yi|xi∈R2(j,s))

遍历所有输入变量，找到最优的切分变量j，构成一对（j,s），依次将输入空间划分为两个区域，接着对每个区域重复上述划分过程，知道满足停止条件为止，这样就生成一棵回归树。这样的回归树通常称为最小二乘回归树（least squares regression tree）。

最小二乘回归树生成算法：
输入：训练数据集D
输出：回归树f(x)
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉树：

1. 选择最优切分变量j与切分点s，求解

   minj,s⎡⎣minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2⎤⎦

   遍历变量j，对固定的切分变量j扫描切分点s，选择达到最小值的(j,s)。

2. 用选定的对(j,s)划分区域，并决定相应的输出值：
   

   R1(j,s)={x|xj≤s}和R2(j,s)={x|xj>s}
   
   
   c^m=1Nm∑xi∈Rm(j,s)yi，(x∈Rm，m=1，2)

3. 继续对两个子区域调用步骤1,2，直至满足停止条件。
4. 将输入空间划分为M个区域R1,R2,...,RM，生成决策树：
   
   f(x)=∑m=1Mc^mI(x∈Rm)

3.4.1.2 分类树的生成

3.4.2 CART剪枝