動態(tài)權(quán)重最大相關(guān)最小冗余算法

殷柯欣，謝愛鋒，翟峻仁

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，吉林 長春 130012)

0 引 言

在當(dāng)今信息爆炸的時代，信息量呈幾何倍數(shù)的速度擴(kuò)充，出現(xiàn)了許多高維數(shù)據(jù)集。這類數(shù)據(jù)集表現(xiàn)出樣本數(shù)量巨大、特征維度高等特點(diǎn)。這些出現(xiàn)在各個領(lǐng)域中的高維數(shù)據(jù)集在促進(jìn)行業(yè)進(jìn)步、技術(shù)發(fā)展的同時，也帶來了巨大挑戰(zhàn)。高維數(shù)據(jù)集因其龐大的樣本個數(shù)和特征維度導(dǎo)致大量的計算資源被占用，且需要耗費(fèi)海量的時間。與此同時，高維數(shù)據(jù)集中包含了大量無關(guān)和冗余的特征，這將會降低后續(xù)模型的性能。特征選擇[1-2]作為一種數(shù)據(jù)預(yù)處理方式，可以很好地解決高維數(shù)據(jù)集帶來的問題。由于特征選擇在降低特征維度的過程中，不曾改變特征原有的物理意義，被廣泛應(yīng)用于文本分類[3]、數(shù)據(jù)挖掘[4]和模式識別等領(lǐng)域。根據(jù)與分類器結(jié)合方式不同，可以將特征選擇分為包裝式[5]、過濾式[6]和嵌入式[7]3類。包裝式和嵌入式方法需要與分類器相結(jié)合，普適性不強(qiáng),容易過擬合且計算復(fù)雜度高。相比于包裝式和嵌入式方法，過濾式特征選擇算法不依賴于分類器，普適性強(qiáng)且計算復(fù)雜度低，在高維數(shù)據(jù)集上有很強(qiáng)的實(shí)用性。對于過濾式方法，評價準(zhǔn)則[8]對其顯得尤為重要，它決定了所選特征的優(yōu)劣。一個優(yōu)秀的評價準(zhǔn)則可以挑選出最優(yōu)的特征子集。現(xiàn)有的評價準(zhǔn)則可以分為距離度量、一致性度量、依賴性度量、信息度量和分類正確率5種。其中，因?yàn)樾畔⒍攘縖9]具有量化特征與特征,特征與類別之間的非線性關(guān)系的優(yōu)點(diǎn)，所以信息度量一直是學(xué)者研究的熱點(diǎn)。

基于信息度量的特征選擇算法，學(xué)者們已經(jīng)提出了很多，但在這些經(jīng)典的算法中卻少有考慮到特征之間的依賴關(guān)系。特征依賴是指具有依賴關(guān)系的單個特征似乎與類標(biāo)簽無關(guān)或弱相關(guān)，但當(dāng)它與相互依賴的特征組合使用時，可能與類標(biāo)簽高度相關(guān)。好在DWFS、IWFS等算法考慮到了特征依賴，根據(jù)候選特征與已選特征的交互作用,對候選特征進(jìn)行加權(quán)。然而，DWFS和IWFS這類算法過度重視特征之間的依賴關(guān)系，卻忽略了候選特征與已選特征之間的冗余關(guān)系。

為了解決DWFS和IWFS存在的算法缺陷，文中提出一種名為基于交互權(quán)重的最大相關(guān)最小冗余算法(Dynamic Weight-based Maximum Relevance Minimum Redundancy Algorithm, DWMRMR)。為了驗(yàn)證文中算法的有效性，在5個數(shù)據(jù)集上與3種有競爭力的算法進(jìn)行比較,實(shí)驗(yàn)表明，DIMRMR算法在大多數(shù)數(shù)據(jù)集上是優(yōu)于其他算法的。

1 信息論[10]

信息熵是隨機(jī)變量不確定性的信息度量。給定兩個離散型隨機(jī)變量X和Y。假設(shè)X=(x1,x2,…,xn),信息熵H(X)的計算公式為

(1)

式中：p(xi)——xi的概率分布。

條件熵是已知變量Y的前提下，X中剩余的不確定性,假設(shè)Y=(y1,y2,…,yn)。條件熵H(X|Y)的表達(dá)式為

(2)

式中：p(xi,yi)——xi和yi的聯(lián)合概率分布；

p(xi|yj)——xi和yi的條件概率分布。

互信息是兩個變量共享的信息量。X和Y的互信息I(X;Y)的表達(dá)式為

