基于多評價準(zhǔn)則融合的特征選擇方法

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

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

0 引 言

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

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

1 特征選擇方法概要

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

1.1 ReliefF算法

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

(1)

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

使用權(quán)值作為ReliefF算法的評估值，當(dāng)其權(quán)值大于0的時候，表示特征是相關(guān)的；當(dāng)其權(quán)值小于0的時候，表示特征不相關(guān)。

1.2 類可分性法

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

(2)

(3)

(4)

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

1.3 互信息

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

(5)

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

(6)

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

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

(7)

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

(8)

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

2 基于多評價準(zhǔn)則融合的特征選擇方法

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

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

2.1 多評價準(zhǔn)則融合模型

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

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表示為原始特征空間的特征維數(shù)，SR(i)、SJ(i)和SH(i)分別表示在ReliefF算法、互信息和類可分性法3種準(zhǔn)則下第i個特征在N維特征集中的權(quán)重排序序號。

將ReliefF算法、互信息和類可分性法3種準(zhǔn)則的排序結(jié)果通過添加重要性權(quán)值系數(shù)的方法進(jìn)行融合處理，得到綜合排序結(jié)果，表示如下

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分別表示不同評價準(zhǔn)則的重要性權(quán)值系數(shù)。S(i)是經(jīng)過融合處理后第i個特征在N維特征集中的權(quán)重排序序號。

2.2 基于序關(guān)系分析法的重要性權(quán)值系數(shù)的確定

序關(guān)系分析法是基于層次分析法改進(jìn)的計算權(quán)值方法，是一種定性和定量相結(jié)合、層次化的分析方法。它因無需構(gòu)建判斷矩陣和一致性檢驗使計算量減小；在應(yīng)用中對評價方案個數(shù)沒有限制，可以規(guī)避層次分析法的弊端。它的具體算法如下：

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

U1?U2?U3

(14)

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

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

(15)

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

(3)計算重要性權(quán)值系數(shù)。評價準(zhǔn)則的重要性權(quán)值系數(shù)和其在序關(guān)系中相應(yīng)位置的重要性權(quán)值系數(shù)是對應(yīng)一致的。重要性權(quán)值系數(shù)的計算公式為

(16)

ωp-1=rp×ωp

(17)

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

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

在綜合排序的基礎(chǔ)上，利用支持向量機(jī)實現(xiàn)最終特征選擇結(jié)果。

3 實驗與討論

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

3.1 基于Iris數(shù)據(jù)集的實驗

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

表1 數(shù)據(jù)集Iris的排序?qū)嶒灲Y(jié)果

表2 數(shù)據(jù)集Iris的實驗分類結(jié)果

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

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

3.2 基于Wine數(shù)據(jù)集的實驗

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

表3 數(shù)據(jù)集Wine的排序?qū)嶒灲Y(jié)果

表4 數(shù)據(jù)集Wine的排序?qū)嶒灲Y(jié)果

表5 數(shù)據(jù)集Wine的實驗分類結(jié)果

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

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

3.3 基于Ionosphere數(shù)據(jù)集的實驗

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

表6 數(shù)據(jù)集Ionosphere的實驗分類結(jié)果

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

4 結(jié)束語

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

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