李靜星，楊有龍

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安 710126

在生物信息學(xué)[1]、基因組學(xué)[2]、圖像處理和文本分類(lèi)等許多機(jī)器學(xué)習(xí)應(yīng)用中[3]，越來(lái)越多的具有成千上萬(wàn)個(gè)特征的高維數(shù)據(jù)集成為普遍存在的事實(shí)[4]。高維數(shù)據(jù)集中的不相關(guān)和冗余特征會(huì)導(dǎo)致較高的計(jì)算復(fù)雜度[5]，嚴(yán)重降低分類(lèi)精度。同時(shí)，高維數(shù)據(jù)集可能會(huì)導(dǎo)致“維數(shù)災(zāi)難”[6]。因此，處理實(shí)際問(wèn)題中產(chǎn)生的大量高維數(shù)據(jù)集是一個(gè)重大的挑戰(zhàn)。為解決這個(gè)問(wèn)題，更好地提取高維數(shù)據(jù)中有效信息的主要方法是特征選擇（Feature Selection，F(xiàn)S）。FS 通過(guò)某一準(zhǔn)則從原始特征集中選出部分子集組成最優(yōu)特征子集，然后再應(yīng)用機(jī)器學(xué)習(xí)算法對(duì)數(shù)據(jù)進(jìn)行分類(lèi)分析。其目的是在不造成大量信息丟失的情況下，盡可能多地識(shí)別和刪除不相關(guān)和冗余特征[7]。

傳統(tǒng)的特征選擇算法是基于信息衡量的單變量特征選擇方法，一般是通過(guò)信息增益、信息增益率[8]、對(duì)稱(chēng)不確定性[9]等信息度量準(zhǔn)則計(jì)算特征與類(lèi)屬性之間的相關(guān)性權(quán)值，然后對(duì)其進(jìn)行排序，根據(jù)用戶定義或給定的閾值選擇前K個(gè)特征[10]。但是這里K的取值是很難確定的，并且這個(gè)方法不能排除冗余特征。近幾年，經(jīng)過(guò)國(guó)內(nèi)外學(xué)者的研究表明，從本質(zhì)上來(lái)講，特征選擇方法就是一個(gè)搜索最優(yōu)子集的優(yōu)化問(wèn)題[11-12]。針對(duì)高維數(shù)據(jù)集的研究，改進(jìn)后的特征選擇算法分為兩大部分，首先對(duì)原始特征集進(jìn)行相關(guān)冗余分析，然后對(duì)輸出的子集進(jìn)行搜索評(píng)價(jià)得到最優(yōu)特征子集，其流程圖如圖1所示。

對(duì)于特征選擇算法中相關(guān)冗余性處理，目前也有一些相應(yīng)的解決方法。Tsamardinos 和Aliferis[13]將忠實(shí)貝葉斯網(wǎng)絡(luò)中的馬爾科夫毯與特征選擇中定義的強(qiáng)相關(guān)特征進(jìn)行關(guān)聯(lián)，然后將特征選擇任務(wù)轉(zhuǎn)移到忠實(shí)貝葉斯網(wǎng)絡(luò)的馬爾科夫毯發(fā)現(xiàn)問(wèn)題中。一些學(xué)者提出基于馬爾科夫毯的濾波器算法，如IAMB[14]、MMMB[15]、HITON_MB[16]、PCMB[17]。這四種方法是在假設(shè)數(shù)據(jù)滿足忠實(shí)分布的情況下發(fā)現(xiàn)單一的馬爾科夫毯。但是當(dāng)數(shù)據(jù)集不滿足忠實(shí)分布時(shí)，目標(biāo)節(jié)點(diǎn)的馬爾科夫毯不唯一，會(huì)隨著數(shù)據(jù)集維數(shù)的增加呈指數(shù)型增加，并且由于特征間的概率關(guān)系不易描述，從而導(dǎo)致尋找目標(biāo)節(jié)點(diǎn)的馬爾科夫毯具有挑戰(zhàn)性。

圖1 改進(jìn)的特征選擇方法

