Machine Learning Techniques Lecture 10: Random Forest | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 10: Random Forest


 
 

内容:

Random forest,演算法就是做bagging,然后在bagging里面做decision tree,为了让decision tree更加随机一点,通常会做randomly projected subspaces,就是随机的选择features下刀。在这样的模型里面,因为采用了bagging,可以得到Out-of-bag(OOB)结果,用来代替validation达到self-validation的效果。有了这个机制,配合premutation test(采用随机排序的特征)来测试每一个特征到底是不是你需要的,其重要性。最后图示该算法的表现。

 
 


 
 

上一讲:

决策树模型,演算法的核心是想办法通过递归的方式切割资料,切割资料的标准就是希望你的资料越纯越好。切开后就得到conditional aggregation的效果,就是根据不同的情况使用不同的小g,就是树叶。

 
 

这一讲:

随机森林

 
 


 
 

先来复习一下两个机器学习模型

 
 

Bagging:通过bootstraooing的方式得到不一样的资料,然后把这些不一样的资料送到base算法里面得到不同的小g,最后让这些不同的小g来投票得到结果。

特点是:小g的变化越大,bagging降低variance的效果越明显。

 
 

Decision Tree:拿到资料后想办法建立一棵树,通过递归的方式利用条件分割资料得到g,分割的依据是资料的纯度。

依据是:variance很大,资料稍微变一点点得到的树可能就差很多。

 
 

两者结合是不是能取长补短呢?

 
 


 
 

Random forest:random(Bagging过程里面的随机性) + forest(Baggin下面的hypothesis是由fully-grown C&RT decision tree得到)

 
 

基本算法:

每一轮的时候想办法用bootstripting的方式得到不同的资料,然后送到完全长成的Decision Tree里面得到g,然后把结果公平的投票得到大G。

 
 

优点:

Bagging的过程用以并行计算,各个独立资料运算无依赖;decision tree的过程也是很有效率;因此整个过程就是很有效率的。

C&RT这个算法有很多好处,可以处理missing feature,multi-class等(见上一课),random算法继承这些好处。

C&RT的问题在于对于资料太敏感,容易overfit,这里通过bagging来缓和这个问题。

 
 


 
 

如何让random forest做的更好。(优化:到处充满随机)

 
 

  1. Bagging + random-subspace C&RT

基本的方法通过bootstript在原来数据里面抽样来得到资料算出小g;这里我们除了在资料端做抽取,还能在feature端做抽取,这个可以看作是特征转换,将原来的高纬度特征投影到低维度空间里面,例如原来有100个特征,每轮随机选择10个特征来处理。这样可以得到更不一样的树。

 
 


 
 

  1. Bagging + random-combination C&RT tree

就是在特征投影的基础上,再选择feature数量也是随机的,而不是使用全部。例如有100个特征,选三个合起来算一个加权的分数再在上面做切割,下一次选五个再在上面做切割,也就是投影的时候不是每次把100个都投影进去。

 
 


 
 

练习

 
 


 
 

Random forest 里面的核心就是 bagging bootstript,这里再来看看 bootstript这个机制告诉了些什么东西给我们。这个机制就是通过在原始资料库里面有放回的随机抽取资料,用来学得小g。把这个随机的结果列成表就如上面所示,在算某个g的时候资料选到就标蓝色,没有就是红色,某个资料从来没被选到过就是 out-of-bag(OOB) data,我们来看看这些资料的奥秘。

 
 


 
 

到底有多少out-of-bag的资料?


假设一共有N笔资料,没被选到的资料数量是N’,如果你抽了N轮的话,一笔资料从没被选到的概率是(1 – 1/N)^N,如果N很大的话可以约等于1/e,也就是差不多1/3左右。

 
 


 
 

Validation的时候:我们把所有的资料切成两个部分,训练资料和验证资料,用验证资料来衡量g的表现,然后选择最好的。验证资料可以这么做的理由是其没有参与训练。

 
 

OOB 资料的特性:对照validation,红色部分没有参与训练,那么就可以用来做validation类似的事情。所以我们可以采用OOB来做g的好坏的验证,但是RT方法的目的是得到G而不是好的小g,这个做法不需要。我们需要的是对G的验证。

 
 

做法:

对于(Xn, Yn),可以当作是g2-gT(G_n^-)这些的validation的资料,但是不能当作g1的validation的资料。每一行都有一个G_n^-。

E_oob(G) = avg(Err(yn, G_N^-(xn))):每一笔资料X_n做出G_n^-来,然后根据yn看看表现就是err,最后把所有的做平均。估算的是G到的表现的是好还是不好。

 
 

