基于隨機森林結合博弈論的特征選擇算法在近紅外光譜分類中的應用研究

孔清清，丁香乾，宮會麗*，李忠任，唐興宏，于春霞

(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 互信息

互信息用來表示兩個隨機變量之間的相關程度?；バ畔⒓瓤梢院饬孔兞恐g的線性關系又能夠衡量變量之間的非線性關系，因此互信息已廣泛應用于機器學習和數據挖掘的特征選擇中[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分類器來說，參數選擇、調優是一個復雜問題，處理不當對分類效果有一定影響。由于樸素貝葉斯假設特征之間相互獨立，因此其分類效果并不理想。徑向基神經網絡會陷入局部最優解，且處理較多樣本時收斂速度慢?？傮w來說，在近紅外光譜數據分類中，隨機森林具有較好的分類識別性能。

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