决策树（ID3、C4.5、CART）与随机森林
1. 什么是决策树？
根据一系列特征，最终决定结果的树，叫做决策树。
2. 如何构建决策树？
方案一：ID3算法
首先，说明一些重要公式：
- 信息量：
- 信息熵：
- 信息熵期望：
；s是未分裂前的节点，sj是按照属性 V 分裂后属于各属性值 j 的节点
信息熵是事物不确定性的度量标准。信息熵越大，不确定性越大，混乱程度越大。
算法流程：
（1）给定样本，先将特征离散化
比如：（这里年龄、性别叫做属性，青年、中年、老年、男、女叫做属性值）
年龄：青年（0）、中年（1）、老年（2）
性别：男（0）、女（1）
Label：买（1）、不买（0）
（2）从根节点开始分裂，选择哪个属性来分裂呢？
假设总体1000人，买：800，不买：200
按年龄分：青年：200，中年：400，老年：400
按性别分：男：600，女：400
1. 计算分裂前“总体”的信息熵期望：
2. 分别计算按年龄、性别分之后的信息熵期望：
a. 按年龄：
青年：200 ---》买：120，不买：80
中年：400 ---》买：320，不买：80
老年：400 ---》买：360，不买：40
b. 按性别算，同理。
3. 计算信息增益：
s：分裂前的总体 ，A：属性
选择信息增益大的属性，且已经选择的属性不能再作为分裂的标准。
4. 假设选择了“年龄”，则现在是：
有3个小总体和1个候选属性
这时计算出 Es1(s1)、 Es2(s2)、Es3(s3) 以及 Es1(性别)、Es2(性别)、Es3(性别) ，比较 【Es1(s1) - Es1(性别)】、【Es2(s2) - Es2(性别)】、【Es3(s3) - Es3(性别)】的大小，取最大的来分裂。
5. 假设【Es1(s1) - Es1(性别)】最大，则 “青年” 继续以 “性别” 分裂，最后得：
买 / 不买：按少数服从多数原则
（3）小结：
每次迭代都是计算出全局的小总统的 Esn(sn) 以及 Esn(An) ，哪个信息增益大，就选哪个小总体sn按An分裂。
（4）缺点：
- 贪婪性：倾向于选择属性值多的属性分裂
- 奥卡姆剃刀原理：尽量用较少的东西来完成较多的事情（已经选择的属性不再作为分裂标准）
- 对于连续值的特征，人为划分的不同，对结果影响很大
方案二：C4.5
算法与ID3只有一点不同
ID3：以信息增益Gain为判断依据
C4.5：以信息增益率GainRatio为判断依据
方案三：CART
CART：分类和回归数，且是二叉树，每个属性只有两个属性值
与ID3和C4.5不同的是，CART用过的属性可以继续使用，且CART可以用于分类和回归，ID3和C4.5仅用于分类。
首先，说明一些重要公式：
- 基尼系数：
- 基尼系数期望：
；A：属性，j：属性值，s：分裂前的总体
一、CART做分类
算法步骤：
不断迭代计算各个“小总体”sn按照属性An分裂的Gini_Index，选择最小的属性分裂。
不同类型的属性如何计算：
1. 二值性属性
| s=10 | ||
|---|---|---|
| 属性：有无房 | t1有房 | t2无房 |
| 买 | 3 | 4 |
| 不买 | 0 | 3 |
2. 多值型属性
| 婚姻状况 | ||
|---|---|---|
| 单身 | 已婚 | 离异 |
因为CART是二叉树，因此只能有两个属性值，于是有：
| s=10 | ||
|---|---|---|
| t1单身或已婚 | t2离异 | |
| 买 | 6 | 1 |
| 不买 | 2 | 1 |
| s=10 | ||
|---|---|---|
| t1单身或离异 | t2已婚 | |
| 买 | 3 | 4 |
| 不买 | 3 | 0 |
| s=10 | ||
|---|---|---|
| t1离异或已婚 | t2单身 | |
| 买 | 5 | 2 |
| 不买 | 1 | 2 |
每种分法得到一个Gini_Index，选择最小的Gini_Index的分法。
3. 连续值型属性
类似于多值型属性，把属性值分成两个，只不过因为是连续值，因此不是采用组合的方式。
以“收入”为例，将“收入”由小到大排序，对相邻的两个值取平均作为“分水岭”，得：
| 收入 | 60 | 70 | 75 | 85 | 90 | 95 | 100 | 120 | 125 | 220 |
|---|
| 分水岭 | 65 | 72 | 80 | 87 | 92 | 97 | 110 | 122 | 172 |
|---|
按照不同的分水岭划分：
| s=10 | |
|---|---|
| <=65 | >65 |
| ............... |
选择这其中最小的Gini_Index的划分情况。
二、CART做回归
算法步骤：
不断迭代计算各个“小总体”sn按照属性An分裂的∑MSE（误差平方和），选择最小的属性分裂。
不同类型的属性如何计算：
1. 二值型属性
| s=10 | |
|---|---|
| R1在郊区 | R2不在郊区 |
| y1...yk | y(k+1)...ym |
计算R内的均值：
计算误差平方和∑MSE：
2. 多值型属性
像上面【CART做分类】的例子那样分情况，最后选取最小∑MSE的那个来划分。
3. 连续值型属性
像上面【CART做分类】的例子那样分情况，最后选取最小∑MSE的那个来划分。
最后结果：
结果为所属样本的平均值。
最后几层叶子节点肯定会有很多的连续值型属性，这样才能使结果分得更加细，有更多的 “y的均值” 出现，这样测试的时候，MSE才会更小。（最后几层类似于神经网络里的全连接层）
3. 决策树的停止条件
- Gain或者GainRatio的增长低于阈值，但这样就要调节阈值
- 测试集错误率或者误差平方和上升
4. 过拟合
决策树本身的问题就是容易过拟合，因为它会不断生长，寻找最大Gain或GainRatio 和 最小Gini_Index或∑MSE，特别是CART。
为了解决过拟合，有两种方案
方案一：剪枝
- 相邻的叶子结点，如果合并后的不纯度增加在允许范围，则合并
- 合并后，测试集错误率或误差平方和下降，则合并
缺点：反复尝试，较耗时间
方案二：随机森林
最后结果采取投票制度，少数服从多数。
1. bagging方法（有放回采样）
随机抽取训练集中的60%建一棵树，每个样本在每一次建树时被抽到的概率都一样，这也说明允许并行建树，共建N课树。最后用测试集验证。
2. boosting方法
10000个样本，将其分为训练集和测试集。
记每个样本从训练集中被抽为“训练”的概率为β（刚开始时，各个β相等）
（1）按照β抽出80%为训练，20%为预测试
（2）建一棵树，然后用预测试集测试，对于被分错的样本，加大它的β，目的是加大错误样本被抽为训练的概率
（3）重复（1）（2）建N棵树
（可选）【直到错误样本被预测正确为止，表现为全局β的和不变】
5. 总结
ID3、C4.5仅用于分类，用过的属性不能再用
CART用于分类和回归，用过的属性还可以再用
欢迎转载，转载请标明出处。