李麗君, 張海清, 李代偉, 向筱銘, 于 曦

(1.成都信息工程大學(xué)軟件工程學(xué)院, 四川 成都 610225;2.四川省氣象探測數(shù)據(jù)中心, 四川 成都 610072;3.成都大學(xué)斯特靈學(xué)院, 四川 成都 610106;4.四川省信息化應(yīng)用支撐軟件工程技術(shù)研究中心, 四川 成都 610255)

0 引言(Introduction)

特征選擇是機(jī)器學(xué)習(xí)以及數(shù)據(jù)挖掘領(lǐng)域?qū)崿F(xiàn)特征約簡的重要方法,通過在眾多特征中篩選出對分類最有效的特征實(shí)現(xiàn)對特征維數(shù)的約簡。ReliefF算法[1]是在Relief特征選擇算法[2]的基礎(chǔ)上對處理多分類問題提出的改進(jìn),但仍存在一些有待解決的問題,例如ReliefF隨機(jī)抽樣時(shí)會(huì)抽取到不具代表性的樣本,沒有考慮特征間的相關(guān)性,缺乏對冗余特征進(jìn)行衡量。針對以上問題,陳平華等[3]以互信息度量特征冗余。項(xiàng)頌陽等[4]將ReliefF與RFE(Recursive Feature Elimination,特征遞歸消除)結(jié)合對冗余特征進(jìn)行遞歸篩選。薛瑞等[5]引入量子粒子群算法對特征集二次篩選剔除冗余特征。張小內(nèi)等[6]結(jié)合ReliefF和Pearson系數(shù)的相關(guān)性原理進(jìn)行特征篩選。此外,已有的對特征間相關(guān)性度量的算法評價(jià)方式過于單一。

本文提出一種兩階段特征選擇算法:①針對樣本冗余問題,對ReliefF算法抽樣策略進(jìn)行改進(jìn),第一階段保留距各類別中心較近的樣本為隨機(jī)抽樣候選集,保證抽取樣本的有效性;②針對特征間冗余問題,第二階段將改進(jìn)抽樣策略后的ReliefF算法所得特征權(quán)重序列劃分為多個(gè)區(qū)段,在區(qū)段內(nèi)進(jìn)一步衡量特征間相關(guān)性,剔除冗余特征;③引入最大信息系數(shù)(Maximal Information Coefficient, MIC)[7]及Pearson相關(guān)系數(shù)共同實(shí)現(xiàn)冗余特征的度量;④根據(jù)特征權(quán)重序列,從高到低給各區(qū)段設(shè)置采樣比例,同時(shí)在縮減特征維數(shù)的基礎(chǔ)上,防止剔除有效特征。

1 ReliefF算法及其改進(jìn)(ReliefF algorithm and its improvement)

1.1 Relief算法

其中:w(j)表示第j個(gè)特征的權(quán)重,m為隨機(jī)抽取樣本次數(shù),函數(shù)diff(·)用于計(jì)算在第j個(gè)特征下兩樣本點(diǎn)的差值。

1.2 ReliefF算法

1994年Knonenko提出Relief擴(kuò)展算法ReliefF[1],改進(jìn)后的算法可用于處理多分類問題。ReliefF公式中針對隨機(jī)選取的樣本是從其同類和異類樣本中查找k個(gè)近鄰樣本,通過求均值更新特征權(quán)重,其公式如下:

(2)

其中:Ri為隨機(jī)抽取的樣本;p(c)為類c的先驗(yàn)概率,即類c在樣本中所占的比例。

1.3 改進(jìn)的ReliefF算法

1.3.1 冗余樣本分析

計(jì)算特征權(quán)重時(shí),ReliefF算法需要在整個(gè)樣本集中進(jìn)行隨機(jī)樣本的抽取,根據(jù)所抽樣本與其近鄰樣本的距離,按照一定規(guī)則更新特征權(quán)重,隨機(jī)抽取的樣本中存在一些冗余的、不具代表性的樣本會(huì)一定程度地影響分類結(jié)果。

針對上述問題,本文對ReliefF隨機(jī)抽樣策略進(jìn)行改進(jìn),在保持抽樣隨機(jī)性不變的前提下,計(jì)算各類樣本與其類別中心的距離,保留距離所屬類別中心較近的部分樣本作為隨機(jī)抽樣的候選集,實(shí)現(xiàn)對樣本抽樣范圍的縮減,從而避免抽取到一些冗余的、不具代表性的樣本,可有效改進(jìn)ReliefF算法衡量特征權(quán)重的準(zhǔn)確度和最終分類性能。

1.3.2 冗余特征分析

ReliefF通過特征與標(biāo)簽相關(guān)性度量權(quán)重,但強(qiáng)相關(guān)特征間可能存在冗余[8-9]。故本文引入MIC及Pearson相關(guān)系數(shù)分別從信息論[10]和相關(guān)性度量[11]兩個(gè)方面出發(fā)共同度量冗余特征。同時(shí),使用兩種度量方式避免算法衡量特征相關(guān)性時(shí)受限于某一度量標(biāo)準(zhǔn)的局限性和盲目性。