Statnikov等人[18]提出可以在非忠實(shí)條件下發(fā)現(xiàn)分布中所有馬爾科夫邊界的算法TIE*（Target Information Equivalence）。Sun 等人[19]提出了基于近似馬爾科夫毯進(jìn)行特征選擇的MIMIC_FS算法，并將得到的子集直接用于訓(xùn)練模型。Yu 等人提出了SRS[20]和SGAI[21]算法，SRS（Selection via Representative Sets）算法對(duì)非忠實(shí)數(shù)據(jù)分布進(jìn)行處理，提出了使用標(biāo)準(zhǔn)的稀疏組lasso從典型集合中選擇特征。SGAI（Selection via Group Alpha-Investing）算法首先得到類(lèi)屬性父子節(jié)點(diǎn)集中每個(gè)特征的代表集，然后通過(guò)兩種衡量標(biāo)準(zhǔn)分別度量代表集中連續(xù)變量和離散變量與類(lèi)屬性的相關(guān)性，最后基于衡量標(biāo)準(zhǔn)從權(quán)值最高的代表集中選取特征，根據(jù)其是否滿足懲罰函數(shù)判斷是否可以加入到預(yù)測(cè)模型中。在這個(gè)過(guò)程中沒(méi)有考慮到冗余特征，并且可能會(huì)選到高相關(guān)但是低預(yù)測(cè)的特征。如圖2 顯示的是數(shù)據(jù)集Wdbc 在NB 分類(lèi)器下的分類(lèi)預(yù)測(cè)精度隨著特征個(gè)數(shù)的變化情況（特征出現(xiàn)的順序根據(jù)與類(lèi)屬性相關(guān)度高低排序），可以看到隨著特征子集個(gè)數(shù)的增加預(yù)測(cè)能力可能會(huì)降低也可能會(huì)增加，如何通過(guò)搜索算法一次性選出預(yù)測(cè)能力較高的特征子集顯得尤為重要。

圖2 數(shù)據(jù)集Wdbc的分類(lèi)精度

為了解決以上問(wèn)題，本文提出了一種MBRPSO（Markov Blanket Representative Set via Particle Swarm Optimization）的特征選擇算法來(lái)解決不滿足忠實(shí)條件的數(shù)據(jù)分類(lèi)問(wèn)題，它充分考慮了特征之間的相關(guān)性和特征與子集之間的冗余性，同時(shí)又引入了結(jié)合特征與類(lèi)屬性相關(guān)性和特征子集對(duì)分類(lèi)預(yù)測(cè)能力的適應(yīng)度函數(shù)，對(duì)粒子群算法初始化的粒子進(jìn)行評(píng)價(jià)更新。MBRPSO 算法首先利用最大信息系數(shù)衡量特征與類(lèi)屬性之間的相關(guān)性，得到類(lèi)屬性的馬爾科夫毯代表集，然后通過(guò)建立特征與子集的冗余性度量準(zhǔn)則，刪除非主導(dǎo)特征得到次最優(yōu)特征子集，最后提出新的適應(yīng)度函數(shù)基于粒子群算法選出最優(yōu)特征子集。通過(guò)與先進(jìn)的特征選擇算法和經(jīng)典的馬爾科夫毯濾波器方法比較，在12 個(gè)基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，MBRPSO 算法對(duì)于不同的數(shù)據(jù)集具有較好的分類(lèi)效果。

1 特征選擇算法MBRPSO

1.1 基礎(chǔ)知識(shí)

定義1（貝葉斯網(wǎng)絡(luò)）[22]設(shè)G=(V,E)是一個(gè)有向非循環(huán)圖，定義P為隨機(jī)變量（節(jié)點(diǎn)集）V上的聯(lián)合概率分布，(G,P) 滿足馬爾科夫條件，因此稱(chēng)B=(G,P)=(V,E,P)為貝葉斯網(wǎng)絡(luò)。

在有向非循環(huán)圖G上的分布P隱含著變量間的獨(dú)立關(guān)系。對(duì)于三個(gè)互不相交的子集X,Y,Z?V，如果IP(X⊥Y|Z)成立，則分布P暗含給定Z時(shí)X和Y獨(dú)立，然而從圖形的角度看，d-分割也決定著X,Y,Z?V間的條件獨(dú)立關(guān)系，可以表示為IG(X⊥Y|Z)。

定義2（忠實(shí)分布）[22]如果對(duì)于任意三個(gè)不相交子集X,Y,Z?V滿足IP(X⊥Y|Z)?IG(X⊥Y|Z)，則稱(chēng)P是定義在G上的忠實(shí)分布，記為P∈Faithful(G)。

定義3（馬爾科夫毯）[22]設(shè)P是變量集V上的分布，變量X∈V，稱(chēng)使得IP(X⊥V-MB-{ }X|MB)成立的一個(gè)變量子集MB為X的一個(gè)馬爾科夫毯。

由以上定義得，如果馬爾科夫分布P是G上的忠實(shí)分布，則由概率關(guān)系決定的條件獨(dú)立完全等價(jià)于圖形決定的d-分割。但是當(dāng)一個(gè)數(shù)據(jù)集不滿足忠實(shí)分布時(shí)，根據(jù)定義2的逆否命題，用概率關(guān)系推導(dǎo)圖中節(jié)點(diǎn)的獨(dú)立是不唯一的，所以此時(shí)目標(biāo)節(jié)點(diǎn)的馬爾科夫毯不唯一。再者從定義3可得，給定目標(biāo)節(jié)點(diǎn)X的馬爾科夫毯MB，則有X與剩余節(jié)點(diǎn)獨(dú)立，即MB中包含了其余特征提供給X的所有相關(guān)信息。將這個(gè)理念應(yīng)用到高維數(shù)據(jù)中，即如果可以找到類(lèi)屬性C的馬爾科夫毯MB(C)，則表示不被包含在MB(C)中的特征與類(lèi)屬性C獨(dú)立，不提供信息，可以安全地刪除，因此MB(C)可用于高維數(shù)據(jù)的特征選擇。

