Question

决策树方法在分类、预测、规则提取等领域有着广泛应用。在20世纪70年代后期和80年代初期，机器学习研究者J.Ross Quinilan提出了ID3算法以后，决策树在机器学习、数据挖掘领域得到极大的发展。Quinilan后来又提出了C4.5，成为新的监督学习算法。1984年几位统计学家提出了CART分类算法。ID3和CART算法大约同时被提出，但都是采用类似的方法从训练样本中构建决策树。

决策树是树状结构，它的每一个叶节点对应着一个分类，非叶节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。对于非纯的叶节点，多数类的标号给出到达这个节点的样本所属的类。构造决策树的核心问题是在每一步如何选择适当的属性对样本做拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下、分而治之的过程。常用的决策树算法见表7-2。

表7-2 决策树算法分类

7.2.1 ID3算法

ID3算法基于信息熵来选择最佳测试属性。它选择当前样本集中具有最大信息增益值的属性作为测试属性。样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时决策树上相当于该样本集的节点长出新的叶子节点。ID3算法根据信息论理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶子节点上选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的拆分，从而得到较小的决策树。

1.基本原理

设S是s个数据样本的集合。假定类别属性具有m个不同的值：C_i （i=1，2，…，m）。设s_i 是类C_i 中的样本数。对一个给定样本，总信息熵为

其中，P_i 是任意样本属于C_i 的概率，一般可以用 估计。

若一个属性A具有k个不同的值{a₁ ，a₂ ，…，a_k }，利用属性A将集合S划分为j个子集{S₁ ，S₂ ，…，S_j }，其中S_j 包含了集合S中属性A取值为a_j 的样本。若选择属性A为测试属性，则这些子集就是从集合S的节点生长出来的新的叶节点。设s_jj 是子集S_j 中类别为C_i 的样本数，则根据属性A划分样本的信息熵值为

其中， 。 是子集S_j 中类别为C_i 的样本的概率。

最后，用属性A划分样本集S后所得的信息增益（Gain）为：

Gain（A）=I（s₁ ，s₂ ，…，s_m ）-E（A）

显然E（A）越小，Gain（A）的值越大，说明选择测试属性A对于分类提供的信息越大，选择A之后分类的不确定程度就越小。属性A的k个不同的值对应样本集S的k个子集或分支，通过递归调用上述过程（不包括已选择的属性），生成其他属性作为节点的子节点和分支来生成整棵决策树。ID3决策树算法作为一个典型的决策树学习算法，其核心是在决策树的各级节点上都用信息增益作为判断标准进行属性的选择，使得在每个非叶子节点上进行测试时，都能获得最大的类别分类增益，使分类后数据集的熵最小。这样的处理方法使得树的平均深度最小，从而有效地提高分类效率。

2.算法实现

ID3算法的详细实现步骤如下：

1）对当前样本集合，计算所有属性的信息增益。

2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集。

3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号之后返回调用处；否则对子样本集递归调用本算法。

我们通过举例说明：使用scikit-learn建立基于信息熵的决策树模型。这个例子是经典的Kaggle^[1] 101问题——泰坦尼克生还预测，见表7-3。

表7-3 泰坦尼克生还预测的部分数据

为了方便说明，数据集有许多属性被删除了。通过观察可知：列Survived是指是否存活，是类别标签，属于预测目标；列Sex的取值是非数值型的。我们在进行数据预处理时应该合理应用Pandas的功能，让数据能够被模型接受。具体代码如代码清单7-3所示。

代码清单7-3 ID3算法预测生还者

# -*- coding:utf-8 -*-
# 使用
ID3算法进行分类
import pandas as pd
from sklearn.tree import DecisionTreeClassifier as DTC, export_graphviz
data = pd.read_csv('../data/titanic_data.csv', encoding='utf-8')
data.drop(['PassengerId'], axis=1, inplace=True)          # 舍弃
ID列，不适合作为特征
# 数据是类别标签，将其转换为数，用
1表示男，
0表示女
data.loc[data['Sex'] == 'male', 'Sex'] = 1
data.loc[data['Sex'] == 'female', 'Sex'] = 0
data.fillna(int(data.Age.mean()), inplace=True)
print data.head(5)                              # 查看数据
X = data.iloc[:, 1:3]                    # 为便于展示，未考虑年龄（最后一列）
y = data.iloc[:, 0]
dtc = DTC(criterion='entropy')               # 初始化决策树对象，基于信息熵
dtc.fit(X, y)                         # 训练模型
print '输出准确率：
', dtc.score(X,y)
# 可视化决策树，导出结果是一个
dot文件，需要安装
Graphviz才能转换为
.pdf或
.png格式
with open('../tmp/tree.dot', 'w') as f:
    f = export_graphviz(dtc, feature_names=X.columns, out_file=f)

