决策树

决策树学习，假设给定训练数据集：

D = {(x₁, y₁), (x₂, y₂), ⋯, (x_N, y_N)}

其中 x_i = (x_i⁽¹⁾, x_i⁽²⁾, ⋯, x_i⁽ⁿ⁾)^T 为输入实例， n 为特征个数，y ∈ {1, 2, ⋯, K}为类标记， N 为样本容量。学习目标是根据训练数据构建一个决策树模型，使它能够对实例正确分类。

1.熵

信息是个很抽象的概念，接下来我们从文件压缩问题来说明信息熵，以便于理解。

压缩原理

压缩的本质就是将重复出现的字符用更短的符号代替，就是找出文件内容的概率分布，将出现概率高的部分替代成更短的形式。因此，内容越是重复的文件就可以压缩的越小。比如，“ABABABABABABAB”可以压缩为”7AB”。而内容毫无重复，就很难进行压缩，例如无理数 π 就很难压缩。

压缩极限

压缩可以分解成两个步骤。第一步是得到文件内容的概率分布；第二步是对文件进行编码，用较短的符号替代那些重复出现的部分。

比如扔硬币的结果，那么只要一个二进制位就够了，1表示正面，0表示表示负面。足球赛的结果，最少需要两个二进制位。扔骰子的结果，最少需要三个二进制位。

在均匀分布的情况下，假定一个字符（或字符串）在文件中出现的概率是 p ，那么该文件种最多可能出现 种字符（字符串）。则需要 个二进制位才能表示 种情况。也就是每种字符（或字符串）需要占用 个二进制位。那么全部压缩该文件总共需要 个二进制位。

更一般情况，假定文件有n个部分组成，并且每个部分的内容在文件中的出现概率分别为 p₁, p₂, ⋯p_n 。可推出如下公式：

上述公式即为压缩极限，表示压缩所需要的二进制位数。

信息熵

在均匀分布的情况下 ，压缩每个字符（字符串）平均需要 个二进制位。对于一般情况下 p_i 不等，压缩每个字符（字符串）平均需要 个二进制位。 即为信息熵公式。

熵（entropy）是表示随机变量不确定性的度量。设 X 是一个取有限个值的离散随机变量，其概率分布为：

P(X = x_i) = p_i, i = 1, 2, ⋯, n

则随机变量 X 的熵定义为：

熵只依赖于 X 的分布，而与 X 的取值无关，因此可以将 X 的熵记做 H(P) ,熵越大随机变量的不确定性就越大，且 0 ≤ H(p) ≤ log n .

设随机变量 (X, Y) ,其联合概率分布为：

P(X, Y) = P(X = x_i, Y = y_i) = p_ij, i = 1, 2, ⋯, n; j = 1, 2, ⋯, m

条件熵 H(Y | X) 表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望：

例

假定有两个文件都包含1024个符号，在ASCII码的情况下，它们的长度是相等的，都是1KB。甲文件的内容50%是a，30%b，20%是c，则平均每个符号要占用1.49个二进制位。

乙文件的内容10%是a，10%是b, ⋯ ,10%是j，则平均每个符号要占用3.32个二进制位。

可以看到文件内容越是分散（随机），所需要的二进制位就越长。所以，这个值可以用来衡量文件内容的随机性（又称不确定性）。这就叫做信息熵（information entropy）。

注:

（1）信息熵只反映内容的随机性，与内容本身无关。

（2）信息熵越大，表示占用的二进制位越长，因此就可以表达更多的符号(信息量并不一定大也许是一堆无序没意义的字符)。

（3）信息熵与热力学的熵，基本无关。

经验熵和经验条件熵

由数据估计(极大似然估计)得到的熵和条件熵。

如数据集 D , 由 K 个类别。经验熵是

特征 A 根据取值把数据集 D 划分为 n 个子集，则给定特征 A 时数据集 D 的经验条件熵是：

