---

三、决策树分类方法

  决策树 (Decision Tree) 是从一组无次序、无规则，但有类别标号的样本集中推导出的、树形表示的分类规则。树的叶子结点表示类别标号，即分类属性的取值，对应一个数据对象的子集；树的内部结点为条件属性，它是一个数据对象子集合的标识符；一个内部结点为每个条件属性值或组合的条件属性值构成一个树枝，连接到树的下一层结点 (也是数据对象子集)；从树根到叶子结点的一条路径称为一条决策规则，它可以对未知数据进行分类或预测。

（一）决策树生成框架

1、决策树的概念

  决策树是一棵有向树，也称为根树，它由矩形结点、椭圆型结点和有向边构成。因有向边的方向始终朝下，故省略表示方向的箭头。决策树包含三种结点，并用含属性值标记的有向边相连。

（1）根结点 (root node)，用矩形表示，如 “天气” 结点，它没有入边，但有零条或多条出边。其中的字串 “天气” 是样本集属性名称。
（2）内部结点 (internal node)，用矩形表示。如 “温度” 结点，它恰有一条入边，但有两条或多条出边。“温度” 是样本集属性名称。
（3）叶结点 (leaf node) 或终结点 (terminal node)，用椭圆表示，如 “是” 结点，恰有一条入边，但没有出边。椭圆形里的 “是” 等字符串是样本集的一个类别标号。
（4）每条有向边都用其出点的属性值标记，如 “晴天”，“多云”、“雨天” 是其出点 “天气” 属性的三种取值。

通常，一个属性有多少种取值，就从该结点引出多少条有向边，每一条边代表属性的一种取值。

2、Hunt算法框架

  Hunt算法是Hunt等人1966年提出的决策树算法，它在选择划分训练集的属性时采用贪心策略，将训练集相继划分成较纯 (包括更少类别) 的子集，以递归方式建立决策树，并成为许多决策树算法的衍生框架，包括ID3、C4.5等。

  假设结点h对应的样本集用 $S_h$ 表示，而 C = { C 1 , C 2 , ⋯ , C k } C=\{C_1, C_2, \cdots, C_k\} C={C1​,C2​,⋯,Ck​} 是其类别属性，则Hunt算法的递归定义如下：
（1）如果 $S_h$ 中所有样本点都属于同一个类 $C_h$，则 $h$ 为叶结点，并用分类标号 $C_h$ 标记该结点。
（2）如果 $S_h$ 中包含多个类别的样本点，则选择一个 “好” 的属性 $A$，以属性 $A$ 命名 $h$ 并作为一个内部结点；然后按属性 $A$ 的取值将 $S_h$ 划分为较小的子集，并为每个子集创建 $A$ 的子女结点；然后把 $A$ 的每个子女结点作为 $h$ 结点，递归地调用Hunt算法。

说明：第（2）步是对训练集的划分，其关键是如何选择一个 “好” 的属性，这就需要好的 “属性测试条件（Attribute Test Condition）”。

3、Hunt算法的停止

简单策略：分裂结点直到所有的记录都属于同一个类，或者所有的记录都具有相同的属性值。
其它策略：在实际过程中还可能出现其它情况，应该考虑其它的标准来提前终止决策树的生长过程。比如附加条件
① 子女结点为空
在Hunt算法第（2）步所创建的子女结点可能为空，即不存在与这些结点条件相关联的样本点，则仍将该结点设为叶结点，其类别标号采用其父结点上多数样本的类别标号。
② 训练集 $S_h$ 属性值完全相同，但类别标号却不相同
即不可能进一步划分这些样本点，故应将该结点设置为叶结点，其类别标号采用该结点多数样本的类别标号。

（二）ID3分类方法

  ID3分类算法以信息论的信息熵为基础，以信息增益度为 “属性测试条件” ，并选择信息增益最大的属性对训练集进行分裂，从而实现对数据的归纳分类。

1、信息熵

  熵 (entropy) 概念最早来源于统计热力学，它是热力学系统混乱程度的一种度量。系统的混乱程度越低，其熵值就越小。

