改进Boruta算法在特征选择中的应用

陈逸杰 唐加山

摘 要：特征选择在机器学习中运用广泛，Boruta算法是一种常见的特征选择方法，算法思想简单、易于操作，但样本复杂度较高。针对该问题提出改进Boruta算法，在原算法阴影特征样本建造中只对部分样本打乱重排序，降低了阴影特征样本的复杂度。实验结果表明，改进的Boruta算法在混合比例约为0.4～0.6时相比原算法，提取出的特征拟合模型预测性能略有提高。使用平均減少不纯度（mean decrease impurity）和随机Lasso这两种传统方法选择同样数量的特征建立模型进行预测，发现改进的Boruta算法预测性能比上述两种方法更优，改进的Boruta算法在降低样本复杂度的同时提高了预测性能。

关键词：特征选择;Boruta;机器学习;阴影特征;混合比例

DOI：10. 11907/rjdk. 182315

中图分类号：TP312文献标识码：A文章编号：1672-7800（2019）004-0069-05

0 引言

特征选择是机器学习方法应用的重要步骤，现代数据集通常用实际模型构建的变量来描述，而大多数变量与分类无关，这导致两个问题：①处理大型数据集会降低算法速度，占用太多资源;②当变量数量明显高于最优值时，许多机器学习算法的准确度会降低[1-2]。因此，进行特征选择就变得非常必要。特征选择是从一组特征中挑选出一些最有效的特征以降低特征空间维数的过程[3-4]，是模式识别的关键步骤。一个好的训练样本对于分类器而言至关重要，将直接影响模型预测的准确度[5-6]，因此高效的特征选择算法是本文研究的重点。

特征选择算法根据所采用的特征评价策略分为过滤和包装两大类。过滤方法独立于后续采取的机器学习算法，可较快排除一部分非关键性噪声特征，缩小优化特征子集搜索范围，但它并不能保证选择出一个规模较小的优化特征子集。包装方法在筛选特征过程中直接用所选特征子集训练分类器，根据分类器在测试集的性能表现评价该特征子集优劣。该方法在计算效率上不如过滤方法，但其所选的优化特征子集规模相对较小[7-8]。

特征选择算法很多，最常用的是随机森林重要性排序，其它比如mRMR 算法[9，10]采用最大相关最小冗余准则进行特征子集排序，使用包装方法进行特征子集选择，其问题是特征子集计算时间长，不能有效删除冗余特征。Shao等[11]提出了一种混合优化的特征选择算法（hybrid optimization based multi-label feature selection，HOML）。该算法综合了模拟退火算法和遗传算法以及贪婪算法寻找最优特征子集。这两种方法直接使用分类器评价特征与标签集合之间的关系，算法计算较复杂，在实际中难以应用。

本文讨论机器学习中常用的Boruta算法[9]。该算法在R及python软件中皆有现成的包，可在软件中直接调用。Boruta算法是一种围绕随机森林[10-12]分类器构建的包装器方法，是Stoppiglia、Dreyfus、Dubois和Oussar（2003）思想的扩展。通过比较真实特征与阴影特征之间的相关性确定变量相关性，在股票收益率研究[13]、地理统计研究[14]中皆有应用。

Boruta算法和mRMR算法及HOML算法存在类似问题，即计算时间长、复杂度较高，影响了运行效率。具体体现在创建阴影特征的样本这一步骤中。因此，本文增加一个参数用于控制阴影特征的比例，不仅可降低样本复杂度，还可提高预测性能。

1 Boruta算法

1.1 Boruta算法原理

Boruta算法是围绕R包randomForest中实现的随机森林分类算法构建的包装器。随机森林分类算法通常可在不调整参数的情况下运行，并给出特征重要性的数值估计。随机森林是一种集成方法，通过对多个无偏的弱分类器投票比如决策树来执行分类。这些树是在训练集的不同装袋样本上独立构建的。将对象之间的属性值随机排列引起的分类准确性的损失作为属性的重要性度量。Boruta算法考虑了森林中树木的平均准确度损失的波动，使用平均下降精度用于度量重要性。

