Kaggle 快速模型之 Random Forrest 随机森林

1. Kaggle 快速模型之 Random Forrest 随机森林

随机森林 RF 在 Kaggle 大名远播，称霸很久。
  
 那么，我们这里就先聊聊 原因 。以下分析来自 University of San Francisco, CS 硕士课程。 
  
 随机森林（文中记为 RF）有以下 5 个优点：
  
  1。用法 ：RF 支持针对连续对象的回归算法，也支持针对离散对象的分类算法。
  
  2。过拟合 ：RF 不太容易过拟合，因为 RF 本质上是模型集成（model ensemble），从  Leo Breiman 的理论来看 RF 也不会因为 树 数量的增加，而导致过拟合，因为这些数都是集合在一起的单独模型，效果不好的树会被 downvote。但是使用 out of bagging 的方法是推荐来帮助 RF 减少过拟合的方法，就是保留一个 validation 数据集在多个模型中选取评价指标更好的模型。
  
  3。范化能力 ：RF 的范化能力也比较好，比较能够处理异常值，不太容易出现波动。
  
  4。数据分布要求 ：不像线性模型，RF 也不要求数据分布符合正态分布，来得到统计结果上的近似。因此任意的数据分布都可以使用 RF。
  
  5。特征工程 ：对于一些简单的线性模型，为了增加特征，我们往往需要增加   这样的特征来作为模型的输入，帮助模型构建更多的特征。但是在 RF 中，这些基础的特征工程是不必要的。但是，需要记得，额高阶特征工程可以帮助增加 RF 的精度（类似日期上的处理，提取出月份，周数等）。
  
  6。数据预处理 ：类似神经网络需要对数据作预处理来得到 0 ～ 1 之间的数据分布，在 RF 这里往往都不太需要，因此 RF 对于数据的要求也不高。
  
 讲完了 RF 的特性之后，我们似乎发现 RF 是万能，但是他真的这么万能麻？我们再来看看 机器学习届广为流传的两个理论，在 RF 上是不是也会存在。
  
  a。高维诅咒 ：这个理论是说随着数据纬度的增加，即数据特征的增加，所有的数据都会十分的分散，使得计算数据点之间的距离变得没有意义，也就是说模型的预测变得不可能实现。当然理论上的确是可以如此证明，这个理论在数学上完全没有问题。但是到了实际的世界上，我们的所有数据其实互相之间是存在依赖的，因此你会发现，这个高维距离始终有意义，并且真实地提供模型预测。
  
  b。无免费的午餐理论 ：这个理论名字就很明显，没有一个模型可以适用于各种数据。当然，从数学理论上可以验证这个结论。但是在实际的工作中，RF 是相对比较全面的一个模型，我们总是可以用他先作出一个 benchmark ，再来优化。尤其是 Kaggle 等赛事上，对模型的精度要求十分明确，我们无需在数据的其他层面上（如收集、确认等）作任何的工作。RF 是很适合开始的模型。
  
 那下节内容，我们就可以说说理论以外的操作了。