MIC由RESHEF等[7]提出,假定存在變量X、Y,其最大信息系數(shù)計(jì)算公式如下:

(3)

Pearson相關(guān)性系數(shù)主要用于衡量兩變量間的相關(guān)程度,其中X、Y表示兩個(gè)待測變量,P為兩個(gè)變量的相關(guān)系數(shù),r值在-1～1,其絕對值越大,表示兩個(gè)變量間相關(guān)性越大,Pearson系數(shù)計(jì)算公式如下:

(4)

本文對冗余特征的判斷使用MIC和Pearson相關(guān)系數(shù)共同作為評價(jià)指標(biāo),將冗余性計(jì)算公式定義如下:

PM(X,Y)=α·|P(X,Y)|+β·MIC(X;Y)

(5)

假定給定一組特征集F={f1,f2,…,fm},其中?fi∈F,i=1,2,…,m,特征fi的冗余性大小即為特征與子集中其他特征相關(guān)性之和,將其定義如下:

(6)

1.3.3 RFSR算法

基于上文對樣本冗余及特征冗余性的分析,本文在改進(jìn)樣本抽樣策略的基礎(chǔ)上衡量兩兩特征之間的相關(guān)性,通過將原始特征劃分為若干個(gè)區(qū)段,對不同區(qū)段分別剔除冗余特征,提出基于冗余性分析的ReliefF算法(ReliefF Feature Selection Algorithm Based on Analysis of Redundancy,RFSR)。

RFSR算法的主要思想如下。

(1)計(jì)算樣本與所屬類中心的距離,僅保留距每類中心較近樣本作為ReliefF隨機(jī)抽樣的候選樣本集,縮小隨機(jī)抽樣范圍,避免抽取到冗余樣本;(2)使用ReliefF算法衡量權(quán)重,得到特征權(quán)重序列;(3)根據(jù)所得權(quán)重序列將特征進(jìn)行分段,并從高到低地設(shè)置采樣比例;(4)在各區(qū)段中,使用Pearson相關(guān)系數(shù)及MIC組合計(jì)算特征間的相關(guān)性并升序排序,根據(jù)所設(shè)采樣比率剔除冗余特征,從不同區(qū)段獲取特征集,保證各子集的多樣性。該算法在確保得到更多與標(biāo)簽強(qiáng)相關(guān)特征的前提下,剔除出冗余性較高的特征,避免使用單一度量方式時(shí)的局限性和盲目性,兼顧特征重要性及冗余性的關(guān)系。改進(jìn)算法偽代碼如下。

算法1：RFSR算法

輸入:訓(xùn)練集D,取樣次數(shù)a,各類樣本選取比例b%,特征個(gè)數(shù)m,最近鄰數(shù)k,劃分區(qū)段個(gè)數(shù)h,每個(gè)區(qū)段內(nèi)特征個(gè)數(shù)m′,第i個(gè)分段的采樣比例Pi,i=1,2,…,h,特征權(quán)重向量W。

輸出:特征子集DT。

(1)初始化w(i)=0。

(2)計(jì)算各個(gè)類別的類中心。

(3)計(jì)算每個(gè)樣本與各自類中心的距離。

(4)按距離由小到大對類別樣本進(jìn)行排序,取各序列中前b%的樣本組成D′。

(5)FORi=1:m。

(6)FORj=1:a。

(7)在D′中隨機(jī)抽取樣本Ri。

(8)找到與Ri同類的k個(gè)最近鄰樣本NHi。

(9)對c≠class(Ri),分別找到與Ri不同類的k個(gè)最近鄰樣本NMi。

(10)根據(jù)公式(1)更新特征權(quán)重w(i)。

(11)END FOR。

(12)END FOR。

(13)根據(jù)特征權(quán)重排序,得到特征權(quán)重序列S。

(14)將特征序列S平均劃分為h個(gè)區(qū)段,其中Si表示第i個(gè)區(qū)段。

(15)FOR EACHfiINSi。

(17)END FOR EACH。

(18)將各區(qū)段中所得特征子集合并形成一組新的特征集DT。

2 實(shí)驗(yàn)結(jié)果與分析(Experiment and result analysis)

本文選取8個(gè)UCI公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)對比(表1)。其中:WDBC為Breast Cancer Wisconsin (Diagnostic)數(shù)據(jù)集,QSAR為QSAR biodegradation,Wine為Winequality-red,Genus為Frogs calls-genus(genus),Family為Frogs calls-family(family),Heart為Statlog(Heart)[12]。

表1 實(shí)驗(yàn)數(shù)據(jù)集