Boruta算法使用随机设计的属性扩展了变量特征。对每个特征创建一个相应的“阴影”特征，其值是通过重新排列原始特征的值获得的。然后，使用此扩展变量的所有特征执行分类，并计算所有特征的重要性。由于存在随机波动，阴影特征的重要性可能非零。因此，由阴影特征的重要性决定哪些特征真正重要。重要性度量本身随随机森林分类器的随机性而变化，对阴影特征很敏感，需要重复洗牌程序以获得有效结果。

简而言之，Boruta算法和随机森林分类器基于相同的思想，即通过向系统添加随机性并从随机样本集合中收集结果，以减少随机波动和相关性产生的误差。这种额外的随机性令使用者更清楚地了解特征的重要程度。

1.2 Boruta算法流程

算法流程如图1所示。

①将[m]行[n]列的原始样本进行复制得到混合样本;②将混合样本中的每一列都独立进行随机行变换，得到[m]行[n]列的阴影特征样本;③将原始样本与阴影特征样本合并得到[m]行[2n]列混合样本;④在新的混合样本上运行随机森林分类器并收集计算每个变量不在模型中的下降精度，计算出平均减少精度MeanImp;⑤将重要性低于MeanImp的特征标记为“不重要”，并将其从变量中永久删除;⑥在阴影特征中找到最好的阴影特征MaxImp;⑦将重要性高于MaxImp的特征标记为“重要”，其它特征标记为“暂定”;⑧删除所有阴影特征;⑨重复此过程，直到所有特征指定重要性，即没有“暂定”特征。

2 改进Boruta算法

2.1 改进算法原理及流程

在创建阴影特征样本时，对每列的全部样本都进行随机重排导致复杂度较高。为提高运行效率，针对样本比例进行改进，改进算法获得阴影特征样本流程如图2所示。

2.3 数据模拟

本改进算法主要体现在扩展数据的阴影特征方面。原算法通过重新排列原始特征值获得阴影特征矩阵，本文通过一组数据模拟展示改进算法与原算法中阴影特征的具体创建过程。

假设有一个5行3列数据，其中[X1]、[X2]、[X3]为原始特征，假设建造阴影特征为[X1]、[X2]、[X3]。将[X1]中的樣本随机重新排列后放入[X1]中，同理可得到[X2]和[X3]的样本，与原始特征合并得到5行6列的扩展数据集，如表1所示。

此时混合样本的复杂度为[（5！）3]，即混合样本中最多有1 728 000种组合，本文提出的改进在于改变建造阴影特征时原始特征值重新排列的比例。

为保证比例选取的随机性，首先将阴影特征打乱，以[X1]、[X2]、[X3]每一行的数据作为一个整体进行行变换，如表2所示。

在5行3列的混合样本中，假设以原算法相同的方法只随机打乱前3行变量得到新的混合样本，与原始样本合并，如表3所示。

3 数值实例

3.1 数据集说明

本文使用的数据集ForestType、Dermatology、Ionosphere、biodeg均来自UCI 数据集（网址为 http：//archive.ics.uci.edu/ml/），每个数据集均随机提取70%～80%之间的数据作为训练集，剩下的数据作为测试集，数据集具体说明见表4。

3.2 Boruta算法改进结果

为检验改进Boruta算法的降维效果，分别对四组数据进行运行实验，首先计算出不使用特征选择算法，以及p值分别从0以0.1为间隔取到1（取1时即为原算法）的改进算法得到的特征数，并使用随机森林作为分类器建立模型，在测试集上检验模型得到预测性能。为避免随机误差的影响，特征数及后续预测皆为计算10次取得的均值，其中，圆圈代表特征数，三角形代表预测性能，见图3-图6。

