决策树-ID3，C4.5，CART

作者: 莱昂纳多91 | 来源:发表于2019-05-15 18:51 被阅读0次

决策树

直观上，决策树是一个树结构，从根节点开始，测试待分类项中相应的特征属性（每次只测一个特征维度），并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果

西瓜书里的图

在挑西瓜模型中，首先判断纹理这一特征维度，分成了3个数据集，其中模糊纹理这一波直接是叶子节点，存放决策结果。

而从数据的特征空间角度，决策树则是把整个特征空间划分成了若干个超立方体。就像魔方

可以是均分空间

更多的是不均分的空间

每一个小块，是一个空间划分 $R_{j}$ ，也是树中的一个叶子节点，存放着决策结果 $y_{j}$ 。
如果是回归树，则叶子结点存放回归结果 $c_{j}$

现在的问题是，就挑西瓜模型来说，应该选用哪个特征作为优先特征作根节点呢？
当然是越重要的，越能区分西瓜好坏的特征越优先选择了。

决策树的一般流程是：
1，对于数据集D(X,Y),按照某种方法选择对于当前数据集最重要的特征。
2，按照这个特征中值的不同划分为对应数量的子数据集 $D_{i}(X,Y)$ 。
3，如果 $D_{i}(X,Y)$ 中有的子数据集只包含一类数据或者类别相对比较纯，则该数据集就可以当作叶子节点。对于其他子数据集，分别重复1，2步。直到到达规定的最大轮数（树最大深度）或者用完了所有特征或者特征空间已经完美分割。
4，最后，得到分类函数：
$f(X_{i})=\sum_{j=1}^{k}y_{j}I(X_{i}\in R_{j})$
假设最终有k个划分空间（叶子节点）

决策树挑选特征的算法主要有3个：

ID3

大致流程

ID3就是使用信息增益来挑选特征的决策树算法。
具体地
1，计算当前数据集 $D_{i}$ 的熵H(X)
2，分别计算当前可用特征下D的条件熵 H(X|Ai)
3，分别计算不同特征的信息增益 I(X,Ai)=H(X)-H(X|Ai)，取最大者作为所挑选特征，如果最大的I也小于阈值，则终止
例如上篇中袜子位置问题，就应该选择袜子颜色特征作为第一个特征，这样甚至不再需要后续特征就能分好。

缺点

ID3算法，简单明了易理解，但有如下缺点：
1，只能处理离散特征，不能处理连续特征
2，未考虑过拟合的处理
3，未对缺失值做处理
4，算法倾向于优先选择取值较多的特征，他认为取值越多的特征，信息增益越大，条件熵越小。如果一个特征A1有10个取值，A2只有2个取值，即使价值相似，ID3也更倾向于选择A1.解释一下原因：
从条件熵公式可以看出：
$\begin{alignedat}{2} H(X|Y) &= -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) \\ &= \sum\limits_{j=1}^{n}p(y_j)H(X|y_j) \end{alignedat}$
当特征取值越多，
即n越大，则每个 $p(y_{j})$ 则相对会越小。
同时，n越大，则每个取值下样本量就会少。样本量少则分布更容易不平均从而导致 $H(X|y_j)$ 相对变小，这个变小会导致虽然n大，累加次数多，但不能弥补 $p(y_{j})$ 和 $H(X|y_j)$ 的双重减小。从而导致条件熵减小，信息增益变大
极端情况下，如果n=样本量，即该特征每个值都对应了唯一一个样本，则 $H(X|Y)=\sum_{j=1}^{n}\frac{1}{n}0=0$ ,信息增益最大，但是却毫无意义。
详见此处

C4.5

大致流程

为了解决上述问题，提出了本算法。
最主要的是，解决了问题4:引入信息增益比替代信息增益
$I_R(D,A) = \frac{I(A,D)}{H_A(D)}$
$H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$
即，每个信息增益，比上数据集在该特征上的熵。

问题1:连续特征作二元离散。在选取切分值的时候，计算每个切分值上的信息增益。取最大。
问题2:剪枝
问题3:缺失值

缺点

1，剪枝需优化
2，多叉树不如二叉树效率高
3，只能分类不能回归
4，熵模型需要计算对数，耗时

CART

思想：无限二分
即每次按照特征把数据分成两部分

一般流程

1，分类
CART树相对于C4.5的关键改变是用基尼指数替代了信息增益比
$Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$
对于数据集D，有k个类别，每个类别有 $C_k$ 个样本,则
$Gini(D) = 1-\sum\limits_{k=1}^{K}(\frac{|C_k|}{|D|})^2$
如果是二类分类问题，计算就更加简单了，如果属于第一个样本输出的概率是p，则基尼指数的表达式为：
$Gini(p) = 2p(1-p)$
对于数据集D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼指数表达式为：
$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$
注意这个式子，很像条件熵的公式。
所以，特征A下D的基尼指数可以认为是条件基尼指数Gini(D|A)
这样，选取最优特征以及特征切分时，应该挑条件基尼指数最小（信息增益最大对应着条件熵最小）的那一组。
这里基尼指数有一点比较特别，是它会根据特征的一个值把数据分成两部分，而不像ID3，C4.5一样特征有多少值就把数据分成几部分，即把多叉树改变成了二叉树

由于CART每次只把数据分成两部分，
那么，对于特征值多于两个的离散特征来说，应该如何划分数据？粗暴，直接穷尽所有组合，寻找基尼指数最小的组合。所以，后续，还会用到该特征
对于连续的特征，则像C4.5一样作离散化，在所有二元切分中找到基尼指数最小的切分，把特征做成二元离散的。同样，后续还会用到该特征
注意到，ID3和C4.5的离散特征只会参与一次特征选择，而CART则不是。

2，回归
回归预测的是连续值，训练数据的Y肯定也是连续值。
无限二分依然有效，只不过不适用基尼指数了，而是使用和方差
例如对于一个已经划分好的特征空间，回归树返回的值是对应的结果划分块中所有样本值的均值或中位数
而如何训练这个划分？
优化如下式子
$\underbrace{min}_{A,s}\Bigg[\underbrace{min}_{c_1}\sum\limits_{x_i \in D_1(A,s)}(y_i - c_1)^2 + \underbrace{min}_{c_2}\sum\limits_{x_i \in D_2(A,s)}(y_i - c_2)^2\Bigg]$
其中，A是特征，s是该特征的一个切分值，D1，D2是按照特征A的切分值s切分后的两个数据集，c1，c2分别是D1，D2内样本值的均值。
中括号内是固定A后，寻找最优s
中括号外是寻找最优的A

剪枝

剪枝非常重要。
CART树的剪枝是后剪枝，即建完树后再剪枝
对于一棵树T，其损失函数：
$C_\alpha(T)=C(T)+\alpha|T|$
C(T)是这棵树的预测误差，可以是对每个叶子里数据的基尼指数（或方差）作加权求和
|T|是树的叶子节点数

观察这个公式
当 $\alpha=0$ 时，树最大，叶子最多，最容易过拟合
当 $\alpha=+\infty$ 时，树最小，缩成了一个根节点

对于一棵树T，设t是其一个非叶子节点 $T_t$ 是以t为根节点的子树,则：
$C_{\alpha}(t) = C(t) + \alpha$
$C_{\alpha}(T_t) = C(T_t) + \alpha|T_t|$
分别表示t节点的损失和 $T_t$ 子树的损失
我们令 $C_{\alpha}(t) = C_{\alpha}(T_t)$ 可得
$\alpha_t = \frac{C(t)-C(T_t)}{|T_t|-1}$
这表示什么？
这表示如果当前剪枝设定的 $\alpha$ = $\alpha_t$ 时，
$T_t$ 这棵子树可以剪掉并用t代替，而不会带来更大的损失
而如果当前剪枝设定的 $\alpha$ > $\alpha_t$ 时
$C_{\alpha}(t) < C_{\alpha}(T_t)$
这表示必须要剪掉 $T_t$ 这棵子树，因为不但可以降低损失，还可以缩小树规模，一举两得。

所以，如果我们遍历所有t，获取所有 $\alpha_t$ 然后对其升序排序得到
$(\alpha_{t0},\alpha_{t1}...\alpha_{tn})$
所以，随着我们逐个设置 $\alpha=\alpha_{ti} ,i=0,1,2...n$
就会得到一个个剪枝过后的T
$(T_{c0},T_{c1},...T_{cn})$
这么多T，那个是最好的？
用个新的数据集测测就OK了，谁高选谁

参考
刘建平博客-决策树
统计学习方法-李航

决策树-ID3，C4.5，CART

决策树

ID3

大致流程

缺点

C4.5

大致流程

缺点

CART

一般流程

剪枝

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读