為驗(yàn)證改進(jìn)算法的有效性,本文進(jìn)行兩組實(shí)驗(yàn),均采用10次10折交叉驗(yàn)證,將10次實(shí)驗(yàn)的分類準(zhǔn)確率均值作為評價(jià)指標(biāo),并保留距各類中心較近的前20%的樣本,將冗余性度量公式(5)中的α、β值均設(shè)為0.5。實(shí)驗(yàn)一中,將不同劃分區(qū)段、采樣比例在不同數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)對比,對10次實(shí)驗(yàn)所得分類準(zhǔn)確率求均值,實(shí)驗(yàn)一所得結(jié)果如表2所示。其中:RFSR-6211和RFSR-532分別指劃分為4個(gè)子集和3個(gè)子集,并將采樣比例分別設(shè)置為{0.6,0.2,0.1,0.1}和{0.5,0.3,0.2};加粗?jǐn)?shù)據(jù)為最好結(jié)果,帶下劃線數(shù)據(jù)為第二好結(jié)果。

表2 實(shí)驗(yàn)一:不同采樣比例下平均準(zhǔn)確率對比

由表2可看出:從區(qū)段劃分來看,將特征劃分為3個(gè)子集的分類效果整體上要優(yōu)于4個(gè)子集;從采樣比例來看,采樣比例設(shè)置為{0.6,0.3,0.1}時(shí),分類效果提升更明顯;第一個(gè)子集采樣占比較高時(shí),所得分類準(zhǔn)確率相對較高,還要兼顧后續(xù)區(qū)段減少特征冗余對分類效果的影響。根據(jù)實(shí)驗(yàn)一所得結(jié)論,實(shí)驗(yàn)二將特征序列劃分為3個(gè)子集,采樣比例設(shè)置為{0.6,0.3,0.1}。將需預(yù)設(shè)特征個(gè)數(shù)的對比算法特征數(shù)設(shè)置為在該比例下所獲得的特征數(shù),把RFSR與ReliefF、MIM、mRMR、RF、CFS以及改進(jìn)算法ReliefF-REF[4]和ReliefF-Pearson[6]分別在SVM以及LightGBM的平均分類準(zhǔn)確率進(jìn)行對比。實(shí)驗(yàn)二的實(shí)驗(yàn)結(jié)果如表3、表4所示。

表3 實(shí)驗(yàn)二:不同特征選擇算法在SVM的分類準(zhǔn)確率對比

表4 實(shí)驗(yàn)二:不同特征選擇算法在LightGBM的分類準(zhǔn)確率對比

綜上可以看出,RFSR算法在大多情況下的分類準(zhǔn)確率優(yōu)于其他幾種特征選擇算法,除在Sonar、QSAR數(shù)據(jù)集上RFSR算法的分類準(zhǔn)確率稍低于RF等外,在其他數(shù)據(jù)集上的分類效果明顯更具優(yōu)勢;與經(jīng)典ReliefF、mRMR、RF、MIM、CFS算法相比,RFSR算法所選特征分類性能更好,并且均高于改進(jìn)算法ReliefF-RFE、ReliefF-Pearson;從分類器選擇來看,LightGBM模型分類準(zhǔn)確率整體高于SVM支持向量機(jī),RFSR算法使用LightGBM在減少特征維度的同時(shí),有效地提高了分類準(zhǔn)確率;RFSR相較于傳統(tǒng)ReliefF算法,在不同數(shù)據(jù)集上的分類準(zhǔn)確率均有提升,在SVM的不同數(shù)據(jù)集上的分類準(zhǔn)確率分別提升0.92%～9.06%,在LightGBM的分類準(zhǔn)確率分別提升0.63%～12.10%,在一定程度上改進(jìn)了ReliefF算法的分類性能。

3 結(jié)論(Conclusion)

本文首先對ReliefF算法抽樣策略進(jìn)行改進(jìn),通過計(jì)算類中心縮減隨機(jī)抽取樣本的范圍。針對特征間冗余問題,將特征序列劃分多個(gè)子集,通過兩種相關(guān)系數(shù)共同衡量特征相關(guān)性,使ReliefF同時(shí)兼顧特征與標(biāo)簽及特征間的關(guān)系,消除冗余特征的不良影響。在8個(gè)UCI數(shù)據(jù)集上展開實(shí)驗(yàn)對比,通過實(shí)驗(yàn)確定參數(shù)設(shè)置,同時(shí)分別在SVM及LightGBM上將改進(jìn)算法與其他幾種算法進(jìn)行對比。結(jié)果表明:改進(jìn)算法在降低特征維度的同時(shí),能有效提高分類準(zhǔn)確率,但算法沒考慮不平衡數(shù)據(jù)及算法穩(wěn)定性問題,若不同類別樣本數(shù)量差異較大,則可能會(huì)影響算法性能。未來,會(huì)從不平衡數(shù)據(jù)性質(zhì)出發(fā),進(jìn)一步對算法性能提升展開研究。