基于随机森林结合博弈论的特征选择算法在近红外光谱分类中的应用研究

孔清清，丁香乾，宫会丽*，李忠任，唐兴宏，于春霞

(1.中国海洋大学 信息科学与工程学院，山东 青岛 266100；2.云南中烟工业有限责任公司 技术中心，云南 昆明 650024)

基于随机森林结合博弈论的特征选择算法在近红外光谱分类中的应用研究

孔清清1，丁香乾1，宫会丽1*，李忠任2，唐兴宏2，于春霞2

(1.中国海洋大学 信息科学与工程学院，山东 青岛 266100；2.云南中烟工业有限责任公司 技术中心，云南 昆明 650024)

针对近红外光谱中的噪声和冗余信息导致分类模型识别率低的问题，提出了随机森林结合博弈论的特征选择算法。该算法首先根据随机森林对特征重要性进行度量，优选出对分类具有一定相关性的特征；然后利用改进的夏普利值结合互信息计算优选特征的权重，从加权后的特征集合中去掉冗余得到最优特征子集。为了验证算法的有效性，将其应用于烟叶产地识别模型，实验结果表明，该文所提出的特征选择算法对烟叶产地识别效果较好，分类识别率可达95.88%。

近红外光谱；随机森林；特征选择；夏普利值；产地识别

近红外光谱分析技术具有快速、高效、无损、无害等特点，已被广泛应用于烟草、食品、石油等领域[1-5]。烟叶产地的鉴别对卷烟计算机辅助设计和维护过程起着重要作用。烟叶产地的鉴别大多通过专家感官评吸和化学成分分析，但这些方式不仅增加了工作量，并且会因主观因素导致识别率低[6]。为了解决这些问题，研究者尝试采用近红外模式识别对烟叶产地进行鉴别。如束茹欣等[7]利用主成分分析(PCA)结合支持向量机(SVM)算法建立了近红外烟叶产地识别模型，并与化学成分结合SVM模型、近红外结合SVM模型做了对比。施丰成等[6]采用PLS-DA算法建立近红外烟叶产地识别模型。这些方法大都采用全光谱建立识别模型，或者以PCA降维后的光谱数据进行识别模型的建立。而全光谱含有大量噪声、无关信息、背景信息等，如果这些信息也参与建模则会降低模型的识别率。PCA降维方法能将高维数据降到低维空间中，是对数据的一种压缩方法。从PCA降维后的数据中寻找远小于原数据维度的低维数据，在维度尽可能低的情况下，它们可以最大限度地提供对原始数据更高的贡献率[8-9]。PCA所得到的高贡献率的数据是对表达样本全面的贡献率，对样本某一方面的属性并不一定达到高贡献率水平。

针对上述问题，本文提出基于随机森林结合博弈论的特征选择算法。该算法通过随机森林内置变量的重要性(基尼指数)对全光谱特征进行排序，得到特征重要性较高的特征集合；利用改进的夏普利值结合互信息计算特征集合的每个特征的权重；根据特征权重重新计算特征的重要性，选取识别率最高的特征子集建立模型。夏普利值计算权重时权重大的特征满足两个条件：一是与类别属性相关性较大，二是与所选特征相互作用无冗余。

1 基于随机森林结合博弈论的特征选择算法研究

1.1 随机森林

随机森林是由Breiman[10]提出的集成多个CART决策树的分类方法。该算法首先采用boostrap重采样技术生成多个训练集。然后根据CART算法构建决策树，随机选取若干特征，作为节点的候选特征，并根据基尼指数最小原则，度量各候选特征的重要性。决策树的根节点到每个叶节点均形成一条判断规则。根据判断规则，对样本进行分类。取各决策树分类情况的众数，作为该样本的最终类别归属。样本集和节点候选特征的构成均具有较强的随机性。所以，随机森林不易出现过拟合，具有良好的泛化能力[11-12]。

(1)

其中fij为第j个训练集中第i维特征，i=1,2,…,k。

1.2 夏普利值

夏普利值(Shapley value)是一种博弈论方法。夏普利值用来权衡一个参与者对合作收益产生的贡献，精确地预测每个参与者所能获得的最大收益[13]。通过计算所有可能出现的联盟中参与者的边际贡献，并经过特定加权后得到夏普利值。则n个参与者联盟中第i个参与者的收益φi(v)为：

