目录

1、概述​

2、决策树模型

3、决策树学习

4、决策树的构建——三步骤

4.1 特征选择

4.1.1 熵（Entropy）

4.1.2 条件熵（Conditional Entropy）H(Y|X)

4.1.3 信息增益（Information Gain）

4.1.4 信息增益比

4.2决策树算法

4.2.1 ID3算法

4.2.2 C4.5算法

4.2.3 Python实现ID3、C4.5算法

4.3 决策树的剪枝

引言

4.3.1 算法目的

4.3.2 算法基本思路

4.3.3 决策树损失函数

4.3.4 剪枝类型——预剪枝、后剪枝、两种剪枝策略对比

总结

优点：

缺点：

1、概述机器学习中的一大类模型，树模型一直以来都颇受学界和业界的重视。目前无论是各大比赛各种大杀器的XGBoost、lightgbm，还是像随机森林、AdaBoost等典型集成学习模型，都是以决策树模型为基础的。

2. 决策树学习旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从所有可能的决策树中直接选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，学习到的决策树是次优的决策树。

决策树学习算法包括3部分：特征选择、决策树的生成和决策树的剪枝。常用的算法有ID3、 C4.5和CART算法。

3.三大经典决策树算法最主要的区别是其特征选择的准则不同。ID3算法选择特征的依据是信息增益、C4.5是信息增益比，而CART则是基尼指数。

4．分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以看成一个if-then规则的集合，也可以看作是定义在特征空间与类空间上的条件概率分布。李航《统计学习方法》P68

2、决策树模型

定义：分类决策树模型是一种描述对实例进行分类的树形结构。

决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点，其中内部结点表示一个特征或属性，叶结点表示一个类。用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定测试序列。在下图中，圆和方框分别表示内部结点和叶结点。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

下图为决策树示意图，圆点——内部节点：特征\属性，方框——叶节点：类

K-近邻算法 可以完成很多分类任务，但是其最大的缺点是无法给出数据的内在含义，决策树的优势在于数据形式非常容易理解。

决策树可以看成一个if-then规则的集合：由决策树的根结点到叶结点的每一条路径构建一条规则； 路径上内部结点的特征对应着规则的条件，二叶结点的类对应这规则的结论。

决策树的路径或其对应的if-then规则集合具有一个重要性质：互斥且完备。每一个实例都被一条路径或者一条规则覆盖，而且只被一条路径或一条规则覆盖。

决策树与条件概率分布：决策树还表示为给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分上。将特征空间划分为互不相交的单元(cell)，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中一个单元。

3、决策树学习

假设给定训练数据集：

为输入实例(特征向量)，n为特征个数， ，N为样本容量。

• 决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。

• 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是决策树学习是由训练数据集估计条件概率模型。 选择与训练集矛盾最小的决策树，同时具有很好的泛化能力；或者的条件概率模型不仅对训练数据有很好的拟合，对未知数据也有很好的预测。

• 决策树学习的损失函数：正则化的极大似然函数。

• 决策树学习的策略：最小化损失函数（以损失函数为目标函数的最小化问题）

• 决策树学习的目标：损失函数确定之后，在损失函数的意义下，选择最优决策树的问题。所以

因为从所有可能的决策树中直接选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，学习到的决策树是次优的决策树。

决策树学习算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

1. 开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。

2. 如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。

3. 如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。

4. 最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。

基本算法如下：

以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。

如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

决策树通常有三个步骤：特征选择、决策树的生成、决策树的修剪。

由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，决策树的剪枝则考虑全局最优。

使用决策树做预测需要以下过程：

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

4、决策树的构建——三步骤

使用决策树做预测的每一步骤都很重要，数据收集不到位，将会导致没有足够的特征让我们构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，将会导致无法构建出分类效果好的决策树模型。从算法方面看，决策树的构建是我们的核心内容。

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

4.1 特征选择

特征选择在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率，如果利用一个特征进行分类的结果与随机分类的结果没有很大差别，则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。

通常特征选择的准则是信息增益(information gain)或信息增益比，后面介绍基尼指数。

