机器学习-随机森林-2020-02-19

RECAP:

在决策树中，在一组数据中，根据每个特征的信息增益，决定应该如何来进行CRT的树枝分叉。在是否贷款的case中，以"是否有房"， "是否有工作" 作为第一轮和第二轮的特征，进行分叉。而进行到full decision tree的时候，发现“年龄”，“信贷情况”，并没有用的上，这两个特征是冗余的特征。

那么，如何将bagging和decision tree进行结合呢？

Random Forest

Random Forest 就是将多个decision tree 进行bagging的组合。需要解决2个问题：

1. 资料从哪来

2. 特征从哪来

第一个问题，之前已经有bootstrapping。采用抽取放回的方式进行资料的抽取。在一组原始资料里，有大约1/e，约1/3的资料取不到。

第二个问题，还是采用bootstrapping的方式，每次对特征进行随机选取。

这样，每组资料和特征都不完全相同，每组资料和特征都可以进行decision tree的计算，这些decision tree都可以并行进行，提高了效率。计算完成后，都可以得到一棵full decision tree，然后按照bagging的方式，进行uniform的结合，得到第一次迭代的Random Forest。

OOB的方式进行self-validation

由于在N笔资料中进行bootstrapping，对于抽取到的资料，可以进行training，未抽取到的资料（OOB），进行validation。在进行validation的时候，关心的是Gt而非gt。因此需要用OOB的资料对Gt进行Validation。怎么做？

1. 找出每个Random Forest对应的OOB资料

2. 计算一个decision tree的OOB。例如（x1,y1）可以对g2进行validation；（xn,yn）可以对g2,g3,gT进行validation. 那么记做：

$G^-_1=avg(g2);$

$G^-_N=avg(g2,g3,gT);$

这种做法我们并不陌生，就像是我们之前介绍过的Leave-One-Out Cross Validation，每次只对一个样本进行g−的验证一样，只不过这里选择的是每个样本是哪些gt的OOB，然后再分别进行Gn−(x)的验证。每个样本都当成验证资料一次（与留一法相同），最后计算所有样本的平均表现：

$E_{oob}(G)=\frac{1}{N} \sum err(y_n, G^-_n(x_n))$

Eoob(G)估算的就是G的表现好坏。我们把 Eoob称为bagging或者Random Forest的self-validation。 self-validation在调整随机森林算法相关系数并得到最小的 Eoob之后，就完成了整个模型的建立，无需重新训练模型。随机森林算法中，self-validation在衡量G的表现上通常相当准确。

机器学习：随机森林RF-OOB袋外错误率

https://blog.csdn.net/wishchin/article/details/52515516

Feature selection

例如decision tree的例子中，“年龄”，“信贷情况”，并没有用的上，这两个特征是冗余的特征。那么如何在d个特征中找出 $\tilde{d}$ 个特征呢？

1. 线性关系 $y=\sum wixi$ 中，使用 |w|来表示特征的重要性。重要性大的，w的绝对值就大

2. 在非线性关系，例如random forest中，使用Permutation Test来衡量特征的重要性

RF中，特征选择的核心思想是random test。random test的做法是对于某个特征，如果用另外一个随机值替代它之后的表现比之前更差，则表明该特征比较重要，所占的权重应该较大，不能用一个随机值替代。相反，如果随机值替代后的表现没有太大差别，则表明该特征不那么重要，可有可无。所以，通过比较某特征被随机值替代前后的表现，就能推断出该特征的权重和重要性。

那么random test中的随机值如何选择呢？通常有两种方法：一是使用uniform或者Gaussian抽取随机值替换原特征；一是通过permutation的方式将原来的所有N个样本的第i个特征值重新打乱分布（相当于重新洗牌）。比较而言，第二种方法更加科学，保证了特征替代值与原特征的分布是近似的（只是重新洗牌而已）。这种方法叫做permutation test（随机排序测试），即在计算第i个特征的重要性的时候，将N个样本的第i个特征重新洗牌，然后比较D和D^{(p)}表现的差异性。如果差异很大，则表明第i个特征是重要的。

知道了permutation test的原理后，接下来要考虑的问题是如何衡量上图中的performance，即替换前后的表现。显然，我们前面介绍过performance可以用Eoob(G)来衡量。但是，对于N个样本的第i个特征值重新洗牌重置的D(p)，要对它进行重新训练，而且每个特征都要重复训练，然后再与原D的表现进行比较，过程非常繁琐。为了简化运算，RF的作者提出了一种方法，就是把permutation的操作从原来的training上移到了OOB validation上去，记为

也就是说，在训练的时候仍然使用D，但是在OOB验证的时候，将所有的OOB样本的第i个特征重新洗牌，验证G的表现。这种做法大大简化了计算复杂度，在RF的feature selection中应用广泛。

Permutation Test 置换检验(转）

https://blog.csdn.net/u011467621/article/details/47971917

机器学习-随机森林-2020-02-19