决策树¶

约 2599 个字预计阅读时间 9 分钟

下图是决策树的一个实例，决策树的内部节点是特征，而叶节点是类别

决策树实例

决策树等价于一系列的 if-then 规则，在决策树中，每个具体的例子都被且仅被一条路径覆盖。

决策树还等价于一种条件概率分布，不过这种条件概率分布被强化成了一个空间的划分。

决策树算法主要有以下三个过程：

特征选择
决策树生成
决策树剪枝

特征选择¶

信息增益法¶

首先我们先定义熵和条件熵

熵

给定一个随机变量 X：

\[ P(X = x_i) = P_i \]

那么该随机变量的熵为：

\[ H(X) = -\sum_{i=1}^{n}P_i\log P_i \quad\quad \in [0，\log n] \]

注意，在讨论熵是默认对数的底为 2，此时熵的单位为 bit.

对熵的理解

假设我们有一个随机为 0-7 的等概率的随机变量，从上式可以很容易计算出他的熵是 3bit，也就是说我们需要 3bit 的信息才能确定这个随机变量的取值。这跟直观上也是吻合的，因为我们需要至少 3bit 的编码来分别这八个信号（000-111）.

上式中的 log 的行为可以理解为，如果一个信号有 ⅛ 的概率出现，那么这个信号需要$-\log_2 1/8 = 3$bit 的编码来表示.如果一个信号有 ¼ 的概率出现，那么这个信号需要$-\log_2 1/4 = 2$bit 的编码来表示.最后我们对这个随机变量的熵的计算其实就是对这个编码长度求期望。

而熵的值越大，我们目前的信息就越少。

假如我们要预测的人的进攻方向，若敌人进攻方向这一随机变量的熵为 3bits，等效敌人从八个方向等可能进攻.但如果我们获取了某个信息后此随机变量的熵只剩下 1bit，等效敌人从两个方向等可能进攻，信息就充足的多了。

所以我们可以有一个直观的理解，某个信息来之后我的熵减少的越多，这个信息的信息量越大，越有用。

条件熵

给定一个联合分布：

\[ P(X = x_i，Y = y_j) = P_{ij} \]

那么条件熵

\[ H(Y|X) = -\sum_{i=1}^{n} P_i H(Y|X = x_i) = -\sum_{i=1}^{n} P_i \sum_{j=1}^{m} P_{j|i} \log P_{j|i} \]

从第一个等号可以看得出来条件熵其实也就是对于不同的 X 的取值求期望

于是我们就可以定义特征 A 对于数据 D 的信息增益：

\[ g(D，A) = H(D) - H(D|A) \]

这也被称为类与特征的互信息，它表示得知特征 A 的信息而使得类 Y 的信息的不确定性减少的程度。

信息增益比¶

信息增益存在一个问题，就是它偏向于可取值较多的特征，因为取值较多的特征的条件熵较小.如果我们希望算法同样考虑那些值比较少但是信息增益同样很不错的特征的话。

\[ g_R(D，A) = \frac{g(D，A)}{H_A(D)} \]

其中$H_A(D) = -\sum_{i=1}^{n} \frac{|D_i|}{|D|} \log \frac{|D_i|}{|D|}$是关于特征 A 对数据集 D 的经验熵，$|D_i|$是$D$中在特征 A 上取值为$a_i$的样本子集.A 的可取值越多，$H_A(D)$的值越大。

基尼指数¶

基尼指数是另一种特征选择的方法，它的定义如下：

基尼指数

\[\begin{aligned} &Gini(P) = 1 - \sum_{k=1}^{K} P_k^2 \\ &Gini(D) = 1 - \sum_{k=1}^{K} \frac{|D_i|}{|D|}^2 \\ &Gini(D，A) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} Gini(D_i) \end{aligned}\]

决策树生成¶

ID3 算法¶

ID3 算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归的构建决策树。

输入：训练集$D$，特征集$A$，阈值$\epsilon$
输出：决策树$T$
base case：若$D$中所有实例属于同一类$C_k$，则$T$为单节点树，并将类$C_k$作为该节点的类标记，返回$T$；
base case: 若$A = \emptyset$，则$T$为单节点树，并将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$.
base case: 若$\max g(D，A) < \epsilon$，则$T$为单节点树，并将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$.
否则，计算$A$中各个特征对$D$的信息增益，选择信息增益最大的特征$A_g$将数据集分类，然后对各个子类调用本算法，递归的构建决策树，返回$T$.

C4.5 算法¶

C4.5 算法根 ID3 算法完全一样，只是用的不是信息增益，而是信息增益比。

决策树剪枝¶

利用正则化函数¶

