目录

3.3.1        原理简介 

3.3.2        算法步骤

3.3.3        实战

3.3.4        实验

前半部分是理论介绍，后半部分是代码实践，可以选择性阅读。 

决策树（decision tree）是功能强大而且相当受欢迎的分类和预估方法，它是一种有监督的学习算法，以树状图为基础，其输出结果是一系列简单实用的规则，故得名决策树。

决策树模型基于特征对实例分类，它是一种树状结构。决策树的优点是可读性强，分类速度快。学习决策树时，通常采用损失函数最小化原则。

3.3.1        原理简介 

决策树算法是一个贪心算法，即在特性空间上执行递归的二元分割，决策树由节点和有向边组成。内部节点表示一个特征或者属性；叶子节点表示一个分类。使用决策树进行分类时，将实例分配到叶节点的类中，该叶节点所属的类就是该节点的分类。

决策树可以表示给定特征条件下，类别的条件概率分类。将特征空间划分为互不相交的单元。设某个单元内部有个样本点，则它定义了一个条件概率分布为第个分类。 

• 每个单元对应于决策树的一条路径。
• 所有单元的条件概率分布构成了决策树所代表的条件概率分布。
• 在单元内部有个样本点，但是整个单元都属于类。其中，。即单元内部的个样本点，哪个分类占优，则整个单元都属于该类。

3.3.2        算法步骤

构建决策树通常包括三个步骤：特征选择、决策树生成、决策树剪枝。

构建决策树时，通常将正则化的极大似然函数作为损失函数，其学习目标是损失函数为目标函数的最小化。构建决策树的算法通常是递归地选择最优特征，并根据该特征对训练数据进行分割，步骤如下：

1. 构建根节点，使所有的训练样本都位于根节点。
2. 选择一个最优特征。通过该特征将训练数据分割成多个子集，确保各个子集都有最好的分类，但要考虑下列两种情况：
   1. 若子集已能够被较好的分类，则构建叶节点，并将该子集划分到对应的叶节点。
   2. 若某个子集不能够被较好的分类，则对该子集继续划分。
3. 递归执行，直到所有的训练样本都被较好的分类，或者没有合适的特征为止。是否被较好的分类，可通过后面介绍的指标来判断。

通过如上步骤生成的决策树对训练样本有很好的分类能力，但是需要的是对未知样本的分类能力。因此通常需要对已生成的决策树进行剪枝，从而使决策树具有更好的泛化能力。剪枝过程是去掉过于细分的叶节点，从而提高泛化能力。

1.特征选择

 特征选择就是选取有较强分类能力的特征。分类能力通过信息增益或者信息增益比来刻画。选择特征的标准是找出局部最优的特征作为判断进行切分，取决于切分后节点数据集中类别的有序程度，划分后的分区数据越纯，切分规则越合适。可衡量节点数据集纯度的有熵、基尼系数和方差。熵和基尼系数是针对分类的，方差是针对回归的。 

2.决策树生成

基本的决策树生成算法中，典型的有ID3生成算法和C4.5生成算法，它们生成树的过程大致相似。ID3采用信息增益作为特征选择的度量，而C4.5采用信息增益比。 

关于两个算法有几点说明如下：

1. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进。
   1. 用信息增益比来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足。
   2. 在树的构造过程中进行剪枝。
   3. 能够完成对连续属性的离散化处理。
   4. 能够对不完整数据进行处理。 
2. C4.5算法的优点：
   1. 产生的分类规则易于理解；
   2. 准确率较高。
3. C4.5算法的缺点：
   1. 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，导致算法低效。
   2. C4.5算法只适合于能够留驻于内存的数据集，当训练集大到内存无法容纳时，程序无法运行。
4. 决策树可能只用到特征集中的部分特征。
5. C4.5算法和ID3算法只有树的生成算法，生成的树容易产生过拟合现象。

3.决策树剪枝

需要剪枝的原因是：决策树产生了过拟合现象。 

