[数据结构与算法]ID3、C4.5、CART决策树

预备知识

信息熵

1.什么是信息熵?
信息熵可描述为：一件事件发生给我们带来的平均信息量。 数学上描述为：事件发生所带来的信息量的期望，即事件发生可能出现结果的概率对所带来信息量的加权。
什么是信息量？如何理解信息量？如何定义信息量？
信息量可理解为一件事情发生所带来的信息的多少。

1. 例：明天下雨、明天太阳从东边升起 两句话带来的信息是不一样的，前者提醒我们带伞或雨衣，而后者则毫无信息量。又可以得知，上述两句话带来的信息量是依赖于我们已有认知，即我们不确定明天的天气，因为天气有很多可能性，但是太阳升起的方向本身很确定，没有信息量。所以，已有认知是否可以理解为事件本身发生的不确定性，答案是肯定的(别杠，杠就是你对)，即：一件事是否有信息量取决于事件本身的不确定性。
2. 天气有很多可能发生的结果，下雨、阴天和晴天等。而太阳升起则是一个确定事件。即：信息量与事件发生的概率有关，并且概率越大，信息量越少，信息量随着概率的增长而减少。
3. 两句话：明天下雨，太阳依旧从东边升起和明天下雨，是工作日。前者只有半句有用，后者两句话都有用。即：信息量可相加。
4. 当两件事不相关且同时发生时，概率及信息量上有$$p(x,y)=p(x)?p(y)$$ $$Info(x,y)=Info(x)+Info(y)$$

在考虑信息量非负的基础上，结合上述规则，可以确定信息量函数定义为：$$Info(x)=?lo{g}_{2}p(x)$$而信息熵则是对该事件发生所带来的信息量的期望，考虑事件发生所有产生的结果，有：$$H(x)=?\sum _{i=n}^{n}p(x)lo{g}_{2}p(x)$$所以可以理解：当事件发生所产生的结果很少时，即确定性很高时，信息量很少，信息熵也很小(太阳升起)。而当事件发生不确定时，信息量提升，信息熵也升高，所以，信息熵可以描述不确定性。

ID3 算法

ID3决策树算法的思想就是依靠于信息熵。即每在决策树中确定一个分支条件，该集合的不确定性应该降低，体现在信息熵上就是，整体信息熵在确定分支条件后，整体的信息熵应该大幅度降低，所以如何确定分支条件是ID3算法的核心。

信息增益

信息增益就可理解为数据集在确定分支条件下，可获取信息的多少，即整体数据集不确定性下降的程度，体现在信息熵上，即信息熵下降的程度。
整体信息熵：$$H(D)=?\sum _{k=1}^{K}p(x_i)lo{g}_{2}p(x_i)$$假设当前选定A特征为切分分值，则切分后数据集的信息熵就为各切分数据集的信息熵之和。
$$H(D,A)=?\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}lo{g}_2\frac{|D_{ik}|}{|D_i|}$$信息增益定义为：$$g(D,A)=H(D)?H(D,A)$$信息增益越大，则表示了在已知A特征下，数据的不确定性下降的最大，即数据边的越纯。

ID3算法描述

1. 确定数据集合和特征集合，计算数据信息熵。
2. 遍历所有特征，计算条件熵和信息增益，并选择信息增益最大的特征作为切分特征。
3. 去除特征集合中的该特征，若剩余特征集合只包含一个特征，则作为叶子结点。否则，针对每一叶子结点，重复1、2步。

ID3算法缺点

1. 贪婪算法，未考虑过拟合。
2. 只能处理离散分布特征，并为考虑缺失值。
3. 针对可取值范围较多的特征，信息增益结果较高。

C4.5

针对ID3算法缺点第三条，引入信息增益率来解决。

信息增益率

数据集D的信息熵定义在数据类别之上。条件信息熵定义在已知特征A后，划分的各子集的信息熵与子集占比加权之和。
信息增益率定义为：
$$g_{ratio}=\frac{g(D,A)}{H_A(D)}$$ $$H_A(D)=?\sum _{i=1}^N\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|}$$其中D_i为特征A取值为i时的集合。
相较于信息增益，信息增益率对特征取值较少的特征存在偏好。所以，C4.5在进行特征选择时，先是取高于信息增益率平均值的所有特征，然后取最高信息增益率的特征作为切分特征。

剪枝策略

顾名思义，防止过拟合，主要有两个。

预剪枝

在树生成时，通过某些规则和条件停止生成。方法有：

1. 样本取值低于阈值(人为设定)。
2. 特征集合无待分裂特征。
3. 从数据准确度入手，切分后的准确度下降。

由于是在训练过程进行剪枝，很可能会带来欠拟合。

后剪枝

在已生成的树上进行剪枝(悲观剪枝)。剪枝条件是：自下向上的进行节点聚合，判断该聚合是否会导致准确度的下降或上升(同错误率的上升或下降)，若准确度上升，则进行剪枝。

C4.5算法描述

1. 初始化训练集合特征集合。
2. 遍历所有特征，计算各特征的信息增益率，取所有高于平均值的特征后，取最大信息增益率的特征，作为当前分裂特征，并在特征集合中去除该特征。
3. 若特征集合中无可分裂特征，或当前叶结点数据集合特征低于某阈值，或叶结点所有数据均属于同一类别，则标记该叶结点，停止。否则，针对该叶结点，重复1、2步。

C4.5缺点

1. 多叉树，非二叉树，复杂度高。
2. 仅用于分类。
3. 针对连续特征，需要遍历内部各切分点的信息增益率，涉及排序、对数运算(信息增益率)操作，时间复杂度高。

CART树

CART树，全程为:Classification And Regression Tree。所以，即可用于分类，也可用于回归。

优点

1. 二叉树，速度快。
2. 回归+分类。
3. 信息熵改为基尼指数。
4. 剪枝方式从悲观到代价剪枝。
5. 特征可重复使用。

特征划分标准

分类树

