利用近似馬爾科夫毯的最大相關(guān)最小冗余特征選擇算法

張俐,王樅,郭文明

(北京郵電大學(xué)可信分布式計算與服務(wù)教育部重點(diǎn)實(shí)驗(yàn)室,100876,北京)

近年來,基于互信息的特征選擇算法受到國內(nèi)外學(xué)者的廣泛關(guān)注[1]。Zhang等僅考慮特征與類別標(biāo)簽之間的相關(guān)性,而忽視了無關(guān)特征或者冗余特征[2];FCBF算法[3-4]采用對稱不確定性原則作為特征與類別標(biāo)簽之間相關(guān)性判斷的準(zhǔn)則,但是這樣所得子集并不是最優(yōu)子集;mRMR算法[5-6]采用最大相關(guān)最小冗余的準(zhǔn)則進(jìn)行特征子集的排序,使用包裝方法進(jìn)行特征子集的選擇,它的問題是特征子集計算時間長,不能有效刪除冗余特征。這些不相關(guān)和冗余特征往往會降低模型的預(yù)測準(zhǔn)確性和算法學(xué)習(xí)效率[7]。因此,非常有必要在數(shù)據(jù)預(yù)處理階段,對這些不相關(guān)和冗余特征進(jìn)行降維處理[8]。通過降維處理既可以有效降低特征維度,又可以防止模型出現(xiàn)過擬合現(xiàn)象,進(jìn)而提高算法的精確度。

針對上述問題,本文提出基于近似馬爾科夫毯的最大相關(guān)最小冗余特征選擇(nmRMR)算法,該算法包括特征相關(guān)性排序和冗余特征刪除兩個階段:第1階段,利用最大相關(guān)最小冗余準(zhǔn)則進(jìn)行相關(guān)特征排序,并采用前向迭代搜索方法進(jìn)行最優(yōu)特征的選擇;第2階段,采用近似馬爾科夫毯算法刪除冗余特征和不相關(guān)特征。

1 互信息、mRMR準(zhǔn)則與馬爾科夫毯條件

定義1設(shè)一個隨機(jī)變量Y有D個維度,Y=(y1,…,yD),根據(jù)香農(nóng)的信息論[9],一個隨機(jī)變量Y的不確定性可以通過熵H(Y)來度量,同理,對于兩個隨機(jī)變量X和Y,它們之間的條件熵H(X|Y)表示為當(dāng)Y確定時,對X的不確定性的度量。I(X;Y)是隨機(jī)變量X中包含的關(guān)于另一個隨機(jī)變量Y的信息量。因此,I(X;Y)、H(X|Y)和H(X)三者之間的關(guān)系為

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

(1)

式中:p(x)和p(y)分別為隨機(jī)變量X和Y的概率密度,p(x,y)為聯(lián)合概率密度。

定義3特征與標(biāo)簽之間的相關(guān)性。假設(shè)S為特征集合,|S|為特征數(shù);C為標(biāo)簽。I(fi;C)為特征fi與標(biāo)簽C之間的互信息,如果S中存在1,2,3,…,n個特征,I(fi;C)的互信息最大,那么,特征fi表示S集合中最強(qiáng)相關(guān)特征,依照mRMR算法的最大相關(guān)準(zhǔn)則,是選出滿足如下等式的特征的方法

(2)

定義4特征間的冗余性。假設(shè)F為特征全集,S?F,fi∈F-S,fj∈S(i≠j),則I(fi;fj)為特征fi和特征fj之間的互信息。mRMR算法最小冗余準(zhǔn)則滿足

(3)

定義5根據(jù)mRMR算法[7]特征與標(biāo)簽相關(guān)性最大、特征間冗余性最小的原則,可得到mRMR算法的計算式

(4)

定義6馬爾科夫毯描述[10]。S?F,fi?S,fi的馬爾科夫毯的條件是fi⊥{F-S-{fi},C}|S,其中⊥表示獨(dú)立,|S表示以S為條件。在給定S集合中,fi獨(dú)立F-S-{fi}和C,這說明,當(dāng)S集合存在時,fi對于標(biāo)簽C已經(jīng)沒有任何貢獻(xiàn)了,應(yīng)該立即刪除。同時,也說明滿足上述條件的最小特征S集合為特征fi的馬爾科夫毯。

定義7近似馬爾科夫毯[11]的判斷條件。對于特征fi和特征fj(i≠j),特征fi是特征fj的馬爾科夫毯條件為

(5)

2 nmRMR算法描述

本文提出nmRMR算法,具體步驟如下:

步驟1初始化F、S集合并設(shè)置S集合為空集合;

步驟2計算F集合中每一個特征與標(biāo)簽之間的互信息,按照互信息大小對F集合中的特征進(jìn)行降序排序;

步驟3將F集合中的第一個特征fi存入S集合,將fi特征從F集合中刪除;

步驟4按照最大相關(guān)最小冗余準(zhǔn)則進(jìn)行特征之間的排序操作,將排序好的特征存入S集合中;

步驟5按照近似馬爾科夫毯條件判斷,在S集合中進(jìn)行不相關(guān)特征和冗余特征刪除操作;

步驟6輸出最優(yōu)的特征集合,即S集合。

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

3.1 nmRMR算法實(shí)驗(yàn)

本文的實(shí)驗(yàn)環(huán)境是Intel(R)-Core(TM)i7-500U,內(nèi)存是8 GB,Windows7-64 bit操作系統(tǒng),仿真軟件是python3.6和Jupyter Notebook。數(shù)據(jù)統(tǒng)計分析軟件是IBM SPSS Statistics20。

