基于多評價準則融合的特征選擇方法

于寧寧，劉 剛，劉 森，曹冰許

(河南科技大學 信息工程學院，河南 洛陽 471023)

0 引 言

特征選擇是以提高分類效率為目的，選擇最優特征子集的過程[1]。特征選擇方法有Wrapper和Filter兩種方式[2]。其中Filter方式的評價準則主要包括：互信息[3]、ReliefF算法[4,5]、類可分性法[6,7]、Fisher比率[8]、相關性[9]等。然而，Filter方式采用單評價準則，并不能全面評價特征集的優劣。將不同的評價準則借助信息融合方式進行融合，使其取長補短便成為研究的熱點。李曉等[10]提出選擇精度有所提高的融合選擇方法；吳迪[11]利用融合方式獲取組合證據體的最終評價結果。但是這兩種方法均存在融合重要性權值系數主觀確定的問題。

在本文的研究中，首先利用ReliefF算法、互信息和類可分性法3種評價準則分別對特征進行評價；然后，為克服特征重要性權值系數確定的主觀性，利用序關系分析法[12,13]確定3個評價準則的重要性權值系數，采用多評價準則的融合模型綜合評價結果；最后利用支持向量機從融合后的特征集中選擇出最優的特征子集。

1 特征選擇方法概要

特征選擇主要研究從已知的特征集中，利用各種評價準則選擇最優子集，達到降低計算代價、提高分類性能的目的。

1.1 ReliefF算法

Kononerko為了解決多分類問題和回歸問題，提出ReliefF算法。它的核心是依據權重選擇特征，選出與類別相關性強的特征，而相關性弱的特征彼此遠離。其計算公式定義如下

(1)

式中：i、W[i]、m、Rs、p(C)、near_hitj、near_missj的定義請參見文獻[10]。

使用權值作為ReliefF算法的評估值，當其權值大于0的時候，表示特征是相關的；當其權值小于0的時候，表示特征不相關。

1.2 類可分性法

類可分性法是通過計算類內和類間的距離之比。它的特點是計算方法簡單，計算效率較高

(2)

(3)

(4)

分子表示類內的歐式距離，其值越小越好，分母表示類間的歐式距離，越大越好。因此，J(i)越大，表示該特征的分類能力越強。

1.3 互信息

兩個變量的互信息指兩個特征共同含有的信息量：在已知一個變量的前提下，另外一個變量在不確定度方面的減少量。這個不確定度使用信息熵來度量。假設一個數據集D，它是由n個特征 (f1,f2,…,fn) 表示N個實例。使用概率函數p(ft)表示特征ft為不同可能值ft的概率。離散特征ft的信息熵H(ft)表示如下

(5)

在已知另一個特征c的取值之后，ft取值的不確定度可以由條件熵H(ft|c) 來度量

(6)

在此基礎上，特征ft與特征c的互信息定義為

I(c;ft)=H(ft)-H(ft|c)=I(ft;c)

(7)

最后，分別計算每個特征與其余特征的總體互信息即score(ft)，可以表示為

(8)

可見，特征的總體互信息越大，表示特征包含的信息越多，特征也就越重要。

2 基于多評價準則融合的特征選擇方法

為了發揮每個評價準則的優點，把不同的評價準則相互融合。本文提出基于多評價準則融合特征選擇方法，其框架如圖1所示。

圖1 基于多評價準則融合的特征選擇方法框架

2.1 多評價準則融合模型

在特征選擇過程中，分別采用ReliefF算法、互信息和類可分性法3種評價原則對特征進行排序。這3種評價原則均是計算的權值越大，該特征的分類性能越強，那么權值越大的特征的排序序號就越小。根據權值大小進行降序排列，得到3個排序結果，分別表示如下

Sort(ReliefF)=[SR(1),SR(2),…,SR(i),…，SR(N)]

(9)

Sort(類可分性法)=[SJ(1),SJ(2),…,SJ(i),…,SJ(N)]

(10)

Sort(互信息)=[SH(1),SH(2),…,SH(i),…，SH(N)]

(11)

其中，N表示為原始特征空間的特征維數，SR(i)、SJ(i)和SH(i)分別表示在ReliefF算法、互信息和類可分性法3種準則下第i個特征在N維特征集中的權重排序序號。

將ReliefF算法、互信息和類可分性法3種準則的排序結果通過添加重要性權值系數的方法進行融合處理，得到綜合排序結果，表示如下

SortF,J,H=[S(1),S(2),…,S(i),…,S(N)]

(12)

S(i)=ω1SR(i)+ω2SJ(i)+ω3SH(i)

(13)

在式(13)中，ω1、ω2和ω3分別表示不同評價準則的重要性權值系數。S(i)是經過融合處理后第i個特征在N維特征集中的權重排序序號。

2.2 基于序關系分析法的重要性權值系數的確定

序關系分析法是基于層次分析法改進的計算權值方法，是一種定性和定量相結合、層次化的分析方法。它因無需構建判斷矩陣和一致性檢驗使計算量減小；在應用中對評價方案個數沒有限制，可以規避層次分析法的弊端。它的具體算法如下：

(1)確定3種評價準則的序關系。針對3種評價準則的重要性程度進行判斷；按照3個評價準則的重要程度，列出3種評價準則的序關系，如下所示

U1?U2?U3

(14)

