随机森林学习总结
1.决策树
决策树：从根节点开始一步步走到叶子节点(决策)，所有的数据最终都会落在叶子节点，既可以做分类也可以做回归。根据决策树的输出结果，决策树可以分为分类树和回归树，分类树输出的结果为离散值(具体的类别)，而回归树输出的结果为连续值(一个确定的数值)。决策树的构建算法主要有三种ID3，C4.5，CART三种，其中ID3和C4.5是分类树，CART是分类回归树，ID3是决策树最基本的构建算法，而C4.5和CART是在ID3的基础上进行优化的算法。下面介绍常见的三种决策树算法。
1.1 ID3
(1)熵 熵是表示随机变量不确定性的度量，直观理解是物体内部的混乱程度。公式如下：
其实就是随机变量的自信息量I(x)的数学期望。
(2)信息增益
其中C为类别，这个变量可能的取值为C1，C2... Cn， T为特征。信息增益可以理解为先验熵(系统原本的熵)与固定特征T之后的条件熵之差。
(3)决策树的构建
数据分割。对于离散型数据，直接按照离散数据的取值进行分裂，每一个取值对应一个子节点。对于连续型数据，ID3原本是没有能力处理的，只有通过离散化将连续性数据转化为离散型数据再进行处理。
选择最优分裂属性。ID3采用信息增益作为选择最优的分裂属性的方法，选择熵作为衡量节点纯度的标准，信息增益的公式如上，分别计算每一个属性的信息增益，选择信息增益最大的属性进行分裂。
停止分裂的条件。①最小节点数，当节点的数据量小于一个指定的数量时，不继续分裂。为了防止噪声的影响和降低复杂度，有利于降低过拟合的影响。②熵或者基尼值小于阀值。熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度时，节点停止分裂。③决策树的深度达到指定的条件。④所有特征已经使用完毕，不能继续进行分裂。
(4)总结
ID3是基本的决策树构建算法，作为决策树经典的构建算法，其具有结构简单、清晰易懂的特点。虽然ID3比较灵活方便，但是有以下几个缺点：①采用信息增益进行分裂，分裂的精确度可能没有采用信息增益率进行分裂高。②不能处理连续型数据，只能通过离散化将连续性数据转化为离散型数据。③不能处理缺省值。④没有对决策树进行剪枝处理，很可能出现过拟合问题。
1.2 C4.5
C4.5在ID3的基础上对上述三个方面进行了相应的改进：①对节点进行分裂时采用信息增益率作为分裂的依据 ② 能够对连续数据进行处理 ③ C4.5采用了剪枝策略，对完全生长的决策树进行剪枝处理，一定程度上降低过拟合的影响。
(1)信息增益率
信息增益率用前面的信息增益Gain(S,A)和分裂信息度量SplitInformation(S,A)共同定义的，分裂信息度量可以理解为：分裂信息用来衡量属性分裂数据的广度和均匀。全部公式如下：
(2)决策树的构建
①采用信息增益率作为分裂的依据，信息增益率越大，说明分裂的效果越好。②对连续型属性进行处理，处理方式是先根据连续
型属性进行排序，然后选择切割点将数据切成两半，切割点的选取：直接计算每一个切割点切割后的信息增益，然后选择分裂效果最
优的切割点。③剪枝。C4.5采用悲观剪枝方法(PEP)。如果剪枝后的误差小于剪枝前精度的上限，则说明剪枝后的效果更佳，此时需
要子树进行剪枝操作。
1.3 CART
(1)简介
CART，又名分类回归树，是在ID3的基础上进行优化的决策树，CART既能是分类树，又能是回归树。当CART是分类树时，采用GINI值作为节点分裂的依据，当CART是回归树时，采用样本的最小方差作为节点分裂的依据。CART是一棵二叉树。
(2)CART的输出
如果是一棵分类树，其叶子节点的输出结果为一个实际的类别，选择叶子节点中数量占比最大的类别作为输出的类别，如果是一棵回归树，一般情况下选择中值、平均值或者众数表示，常见的是平均值。
(3)分裂的属性
如果是分类树，采用GINI值衡量节点不纯度，如果是回归树，采用样本方差衡量节点的不纯度。不纯度越高，节点分类或者预测的效果就越差。GINI的计算公式：
Pk表示观测点中属于k类的概率，当GINI(A)=0时，表示所有样本属于同一类，当所有类在节点中以相同的概率出现时，GINI(A)最大化,即类别分布越平均，GINI值越大，类分布越不均匀，GINI值越小。回归方差计算公式：
方差越大，表示该节点的数据越分散，预测的效果就越差。如果一个节点的所有数据相同，那么方差就为0，此时可以肯定得认为时该节点的输出值，如果节点的数据相差很大，那么输出的值很大的可能与实际值相差较大。
因此，无论是分类树还是回归树，CART都要选择使子节点的GINI值或者回归方差最小的属性作为分裂的方案，即最小化分类树。
(4)剪枝。CART采用CCP(代价复杂度)剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。
2.随机森林
随机森林，指的是利用多棵树对样本进行训练并预测的一种分类器。随机森林就是由多棵CART树构成的。随机森林具有两个随机性：
①样本随机性：对于每棵树，它们使用的训练集是从总的训练集中有放回采样出来的。这意味着，总的训练集中的有些样本可能多次出现在一棵树的训练集中，也可能从未出现在一棵树的训练集中。
②特征随机性：在训练每棵树的节点时，使用的特征是从所有特征中按照一定比例随机地无放回抽取的，根据Leo Breiman的建议，假设总的特征数量为M，这个比例可以是sqrt(M),1/2sqrt(M), 2sqrt(M)。
随机森林与使用决策树作为基本分类器的bagging有些类似，它们都具有①，但是使用决策树做为基分类器的bagging不具有②。
2.1 随机森林的训练过程
(1)给定训练集S，测试集T，特征维数F。确定参数：使用到的CART的数量为t ,每棵树的深度d,每个节点使用到的特征数量f, 终止条件：节点上最少样本数s，节点上最少的信息增益m
对于第t-1棵树，i=t-1:
(2)从S中有放回的抽取大小和S一样的训练集S(i),作为根节点的样本，从根节点开始训练
(3)如果当前节点上达到终止条件，则设置当前节点为叶子节点，如果是分类问题，该叶子节点的预测输出为当前节点样本集合中数量最多的哪一类c(j),概率p为c(j)占当前样本集的比例；如果是回归问题，预测输出为当前节点样本集各个样本值的平均值。然后继续训练其他节点。如果当前节点没有达到终止条件，则从F维特征中无放回的随机选取f维度特征。利用这f维特征，寻找分类效果最好的一维特征k及其阈值th,当前节点上样本第k维特征小于th的样本被划分到左节点，其余的被划分到右节点。继续训练其他节点。
(4)重复(2)(3)直到所有节点都训练过了或者被标记为叶子节点。
(5)重复(2)(3)(4)直到所有CART都被训练过。
2.2 利用随机森林的预测过程
对于第t-1棵树，i=t-1;
(1)从当前树的根节点开始，根据当前节点的阈值th,判断是进入左节点(<th)还是进入右节点(>=th)，直到到达某个叶子节点，并输出预测值。
(2)重复执行(1)直到所有t棵树都输出了预测值。如果是分类问题，则输出为所有树种预测概率总和最大的那一个类，即对每个c(j)的p进行累计；如果是回归问题，则输出为所有树的输出的平均值。
3.随机森林的特点
影响分类性能的主要因素：①森林中单棵树的分类强度：每棵树的分类强度越大，则随机森林的分类性能越好。②森林中树之间的相关度：树之间的相关度越大，则随机森林的分类性能越差。
两个随机性的引入，使得随机森林不容易陷入过拟合
两个随机性的引入，使得随机森林具有很好的抗噪声能力
对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。
可生成一个Proximities=(pij)矩阵，用于度量样本之间的相似性：pij=aij/N,aji表示样本i和j出现在随机森林中同一个叶子结点的次数，N表示随机森林中树的棵树。
可以得出变量重要性排序(两种：基于OOB误分率的增加量和基于分裂时的GINI下降量)
bootstrapping中没有被选择的数据称为out of bag(OOB) examples, 这些数据由于没有用来训练模型，故可以用于模型的验证。
4.简述RF、GBDT、xgboost区别
随机森林Random Forest是一个包含多个决策树(CART)的分类器。GBDT(Gradient Boosting Decision Tree)即梯度上升决策树算法，相当于融合决策树和梯度上升boosting算法。xgboost类似于gbdt的优化版，不论是精度还是效率上都有了提升。与gbdt相比，具体的优点有：①损失函数是用泰勒展式二项逼近，而不像gbdt里的就是一阶导数。②对树的结构进行了正则化约束，防止模型过度复杂，降低了过拟合的可能性。③节点分裂的方式不同，gbdt是用的gini系数，xgboost是经过优化推导后的。
参考链接：
http://www.cnblogs.com/yonghao/p/5135386.html
http://www.cnblogs.com/hrlnw/p/3850459.html
http://blog.****.net/a819825294/article/details/51177435