定义9-2 设 $\xi$ 为可取n个离散数值的随机变量，它取 ${\epsilon }_i$ 的概率为 $p({\epsilon }_i)(i=1,2,\cdots ,n)$，则我们定义 $$E(\xi )=-\sum _{i=1}^{n}p({\epsilon }_i){\log }_{2}p({\epsilon }_i)\text{\hspace{1em}(9-2)}$$为随机变量 $\xi$ 的信息熵 (Information Entropy)。

  样本数据集 $S$ 的任一属性 $A$ 都可看作一个随机变量，假设其取值为 { a 1 , a 2 , ⋯ , a n } \{a_1, a_2 ,\cdots, a_n\} {a1​,a2​,⋯,an​}，则 $E(A)$ 就是属性 $A$ 所有取值的信息熵，其熵值越小所蕴含的不确定信息越小，越有利于数据的分类。

定义9-3 设 $S$ 是有限个样本点集合，分类属性 C = { C 1 , C 2 , ⋯ , C k } C=\{C_1,C_2,\cdots,C_k\} C={C1​,C2​,⋯,Ck​}，有 $S=C_1\cup C_2\cup \cdots \cup C_k$，且 $C_i\cap C_j=\varphi (i\ne j)$，则定义 $C$ 划分样本集 $S$ 的信息熵 (简称$C$的分类信息熵) 为 $$E(S,C)=-\sum _{i=1}^k\frac{|C_i|}{|S|}{\log }_2\frac{|C_i|}{|S|}\text{\hspace{1em}(9-3)}$$ 其中，$|C_i|$ 表示类 $C_i$ 中的样本点个数，$|C_i|/|S|$ 也被称为 $S$ 中任意一个样本点属于 $C_i(i=1,2,\cdots ,k)$ 的概率。

定义9-4 设 $S$ 是有限个样本点的集合，其条件属性 $A$ 划分 $S$ 所得子集为 { S 1 , S 2 , ⋯ , S v } \{S_1,S_2,\cdots,S_v\} {S1​,S2​,⋯,Sv​}，则定义 $A$ 划分样本集 $S$ 的信息熵 (简称属性$A$的分类信息熵) 为 $$E(S,A)=-\sum _{j=1}^v\frac{|S_j|}{|S|}{\log }_2\frac{|S_j|}{|S|}\text{\hspace{1em}(9-4)}$$ 其中 $|S_j|/|S|$ 也称为 $S$ 中任意一个样本点属于 $S_j(i=1,2,\cdots ,v)$ 的概率。

定义9-5 设 $S$ 是有限个样本点的集合，其条件属性 $A$ 划分 $S$ 所得子集为 { S 1 , S 2 , ⋯ , S v } \{S_1,S_2,\cdots,S_v\} {S1​,S2​,⋯,Sv​}，则定义条件属性 $A$ 划分样本集 $S$ 相对于 $C$ 的信息熵 (简称$A$相对$C$的分类信息熵) 为 $$E(S,A|C)=\sum _{j=1}^v\frac{|S_j|}{|S|}E(S_j,C)\text{\hspace{1em}(9-5)}$$ 其中，$|S_i|/|S|$ 充当分类属性 $C$ 划分第 $j$ 个子集 $S_j$ 的信息熵权重；而 $E(S_j,C)$ 就是 $C$ 分类 $S_j$ 的信息熵。$$E(S_j,C)=-\sum _{i=1}^k\frac{|C_i\cap S_j|}{|S_j|}{\log }_2\left(\frac{|C_i\cap S_j|}{|S_j|}\right)\text{\hspace{1em}(9-6)}$$ 其中 $|C_i\cap S_j|/|S_j|$ 也称为子集 $S_j$ 中样本属于类 $C_i$ 的概率 $(i=1,2,\cdots ,k;j=1,2,\cdots ,v)$。

根据信息熵的概念，$E(S,A|C)$ 的值越小，则利用条件属性 $A$ 对 $S$ 进行子集划分的纯度越高，即分类能力越强。

2、信息增益

定义9-6 条件属性 $A$ 划分样本集合 $S$ 相对 $C$ 的信息增益 (information gain) (也称为$A$ 相对$C$的分类信息增益，简称$A$的信息增益) 定义为 $$gain(S,A|C)=E(S,C)-E(S,A|C)\text{\hspace{1em}(9-7)}$$ 即 $gain(S,A|C)$ 是分类属性 $C$ 划分样本集 $S$ 的信息熵与属性 $A$ 划分样本集 $S$ 相对 $C$ 的信息熵之差。