利用馬爾科夫毯定義高維數(shù)據(jù)中的冗余特征為：若一個(gè)特征Fi是冗余特征當(dāng)且僅當(dāng)在特征集F中存在的馬爾科夫毯MBi。

1.2 特征預(yù)處理

1.2.1 特征相關(guān)分析

在之前提出的方法中，信息測(cè)量被認(rèn)為是衡量特征與類(lèi)屬性之間相關(guān)性最有效的度量方法之一[23]，通過(guò)它可以捕捉特征與類(lèi)屬性之間的線性和非線性關(guān)系。為了探索變量間的更多相關(guān)性，Reshef 等人[24]提出了一種統(tǒng)計(jì)方法，叫做最大信息系數(shù)（Maximal Information Coefficient，MIC）。MIC通過(guò)蒙特卡羅的思想解決了連續(xù)隨機(jī)變量概率的求解問(wèn)題，是檢測(cè)大數(shù)據(jù)集中各種變量關(guān)聯(lián)的有效手段。最大信息系數(shù)主要是通過(guò)互信息和網(wǎng)格劃分計(jì)算得到，將連續(xù)隨機(jī)變量離散在二維空間中并且使用散點(diǎn)圖表示，然后用小方格來(lái)劃分并計(jì)算落入每個(gè)小方格的概率。其具體實(shí)現(xiàn)過(guò)程如下：

假設(shè)數(shù)據(jù)集D={(xi,yj),i=1,2,…,n} ，則有隨機(jī)變量X={xi,i=1,2,…,n}和Y={yj,j=1,2,…,n}，給定劃分G，將變量組成的散點(diǎn)圖劃分為i行j列的網(wǎng)格。根據(jù)公式：

計(jì)算每個(gè)網(wǎng)格分區(qū)的互信息值，并將最大互信息值作為劃分G下D的最大互信息，其計(jì)算公式為：

其中，p(x,y)為X和Y的聯(lián)合概率密度，p(x)和p(y)分別為X和Y的邊緣概率密度，D|G表示用G劃分?jǐn)?shù)據(jù)D。同時(shí)將其歸一化處理為：

由于G有多種形式，將取不同劃分方法下的最大互信息值作為最大信息系數(shù)值，定義為：

其中，B(n)為i×j網(wǎng)格的上限，一般取B(n)=n0.6，n為數(shù)據(jù)的大小。

MIC不僅可以應(yīng)用于離散數(shù)據(jù)和連續(xù)數(shù)據(jù)，也可以度量線性和非線性變量之間的關(guān)系，挖掘出變量間的函數(shù)依賴(lài)關(guān)系。本文將MIC 應(yīng)用到馬爾科夫毯中處理特征間的相關(guān)性問(wèn)題。由于目標(biāo)節(jié)點(diǎn)的馬爾科夫毯由目標(biāo)節(jié)點(diǎn)的父子節(jié)點(diǎn)PC和配偶節(jié)點(diǎn)組成，但是配偶節(jié)點(diǎn)尋找的概率模型不易描述。因此，可以轉(zhuǎn)化思想，尋找類(lèi)屬性父子節(jié)點(diǎn)的父子節(jié)點(diǎn)，從而構(gòu)成類(lèi)屬性的馬爾科夫毯代表集，解決不忠實(shí)條件下馬爾科夫毯不唯一的問(wèn)題。

從概率角度來(lái)看，如果：

則Fk稱(chēng)為Fi的相關(guān)特征。記作Fk=Cor(Fi)。在貝葉斯網(wǎng)絡(luò)中，如果在Fi∈F和Fk∈F之間存在有向邊，那么稱(chēng)Fk和Fi直接相關(guān)。

在本文中利用MIC 衡量特征與類(lèi)屬性之間的相關(guān)性，然后將得到的權(quán)值排序取相關(guān)度高的特征子集組成類(lèi)屬性的父子節(jié)點(diǎn)ξ=PC(C)，令Rs1,Rs2,…,Rsk為ξ=PC(C)中每一個(gè)特征的代表集，定義Rsi={Fi?Cor(Fi)},Fi∈ξ,i=1,2,…,k，令

為類(lèi)屬性的馬爾科夫毯代表集。