2. 基于树模型的集成算法---Random Forest

  随机森林是一种由决策树构成的集成算法. 随机森林属于集成学习中的 Bagging. 用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。 在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。
   相较于一般的决策树, RF 中存在了对特征的子采样,增强了模型的随机性,虽然这增加了偏差,但是是同时因为集成效果,降低了方差,因而这通常在整体上会获得一个更好的模型。
   除了普通版本的随机森林以外,我们还可以通过使用极限随机树来构建极限随机森林,极限随机树与普通随机森林的随机树的区别在于,前者在划分属性的时候并非选取最优属性,而是随机选取(sklearn中的实现方式是,对每个属性生成随机阈值,然后在随即阈值中选择最佳阈值)
   sklearn 中还实现了随机森林的一种特殊用法, 即完全随机树嵌入(RandomTreesEmbedding) 。RandomTreesEmbedding 实现了一个无监督的数据转换。 通过由完全随机树构成的森林，RandomTreesEmbedding 使用数据最终归属的叶子节点的索引值（编号）对数据进行编码。 该索引以 one-of-K 方式编码，最终形成一个高维的稀疏二进制编码。 这种编码可以被非常高效地计算出来，并且可以作为其他学习任务的基础。 编码的大小和稀疏度可以通过选择树的数量和每棵树的最大深度来确定。
   如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；
   如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是"有偏的"，都是"片面的"，也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是"盲人摸象"。
   随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。在构建每棵树时，我们对训练集使用了不同的 bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第 k 棵树的oob样本。
    sklearn 中的随机森林: 
    重要参数: 
   n_estimators 是森林里树的数量，通常数量越大，效果越好，但是计算时间也会随之增加。 此外要注意，当树的数量超过一个临界值之后，算法的效果并不会很显著地变好。
   max_features 是分割节点时考虑的特征的随机子集的大小。 这个值越低，方差减小得越多，但是偏差的增大也越多。 根据经验，回归问题中使用 max_features = n_features， 分类问题使用max_features = sqrt（n_features （其中 n_features 是特征的个数）是比较好的默认值。
   max_depth = None 和 min_samples_split = 2 结合通常会有不错的效果（即生成完全的树）。 这些（默认）值通常不是最佳的，同时还可能消耗大量的内存，最佳参数值应由交叉验证获得。 另外，请注意，在随机森林中，默认使用自助采样法（bootstrap = True）， 当使用自助采样法方法抽样时，泛化精度是可以通过剩余的或者袋外的样本来估算的，设置 oob_score = True 即可实现。
   oob_score 误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。
    重要方法: 
    随机森林的应用方向: 