3、ID3算法

  ID3算法用信息增益作为属性测试条件，且信息增益值越大以该属性作为分支结点越好。因此，设 $S_h$ 是结点h的样本集，而 C = { C 1 , C 2 , ⋯ , C k } C=\{C_1, C_2, \cdots, C_k\} C={C1​,C2​,⋯,Ck​} 是其类别属性，则ID3算法的递归定义如下：
（1）如果 $S_h$ 中所有记录都属于同一个类 $C_h$，则 $h$ 作为一个叶结点，并用分类标号 $C_h$ 标记该节点。
（2）如果 $S_h$ 中包含有多个类别的样本点，则记 $S=S_h$，
  ① 计算 $C$ 划分样本集 $S$ 的信息熵 $E(S,C)$；
  ② 计算 $S$ 中每个属性 $A^{\prime }$ 划分 $S$ 相对于 $C$ 的信息熵 $E(S,A^{\prime }|C)$ 及其信息增益 $gain(S,A^{\prime }|C)=E(S,C)-E(S,A^{\prime }|C)$；
  ③ 假设取得最大增益的属性为 $A$，则创建属性 $A$ 结点；
  ④ 设属性 $A$ 划分 $S$ 所得子集的集合为 { S 1 , S 2 , ⋯ , S v } \{S_1,S_2,\cdots,S_v\} {S1​,S2​,⋯,Sv​}，则从子集 $S_h(h=1,2,\cdots ,v\}$ 中删除属性 $A$ 后仍将其记作 $S_h$，为 $A$ 结点创建子女结点 $S_h$，并对 $S_h$ 递归地调用ID3算法。

4、从决策树提取分类规则

（1）如果天气=“晴”$\wedge$湿度=“大”，则适宜打球=“否”。
（2）如果天气=“晴”$\wedge$湿度=“小”，则适宜打球=“是”。
（3）如果 天气=“云”，则 适宜打球=“是”。
（4）如果 天气=“雨”$\wedge$风力=“有”，则适宜打球=“否”。
（5）如果 天气=“雨”$\wedge$风力=“无”，则适宜打球=“是”。

5、ID3算法的优点与缺点

1）主要优点
（1）模型理解容易：可方便地提取 “如果-则” 形式的分类规则。
（2）噪声影响较小：信息增益计算使用当前的所有训练样本，可以降低个别错误样本点带来的影响。
（3）分类速度较快，对未知类别标号的样本 $Z_u$，只需从树根开始搜索一条分裂属性值与 $Z_u$ 对应属性值相等的一条路径，即可对 $Z_u$ 分类。

2）主要缺点
（1）只能处理离散属性数据：ID3算法仅处理具有离散属性的数据集。
（2）不能处理有缺失的数据：ID3算法不能处理属性值有缺失的数据。
（3）仅是局部最优的决策树：ID3采用贪心算法，结果非全局最优。
（4）偏好取值种类多的属性：ID3采用信息增益作为选择分裂属性的度量标准，但大量的研究分析与实际应用发现，信息增益偏向于选择属性值个数较多的属性，而属性取值个数较多的属性并不一定是最优或分类能力最强的属性。

（三）决策树的剪枝

  一般地说，对于同一个训练样本集，其决策树越矮小就越容易理解，且存储与传输的代价也越小；反之，决策树越高大，可能导致决策树在测试集上的泛化误差增大。然而，决策树过于矮小也会导致泛化误差较大。因此，剪枝需要在决策树的大小与模型正确率之间寻求一个平衡点。

  ID3生成的决策树完全与训练样本拟合,而在有噪声情况下，完全拟合将导致过度拟合 (Overfitting)，即对训练数据的完全拟合反而使对现实其它数据的分类预测性能下降。剪枝就是一种克服噪声的基本技术，可防止决策树的过度拟合，同时还能使决策树得到简化而变得更容易理解。剪枝技术主要包括预剪枝 (Pre-Pruning) 和后剪枝 (Post-Pruning) 两种方法。

1、预剪枝

  预剪枝技术的基本思想是限制决策树的过度生长，主要通过在训练过程中明确地控制树的大小来简化决策树。

  常用的预剪枝方法主要有以下几种。