(3)

互信息、信息熵和條件熵之間的關(guān)系為

I(X;Y)=H(X)-H(X|Y)。

(4)

假設(shè)C為離散型隨機(jī)變量，C=(c1,c2,…,cn)。在給定C的條件下，X和Y的條件互信息定義如下

I(X;Y|C)=H(X|Y)-H(X|Y,C)。

(5)

聯(lián)合互信息是兩個隨機(jī)變量X和Y與變量C所共享的信息量，聯(lián)合互信息I(X,Y;C)可以由條件互信息和互信息相加得到，

I(X,Y;C)=I(X;C|Y)+I(Y;C)。

(6)

2 相關(guān)工作

最大互信息算法(MIM)[11]又稱為信息增益，是基于互信息最原始的特征選擇方法之一，它的目標(biāo)函數(shù)

(7)

式中：fi——候選特征；

F——候選特征集合；

c——類標(biāo)簽。

MIM計算每一個候選特征fi與標(biāo)簽c的互信息，按其值從大到小排列，然后按照約定選取特征。但是MIM只考慮了特征與類標(biāo)簽之間的相關(guān)性，卻忽視了候選特征與已選特征之間存在的冗余關(guān)系。

為彌補(bǔ)MIM算法的不足，Battiti R[12]提出互信息特征選擇算法(MIFS)，

(8)

MIFS給MIM增加一個冗余項(xiàng)。但由于參數(shù)β是一個固定的值，MIFS的冗余項(xiàng)會隨著已選特征數(shù)量的增加而變大，從而高估了特征之間的冗余。

2005年，Peng H等[13]提出基于最大相關(guān)最小冗余的互信息特征選擇算法(MRMR)，

(9)

基于互信息的MIFS、MRMR等算法被認(rèn)為偏向互信息值較大特征，為了解決這個問題，歸一化互信息特征選擇算法(NMIFS)[14]被提出,

(10)

NMIFS只是MIFS改進(jìn)算法中最經(jīng)典的算法之一。例如，MIFS-U[15]通過在冗余項(xiàng)前面增加一個限制對MIFS進(jìn)行改進(jìn)，取得了不錯的效果。將貪心算法 Non-dominated Sorting Genetic Algorithm-Ⅱ與MIFS相結(jié)合提出了名為MIFS-ND[16]的特征選擇算法。

Joint Mutual Information (JMI)是基于聯(lián)合互信息的特征選擇算法，它在分類性能和穩(wěn)定性方面表現(xiàn)良好，目標(biāo)函數(shù)

(11)

條件互信息最大化算法(CMIM)[17]將條件互信息與“maximum of the minimum”準(zhǔn)則相結(jié)合，設(shè)計出一種不同于傳統(tǒng)方法的算法,

與CMIM算法類似，2015年，Bennasar M等[18]提出聯(lián)合互信息最大化算法(JMIM)，JMIM將“maximum of the minimum”準(zhǔn)則與聯(lián)合互信息結(jié)合，解決了傳統(tǒng)算法在使用累計求和時高估某些特征重要性的問題，

(13)

上述算法各有優(yōu)點(diǎn)，但均忽略特征之間的依賴關(guān)系。特征依賴是指具有依賴關(guān)系的單個特征在分類任務(wù)中似乎不起作用，但如果將相互依賴的特征放在一起，將會起到更好的分類效果。為了解決這個問題，學(xué)者們提出了幾個經(jīng)典的特征選擇算法，比如Dynamic Weighting-Based Feature Selection (DWFS)[19]、Interaction Weight Feature Selection (IWFS)[20]。

(14)

式中：w(i)——每一個候選特征的權(quán)重，初始化為1；

fj——新選中的特征。

(15)

式中：w(fi)——每一個候選特征的權(quán)重，初始化為1；

fj——新選中的特征。

由DWFS和IWFS的準(zhǔn)則函數(shù)可以看出，兩者算法相似，并且存在相同的問題，文中將DWFS和IWFS歸為相同的一類。雖然這類方法加快了計算速度，但只考慮到了類相關(guān)特征冗余，卻忽略了特征之間的類獨(dú)立特征冗余關(guān)系。

類相關(guān)特征冗余和類獨(dú)立特征冗余如圖1所示。

圖1 類相關(guān)特征冗余和類獨(dú)立特征冗余

3 算法描述

為解決DWFS這一類算法忽視特征之間冗余關(guān)系的問題，文中提出一種名為基于動態(tài)權(quán)重的最大相關(guān)最小冗余算法。