3. 随机森林算法梳理

 全称Bootstrap Aggregation的集成算法。每个基学习器都会对训练集进行 有放回抽样得到子训练集 ，比较著名的采样法为 0.632 自助法。每个基学习器 基于不同子训练集进行训练，并综合所有基学习器的预测值得到最终的预测结果 。 Bagging 常用的综合方法是投票法，票数最多的类别为预测类别 。
                                           Boosting 训练过程为阶梯状， 基模型的训练是有顺序的，每个基模型都会在前一个基模型学习的基础上进行学习，最终综合所有基模型的预测值产生最终的预测结果，用的比较多的综合方式为加权法 。   
                                           
   Stacking 是 先用全部数据训练好基模型，然后每个基模型都对每个训练样本进行的预测，其预测值将作为训练样本的特征值，最终会得到新的训练样本，然后基于新的训练样本进行训练得到模型，然后得到最终预测结果。    
                                           
   那么，为什么集成学习会好于单个学习器呢？原因可能有三：
   训练样本可能无法选择出最好的单个学习器，由于没法选择出最好的学习器，所以干脆结合起来一起用；   假设能找到最好的学习器，但由于算法运算的限制无法找到最优解，只能找到次优解，采用集成学习可以弥补算法的不足；   可能算法无法得到最优解，而集成学习能够得到近似解。比如说最优解是一条对角线，而单个决策树得到的结果只能是平行于坐标轴的，但是集成学习可以去拟合这条对角线。
   不是所有集成学习框架中的基模型都是弱模型。Bagging 和 Stacking 中的基模型为强模型（偏差低，方差高），而Boosting 中的基模型为弱模型（偏差高，方差低）。
                                           对于 Bagging 来说，每个基模型的权重等于 1/m 且期望近似相等，故我们可以得到：
                                           通过上式我们可以看到：
   在此我们知道了为什么 Bagging 中的基模型一定要为强模型，如果 Bagging 使用弱模型则会导致整体模型的偏差提高，而准确度降低。Random Forest 是经典的基于 Bagging 框架的模型，并在此基础上通过引入特征采样和样本采样来降低基模型间的相关性，在公式中显著降低方差公式中的第二项，略微升高第一项，从而使得整体降低模型整体方差。
   对于 Boosting 来说，由于基模型共用同一套训练集，所以基模型间具有强相关性，故模型间的相关系数近似等于 1，针对 Boosting 化简公式为：
                                           通过观察整体方差的表达式我们容易发现：
   基于 Boosting 框架的 Gradient Boosting Decision Tree 模型中基模型也为树模型，同 Random Forrest，我们也可以对特征进行随机抽样来使基模型间的相关性降低，从而达到减少方差的效果。
   ️那么这里有一个小小的疑问，Bagging 和 Boosting 到底用的是什么模型呢？
   随机森林就是通过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于集成学习方法。随机森林的名称中有两个关键词，一个是“随机”，一个就是“森林”。“森林”我们很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，这也是随机森林的主要思想--集成思想的体现。然而，bagging的代价是不用单棵决策树来做预测，具体哪个变量起到重要作用变得未知，所以bagging改进了预测准确率但损失了解释性。
   “森林”容易理解，就是由很多“树”组成，那么“随机”体现在什么方面呢？
   （1）训练集随机的选取：如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；这样保证了每颗树的训练集都不同，从而构建的树也不同
   （2）特征的随机选取：从M个特征中选取m个特征，这样可以避免某个特征与分类结果具有强相关性，如果所有特征都选取，那么所有的树都会很相似，那样就不够“随机”了
   另外还有一点，随机森林法构建树的时候不需要做额外的剪枝操作。个人理解：因为前两个“随机”操作，以及多颗树的建立，已经避免了过拟合现象，所以这种情况下，我们只需要让每棵树在它自己的领域内做到最好就可以了。
   随机森林算法的预测性能与两个因素有关：
   （1）森林中任意两棵树的相关性，相关性越强，则总体性能越容易差
   （2）森林中每棵树的预测性能，每棵树越好，则总体性能越好
   其实可以理解为要求“好而不同”。然而特征数m的选择越大，则相关性与个体性能都比较好，特征数m选择越小，则相关性与个体性能都更小，所以m的选择影响着随机森林的预测性能。
   在包括N个样本的数据集中，采用有放回的抽样方式选择N个样本，构成中间数据集，然后在这个中间数据集的所有特征中随机选择几个特征，作为最终的数据集。以上述方式构建多个数据集；一般回归问题选用全部特征，分类问题选择全部特征个数的平方根个特征
   利用CART为每个数据集建立一个完全分裂、没有经过剪枝的决策树，最终得到多棵CART决策树；
   根据得到的每一个决策树的结果来计算新数据的预测值。
   由于RF在实际应用中的良好特性，基于RF，有很多变种算法，应用也很广泛，不光可以用于分类回归，还可以用于特征转换，异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。
   extra trees是RF的一个变种, 原理几乎和RF一模一样，有区别有：
   对于每个决策树的训练集，RF采用的是 随机采样bootstrap来选择采样集作为每个决策树的训练集 ，而extra trees一般不采用随机采样，即 每个决策树采用原始训练集。 
   在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。
   从第二点可以看出， 由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。   也就是说，模型的方差相对于RF进一步减少，但是偏倚相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好。 
   Totally Random Trees Embedding(以下简称 TRTE)是一种 非监督学习的数据转化方法。它将低维的数据集映射到高维 ，从而让映射到高维的数据更好的运用于分类回归模型。我们知道，在支持向量机中运用了核方法来将低维的数据集映射到高维，此处TRTE提供了另外一种方法。
   TRTE在数据转化的过程也使用了类似于RF的方法，建立T个决策树来拟合数据。当决策树建立完毕以后，数据集里的每个数据在T个决策树中叶子节点的位置也定下来了。比如我们有3颗决策树，每个决策树有5个叶子节点，某个数据特征x划分到第一个决策树的第2个叶子节点，第二个决策树的第3个叶子节点，第三个决策树的第5个叶子节点。则x映射后的特征编码为(0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,1), 有15维的高维特征。这里特征维度之间加上空格是为了强调三颗决策树各自的子编码。
   映射到高维特征后，可以继续使用监督学习的各种分类回归算法了。
   Isolation Forest（以下简称IForest）是一种 异常点检测的方法。 它也使用了类似于RF的方法来检测异常点。
   对于在T个决策树的样本集，IForest也会对训练集进行随机采样,但是采样个数不需要和RF一样，对于RF，需要采样到采样集样本个数等于训练集个数。但是IForest不需要采样这么多，一般来说，采样个数要远远小于训练集个数？为什么呢？因为我们的目的是异常点检测，只需要部分的样本我们一般就可以将异常点区别出来了。
   对于每一个决策树的建立， IForest采用随机选择一个划分特征，对划分特征随机选择一个划分阈值。这点也和RF不同。
   另外，IForest一般会选择一个比较小的最大决策树深度max_depth,原因同样本采集，用少量的异常点检测一般不需要这么大规模的决策树。
   对于异常点的判断，则是将测试样本点x拟合到T颗决策树。计算在每颗决策树上该样本的叶子节点的深度ht(x),从而可以计算出平均高度h(x)。此时我们用下面的公式计算样本点x的异常概率:
     
   其中，m为样本个数。c(m)的表达式为：
     
   s(x,m)的取值范围是[0,1],取值越接近于1，则是异常点的概率也越大。
   RF的主要优点有：   训练可以 高度并行化 ，对于大数据时代的大样本训练速度有优势。
   由于可以随机选择决策树节点划分特征，这样在 样本特征维度很高的时候，仍然能高效的训练模型。 
   在训练后，可以给出各个特征对于输出的重要性
   由于采用了随机采样，训练出的模型的 方差小，泛化能力强。 
   相对于Boosting系列的Adaboost和GBDT，  RF实现比较简单 。
    对部分特征缺失不敏感。 
   缺点：   在某些噪音比较大的样本集上， RF模型容易陷入过拟合。 
    取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。 
   数据维度相对低（几十维），同时对准确性有较高要求时。   因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。
    sklearn.ensemble.RandomForestClassifier(n_estimators=100, criterion='gini', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features='auto', max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, bootstrap=True, oob_score=False, n_jobs=None, random_state=None, verbose=0, warm_start=False, class_weight=None) 