(2)

其中i=1,2,3,…,|S|,S为包括第i个参与者在内的子联盟，|S|为S的长度。v(S)表示子联盟S的总收益。v(S/i)表示除去第i个参与者S的总收益。夏普利值在本文中用来计算特征权重[14]。

1.3 互信息

互信息用来表示两个随机变量之间的相关程度。互信息既可以衡量变量之间的线性关系又能够衡量变量之间的非线性关系，因此互信息已广泛应用于机器学习和数据挖掘的特征选择中[15-16]。两个随机变量X和Y的联合概率分布为p(x,y)，这两个随机变量的互信息定义为MI(X；Y)。

(3)

条件互信息为给出随机变量Z，随机变量X和Y之间的信息量。条件互信息CMI(X；Y|Z)定义为：

(4)

本文互信息用来衡量特征fj与类别的互信息MI(fj;class)，以及在特征fi已知条件下特征fj与类别之间的互信息CMI(fj;class|fi)。

1.4 本文算法

本文算法首先根据随机森林的特征重要性评分对所有特征进行排序并选取大于设定阈值的特征，该条件下噪声和无关信息会被删除，但剩余特征仍含有冗余信息；为了消除冗余信息，利用改进的夏普利值结合互信息计算特征权重，根据特征权重重新计算特征重要性评分，并根据新的特征重要性评分筛选出无冗余的特征子集。本文算法的具体步骤如下：

Step 2将式(2)表示为如下方式：

(5)

Δi(S)=v(S)-v(S/i)

(6)

本文特征fi的权重表示为ωi且令ωi=φi(v)。用夏普利值表示特征权重，改进夏普利值，令Δi(S)表示为：

(7)

其中Ψ(i,j)表示特征fi和特征fj是否是依存关系。Ψ(i,j)定义为：

(8)

根据公式(7)、(8)，既可以保证特征fj与类的相关性，又保证了特征fi与所选特征一半以上的特征相互作用，因此包含冗余信息的冗余特征不会被选择。

Step 4根据特征权重重新计算特征重要性评分并降序排序。新的特征重要性评分S′(i)表示为：

S′(i)=ωi×S(i)

(9)

Step 5采用折半查找搜索方式寻找最优特征子集。首先将S′集合的所有特征建立分类模型，其类别识别率设为A0。降序排序后的集合S′，每一特征所在点的特征集合为包含此特征和此特征之前的所有特征，然后以识别率为比较标准，折半查找拥有最高识别率Ah所对应的特征子集。折半查找时，满足条件Anext>Acurrent>Asymmetry。Anext为下一个确定搜索的特征集合的识别率，Acurrent为当前搜索的特征集合的识别率，Asymmetry为以current特征集合点为对称点与next特征集合对称的特征集合的识别率。

2 实验部分

2.1 仪 器

实验使用丹麦FOSS公司生产的Foss DS2500光谱仪，光谱采样间隔0.5 nm，光谱扫描范围1 100～2 500 nm，分辨率为8 nm，扫描次数64次。

2.2 样本制备

选取山东潍坊、临沂、日照、莱芜、淄博、青岛6个产区的2011～2016年500个烟叶样本。采用烘箱法制备样品，将样品置于烘箱中，60 ℃干燥4 h，然后磨粉过60目筛，每个样品称重15 g。

2.3 光谱采集与数据处理

光谱采集：待光谱仪自检通过后，将粉末样品置于样品杯中，放入光谱仪上进行扫描。每个样品重复测定3次，取3次测定的平均光谱数据为每个样品的最终光谱数据。

光谱预处理：选用Norris Gap一阶导数加5个数据点平滑的光谱预处理方法，以Unscrambler 9.7软件对数据进行预处理。

实验数据集：随机选取样本集的2/3为训练集，1/3为测试集。算法模型训练与预测使用Matlab2010软件。

图1 各个产地烟叶样品的光谱图Fig.1 Raw spectra of tobacoo leaf samples from different production areas1.Weifang,2.Zibo,3.Laiwu,4.Linyi,5.Qingdao,6.Rizhao

图2 特征数与识别率关系Fig.2 The relationship between the number of features and recognition rate

图3 本文算法选择的特征Fig.3 The features selected by algorithm in this paper

3 结果与讨论