*代码详见：示例程序/code/7-2.py

运行代码后，将会输出一个tree.dot的文本文件。为了进一步将它转换为可视化格式，需要安装Graphviz（跨平台的、基于命令行的绘图工具），再在命令行中以如下方式编译。

dot –
Tpdf tree.dot –
o tree.pdf
dot –
Tpng tree.dot –
o tree.png

生成的效果图如图7-4所示。

图7-4 决策树可视化效果图

7.2.2 其他树模型

ID3算法是决策树系列中的经典算法之一，包含了决策树作为机器学习算法的主要思想。但ID3算法在实际应用中有许多不足，所以在此之后提出了大量的改进策略，如C4.5算法、C5.0算法和CART算法。在这一节中，我们将简要介绍这三种决策树算法。常用的决策树算法还有SLIQ算法、SPRINT算法、CHAID算法和PUBLIC算法等。

由于ID3决策树算法采用信息增益作为选择测试属性的标准，会偏向于选择取值较多的，即所谓高度分支属性，而这类属性并不一定是最优的属性。同时，ID3算法只能处理离散属性，对于连续型的属性，在分类前需要对其进行离散化。为了解决倾向于选择高度分支属性的问题，人们采用信息增益率作为选择测试属性的标准，这样便得到C4.5决策树算法。

1.C4.5算法

C4.5是基于ID3算法进行改进后的一种重要算法，它是一种监督学习算法，其目标是通过学习，找到一个从属性值到类别的映射关系，并且这个映射能用于对新的未知类别的实体进行分类。

C4.5算法的优点是：

1）产生的分类规则易于理解，准确率较高。

2）改进了ID3算法的缺点：使用信息增益选择属性时偏向于选择高度分支属性。

3）相比于ID3算法，能处理非离散数据或不完整数据。

C4.5算法的缺点是：

1）在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

2）当训练集大小超过内存上限时程序无法运行，故只适合能够驻留于内存的数据集。

2.C5.0算法

C5.0算法是C4.5算法的修订版，适用于处理大数据集，采用Boosting方式提高模型准确率，又称为Boosting Trees，在软件上计算速度比较快，占用的内存资源较少。C5.0作为经典的决策树模型算法之一，可生成多分支的决策树，C5.0算法根据能够带来的最大信息增益的字段拆分样本。第一次拆分确定的样本子集随后再次拆分，通常是根据另一个字段进行拆分，这一过程重复进行直到样本子集不能再被拆分为止。最后，重新检查最低层次的拆分节点，那些对模型值没有显著贡献的样本子集被剔除或者修剪。

C5.0较其他决策树算法的优势在于：

1）C5.0模型在面对数据遗漏和输入字段很多的问题时非常稳健。

2）C5.0模型比一些其他类型的模型易于理解，模型输出的规则有非常直观的解释。

3）C5.0也提供强大的技术支持以提高分类的精度。

3.CART算法

分类回归树（Classification And Regression Tree，CART）算法最早由Breiman等人提出，现已在统计领域和数据挖掘技术中普遍使用，Python中的scikit-learn模块的Tree子模块主要使用CART算法来实现决策树。

实际上，Breiman在1984年就提出：“用于解决分类问题的树模型和用于处理回归问题的树模型具有相似之处”。这也是CART算法名称的由来，它既能胜任“分类”任务，也能满足“回归”的需求。我们将利用CART算法对数据点进行回归处理来简要解释CART如何适用于回归任务，以防读者感到困惑。

图7-5中的数据由正弦函数sin（x）随机生成。可以明显观察到：由CART算法生成的回归线对应一个阶梯函数。用生成图7-4时提到的方法，我们将CART模型内部的分类规则可视化，如图7-6所示。

图7-5 CART算法用作回归问题

图7-6 CART决策规则可视化

读者可以在此按下“暂停键”，仔细思考图7-5与图7-6的联系。由于决策树的特性，一维自变量仅能体现为阶梯函数（不可能出现斜线或曲线）。但考虑极限情况，阶梯函数可以逼近一条曲线。这里可以认为：在仅允许用阶梯函数做回归的条件下，算法达到了均方误差最小的要求。

CART算法采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART算法构建的预测树在很多情况下比常用的统计方法构建的代数预测准则更加准确，而且数据越复杂、变量越多，算法的优越性就越显著。模型的关键在于预测准则的构建。

它是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个属性有多个取值，也是把数据分为两部分。在CART算法中主要分为两个步骤：第一步是将样本递归划分进行建树过程；第二步是用验证数据进行剪枝。

[1] Kaggle：世界上最大的数据科学家社区，常年开放数据挖掘挑战，101是最简单的练习题。