机器学习总结（lecture 15）算法：随机森林Random Forest（RF）_随机森林loss函数

lecture 15：随机森林Random Forest

目录

1Bagging与Boosting的区别

随机森林属于集成学习（Ensemble Learning）中的bagging算法。
在集成学习中，主要分为bagging算法和boosting算法。

我们先看看这两种方法的特点和区别：

Bagging（套袋法）

bagging的算法过程如下：

1、从原始样本集中使用Bootstraping方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集。（k个训练集之间相互独立，元素可以有重复）
2、对于k个训练集，我们训练k个模型（这k个模型可以根据具体问题而定，比如决策树，knn等）
3、对于分类问题：由投票表决产生分类结果；
对于回归问题：由k个模型预测结果的均值作为最后预测结果。（所有模型的重要性相同）

Boosting（提升法）

boosting的算法过程如下：

1、对于训练集中的每个样本建立权值wi，表示对每个样本的关注度。当某个样本被误分类的概率很高时，需要加大对该样本的权值。
2、进行迭代的过程中，每一步迭代都是一个弱分类器。我们需要用某种策略将其组合，作为最终模型。
（例如AdaBoost给每个弱分类器一个权值，将其线性组合最为最终分类器。误差越小的弱分类器，权值越大）

Bagging，Boosting的主要区别

1、样本选择上：
Bagging采用的是Bootstrap随机有放回抽样；
而Boosting每一轮的训练集是不变的，改变的只是每一个样本的权重。

2、样本权重：
Bagging使用的是均匀取样，每个样本权重相等；
Boosting根据错误率调整样本权重，错误率越大的样本权重越大。

3、预测函数：
Bagging所有的预测函数的权重相等；
Boosting中误差越小的预测函数其权重越大。

4、并行计算：
Bagging各个预测函数可以并行生成；
Boosting各个预测函数必须按顺序迭代生成。

下面是将决策树与这些算法框架进行结合所得到的新的算法：

• 1）Bagging + 决策树 = 随机森林 RF
• 2）AdaBoost + 决策树 = 提升树
• 3）Gradient Boosting + 决策树 = GBDT

2决策树

常用的决策树算法有ID3，C4.5，CART三种。

3种算法的模型构建思想都十分类似，只是采用了不同的指标。决策树模型的构建过程大致如下：

ID3，C4.5决策树的生成

输入：训练集D，特征集A，阈值eps 输出：决策树T

1、若D中所有样本属于同一类Ck，则T为单节点树，将类Ck作为该结点的类标记，返回T
2、若A为空集，即没有特征作为划分依据，则T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T
3、否则，计算A中各特征对D的信息增益(ID3)/信息增益比(C4.5)，选择信息增益最大的特征Ag
4、若Ag的信息增益（比）小于阈值eps，则置T为单节点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T
5、否则，依照特征Ag将D划分为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由结点及其子节点构成树T，返回T
6、对第i个子节点，以Di为训练集，以A-{Ag}为特征集，递归地调用1~5，得到子树Ti，返回Ti

CART决策树的生成

这里只简单介绍下CART与ID3和C4.5的区别。

1、CART树是二叉树，而ID3和C4.5可以是多叉树
2、CART在生成子树时，是选择一个特征一个取值作为切分点，生成两个子树
选择特征和切分点的依据是基尼指数，选择基尼指数最小的特征及切分点生成子树

决策树的剪枝

决策树的剪枝主要是为了预防过拟合，过程就不详细介绍了。

主要思路是从叶节点向上回溯，尝试对某个节点进行剪枝，比较剪枝前后的决策树的损失函数值。最后我们通过动态规划（树形dp，acmer应该懂）就可以得到全局最优的剪枝方案。

3随机森林

随机森林是一种重要的基于Bagging的集成学习方法，可以用来做分类、回归等问题。

随机森林有许多优点：

• 具有极高的准确率
  随机性的引入，使得随机森林不容易过拟合
  随机性的引入，使得随机森林有很好的抗噪声能力
  能处理很高维度的数据，并且不用做特征选择
  既能处理离散型数据，也能处理连续型数据，数据集无需规范化
  训练速度快，可以得到变量重要性排序
  容易实现并行化

随机森林的缺点：

• 当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大
  随机森林模型还有许多不好解释的地方，有点算个黑盒模型

与上面介绍的Bagging过程相似，随机森林的构建过程大致如下：

1、从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集

2、对于n_tree个训练集，我们分别训练n_tree个决策树模型

3、对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂

4、每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝

5、将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果

4随机森林算法

理解了bagging算法，随机森林(Random Forest,以下简称RF)就好理解了。它是Bagging算法的进化版，也就是说，它的思想仍然是bagging,但是进行了独有的改进。我们现在就来看看RF算法改进了什么。　　　

• 首先，RF使用了CART决策树作为弱学习器，让我们想到了梯度提升树GBDT。
• 第二，在使用决策树的基础上，RF对决策树的建立做了改进，对于普通的决策树，我们会在节点上所有的n个样本特征中选择一个最优的特征来做决策树的左右子树划分，但是RF通过随机选择节点上的一部分样本特征，这个数字小于n，假设为$n_{sub}$
• 然后在这些随机选择的nsub个样本特征中，选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。　　　　
• 如果nsub=n，则此时RF的CART决策树和普通的CART决策树没有区别
• nsub越小，则模型约健壮，当然此时对于训练集的拟合程度会变差。也就是说nsub越小，模型的方差会减小，但是偏倚会增大。
• 在实际案例中，一般会通过交叉验证调参获取一个合适的nsub的值。

1）对于t=1,2…,T:

• a)对训练集进行第t次随机采样，共采集m次，得到包含m个样本的采样集Dm
• b)用采样集Dm训练第m个决策树模型Gm(x)，在训练决策树模型的节点的时候， 在节点上所有的样本特征中选择一部分样本特征， 在这些随机选择的部分样本特征中选择一个最优的特征来做决策树的左右子树划分

2) 如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。
如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

5随机森林的推广

参考博客：https://www.cnblogs.com/pinard/p/6156009.html

由于RF在实际应用中的良好特性，基于RF，有很多变种算法，应用也很广泛，不光可以用于分类回归，还可以用于特征转换，异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。

• 1、extra trees
  是RF的一个变种, 原理几乎和RF一模一样，仅有区别有：
  　　　　1） 对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。
  　　　　2） 在选定了划分特征后，RF的决策树会基于信息增益，基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。
  　　　　从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是偏倚相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好。
• 2、Totally Random Trees Embedding(以下简称 TRTE)
  是一种非监督学习的数据转化方法。它将低维的数据集映射到高维，从而让映射到高维的数据更好的运用于分类回归模型。我们知道，在支持向量机中运用了核方法来将低维的数据集映射到高维，此处TRTE提供了另外一种方法。
• 3、Isolation Forest（以下简称IForest）
  是一种异常点检测的方法。它也使用了类似于RF的方法来检测异常点

6总结

　　　RF的算法原理也终于讲完了，作为一个可以高度并行化的算法，RF在大数据时候大有可为。 这里也对常规的随机森林算法的优缺点做一个总结。

RF的主要优点有：

　　　　1） 训练可以高度并行化，对于大数据时代的大样本训练速度有优势。个人觉得这是的最主要的优点。

　　　　2） 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。

　　　　3） 在训练后，可以给出各个特征对于输出的重要性

　　　　4） 由于采用了随机采样，训练出的模型的方差小，泛化能力强。

　　　　5） 相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。

　　　　6） 对部分特征缺失不敏感。

RF的主要缺点有：

　　　　1）在某些噪音比较大的样本集上，RF模型容易陷入过拟合。

　　　　2) 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。

7sk-learn中的随机森林算法

• sklearn.ensemble模块中包含两种基于随机决策树的平均算法：随机森林算法和ExtraTrees的方法。

这两种算法都是专为决策树设计的包含混合扰动技术的算法。这意味着分类器依赖着引入随机性来进行建模。整体的预测结果，来自各个独立分类器的综合平均预测结果。

• 原理：随机森林，顾名思义，就是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是独立没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类，然后看看哪一类被选择最多，就预测这个样本为那一类。

from sklearn.ensemble import RandomForestClassifier  
X = [[0, 0], [1, 1]]  
Y = [0, 1]  
clf = RandomForestClassifier(n_estimators=10)  
clf = clf.fit(X, Y)
1
2
3
4
5
6

• ET或Extra-Trees（Extremely randomized trees，极端随机树）是由PierreGeurts等人于2006年提出。该算法与随机森林算法十分相似，都是由许多决策树构成。但该算法与随机森林有两点主要的区别：

1、随机森林应用的是Bagging模型，而ET是使用所有的训练样本得到每棵决策树，也就是每棵决策树应用的是相同的全部训练样本；

2、随机森林是在一个随机子集内得到最佳分叉属性，而ET是完全随机的得到分叉值，从而实现对决策树进行分叉的。

from sklearn.datasets import make_blobs  
from sklearn.ensemble import RandomForestClassifier  
from sklearn.ensemble import ExtraTreesClassifier  
from sklearn.tree import DecisionTreeClassifier  
from sklearn.model_selection import cross_val_score  

#在这里我们先引入一些训练数据集   
X, y = make_blobs(n_samples=10000, n_features=10, centers=100, random_state=0)  

#定义一个决策树分类器 
clf = DecisionTreeClassifier(max_depth=None, min_samples_split=2, random_state=0)  
scores = cross_val_score(clf, X, y)  
print(scores.mean())                      

#定义一个随机森林分类器
clf = RandomForestClassifier(n_estimators=10, max_depth=None, min_samples_split=2, random_state=0)  
scores = cross_val_score(clf, X, y)  
print(scores.mean())        

#定义一个极端森林分类器
clf = ExtraTreesClassifier(n_estimators=10, max_depth=None, min_samples_split=2, random_state=0)    
scores = cross_val_score(clf, X, y)  
print(scores.mean())#这里是极端森林训练器的模型精确度得分，效果优于随机森林  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

0.979408793821
0.999607843137
0.999898989899