2.信息增益

特征 A 对训练数据集 D 的信息增益 g(D, A) ，定义为集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验熵 H(D | A) 之差，即：

g(D, A) = H(D) − H(D|A)

H(D) 表示对数据集 D 进行分类的不确定性， H(D | A) 表示按特征 A 分类过后的所有熵的总和；二者的差表示分类前后不确定性减少的程度，因此信息增益大的特征有更强的分类能力。

设数据集为 D ,| D |表示样本个数，设有 K 个类 C_k ,| C_k |为属于 C_k 的样本个数， | C_k | = | D |。设特征 A 有 n 个不同取值 {a₁, a₂, ⋯, a_n} ，根据 A 的取值将 D 划分为 n 个子集 D₁, D₂, ⋯, D_n ,| D_i |为 D_i 的样本个数， | D_i | = | D |,记子集 D_i 中属于类 C_k 的样本的集合为 D_ik ,即 D_ik = D_i⋂C_k, | D_ik |为 D_ik 的样本个数，则

信息增益的问题

对于取值很多的特征，比如连续型数据(时间)。每一个取值几乎都可以确定一个样本。即这个特征就可以划分所有的样本数据。

• 信息增益不适合连续型、取值多的特征
• 使得所有分支下的样本集合都是纯的，极端情况每一个叶子节点都是一个样本
• 数据更纯，信息增益更大，选择它作为根节点，结果就是庞大且深度很浅的树

3.信息增益比

特征 A 对训练数据集 D 的信息增益比：

其中 H_A(D) 为数据集 D 关于特征 A 的值的熵, n 是特征 A 取值的个数。

解决信息增益的问题：特征 A 分的类别越多， D 关于 A 的熵就越大，作为分母，所以信息增益 g_R(D, A) 就越小。在信息增益的基础上增加了一个分母惩罚项。

信息增益比的问题：实际上偏好可取类别数目较少的特征。

4. ID3 算法

决策树的生成， ID3 算法以信息增益最大为标准选择特征。递归构建，不断选择最优特征对训练集进行划分。

递归终止条件：

• 当前节点的所有样本，属于同一类别 C_k ，无需划分。该节点为叶子节点，类标记为 C_k
• 当前属性集为空，或所有样本在属性集上取值相同
• 当前节点的样本集合为空，没有样本

在集合 D 中，选择信息增益最大的特征 A_g :

• 增益小于阈值，则不继续向下分裂，到达叶子节点。该节点的标记为该节点所有样本中的 majority class C_k 。 这也是预剪枝
• 增益大于阈值，按照特征 A_g 的每一个取值 A_g = a_i 把D划分为各个子集 D_i ，去掉特征 A_g

继续对每个内部节点进行递归划分。

C4.5 算法

C4.5 是 ID3 的改进， C4.5 以信息增益率最大为标准选择特征。

5.决策树剪枝

决策树递归生成算法，易出现过拟合现象，这是由于在学习时过多的考虑如何提高对训练数据的正确分类，从而导致构建的决策树过于复杂，我们可以通过对决策树进行剪枝来简化决策树。

决策树剪枝通过极小化损失函数来实现。假设树 T 的叶节点个数为| T |, t 是树| T |的叶节点，该叶节点有 N_t 个样本点，其中 k 类的样本点有 N_tk 个， H_t(T) 位叶节点 t 上的经验熵， α ≥ 0 为参数，则决策树的损失函数可定义为：

其中经验熵为：

令

则 C_α(T) = C(T) + α | T | ，其中 C(T) 表示模型对训练数据的预测误差，即模型与数据的拟合程度，| T |表示模型的复杂程度，较大的 α 促使选择简单的模型，较小的 α 促使选择较复杂的模型。