3.1 特征關(guān)系

3.1.1 特征冗余[21]

如果特征fi滿足I(c;fi|Xi)

3.1.2 特征依賴

如果特征fi與類標(biāo)簽的相關(guān)性可以通過了解Xi得到補(bǔ)充，即I(c;fi|Xi)>I(c;fi)，則認(rèn)為fi與Xi相互依賴。

3.1.3 特征獨(dú)立

如果特征fi滿足I(c;fi|Xi)=I(c;fi)，則認(rèn)為fi與Xi彼此獨(dú)立。

3.2 基于動態(tài)權(quán)重的最大相關(guān)最小冗余算法(DWMRMR)

為了解決DWFS這一類算法忽視特征之間冗余關(guān)系的問題，文中對DWFS的準(zhǔn)則函數(shù)進(jìn)行修改，

(16)

DWMRMR算法1如下：

Input：

A training sample M with an entire features F=({f1,f2,…,fn} and the class c;User-specified threshold K.

Output:

selected feature subset S.

1：S=?,k=0

2：for i=1 to n do

3:Calculate the mutual informationI(fi;c)

4：end for

5：Initial DW(fi)=I(fi;c) for each feature;

6：while k

7：select the feature fjwith the largest DW(fi);

8：S=S∪{fj}

9：F=F-{fj}

10：or each candidate feature fi∈F do

13：Update DW(fi)=J(MRMR)*DI(fi)；

14：end for

15：k=k+1

16：end while

4 實(shí)驗(yàn)結(jié)果與分析

4.1 DWMRMR算法實(shí)驗(yàn)

為了驗(yàn)證文中算法的有效性，將該算法與3種有競爭力的特征選擇算法MRMR、DWFS和DRJMIM相比較。其中，文中算法DWMRMR可分別認(rèn)為是DWFS和MRMR的改進(jìn)算法。 DRJMIM與DWMRMR是同類算法,且DRJMIM是最新考慮到特征依賴關(guān)系的算法。

實(shí)驗(yàn)環(huán)境是Inter(R)-Core(TM)i7-10750H,內(nèi)存8 G,運(yùn)行速度2.59 GHz，Window10-64 bit操作系統(tǒng)，仿真軟件為PyCharm。實(shí)驗(yàn)過程中采用10折交叉驗(yàn)證方法，用10次測試結(jié)果的平均值作為最終的準(zhǔn)確率。由于部分?jǐn)?shù)據(jù)集都是連續(xù)的，實(shí)驗(yàn)采用CAIM[22]方法將其進(jìn)行離散化[23]處理。實(shí)驗(yàn)中采用KNN、SVM和Native Bayes分類器構(gòu)造預(yù)測模型。

實(shí)驗(yàn)選擇了UCI通用數(shù)據(jù)集和ASU數(shù)據(jù)集，涉及醫(yī)學(xué)、工程科學(xué)等領(lǐng)域，5個數(shù)據(jù)集包含不同的樣本數(shù)、特征數(shù)和類別數(shù)，數(shù)據(jù)集的具體參數(shù)描述見表1。

表1 數(shù)據(jù)集的描述

特征選擇的目的是從原始集合中選出最小的特征子集。從表1可以看出，數(shù)據(jù)集的特征維度是極高的，在特征選擇中，選取數(shù)據(jù)集的全部特征是對時間和資源的極大浪費(fèi)，同時毫無意義。于是，文中約定所選特征的個數(shù)限制在50以下。

4.2 實(shí)驗(yàn)結(jié)果分析

平均準(zhǔn)確率是指最優(yōu)特征子集從一個特征的準(zhǔn)確率到全部特征的準(zhǔn)確率累加和的平均值。4種算法在3NN、SVM、NB分類器上的表現(xiàn)分別見表2～表4。

表2 4種算法在3NN分類器上的表現(xiàn)(平均準(zhǔn)確率±標(biāo)準(zhǔn)差)

表3 4種算法在SVM分類器上的表現(xiàn)(平均準(zhǔn)確率±標(biāo)準(zhǔn)差)

表4 4種算法在NB分類器上的表現(xiàn)(平均準(zhǔn)確率±標(biāo)準(zhǔn)差)

對DWMRMR的分類率與其他算法進(jìn)行配對雙尾t檢驗(yàn),當(dāng)P值小于5%時，認(rèn)為實(shí)驗(yàn)結(jié)果具有顯著性差異。

