# Random Forest

见李航的《统计学习方法》

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F76040f98a3fe90aa1e633529801be9ecc3e17504.png?generation=1589383924044650\&alt=media)

[决策树方法小结](http://blog.csdn.net/yujianmin1990/article/details/47406037)

应思考的几个问题

* 属性值应当完全二值的还是多值的？或者节点的分支数应该是几?(CRAT和random forest是二叉树，ID3，C4.5等都是多叉树)
* 如何确定某节点出应该测试哪个属性
* 何时可以令某个节点成为叶子节点，即合适停止分裂。（1叶子节点很纯，2分裂后信息增益或gini系数或xgboost中的“gini”系数小于阈值）
* 如果树生长的“过大”，如何“剪枝”使得它变小变简单（误判，以父节点“作为”叶子节点，对比子节点的预测效果，若更优，则删除子节点）
* 如果叶子节点仍然不“纯”，那么怎么给他赋类别标签（以比较多的那类样本标签作为该节点的类别标签）
* 缺省属性的数据如何处理（随机森林中就包含着随机选择属性）

## 处理缺失属性

如果有些训练样本或者待分类样本缺失了一些属性值，那么该如何处理？要解决这个问题，需要考虑3个问题：

i)当开始决定选择哪个属性用来进行分支时，如果有些训练样本缺失了某些属性值时该怎么办？

ii)一个属性已被选择，那么在决定分支的时候如果有些样本缺失了该属性该如何处理？

iii)当决策树已经生成，但待分类的样本缺失了某些属性，这些属性该如何处理？针对这三个问题，昆兰提出了一系列解决的思路和方法。

**对于问题i)**,计算属性a的增益或者增益率时，如果有些样本没有属性a，那么可以有这么几种处理方式：

(I)**忽略这些缺失属性a的样本**。（这种适合于只含少量缺失值的情况）

(C)给缺失属性a的样本赋予属性a一个**均值或者最常用的值**。

(R)计算增益或者增益率时根据**缺失属性样本个数所占的比率**对**增益/增益率进行相应的“打折”**。

> **Gain**(**A**)**=**属性 A 在数据集中不空的比率 **×** ( **Entropy**(**S**)**−Entropy\_A**(**S**) )
>
> $$SplitE(A) = -\sum\_{i=1}^k \frac{|S\_i|}{|S|}log\_2\frac{|S\_i|}{|S|} - \frac{|S\_{unknow}|}{|S|}log\_2\frac{|S\_{unknow}|}{|S|}$$

(S)根据其他未知的属性想办法把这些样本缺失的属性补全。

**对于问题ii)**，当属性a已经被选择，该对样本进行分支的时候，如果有些样本缺失了属性a,那么：

(I)忽略这些样本。

(C)把这些样本的属性a赋予一个均值或者最常出现的值，然后再对他们进行处理。

(R)把这些属性缺失样本，按照具有属性a的样本**被划分成的子集样本个数的相对比率**，分配到各个子集中去。至于哪些缺失的样本被划分到子集1，哪些被划分到子集2，这个没有一定的准则，可以随机而动。

(A)把属性缺失样本**分配给所有的子集**，也就是说每个子集**都有**这些属性缺失样本。

(U)单独为属性缺失的样本划分一个分支子集。

(S)对于缺失属性a的样本，尝试着根据其他属性给他分配一个属性a的值，然后继续处理将其划分到相应的子集。

**对于问题iii)**，对于一个缺失属性a的待分类样本，有这么几种选择：

(U)如果有单独的缺失分支，依据此分支。

(c)把待分类的样本的属性a值**分配一个最常出现的a的属性值**，然后进行分支预测。

(S)根据其他属性为该待分类样本填充一个属性a值，然后进行分支处理。

(F)在决策树中属性a节点的分支上，遍历属性a节点的所有分支，探索可能所有的分类结果，然后把这些分类结果结合起来一起考虑，按照概率决定一个分类。

(H)待分类样本在到达属性a节点时就终止分类，然后根据此时a节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。

[C4.5决策树](http://blog.sina.com.cn/s/blog_68ffc7a40100urn3.html)

剪枝

## 处理连续值的属性

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F2b1ecf6d58f717061914846da00980155f2c11b3.png?generation=1589383924519238\&alt=media)

## ID3与C4.5

C4.5算法与ID3算法相似，但：

1. 能处理连续值的特征，对连续值进行离散化
2. 能够处理缺失值
3. 能剪枝
4. 生成节点过程中使用的是信息增益比来选择特征

**信息增益**：特征A对训练集D的信息增益$$g(D,A)$$,为集合D的经验熵$$H(D)$$与特征A给定条件下D的经验条件熵$$H(D|A)$$之差$$g(D,A) = H(D) - H(D|A)$$。

> 信息增益就是互信息$$I(X;Y) = H(X) - H(X|Y)$$

**信息增益比**：特征A对训练集D的信息增益$$g\_R(D,A)$$，为其信息增益$$g(D,A)$$与经验熵$$H(D)$$之比$$g\_R(D,A) = \frac {g(D,A)}{H(D)}$$。\
C4.5选择信息增益比，是因为信息增益值的大小受训练数据集经验熵影响。

![](https://2270971654-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7DcNFhVrwIk3Tks_pB%2Fsync%2F84ca77956eb2dad348cd20edd8dbb58201480efc.png?generation=1589383924582561\&alt=media)

## CART (Classification and regression tree 分类回归树）

ID3和C4.5只能做分类，而CART既可以处理分类，也可以处理回归。

CART算法采用一种二分递归分割的技术，与基于信息熵的算法不同，CART算法对每次样本集的划分计算GINI系数，**GINI系数可以衡量纯度，与熵有类似性质**，所以GINI系数越小则划分越合理。CART算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。

[如何理解决策树的损失函数?](https://github.com/json0071/svm/tree/1836843c016047720ba523156f66edf061a64a7d/%E5%A6%82%E4%BD%95%E7%90%86%E8%A7%A3%E5%86%B3%E7%AD%96%E6%A0%91%E7%9A%84%E6%8D%9F%E5%A4%B1%E5%87%BD%E6%95%B0?/README.md)

[Logistic Regression Vs Decision Trees Vs SVM](http://www.edvancer.in/logistic-regression-vs-decision-trees-vs-svm-part1/\)%20%20%0A\[WHY%20ARE%20WE%20GROWING%20DECISION%20TREES%20VIA%20ENTROPY%20INSTEAD%20OF%20THE%20CLASSIFICATION%20ERROR?]%28http://sebastianraschka.com/faq/docs/decisiontree-error-vs-entropy.html)

[Why are we growing decision trees via entropy instead of the classification error?](https://sebastianraschka.com/faq/docs/decisiontree-error-vs-entropy.html)

[分类算法：决策树（C4.5）](http://shiyanjun.cn/archives/428.html)

[数据挖掘十大经典算法--CART: 分类与回归树](http://blog.csdn.net/u011067360/article/details/24871801)

[如何解读决策树和随机森林的内部工作机制？](https://zhuanlan.zhihu.com/p/29622649)