剪枝就是当 α 确定时，选择损失函数最小的模型，假设一组叶节点回缩到其父节点之前与之后的整体树分别为 T_B 和 T_A ，其对应的损失函数数值分别为 C_α(T_B) 和 C_α(T_A) ,如果 C_α(T_B) ≥ C_α(T_A) ，则进行剪枝，即将父节点变为新的叶节点。

6.CART算法

6.1.回归生成树

首先，选择切分变量 j 与切分点 s ，将每个区域切分成两个子区域

R₁(j, s) = {x|x^(j) ≤ s}, R₂(j, s) = {x|x^(j) > s}

然后选择最优切分变量 j 和切分点 s ，具体地，求解：

min_j, s[min_c1∑_{xi ∈ R1(j, s)}(y_i − c₁)² + min_c2∑_{xi ∈ R2(j, s)}(y_i − c₂)²]

然后用选定的对 (j, s) 划分区域并决定相应的输出值：

递归对子区域做上述操作，直到满足停止条件。将输入空间划分为 M 个区域 R₁, R₂, ⋯, R_M ，生成决策树：

其中 I() 是指示函数。

6.2.分类树生成

尼基指数

分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 p_k ,则概率分布的尼基指数定义为:

对于给定样本集合 D ，其尼基指数为：

这里 C_k 是 D 中属于第 k 类的样本子集， K 是类的个数。

如果样本集合 D 根据特征 A 是否取某一可能值 a 被分割成 D₁ 和 D₂ 两部分，即 ，则在特征 A 的条件下，集合 D 的尼基指数定义为：

Gini(D) 表示集合 D 的不确定性， Gini(D, A) 表示经过 A = a 分割后集合 D 的不确定性。尼基指数越大，样本集合的不确定性越大同熵。

决策树生成：

1.计算现有特征对数据集的尼基指数，对每一个特征 A ，对其可能取得每个值 a ,根据是否 A = a 将 D 切割成 D₁, D₂ ,并计算 A = a 时的尼基指数。

2.在所有可能的特征 A 以及它们所有可能的切分点 a 中，选择尼基指数最小的特征及其对应的切分点最为最优特征与最优切分点。一最优特征和最优切分点，从现有节点生成两个子节点，将训练数据集以特征分配到两个子节点中。

对子节点递归做1,2操作直至满足停止条件，生成CART决策树。

6.3. CART 剪枝

CART剪枝算法从“完全生长”的决策树的底端剪掉一些子树，使决策树变小，从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成；首先从生成算法产生的决策树 T₀ 底端开始不断剪枝，直到 T₀ 的根节点，形成一个子树序列

{T₀, T₁, ⋯, T_n}

然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

1. 剪枝，形成一个子树序列

在剪枝过程中，计算子树的损失函数:

C_α(T) = C(T) + α|T|

其中， T 为任意子树， C(T) 为对训练数据的预测误差（如基尼指数）， | T | 为子树的叶结点个数， α ≥ 0 为参数， C_α(T) 为参数是 α 时的子树 T 的整体损失，参数 α 权衡训练数据的拟合程度和模型的复杂度。

对固定的 α ,一定存在使损失函数 C_α(T) 最小的子树，将其表示为 T_α 。 T_α 在损失函数 C_α(T) 最小的意义下是最优的。容易验证这样的最优子树是唯一的。当 α 大的时候，最优子树 T_α 偏小；当 α 小时，最优子树 T_α 偏大。极端情况，当 α = 0 时，整体树是最优的。当 α → ∞ 时，根节点组成的单节点树是最优的。

Breiman等人证明：可以用递归的方法对树进行剪枝。将 α 从小增大， 0 = α₀ < α₁ < ⋯ < α_n < +∞ ,产生一系列的区间 [α_i, α_i + 1), i = 0, 1.⋯, n ;剪枝得到的子树序列对应着区间 α ∈ [α_i, α_i + 1), i = 0, 1.⋯, n 的最优子树序列

{T₀, T₁, ⋯, T_n}

序列中的子树是嵌套的。

