二探决策树（Decision Tree）基于连续属性生成的决策树及其他

本文是笔者学习决策树时对连续性数据和数据有缺失值时的处理方法的学习笔记

连续值离散化

个人对连续值离散化的理解在于：
一种简单的办法是二分法^[1]，C4.5算法正是使用了二分法作为连续属性数值离散化的机制。
给定样本 $D$ 和连续属性 $a$ ，先对 $a$ 特征上的 $n$ 个不同的取值进行排序。将它们记作 $\{{a_1},{a_2},\cdot \cdot \cdot,{a_n}\}$ ，我们需要找到一个划分点 $t$ ，使得 $D$ 按照大于被分为子集 ${D_t^-}$ 以及 ${D_t^+}$ .
因而，最基本的想法是考察所有的相邻的两组数据共 $n-1$ 个中位点（还未去重）作为划分的集合。我们用信息增益(information gain)对各中位点进行考察。
那么，对这个属性的信息增益，就是各个划分点中出现的信息增益的最大值。<br />
$\begin{align*} Gain(D,a)&=(\max\limits_{t \in T_a}\,Gain(D,a,t)\\ &=(\max\limits_{t \in T_a}\,Ent(D)-\sum\limits_{\lambda\in\{-,+\}} {\frac{|D_i^{\lambda}|}{D}} Ent(D_i^{\lambda}) \end{align*}$

缺失值处理

缺失值处理主要面临两个问题的解决：

如何在属性值缺失的情况下划分属性选择？
若样本在给定的属性上缺失，应该怎么对样本进行划分？

我们给出一组定义：给定训练集 $D$ 和属性 $a$ ，考虑a的V个可取值 $\{a^1,a^2,...,a^V\}$ ，令 $\tilde{D^v}$ 表示 $\tilde{D}$ 中在属性 $a$ 上取值为 $a^v$ 的值。 $\tilde{D_k}$ 表示 $\tilde{D}$ 中属于第 $k$ 类 $\,$$\{k=1,2,...,|Y|\}$ 的样本子集，显然 $\tilde{D} = \cup_{k=1}^{|Y|}\tilde{D_k}$ , $\tilde{D} = \cup_{v=1}^{V}\tilde{D_k}$ 。假设我们为每一个样本 $x$ 赋予一个权重 $w_x$ (所有的 $w_x$ 权重初始值为1)并且定义以下三个量：
$\rho=\frac{\sum_{x \in \tilde{D}}w_x}{\sum_{x \in {D}}w_x} \\ \tilde{p_k}=\frac{\sum_{x \in \tilde{D_k}}w_x}{\sum_{x \in \tilde{D}}w_x}\; (1\le k \le |Y|) \\ \tilde{r_v}=\frac{\sum_{x \in \tilde{D^v}}w_x}{\sum_{x \in \tilde{D}}w_x}\; (1\le k \le V) \\$
$\rho$ 可以理解为在属性 $a$ 上值没有缺失的样本所占比例， $\tilde{p_k}$ 可以理解为无缺失样本中第 $k$ 类所占比例, $\tilde{r^v}$ 可以理解为无缺失样本中在 $a$ 上取值为 $a^v$ 所占比例.显然地,有 $\sum\tilde{p_k}=1=\sum \tilde{p_k}$

对于问题(1),C4.5算法假定数据缺失具有随机性,在确立分点的时候直接暂时剔除了在本项特征缺失的数据.并且对信息增益进行修正:
$\begin{align*} Gain(D,a)&=\rho\times\,Gain(\tilde{D},a)\\ &=\rho\times(\,Ent(\tilde{D})-\sum\limits_{v=1}^V {\tilde{r_v}} Ent(D^{v})) \end{align*}$
并且有:
$Ent(\tilde{D})=-\sum\limits_{k=1}^{|Y|}\tilde{p_k}log\tilde{p_k}$
对于问题(2),C4.5可以通过把该特征数据缺失的数据按照 $\tilde{r_v}$ 作为权重进行分配,将原有的 $w_x$ 分配到各个节点中,权重变为 $\tilde{r_v}\cdot w_x$ ,继续递归算法.
<br />

CART算法

CART算法的决策树是二叉树,给定输入变量 $X$ ,输出随机变量 $Y$ 的概率分布的学习方法.假设了:决策树是二叉树.主要算法也是生成树-树剪枝.适用于数值和标称型数据,要将标称型数据转化为二值型数据.
1.回归树:考虑训练集 $D=\{(x_1.y_1),(x_2.y_2),(x_3.y_3),...,(x_N.y_N),\}$ 求一棵回归树
我们假设已经把输出空间划分为 $M$ 份 $R_1,R_2,...,R_M$ ,在每个单元有输出 $c_i$ 与之对应,这个模型可以表示做:<br />
$f(x)=\sum\limits_{m=1}^M c_m I(x \in R_m)$
不妨用平方误差来表示预测误差。

最小二乘回归树生成算法：

1.遍历特征j，找到特征j上切分点s.
$s.t. \qquad \min\limits_{c_1} \sum\limits_{x_i \in R_1(j,s)}(y_i-c_1)^2+\min\limits_{c_2} \sum\limits_{x_i \in R_2(j,s)}(y_i-c_2)^2$
2.划分区域并且决定输出值,划分区域后, $\hat{c_m}$ 是区域的均值
$R_1(j,s)=\{x|x_j \leq s\},R_2(j,s)=\{x|x_j \leq s\}\\ \hat{c_m}= \frac{1}{N_m} \sum\limits_{x \in R_m (j,s)}y_i,\qquad x \in R_m, m=1,2$
3.不断划分,直到停止
4.将输入空间划分,生成决策树
$f(x)=\sum\limits_{m=1}^M c_m I(x \in R_m)$

分类树的生成:

概率分布的基尼系数
$Gini(p)=\sum\limits_{k=1}^Kp_k(1-p_k)=1-\sum\limits_{k=1}^K p_k^2$
对于分类问题的集合D,其基尼系数为:
$Gini(p)=1-\sum\limits_{k=1}^K (\frac {|C_k|}{|D|})^2$
特征A下的集合基尼系数(二分类):
$Gini(D,A)=\frac{|D_1|}{|D|}| Gini(D_1)+\frac{|D_2|}{|D|} Gini(D_2)$

CART生成算法

CART生成算法构造的是二叉决策树.考虑训练集 $D$ ,计算现有特征对数据集的基尼系数.遍历所有特征的所有切分点,遴选出基尼系数最小的特征进行二分类并且对子节点递归调用算法直到满足停止条件.

CART剪枝

Loss function: $C_\alpha (T)=C(T)+\alpha |T|$
$C(T)$ 为预测误差, $|T|$ 为子树结点个数
对于固定的 $\alpha$ ,随着数分支的增加,有序度增加,预测误差减小,子树结点增加.
对于任意结点 $t$ 和其子树 $T_t$ .当 $\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$ 时,t作为结点和其扩展出的子树效力相同,根据奥卡姆剃刀原理,应该进行剪枝.

CRAT剪枝算法

输入生成决策树 $T_0$ ,输出最优决策树 $T_\alpha$
$k=0,T=T_0, \alpha= +\infty.$
自底向上对结点 $t$ 去计算 $C_t,|T_t|,g(t)=\frac{C(t)-C(T_t)}{|T_t|-1} \\ \alpha = min(\alpha,g(t))$
考察 $g(t)=\alpha$ 的结点( $\alpha$ 最小)对其进行剪枝,并且对 $t$ 以多数表决决定类得到新树.
$k++,\alpha_k=\alpha,T_k=T$ 直到树只剩下根节点和两个叶子.
交叉验证过程中生成的所有子树 $T_i$

模型树

把叶节点设定为分段的线性函数.相较于回归树,模型书的结果更容易理解,并且,具有更好的预测准确度.

阅读:

多变量决策树:
假设数据集 $D$ 有 $V$ 个特征,我们可以把决策树考虑为一系列轴平行的(axis-parallel)状态空间分类边界.多变量决策树(multivariate decision tree)或者说斜决策树(oblique decision tree)可以较好解决这个问题.这里的决策树的非叶节点就是一个形如 $\sum_{i=1}^dw_ia_i=t$ 的线性分类器.

链接：
初探决策树（Decision Tree）基于离散属性生成的决策树

之所以说二分法是简单的方法，是因为有时候二分不是能够那么好地解决所有模型，有的变量对一些特征的某个临界点发生的很微小的变动非常敏感，所以这个机制和算法还要随着具体模型的改变而改变。 ↩