如果一個(gè)特征Fi在當(dāng)前的特征集中存在一個(gè)馬爾科夫毯Mi，則表示Mi包含了Fi對(duì)類(lèi)屬性C和其他特征F-Mi-{Fi}的所有相關(guān)信息，因此可以安全地刪除Fi。通過(guò)對(duì)特征與類(lèi)屬性之間的相關(guān)性分析，得到類(lèi)屬性的馬爾科夫毯代表集，從而可以排除其他特征減少特征搜索空間。

1.2.2 特征冗余分析

由前面討論可知，在尋找類(lèi)屬性馬爾科夫毯代表集的過(guò)程中，會(huì)含有一些冗余特征被選擇，所以需要建立冗余性衡量準(zhǔn)則剔除代表集中的冗余特征。

給出一個(gè)已被選擇的特征子集S={Fi}?F，以及一個(gè)任意的特征Fi∈F?Fi∈S，定義特征Fi與子集S的相關(guān)性為：

當(dāng)且僅當(dāng)特征與類(lèi)屬性的相關(guān)性較低且與馬爾科夫毯代表集相關(guān)性較高時(shí)，特征被稱(chēng)為非主導(dǎo)特征。

即當(dāng)?shù)仁剑?）的值較小時(shí)，稱(chēng)Fj為非主導(dǎo)特征。找出這類(lèi)特征，將其從馬爾科夫毯代表集中刪除得到次最優(yōu)特征子集。例如，圖3表示類(lèi)屬性C的次最優(yōu)特征子集尋找過(guò)程，圖中的幾個(gè)藍(lán)色節(jié)點(diǎn)表示類(lèi)屬性的父子節(jié)點(diǎn)，用紅線標(biāo)出的幾個(gè)大圈表示類(lèi)屬性的馬爾科夫毯代表集。即藍(lán)色節(jié)點(diǎn)的父子節(jié)點(diǎn)組成的集合，假設(shè)節(jié)點(diǎn)K的ND(K)值較小，小于給定的閾值θ時(shí)，剔除節(jié)點(diǎn)K，則得到的集合就是類(lèi)屬性的次最優(yōu)特征子集。

圖3 類(lèi)屬性C 的次最優(yōu)特征子集

1.3 選出最優(yōu)特征子集

1.3.1 適應(yīng)度函數(shù)的提出

在對(duì)數(shù)據(jù)集的原始特征集進(jìn)行特征預(yù)處理得到類(lèi)屬性的次最優(yōu)特征子集之后，采用粒子群算法尋找最優(yōu)解。通過(guò)提出相應(yīng)的適應(yīng)度函數(shù)來(lái)確定粒子的最佳位置，從而通過(guò)迭代對(duì)粒子進(jìn)行更新，找到問(wèn)題的最優(yōu)解，其關(guān)鍵一步就是建立適應(yīng)度函數(shù)。本文利用加權(quán)系數(shù)μ將平衡分類(lèi)精度與相關(guān)性度量結(jié)合得到新的適應(yīng)度函數(shù)，公式如下：

其中，balanced_acc表示平衡分類(lèi)精度，計(jì)算公式為：

c為類(lèi)別個(gè)數(shù)，TPi為第i類(lèi)正確識(shí)別的實(shí)例數(shù)，為第i類(lèi)的樣本量，所有類(lèi)均以的權(quán)重進(jìn)行處理。

式（9）中的junzhi_FS表示使用邏輯損失函數(shù)將junzhi_MIC歸一化得到的值，junzhi_MIC表示當(dāng)前特征子集與類(lèi)屬性C的最大信息系數(shù)均值，其具體計(jì)算過(guò)程如（11）、（12）所示：

nOfselection是當(dāng)前選進(jìn)最優(yōu)特征子集中的特征個(gè)數(shù)，MIC(Fk,C)表示當(dāng)前子集中的特征與類(lèi)屬性的最大信息系數(shù)值。邏輯損失函數(shù)的參數(shù)選擇見(jiàn)圖4（b），采用系數(shù)為-6 的邏輯損失函數(shù)可以將均值歸一化到[0.5，1]，系數(shù)為-1 的邏輯損失函數(shù)如圖4（a）所示，不能將輸入的均值返回到全范圍的[0.5，1]中。

1.3.2 MBRPSO算法的實(shí)現(xiàn)