從表2～表4中可以看出，DWMRMR算法在KNN和NB分類器上均取得了最優(yōu)表現(xiàn)，在SVM分類器上取得了次優(yōu)表現(xiàn)，5種數(shù)據(jù)集在3個分類器上的Avg.值分別為78.28%、78.64%、69.24%。在表2中，DWMRMR、DRJMIM、DWFS和MRMR的Avg.值分別為78.28%、78.05%、76.56%、77.38%，DRJMIM、DWFS和MRMR分別比DWMRMR降低了0.23%、1.72%、0.9%。根據(jù)Avg.值可以得到，DWMRMR算法明顯優(yōu)于DWFS,且與最新算法DRJMIM相比，DWMRMR仍然表現(xiàn)出強(qiáng)勁的競爭優(yōu)勢。W/T/L值亦可以佐證這一點(diǎn)。例如在表4中，4/0/1表示DRJMIM只贏了DWMRMR算法一個數(shù)據(jù)集。4/1/0表示DWFS輸給DWMRMR 4個數(shù)據(jù)集，平局一局。從5/0/0中得出MRMR輸了5個數(shù)據(jù)集。

與此同時，從表2～表4可以看出，同一特征選擇算法在不同的分類器上分類表現(xiàn)不同。比如DWMRMR算法在KNN和NB分類器上表現(xiàn)出最佳性能，然而在SVM上只獲得了次優(yōu)解。因此，分類效果與分類器是密不可分的。為了降低特定分類器對特征選擇算法的影響，文中使用3個分類器的平均值表示特征選擇算法的精度，如圖2所示。

(a) WarpPIE10P (b) Movement libras

(c) Multi-feature factors (d) lung_discrete

(e) Colon

圖2顯示，DWMRMR算法在大多數(shù)數(shù)據(jù)集上取得了最好的分類結(jié)果，其性能明顯優(yōu)于MRMR、DRJMIM和DWFS。雖然在Colon數(shù)據(jù)集上，DWMRMR算法沒有取得最大的分類率，但文中算法用最少的特征取得了次優(yōu)解。這符合特征選擇算法的目的，即選取最小的特征子集以達(dá)到最優(yōu)的分類效果。為了更直觀地體現(xiàn)特征選擇算法的優(yōu)劣，列出每種特征選擇算法平均分類率的最大值，見表5。

表5 4種算法在每個數(shù)據(jù)集上平均分類率的最大值(最優(yōu)特征子集個數(shù))

此時的平均分類率是3種分類器的平均值。

從表5可以看出，DWMRMR算法明顯優(yōu)于其他3種特征選擇算法，這種差距相對于DWFS表現(xiàn)得最為明顯。根據(jù)平均分類器最大值的平均值可以看出，DWMRMR算法分別比DRJMIM、DWFS和MRMR高出1.47%、1.2%和0.58%；并且根據(jù)W/T/L，DWMRMR算法在5個數(shù)據(jù)集中，分別贏了DRJMIM、DWFS和MRMR算法4個、5個和5個數(shù)據(jù)集。由此可見，DWMRMR算法在大多數(shù)數(shù)據(jù)集上優(yōu)于DRJMIM、DWFS和MRMR算法。

上述數(shù)據(jù)已經(jīng)證明了DWMRMR算法分類性能的優(yōu)越性。為了更加直觀地展示各算法的時間花費(fèi)，給出了4種特征選擇算法在同一數(shù)據(jù)集上的時間花費(fèi)，見表6。

表6 4種算法在Multi-feature factors數(shù)據(jù)集上的時間花費(fèi) s

由表6可知，DWMRMR算法的時間花費(fèi)高于DWFS,與MRMR的時間花費(fèi)幾乎一樣，同樣明顯低于DRJMIM。雖然DWFS算法的時間花費(fèi)最低，但其分類表現(xiàn)不佳。盡管DWMRMR的時間花費(fèi)不是最低，但他的分類表現(xiàn)卻是最優(yōu)的。為此，DWMRMR算法的整體性能是可以接受的。

5 結(jié) 語

特征選擇作為一種數(shù)據(jù)預(yù)處理技術(shù)，在諸多領(lǐng)域得到了廣泛應(yīng)用。基于信息度量的過濾式特征選擇算法，由于計算效率高、分類效果優(yōu)異等特點(diǎn)被學(xué)者們大量研究。文中算法就是一種基于信息度量的過濾式特征選擇算法。雖然文中算法DWMRMR改進(jìn)了DWFS的分類效果，但卻增加了計算時間。為此，協(xié)調(diào)時間和算法的分類性能將是下一步工作。