(本科）第12章-随机森林.pdf

(c) 2020，陈强，机器学习及 R 应用，高等教育出版社 1 第第 12 章章 随机森林随机森林 第 12-13 章介绍集成学习(ensemble learning )，也为“组合学习” 。 12.1 集成学习集成学习 集成学习的基本问题：如果有一些预测效果一般的“弱学习器”(weak learner)，能否以某种方式将它们组合起来，构成一个预测效果优良的“强学习器”(strong learner)？ 集成学习的思路类似于 “三个臭皮匠， 顶个诸葛亮”（wisdom of crowds） 。 用于集成学习的弱学习器，也称为“基学习器”(base learner)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 2 决策树是最常见的基学习器。 给定数据与算法，则监督学习的估计结果是基本确定的(可能由于随机分组的不同而略有差异)，这可表示为 数据算法结果 (12.1) 怎么才能得到不同结果呢？ 一种方法是，给定数据，但使用不同的算法，然后将所得的不同结果组合在一起；比如加权平均，而权重以交叉验证来确定。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 3 以回归问题为例，假设共有三种不同的算法(比如线性回归、KNN 与决策树)，其预测结果分别为1( )f x，2( )fx与3( )f x；则集成算法的最终预测结果为 1 122123( )( )( )(1)( )ffffxxxx (12.2) 其中，10，20，且121。最优调节参数1与2可通过交叉验证来确定。 由于算法1( )f x，2( )fx与3( )f x皆为集成算法( )f x的特例， 故( )f x的预测效果肯定优于(至少不差于)这三种单独的算法。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 4 类似地，对于分类问题，则可将不同算法的预测结果，进行加权求和，按多数票规则投票；而投票权重可通过交叉验证确定。 集成学习的另一方式为，给定算法(比如以决策树的 CART 算法为基学习器)，然后“搅动数据” ，得到不同的决策树模型，再组合在一起，即所谓“Perturb + Combine”的模式。 本章介绍的装袋法与随机森林属于这种方式。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 5 12.2 装袋法装袋法 Breiman(1996)提出“装袋法”(bootstrap aggregating，简记 bagging)。 装袋法使用“自助法”(bootstrap)来搅动数据。所谓自助法，是一种有放回的再抽样方法(resampling with replacement)。装袋法的具体步骤如下。 首先，对训练数据进行有放回的再抽样，得到B个自助样本(bootstrap samples)，比如500B 。其中，第b个自助样本可写为 *1,1,nbbiiiybBx (12.3) 其中，上标星号“*”表示自助样本。每个自助样本的样本容量均为n(样本容量不变)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 6 其次， 根据自助样本*1,Bbbiibyx估计B棵不同的决策树， 不进行修枝。记其预测结果为 *( ) ,1,bfbBx (12.4) 最后，对于回归树，将B棵决策树的预测结果进行平均： *11( )( )BbbagbffBxx (12.5) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 7 对于分类树，则将B棵决策树的预测结果进行多数投票(majority vote)，得票最多的类别胜出： *1,1( )argmax( )BbbagyKbfI yfxx (12.6) 其中，假设1,yK，共分为K类。( )I 为示性函数(indicator function)，判断是否“*( )byfx” ；如果是，则记为 1，否则记为 0。 通过多数票， 将许多弱分类器进行组合， 即所谓 “combining many weaker classifiers to produce a powerful committee” 。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 8 由于装袋法把很多自助样本(bootstrap samples)的估计结果汇总(aggregating)，故名“bootstrap aggregating” 。 12.3 装袋法的原理装袋法的原理 由于 bagging 将很多决策树进行平均， 故可降低估计量的方差(variance)，从而提高模型的预测准确率。 例如，假设随机变量1,nzz为独立同分布(iid)，而方差为2，则样本均值11niizzn的方差可缩小n倍： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 9 221111Var( )VarVar( )nniiiizzznnn (12.7) 其中，由于1,nzz相互独立，故上式中的协方差均为 0，而所有2Var( )iz(同分布)。 另一方面，由于装袋法并不修枝，而让决策树尽情生长，故可降低每棵决策树的偏差(bias)；然后，通过 bagging 来控制方差(variance)。 在一定条件下，装袋法可以同时降低偏差与方差，故可减小均方误差(MSE)或总误差。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 10 Breiman(1996)使用若干标准的机器学习数据集， 发现与单棵决策树相比，bagging 可显著降低测试误差。 应该在什么情况下使用装袋法？ Bagging 特别适用于方差较大的不稳定估计量(unstable estimators)， 比如决策树、线性回归的变量子集选择(subset selection)等。 对于不稳定估计量，当样本数据轻微扰动时(比如换一个样本，或使用子样本)，则可能引起估计结果较大的变化。 比如，当数据轻微变化时，所得决策树结构可能发生较大改变。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 11 又比如，当用线性回归进行变量子集选择时，所选变量也对样本数据比较敏感，并不稳健。 另一方面，bagging 对于方差较小的稳定估计量(stable estimators)，比如KNN，则作用不大。对于 KNN 而言，即使搅动数据，一般也不会对附近K近邻的平均结果产生明显影响。 由于单棵决策树为分段常值函数(piecewise constant function)，故并不连续。 将许多决策树进行平均，则可得到更为连续的回归函数或决策边界，从而提高预测性能。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 12 以第 10 章的摩托车撞击实验数据集 mcycle 为例。 首先，估计单棵回归树，并画所估函数，结果参见图 12.1： library(rpart) fit pred plot(mcycle$times,mcycle$accel,xlab=Time, ylab=Acceleration, main=Single Tree Estimation) lines(mcycle$times,pred,col=blue) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 13 图 12.1 单棵决策树所估计的回归函数 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 14 从图 12.1 可见，单棵决策树所估计的回归函数为“阶梯函数”(step function)，并不连续。 虽然回归树抓住了数据变化的主要特征， 但在细节上比较粗糙， 存在 “欠拟合”(underfit)。 下面使用 R 包 randomForest 的 randomForest()函数进行装袋法估计，结果参见图 12.2： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 15 install.packages(randomForest) library(randomForest) set.seed(1) fit pred plot(mcycle$times,mcycle$accel,xlab=Time, ylab=Acceleration,main=Bagging Estimation) lines(mcycle$times,pred,col=blue) 以上 R 代码的解释，参见第 12.8 节的 R 案例。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 16 图 12.2 装袋法所估计的回归函数 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 17 图 12.2 显示，虽然 bagging 所估计的回归函数依然不太光滑，但已经比单棵决策树更为贴近数据，拟合效果更好。 在此例中，之所以 bagging 所估函数不太光滑，可能是由于样本容量太小，仅 133 个观测值。 12.4 袋外误差袋外误差 Bagging 还提供了估计测试误差的简便方法，可以不用测试集(test set)或交叉验证(CV)。 由于进行有放回的再抽样，每棵树都有些观测值未使用，称为“袋外观测值”(Out-of-Bag observations，简记 OOB 观测值)，可作为测试集。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 18 对于任意观测值ix，它未出现于大约3B的决策树，故对于这些决策树而言是 OOB 观测值。 将这些(未用到ix)决策树的预测结果进行平均(或多数投票)，记为对第i个观测值的袋外预测值(OOB prediction for the ith observation),i OOBy。由此可得对所有观测值的袋外预测值,1ni OOBiy。 将袋外预测值,i OOBy与实际观测值iy对比，即可得到袋外误差(out-of-bag error)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 19 对于回归问题，袋外误差为 OOB 均方误差(OOB MSE)： 2,11MSE()nOOBi OOBiiyyn (12.8) 对于分类问题，袋外误差则为 OOB 错误率(OOB error rate)： ,11Err()nOOBi OOBiiI yyn (12.9) 如果自助样本的数目B足够大，则袋外误差与“留一交叉验证误差”(Leave-One-Out Cross-Validation error，简记 LOOCV)几乎等价。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 20 对于样本容量很大或变量很多的大数据，尤其方便使用袋外误差(可节省运算时间)，作为对测试误差的估计。 对于回归问题，还可根据 OOB 均方误差计算准2R(pseudo 2R)，即在响应变量y的样本方差中，有多大比例可由模型解释： 2Var( )MSEMSEPseudo1Var( )Var( )OOBOOByRyy (12.10) 其中，Var( )y为响应变量y的样本方差。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 21 12.5 随机森林随机森林 如果1,nzz为 iid，则其样本均值z的方差可缩小n倍。 但如果1,nzz之间相关，则样本均值z的方差一般不会缩小n倍。 “三个臭皮匠， 顶个诸葛亮” 的成立有前提条件， 即希望这些 “臭皮匠”互不相关，才更有互补性。 在使用装袋法时，由于所用算法完全相同(比如都是 CART 算法)，而每棵决策树所用自助样本都来自同样的原始数据，故存在较高的相关性。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 22 如果想进一步提高 bagging 的预测性能，必须降低这些决策树之间的相关性。 如何使决策树之间更不相关(decorrelate)？ Bagging 的决策树之间相关性强，也是因为使用相同的特征变量ix。 Breiman(2001b)大胆地提出随机森林(Random Forest)： 在 bagging 的基础上(依然使用自助样本)，在决策树的每个节点进行分裂时，仅随机选取部分变量(比如m个变量)作为候选的分裂变量。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 23 比如，在一个节点随机选择m个变量作为候选的分裂变量(其余()pm个变量则不用)，而在下一节点再次随机选择(可能不相同的)m个变量作为候选的分裂变量，以此类推；然后对随机森林中的每棵决策树都如此操作。 对于回归树， 一般建议随机选取3mp个变量(p为特征变量的个数)。 对于决策树，则一般建议mp。 这种做法称为随机特征选择(random feature selection)，其目的是为了降低决策树之间的相关性。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 24 随机特征选择也称为列子抽样(column subsampling)， 因为在数据框的二维表结构中，每一列都对应于一个特征变量。 随机森林作预测的方式与装袋法相同， 也是对所有决策树的预测结果进行平均(回归问题)，或多数投票(分类问题)。 在决策树的每个节点，随机森林仅使用少部分变量。这种做法似乎有些疯狂，因为大多数变量被暂时遗弃，未使用全部信息，无疑会增大偏差(bias)。 由于不同节点被强迫使用不同的变量进行分裂， 故可降低不同决策树之间的相关性，从而减小方差(variance)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 25 在一次节点分裂中未选为候选变量的特征变量，以后依然有机会选上；或在其他决策树选上。 在偏差与方差的权衡中，随机森林以牺牲少量偏差为代价，可以换取方差的更大幅下降，从而降低均方误差(或总误差)。 装袋法为随机森林的特例。对于随机森林，如果令mp，则为装袋法。在每个节点，装袋法均将所有变量作为候选的分裂变量。由于使用所有特征变量进行分裂，故偏差较小，但不同决策树之间相关性较强，导致方差较大。 在另一极端，如果m很小，虽然决策树之间很不相关，可降低方差，但由于每次用于分裂的变量太少，导致偏差较大。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 26 随机森林最重要的调节参数就是m。 调节参数m的选择，涉及偏差与方差的权衡，可通过袋外误差或交叉验证来确定。选择一个最优参数m，使得袋外误差或交叉验证误差最小化。 对于随机森林，自助样本的数目B，则不太重要。通常选择500B 或更多。 由于随机森林使用B棵决策树的预测结果进行平均或多数投票，故增加B并不会导致过拟合(由大数定律所保证)。 一般选择足够大的B，使得袋外误差或交叉验证误差不再随着B增大而下降即可。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 27 12.6 变量重要性变量重要性 随机森林包含很多决策树(比如 500 棵决策树的平均)，故无法像单棵决策树那样进行解释。 对于随机森林，应如何度量“变量重要性”(Variable Importance)？ 对于每个变量，在随机森林的每棵决策树，可度量由该变量所导致的分裂准则函数(残差平方和或基尼指数)之下降幅度。针对此下降幅度，对每棵决策树进行平均，即为对该变量重要性的度量。 将每个特征变量的重要性依次排列画图，即为变量重要性图(Variable Importance Plot)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 28 12.7 偏依赖图偏依赖图 我们感兴趣每个变量对于y的边际效应(marginal effects)。 对于特征向量12()px xx x，假设( )yfx，但函数( )f 无解析表达式(比如随机森林)。 不失一般性，考虑第 1 个特征变量1x对y的边际效应： 1211( ,)pf x xxyxx (12.11) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 29 边际效应1yx依赖于其他变量2(,)pxx的取值，一般来说不是常数(除非是线性模型)。 考虑在函数12( ,)pyf x xx中， 将其他变量2(,)pxx对于y的影响通过积分平均掉： 21,12()E( ,)pxxpxf x xx (12.12) 其中， 期望算子2,E( )pxx对变量2(,)pxx求期望， 故所得结果1( )x只是1x的函数。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 30 由于( )f 无解析表达式，一般很难直接计算此期望。 使用统计学方法，以样本均值替代总体均值2,E( )pxx可得： 11211()( ,)niipixf x xxn (12.13) 任意给定1x，均可计算1( )x，并可画出11( , ( )xx的图像，称为偏依赖图(Partial Dependence Plot)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 31 偏依赖图适用于任何( )f 无解析表达式的黑箱(black box)方法。 也可同时考虑多个变量对于y的偏影响。 比如，响应变量y对于12( ,)x x的偏依赖可定义为 1212311( ,)( ,)niipix xf x x xxn (12.14) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 32 12.8 回归问题的随机森林回归问题的随机森林 R 案例案例 对于回归问题，以波士顿房价数据 Boston 演示随机森林的 R 操作。 * 详见教材，以及配套 R 程序（现场演示） 。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 33 12.9 分类问题的随机森林分类问题的随机森林 R 案例案例 作为分类问题的随机森林案例， 使用 R 包 mlbench 的声呐数据 Sonar来演示。它包含 208 个观测值与 61 个变量。 响应变量为因子 Class， 表示声呐回音来自 “金属筒” (Metal Cylinder，记为 M)还是“岩石”(Rock，记为 R)。 特征变量共 60 个(V1-V60)，表示在不同角度(aspect angle)与频道(frequency band)下，声呐反射信号的能量。研究目的是为了区分这些声呐信号究竟来自金属还是岩石。 * 详见教材，以及配套 R 程序（现场演示） 。