那么，什么是信息增益？在讲解信息增益之前，让我们看一组实例，贷款申请样本数据表。

图5.3(a)所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。图5.3(b)所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。

问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。信息增益就能够很好地表示这一直观的准则。

4.1.1 熵（Entropy）

在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。熵也指物体内部的混乱程度，熵值越高，混乱程度越高。或者训练集中不同类别的样本分布越均匀，熵越大，即不确定性越大。

设X是一个取有限个值的离散随机变量，其概率分布为:

随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：

。

当熵和条件熵中的概率由数据估计（如极大似然估计）得到时(由训练集计算得到)，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，如果有0概率，令

一般地，熵H(Y)与条件熵H(Y∣X)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

决策树学习应用信息准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在给定特征A条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。

信息增益算法：

输入：训练数据集D和特征A

输出：特征A对训练数据集D的信息增益g(D, A)

其中，H(D)是数据集D的熵，H(D_i)是数据集Di的熵，H(D∣A)是数据集D对特征A的条件熵。 D_i是D中特征A取第i个值的样本子集，C_k是D中属于第k类的样本子集。n是特征A取 值的个数，K是类的个数。

根据此公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：

4.1.4 信息增益比

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

定义(信息增益比)：

特征A对训练数据集D的信息增益比之比：

信息增益比偏向于取值较少的特征地问题。 特征A地取值越多，样本越混杂，越不纯净；D_{i}中类别分布越均匀，(经验条件)熵越大。为了使越小，所以要选n小的特征来保证比值结果大，也就是对取值数目较少的属性有所偏好。

【代码实现经验熵、信息增益、信息增益比】

import numpy as npimport pandas as pdimport matplotlib.pyplot as plt%matplotlib inlineimport mathimport operatorfrom matplotlib.font_manager import FontPropertiesfrom math import logimport pprintfrom sklearn.datasets import load_irisfrom collections import Counter"""函数说明:计算经验熵(香农熵)Parameters:    datasets - 数据集    j-数据集第j列Returns:     ent - 经验熵(香农熵)     当j=-1时，返回训练数据集D的经验熵     当j为其他时，返回训练数据集关于第j特征的值的熵"""def single_ent(datasets,j):    data_length = len(datasets)#返回数据集的行数即样本个数    label_count = {}#保存每个标签(Label)出现次数的字典    for i in range(data_length):        label = datasets[i][j]#数据集的最后一列        if label not in label_count:#如果标签(Label)没有放入统计次数的字典,添加进去            label_count[label] = 0        label_count[label] += 1#Label计数    ent = -sum([(p / data_length) * log(p / data_length, 2)#计算经验熵                for p in label_count.values()])    return ent#返回经验熵"""函数说明:计算各个特征对于训练集的条件经验熵Parameters:    datasets - 数据集    j - 数据集第j列即特征值索引Returns:     cond_ent - 条件经验熵(香农熵)"""# 经验条件熵$ H(D|A)$def cond_ent(datasets, j):#参数j：指定特征    data_length = len(datasets)    feature_sets = {}    for i in range(data_length):        feature = datasets[i][j]        if feature not in feature_sets:#如果特征没有放入统计次数的字典,添加进去            feature_sets[feature] = []        feature_sets[feature].append(datasets[i])#划分数据集    cond_ent = sum(        [(len(p) / data_length) * single_ent(p,-1) for p in feature_sets.values()])    return cond_ent"""函数说明:计算某特征对于训练集的信息增益Parameters:    datasets - 数据集    j - 数据集第j列即特征值索引Returns:信息增益    """# 信息增益def info_gain(datasets, j):    return single_ent(datasets,-1)-cond_ent(datasets,j)"""函数说明:计算某特征对于训练集的信息增益比Parameters:   datasets - 数据集    j - 数据集第j列即特征值索引Returns:信息增益比"""# 信息增益比def info_gain_ratio(datasets,j):    return 0 if single_ent(datasets,j)==0 else info_gain(datasets,j)/single_ent(datasets,j)"""函数说明:输出所有特征信息增益，并选择信息增益最大的特征，为根结点特征Parameters:    datasets - 数据集Returns:    bestFeature - 信息增益最大的(最优)特征的索引值"""def info_gain_bestfeature(datasets):    count = len(datasets[0]) - 1  #特征数量    features = [] #记录各个特征的信息增益    for c in range(count):        c_info_gain = info_gain(datasets,c)#信息增益        features.append((c, c_info_gain))        print('特征({}) - 信息增益 - {:.3f}'.format(labels[c], c_info_gain))    # 比较大小    best_ = max(features, key=lambda x: x[-1])    bestFeature=best_[0]    return '特征({})的信息增益最大，选择为根节点特征'.format(labels[best_[0]])"""函数说明:输出所有特征信息增益比，并选择信息增益比最大的特征，为根结点特征Parameters:    datasets - 数据集Returns:    bestFeature - 信息增益最大的(最优)特征的索引值"""def info_gain_ratio_bestfeature(datasets):    count = len(datasets[0]) - 1  #特征数量    features1 = [] #记录各个特征的信息增益    for c in range(count):        c_info_gain_ratio = info_gain_ratio(datasets,c)#信息增益比        features1.append((c, c_info_gain_ratio))        print('特征({}) - 信息增益比 - {:.3f}'.format(labels[c], c_info_gain_ratio))    # 比较大小    best_ = max( features1, key=lambda x: x[-1])    bestFeature=best_[0]    return '特征({})的信息增益比最大，选择为根节点特征'.format(labels[best_[0]])