4. 随机森林算法简介

随机森林是一种包含多个决策树的分类器。随机森林的算法是由Leo Breiman和Adele Cutler发展推论出的。随机森林，顾名思义就是用随机的方式建立一个森林，森林里面由很多的决策树组成，而这些决策树之间没有关联。
  
 随机森林就是用过集成学习的思想将多棵树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的一大分支------集成学习（Ensemble Learning）方法。集成学习就是使用一系列学习器进行学习，并将各个学习方法通过某种特定的规则进行整合，以获得比单个学习器更好的学习效果。集成学习通过建立几个模型，并将它们组合起来来解决单一预测问题。它的工作原理主要是生成多个分类器或者模型，各自独立地学习和作出预测。
  
 随机森林是由多棵决策树构成的。对于每棵树，他们使用的训练集是采用放回的方式从总的训练集中采样出来的。而在训练每棵树的结点时，使用的特征是从所有特征中采用按照一定比例随机地无放回的方式抽取的。
  
 随机森林的建立基本由随机采样和完全分裂两部分组成。
  
 随机森林对输入的数据进行行、列的采样，但两种采样的方法有所不同。对于行采样，采用的方式是有放回的的采样，即在采样得到的样本集合中，可能会有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这使得在训练时，每棵树的输入样本都不是全部的样本，所以相对不容易出现过拟合。对于列采样，采用的方式是按照一定的比例无放回的抽样，从M个特征中，选择m个样本（m<M）;
  
 在形成决策树的过程中，决策树的每个节点都要按完全分裂的方式来分裂，直到结点不能再分裂。采用这种方式建立出的决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本都是指向同一个分类器。

5. 随机森林算法是什么？

6. 随机森林算法是什么?

随机森林是一种比较新的机器学习模型。
经典的机器学习模型是神经网络，有半个多世纪的历史了。神经网络预测精确，但是计算量很大。上世纪八十年代Breiman等人发明分类树的算法（Breiman et al. 1984），通过反复二分数据进行分类或回归，计算量大大降低。
2001年Breiman把分类树组合成随机森林（Breiman 2001a），即在变量（列）的使用和数据（行）的使用上进行随机化，生成很多分类树，再汇总分类树的结果。随机森林在运算量没有显著提高的前提下提高了预测精度。
随机森林对多元共线性不敏感，结果对缺失数据和非平衡的数据比较稳健，可以很好地预测多达几千个解释变量的作用（Breiman 2001b），被誉为当前最好的算法之一（Iverson et al. 2008）。

随机森林优点：
随机森林是一个最近比较火的算法，它有很多的优点：
a、在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合。
b、在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力。
c、它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。

7. 随机森林算法的原理

随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。该分类器最早由Leo Breiman和Adele Cutler提出，并被注册成了商标。
在机器学习中，随机森林是一个包含多个决策树的分类器， 并且其输出的类别是由个别树输出的类别的众数而定。 Leo Breiman和Adele Cutler发展出推论出随机森林的算法。 而 "Random Forests" 是他们的商标。 