信息增益换为基尼指数。基尼指数代表了模型的不纯度，即基尼指数越小，数据越纯，越不乱。定义为：
$$Gini(D)=\sum _{k=1}^K\frac{|D_k|}{|D|}(1?\frac{|D_k|}{|D|})=1?\sum _{k=1}^K(\frac{|D_k|}{|D|}{)}^2$$$$Gini(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$$基尼指数表示了数据集中随机抽取两个样本，其类别标记不一致的概率。值越小，数据纯度越高，且偏向于特征值较多的特征，类似信息增益。可用于度量任何不均匀分布。当为二分类时，基尼指数为：
$$Gini(D|A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$Gini指数与信息熵的差异：
$$H(D)=?\sum _{k=1}^{K}p(x_i)lo{g}_{2}p(x_i)\approx \sum _{k=1}^{K}p(x_i)(1?p(x_i))$$可以理解：基尼指数为熵模型的一阶泰勒展开。

回归树

使用和方差度量，对于任意特征A，在特征A中寻找切分点，得到基于A特征切分点划分的$D_1$和$D_2$，然后求出分别使得$D_1$和$D_2$均方差最小的切分点，同时该切分点满足$D_1$和$D_2$的和方差最小，对比所有可切分特征的和方差，选择最小的特征和切分点，作为当前分支策略。即求取下式：
$$\underset{a,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in D_1}(y_i?c_1{)}^2+\underset{c_2}{\min }\sum _{x_2\in D_2}(y_i?c_2{)}^2]$$式中，$c_1$为$D_1$子集$A$特征的均值，$c_2$为$D_2$子集$A$特征的均值。

剪枝策略

CART树采用代价复杂度剪枝算法，这可以理解为一种枚举算法。从最开始的一棵完整树，通过一种成本复杂度的度量准则决定某些节点可以被一个类别叶结点所代替，最后只剩下包含全部数据的单个结点时停止。
代价复杂度算法需要一个测试集来计算所有树的损失，选择分类性能最佳的树作为最优树进行返回。

1. 最大树T₀，定义树的损失函数为：$$C_{\alpha }(T)=C(T)+\alpha |T|$$第一项为预测误差，第二项为正则项，$|T|$为叶结点个数，$\alpha$是平衡预测误差和正则项的参数。
2. 如何权衡$\alpha$的取值，当树确定时，可以确定唯一值$\alpha$使得$C_{\alpha }(T)$即，对于$\alpha$从0取到$+\infty$，对于每一个固定的 $\alpha$，可以找到最小的最优子树$T(\alpha )$。当$\alpha$很小时，$T_0$(全树)是最优子树。当$\alpha$很大时，单独根节点构成的树最优子树。当$\alpha$逐渐增大时，即每次剪枝后，都会得到一棵子树，最终得到树的序列：$T_0,T_1,T_2,T_3,...,T_n$。

问题：如何确定$\alpha$的值？如何进行剪枝？如何判断该分支该不该减？
根据李航《统计机器学习》中的内容判定，对于当前树中的某一子树的根节点，有：$$C_{\alpha }(T)=C(T_t)+\alpha |T|$$把该子树剪掉后(被剪枝子树上的节点剪枝后全部分布在该子树根节点)，有损失：$$C_{\alpha }(t)=C(t)+\alpha$$剪枝后，树模型复杂度下降，但是准确度变化情况不得而知(即损失第一项)，那么如何判断该分支该不该剪？
上述两式肯定存在有$$C_{\alpha }(T)\ge C(t)||C_{\alpha }(T)\le C(t)$$即肯定存在一点，使得$$C_{\alpha }(T)=C(t)$$可以解得：$$\alpha =\frac{C(t)?C_{\alpha }(T_t)}{|T_t|?1}$$如何理解此时$\alpha$的作用？
当$\alpha$取上式时，可以认为，当前子树剪枝或不剪给模型带来的损失一样，即可认为当前$\alpha$是一阈值，当$\alpha$增大时，不剪枝带来的损失大于剪枝后的损失，即可以将上式变为：$$g(t)=\frac{C(t)?C_{\alpha }(T_t)}{|T_t|?1}$$即当$\alpha$取值超过$g(t)$时，就对该子树剪枝。
即，对于某棵树，其$\alpha$是一样的，当$\alpha$逐渐增加时，肯定超过了某棵子树或节点的$g(t)$值，但还没有超过其它节点的$g(t)$值。该$\alpha$逐渐增大后，最终只剩下一个节点的树，则表示剪枝完成，然后使用一个测试集测试所有树的误差，保留误差最小的树作为最终树。

CART的优势

缺失值处理

采用替代划分处理缺失值。

1. 存在缺失值的特征如何计算$Gini$指数？
   先计算在该特征下，非缺失数据划分后的$Gini$指数，然后将非缺失值所占比例作为系数与指数相乘作为最终该特征下的增益。
2. 当缺失值特征有最大的$Gini$指数时，如何进行？
   代理选择。计算其余所有特征的$Gini$指数，选择排名第二特征，若也有缺失值，则继续选择，直到一个没有缺失值的特征出现，然后将该特征作为最终划分特征。
3. 若所有特征都有缺失值，当前如何划分？
   选定最大$Gini$指数的特征，在无缺失数据划分后，依靠左右字数的比重作为系数，将缺失值数据分别乘以系数后分配在左右子树中，即左右子树都含有该缺失数据，但是权重不一样。

类别不平衡问题

采取了一种先验机制，想当与对数据进行加权，在CART分类策略中，需要计算每个节点中正负样本与根节点正负样本的比例的大小，想当与对数据进行加权。
即对于叶结点归属类别(假设为二分类)，此时若有节点$N_i$：$$\frac{N_i^1}{N_{root}^1}>\frac{N_i^0}{N_{root}^0}$$若上式满足时，则该节点$N_i$可被分为1类。

ID3、C4.5与CART比较

参考

李航 《统计机器学习》
各种百度、知乎资料，不一一列举了(杂乱)。