可以看出，几组数据集在使用改进Boruta算法进行特征选择的情况下，得到的模型预测性能在几种方法中均较高，比使用原始Boruta算法（[p=1]）以及不使用特征选择算法时的模型预测性能更好。在ForestTpye数据集中发现，[p]从0.3～0.4之后特征选择值出现变化，对应预测性能得到提高，特征数为20;而在Dermatology数据集中，改进算法对该数据的特征选择结果与原算法完全相同，特征数为33;在Ionosphere数据集中从0.6～0.7变化时，特征选择结果出现变化，预测性能随之降低，性能最优时特征数为33;在biodeg数据集中，改进算法对该数据的特征选择结果也同样与原算法相同，特征数为31。对4个数据集结果进行分析比较发现，在0.4～0.6区间上，预测性能均达到各自的最高值。归纳发现，不同样本数不同特征数的数据集，代表混合比例的[p]值在区间[0.4，0.6]中取值时，预测性能可达最优。究其原因，随着p值从0.1开始增加，阴影特征样本可提供更多信息，然而随着p值的进一步增大，特别当p值接近于1时，数据冗余反而会降低预测性能。为方便改进算法的使用，不失一般性，取[p]值为区间中值，即0.5。因此得出结论，改进Boruta算法在降低样本复杂度的情况下修正了特征选择结果，使模型得到了更高的预测性能。

3.3 与传统特征选择算法对比

为进一步检验改进的Boruta算法预测性能，选取两种传统特征选择方法与改进Boruta算法进行比较，分别是平均减少不纯度和随机LASSO（改进算法的特征数由[p]=0.5时计算得到）。

（1）计算平均减少不纯度。当训练决策树时，可计算每个特征减少了多少树的不纯度。当训练决策树森林时，则可计算出每个特征平均减少了多少不纯度，并把平均减少的不纯度作为特征选择的值[12-15] 。

（2）随机LASSO[16-18]。该方法使用正则化方法把额外的约束或惩罚项加到已有模型（损失函数）上，以防止过拟合并提高泛化能力。损失函数由原来的[E（X，Y）]变为[E（X，Y）+alpha*||w||]。[w]是模型系数组成的向量，[||.||]一般是[L1]或[L2]范数，[alpha]是一个可调的参数，控制着正则化强度。[L1]正则化时即为Lasso。Lasso能够对变量进行筛选并降低模型的复杂度。这里的变量筛选指不把所有的变量都放入模型中进行拟合，而是有选择地把变量放入模型，从而得到更好的性能参数[19-20]。

由于传统特征选择算法得到的结果为特征重要性排序，因此本文采取如下方式对几种方法进行对比：观察改进Boruta算法选择的[n]个特征，及两种传统算法特征重要性顺序得出的前[n]个特征，记改进Boruta算法和传统算法得到的相同特征占比为特征相符度。以这三组特征分别建立模型得到模型预测性能，如表5所示。

从表5可以发现，在ForestType、Dermatology和biodeg数据集上验证的结果均为改进Boruta算法的结果最优，而Ionosphere数据集的实验结果则与3种方法得出的特征完全相同，得到的模型预测性能也相同。因此，可得出结论：传统算法与改进Boruta算法筛选出相同特征数情况下，改进的Boruta算法效果最佳。

4 结语

数据集存在过多的无用变量影响后续模型，因此特征选择必不可少。本文在研究Boruta算法时发现了阴影特征样本复杂度较高问题，在阴影特征样本构建时选择比例0.4-0.6进行改进，不仅降低了样本复杂度，还修正了特征选择结果，从而得到比原Boruta算法更优的预测性能，在与两种传统的特征选择算法相比较时具有更优的预测结果，因此改进的Boruta算法在成功降低样本复杂度的同时提高了预测性能。至于混合比例为何在0.4～0.6之间会取得较好效果是一个值得进一步研究的问题。

参考文献：

[1] KOHAVI R， JOHN G H.Wrappers for feature subset selection[J]. Artificial Intelligence，1997（3）：273-324.

