1 决策树的过拟合问题

1.1 问题描述

决策树对训练属于有很好的分类能力，但是对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。

1.2 解决方法

（1）剪枝

 

 

（2）合理有效抽样

bagging:

 OOB数据

 随机森林

• 随机森林/Bagging与决策树的关系

决策树是基础分类器；

SVM、Logistic回归等其他分类器组成“总分类器”，叫做随机森林。 

举例：回归问题

2 回归

2.1 算法过程

做100次bootstrap，每次得到的数据Di（Di的长度为N）。对于每个Di，使用局部回归（LOESS）拟合成一条曲线。然后将这些曲线取平均，得到最终的最终拟合曲线，该曲线过拟合情况是减弱的。

2.2 举例

投票：（1）简单投票机制：一票否决、少数服从多数、阈值表决（2）贝叶斯投票机制

电影评价：使得尽可能大。

 

3 随机森林的用途

3.1 使用随机森林计算样本间相似度

原理：若两样本同时出现在相同叶结点的次数越多，则两者越相似。

算法过程：记样本个数为N，初始化NXN的零矩阵S，S[i,j]表示样本i和j的相似度。对于m棵决策树形成的随机森林，遍历所有决策树的所有叶子结点（样本i,j出现在相同的结点，则s[i,j]加1）。遍历结束，S为样本间相似度矩阵。

3.2 使用随机森林计算特征重要性

（1）计算正例经过的结点，使用经过结点的数目、gini系数和等指标来判断特征的重要性。

（2）随机替换一列数据，重新建立决策树，计算新模型的正确率变化来判断这一列的特征的重要性。

3.3 孤立森林

孤立森林（Isolation Forest）通过对样本点的孤立来检测异常值。

特征、分割点都随机选择，然后生成一定深度的决策树iTree，若干棵iTree组成iForest。

先计算iTree中样本从根到叶子的长度f(x)，然后计算iForest中f(x)的总和F(x)。

检测标准：F(x)较小的样本x为异常值。

总结

决策树/随机森林的代码清晰、逻辑简单，在胜任分类问题的同时，往往也可以作为对数据分布探索的首要尝试算法。

随机森林的集成思想也可用在其他分类器的设计中。