具体地，从整体树 T₀ 开始剪枝，对 T₀ 的任意内部结点 t ,以 t 为单节点树的损失函数是

C_α(t) = C(t) + α

以 t 为根节点的子树 T_t 的损失函数是

C_α(T_t) = C(T_t) + α|T_t|

当 α = 0 及 α 充分小时，有不等式

C_α(T_t) < C_α(t)

当 α 增大时，在某一 α 有

C_α(T_t) = C_α(t)

当 α 再增大时，有

C_α(T_t) > C_α(t)

只要

T 与 t 有相同的损失函数值，而 t 的节点更少 ,因此 t 比 T_t 更可取，对 T_t 进行剪枝。

为此，对 T₀ 中每一个内部节点 t ，计算

它表示剪枝候整体损失函数减少的程度，在 T₀ 中剪去 g(t) 最小的 T_t ，将得到的子树作为 T₁ ，同时将最小的 g(t) 设为 α_t . T₁ 为区间 [α₁, α₂) 的最优子树。

如此剪枝下去，直至得到根节点。在这一过程中，不断地增加 α 的值，产生新的区间。

2.在剪枝得到的子树序列 T₀, T₁, ⋯, T_n 中通过交叉验证选取最优子树 T_α

具体地，利用独立的验证数据集，测试子树序列 T₀, T₁, ⋯, T_n 中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每颗子树 T₁, T₂, ⋯, T_n 对应于一个参数 α₁, α₂, ⋯, α_n .所以当最优子树 T_k 确定时，对应的 α_k 也确定了，即得到最优决策树 T_α.

CART 剪枝算法

输入： CART 算法生成的决策树 T₀;

输出：最优决策树 T_α.

(1)设 k = 0, T + T₀, α = +∞.

(2)自下而上地对各内部节点 t 计算 C(T_t), | T_t | 以及

α = min (α, g(t))

这里， T_t 表示以 t 为根节点的子树， C(T_t) 是对训练数据的预测误差， | T_t | 是 T_t 的叶节点个数。

3. 自上而下地访问内部节点 t ,如果有 g(t) = α , 进行剪枝，并对叶节点 t 以多数表决法决定其类，得到树 T .

(4)设 k = k + 1, α_k = α, T_k = T .

(5)如果 T 不是由根节点单独构成的树，则回到步骤(3)

(6)采用交叉验证法在子树序列 T₀, T₁, ⋯, T_n 中选取最优子树 T_α .

7.集成化(Ensemble)

Bagging(bootstrap aggregating)

首先，从大小为 N 的数据集 D 中，分别独立进行多次随机抽取 n 个数据，并使用每次抽取的数据训练弱分类器 C_i 。

然后，对新的数据进行分类时，首先将新的数据放进每一个分类器 C_i 中进行分类，得到每一个分类器对新数据的分类结果，并进行投票后获得优胜的结果。

随机森林(Random forest)

首先，从原始数据集从大小为 N 的数据集 D 中，有放回的抽取 N 个数据，同一条数据可以重复被抽取，假设进行 k 次，然后根据 k 个数据集构建 k 个决策树。

其次，设有 n 个特征，在每一棵树的每个节点随机抽取 m 个特征，并计算特征蕴含的信息量，并选择一个最具分类能力的特征进行节点分裂。每棵树最大限度的生长，不做任何剪裁。

最后，将生成的多棵树组成随机森林，用随机森林进行分类，分类结果桉树分类器投票多少而定。

Boosting

假设训练集上一个有 n 个样例，并对每个样例赋上一个权重 W_i ,在训练起初每个点的权重相同；训练过程中提高在上次训练中分类错误的样例的权重，并降低分类正确样例的权重；在全部训练完成后得到 M 个模型，对 M 个模型的分类结果通过加权投票决定：

另外还有AdaBoost和GBDT等。

参考

1. 李航 《统计学习方法》
2. 周志华 《机器学习》
3. CART回归树