发生过拟合是由于决策树太复杂，解决过拟合的方法是控制模型的复杂度，对于决策树来说就是简化模型，即为剪枝。

        决策树剪枝的过程是从已生成的决策树上裁掉一些子树或者叶节点。剪枝的目标是通过极小化决策树的整体损失函数或代价函数来实现的。

        决策树剪枝的目的是通过剪枝来提高泛化能力。剪枝的思路就是在决策树对训练数据的预测误差和数据复杂度之间找到一个平衡。

4.CART模型

分类与回归树（classification and regression tree，CART）模型也是一种决策树模型，它既可以用于分类，也可以用于回归。其学习算法分为如下两步：

1. 决策树生成：用训练数据生成决策树，生成树尽可能的大。
2. 决策树剪枝：基于损失函数最小化的标准，用验证数据对生成的决策树剪枝。

CART模型采用不同的最优化策略。

1. CART回归生成树用平方误差最小化策略。
2. CART分类生成树用基尼系数最小化策略。

3.3.3        实战

1.数据集

采用鸢尾花数据集。 

2.Sklearn实现

DecisionTreeClassifier()函数实现了分类决策树，用于分类问题。

代码如下： 

import numpy as np
import matplotlib as plt
from sklearn import datasets
from sklearn import model_selection
from sklearn.tree import DecisionTreeClassifier


def test_DecisionTreeClassifier(* data):
    X_train, X_test, y_train, y_test = data
    clf = DecisionTreeClassifier()
    clf.fit(X_train, y_train)
    print("Training score:%f" % (clf.score(X_train, y_train)))
    print("Testing score:%f" % (clf.score(X_test, y_test)))


X, y = datasets.load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.3, random_state=42)
test_DecisionTreeClassifier(X_train, X_test, y_train, y_test)

 运行结果：

实验结果非常好，下面考察评价切分质量的评价准则criterion对分类性能的影响，函数如下 

import numpy as np
import matplotlib as plt
from sklearn import datasets
from sklearn import model_selection
from sklearn.tree import DecisionTreeClassifier


def test_DecisionTreeClassifier_criterion(* data):
    X_train, X_test, y_train, y_test = data
    criterions = ['gini', 'entropy']
    for criterion in criterions:
        clf = DecisionTreeClassifier(criterion=criterion)
        clf.fit(X_train, y_train)
        print("criterion:%s" % criterion)
        print("Training score:%f" % (clf.score(X_train, y_train)))
        print("Testing score:%f" % (clf.score(X_test, y_test)))
        

X, y = datasets.load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.25, random_state=42)
test_DecisionTreeClassifier_criterion(X_train, X_test, y_train, y_test)

实验结果：

可以看出二者对训练集的拟合效果都很好。接下来检验随即划分与最优划分的影响，函数如下： 

import numpy as np
import matplotlib as plt
from sklearn import datasets
from sklearn import model_selection
from sklearn.tree import DecisionTreeClassifier


def test_DecisionTreeClassifier_splitter(* data):
    X_train, X_test, y_train, y_test = data
    splitters = ['best', 'random']
    for splitter in splitters:
        clf = DecisionTreeClassifier(splitter=splitter)
        clf.fit(X_train, y_train)
        print("splitter:%s" % splitter)
        print("Training score:%f" % (clf.score(X_train, y_train)))
        print("Testing score:%f" % (clf.score(X_test, y_test)))
        

X, y = datasets.load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.25, random_state=42)
test_DecisionTreeClassifier_splitter(X_train, X_test, y_train, y_test)

实验结果：

可以看出，二者对训练集的拟合效果都很好。 

最后考察决策树深度的影响。决策树的深度对应树的复杂度。决策树越深，则模型越复杂，函数如下： 

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn import model_selection
from sklearn.tree import DecisionTreeClassifier


def test_DecisionTreeClassifier_deepth(*data, maxdeepth):
    X_train, X_test, y_train, y_test = data
    deepths = np.arange(1, maxdeepth)
    training_scores = []
    testing_scores = []
    for deepth in deepths:
        clf = DecisionTreeClassifier(max_depth=deepth)
        clf.fit(X_train, y_train)
        training_scores.append(clf.score(X_train, y_train))
        testing_scores.append(clf.score(X_test, y_test))
    fig = plt.figure()
    ax = fig.add_subplot(1, 1, 1)
    ax.plot(deepths, training_scores, label="training score", marker='o')
    ax.plot(deepths, testing_scores, label="testing score", marker='x')
    ax.set_xlabel("maxdepth")
    ax.set_ylabel("score")
    ax.set_title("Decision Tree Classification")
    ax.legend(framealpha=0.5, loc='best')
    plt.show()

        