[2] 周志华. 机器学习[M]. 北京：清华大学出版社，2016.

[3] 李航. 统计学习方法[M]. 北京：清华大学出版社，2012.

[4] 边肇祺，张学工. 模式识别[M]. 第2版. 北京：清华大学出版社，2000.

[5] 姚旭，王晓丹，张玉玺，等. 特征选择方法综述[J]. 控制与决策， 2012，27（2）：161-166.

[6] YAO H，LIU C，ZHANG P，et al. A feature selection method based on synonym merging in text classification system[J]. Eurasip Journal on Wireless Communications & Networking，2017（1）：166-167.

[7] INZA I，LARRA？AGA P，BLANCO R，et al. Filter versus wrapper gene selection approaches in DNA microarray domains[J]. Artificial Intelligence in Medicine，2004， 31（2）：91-103.

[8] 姚登举，杨静，詹晓娟. 基于随机森林的特征选择算法[J]. 吉林大学学报，2014，44（1）：137-141.

[9] PENG H，LONG F，DING C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy[J]. IEEE Transactions pattern analysis and machine intelligence，2005，27（8）：1226-1238.

[10] ZHOU P，HU X，LI P，et al. Online feature selection for high-dimensional class-imbalanced data[J]. Knowledge-Based Systems，2017（136）： 187-199.

[11] SHAO H， LI G，LIU G， et al. Symptom selection for multi-label data of inquiry diagnosis in traditional Chinese medicine[J]. Science China Information Sciences， 2012， 54（1）： 1-13

[12] KURSA MB，RUDNICKI W R. Feature selection with the Boruta package[J].  Journal of Statistical Software，2010，36（11）：1-13.

[13] 郭海山，高波涌，陆慧娟. 基于Boruta-PSO-SVM的股票收益率研究[J]. 传感器与微系统，2018（3）：194-197.

[14] SHAHEEN A，IQBAL J. Spatial distribution and mobility assessment of carcinogenic heavy metals in soil profiles using geostatistics and random forest， Boruta algorithm[J]. Sustainability， 2018， 10（3）：799-780.

[15] BREIMAN L. Random forests， machine learning 45[J]. Journal of Clinical Microbiology， 2001（2）：199-228.

[16] OUSSAR Y. Ranking a random feature for variable and feature selection[J]. Journal of Machine Learning Research，2003（3）：1399-1414.

[17] 师彦文， 王宏杰.  基于新型不纯度度量的代价敏感随机森林分类器[J].  计算机科学，2017， 44（b11）：98-101.

[18] DAMBROSIO A， TUTORE V A. Conditional classification trees by weighting the Gini impurity measure[M].  New Perspectives in Statistical Modeling and Data Analysis， Springer Berlin Heidelberg， 2011：273-280.

[19] KHAN A，BAIG A R. Multi-objective feature subset selection using non-dominated sorting genetic algorithm[J].  Journal of Applied Research & Technology， 2015， 13（1）：145-159.

[20] 李洪成，许金炜，李舰.  机器学习与 R 语言[M]. 北京： 机械工业出版社，2015： 65-67.

[21] 王小宁，刘撷芯，黄俊文.  R 语言实战[M]. 北京： 人民邮电出版社，2016： 363-367.

[22] 刘睿智，杜溦. 基于LASSO变量选择方法的投资组合及实证分析[J].  经济问题， 2012（9）：103-107.

[23] 张秀秀，王慧，田双双，等. 高维数据回归分析中基于LASSO的自变量选择[J]. 中国卫生统计， 2013， 30（6）：922-926.

[24] 胡敏杰，林耀进，王晨曦，等. 基于拉普拉斯评分的多标记特征选择算法[EB/OL]. [2018-08-21]. http：//kns.cnki.net/kcms/detail/51.1307.TP.20180719.1010.014.html

[25] ALHAMZAWI R，HTM A. The Bayesian adaptive Lasso regression[M].  Mathematical Biosciences， 2018.

（責任编辑：杜能钢）