决策树

决策树

本文章中，总数据集是 \(D\)，属性集是 \(a\)，其中 \(a = \{a^1, a^2, \ldots, a^V \}\)，表示属性 \(a\) 有 \(V\) 种取值；\(D^v = \{D(\text{attribute}(a) = a^v)\}\) 则表示总数据集 \(D\) 中满足属性 \(a = a^v\) 的数目。

决策树是一种分类算法，本文将介绍三种决策树算法，包括三种决策树算法涉及到的多个概念，比如信息熵、信息增益、信息增益比等等。

信息熵

\[ p_k = \frac{\sum(sort = k)}{|D|} \quad (k = 1,2,\ldots,|\mathscr{Y}|) \]

用符号 \(\operatorname{Ent}\) 表示信息熵

\[ \text{Ent}(D) = -\sum_{k=1}^{|\mathscr{Y}|}p_k\log_2p_k \]

信息增益

用符号 \(\text{Gain}\) 表示信息增益

\[ \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v = 1}^{V} \frac{|D^v|}{|D|}\text{Ent}(D^v) \]

信息增益比

用符号 \(\text{Gain\_ratio}\) 表示信息增益比

\[ \text{Gain\_ratio}(D,a) = \frac{\text{Gain}(D,a)}{\text{IV}(a)} \]

其中，

\[ \text{IV}(a) = -\sum_{v = 1}^{V}\frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} \]

基尼指数

用符号 \(\text{Gini\_index}\) 表示基尼指数

\[ \begin{align*} \text{Gini}(D^v) &= \sum_{k = 1}^{|\mathscr{Y}|}\sum_{k' \neq k}p_k p_{k'} \\ \text{Gini}(D^v) &= 1 - \sum_{k = 1}^{|\mathscr{Y}|}p_k^{2} \\ \text{Gini\_index}(D,a) &= \sum_{v = 1}^{V} \frac{|D^v|}{|D|} \text{Gini}(D^v) \end{align*} \]

剪枝

损失函数

假设决策树 \(T\) 有 \(|T|\) 个叶节点，每个叶节点 \(t\) 有 \(N_t\) 个样本，其中类别 \(k = 1, 2, \ldots, K\) 的样本数为 \(N_{tk}\)。

损失函数

\[ C_\alpha(T) = \sum_{t=1}^{|T|}N_t \operatorname{Ent}(D_t) + \alpha |T| \]

其中 \(\operatorname{Ent}(D_t)\) 是叶节点 \(t\) 上样本集合 \(D_t\) 的信息熵，

\[ \operatorname{Ent}(D_t) = -\sum_{k=1}^{|\mathscr{Y}|} p_{tk} \log_2 p_{tk} \]

其中 \(p_{tk} = \frac{N_{tk}}{N_t}\)，\(N_{tk}\) 为叶节点 \(t\) 上第 \(k\) 类样本数，\(N_t\) 为叶节点 \(t\) 的样本总数。

所以可以将损失函数写成：

\[ \begin{align*} C(T) &= -\sum_{t=1}^{|T|} N_t \sum_{k=1}^{|\mathscr{Y}|} p_{tk} \log_2 p_{tk} \\\\ C_\alpha(T) &= C(T) + \alpha |T| \end{align*} \]

我们的目的就是最小化损失函数

\[ \min_{T} \quad C_\alpha(T) = \sum_{t=1}^{|T|}N_t \operatorname{Ent}(D_t) + \alpha |T| \]

算法步骤

我们可以定义一个DP[]数组，并使用动态规划的思想来找到最优剪枝

• 输入数据 \(X = \{(\vec{x}_1, y_1), (\vec{x}_2, y_2), \ldots, (\vec{x}_N, y_N) \}\)
• 输出 \(T_\alpha\)

1. 对于树T中的每个节点t，计算 \(H_t(T)\)
2. 从树的叶节点开始递归地向上回溯，比较 \(C_\alpha(T_A)\) 和 \(C_\alpha(T_B)\)
3. 返回步骤2

CART

回归树

回归树对应于输入空间的分割和分割单元内的输出值。

输入空间 \(M = R_1, R_2, \ldots, R_M\)，每个空间 \(R_m\) 有一个输出值 \(c_m\)，我们可以定义回归树模型如下：

回归树模型 \[ f(x) = \sum_{m=1}^{M} c_m I (x \in R_m) \]

均方误差 \[ \sum_{x_i \in R_m} (y_i - f(x_i))^2 \]

\[ \hat{c}_m = \text{ave}(y_i \mid x_i \in R_m) \]

分割算法

• 输入：训练数据 \(D\)
• 输出：回归树 \(f(x)\)

1. 选择 \(x_j\)，其输出为 \(s\)。空间 \(R_1(j, s) = \{x \mid x^{(j)} \leq s\}\)，空间 \(R_2(j, s) = \{x \mid x^{(j)} > s\}\)
2. \[\min_{j,s}\left[\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right]\]
3. \[\frac{1}{N_m} \sum_{x_i \in R_m(j,s)} y_i, \quad x_i \in R_m, \quad m = 1, 2\]
4. 重复步骤2和3，直至满足停止条件。

分类树

根据基尼指数进行分类即可

\[ \begin{aligned} \text{Gini}(D^v) &= \sum_{k = 1}^{|\mathscr{Y}|}\sum_{k' \neq k}p_k p_{k'} \\ \text{Gini}(D^v) &= 1 - \sum_{k = 1}^{|\mathscr{Y}|}p_k^{2} \\ \text{Gini\_index}(D,a) &= \sum_{v = 1}^{V} \frac{|D^v|}{|D|} \text{Gini}(D^v) \end{aligned} \]

\(\text{CART}\) 剪枝

\(\text{CART}\) 剪枝算法由两步组成：手下从省城算法产生的决策树 \(T_0\) 底端开始不断简直，直到 \(T_0\) 的根节点，形成一个子树序列 \(\{T_0, T_1, \cdots T_n\}\)；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

\(\text{CART}\) 剪枝算法

输入：\(\text{CART}\) 算法生成的决策树 \(T_0\)； 输出：最优决策树 \(T_{\alpha}\)。