决策树
约 4367 个字 预计阅读时间 29 分钟
决策树理论
决策树的基本组成部分：决策结点、分支和叶子
决策树中最上面的结点称为根结点，是整个决策树的开始。每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或者决策。通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果。
决策树的学习通常包括3个步骤
- 特征选择
- 决策树的生成
- 决策树的剪枝（以防生成的树太过复杂。不同的根结构会影响树的复杂度）
决策树还表示给定特征条件下类的条件概率分布，这一条件概率分布定义在特征空间的一个划分 (partition) 上, 将特征空间划分为互不相交的单元 (cell) 或区域 (region) , 并在每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分种的一个单元，决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。各叶结点的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。
优点：
- 推理过程容易理解
- 推理过程完全依赖于属性变量的取值特点
- 可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性、减少变量的数目提供参考。
CLS 算法是一个比较简单的决策树生成算法，其过程如下：
CLS 算法
从一棵空决策树开始，选择某一属性（分类属性）作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集：
- 如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点；
- 否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类
CLS 算法的一个缺点是不同测试属性及其先后顺序会产生不同的决策树，影响学习效果。而有些测试属性并不具有分类能力，因此需要对测试属性进行特征选择。
特征选择
常用的特征选择的准则是信息增益或信息增益比。
在介绍这两种准则之前，先引入信息量和熵的概念。
信息量是对于信息内容的度量，依赖于概率分布 \(p(x)\) ，其函数表达式 \(h(x)\) 满足：它是概率的单调递增函数，表达了信息的内容。 \(h(\cdot)\) 的形式可以这样寻找：如果我们有两个不相关的事件和，那么我们观察到两个事件同时发⽣时获得的信息应该等于观察到事件各⾃发⽣时获得的信息之和，即 \(h(x,y)=h(x)+h(y)\) 。两个不相关事件是统计独⽴的，因此 \(p(x,y)=p(x)p(y)\) 。根据这两个关系，很容易看出⼀定与对数有关。因此有：
其中，符号确保了信息一定是正数或者是零。注意，低概率事件 \(x\) 对应于高的信息量。
假设一个发送者想传输一个随机变量的值给接收者，在这个过程中，他们传输的平均信息量可以通过公式关于概率分布 \(p(x)\) 的期望得到，期望值为
这个被称为随机变量 \(x\) 的熵。
熵满足如下不等式：
证明第二个不等式，对于 \(f(x) = - p(x) \log_2 p(x)\)，其在 \([0,1]\) 上是一个凹函数，利用琴生不等式
（Jensen不等式给出的是凸函数的关系，上式是适用于凹函数的Jensen不等式，对于凸函数，只需将不等号换个方向即可）
可得
得证
设有随机变量 \((X,Y)\) ，其联合概率分布为：
定义条件熵 \(H(Y|X)\) ：表示在已知随机变量 \(X\) 的条件下随机变量 \(Y\) 的不确定性，定义为 \(X\) 给定条件下 \(Y\) 的条件概率分布的熵对 \(X\) 的数学期望：
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)
信息增益
特征 \(A\) 对训练数据集 \(D\) 的信息增益 \(g(D,A)\)，定义为集合 \(D\) 的经验熵 \(H(D)\) 与特征 \(A\) 给定条件下 \(D\) 的经验条件熵 \(H(D|A)\) 之差，即
\(H(D)\) 表示对数据集 \(D\) 进行分类的不确定性，信息增益表示得知特征 \(A\) 的信息而使得对数据集类 \(D\) 的信息的不确定性减少的程度
显然，对于数据集 \(D\) 而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。
一般地，熵 \(H(Y)\) 与条件熵 \(H(Y|X)\) 之差称为互信息（mutual Information）。决策树中的信息增益等价于训练条件数据集中类与特征的互信息。
对训练数据集（子集）\(D\) ，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征问题，可以使用信息增益比校正
信息增益比
特征 \(A\) 对训练数据集 \(D\) 的信息增益比 \(g_R(D,A)\) 定义为其信息增益 \(g(D,A)\) 与训练数据集 \(D\) 关于特征 \(A\) 的值的熵 \(H_A(D)\) 之比，即
其中 \(H_A(D) = -\sum^{n}_{i=1} \frac{\lvert D_{i} \rvert }{\lvert D \rvert }\log_{2} \frac{\lvert D_{i} \rvert }{\lvert D \rvert }\)
ID3 和 C4.5 算法
现在给出信息增益的算法
信息增益的算法
输入：训练数据集 \(D\) 和特征 \(A\)
输出：特征 \(A\) 对训练数据集 \(D\) 的信息增益 \(g(D,A)\)
(1)计算数据集 \(D\) 的经验熵 \(H(D)\)
(2)计算特征 \(A\) 对数据集 \(D\) 的经验条件熵 \(H(D|A)\)
(3)计算信息增益
ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。
ID3 算法
输入:训练数据集 \(D\) ，特征集 \(A\) 阈值 \(\varepsilon\)；
输出:决策树 \(T\) 。
- 若 \(D\) 中所有实例属于同一类 \(C_k\) ， 则 \(T\) 为单结点树，并将类 \(C_k\) 作为该结点的类标记，返回 \(T\) ;
- 若 \(A= \emptyset\)，则 \(T\) 为单结点树，并将 \(D\) 中实例数最大的类 \(C_k\) 作为该结点的类标记，返回 \(T\) ；
- 否则，按算法5.1计算 \(A\) 中各特征对 \(D\) 的信息增益，选择信息增益最大的特征 \(A_g\)；
- 如果 \(A_g\) 的信息增益小于阈值 \(\varepsilon\) ，则置 \(T\) 为单结点树，并将 \(D\) 中实例数最大的类 \(C_k\) 作为该结点的类标记，返回 \(T\) ；
- 否则，对 \(A_g\) 的每一可能值 \(a_i\)，依 \(A_g=a_i\) 将 \(D\) 分割为若干非空子集 \(D_i\) ，将 \(D_i\) 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 \(T\) ，返回 \(T\) ；
- 对第 \(i\) 个子结点，以 \(D_i\) 为训练集，以 \(A-{Ag}\) 为特征集，递归地调用步(1)~步(5)，得到子树 \(T_i\) ，返回 \(T_i\) 。
C4.5 算法在生成过程中，用信息增益比来选择特征
C4.5 算法
输入:训练数据集 \(D\) ，特征集 \(A\) 阈值 \(\varepsilon\)；
输出:决策树 \(T\) 。
- 若 \(D\) 中所有实例属于同一类 \(C_k\) ， 则 \(T\) 为单结点树，并将类 \(C_k\) 作为该结点的类标记，返回 \(T\) ;
- 若 \(A= \emptyset\)，则 \(T\) 为单结点树，并将 \(D\) 中实例数最大的类 \(C_k\) 作为该结点的类标记，返回 \(T\) ；
- 否则，计算 \(A\) 中各特征对 \(D\) 的信息增益比，选择信息增益比最大的特征 \(A_g\)；
- 如果 \(A_g\) 的信息增益比小于阈值 \(\varepsilon\) ，则置 \(T\) 为单结点树，并将 \(D\) 中实例数最大的类 \(C_k\) 作为该结点的类标记，返回 \(T\) ；
- 否则，对 \(A_g\) 的每一可能值 \(a_i\)，依 \(A_g=a_i\) 将 \(D\) 分割为若干非空子集 \(D_i\) ，将 \(D_i\) 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 \(T\) ，返回 \(T\) ；
- 对第 \(i\) 个子结点，以 \(D_2\) 为训练集，以 \(A-{Ag}\) 为特征集，递归地调用步(1)~步(5)，得到子树 \(T_i\) ，返回 \(T_i\) 。
CART 算法
理想的决策树有三种：
- 叶子结点数少
- 叶子结点深度小
- 叶子结点数少且叶子结点深度小
要找到这种最优的决策树是 NP 难题，因此，决策树优化的目的就是要找到尽可能趋向于最优的决策树。
一般将分类模型的误差分为：
- 训练误差(Training Error)：模型在训练记录上误分类样本比例；
- 泛化误差(Generalization Error)：模型在未知记录上的期望误差
一个好的分类模型必须具有低的训练误差和泛化误差。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning）。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function) 来实现。设树 \(T\) 的叶结点个数为 \(\lvert T \rvert\)，\(t\) 是树 \(T\) 的叶结点，该叶结点上有 \(N_{t}\) 个样本点，其中 \(k\) 类的样本点有 \(N_{tk}\) 个，\(H_{t}(T)\) 为叶结点 \(t\) 上的经验熵，\(\alpha\) 为参数，则决策树学习的损失函数定义为：
其中
\(C(T)\) 表示模型对训练数据的预测程度，\(\lvert T \rvert\) 表示模型复杂度，参数 \(\alpha\geq 0\) 控制两者之间的影响，较大的 \(\alpha\) 促使选择较简单的模型，较小的 \(\alpha\) 促使选择较复杂的模型， \(\alpha =0\) 意味着只考虑模型与训练数据的拟合程度，不考虑复杂度
CART
CART 是在给定输入随机变量 \(X\) 条件下输出随机变量 \(Y\) 的条件概率分布的学习方法。CART 假设决策树是二叉树，内部结点特征的取值为 “是” 或 “否” ，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART 算法由以下两步组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优的子树，这时用损失函数最小作为剪枝的标准
在CART算法并不是使用信息增益或信息增益比来划分特征，而是使用基尼指数选择最优特征，同时决定该特征的最优二值切分点。定义基尼指数：
基尼指数
分类问题中，假设有 \(K\) 个类，样本点属于第 \(k\) 类的概率为 \(p_k\) ，则概率分布的基尼指数定义为
对于给定样本集合 \(D\) 其基尼指数为
基尼指数 \(\mathrm{Gini}(D)\) 表示集合 \(D\) 的不确定性，基尼指数值越大，样本集合的不确定性也就越大。CART 算法为：
CART 生成算法
输入：训练数据集 \(D\)，停止计算的条件；
输出：CART 决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
-
设结点的训练数据集为 \(D\)，计算现有特征对该数据集的基尼指数。此时，对每一个特征 \(A\)，对其可能取的每个值 \(a\)，根据样本点对 \(A=a\) 的测试为“是”或“否”将 \(D\) 分割成 \(D1\) 和 \(D2\) 两部分，计算 \(A=a\) 时的基尼指数。
-
在所有可能的特征 \(A\) 以及它们所有可能的切分点 \(a\) 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
-
对两个子结点递归地调用（1），（2），直至满足停止条件。
-
生成 CART 决策树。
CART 的剪枝：
- 从生成算法产生的决策树 \(T_{0}\) 底端开始不断剪枝，直到 \(T_{0}\) 的根结点，形成子树序列 \(\left\{ T_{0},T_{1},\dots,T_{n} \right\}\)
- 通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树
在剪枝过程中，计算子树的损失函数：
对固定的 \(α\)，一定存在使损失函数 \(C_{\alpha}(T)\) 最小的子树，将其表示为 \(T_\alpha\)。\(T_{\alpha}\) 在损失函数 \(C_{\alpha}(T)\) 最小的意义下是最优的。容易验证这样的最优子树是唯一的。当 \(\alpha\) 大的时候，最优子树 \(T_{\alpha}\) 偏小；当 \(\alpha\) 小的时候，最优子树 \(T_{\alpha}\) 偏大。极端情况，当 \(\alpha=0\) 时，整体树是最优的。当 \(\alpha\to \infty\) 时，根结点组成的单结点树是最优的
Breiman等人证明：可以用递归的方法对树进行剪枝。将 \(\alpha\) 从小增大，\(0=\alpha_{0}<\alpha_{1}<\dots<\alpha_{n}<+\infty\) 产生一系列的区间 \([\alpha_{i},\alpha_{i+1})\) ,剪枝得到的子树序列对应着区间 \(\alpha\in [\alpha_{i},\alpha_{i+1})\) 的最优子树序列 \(\left\{ T_{0},T_{1},\dots,T_{n} \right\}\) ，序列中的子树时嵌套的
对 \(T_{0}\) 的任意内部结点 \(t\) ，以 \(t\) 为单结点树的损失函数是
以 \(t\) 为根结点的子树 \(T_{t}\) 的损失函数是
当 \(\alpha =0\) 及 \(\alpha\) 充分小时，有不等式
当 \(\alpha\) 增大时，在某一 \(\alpha\) 有
当 \(\alpha\) 增大时，不等式反向，取 \(\alpha = \frac{C(t)-C(T_{t})}{\lvert T_{t} \rvert-1}\) \(T_{t}\) 与 \(t\) 有相同的损失函数值，而 \(t\) 的结点少，因此 \(t\) 比 \(T_{t}\) 更可取，对 \(T_{t}\) 进行剪枝，为此，对 \(T_{0}\) 中每一内部结点 \(t\) ，计算
它表示剪枝后整体损失函数的减少程度，在 \(T_{0}\) 中减去 \(g(t)\) 最小的 \(T_{t}\) ，将得到的子树作为 \(T_{1}\) ，同时将最小的 \(g(t)\) 设为 \(\alpha_{1}\) 。\(T_{1}\) 为区间 \([\alpha_{1},\alpha_{2})\) 的最优子树
如此剪枝下去直到得到根结点，在这一过程中不断增加 \(\alpha\) 值，产生新的区间。
我们利用独立的验证数据集，测试子树序列 \(T_{0},T_{1},\dots,T_{n}\) 中各棵子树的平方误差或基尼指数，平方误差或基尼指数最下的决策树被认为是最优的决策树，在子树序列中，每棵子树 \(T_{1},T_{2},\dots,T_{n}\) 都对应于一个参数 \(\alpha_{1},\alpha_{2},\dots,\alpha_{n}\) 所以当最优子树 \(T_{k}\) 确定是，对应的 \(\alpha_{k}\) 也确定了，即得到了最优决策树 \(T_{\alpha}\)
回归树算法
假设 \(X\) 与 \(Y\) 分别作为输入和输出变量，且 \(Y\) 是连续变量，给定训练数据集
假设将输入空间划分为 \(M\) 个单元 \(R_{1},R_{2},\dots,R_{M}\) ，并且在每个单元 \(R_{m}\) 上有一个固定的输出值 \(c_{m}\) ，于是回归树模型可表示为：
当输入空间划分确定时，可以用平方误差 \(\underset{ x_{i}\in R_{m} }{ \overset{ }{ \sum } }(y_{i}-f(x_{i}))^{2}\) 表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值，单元 \(R_m\) 上的 \(c_{m}\) 的最优值 \(\hat{c}_{m}\) 时 \(R_{m}\) 上所有输入实例 \(x_{i}\) 对应的输出 \(y_{i}\) 的均值，即
采用启发式方法对输入空间进行划分，选择第 \(j\) 个变量 \(x^{(j)}\) 和它取的值 \(s\) 作为切分变量(splitting variable) 和切分点 (splitting point) ，并定义两个区域：
求解
对固定输入变量 \(j\) 可以找到最优切分点 \(s\) ，遍历所有输入变量，找到最优的切分变量 \(j\) ，构成一对 \((j,s)\) 。依次将输入空间划分为两个区域。接着对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树，这样的回归树通常称为最小二乘回归树
最小二乘回归树生成算法
输入：训练数据集 \(\mathcal{D}\)
输出：回归树 \(f(x)\)
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域，并决定每个子区域上输出值，构建二叉决策树：
(1)选择最优切分变量 \(j\) 和切分点 \(s\) ，求解
遍历变量 \(j\) ，对固定地切分变量 \(j\) 扫描切分点 \(s\) ，使上式输出最小值的对 \((j,s)\)
(2)用选定的对 \((j,s)\) 划分区域并决定相应的输出值：
(3)继续对两个子区域调用步骤1、2，直至满足停止条件
(4)将输入空间划分为 \(M\) 个区域 \(R_{1},R_{2},\dots,R_{M}\) ，生成决策树：