本文使用粒子群算法搜索評(píng)價(jià)特征子集。首先隨機(jī)產(chǎn)生一群初始化粒子，每個(gè)粒子的位置代表一個(gè)完整的候選解決方案，粒子實(shí)際上是一個(gè)有N維實(shí)向量，其中N是設(shè)定的最優(yōu)子集特征個(gè)數(shù)。通過(guò)位置和速度兩個(gè)參數(shù)來(lái)描述一個(gè)粒子的運(yùn)動(dòng)狀態(tài)。并且在每一次迭代中，通過(guò)適應(yīng)度函數(shù)記錄每個(gè)粒子的個(gè)體歷史最優(yōu)位置和群體的歷史最優(yōu)位置，最后利用這兩個(gè)最優(yōu)位置再結(jié)合粒子本身的慣性共同影響粒子的運(yùn)動(dòng)狀態(tài)，由此來(lái)更新粒子的位置和的速度。在這個(gè)算法中粒子僅有兩個(gè)屬性：速度和位置，速度代表移動(dòng)的快慢，位置代表移動(dòng)的方向。位置速度和位置更新是粒子群算法的核心，其原理表達(dá)式和更新方式如下：

圖4 邏輯函數(shù)參數(shù)的選擇

算法1MBRPSO算法

輸入：訓(xùn)練集T，特征集合F=(F1,F2,…,Fn,C)，閾值θ和權(quán)值系數(shù)μ。

輸出：最優(yōu)特征子集FS。

1.fori=1,2,…,n//特征集合中任取一個(gè)特征

計(jì)算每個(gè)特征與類(lèi)屬性的最大信息系數(shù)值MIC(Fi,C)；end

2.將MIC(Fi,C)值從大到小排列，得到貝葉斯網(wǎng)絡(luò)中與類(lèi)屬性C相關(guān)的父子節(jié)點(diǎn)ξ=PC(C)

3.記K=| |ξ//ξ中特征的個(gè)數(shù)

4.forj=1,2,…,K//特征集ξ中任取一個(gè)特征Rsj=PC(Fj)?Fj,Fj∈ξend

5.獲得類(lèi)屬性C的馬爾科夫毯代表集，記Rs=|L|；

6.當(dāng)Rs≠Null 時(shí)

7.fork=1,2,…,L//從代表集中任取一個(gè)特征

8.如果

則從Rs中剔除特征Fk

9.否則，繼續(xù)上述操作

10.end

11.返回類(lèi)屬性的次最優(yōu)特征子集S；

12.初始化粒子

13.使用式（9）計(jì)算每個(gè)粒子的適應(yīng)度函數(shù)值，更新粒子的位置和速度，得到最優(yōu)特征子集FS返回一個(gè)具有特定個(gè)數(shù)的最優(yōu)特征子集。

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

主要評(píng)估所提出的MBRPSO 算法的有效性。將MBRPSO 算法與四種先進(jìn)的特征選擇方法和四種經(jīng)典的馬爾科夫毯濾波器進(jìn)行比較，分別使用三種分類(lèi)器對(duì)來(lái)自不同研究領(lǐng)域并且有著不同規(guī)模的12個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)分析比較，從而驗(yàn)證MBRPSO 算法的可行性和有效性。

2.1 數(shù)據(jù)集

在表1中，選擇了UCI的12個(gè)基準(zhǔn)數(shù)據(jù)集，其中有5個(gè)機(jī)器學(xué)習(xí)數(shù)據(jù)集存儲(chǔ)庫(kù)（Spect、Wdbc、Spectf、Promoter、Spambase）、4 個(gè)生物醫(yī)學(xué)數(shù)據(jù)集（Colonoscopy、Scadi、Arrhythmia、Dermatology）、2 個(gè) 2003NIPS 特征選擇挑戰(zhàn)數(shù)據(jù)集（Madelon、arcene）和1 個(gè)圖像處理數(shù)據(jù)集（DrivFace）。這12個(gè)數(shù)據(jù)集涵蓋了廣泛的實(shí)際應(yīng)用，包括臨床成像、基因表達(dá)、生態(tài)學(xué)和分子生物學(xué)。12個(gè)數(shù)據(jù)集的維度從22到10 000、樣本大小從70到數(shù)千、數(shù)據(jù)集的類(lèi)別從2到16，代表性廣泛。對(duì)表1中的每個(gè)數(shù)據(jù)集，隨機(jī)選取50%的實(shí)例作為所有實(shí)驗(yàn)應(yīng)用的訓(xùn)練數(shù)據(jù)集，其余50%的實(shí)例作為測(cè)試數(shù)據(jù)集。利用訓(xùn)練數(shù)據(jù)通過(guò)各種特征選擇方法來(lái)選擇最優(yōu)的特征子集。然后將所選擇的最優(yōu)特征子集應(yīng)用于測(cè)試數(shù)據(jù)。

表1 實(shí)驗(yàn)數(shù)據(jù)集

2.2 實(shí)驗(yàn)裝置

