Decision Tree

决策树模型

• 决策树是一种基本的分类与回归的方法
• 决策树由节点和有向边组成
• 节点分为内部节点和叶节点
• 决策树的学习其实就是特征选择的过程

决策树学习

决策树学习算法包含特征选择、决策树的生成和决策树的剪枝过程

给定数据集$D=\lbrace (x_1,y_1),…,(x_m,y_m) \rbrace$其中$m$为样本容量，$x_i=(x_i^{(1)},…,x_i^{(n)})$，$n$为特征个数；$y_i\in \lbrace 1,2,…,K \rbrace$为类标记。

信息增益

统计学中，熵是随机变量不确定性的度量，即混乱程度。假设$X$是一个取有限个值的离散随机变量，其概率分布为$P(X=x_i)=p_i,i=1,..,N$，那么$X$的熵定义为$H(X)=-\sum_{i=1}^n p_i log p_i$条件熵$H(Y|X)$可以表示为已知随机变量$X$的条件下，随机变量$Y$的不确定性，也可以表示成$H(Y|X)=\sum_{i=1}^N p_iH(Y|X=x_i)$其中$p_i=P(X=x_i)$。当熵和条件熵中的概率由数据估计得到时，则分别称之为经验熵和条件经验熵，如果出现0概率，则令$0log0=0$。

信息增益表示在得知特征$X$的情况下而使得$Y$的不确定性减少的程度，形式化表述为：特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为$g(D,A)=H(D)-H(D|A)$这里的信息增益等价于训练数据集中类与特征的互信息。计算信息增益的算法如下：

---

输入：数据集$D$和特征$A$

---

1 计算数据集$D$的经验熵$H(D)=-\sum_{k=1}^K \frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
2 计算特征$A$对数据集$D$的经验条件熵$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|}$
3 计算信息增益$g(D,A)=H(D)-H(D|A)$.

---

输出信息增益

---

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以缓解这个问题。特征$A$对训练数据集$D$的信息增益比定义为其增益信息$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即

$$\begin{aligned} g_R(D,A)=\frac{g(D,A)}{H_A(D)} \end{aligned}$$

其中，$H_A(D)=-\sum_{i=1}^{A_n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$，$A_n$是特征$A$取值的个数。

ID3

ID3算法采用自上而下递归式的算法构建决策树，它使用信息增益作为特征选择的标准。停止条件是节点所有特征的信息增益都很小（阈值$\epsilon$）或没有特征可以选择为止。

---

输入：训练数据集$D$，特征集$A$，阈值$\epsilon$

---

1 若$D$中所有实例属于同一类$C_k$，$T$为单节点树，$C_k$为该节点的类标记，返回$T$
2 若$A=\emptyset$则$T$为单节点树，将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$
3 否则，分别计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_g$
4 如果$A_g<\epsilon$，则置T为单节点树，将$D$中实例数最大的类$C_k$作为该节点的类标记，返回$T$
5 否则，对$A_g$的每一个可能值$a_i$，根据$A_g=a_i$将$D$分割成若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树$T$，返回$T$
6 对每个子节点$i$，以$D_i$为训练集，以$A-A_g$为特征集，递归调用以上步骤

---

输出：决策树$T$

---

C4.5

C4.5与ID3的差异在于C4.5使用信息增益比进行选择选择

基尼指数

基尼指数表示不确定程度，基尼指数越大，样本集的不确定程度就越大、纯度越低。

分类问题中，假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为$Gini(p)=1-\sum_{k=1}^K p_k^2$对于给定的样本集$D$，其基尼指数为$Gini(D)=1-\sum_{k=1}^K\left( \frac{|C_k|}{|D|} \right)^2$其中$C_k$表示第$k$类的样本子集。表示集合$D$的不确定性。

假设样本集$D$根据特征$A$的不同取值被分成$A_n$个部分，则定义在特征$A$下集合$D$的基尼指数为

$$\begin{aligned} Gini(D,A)=\sum_{i=1}^{A_n} \frac{|D_i|}{|D|}Gini(D_i) \end{aligned}$$

CART

CART分类树
使用基尼指数作为划分属性的标准，每次选择基尼指数最小的属性。

CART回归模型
假设已将输入空间划分为$M$个单元$R_1,…,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，回归树模型可以表示为$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$当输入空间划分确定时，可以用平方误差$\sum_{x_i}(y_i-f(x_i))^2$表示训练误差, $c_m$输出值为对应$R_m$上所有样本输出值的均值。

使用启发式的方法划分输入空间，遍历输入变量和可能的切分变量找到最优的切分变量$j$和切分点$s$，即找到切分后部分的误差最小：

$$\begin{aligned} &R_1(j,s)=\lbrace{x|x^{(j)}\le s\rbrace} \\ &R_2(j,s)=\lbrace x|x^{(j)}> s \rbrace \\ &\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] \end{aligned}$$

其中$c_1,c_2$是划分后部分中输出值的均值。最小二乘回归树算法描述如下：

---

输入：训练集$D$

---

1. 选择最优切分变量$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]$
2. 用选定的对$(j,s)$划分区域并决定相应输出值：$R_1,R_2,c_1,c_2$
3. 继续对两个子区域调用步骤1、2直至满足停止条件
4. 将输入空间划分为$M$个区域$R_1,…,R_M$，生成CART树$f(x)=\sum_{m=1}^Mc_mI(x\in R_m)$

---

输出：$f(x)$

---

决策树的剪枝

以上方法可能会产生过拟合现象，适当剪枝会使得决策树的泛化效果变得更好
剪枝分为预剪枝和后剪枝两种，预剪枝指的是在决策树生成的过程中进行剪枝，后剪枝则是在生成决策树之后再进行剪枝。

预剪枝

大致过程描述：对于一个节点，考虑其剪枝或者不剪枝的情况，看这两种情况下哪种正确率高（一个节点的类别由其包含同类样本数最多的决定），由此决定是否剪枝。

预剪枝基于贪心本质禁止某些节点展开，而这些节点第一次展开效果可能不好，但后续表现可能显著提高，所以会带来欠拟合的风险。

后剪枝

大致过程描述：自下而上，叶节点不考虑，考虑其父节点F是否需要剪枝，可以仅仅通过父节点包含的样本，在剪枝和不剪枝的情况下分别计算准确率，然后确定是否需要剪枝。

下面是令一种后剪枝的方法（我不是很了解）：
通过极小化决策树整体的损失函数来实现。设树的叶节点个数为$|T|$，$t$是树$T$的叶节点，此叶节点上有$N_t$个样本，属于类$C_k$的样本有$N_{tk}$个，$H_t(T)$为叶节点$t$上的经验熵，$\alpha \ge 0$为参数，则决策树学习的损失函数可以定义为

$$\begin{aligned} C_{\alpha}(T)=\sum_{t=1}^{|T|} N_tH_t(T)+\alpha |T|=C(T)+\alpha |T| \end{aligned}$$

其中经验熵为$H_t(T)=-\sum_k \frac{N_{tk}}{N_t}log_2 \frac{N_{tk}}{N_t}$。$C(T)$表示模型对训练数据的预测误差，|T|表示模型的复杂度。剪枝算法描述如下：

---

输入：决策树$T$，参数$\alpha$

---

1 计算每个节点的经验熵
2 递归地从树的节点向上回溯，如果保留子节点的损失函数更大，剪枝以父节点作为叶子
3 返回2直到不能继续为止

---

输出：修建后的决策树$T_{\alpha}$

---