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

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

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

0 引言(Introduction)

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

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

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

1.1 Relief算法

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

1.2 ReliefF算法

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

(2)

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

1.3 改進的ReliefF算法

1.3.1 冗余樣本分析

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

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

1.3.2 冗余特征分析

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

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

(3)

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

(4)

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

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

(5)

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

(6)

1.3.3 RFSR算法

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

RFSR算法的主要思想如下。

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

算法1：RFSR算法

輸入:訓練集D,取樣次數a,各類樣本選取比例b%,特征個數m,最近鄰數k,劃分區段個數h,每個區段內特征個數m′,第i個分段的采樣比例Pi,i=1,2,…,h,特征權重向量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)根據公式(1)更新特征權重w(i)。

(11)END FOR。

(12)END FOR。

(13)根據特征權重排序,得到特征權重序列S。

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

(15)FOR EACHfiINSi。

(17)END FOR EACH。

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

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

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

表1 實驗數據集

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

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

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

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

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

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

3 結論(Conclusion)

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