對(duì)于表1 中的每個(gè)數(shù)據(jù)集，使用了三個(gè)分類(lèi)器，分別是MATLAB 統(tǒng)計(jì)工具箱提供的NB 和KNN 分類(lèi)器，LIBSVM庫(kù)提供的SVM分類(lèi)器，分析數(shù)據(jù)的預(yù)測(cè)誤差，從而評(píng)估特征選擇算法的有效性。為了避免所選數(shù)據(jù)的偏倚，使實(shí)驗(yàn)更有說(shuō)服力，使用十折交叉驗(yàn)證對(duì)特征子集進(jìn)行測(cè)試和評(píng)價(jià)，重復(fù)實(shí)驗(yàn)20 次。本文將提出的算法與四種經(jīng)典的馬爾科夫毯濾波器和四種先進(jìn)的特征選擇方法進(jìn)行比較分析。

對(duì)于先進(jìn)的特征選擇方法，主要采用以下四種方法進(jìn)行比較：（1）TIE*算法[18]，在數(shù)據(jù)集不滿足忠實(shí)條件時(shí)，以HITON_PC作為基本尋找所有的馬爾科夫毯，其中參數(shù)的設(shè)置詳見(jiàn)文獻(xiàn)[18]。（2）MIMIC_FS 算法[19]，基于最大信息系數(shù)和近似馬爾科夫毯對(duì)特征進(jìn)行選擇，關(guān)于參數(shù)的設(shè)置見(jiàn)文獻(xiàn)[19]。（3）SRS 算法[20]，在不忠實(shí)的情況下，提出了利用稀疏組從典型集合中選擇特征子集，其參數(shù)的具體設(shè)置見(jiàn)文獻(xiàn)[20]。（4）SGAI算法[21]，基于對(duì)稱(chēng)不確定性和概率密度函數(shù)建立代表集與類(lèi)屬性之間的相關(guān)性權(quán)值，然后根據(jù)權(quán)值從每個(gè)代表集中選擇特征組成最優(yōu)子集，其關(guān)于搜索算法的參數(shù)設(shè)置見(jiàn)文獻(xiàn)[21]。除去這四種特征選擇方法，本文還將MBRPSO 算法與1.2節(jié)提出的馬爾科夫毯代表集Rs進(jìn)行比較。

對(duì)于經(jīng)典的馬爾科夫毯濾波器，主要采用以下四種方法進(jìn)行比較分析：（1）IAMB[14]，在忠實(shí)性的假設(shè)下采用啟發(fā)式搜索從高維數(shù)據(jù)庫(kù)中學(xué)習(xí)類(lèi)屬性的馬爾科夫毯。（2）MMMB[15]，采用分治法分兩步搜索目標(biāo)節(jié)點(diǎn)的馬爾科夫毯。（3）HITON_MB算法[16]，旨在緩解IAMB算法中數(shù)據(jù)效率低下的問(wèn)題，同樣是分兩步學(xué)習(xí)馬爾科夫毯。（4）PCMB 算法[17]，不需要學(xué)習(xí)全都的貝葉斯網(wǎng)絡(luò)，而且識(shí)別目標(biāo)節(jié)點(diǎn)的馬爾科夫毯所需的實(shí)例個(gè)數(shù)不取決于馬爾科夫毯，克服了數(shù)據(jù)無(wú)效率的問(wèn)題。四種算法的顯著性水平取為0.01。

在本文提出的MBRPSO 算法中，閾值θ用于控制單個(gè)特征與特征子集的冗余性。每個(gè)數(shù)據(jù)集的閾值不一樣，取決于每個(gè)特征與已選子集的最大信息系數(shù)值。對(duì)于表1 給出的數(shù)據(jù)集，θ的取值范圍為[-0.3,0.1]。粒子群算法中的慣性權(quán)重ω取為0.2，學(xué)習(xí)因子c1,c2取為2。適應(yīng)度函數(shù)中的參數(shù)μ取值為[0.2，03]，迭代次數(shù)為50，初始化粒子的大小為特征數(shù)20（限制最大為300）。

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

特征選擇的目的是在特征信息較少遺漏的情況下，選擇較少的特征達(dá)到較高的分類(lèi)預(yù)測(cè)能力。因此，本文通過(guò)分類(lèi)預(yù)測(cè)能力和算法最終選擇的特征個(gè)數(shù)兩方面對(duì)算法的有效性進(jìn)行分析評(píng)價(jià)。

2.3.1 比較MBRPSO與先進(jìn)特征選擇算法

（1）比較分類(lèi)預(yù)測(cè)能力