根据实验部分所述，得到各个产地烟叶样品的光谱图。图1为随机选取的潍坊(Weifang)、淄博(Zibo)、莱芜(Laiwu)、临沂(Linyi)、青岛(Qingdao)、日照(Rizhao)上部烟叶的原始光谱图。

全光谱共2 800个特征波数。根据“1.4”算法，特征重要性阈值设为0.025，得到特征重要性≥0.025的特征数为519。对这519个特征计算特征权重，夏普利值计算特征权重时考虑特征冗余，因此冗余特征权重会被削弱。将特征权重与特征重要性相乘得到新的特征重要性。对新的特征重要性降序排序，以分类识别率为依据折半查找最优特征子集。折半查找的特征数量与测试集识别率之间的关系如图2所示。图2中的18个点表示不同特征数对应的分类模型所取得的识别率，即折半查找算法共搜索了18个特征集合。折半查找算法明显降低了特征搜索复杂度，能够快速搜索出拥有最高识别率的特征集合。图2中有最高识别率的特征个数为144，最高为95.88%。算法所得144个特征见图3。

本文算法所建立的分类模型的测试集混淆矩阵如表1所示，测试样本共170个，被正确分类的样本163个，被错误分类的样本7个。在错误分类中，潍坊有1个被分到淄博；淄博有1个被分到莱芜；临沂有1个被分到临沂，1个被分到青岛；青岛有1个被分到淄博，1个被分到临沂；日照1个被分到淄博。

以本文算法选择的特征、全光谱、大于μ的特征以及常用波长变量选择的遗传算法(Genetic algorithm，GA)建立随机森林(RF)、支持向量机(SVM)、朴素贝叶斯(Naive Bayes，NB)和径向基神经网络(RBF Network) 4种不同分类器的分类模型识别率如表2所示。

从表2可以看出，全光谱所建立各分类模型的识别率最低，本文算法选择的特征建立的随机森林分类模型识别率最高，说明本文算法具有较好的性能。全光谱不仅含有大量的噪声、冗余信息，还包含了大量的背景信息和仪器误差信息等无关、干扰信息，会大大降低模型的识别率。从全光谱建立的分类模型的识别率来看，随机森林较其他3种分类器表现较好，这也说明随机森林具有良好的容噪能力，处理高维、非线性关系数据表现较为理想。由于根据特征重要性大于设定阈值，删除了小于阈值的大量噪声、无关信息、背景信息，因此特征重要性较大的特征集合建立的模型识别率与全光谱建立的模型识别率相比明显提高。但大于阈值的特征集合中包含了冗余信息，而本文算法通过降低冗余特征的权重，从而减少了冗余信息对识别率的影响。这是与消除冗余信息的方法相比，大于阈值特征集合所建立模型的识别率较低的原因。遗传算法在高维数据中存在易陷入局部最优的问题。从表2中可见，以遗传算法所选特征建立的各个模型的识别率均低于本文方法。本文通过选取与样本类别相关性较强且无冗余的特征进行建模，避免了一些特征选择方法的缺点。

表1 测试集混淆矩阵Table 1 The confusion matrix of test set

表2 不同特征选择方法在不同分类器模型下的识别率(%)Table 2 The recognition rates of different feature selection methods under different classifier models(%)

从表2分类器角度来看，随机森林分类器无论是全光谱建模还是特征选择后建模，均优于其他3种分类器的分类效果。就SVM分类器来说，参数选择、调优是一个复杂问题，处理不当对分类效果有一定影响。由于朴素贝叶斯假设特征之间相互独立，因此其分类效果并不理想。径向基神经网络会陷入局部最优解，且处理较多样本时收敛速度慢。总体来说，在近红外光谱数据分类中，随机森林具有较好的分类识别性能。

4 结 论

本文提出基于随机森林结合博弈论的特征选择算法，利用随机森林分类模型泛化能力强、训练速度快等优势，建立了烟叶产地模式识别模型。与其他方法相比，本方法对烟叶产地识别有较高的分类识别率,证明了其有效性。本方法建立的具有良好性能的产地识别模型能够为卷烟配方设计与维护、质量分析提供更好的思路和一定的参考价值。如何进一步使模型更简单、高效是未来研究的重点方向。

[1] Xu X G,Zhao C J,Wang J H,Li C J,Yang X D.J.InfraredMillim.Waves(徐新刚，赵春江，王纪华，李存军，杨小冬.红外与毫米波学报),2013,32(4):351-358.