实现上述案例表5.1

1. 创建数据表

def create_data():    datasets = [['青年', '否', '否', '一般', '否'],               ['青年', '否', '否', '好', '否'],               ['青年', '是', '否', '好', '是'],               ['青年', '是', '是', '一般', '是'],               ['青年', '否', '否', '一般', '否'],               ['中年', '否', '否', '一般', '否'],               ['中年', '否', '否', '好', '否'],               ['中年', '是', '是', '好', '是'],               ['中年', '否', '是', '非常好', '是'],               ['中年', '否', '是', '非常好', '是'],               ['老年', '否', '是', '非常好', '是'],               ['老年', '否', '是', '好', '是'],               ['老年', '是', '否', '好', '是'],               ['老年', '是', '否', '非常好', '是'],               ['老年', '否', '否', '一般', '否'],               ]    labels = [u'年龄', u'有工作', u'有自己的房子', u'信贷情况', u'类别']    #返数据集和每个维度的名称    return datasets, labels

可以表格的形式查看原表格（非必要的一步）

datasets, labels = create_data()train_data = pd.DataFrame(datasets, columns=labels)train_data

2. 套用上述模块

info_gain_bestfeature(np.array(datasets))

运行结果

查看结果，与航统计学习方法书上例题5.2答案一样。

info_gain_ratio_bestfeature(np.array(datasets))

4.2决策树算法

构建决策树的算法有很多，比如ID3、C4.5和CART。

4.2.1 ID3算法

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

具体方法：

1. 从根节点(root node)开始，对结点计算的所有可能的特征的信息增益，选择信息增益最大的特征作为该结点特征。
2. 由该特征的不同取值建立子结点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。
3. 最后得到一个决策树。

ID3算法相当于用极大似然法进行概率模型的选择。

决策树ID3算法的局限性

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

• ID3没有考虑连续特征，比如长度、密度都是连续值，无法再ID3中运用。这大大限制了ID3的用途。
• ID3采用信息增益大的特征优先建立决策树的结点。很快人们发现，在相同条件下，取值比较多的特征比取值较少的特征信息增益大。比如一个变量由2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值得比取两个值得信息增益大。如何校正这个呢？
• ID3算法对于缺失值得情况没有考虑
• 没有考虑过拟合的问题
  • ID3算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，下面我们就介绍C4.5算法。

4.2.2 C4.5算法

上一节我们讲到ID3算法有四个主要不足，一是不能处理连续特征，第二个是用信息增益为标准容易偏向于取值较多的特征，最后两个缺失值的处理问题和过拟合问题。昆兰在C4.5算法中改进了上述四个问题。