表2、表3和表4顯示了MBRPSO與SGAI、MIMIC_FS、SRS、Rs、TIE*的實(shí)驗(yàn)結(jié)果，以及展現(xiàn)了使用不同分類(lèi)器的同一種特征選擇方法在不同數(shù)據(jù)集下的平均分類(lèi)精度，最低的預(yù)測(cè)誤差以粗體突出顯示。從表中可以看出，MBRPSO 算法的分類(lèi)性能優(yōu)于其他先進(jìn)的特征選擇方法。由于所選數(shù)據(jù)分為離散數(shù)據(jù)和連續(xù)數(shù)據(jù)，以及兩類(lèi)數(shù)據(jù)和多類(lèi)數(shù)據(jù)，這些都會(huì)對(duì)數(shù)據(jù)集的分類(lèi)和預(yù)測(cè)能力產(chǎn)生影響。對(duì)于KNN分類(lèi)器，在本節(jié)的12組實(shí)驗(yàn)中，MBRPSO算法在10個(gè)數(shù)據(jù)集中始終優(yōu)于其他方法，其平均值為84.77%，分別比SGAI、MIMIC_FS、SRS、Rs和TIE*高出6.23%、3.84%、7.03%、7.96%和6.57%。對(duì)于NB 分類(lèi)器，MBRPSO 算法在8 個(gè)數(shù)據(jù)集中始終優(yōu)于其他方法，其平均值為85.53%，分別比SGAI、MIMIC_FS、SRS、Rs和TIE*分別高出7.09%、9.65%、7.60%、7.61%和4.13%。對(duì)于SVM分類(lèi)器，MBRPSO算法在9個(gè)數(shù)據(jù)集中始終優(yōu)于其他方法，平均為85.49%，分別高出其他算法6.28%、7.42%、7.25%、6.72%和5.52%。

表2 五種特征選擇在KNN上的平均分類(lèi)精度比較

表3 五種特征選擇在NB上的平均分類(lèi)精度比較

以上比較中，MBRPSO 與SGAI 都是通過(guò)衡量特征與類(lèi)屬性的相關(guān)性，然后通過(guò)高相關(guān)的特征組成代表集，進(jìn)而利用搜索算法選出最優(yōu)子集。主要不同之處在于MBRPSO 得到的是類(lèi)屬性的馬爾科夫毯代表集，并利用搜索算法選出一組特征。而SGAI得到的是每個(gè)高相關(guān)特征的代表集，從空集出發(fā)，在每個(gè)代表集中一個(gè)一個(gè)選出特征。通過(guò)這兩個(gè)算法的比較可以直觀地看出一次性選出特征子集的優(yōu)勢(shì)。其堆積百分比柱狀圖如圖5 所示。圖中主要體現(xiàn)的是不同的特征選擇方法利用不同分類(lèi)器的預(yù)測(cè)誤差比較，可以看出特征選擇方法與何種分類(lèi)器搭配預(yù)測(cè)能力最大。在KNN中，8組準(zhǔn)確率差異均在3%以上，分類(lèi)準(zhǔn)確率最高的為19.21%。MBRPSO 中最差的實(shí)驗(yàn)結(jié)果比SGAI 低3.29%，算法性能具有可比性。通過(guò)分析SVM 和NB 分類(lèi)器的實(shí)驗(yàn)結(jié)果，得到了MBRPSO 算法的分類(lèi)性能優(yōu)于SGAI 算法。從圖中看出，與SGAI 相比，MBRPSO 對(duì)于多類(lèi)數(shù)據(jù)集具有更高的分類(lèi)預(yù)測(cè)精度，當(dāng)樣本數(shù)量遠(yuǎn)遠(yuǎn)大于特征數(shù)量時(shí)，MBRPSO的效果略差。

表4 五種特征選擇在SVM上的平均分類(lèi)精度比較

圖5 MBRPSO與SGAI基于三種分類(lèi)器預(yù)測(cè)誤差的比較

（2）比較最終選擇的特征個(gè)數(shù)

圖6（a）～（e）顯示了使用 SGAI、MIMIC_FS、TIE*、SRS 和Rs 選出的特征數(shù)與MBRPSO 算法的比較結(jié)果。表5為MBRPSO算法最終選出的特征數(shù)。在大多數(shù)數(shù)據(jù)集中，MBRPSO 算法選擇的特征比其他算法少。MBRPSO 從特征與類(lèi)屬性的相關(guān)性角度出發(fā)，最大限度地保留了與類(lèi)相關(guān)的、更有區(qū)別性的特征。在特征之間的冗余方面，MBRPSO 可以更有效地去除冗余特征，進(jìn)一步減少特征之間的冗余，從而在特征分類(lèi)數(shù)據(jù)較少的情況下達(dá)到最高的分類(lèi)性能。重要的是，MBRPSO 可以預(yù)先確定最終選擇特征子集的數(shù)量。其他先進(jìn)的馬爾科夫毯特征選擇算法在特征數(shù)量方面具有不確定性和不靈活性。

圖6 算法所選特征個(gè)數(shù)的比較

表5 MBRPSO選出的特征數(shù)量

2.3.2 比較MBRPSO與馬爾科夫?yàn)V波器

（1）比較分類(lèi)預(yù)測(cè)能力