[2] Xia J,Lu Y,Su Y,Pan L,Lin K,Zhu S X,Lu M H.ActaTabaccoSin.(夏骏，陆扬，苏燕，潘力，林垦，朱书秀，陆明华.中国烟草学报),2015,21(2):19-22.

[3] Huang C Y,Fan H B,Liu F,Xu G R.J.Instrum.Anal.(黄常毅，范海滨，刘飞，许赣荣.分析测试学报),2014,33(5):520-526.

[4] Qin Y H,Gong H L.InfraredPhysics&Technology,2016,77:239-243.

[5] Liang L,Fang G G,Wu T,Cui H H,Zhang X M,Zhao Z Y.J.Instrum.Anal.(梁龙，房桂干，吴珽，崔宏辉,张新民，赵振义.分析测试学报),2016,35(1):101-106.

[6] Shi F C,Li D L,Feng G L,Song G F,Zhou Z G.TobaccoSci.Technol.(施丰成，李东亮，冯广林，宋光富，周志刚.烟草科技),2013,4:56-59.

[7] Shu R X,Sun P,Yang K,Zhang J P,Liu T A.TobaccoSci.Technol.(束茹欣，孙平，杨凯，张建平，刘太昂.烟草科技),2011,11:50-57.

[8] Zeng B,Li Y Z,Liu Z Q,Feng J H,Zhang J H,Pan M M.PowerSystemTechnology(曾博，李英姿，刘宗岐，冯家欢，张建华，潘明明.电网技术),2016,40(2):396-404.

[9] Li W,Hu B,Wang M W.Spectrosc.SpectralAnal.(李武，胡冰，王明伟.光谱学与光谱分析),2014,34(12):3235-3240.

[10] Breiman L.MachineLearning,2001,45(1):5-32.

[11] Jang S,Park S H,Baek J G.ExpertSyst.Appl.,2017,71:358-369.

[12] Winham S J,Freimuth R R,Biernacka J M.Stat.Anal.DataMin.,2013,6(6):496-505.

[13] Sasikala S,Balamurugan S A A,Geetha S.AppliedSoftComputing,2016,49:407-422.

[14] Sun X,Liu Y H,Li J,Zhu J Q,Liu X J,Chen H L.Neurocomputing,2012,(97):86-93.

[15] Wu Y,Liu Y H.ApplicationResearchofComputers(吴雨，刘媛华.计算机应用研究).[2017-01-23].http://www.arocmag.com/article/02-2017-12-039.html.

[16] Fan X L,Feng H H,Yuan M.ControlandDecision(范雪莉，冯海泓，原猛.控制与决策),2013,28(6):915-919.

Research on Application of Feature Selection Algorithm Based on Combination of Random Forest and Game Theory in Near Infrared Spectroscopy

KONG Qing-qing1，DING Xiang-qian1，GONG Hui-li1*，LI Zhong-ren2，TANG Xing-hong2，YU Chun-xia2

(1.College of Information Science and Engineering,Ocean University of China,Qingdao 266100, China；2.Technical Research Center,China Tobacco Yunnan Industrial Co.,Ltd.,Kunming 650024,China)

The feature selection algorithm based on the combination of random forest and game theory was proposeed in this paper as noise and redundant information in the near infrared spectroscopy would lead to the low recognition rate of a model.This algorithm was first used to measure the feature significance according to the random forest and select some features related to classification,then compute the weights of selected characters by using the improved Shapley values and mutual information computed to remove redundant information from the weighted feature set and get the optimal feature subset.To validate effectiveness of this algorithm,the tobacco leaf production area identification model was established.The experimental results indicated that the algorithm proposed in this paper had a good recognition on the area of tobacco leaf production with a recognition rate of 95.88%.

NIR spectroscopy；random forest；feature selection；shapley value；production area identification

10.3969/j.issn.1004-4957.2017.10.006

O657.3；O433.4

A

1004-4957(2017)10-1203-05

2017-05-22；

2017-07-18

国家科技支撑计划项目(2015BAF12B01)；云南中烟工业有限责任公司项目(JSZX2014YL01，20530001020152000086)

*

宫会丽，博士，高级工程师，研究方向：近红外光谱分析、数据挖掘，Tel:0532-85902968，E-mail:huiligong@163.com