机器学习算法-决策树（一）

什么是决策树？类似于流程图的树结构；每个内部节点表示在一个属性上的测试；每个分枝代表一个测试输出；每个树叶节点存放一个类编号。

如何使用决策树分类？给定一个类标号未知的元组X，在决策树上测试元组的属性值，跟踪一条由根到叶节点的路径，叶节点存放该元组的类预测。决策树容易转换为分类规则。

一、决策树生成过程

决策树的生成由两个阶段组成：
1.决策树构建
使用属性选择度量来选择将元组最好的划分为不同的类的属性
递归的通过选定的属性，来划分样本
2.树剪枝
决策树建立时，许多分枝反映的是训练数据中的噪声和离群点，树剪枝试图识别并剪去这种分枝，以提高对未知数据分类的准确性

二、决策树生成算法

输入

• 数据划分D是训练元组和对应类标号的集合
• attribute_list,候选属性的集合
• Attribute_selection_method，指定选择属性的启发性过程

算法步骤

1. 树以代表训练样本的单个节点（N）开始
2. 如果样本都在同一个类，则该节点成为树叶，并用该类标记
3. 否则，算法调用Attribute_selection_method，选择能够最好的将样本分类的属性；确定“分裂准则”，指出“分裂点”或“分裂子集”。
4. 对测试属性每个已知的值，创建一个分支，并以此划分元组；
5. 算法使用同样的过程，递归的形成每个划分上的元组决策树。一旦一个属性出现在一个节点上，就不在该节点的任何子节点上出现；
6. 递归划分步骤停止的条件
   划分D（在N节点提供）的所有元组属于同一类
   没有剩余属性可以用来进一步划分元组——使用多数表决没有剩余的样本
   给定分支没有元组，则以D中多数类创建一个树叶

三、属性选择度量

1. 属性选择度量是一种选择分裂准则，将给定类标号的训练元组最好的进行划分的方法。

   • 理想情况，每个划分都是“纯”的，即落在给定划分内的元组都属于相同的类。
   • 属性选择度量又称为分裂准则

2. 常用的属性选择度量

   • 信息增益–ID3
   • 增益率–C4.5
   • Gini指标–CART

四、为什么需要属性选择度量

决策树学习的本质是从训练集中归纳出一组分类规则。与训练数据集不相矛盾的决策树可能有多个，也可能一个都没有。如针对如下数据集，采用不同的测试属性及其先后顺序将会生成不同的决策树。

学生	鸡肉	猪肉	牛肉	羊肉	鱼肉	鸡蛋	青菜	番茄	牛奶	健康情况
1	0	1	1	0	1	0	1	0	1	不缺钙
2	0	0	0	0	1	1	1	1	1	不缺钙
3	1	1	1	1	1	0	1	0	0	缺钙
4	1	1	0	0	1	1	0	0	1	不缺钙
5	1	0	0	1	1	1	0	0	0	缺钙
6	1	1	1	0	0	1	0	1	0	缺钙
7	0	1	0	0	0	1	1	1	1	不缺钙
8	0	1	0	0	0	1	1	1	1	缺钙
9	0	1	0	0	0	1	1	1	1	不缺钙
10	1	0	1	1	1	1	0	1	1	不缺钙

显然生成的两种决策树的复杂性和分类意义相差很大，由此可见选择测试属性是决策树学习算法中需要研究的重要课题。

五、由决策树提取分类规则

可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示：对从根到树叶的每条路径创建一个规则；沿着给定路径上的每个属性-值对形成规则前件（”IF”部分）的一个合取项；叶节点包含类预测，形成规则后件（”THEN”部分）；IF-THEN规则易于理解，尤其树很大时。
示例：
IF age = “youth” AND student = “no” THEN buys_computer = “no”
IF age = “youth” AND student = “yes” THEN buys_computer = “yes”
IF age = “middle_aged” THEN buys_computer = “yes”
IF age = “senior” AND credit_rating = “excellent” THEN buys_computer = “yes”
IF age = “senior” AND credit_rating = “fair” THEN buys_computer = “no”

六、决策树的优缺点

1. 相对于其他数据挖掘算法，决策树在以下几个方面拥有优势：
   
   • 使用白盒模型，理解和解释起来比较简单，并且易于实现。
   • 对缺失值不敏感，并且可以处理非常规型属性，前期对数据的准备往往是简单或者是不必要的 。其他的很多分类算法往往要求先把数据一般化，比如数值化、去掉多余的或者空白的属性值。
   • 在相对短的时间内能够对大型数据源做出可行且效果良好的结果，并支持多分类问题。
   • 分类效率高，泛化能力强。决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
2. 决策树也存在种种缺点：
   
   • 虽然可以创建复杂的树，但是容易过拟合–对训练数据有很好的分类能力、对未知的测试数据却未必有很好的分类能力，需要对已生成的树进行自下而上的剪枝，提升其泛化能力。
   • 对训练数据较敏感，数据中一个很小的变化可能导致生成一个完全不同的树，不过此问题可以通过使用集成决策树来解决。
   • 决策树学习的策略是以损失函数为目标函数的最小化，当损失函数确定后，学习问题就变成在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选择最优的决策树是NP完全问题，所以现实中通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优的。

七、决策树剪枝

产生的决策树会出现过分适应数据的问题：由于数据中的噪声和孤立点，许多分枝反应的是训练数据中的异常，导致生成的决策树后续对新样本的判定很不精确。
防止过分适应的两种方法：

• 先剪枝：通过提前停止树的构造—如果在一个节点划分样本将导致低于预定义临界值的分裂（e.g. 使用信息增益度量），可惜选择一个合适的临界值往往很困难。

• 后剪枝：由“完全生长”的树剪去分枝—对于树中的每个非树叶节点，计算该节点上的子树被剪枝可能出现的期望错误率，小于一定阈值则将此分支完全剪掉。在剪枝过程中经常使用一个独立的测试集来评估每颗树的准确率，就能得到具有最小期望错误率的决策树。

因为前剪枝方法比较复杂，所以常采用的都是后剪枝。后剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。
假设树T的叶节点个数为 |T| ， t 是树T的叶节点，该叶节点有 Nt 个样本点，其中属于 k 类的样本点有 Ntk 个， k=1,2,...,K ， Ht(T) 为叶节点 t 上的经验熵，定义为：
Ht(T)=∑kNtkNtlogNtkNt.
则决策树学习的损失函数可以定义为：
Cα(T)=∑t=1|T|NtHt(T)+α|T|.

上式第一项表示决策树模型对数据的预测误差，即模型与训练数据的拟合程度；第二项中的 |T| 表示模型的复杂度。参数 α≥0 控制两项之间的影响：较大的 α 促使选择较简单的决策树，较小的 α 促使选择较复杂的决策树。 α=0 意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

可以看出，决策树在生成时只考虑了通过提高信息增益或信息增益比对训练数据进行更好的拟合。而剪枝通过在损失函数与模型复杂度之间进行博弈，取得一个很好地平衡，保证整体模型（数据拟合能力+模型复杂度）的最优化。

下面详细介绍决策树的剪枝算法：

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

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

参考资料

1. https://item.jd.com/10975302.html 《统计学习方法》 李航