表6～8 分別給出了算法MBRPSO、IAMB、PCMB、HITON_MB和MMMB的預(yù)測(cè)誤差，以及同一特征選擇方法在不同數(shù)據(jù)集中的平均分類(lèi)精度。最低的預(yù)測(cè)誤差以粗體突顯。從表中可以看出，MBRPSO 的分類(lèi)性能優(yōu)于其他馬爾科夫毯濾波器，體現(xiàn)出在數(shù)據(jù)集不滿足忠實(shí)分布的情況下，引入馬爾科夫毯代表集的優(yōu)勢(shì)。分析表6得對(duì)于KNN，在本節(jié)的12組實(shí)驗(yàn)中，MBRPSO算法在9 個(gè)數(shù)據(jù)集中始終優(yōu)于其他方法，其平均值為84.77%，分別比IAMB、PCMB、HITOM_MB 和MMMB高4.28%、7.69%、3.48%和6.97%。表7展現(xiàn)出了對(duì)于NB，MBRPSO 算法在10 個(gè)數(shù)據(jù)集中始終優(yōu)于其他方法，其平均值為85.53%，分別比IAMB、PCMB、HITOM_MB和MMMB高9.44%、10.07%、5.43%和7.78%。從表8可得，對(duì)于SVM，MBRPSO算法在9個(gè)數(shù)據(jù)集中始終優(yōu)于其他方法，其平均值為85.49%，分別比IAMB、PCMB、HITOM_MB和MMMB高9.16%、8.97%、7.09%和7.94%。

表6 五種特征選擇過(guò)濾器在KNN上的平均分類(lèi)精度比較

表7 五種特征選擇過(guò)濾器在NB上的平均分類(lèi)精度比較

表8 五種特征選擇過(guò)濾器在SVM上的平均分類(lèi)精度比較

（2）比較最終選擇的特征個(gè)數(shù)

從圖7 顯示了MBRPSO 算法選出的特征數(shù)與其他算法特征數(shù)的比較。分析得到這五種算法在9 個(gè)數(shù)據(jù)集上選出的特征數(shù)是相近的，并且在剩余的數(shù)據(jù)集中，MBRPSO算法與IAMB和HITON_MB算法選出特征數(shù)相差較大，與MMMB 和PCMB 算法選出的特征數(shù)相近。在特征個(gè)數(shù)相近的數(shù)據(jù)集中，可以由分類(lèi)預(yù)測(cè)誤差得到，MBRPSO算法的性能更強(qiáng)。

圖7 五種算法特征個(gè)數(shù)的比較

綜上所述，研究表明：在數(shù)據(jù)集不滿足忠實(shí)條件的情況下，單一的馬爾科夫毯特征選擇算法選出的特征并不是有較高預(yù)測(cè)能力的最優(yōu)特征集。而MBRPSO不需要對(duì)真實(shí)數(shù)據(jù)集中所有馬爾可夫毯的未知空間進(jìn)行徹底的搜索，就可以通過(guò)剔除與類(lèi)屬性和代表集冗余的特征，有效地找到特征選擇的最優(yōu)特征子集。

3 結(jié)束語(yǔ)

隨著社會(huì)信息化的迅猛發(fā)展，數(shù)據(jù)規(guī)模的巨大化，數(shù)據(jù)結(jié)構(gòu)的復(fù)雜化以及數(shù)據(jù)表現(xiàn)形式的多樣化，使得從數(shù)據(jù)集中提取有效的信息，處理高維數(shù)據(jù)的分類(lèi)問(wèn)題變得極其困難。所以利用特征選擇方法避免維數(shù)災(zāi)難減小特征搜索空間變得尤為重要。

本文針對(duì)高維數(shù)據(jù)的特征選擇問(wèn)題，提出了一種有效的算法MBRPSO來(lái)解決數(shù)據(jù)集不滿足忠實(shí)分布時(shí)類(lèi)屬性的馬爾科夫毯發(fā)現(xiàn)問(wèn)題。MBRPSO 算法主要通過(guò)最大信息系數(shù)建立特征與類(lèi)屬性相關(guān)性和特征與子集冗余性的衡量準(zhǔn)則，從而得到類(lèi)屬性的馬爾科夫毯代表集和次最優(yōu)特征子集對(duì)原始特征集進(jìn)行預(yù)處理，然后設(shè)立同時(shí)考慮特征子集的相關(guān)性和預(yù)測(cè)能力的適應(yīng)度函數(shù)，利用粒子群算法選出最優(yōu)特征子集。實(shí)驗(yàn)結(jié)果表明，與其他相關(guān)方法相比，采用特征預(yù)處理步驟縮小原始特征集的搜索空間并基于集合的形式搜索最優(yōu)子集，可以在測(cè)試階段提高分類(lèi)精度且起到顯著的降維效果。