（1）为决策树的高度设置阈值，当决策树到达阈值高度时就停止树的生长。通常能够取得比较好的效果，高度阈值设置困难，需反复尝试。
（2）如果当前结点中的训练样本点具有完全相同的属性值，即使这些样本点有不同的类别标号，决策树也不再从该结点继续生长；
（3）设定结点中最少样本点数量的阈值，如果当前结点中的样本点数量达不到阈值，决策树就不再从该结点继续生长，但这种方法不适用于小规模训练样本集。
（4）设定结点扩展的信息增益阈值，如果计算的信息增益值不满足阈值要求，决策树就不再从该结点继续生长。如果在最好情况下扩展的信息增益都小于阈值，即使有些结点的样本不属于同一类，算法也可以终止。当然，选取恰当的阈值也是比较困难的，阈值过高可能导致决策树过于简化，而阈值过低又可能对树的化简不够充分。

2、后剪枝

  后剪枝技术是在生成决策树时允许其过度生长，当决策树完全生成后，再根据一定的规则或条件，剪去决策树中那些不具有一般代表性的叶结点或分支。

  后剪枝算法有 “自上而下” 和 “自下而上” 两种剪枝策略。自下而上的剪枝算法首先从最底层的内部结点开始，剪去满足一定条件的内部结点，并在生成的新决策树上递归调用这个算法，直到没有可以剪枝的结点为止。自上而下的算法是从根结点开始向下逐个考虑结点的剪枝问题，只要结点满足剪枝的条件就进行剪枝。

  后剪枝是边修剪边检验的过程，一般规则是：在决策树不断剪枝的过程中，利用训练样本集或检验样本集的样本点，检验决策子树的预测精度，并计算出相应的错误率。如果剪去某个叶结点后能使得决策树在测试集上的准确度或其它测度不降低，就剪去这个叶结点。当产生一组逐渐被剪枝的决策树之后，使用一个独立的测试集评估每棵树的准确率，就能得到具有最小期望错误率的决策树。

（四）C4.5算法

  C4.5算法不仅继承了ID3算法的优点，并增加了对连续型属性和属性值空缺情况的处理，对树剪枝也使用了当时更为成熟的方法。特别地，C4.5采用基于信息增益率 (information gain ratio) 作为选择分裂属性的度量标准。

1、信息增益率

定义9-8 设 $S$ 是有限个样本点的集合，条件属性 $A$ 划分 $S$ 所得子集为 { S 1 , S 2 , ⋯ , S v } \{S_1,S_2,\cdots,S_v\} {S1​,S2​,⋯,Sv​}，则定义 $A$ 划分样本集 $S$ 的信息增益率为 $$gainRatio(S,A)=gain(S,A|C)/E(S,A)\text{\hspace{1em}(9-8)}$$ 其中，$gain(S,A|C)$ 由公式 (9-7) 计算，$E(S,A)$ 由公式 (9-4) 给出。

2、连续型属性的处理

  基本思想是把连续值属性的值域分割为离散的区间集合。若 $A$ 是在连续区间取值的连续型属性，则按照以下方法将 $A$ 分为二元属性。

（1）将训练集中的样本在属性 $A$ 上的取值从小到大排序。假设训练样本集中属性 $A$ 有m个不同的取值，其按非递减方式排序结果为 $v_1,v_2,\cdots ,v_m$；
（2）按顺序将两个相邻的平均值 $v_j^a=\frac{(v_j+v_{j+1})}{2}，(j=1,2,\cdots ,m-1)$ 作为分割点，共获得 $m-1$ 个分割点，且每个分割点都将样本集划分为两个子集，分别对应 $A\le v_j^a$ 和 $A>v_j^a$ 的样本集。
（3）计算分割点 $v_j^a(j=1,2,\cdots ,k-1)$ 划分样本集 $S$ 的信息增益，选择具有最大信息益 $gain(A_{v^{\prime }})$ 的分割点 $v^{\prime }$，将样本集划分为 $A\le v^{\prime }$ 和 $A>v^{\prime }$ 的两个子集，并将 $gain(A_{v^{\prime }})$ 作为属性 $A$ 划分样本集的信息增益。

3、空值的处理

（1）从训练集中将有空值的样本删除，使训练集属性都没有空值；
（2）以某种方法填充缺失数据，其目的也是使训练集的任何属性都没有空值。
  ① 对于数值属性，可用该属性非空值的平均值或频率最高值去填充；
  ② 对于离散属性，可以用该属性出现频率最高的值去填充空值，还可将空值作为一种特殊取值对待等。