實(shí)驗(yàn)數(shù)據(jù)集選擇了國際著名的UCI通用數(shù)據(jù)集,數(shù)據(jù)集涉及醫(yī)學(xué)、工程科學(xué)和生物科學(xué)等領(lǐng)域,8個樣本數(shù)據(jù)集包含不同的樣本數(shù)、特征數(shù)和類別數(shù),數(shù)據(jù)集的具體參數(shù)描述見表1。樣本數(shù)的范圍為27～4 601,特征數(shù)的范圍為23～91,類別數(shù)的范圍為2～17。

表1 實(shí)驗(yàn)測試數(shù)據(jù)集的描述

由于某些數(shù)據(jù)集中具體特征值存在缺失導(dǎo)致樣本不完整,在進(jìn)行實(shí)驗(yàn)前,直接刪除不完整的樣本,根據(jù)Kuargan提出的類別屬性依賴最大化方法[12]離散化處理連續(xù)型數(shù)據(jù)。

本文采用預(yù)測分類準(zhǔn)確率最為常見的k-NearestNeighbor分類器(簡稱為KNN)[2]和Native Bayes分類器[13-15]來構(gòu)建預(yù)測模型。

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

在實(shí)驗(yàn)過程中采用10折交叉驗(yàn)證方法進(jìn)行實(shí)驗(yàn),10折交叉驗(yàn)證就是每次將數(shù)據(jù)集平均分成10等份,其中9份作為訓(xùn)練數(shù)據(jù)集,1份作為測試數(shù)據(jù)集。為了保證公平,每個數(shù)據(jù)集都做10次實(shí)驗(yàn),通過10次結(jié)果求平均值來求得平均準(zhǔn)確率。與FCBF、mRMR和Fullset算法進(jìn)行對比,驗(yàn)證本文算法是否可以提高分類的準(zhǔn)確率和降低數(shù)據(jù)的特征數(shù)。

比較不同算法優(yōu)劣性的方式就是兩種分類器在8個數(shù)據(jù)集上進(jìn)行驗(yàn)證。FullSet算法不進(jìn)行任何特征排序;mRMR算法依賴于最大相關(guān)最小冗余準(zhǔn)則進(jìn)行特征排序;FCBF算法和nmRMR算法都是在特征初選時對特征進(jìn)行排序篩選。FullSet和mRMR算法并不具有特征初選的功能。為了保證本實(shí)驗(yàn)的公正性,模擬實(shí)驗(yàn)都對初選的特征子集不加以限制。

表2～5分別給出了4種算法在KNN、Native Bayes兩種分類器中的分類準(zhǔn)確率和選擇出特征數(shù)比較。由表2可以看出,在spambase數(shù)據(jù)集中,nmRMR算法分類準(zhǔn)確率略低于mRMR算法,但是在其他7個數(shù)據(jù)集上,nmRMR算法均優(yōu)于mRMR算法。同時,nmRMR算法的平均分類準(zhǔn)確率比mRMR算法提高了0.42%。由表3可以看出,nmRMR算法選擇出的平均特征子集數(shù)比mRMR算法少了5.375個。由表4可以看出,nmRMR算法和mRMR算法在lung-cancer數(shù)據(jù)集上平均分類準(zhǔn)確率相等外,在其他7個數(shù)據(jù)集上,nmRMR算法均優(yōu)于mRMR算法。同時,nmRMR算法的平均分類準(zhǔn)確率比mRMR算法提高了1.14%。由表5可以看出,nmRMR算法選擇出的平均特征子集數(shù)比mRMR算法少了8.375個。由表2和表3可以看出,nmRMR算法的平均分類準(zhǔn)確率比FCBF算法提高了0.4%,nmRMR算法選擇出的平均特征子集數(shù)比FCBF算法少了1個。由表4和表5可以看出,nmRMR算法的平均分類準(zhǔn)確率比FCBF算法提高了1.25%,nmRMR算法選擇出的平均特征子集數(shù)比FCBF算法少了5.375個。

表2 4種算法在KNN分類器中分類準(zhǔn)確率的比較

表3 4種算法在KNN分類器中選擇特征數(shù)的比較

表4 4種算法在Native Bayes分類器中

表5 4種算法在Native Bayes分類器中選擇特征數(shù)的比較

本實(shí)驗(yàn)同時給出4種算法在不同分類器上的分類準(zhǔn)確率,具體如圖1～圖4所示。從圖1～圖4可以看出,nmRMR算法的分類準(zhǔn)確率和特征子集的選擇均優(yōu)于或等于mRMR、FCBF和FullSet算法。

圖1 4種算法在KNN分類器中wdbc數(shù)據(jù)集上 的分類準(zhǔn)確率

圖2 4種算法在KNN分類器中movement_libras數(shù)據(jù)集 上的分類準(zhǔn)確率

圖3 4種算法在Native Bayes分類器中spect數(shù)據(jù)集 上的分類準(zhǔn)確率

圖4 4種算法在Native Bayes分類器中ionosphere 數(shù)據(jù)集上的分類準(zhǔn)確率

4 結(jié) 論

本文提出了一種基于近似馬爾科夫毯的nmRMR特征選擇算法,該算法在第1`階段采用最大相關(guān)最小冗余的評價準(zhǔn)則進(jìn)行特征相關(guān)性冗余性的分析與排序;第2階段采用近似馬爾科夫毯方法進(jìn)行特征與標(biāo)簽以及特征間依賴關(guān)系的分析,將特征間相互依賴程度高的特征進(jìn)行刪除,保留能夠有較高區(qū)分能力的特征,組成最優(yōu)特征子集。由于nmRMR算法具有初期特征子集優(yōu)選能力,它可以進(jìn)一步地提高分類學(xué)習(xí)算法的泛化能力。