X, y = datasets.load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.3, random_state=42)
test_DecisionTreeClassifier_deepth(X_train, X_test, y_train, y_test, maxdeepth=100)

实验结果如下：

可以看出，随着树深度的增加（对应着模型复杂度的提高），模型对训练集和预测集的拟合度都在提高。这里的训练数据集大小较小（大约150个数据），所以结果看上去非常号，在面对较大的数据集时，效果就会下降。

3.算法实现

下面以一个经典的打球的例子来说明如何构建决策树。是否去打球(play)主要由天气(outlook)、温度(temperature)、湿度(humidity)、是否有风(windy)来决定。样本中共14条数据。 

打球数据集示例

序号	outlook	temperature	humidity	windy	play
1	sunny	hot	high	FALSE	no
2	sunny	hot	high	TRUE	no
3	overcast	hot	high	FALSE	yes
4	rainy	mild	high	FALSE	yes
5	rainy	cool	normal	FALSE	yes
6	rainy	cool	normal	TRUE	no
7	overcast	cool	normal	TRUE	yes
8	sunny	mild	high	FALSE	no
9	sunny	cool	normal	FALSE	yes
10	rainy	mild	normal	FALSE	yes
11	sunny	mild	normal	TRUE	yes
12	overcast	mild	high	TRUE	yes
13	overcast	hot	normal	FALSE	yes
14	rainy	mild	high	TRUE	no

下面将分别介绍使用ID3算法和C4.5算法构建决策树的方法。

1）使用ID3算法构建决策树。 

ID3算法是使用信息增益来选择特征的。

步骤如下：

（1）计算play(是否去打球)的经验熵

 在本例中，目标变量就是play(是否去打球)，即yes(打球)和no(不打球)。。就是目标变量play(是否去打球)的分类数，yes(打球)这个分类下有9个样本，而no(不打球)这个分类下有5个样本，所以信息熵

（2）计算outlook(天气)的经验熵

记outlook特征为特征A，共有3个不同的取值，即，根据特征A的取值，将数据集分为如下3个子集。

• sunny的子集：共有5个样本，2个打球，3个不打球
• overcast的子集：共有4个样本，均为打球
• rainy的子集：共有5个样本，3个打球，2个不打球

 每个子集可以分别计算熵，公式如下：

所以outlook特征的信息增益为 

（3）计算temperature(温度)的经验熵

记temperature特征为特征B，共有3个不同的取值，即，根据特征B的取值，将数据集分为如下3个子集。

• hot的子集：共有4个样本，2个打球，2个不打球
• mild的子集：共有6个样本，4个打球，2个不打球
• cool的子集：共有4个样本，3个打球，1个不打球

每个子集可以分别计算熵，公式如下：

所以temperature特征的信息增益为  

（4）计算humidity(湿度)的经验熵

记humidity特征为特征C，共有2个不同的取值，即，根据特征C的取值，将数据集分为如下2个子集。

• high的子集：共有7个样本，3个打球，4个不打球
• normal的子集：共有7个样本，6个打球，1个不打球

 每个子集可以分别计算熵，公式如下：

所以humidity特征的信息增益为   

（5）计算windy(是否有风)的经验熵

记windy特征为特征E(区别于数据集D)，共有2个不同的取值，即，根据特征E的取值，将数据集分为如下2个子集。

• TRUE的子集：共有6个样本，2个打球，4个不打球
• FALSE的子集：共有8个样本，6个打球，2个不打球

 每个子集可以分别计算熵，公式如下：

 所以humidity特征的信息增益为   

（6）确定root节点

对比上面四个特征的信息增益如下：

                

                

                

                

可以看出outlook特征的信息增益最大，所以选择outlook特征作为决策树的根节点。

        特征A(天气)有三个不同的取值，即，根据特征A的取值，将数据集分为如下3个子集。

