本文参考来源于:
杨凯, 侯艳, 李康. 随机森林变量重要性评分及其研究进展[J]. .
码字不易,各位看官大大的赞是我更细的动力!
一、引言
随机森林(randomforest,RFrandom\;\; forest,RFrandomforest,RF)由BreimanBreimanBreiman等人在2001年提出。
RFRFRF具有很高的预测准确率,对异常值和噪声有很强的容忍度,能够处理高维数据(变量个数远大于观测个数),有效地分析非线性、具有共线性和交互作用的数据, 并能够在分析数据的同时给出变量重要性评分(variableimportancemeasures,VIMvariableimportance\;\;measures,VIMvariableimportancemeasures,VIM)。这些特点使得RFRFRF特别适用于高维组学数据的研究,即在对疾病进行分类的同时通过VIMVIMVIM值筛选出潜在的生物标志物,研究疾病发生、发展的生物学机制。然而, 由于在实际中由RF筛选变量使用的统计量不同,可能会使结果有较大的差异,为此本文在简单介绍RFRFRF筛选变量的基础上,拟针对目前随机森林变量重要性评分的不同计算方法和新近提出的改进方法, 说明其在高维组学数据分析中的应用。
二、随机森林的基本原理
了解决策树的算法,那么随机森林是相当容易理解的。随机森林的算法可以用如下几个步骤概括:
1.用有抽样放回的方法(bootstrap
)从样本集中选取nnn个样本作为一个训练集;
2.用抽样得到的样本集生成一棵决策树。在生成的每一个结点:
(1)随机不重复地选择ddd个特征
(2)利用这ddd个特征分别对样本集进行划分,找到最佳的划分特征(可用基尼系数、增益率或者信息增益判别)
3.重复步骤1到步骤2共kkk次,kkk即为随机森林中决策树的个数。
4.用训练得到的随机森林对测试样本进行预测,并用投票法决定预测的结果。
下图比较直观地展示了随机森林算法:
图片来源:
杨凯, 侯艳, 李康. 随机森林变量重要性评分及其研究进展[J]. .
RFRFRF中的每一棵分类树为二叉树,根节点包含全部训练自助样本,按照一定的原则,在每个节点从一组随机选取的变量中选择使分枝后节点“不纯度” 最小的变量作为分枝变量,分裂为左节点和右节点, 它们分别包含训练数据的一个子集, 分裂后的节点按照同样规则继续分裂, 直到满足分枝停止规则而停止生长, 具体过程见图 1。
“不纯度” 的衡量标准包括GiniGiniGini不纯度、 熵和错误率等。 变量筛选使用VIMVIMVIM统计量。
三、随机森林常规的变量重要性评分
现假定有变量X1,X2,L,XMX_1\;,\;X_2\;,\;L\;,\;X_MX1,X2,L,XM,需要计算出MMM个VIMVIMVIM得分统计量。
RFRFRF常规的VIMVIMVIM计算方法分为两种,即根据GiniGiniGini指数和袋外数据(OOBOOBOOB) 错误率计算得到, 变量XjX_jXj的得分统计量分别用VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)和VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)表示。
2.1 Gini指数
统计量VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)表示第jjj个变量在RFRFRF所有树中节点分裂不纯度的平均改变量。GiniGiniGini指数的计算公式为:
GIm=∑k=1Kp^mk(1−p^mk)(1)GI_{m}=\sum_{k=1}^K\hat{p}_{mk}(1-\hat{p}_{mk})\;\;\;\;(1) GIm=k=1∑Kp^mk(1−p^mk)(1)
KKK为自助样本集的类别数,p^mk\hat{p}_{mk}p^mk为节点mmm样本属于第kkk类的概率估计值,当样本为二分类数据时(K=2K=2K=2) ,节点mmm的GiniGiniGini指数为:
GIm=2p^m(1−p^m)(2)GI_{m}=2\hat{p}_{m}(1-\hat{p}_{m})\;\;\;\;(2) GIm=2p^m(1−p^m)(2)
p^m\hat{p}_{m}p^m为样本在节点mmm属于任意一类的概率估计值。
变量XjX_jXj在节点mmm的重要性,即节点mmm分枝前后GiniGiniGini指数变化量为:
VIMjm(Gini)=GIm−GIl−GIr(3)VIM_{jm}^{(Gini)}=GI_{m}-GI_{l}-GI_{r}\;\;\;\;(3) VIMjm(Gini)=GIm−GIl−GIr(3)
GIlGI_{l}GIl和GIrGI_{r}GIr分别表示由节点mmm分裂的两新节点的GiniGiniGini指数。
如果变量XjX_jXj在第iii棵树中出现MMM次,则变量XjX_jXj在第iii棵树的重要性为:
VIMij(Gini)=∑m=1MVIMjm(Gini)(4)VIM_{ij}^{(Gini)}=\sum_{m=1}^MVIM_{jm}^{(Gini)}\;\;\;\;(4) VIMij(Gini)=m=1∑MVIMjm(Gini)(4)
变量XjX_jXj在RFRFRF中的GiniGiniGini重要性定义为:
VIMj(Gini)=1n∑i=1nVIMij(Gini)(5)VIM_{j}^{(Gini)}=\frac{1}{n}\sum_{i=1}^nVIM_{ij}^{(Gini)}\;\;\;\;(5) VIMj(Gini)=n1i=1∑nVIMij(Gini)(5)
其中,nnn为RFRFRF中分类树的数量。
2.2 OOB 错误率
VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)的定义为:在RFRFRF的每棵树中,使用随机抽取的训练自助样本建树,并计算袋外数据(OOBOOBOOB)的预测错误率,然后随机置换变量XjX_jXj的观测值后再次建树并计算OOBOOBOOB的预测错误率,最后计算两次OOBOOBOOB错误率的差值经过标准化处理后在所有树中的平均值即为变量XjX_jXj的置换重要性(VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB))。
变量XjX_jXj在第iii棵树的VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)为:
VIMj(OOB)=∑p=1noiI(Yp=Ypi)noi−∑p=1noiI(Yp=Yp,πji)noiVIM_{j}^{(OOB)}=\frac{\sum_{p=1}^{n_o^i}I(Y_p=Y_p^i)}{n_o^i}-\frac{\sum_{p=1}^{n_o^i}I(Y_p=Y_{p,\pi_j}^i)}{n_o^i} VIMj(OOB)=noi∑p=1noiI(Yp=Ypi)−noi∑p=1noiI(Yp=Yp,πji)
其中,noin_o^inoi为第iii棵树OOBOOBOOB数据的观测例数,I(g)I(g)I(g)为指示函数,即两值相等时取1,不等时取0;Yp∈{0,1}Y_p\in\{0,1\}Yp∈{0,1}为第ppp个观测的真实结果,Ypi∈{0,1}Y_p^i\in\{0,1\}Ypi∈{0,1}为随机置换前第iii棵树对OOBOOBOOB数据第ppp个观测的预测结果,Yp,πji∈{0,1}Y_{p,\pi_j}^i\in\{0,1\}Yp,πji∈{0,1}为随机置换后第iii棵树对OOBOOBOOB数据第ppp个观测的预测结果。
当变量jjj没有在第iii棵树中出现时,VIMij(OOB)=0VIM_{ij}^{(OOB)}=0VIMij(OOB)=0
变量XjX_jXj在RFRFRF中的置换重要性定义为:
VIMj(OOB)=∑i=1nVIMij(OOB)nVIM_{j}^{(OOB)}=\frac{\sum_{i=1}^nVIM_{ij}^{(OOB)}}{n} VIMj(OOB)=n∑i=1nVIMij(OOB)
其中,nnn为RFRFRF中分类树的数量。
2.3 常规变量重要性评分的优缺点
VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)在数据挖掘中估计变量重要性时有着广泛的应用。 当变量为连续型变量且互不相关时,VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)的估计是无偏的;
当信噪比较低时,VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)的准确性也高于VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB),因此,VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)有更高的稳定性。
然而, 当同时存在连续变量和分类变量或者分类变量的水平数不同时,VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)估计则不够准确。由于KKK个水平的分类变量在节点处可以有2K−1−12^{K-1}-12K−1−1种分割, 连续变量在节点处可以有b−1b-1b−1种分割(bbb为样本量)。在备选分割较多时, 即使变量没有分类作用, 也可能使GiniGiniGini指数降低, 从而更容易被选为分枝变量, 即VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)被高估。 实际上, 由于GiniGiniGini指数的计算问题, 水平数多的分类变量的GiniGiniGini指数降低会大于水平数少的分类变量。
当分类变量水平数相同时, 如果不同变量的水平间差别不同, 容易过高估计水平间差别大的变量的VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini) 。 在 SNP 数据分析中, Nicodemus 等人指出当所有 SNP 都不具有分类能力时,不相关 SNP 的VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)高于高度相关 SNP 的VIMj(Gini)VIM_{j}^{(Gini)}VIMj(Gini)
事实上,VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)在实际中的应用范围更加广泛。 由于VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)是通过OOBOOBOOB数据计算的, 因此可以看作变量具有的分类能力, 没有分类能力的变量在观测值置换前后的OOBOOBOOB错误率不会发生改变, 即数学期望E(VIMj(OOB))=0E(VIM_{j}^{(OOB)})=0E(VIMj(OOB))=0,此外,VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)不仅能够衡量变量单独的分类能力, 还能够衡量变量间交互作用的分类能力。
当同时存在连续变量和分类变量或者分类变量水平数不同时, 并不会影响VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)准确性。VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)是通过随机置换变量观测值前后OOBOOBOOB错误率的差值计算的, 即使没有分类作用, 水平数多的变量也更容易被选为分枝变量, 但置换前后并不会影响OOBOOBOOB错误率,同时会使VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)的变异增大。
在分类数据不平衡时,VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)的准确性会受到一定影响。例如多数为正常人, 无论变量是否置换, 大部分的数据都会被预测为正常, 虽然OOBOOBOOB错误率受到的影响可能不大,但却会严重低估所有变量的VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)。
当单棵树的预测准确率较低时(如OOBOOBOOB错误率达到 50%) , 会低估变量的VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)
当置换前OOBOOBOOB错误率已经很大时, 置换变量观测值使得 OOB 错误率变大的可能性降低, 从而低估变量的VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)
当没有分类能力的变量与有分类能力的变量相关时, 可能低估相关有分类能力变量的VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB),且估计方差变异增加, 而此时没有分类能力变量的VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)则被高估。
组学数据中存在大量的噪声变量, 当变量数目巨大而具有分类能力的变量所占比例很小时,RFRFRF建模容易受到大量噪声变量的干扰, 使变量的VIMVIMVIM计算受到影响, 变量筛选的结果不可信。
2.4 变量重要性( VIM ) 的显著性检验
VIMVIMVIM给出了变量的重要性排序, 但无法在变量筛选时给出显著性假设检验的阈值。 事实上, 当所有变量都没有分类能力时,VIMVIMVIM也会给出变量重要性排序, 筛选出不具有分类能力的变量; 而当有分类能力的变量很多时, 仅通过变量的排序进行变量筛选, 可能漏掉一些具有分类能力的变量。
BreimanBreimanBreiman等人提出通过ZZZ值直接计算VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)的显著性, 即:
Z=VIMj(OOB)/(σ^/n)Z=VIM_{j}^{(OOB)}/(\hat{\sigma}/\sqrt{n}) Z=VIMj(OOB)/(σ^/n)
其中,σ^\hat{\sigma}σ^为RFRFRF中各棵树VIMj(OOB)VIM_{j}^{(OOB)}VIMj(OOB)的标准差,nnn为随机森林(RFRFRF)中树的数量。 然而,StroblStroblStrobl等人通过模拟实验表明:ZZZ值的检验效能与样本量bbb及树的数量nnn有很大的关系, 当样本量bbb很大而树的数量nnn小时, 检验效能接近于0。