式中：由于ReliefF算法和類可分性法是根據特征對樣本類別的區分能力來評價特征的重要性，而互信息是根據特征與特征間所含有的信息量大小來評價特征的重要性，所以從分類性能角度考慮，ReliefF算法和類可分性法的重要性程度比互信息大；ReliefF算法核心是根據被選擇的樣本和兩個最近鄰樣本間的距離來評價特征，運行效率高，而類可分性法僅根據類內和類間的歐式距離來進行特征評估，因此從分類性能角度考慮，ReliefF算法比類可分性法的重要性程度大。據此，U1、U2、U3分別指ReliefF算法、類可分性法和互信息。

(2)確定兩個相鄰評價準則間的重要性程度之比的理性判斷值。對評價準則Up-1和Up的重要程度之比ri進行理性判斷，ri的賦值參考表請參見文獻[13]。ri重要性程度之比公式如式(15)所示

(15)

根據式(15)和ri的重要性程度之比的賦值參考表，對3種評價準則的序關系中相鄰準則的重要性程度之比進行理性判斷，其判斷值分別為

(3)計算重要性權值系數。評價準則的重要性權值系數和其在序關系中相應位置的重要性權值系數是對應一致的。重要性權值系數的計算公式為

(16)

ωp-1=rp×ωp

(17)

根據式(16)和式(17)，計算可以得到

據此，可以獲得式(12)中3種評價準則的重要性權值系數。將重要性權值系數代入式(13)，即可得到特征融合排序值，進而得到綜合排序。

在綜合排序的基礎上，利用支持向量機實現最終特征選擇結果。

3 實驗與討論

為了測試本文提出的基于Filter方式的多評價準則融合的特征選擇方法的分類能力的高效性和性能的穩定性，本文利用UCI數據集的Iris、Wine和Ionosphere 這3個數據集設計實驗。在3個實驗中，采用支持向量機分類器，實驗均重復50次，采用實驗的平均值作為最終結果；測試樣本分為兩部分：訓練樣本和驗證樣本；采用Intel i5的CPU、4 G的內存的測試環境；針對上述3種評價準則分別進行實驗；使用式(13)的加權參數規則和利用式(16)、式(17)計算出的重要性權值系數進行本文所提方法的實驗。

3.1 基于Iris數據集的實驗

為驗證本文所提出的方法，本實驗采用Iris數據集。擁有150個數據樣本的數據集被分為每類含有50個樣本點的3種類別的鳶尾花，而每個樣本點包含4個屬性特征，分別用來描述鳶尾花的花萼和花瓣的長度、寬度。首先從3個類別樣本中分別隨機抽取60%(合計90個)作為訓練樣本，剩余的40%(合計60個)作為測試樣本。實驗結果如表1、表2和圖2所示。

表1 數據集Iris的排序實驗結果

表2 數據集Iris的實驗分類結果

圖2 各種評價原則的特征選擇方法的結果比較

在表1中，顯示特征的重要性排序序號。其中特征3和特征2融合處理后的重要性排序序號為1和4，說明特征3的重要性權重最大，對分類的貢獻最大；特征2的重要性權重最小，對分類的貢獻就最小。

3.2 基于Wine數據集的實驗

為驗證本文所提出的方法，本實驗采用Wine數據集。它包含有178個數據樣本，一共分為3類葡萄酒，分別為59、71、48個數據樣本點，每個數據包含13個屬性，分別從色調、堿度、顏色強度、所含蘋果酸、原花青素等角度描述葡萄酒。首先從3個類別樣本中分別隨機抽取60%(合計99個)作為訓練樣本，剩余的40%(合計79個)作為測試樣本。實驗結果如表3～表5和圖3所示。

表3 數據集Wine的排序實驗結果

表4 數據集Wine的排序實驗結果

表5 數據集Wine的實驗分類結果

圖3 各種評價原則的特征選擇方法的結果比較

在表3、表4中，顯示特征的重要性排序序號。其中特征2和特征6融合處理后的重要性排序序號為1和13，說明特征2的重要性權重最大，對分類的貢獻最大；特征6的重要性權重最小，對分類的貢獻就最小。

3.3 基于Ionosphere數據集的實驗

為驗證本文所提的方法，本實驗采用Ionosphere數據集。它是一個二元分類問題的電離層數據集，它需要根據給定的電離層中的自由電子的雷達回波預測大氣結構。該數據集包含了表示陰性和陽性的2個類別、17對雷達回波數據即34維特征和有351個樣本點，其中第一類樣本點為225個，第二類樣本點為126個。首先從兩個類別樣本中分別隨機抽取60%(合計211個)作為訓練樣本，剩余的40%(合計140個)作為測試樣本。實驗結果如表6和圖4所示。

表6 數據集Ionosphere的實驗分類結果

3個實驗的結果表明：在分類準確率方面，本文所提方法比單個的評價準則有所提高，有效地降低了最優子集的特征維數，并且在分類過程中具有良好的魯棒性。

4 結束語

本文提出了基于Filter方式的ReliefF算法、互信息和類可分性法的多評價準則融合方法，通過序關系分析法計算特征重要性權值系數，最后利用支持向量機從融合后的特征集中選擇出最優的特征子集。它使3種評價準則之間取長補短，不僅擁有較高的分類識別率，而且擁有良好的穩定性和適應性。

基于多評價準則融合特征選擇方法，雖然計算效率較高，但是在特征選擇方法重要性程度判斷上存在一定的主觀性。在后續研究中，考慮利用證據組合方法計算特征重要性權值進一步保證其客觀性。