• sunny的子集：共有5个样本，2个打球，3个不打球
• overcast的子集：共有4个样本，均为打球
• rainy的子集：共有5个样本，3个打球，2个不打球

对每个子集分别计算熵如下：

        上面的overcast熵=0，如下图所示。也就是也部分已经分好类了，都为打球，所以直接就可以作为叶节点，不需要在进行分类。而sunny熵、rainy熵都大于0，还需要按照上面根节点的选择方式继续选择特征。

（7）计算outlook特征为sunny的数据集，该数据集如下表所示

1.计算outlook这个分支样本的信息熵。 

yes这个分类下有2个样本，而no这个分类下有3个样本，所以信息熵

2.计算temperature特征的信息增益

记temperature特征为特征A，共有3个不同的取值，即，根据特征B的取值，将数据集分为如下3个子集。

• hot的子集：共有2个样本，2个不打球
• mild的子集：共有2个样本，1个打球，1个不打球
• cool的子集：共有1个样本，1个打球

每个子集可以分别计算熵，公式如下：

所以temperature特征的信息增益为  

3.计算humidity的信息增益

记humidity特征为特征B，共有2个不同的取值，即，根据特征B的取值，将数据集分为如下2个子集。

• high的子集：共有3个样本，3个不打球
• normal的子集：共有3个样本，2个打球

每个子集可以分别计算熵，公式如下：

 所以humidity特征的信息增益为   

humidity特征划分已经将信息熵降到0，所以不用继续计算了，直接把湿度作为分类的特征即可，如下图所示

（8）计算outlook特征为rainy的数据集

用相同的方法计算此部分的数据后，最终得出的决策树如下图所示

下面的代码是基于ID3算法的信息增益来实现的。 

code 

代码块过长，这里只展示结果，源码在我的github仓库中。

2）使用C4.5算法构建决策树 

        C4.5算法使用信息增益率来进行特征选择。由于前面ID3算法使用信息增益选择分裂属性的方式会倾向于选择具有大量值的特征，如对于no，每条数据都对应一个play值，即按此特征划分，每个划分都是纯的(即完全的划分，只有属于一个类别)，no的信息增益为最大值1，但这种按该特征的每个值进行分类的方式是没有任何意义的。为了解决这一弊端，有人提出了采用信息增益率(GainRate)来选择分裂特征。计算方式如下：

其中，就是ID3算法中的新增增益。

计算各特征的信息增益率如下： 

1.outlook特征的信息增益率。 

上述内容已经计算了

2.temperature特征的信息增益率 

上述内容已经计算了

3.humidity特征的信息增益率

上述内容已经计算了

4.windy特征的信息增益率

上述内容已经计算了

对比上面四个特征的信息增益率，outlook特征的信息增益率最大，所以outlook作为root节点。其他计算方法类似。 

code

代码块过长，这里只展示结果，源码在我的github仓库中。

3.3.4        实验

1.实验目的

学会决策树的基本原理和基本的构建方法。了解分类问题以及训练集、测试集的构造以及决策树的基本定义，决策树的用法，构建决策树的方法流程。并拓展到在属性选择时用什么指标来衡量，了解ID3信息熵以及CART使用基尼系数进行度量的两种重要方法。

2.实验数据

打球数据集

 打球数据集示例

序号	outlook	temperature	humidity	windy	play
1	sunny	hot	high	FALSE	no
2	sunny	hot	high	TRUE	no
3	overcast	hot	high	FALSE	yes
4	rainy	mild	high	FALSE	yes
5	rainy	cool	normal	FALSE	yes
6	rainy	cool	normal	TRUE	no
7	overcast	cool	normal	TRUE	yes
8	sunny	mild	high	FALSE	no
9	sunny	cool	normal	FALSE	yes
10	rainy	mild	normal	FALSE	yes
11	sunny	mild	normal	TRUE	yes
12	overcast	mild	high	TRUE	yes
13	overcast	hot	normal	FALSE	yes
14	rainy	mild	high	TRUE	no

3.实验要求

分别使用scikit-learn的相关包、Python语言编程来构建ID3、ID4.5决策树，最后将训练出的决策树以图表形式显示。

即为算法实现中的结果。