基于冗余性分析的改進ReliefF特征選擇算法

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

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

0 引言(Introduction)

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

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

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

1.1 Relief算法

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

1.2 ReliefF算法

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

(2)

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

1.3 改進的ReliefF算法

1.3.1 冗余樣本分析

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

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

1.3.2 冗余特征分析

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

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

(3)

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

(4)

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

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算法

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

RFSR算法的主要思想如下。

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

算法1：RFSR算法

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

輸出:特征子集DT。

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

(2)計算各個類別的類中心。

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

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

(5)FORi=1:m。

(6)FORj=1:a。

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

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

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

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

(11)END FOR。

(12)END FOR。

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

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

(15)FOR EACHfiINSi。

(17)END FOR EACH。

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

2 實驗結(jié)果與分析(Experiment and result analysis)

本文選取8個UCI公開數(shù)據(jù)集進行實驗對比(表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ù)據(jù)集

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

表2 實驗一:不同采樣比例下平均準確率對比

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

表3 實驗二:不同特征選擇算法在SVM的分類準確率對比

表4 實驗二:不同特征選擇算法在LightGBM的分類準確率對比

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

3 結(jié)論(Conclusion)

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