对整棵树，我们可以构造一个正则化损失函数： $$ C_{\alpha}(T) = \sum_{t \in T} N_t H_t(T) + \alpha |T| $$ 其中 T 为所有叶节点的集合，t 为某个叶节点，$N_t$为叶节点 t 的样本个数，$H_t(T)$为叶节点 t 的经验熵，$|T|$为叶节点的个数，$\alpha$为正则化参数。

具体来说，假设 t 叶节点的所有$N_t$个样本中，k 类的样本有$N_{tk}$个，那么$H_t(T) = -\sum_{k=1}^{K} \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$.

我们需要对这个损失函数进行最小化，容易看出，如果叶节点全部都是单一类，那么第一项的值为 0.这时候决策树的分类效果好，但是叶子节点容易过多，第二项很大.但如果第二项极端的优化，我们只有一个叶节点，那么树是小了，但是所有样本都在一个节点内，可以说是毫无分类效果.所以我们最小化这个损失函数就是要在二者之间找到一个平衡，树既不会过深，分类效果也有保障。

算法

计算所有节点经验熵
从叶节点往上，试图把某个两个叶节点回缩到公共父节点上，检验损失函数是否减小。
直到没有节点可试

实例¶

CART 回归树算法¶

假设我们有数据集$\{(x_i，y_i)\}$，其中$x \in \mathbb{R}^n$，$y_i \in \mathbb{R}$，现在给出一个新的数据点$x$，求出它的对应 y.

CART 回归树算法会把空间划分成 m 块$R_1，R_2...R_m$，每个单元上函数的输出值都是固定的：

\[ f(x) = \sum_{m=1}^{M} c_m I(x \in R_m) \]

因为我们的损失函数选用平方误差，容易证明，在每个区域上最佳的输出值就是该区域内所有样本的均值。

\[ c_m = \frac{1}{N_m} \sum_{x_i \in R_m} y_i \]

算法：

输入：训练集$D$，阈值$\epsilon$
输出：回归树$f(x)$
开始：遍历维度 j 以及该维度上变量划分点 S，将数据集在该维度上按照划分点划分成两部分$R_1(j，s)，R_2(j，s)$，计算对应的损失函数值$min_{s} \sum_{x_i \in R_1(j，s)} (y_i - c_1)^2 + \sum_{x_i \in R_2(j，s)} (y_i - c_2)^2$
找到最佳维度和最佳划分之后，把数据集划分为$R_1，R_2$，然后对$R_1，R_2$分别递归的调用本算法，直到满足停止条件（区域内部损失函数小于阈值）

CART 分类树算法¶

首先我们先用基尼指数生成决策树，然后对决策树进行剪枝.我们着重介绍这里使用的剪枝算法

我们先构造一个以$\alpha$为参数的损失函数：

\[ C_{\alpha}(T) = C(T)+ \alpha |T| \quad\quad \alpha \in [0，\infty) \]

其中$C(T)$为用该决策树对训练集进行预测的损失函数（用基尼指数）. 我们的目标是找到$\alpha$从 0 到正无穷的每一个区间内的剪枝后的最优树。

在此语境下，对某个节点进行剪枝就是在决策树中用一个单一节点代替以当前节点为根的子树，该单一节点含有子树中所有的样本。

我们先来看比较极端的$\alpha$，看他对决策树的影响，当$\alpha$为 0 时，我们的损失函数就是$C(T)$，此时我们的目标就是最小化$C(T)$，也就是说我们的目标是生成一个最优的决策树，就算我们分出了非常多的节点也无所谓.当$\alpha$为正无穷时，我们的损失函数就是$|T|$，此时我们的目标就是最小化$|T|$，也就是说我们的目标是生成一个节点最少的树，那么毫无疑问所有的样本都放在根节点内就是最优解.可以看出， $\alpha$越大，决策树会被剪的越干净。

在以上前提下，我们发现我们可以单独讨论一个节点是否要被剪枝（回忆一下什么叫做对一个节点进行剪枝），假设一个节点所代表的子树为$T_t$，把子树内的所有样本都收到节点内所构成的节点为 t，那么该节点从不剪枝转向剪枝的关键节点就是当下式成立时：

\[ C(t) + \alpha * 1 = C(T_t) + \alpha * |T_t| \]

第一项是我们在决策树中放置单一节点（也就是剪枝后的节点）带来的损失函数，第二项式我们在决策树中放置子树带来的损失函数.我们可以直接计算出这个临界的$\alpha_{t}$，那么如果$\alpha \in (0，\alpha_{t})$，我们就不剪枝，如果$\alpha \in [\alpha_{t}，\infty)$，我们就剪枝。

所以我们可以对决策树内的所有节点都计算临界$\alpha$，我们从$\alpha = 0$开始逐渐增大，每次达到临界点我们就剪枝，直到所有枝都被剪掉，直到整棵树只有一个节点。

在上述过程中我们就得到了一系列的不同$\alpha$区间下的决策树，我们可以用交叉验证的方法来选择最优的$\alpha$.