这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林（random decision forests）而来的。
这个方法则是结合 Breimans 的 "Bootstrap aggregating" 想法和 Ho 的"random subspace method"以建造决策树的集合。
学习算法
根据下列算法而建造每棵树：
1、 用N来表示训练用例（样本）的个数，M表示特征数目。
2、 输入特征数目m，用于确定决策树上一个节点的决策结果；其中m应远小于M。
3、 从N个训练用例（样本）中以有放回抽样的方式，取样N次，形成一个训练集（即bootstrap取样），并用未抽到的用例（样本）作预测，评估其误差。
4、 对于每一个节点，随机选择m个特征，决策树上每个节点的决定都是基于这些特征确定的。根据这m个特征，计算其最佳的分裂方式。
5、 每棵树都会完整成长而不会剪枝，这有可能在建完一棵正常树状分类器后会被采用）。

8. 分类算法 - 随机森林

 上次我写了决策树算法，决策树可以解决分类问题，也有CART算法可以解决回归问题，而随机森林也和决策树非常类似，采用了CART算法来生成决策树，因此既可以解决分类问题，也可以解决回归问题。从名字中可以看出，随机森林是用随机的方式构建的一个森林，而这个森林是由很多的相互不关联的决策树组成。实时上随机森林从本质上属于机器学习的一个很重要的分支叫做集成学习。集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。   所以理论上，随机森林的表现一般要优于单一的决策树，因为随机森林的结果是通过多个决策树结果投票来决定最后的结果。简单来说，随机森林中每个决策树都有一个自己的结果，随机森林通过统计每个决策树的结果，选择投票数最多的结果作为其最终结果。我觉得中国一句谚语很形象的表达了随机森林的运作模式，就是“三个臭皮匠，顶个诸葛亮”。
                                           我有一批100条的数据，通过颜色、长度、甜度、生长地方和水果类别，那么我要预测在某种颜色、长度、甜度和生长地方的水果究竟是什么水果，随机森林要怎么做呢？
   这里的抽样是指的在这批水果中，有放回地抽样，比如我要生成3个决策树来预测水果种类，那么每棵树要抽样50条数据来生成，每棵树抽取数据后数据要放回，下一棵树抽取数据仍然要从100条数据里面抽取。这种方法就叫做 bootstrap重采样技术 。
   每棵树利用抽取的样本生成一棵树，值得注意的是，由于采用的是CART算法，因此生成的是二叉树，并且可以处理连续性数据。如果每个样本的特征维度为M，像以上提到的数据，样本特征维度5，指定一个常数m<<M，随机地从5个特征中选取m个特征子集 （这一点非常重要，这也是随机森林的随机这个名字的来源，因此这样才能保证生成的决策树不同） ，每次树进行分裂时，从这m个特征中选择最优的，并且每棵决策树都最大可能地进行生长而不进行剪枝。   此时，一颗茂盛的决策树就生成了。
   根据3颗决策树的结果，如果是连续型的数据最终需要求均值获得结果，如果是分类型的数据最后求众数获得结果。
   1）正如上文所述，随机森林算法能解决分类与回归两种类型的问题，并在这两个方面都有相当好的估计表现
   2）随机森林对于高维数据集的处理能力令人兴奋，它可以处理成千上万的输入变量，并确定最重要的变量，因此被认为是一个不错的降维方法。此外，该模型能够输出变量的重要性程度，这是一个非常便利的功能
   3）在对缺失数据进行估计时，随机森林是一个十分有效的方法。就算存在大量的数据缺失，随机森林也能较好地保持精确性
   4）当存在分类不平衡的情况时，随机森林能够提供平衡数据集误差的有效方法
   5）模型的上述性能可以被扩展运用到未标记的数据集中，用于引导无监督聚类、数据透视和异常检测
   6）随机森林算法中包含了对输入数据的重复自抽样过程，即所谓的bootstrap抽样。这样一来，数据集中大约三分之一将没有用于模型的训练而是用于测试，这样的数据被称为out of bag samples，通过这些样本估计的误差被称为out of bag error。研究表明，这种out of bag方法的与测试集规模同训练集一致的估计方法有着相同的精确程度，因此在随机森林中我们无需再对测试集进行另外的设置。
   1）随机森林在解决回归问题时并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续型的输出。当进行回归时，随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些还有特定噪声的数据进行建模时出现过度拟合。
   2）对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试。