通过 E_oob,对于bagging/Random forest来说训练完就可以马上知道G到底好不好。

 
 


 
 

Validation:训练的资料D_train通过算法A得到结果,再比较验证看结果是否正确来得到E_m。

 
 

RF:通过得到资料D的random forest,然后就可以自验证得到 E_oob 来衡量G到底好不好。而且不存在re-training。E_oob衡量G的表现通常相当准确。

 
 


 
 

练习

 
 


 
 

假设你的资料的特征维度是很高的,比如10000个维度,这时候你就比较想减低资料的维度。

  1. 把冗余的特征移掉。(比如年龄和生日两个特征)
  2. 把和你的目标无关的特征移掉。(比如病人的保险状况和是否癌症的判断无关)

 
 

好处:可以看作是对杂讯的排除,不容易overfit,结果会比较好;后续的训练测试效率更高。

缺点:降维度可能在计算上就需要花费很多力气;降维没做好的话就很容易overfit。

 
 

决策树的算法过程本身就包含特征选择的过程,每一步你用什么特征来切分就是。

 
 


 
 

Feature selection 是一个组合爆炸的问题,解决这个问题的一个方法是:把feature根据重要性排序,然后取前n重要的就好了,这种方式在线性模型里面最好用,因为权重决定了影响力。对于非线性模型要理清特征的权重就比较困难,random forest就是非线性模型,但是因为其具有的一些特征使得做特征选择相对比较容易。

 
 


 
 

基本想法:random test

若你现在在做学习,那么对于某一个你认为很重要的特征,加入一些随机杂讯后,你学习就比较困难,但因为重要所以你一定要学会他,花比较长时间。也就是很说你只要比对学习特征的时间和学习加入杂讯后特征的时间的差值,越大说明越重要。

 
 

塞什么杂讯进去?

  1. 平均、随机、高斯分布,这些会影响到目标分布,这一点RF是敏感的,不好
  2. Bootstrip(permutation)方式,目标分布是没有变化的,比较好

 
 

Permutation test:比较我原来的表现和permutation方式做过的资料后的表现的差值。

整体做法就是每一次用permutation方式对第i个维度污染一下,计算一下差值。

 
 


 
 

最后我们怎么来衡量这些performance(i):

 
 

Performance(D):拿这些重新排列的资料来重新做一次训练,得到G然后再做validation来验证,就是使用OOB得到结果 E_oob(G)。

Performance(D^p):对应上面的结果应该是 E_oob(G^p),约等于 E_oob^p(G),这样就可以保持G不变不用再re-train一遍,而是在验证的时候动手脚,验证的时候采用p变化后的资料来算错误率。

 
 

所以:

RF 的特征选择是通过 permutation(随机排序) + OOB(错误衡量) 来得到特征的重要性,然后就选出了重要特征。

这种方式做特征选择非常好用,实际上遇到非线性特征选择的时候常用。

 
 


 
 

练习

 
 


 
 

最后是一个例子

 
 

一棵树

  1. Random combination:把特征随机的集合起来再切分,看上去就是可一切斜的刀。
  2. 粗的标起来的就是bootstript选到的,其他的没选到。

 
 


 
 

T = 100 就是100棵树,最右边的边界已经很复杂了。

 
 


 
 

200棵树,最右边更平滑

 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 

对比1000棵树和1棵树

 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 


 
 

投票机制会消除一定的杂讯,让边界平滑。

 
 


 
 

RF的缺点:随机相关,对于变化敏感,因此需要大量的树来尽量减少random对结果的影响。

 
 

树的棵树越多越好,理论上无限多棵最好,实际应用的时候看你的G是否稳定,如果树的数量增加很多G稳定的时候就差不多了。

 
 


 
 

练习

 
 


 
 

总结:

Random forest,演算法就是做bagging,然后在bagging里面做decision tree,为了让decision tree更加随机一点,通常会做randomly projected subspaces,就是随机的选择features下刀。在这样的模型里面,因为采用了bagging,可以得到Out-of-bag(OOB)结果,用来代替validation达到self-validation的效果。有了这个机制,配合premutation test(采用随机排序的特征)来测试每一个特征到底是不是你需要的,其重要性。最后图示该算法的表现。

 
 

下一讲:

这里讲完了random forest,是bagging和decision tree的结合,下面讲boosted decision tree,就是adaboost和decision tree的结合,以及延伸到不只是classification的情况下的使用。


2 Comments

Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags