决策树中的算法实现
本文主要描述以下概念及算法
- 信息增益的计算方法
- 信息增益比的计算方法
- ID3 算法的实现
- C4.5 算法的实现
- 决策树的剪枝算法
- 基尼指数的计算方法
- 最小二乘回归树生成算法
- CART 生成算法
- CART 剪枝算法
信息增益算法($Information\ Gain$)
输入
- 训练数据集$D$
- 特征$A$
输出
特征$A$对训练数据集$D$的信息增益$g(D,A)$
具体实现
- 计算数据及$D$的经验熵
$$
H(D) = -\sum_{k=1}^K \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}\tag{1}
$$
公式说明：
$|D|$中竖线的意思为数据集中的个数，可以用公式表示：
$$
|D| = \sum_k I (c_k \in D) \tag{1.1}
$$
- 按照常规的熵的定义，$H(D) = - \sum_k p_k \log_2p_k$，是使用概率定义的，这里我们进行计算的时候，使用$\frac{|C_k|}{|D|}$来代表概率，即使用经验中简单的统计占比来表示。
- 计算特征$A$对数据集$D$的经验条件熵$H(D|A)$：
$$
H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) = - \sum_{i=1}^n \frac{|D_i|}{|D|} \sum_{k=1}^K \frac{|D_{ik}|}{|D_i|}
\log_2 \frac{|D_{ik}|}{|D_i|} \tag{2}
$$
公式说明：
- 分别求属性$A$的每个分类对应求得的熵，然后按照权重相加，其中，$\frac{|D_i|}{|D|}$就是属性$A_i$的权重。
- 计算总的信息增益：
$$
g(D,A) = H(D) - H(D|A) \tag{3}
$$
信息增益比
计算方法：
$$
g_R (D, A) = \frac{g(D,A)}{H_A(D)} \tag{4}
$$
ID3 算法
输入
训练数据集：$D$
特征集：$A$
阈值：$\varepsilon$
输出
决策树：$T$
具体实现
- 若$D$中所有实例均属于同一类$C_k$，则 T 为节点树，并将类$C_k$作为该节点的类标记，返回$T$；
- 若$A=\mathcal{\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_i$作为训练集，以$A-\lbrace A_g \rbrace$为特征集，递归调用步骤$1$~$5$，得到子树$T_i$， 返回$T$。
C4.5 算法（和上面的算法差不多）
输入
训练数据集：$D$
特征集：$A$
阈值：$\varepsilon$
输出
决策树：$T$
具体实现
- 若$D$中所有实例均属于同一类$C_k$，则 T 为节点树，并将类$C_k$作为该节点的类标记，返回$T$；
- 若$A=\emptyset$，则$T$为单节点树，并将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$；
- 否则按照信息$（4）$式计算$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-\lbrace A_g \rbrace$为特征集，递归调用步骤$1$~$5$，得到子树$T_i$， 返回$T$。
决策树剪枝算法
输入
生成算法产生的整个树：$T$
参数：$ \alpha$
输出
修剪后的子树： $T_\alpha$
具体实现
计算每个节点的经验熵；
递归地从树的叶节点向上回缩；
设一组叶节点回缩到器父节点之前与之后的整体树分别为$T_B$与$T_A$，其对应的损失函数值分别是$C_\alpha(T_B)$与$C_\alpha(
T_A)$，如果符合下面的条件则进行剪枝，即将父节点变为性的叶节点，将原本的叶节点合如该节点。
$$
C_\alpha(T_A) \le C_\alpha(T_B)\tag{5}
$$
注：$(5)$式中的等于是因为如果损失函数没有变化，则没必要去在计算一层树，直接剪掉 ⚔ 就好了。
- 返回$(2)$，知道不能继续为止，则得到了损失函数最小的子树$T_A$
基尼指数的计算方法
分类问题中假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为:
$$
Gini(p) = \sum_{k=1}^K p_k(1 - p_k) = 1 - \sum_{k=1}^K p^2_k \tag{6}
$$
对于二分类问题，若样本点属于第一个类的概率是$p$，则概率分布的基尼为：
$$
Gini(p) = 2p(1-p) \tag{6.1}
$$
对于给定的样本集合$D$，其基尼指数为：
$$
Gini(D) = 1-\sum_{k-1}^K (\frac{|C_k|}{|D|})^2 \tag{6.2}
$$
这里同样使用了基于统计数计算概率的方法。$C_k$是$D$中属于第$k$类样本的子集，$K$是类的个数。
最小二乘回归树生成算法
输入
训练数据集：$D$；
输出
回归树：$f(x)$
具体实现
在训练数据集所在的输入空间中，递归的将每个区域划分成两个子区域，并决定每个子区域上的输出值。构建二叉决策树。
- 选择最优切分变量$j$与切分点$s$求解：
$$
\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 ]
\tag{7.1}
$$
遍历变量$j$，对固定的切分变量$j$扫描切分点$s$。选择是上式达到最小值的$(j,s)$。
- 用选定的$(j,s)$划分区域并决定相应的输出值：
$$
R_1(j,s) = \left \lbrace x | x^{(j)} \le s \right \rbrace, \\
R_2(j,s) = \left \lbrace x | x^{(j)} \gt s \right \rbrace, \\
\hat{c}_m = \frac{1}{N_m}
\sum_{x_i \in
R_n(j,s)}
y_i, x \in R_m, m = 1,2
\tag{7.2}
$$
- 继续对两个子区域调用步骤$1，2$，直至满足停止条件。
- 将输入空间划分为$M$个区域$R_1,R_2,\cdots,R_M$，生成决策树。
$$
f(x) = \sum_{m=1}^M \hat{c}_m I (x \in R_M) \tag{7.3}
$$
CART 生成算法
输入
训练数据集 D；
停止计算的条件；
输出
CART 决策树
具体实现
根据训练数据集，从根节点开始递归地对每个节点进行以下操作构建二叉决策树。
设节点的训练数据集为$D$，计算现有特征对该数据集的基尼指数，此时对每一个特征$A$对其可能取到每个值$\alpha$根据样本点对$A=\alpha$的测试为“是”或“否”将$D$分隔成$D_1$和$D_2$两个部分，利用基尼指数计算公式计算$A=
\alpha$的基尼指数。
- 在所有可能的特征$A$以及他们所有可能的切分点$\alpha$中选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点，依照最优特征与最优切分点从现节点生成两个子节点，将训练数据集依照特征分配到两个子节点中去。
- 对两个子节点递归调用$(1), (2)$，直至满足停止条件。
- 生成$CART$决策树。
CART 剪枝算法
输入
$CART$算法生成的决策树$T_0$
输出
最优决策树$T_\alpha$
具体实现
- 设$k=0, T=T\alpha$；
- 设$\alpha = + \infty$；
- 自下而上地对个内部节点$t$计算$C(T_t)$，$|T_t|$以及
$$
g(t) = \frac{C(t) - C(T_t)}{|T_t| - 1} \tag{8} \\
\alpha = min(\alpha, g(t))
$$
这里，$T_t$表示以$t$为根节点的子树，$C(T_i)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶子节点个数。
- 对$g(t)=\alpha$的内部节点$t$进行剪枝，并对叶节点$t$以多数表决法决定其类，得到树$T$
- 设$k=k+1$，$ \alpha_k = \alpha$， $T_k = T$；
- 如果$T_k$不是有根节点即两个叶节点构成的树，则糊掉步骤$(2)$；否则令$T_k=T_n$；
- 采用交叉验证法在字数序列$T_0,T_1,\cdots,T_n$中选择最优子树$T_\alpha$。
