【机器学习】（9）:决策树

2015/4/23 9:59:06

决策树是一种实现分治策略的层次数据结构，它是一种有效的非参数学习方法，可以用于分类和回归。本节我们来简单介绍决策树的相关知识。

• 什么是决策树
• 单变量树
• 单变量分类树
• 剪枝
• 由决策树提取规则

一、什么是决策树

决策树（decision tree）是一种用于监督学习 的层次模型，通过这种特殊的层次模型，局部区域可以通过少数几步递归分裂确定。决策树由一些内部决策节点和终端树叶组成。所谓决策节点，即运行某个判断/测试函数，来确定数据是否符合条件，从而进行选择分支地输出。树叶节点一般用来存放最终不可再分的数据集合，一个决策节点可以分支出一个树叶节点，也可以分支出一个新的决策节点，从而继续递归分裂。一个简单的决策树模型如下：

其中C1、C2、C3表示数据集，也可以说是我们的分类，而菱形流程表示测试\判断函数。每个测试函数的输入可以是一个d-维向量。如果我们考虑的是一个数值数据，那么分支一般是两分的，比如这里使用X1 > W10 对数据进行两分，一般最好的情况下每次都可以讲数据集二分，因此如果存在b个区域\类别，那么最好的情况可以通过对b求以2为底的对数次找到正确的区域，即LOG2(b)。

二、单变量树

对于一个决策树来说，如果输入测试节点的数据是单维的，即只有一个变量，那么称为单变量树。如果使用的输入维是离散的，取n个可能值之一，那么就对应一个n路划分；如果是一个连续值，则对应一个两分（binary split）。需要注意，每次测试节点进行的划分都是两两正交的，即每次划分都是独立、不存在重复关联。

树归纳是指构造给定训练样本的树，一般对于给定的训练集，我们可以找到多个使用的决策树，为了简单考虑，我们一般最感兴趣地是寻找其中最小的树，树的大小用树的节点和决策节点数来衡量。但是寻找最小数是NP完全问题，所以我们只能使用基于启发式的局部搜索过程，在合理的时间内得到合理的树。

树学习算法根本上是贪心算法，从包含全部训练数据的根节点开始，每一步都选择最佳划分。依赖于所选取的属性是离散还是连续的，每次都可以将训练数据划分成n个或两个子集，然后对相应子集进行递归决策、划分，直到不再需要划分，此时就创建一个树叶节点并标记。

三、单变量分类树

对于单变量分类树来说，划分的优劣判断标准是不纯性度量（impurity measure） ，我们说一个划分是纯的，是说如果对于所有分支，划分后选择相同分支的所有实例都属于相同的类。这里的意思说白了就是每个树叶节点应当表示一个单纯类的实例。

四、剪枝

一般如果到达一个节点的训练实例树小于训练集的某个比例，比如5%，无论是否不纯或是否有错误，该节点都不再进一步分裂。因为 基于过少实例的决策树会导致方差太大，从而导致泛化误差较大。这种在树完全构造出来之前提前停止树构造的方法称作树的先剪枝（prepruning）。

另一个得到较小树的方法是后剪枝（postpruning） ，实践中比先剪枝要好些。我们让树完全增站直到所有的树叶都是纯的并具有零训练误差。然后我们找出导致过分拟合的子树并剪掉它们。方法是我们最初从数据集中暴力一个剪枝集，训练阶段不使用。我们用一个被子树覆盖的训练实例标记的树叶节点替换该子树，如果该树叶在剪枝集上的性能不比该子树差，则剪掉该子树并保留树叶节点。

一般来说，先剪枝速度快，但是后剪枝更加准确。

五、由决策树提取规则

决策树可以提取特征，我们要做的是将每条路径描述出来就可以了。我们可以方便地将树的路径转换成IF-THEN规则。 比如对于下图的一个关于员工信息对应工作效率的实例：

这样我们可以描述每个分支，这里我们仅举个简单的例子：

R1: IF(age > 38.5) AND (years-in-job > 2.5) THEN y=0.8

可以看到，上面的IF-THEN规则描述了最左侧的分支情况。这样的规则库可以提取知识。容易理解，并且使得领域专家可以通过验证从数据学习得到的模型。

多变量树的情况可以由单变量树对输入维度扩展得到。自从凯撒将一个复杂的“高卢人问题”分解成一组较简单的问题以来，分治 一直作为一种启发式方法频繁使用。决策树更多地用在监督式学习的分类问题，并且通常在使用复杂算法以前，可以先试验决策树，并将它的准确率作为性能基准。

Refer： 《机器学习导论》，Ethen Alpaydin（土耳其），机械工业出版社