• 对于第一个问题，不能处理连续特征，C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到达排列为。对于这m-1个点，分别计算以该点作为二元分类时得信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为的值为类别1，大于

  决策树C4.5算法的局限性

  C4.5虽然改进或改善了ID3算法的几个主要问题，但是仍然存在优化的空间。

  1）由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化空间。思路主要有两种：一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一种是后剪枝，即先生成决策树，再通过交叉验证来剪枝。剪枝算法见下篇。

  2）C4.5生成的是多叉树，即一个父结点可以有多个结点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。

  3）C4.5只能用于分类，如果能将决策树用于回归的话，可以扩大它的使用范围。

  4）C4.5由于使用了熵模型，里面有大量的耗时的对数运算，如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多的准确性的话，就更好了。

  这四个问题在CART算法里面部分加以了改进。所以目前如果不考虑集成算法学习的话，在普通的决策树算法里，CART算法是比较优的算法了。scikit_learn决策树使用的也是CART算法。在下篇我们会重点介绍CART算法的主要改进思路。

  4.2.3 Python实现ID3、C4.5算法

  由于ID3算法和C4.5算法相似，因此可以写一个python模块，只不过增加一个选方法(信息增益 or 信息增益比)的函数。

  【代码实现，构建决策树】

  第一部分：构建决策树

  import numpy as npimport pandas as pdimport matplotlib.pyplot as plt%matplotlib inlineimport mathimport operatorfrom matplotlib.font_manager import FontPropertiesfrom math import logimport pprintfrom sklearn.datasets import load_irisfrom collections import Counter"""函数说明:计算经验熵(香农熵)Parameters:    datasets - 数据集    j-数据集第j列Returns:     ent - 经验熵(香农熵)     当j=-1时，返回训练数据集D的经验熵     当j为其他时，返回训练数据集关于第j特征的值的熵"""def single_ent(datasets,j):    data_length = len(datasets)#返回数据集的行数即样本个数    label_count = {}#保存每个标签(Label)出现次数的字典    for i in range(data_length):        label = datasets[i][j]#数据集的最后一列        if label not in label_count:#如果标签(Label)没有放入统计次数的字典,添加进去            label_count[label] = 0        label_count[label] += 1#Label计数    ent = -sum([(p / data_length) * log(p / data_length, 2)#计算经验熵                for p in label_count.values()])    return ent#返回经验熵"""函数说明:计算各个特征对于训练集的条件经验熵Parameters:    datasets - 数据集    j - 数据集第j列即特征值索引Returns:     cond_ent - 条件经验熵(香农熵)"""# 经验条件熵$ H(D|A)$def cond_ent(datasets, j):#参数j：指定特征    data_length = len(datasets)    feature_sets = {}    for i in range(data_length):        feature = datasets[i][j]        if feature not in feature_sets:#如果特征没有放入统计次数的字典,添加进去            feature_sets[feature] = []        feature_sets[feature].append(datasets[i])#划分数据集    cond_ent = sum(        [(len(p) / data_length) * single_ent(p,-1) for p in feature_sets.values()])    return cond_ent"""函数说明:计算某特征对于训练集的信息增益Parameters:    datasets - 数据集    j - 数据集第j列即特征值索引Returns:信息增益    """# 信息增益def info_gain(datasets, j):    return single_ent(datasets,-1)-cond_ent(datasets,j)"""函数说明:计算某特征对于训练集的信息增益比Parameters:   datasets - 数据集    j - 数据集第j列即特征值索引Returns:信息增益比    """# 信息增益比def info_gain_ratio(datasets,j):    return 0 if single_ent(datasets,j)==0 else info_gain(datasets,j)/single_ent(datasets,j)"""函数说明:选取最优特征Parameters:    datasets - 数据集    method-选择最优特征准则：ID3：依据信息增益；C4.5:依据信息增益比Returns:    bestFeature - 信息增益最大的(最优)特征的索引值"""def bestfeature(datasets,method='ID3'):    assert method in ['ID3','C4.5'],"method 须为id3或c45"    def calcEnt(datasets,j):        if method=='ID3':            return info_gain(datasets,j)        if method=='C4.5':            return info_gain_ratio(datasets,j)    count = len(datasets[0]) - 1  #特征数量       features = [] #记录各个特征的信息增益        for c in range(count):        c_info_gain = calcEnt(datasets,c)#信息增益        features.append((c, c_info_gain))        #print('特征({}) - 信息增益 - {:.3f}'.format(labels[c], c_info_gain))    # 比较大小    best_ = max(features, key=lambda x: x[-1])    bestFeature=best_[0]    return bestFeature"""函数说明:统计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中出现次数最多的元素"""函数说明:按照给定特征划分数据集Parameters:    datasets - 待划分的数据集    axis - 划分数据集的特征    value - 需要删除的特征的值Returns:    无"""def splitDataSet(datasets, axis, value):           retDataset = []                                        #创建返回的数据集列表    for featVec in datasets:                             #遍历数据集        if featVec[axis] == value:            reducedFeatVec = featVec[:axis]                #去掉axis特征            reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集            retDataset.append(reducedFeatVec)    return retDataset                                      #返回划分后的数据集"""函数说明:创建决策树Parameters:    datasets - 训练数据集    labels - 分类属性标签    featLabels - 存储选择的最优特征标签Returns:    myTree - 决策树"""def createTree(datasets, labels, featLabels):    classList = [example[-1] for example in datasets]            #取分类标签(是否放贷:yes or no)    if classList.count(classList[0]) == len(classList):            #1、如果类别完全相同则停止继续划分        return classList[0]    if len(datasets[0]) == 1:                                   #2、如果特征集为空即数据集只有1列        return majorityCnt(classList)                          #遍历完所有特征时返回出现次数最多的类标签    bestFeat = bestfeature(datasets,method='ID3')                #3、选择最优特征，方法可以更改    bestFeatLabel = labels[bestFeat]                            #最优特征的标签    featLabels.append(bestFeatLabel)    myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树    del(labels[bestFeat])                                        # 已经选择的特征不再参与分类    featValues = [example[bestFeat] for example in datasets]        #得到训练集中所有最优特征的属性值    uniqueVals = set(featValues)                                #去掉重复的属性值    for value in uniqueVals:                                    #遍历特征，创建决策树。                               myTree[bestFeatLabel][value] = createTree(splitDataSet(datasets, bestFeat, value), labels, featLabels)    return myTree

  第二部分：决策树可视化

  """函数说明:获取决策树叶子结点的数目Parameters:    myTree - 决策树Returns:    numLeafs - 决策树的叶子结点的数目"""def getNumLeafs(myTree):    numLeafs = 0                                                #初始化叶子    firstStr = next(iter(myTree))                                #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]    secondDict = myTree[firstStr]                                #获取下一组字典    for key in secondDict.keys():        if type(secondDict[key]).__name__=='dict':                #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点            numLeafs += getNumLeafs(secondDict[key])        else:   numLeafs +=1    return numLeafs"""函数说明:获取决策树的层数Parameters:    myTree - 决策树Returns:    maxDepth - 决策树的层数"""def getTreeDepth(myTree):    maxDepth = 0                                                #初始化决策树深度    firstStr = next(iter(myTree))                                #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]    secondDict = myTree[firstStr]                                #获取下一个字典    for key in secondDict.keys():        if type(secondDict[key]).__name__=='dict':                #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点            thisDepth = 1 + getTreeDepth(secondDict[key])        else:   thisDepth = 1        if thisDepth > maxDepth: maxDepth = thisDepth            #更新层数    return maxDepth"""函数说明:绘制结点Parameters:    nodeTxt - 结点名    centerPt - 文本位置    parentPt - 标注的箭头位置    nodeType - 结点格式Returns:    无"""def plotNode(nodeTxt, centerPt, parentPt, nodeType):    arrow_args = dict(arrowstyle="<-")                                            #定义箭头格式    font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)        #设置中文字体    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',    #绘制结点        xytext=centerPt, textcoords='axes fraction',        va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)"""函数说明:标注有向边属性值Parameters:    cntrPt、parentPt - 用于计算标注位置    txtString - 标注的内容Returns:    无"""def plotMidText(cntrPt, parentPt, txtString):    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                                            #计算标注位置                       yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)"""函数说明:绘制决策树Parameters:    myTree - 决策树(字典)    parentPt - 标注的内容    nodeTxt - 结点名Returns:    无"""def plotTree(myTree, parentPt, nodeTxt):    decisionNode = dict(boxstyle="sawtooth", fc="0.8")                                        #设置结点格式    leafNode = dict(boxstyle="round4", fc="0.8")                                            #设置叶结点格式    numLeafs = getNumLeafs(myTree)                                                          #获取决策树叶结点数目，决定了树的宽度    depth = getTreeDepth(myTree)                                                            #获取决策树层数    firstStr = next(iter(myTree))                                                            #下个字典                                                     cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)    #中心位置    plotMidText(cntrPt, parentPt, nodeTxt)                                                    #标注有向边属性值    plotNode(firstStr, cntrPt, parentPt, decisionNode)                                        #绘制结点    secondDict = myTree[firstStr]                                                            #下一个字典，也就是继续绘制子结点    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD                                        #y偏移    for key in secondDict.keys():                                       if type(secondDict[key]).__name__=='dict':                                            #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点            plotTree(secondDict[key],cntrPt,str(key))                                        #不是叶结点，递归调用继续绘制        else:                                                                                #如果是叶结点，绘制叶结点，并标注有向边属性值                                                         plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD"""函数说明:创建绘制面板Parameters:    inTree - 决策树(字典)Returns:    无"""def createPlot(inTree):    fig = plt.figure(1, facecolor='white')                                                    #创建fig    fig.clf()                                                                                #清空fig    axprops = dict(xticks=[], yticks=[])    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)                                #去掉x、y轴    plotTree.totalW = float(getNumLeafs(inTree))                                            #获取决策树叶结点数目    plotTree.totalD = float(getTreeDepth(inTree))                                            #获取决策树层数    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;                                #x偏移    plotTree(inTree, (0.5,1.0), '')                                                            #绘制决策树    plt.show()                                                                                 #显示绘制结果     

  案例：

  

  if __name__ == '__main__':    datasets, labels = create_data()#上一例子已创建    featLabels = []    myTree = createTree(datasets, labels, featLabels)    print(myTree)    createPlot(myTree)  

  

  • C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度。
  • α|T|是为了避免过拟合，给优化目标函数增加一个正则项，正则项包含模型的复杂度信息|T|。对于决策树来说，其叶结点的数量|T|越多就越复杂。
  • 参数α控制了两者之间的影响程度，较大的α促使选择较简单的模型(树)，较小的α促使选择较复杂的模型(树)，α=0意味着只考虑模型与训练数据的拟合程度，不考虑模型复杂度。
  • 上式定义的损失函数

    其中的核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。

    （2）后剪枝

    后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。

    周志华老师《机器学习》中述说如下：

    后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。

    李航《统计学习方法》中述说如下：

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

    1. 计算每个结点的经验熵
    2. 递地从树的叶结点向上回缩

    设一组叶结点回缩到父结点之前与之后的整体树分别为，其对应的损失函数值分别是与，如果

    

    则进行剪枝，即将父节点变为新的叶节点。

    3. 返回(2)，直至不能继续为止，得到损失函数最小的子树Tα

    （3）两种剪枝策略对比

    • 后剪枝决策树通常比预剪枝决策树保留了更多的分支；
    • 后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树；
    • 后剪枝决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

    总结

    优点：

    • 计算复杂度不高；
    • 对中间缺失值不敏感；
    • 解释性强，在解释性方面甚至比线性回归更强；
    • 与传统的回归和分类方法相比，决策树更接近人的决策模式，可以用图形表示，非专业人士也可以轻松理解；
    • 可以直接处理定性的预测变量而不需创建哑变量。

    缺点：

    • 决策树的预测准确性一般比回归和分类方法弱，但可以通过用集成学习方法组合大量决策树，显著提升树的预测效果；

    • 可能会产生过度匹配的问题

    【SK-Learn代码实现】

    CART算法见后一篇