基于節(jié)點(diǎn)度中心性的無監(jiān)督特征選擇

閆泓任 馬國帥 錢宇華

（山西大學(xué)大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院，太原，030006）

引 言

隨著獲取數(shù)據(jù)的手段愈加多樣，包含豐富信息的高維數(shù)據(jù)涌現(xiàn)在各個(gè)領(lǐng)域，如生物信息學(xué)[1]、地理學(xué)[2]、以及社交網(wǎng)絡(luò)等[3]。但是急劇增長的數(shù)據(jù)規(guī)模往往使得冗余信息過多、數(shù)據(jù)處理緩慢或者建模效果不佳。因此使用合理的數(shù)據(jù)挖掘技術(shù)自動(dòng)提取數(shù)據(jù)中的有效信息十分必要。

低維度空間上有效的智能算法處理高維數(shù)據(jù)時(shí)常常面臨維度災(zāi)難：數(shù)據(jù)變得十分稀疏，且建立在大量特征上的模型往往出現(xiàn)過擬合從而影響預(yù)測(cè)結(jié)果[4]。為解決這一難題，降維方法近年得到研究者的重視。這些方法大多可分為兩類：一類是特征提取，將高維原始空間線性或非線性的投影到一個(gè)維度更低的特征空間[5]；另一類則是特征選擇，即直接選擇原有特征集中的一個(gè)子集[6]。正確使用這兩類方法可以有效提高模型學(xué)習(xí)能力和泛化能力，并降低時(shí)間和空間計(jì)算復(fù)雜度。本文關(guān)注的方法以特征選擇為主。

對(duì)于給定的任務(wù)和數(shù)據(jù)集，如何為模型選擇合適的特征子集，這取決于在一個(gè)數(shù)據(jù)集中棄用或保留某些特征會(huì)對(duì)未來的預(yù)測(cè)結(jié)果準(zhǔn)確性產(chǎn)生的影響。這種影響主要包含兩方面：特征和類標(biāo)簽之間的相關(guān)性（簡稱特征關(guān)聯(lián)）以及特征冗余[7]。特征關(guān)聯(lián)度決定了一個(gè)特征在聚類分類等任務(wù)上有效抓取樣本類別信息的能力。假如某個(gè)特征具備分辨類別的能力，則它被認(rèn)為有關(guān)聯(lián)；反之如果它使得原本的分辨更加模糊則被認(rèn)為無關(guān)。冗余特征是一類有弱關(guān)聯(lián)度且無法增加分辨能力的特征。普遍認(rèn)為特征冗余是依賴于特征相關(guān)度和給定特征子集而存在的。在這些定義之下，Koller等提出了基于信息論和馬爾可夫毯的特征選擇理論框架和實(shí)現(xiàn)方法。Blum等提出逐個(gè)評(píng)估(即特征排名)方法，即設(shè)定準(zhǔn)則對(duì)每個(gè)特征的關(guān)聯(lián)度進(jìn)行獨(dú)立計(jì)算并排名，然后選取分?jǐn)?shù)最高的一群特征作為輸出[8]。此后He等[9]對(duì)樣本相似性建模得到Laplacian score（詳見第1節(jié)），通過構(gòu)造仿射矩陣來保持?jǐn)?shù)據(jù)的流形結(jié)構(gòu)。

由于冗余的特征常常具有相近的分?jǐn)?shù)，上面的方法無法消除冗余現(xiàn)象。Brown等[10]研究者的極大似然選擇框架以及Liu等[11]的子集評(píng)估（搜索策略+評(píng)估停止準(zhǔn)則）方法既可消除無關(guān)亦可減少冗余，但是搜索最小子集的策略效率不高。在此基礎(chǔ)上Liu等[12]提出了新的選擇框架，使得關(guān)聯(lián)度和冗余的分析更加高效。之后陸續(xù)有新算法被提出。其中一類方法通過在已知類標(biāo)簽的情況下建立稀疏學(xué)習(xí)模型[13]，最小化含有稀疏正則項(xiàng)的目標(biāo)函數(shù)的擬合誤差，最后輸出特征系數(shù)作為特征的排名[14]。這類方法雖然可以在優(yōu)化目標(biāo)函數(shù)的過程當(dāng)中同時(shí)處理特征關(guān)聯(lián)和特征冗余，可是它的缺陷也很明顯：依賴于特定學(xué)習(xí)算法，遷移能力弱；且在正則化的限制下特征系數(shù)變得極為稀疏，從而無法充分考慮冗余特征。

傳統(tǒng)特征選擇算法會(huì)潛在假設(shè)各特征之間的獨(dú)立性（此時(shí)的特征被稱為flat feature），但是大量真實(shí)數(shù)據(jù)中彼此相關(guān)的特征——如健康大數(shù)據(jù)中不同疾病之間的關(guān)聯(lián)或生物數(shù)據(jù)中基因之間的協(xié)調(diào)關(guān)系等，嚴(yán)重影響算法有效性。此后的研究文獻(xiàn)有時(shí)在構(gòu)筑模型前預(yù)先假定特征結(jié)構(gòu)的存在。同樣基于稀疏學(xué)習(xí)的框架，將特征當(dāng)作節(jié)點(diǎn)，關(guān)聯(lián)當(dāng)作連邊，文獻(xiàn)[15]提出Lasso方法，建立特征相關(guān)性的圖結(jié)構(gòu)并優(yōu)化特征系數(shù)。這類方法雖然提高了學(xué)習(xí)任務(wù)的效果，可求解的優(yōu)化目標(biāo)復(fù)雜，計(jì)算成本較高，且無法通過數(shù)據(jù)自動(dòng)提取特征結(jié)構(gòu)。

以上提到的方法有效地應(yīng)用在標(biāo)簽數(shù)據(jù)上，但是對(duì)于無標(biāo)簽或少標(biāo)簽的數(shù)據(jù)，由于無法利用標(biāo)簽作為評(píng)價(jià)準(zhǔn)則，效果不夠理想[16]。文獻(xiàn)[17]利用進(jìn)化局部搜索算法，在無監(jiān)督的情況下，能夠同時(shí)找到特征組合和聚類數(shù)目，Cai等[18]提出基于稀疏學(xué)習(xí)的多聚類特征選擇等經(jīng)典無監(jiān)督方法（詳見第1節(jié)）。這些技術(shù)之所以能夠產(chǎn)生較好的結(jié)果，是因?yàn)樗鼈兊哪Ｐ桶盐盏綐颖净蛱卣鞯木植筷P(guān)聯(lián)，卻同時(shí)因?yàn)槿笔?duì)全局關(guān)聯(lián)的考察導(dǎo)致選擇過程無法得到宏觀信息。

在無監(jiān)督學(xué)習(xí)的場(chǎng)景下，當(dāng)特征維數(shù)越來越巨大，特征空間并不明確存在分布，甚至具有很強(qiáng)的異質(zhì)性，傳統(tǒng)的條件概率框架或旨在利用流形學(xué)習(xí)（或稀疏學(xué)習(xí)）發(fā)掘局部信息的方法將越來越難推斷什么特征更加重要。鑒于以往排名方法處理特征冗余時(shí)的不充分、特征空間的局部結(jié)構(gòu)方法的局限性，本文提出啟發(fā)式無監(jiān)督算法框架，引入復(fù)雜網(wǎng)絡(luò)的概念對(duì)特征的全局關(guān)聯(lián)進(jìn)行建模。復(fù)雜網(wǎng)絡(luò)可以很好地模擬群體中的交互行為，群體形成的網(wǎng)絡(luò)具有獨(dú)特的拓?fù)湫再|(zhì)。理解這些性質(zhì)有助于認(rèn)知這個(gè)群體和其中的個(gè)體。把特征空間作為一個(gè)群體，那么復(fù)雜網(wǎng)絡(luò)能夠全局地捕捉到特征之間存在的關(guān)聯(lián)。在網(wǎng)絡(luò)中，為了找到最重要的特征（節(jié)點(diǎn)），本文使用社會(huì)網(wǎng)絡(luò)分析當(dāng)中常用的概念——節(jié)點(diǎn)度中心性，衡量一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的鄰居占網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比例[19]來選擇最重要的特征子集。在以往的子集搜索方法中，尋找到的所有子集之間存在交集，這個(gè)交集對(duì)應(yīng)著空間中最重要的特征；但是真實(shí)情況下這個(gè)交集不總滿足非空。相反，利用度中心性可以近似刻畫這類特征：假如一個(gè)特征度中心性最大，說明它跟網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)之間的相關(guān)程度最小，那么它被認(rèn)為無關(guān)或冗余的可能性最小，在每個(gè)不同的“最優(yōu)子集”中同時(shí)出現(xiàn)的可能最大；相反如果一個(gè)特征度中心性最小，那么它與其他所有節(jié)點(diǎn)的相關(guān)程度最大，則它很有可能被判定為冗余特征。其次，在獲取全局信息的基礎(chǔ)上，對(duì)所有特征按照重要性進(jìn)行排名，可以有效規(guī)避高分的冗余特征，同時(shí)不會(huì)因?yàn)楹唵蔚貏h除大量特征致使忽視對(duì)冗余特征的處理。

1 特征選擇相關(guān)工作

過濾方法是一類重要的特征選擇方法，可獨(dú)立應(yīng)用于數(shù)據(jù)預(yù)處理階段[20]。其中的排名方法因其簡單高效而用途廣泛。它的步驟大致如下：(1)設(shè)定特征重要度評(píng)判準(zhǔn)則；(2)根據(jù)準(zhǔn)則給特征打分；(3)選擇分?jǐn)?shù)閾值并過濾掉閾值之下的特征。排名方法根據(jù)類標(biāo)簽的使用情況又可分為有監(jiān)督排名、半監(jiān)督排名、和無監(jiān)督排名本文提出的方法即無監(jiān)督排名方法。

無監(jiān)督的排名方法將數(shù)據(jù)作為輸入，通過準(zhǔn)則為特征評(píng)分，并按要求輸出高分特征，整個(gè)過程不需使用類標(biāo)簽信息。根據(jù)不同的特征相關(guān)準(zhǔn)則，這些方法大致分3類。一類是基于相似度的方法[21]，通過衡量特征維持?jǐn)?shù)據(jù)在流形上的結(jié)構(gòu)相似性的能力判別特征重要性。首先將數(shù)據(jù)相似性編碼成為仿射矩陣?。黄浯芜x定k個(gè)特征；進(jìn)而最大化這個(gè)集合在由Α誘導(dǎo)出的仿射矩陣B上的效用。這一類中的方法因矩陣B的設(shè)計(jì)方法改變而不同。常見方法是Laplacian score(LS)以及譜特征選擇(Spectral feature selection,SPEC)[22]。在 LS中，如果 i和 j是 p-近鄰，Ai,j=Bi,j=exp{-||xi-xj||22/t}，如果不是則規(guī)定 Ai,j=Bi,j=0,其中xi為樣例，Ai,j為Α在(i,j)位置上的元素。在SPEC中Ai,j=exp{-||xi-xj||22/(2δ2)}(稱作徑向內(nèi)核核函數(shù))，B根據(jù)3個(gè)不同的打分準(zhǔn)則分別為不同的關(guān)于Α的標(biāo)準(zhǔn)化拉普拉斯矩陣的矩陣。

基于稀疏學(xué)習(xí)和流形學(xué)習(xí)，Cai等發(fā)表多類簇屬性選擇(Multi-cluster feature selection,MCFS)的方法。MCFS考慮到兩方面：最大程度保持?jǐn)?shù)據(jù)的簇結(jié)構(gòu)；被選特征的分辨能力能夠?qū)λ蓄惔囟加行?。它?個(gè)步驟：(1)選擇p近鄰(類似于LS)，建立仿射矩陣S和它的拉普拉斯矩陣L，利用譜聚類技術(shù)將數(shù)據(jù)嵌入流形結(jié)構(gòu)[23]；(2)使用譜回歸模型對(duì)特征重要性進(jìn)行度量；(3)對(duì)每一個(gè)特征打分，并選擇分?jǐn)?shù)最高的特征。同樣，利用譜分析方法，無監(jiān)督判別特征選擇(Unsupervised discriminative feature selection,UDFS)[24]及非負(fù)判別特征選擇(Nonnegative discriminative feature selection,NDFS)[25]著重對(duì)特征的分辨能力進(jìn)行建模。

第3種是統(tǒng)計(jì)類方法，其中經(jīng)典的Low Variance用于離散數(shù)據(jù)的無監(jiān)督特征選擇。給定閾值，計(jì)算特征方差。方差低于閾值的特征將被篩除。盡管這種方法可以篩選出分辨樣本點(diǎn)能力最弱的特征，但是無法處理特征冗余現(xiàn)象。

此外，還有一種經(jīng)典特征提取方法：主成分分析（Principal component analysis,PCA）。根據(jù)最大化方差的原則，原數(shù)據(jù)表的協(xié)方差矩陣通過正交變換，數(shù)據(jù)的協(xié)方差矩陣被轉(zhuǎn)化為一個(gè)對(duì)角矩陣，此對(duì)角陣上的元素按照數(shù)值大小降序排列。每個(gè)元素（即特征值）對(duì)應(yīng)于原協(xié)方差矩陣在新的坐標(biāo)系下某個(gè)維度的投影，是原特征集中元素的線性組合。

這些方法雖然在一定程度上實(shí)現(xiàn)了降維，但是不足之處在于它們處理特征結(jié)構(gòu)的能力有限。因而本文利用復(fù)雜網(wǎng)絡(luò)，對(duì)特征之間的關(guān)系進(jìn)行探索，挖掘特征之間的關(guān)聯(lián)結(jié)構(gòu)。盡管復(fù)雜網(wǎng)絡(luò)研究的往往是不規(guī)則圖，且節(jié)點(diǎn)或者連邊的數(shù)量巨大，統(tǒng)計(jì)物理的方法論仍然可以為認(rèn)知大規(guī)模關(guān)聯(lián)提供助力[26]。一些用來衡量節(jié)點(diǎn)重要性、網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性等拓?fù)湫再|(zhì)的統(tǒng)計(jì)學(xué)指標(biāo)相繼被提出。

2 基于節(jié)點(diǎn)度中心性的無監(jiān)督特征選擇

2.1 預(yù)備知識(shí)

本文使用相關(guān)系數(shù)（或稱皮爾森系數(shù)）來量化特征間（線性）相關(guān)程度，相關(guān)關(guān)系定義如下。

定義1隨機(jī)變量X1和X2的相關(guān)系數(shù)為

式中σX1和σX2分別是 X1和X2的標(biāo)準(zhǔn)差。相關(guān)系數(shù)有以下特性：(1)-1≤ρ(X1,X2)≤1；(2)ρ(X1,X2)=ρ(X2,X1)；(3)ρ有尺度不變性和平移不變性；(4)ρ對(duì)散點(diǎn)圖的旋轉(zhuǎn)敏感。在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)度用來衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。

定義2節(jié)點(diǎn)度中心性定義為

式中ki為節(jié)點(diǎn)i的度值，Z為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)。某節(jié)點(diǎn)度中心性值越大，它在網(wǎng)絡(luò)中的重要程度越高。

表1列出文章中使用的符號(hào)及其含義。

表1 符號(hào)及其含義Tab.1 Notations

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

本文在6個(gè)高維數(shù)據(jù)集上進(jìn)行方法驗(yàn)證。這些數(shù)據(jù)集描述如下（參照http：//featureselection.asu.edu）。(a)BASEHOCK，包含1 993個(gè)樣例，4 862個(gè)特征，2個(gè)類別；(b)PCMAC，包含1 943個(gè)樣例，3 289個(gè)特征，2個(gè)類別；(c)RELATHE，包含1 427個(gè)樣例，4 322個(gè)特征，2個(gè)類別；以上3個(gè)文本數(shù)據(jù)集出自于20 newsgroups原始數(shù)據(jù)集。(d)warpAR10P，包含 130個(gè)樣例，2 400個(gè)特征，10個(gè)類別；(e)warpPIE10P，包含210個(gè)樣例，2 420個(gè)特征，10個(gè)類別；以上為人臉識(shí)別數(shù)據(jù)庫中的兩個(gè)樣本。(f)USPS，包含9 298個(gè)樣例，256個(gè)特征，10個(gè)類別，為手寫體數(shù)據(jù)集。表2匯集這6個(gè)數(shù)據(jù)集。

表2 數(shù)據(jù)集說明表Tab.2 Datasets

實(shí)驗(yàn)分析中，以下所有圖示和列表中的編號(hào)(a～f)與本節(jié)數(shù)據(jù)集的編號(hào)一致。

2.3 方法步驟

本文介紹一種基于節(jié)點(diǎn)度中心性的無監(jiān)督特征選擇方法（Degree centrality based feature selection,DCFS）。先利用特征和它們的關(guān)聯(lián)構(gòu)建網(wǎng)絡(luò)G(V,E)，再通過復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)度中心性篩選符合標(biāo)準(zhǔn)的特征。基本步驟如下：

(1)算法首先計(jì)算f1,f2,…,fM兩兩間相關(guān)系數(shù)ρij?ρ(fi,fj)，進(jìn)而將所有的ρij組成相關(guān)系數(shù)矩陣(ρij)M×M，以此表示整個(gè)特征集之內(nèi)的全局關(guān)聯(lián)。

(2)對(duì)所有系數(shù)進(jìn)行歸一化,其目的是將所有特征間的相關(guān)成都放在同一尺度下進(jìn)行比較。歸一化形式為

(3)為了下一步構(gòu)建特征網(wǎng)絡(luò)并提取這一網(wǎng)絡(luò)里的拓?fù)湫畔⒁员銓ふ矣杏绊懥Φ奶卣?，需要選定篩選閾值0＜ θ＜ 1，用以過濾{ρij：ρij≥ θ}且同時(shí)保留低于閾值的關(guān)聯(lián)。其合理性在于，如果把特征視作數(shù)據(jù)聚類的參照，本文啟發(fā)式地認(rèn)為正相關(guān)性較大的兩個(gè)特征觀點(diǎn)相近，相關(guān)性較小的兩個(gè)特征往往觀點(diǎn)無法比較，而負(fù)相關(guān)性較大的觀點(diǎn)近乎相左。在這里更關(guān)注相關(guān)性小的或負(fù)相關(guān)性大的關(guān)聯(lián)。

(4)ρ的對(duì)稱性導(dǎo)致網(wǎng)絡(luò)是無向的。此外本文認(rèn)為每個(gè)小于閾值的關(guān)聯(lián)都對(duì)整個(gè)網(wǎng)絡(luò)產(chǎn)生同等的效用。令φθ是[-1,1]上的閾值函數(shù)

利用φθ將關(guān)聯(lián)關(guān)系二值化，換言之原來的由相關(guān)系數(shù)組成的鄰接陣矩陣變?yōu)榱瞬紶栃袜徑泳仃嚒?/p>

(5)將上面的布爾矩陣轉(zhuǎn)換成無向圖，其中特征是節(jié)點(diǎn)，關(guān)聯(lián)是連邊。

(6)繼而算法使用復(fù)雜網(wǎng)絡(luò)中的指標(biāo)來度量節(jié)點(diǎn)影響力，為了計(jì)算的便捷性，選取節(jié)點(diǎn)度中心性指標(biāo)。計(jì)算G(V,E)中所有特征的后將它們排序。

(7)根據(jù)特征選擇數(shù)量k,選擇排序結(jié)果最大的k個(gè)節(jié)點(diǎn)指標(biāo)進(jìn)而得到這些指標(biāo)對(duì)應(yīng)的特征。

DCFS流程見圖1。本算法結(jié)果強(qiáng)烈依賴θ的取值。θ取值不同，節(jié)點(diǎn)度中心性誘導(dǎo)出的最優(yōu)特征隨之改變。考慮以下情況：如果令θ=1,得到的網(wǎng)絡(luò)是無權(quán)無向完全圖，此時(shí)無法通過節(jié)點(diǎn)度中心性來判斷特征的重要性，算法將按照構(gòu)圖時(shí)排列特征的順序進(jìn)行特征選擇，最終導(dǎo)致特征選擇失效；θ=0意味著完全忽略了非負(fù)相關(guān)系數(shù)的關(guān)聯(lián)，那么生成的特征網(wǎng)絡(luò)便無法全面地權(quán)衡特征重要性；從圖2可以看出歸一化后的相關(guān)系數(shù)的值分布形狀不同，假如在(a)(b)或者(c)中令θ=0.5，得到的網(wǎng)絡(luò)將基本呈現(xiàn)完全圖的樣貌，預(yù)期的特征篩選結(jié)果將會(huì)非常不理想。因而選取適合歸一化后相關(guān)系數(shù)的值分布的θ非常重要。

圖1 基于度中心性的無監(jiān)督特征選擇算法Fig.1 Degree centrality based unsupervised feature selection algorithm

圖2 歸一化相關(guān)系數(shù)分布圖Fig.2 Distribution of the normalized correlation coefficients

從特征相關(guān)性來講，DCFS在保留全局信息的同時(shí)將特征冗余轉(zhuǎn)化為相關(guān)關(guān)系冗余。衡量一個(gè)特征好壞取決于它和其他所有特征之間的關(guān)系。刪除關(guān)聯(lián)可以一定程度上改善特征冗余：如果一個(gè)特征與其他特征之間的關(guān)聯(lián)都很大，那么通過合理篩選θ值，這個(gè)特征的度中心性在構(gòu)建出的網(wǎng)絡(luò)中將會(huì)比別的特征的度中心性小。

3 實(shí)驗(yàn)過程和分析

本文先進(jìn)行對(duì)照實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果比照4種降維算法：PCA，LS，MCFS，SPEC。所有方法選擇的特征分別在K均值聚類(K-means)方法上進(jìn)行驗(yàn)證，然后使用標(biāo)準(zhǔn)互信息（Normalized mutual information,NMI）來衡量預(yù)測(cè)標(biāo)簽和真實(shí)標(biāo)簽之間的差距。令c標(biāo)識(shí)真實(shí)類標(biāo)簽向量，c'表示預(yù)測(cè)類標(biāo)簽向量，它們之間的互信息MI(c,c')定義為

式中：p(ci,cj')是c和c'的聯(lián)合概率分布函數(shù)；p(ci)和p(cj')分別是c和c'的邊緣概率分布函數(shù)。NMI定義為

式中 H(c)和H(c')分別為 c和 c'的信息熵，NMI取值為[0,1]。

對(duì)比實(shí)驗(yàn)中，限定k在10～200的范圍之內(nèi)。DCFS僅有的一個(gè)參數(shù)θ，需根據(jù)數(shù)據(jù)集的特征相關(guān)系數(shù)的值分布（見圖2）進(jìn)行調(diào)整。在以下實(shí)驗(yàn)中，不同數(shù)據(jù)集上設(shè)定不同的θ值。圖3是幾種方法在6個(gè)數(shù)據(jù)上的性能示意圖，其中：圖3(a)為BASEHOCK上的對(duì)比結(jié)果，θ=0.4；圖3(b)為PCMAC上的對(duì)比結(jié)果，θ=0.2；圖3(c)為RELATHE上的對(duì)比結(jié)果，θ=0.15；圖3(d)為warpPIE10P上的對(duì)比結(jié)果，θ=0.6；圖3(e)為warpAR10P上的對(duì)比結(jié)果，θ=0.05；圖3(f)為USPS上的對(duì)比結(jié)果，θ=0.5。

圖3 對(duì)比實(shí)驗(yàn)結(jié)果Fig.3 Compared results of proposed method and other five comparative methods

DCFS在圖3(a)，(d)，(e)上表現(xiàn)出很大優(yōu)勢(shì)。(a)中特征選擇數(shù)量從70變動(dòng)到140的過程中，DCFS的效果保持穩(wěn)定，此時(shí)可以認(rèn)為特征數(shù)量為70且θ=0.4時(shí)，DCFS達(dá)到最優(yōu)，之后增加的特征（排名71～140）為冗余特征，并未影響聚類算法的判別能力。當(dāng)k＞140,算法判別能力急劇下降。DCFS的性能在(d)上隨k值增大而增大。在圖3(e)上特征數(shù)量較少時(shí)略有波動(dòng)，而后趨于平穩(wěn)。圖3(b)和(c)顯示DCFS在特征數(shù)量較少時(shí)效果較好，并在某k值達(dá)到最高峰值；但是特征數(shù)量上升時(shí)，NMI劇烈震蕩并下降。圖3(f)中的DCFS方法效果并不突出，考慮到USPS數(shù)據(jù)集的特征數(shù)量，由于特征數(shù)量很少（M=256），θ取值為0.5時(shí)，特征網(wǎng)絡(luò)中的結(jié)構(gòu)不夠清晰，所有節(jié)點(diǎn)的度中心性比較接近，所以導(dǎo)致對(duì)K均值聚類的效果提升并不大；在θ=0.1時(shí)，特征網(wǎng)絡(luò)只有很少的節(jié)點(diǎn)(34個(gè))和連邊（62個(gè)），不足以反映全局的特征結(jié)構(gòu)。圖4中圖3(d)和(e)數(shù)據(jù)集從類型、特征數(shù)量和標(biāo)簽數(shù)量等方面看非常相似，結(jié)果卻不太相同，可能的原因?yàn)椋禾卣飨蛄康木S度決定關(guān)聯(lián)度的準(zhǔn)確性。實(shí)際上，此時(shí)選擇結(jié)果顯示，樣例少的warpAR10P（N=130）的準(zhǔn)確度低于在warpPIE10P（N=210）上的準(zhǔn)確度。圖2所示為USPS在不同閾值下的特征網(wǎng)絡(luò)G(V,E)。表3為6種方法的性能比較。

圖4 USPS在不同[θ]下構(gòu)建的網(wǎng)絡(luò)Fig.4 Feature network of USPS under different[θ]

表3 各特征選擇方法最佳性能對(duì)比Tab.3 NMI value comparison among six methods

從圖2處觀察到在3個(gè)（離散）文本數(shù)據(jù)上相關(guān)系數(shù)的分布聚集在很窄的范圍；相反3個(gè)連續(xù)數(shù)據(jù)集上的分布相對(duì)平滑。其原因是在這些離散的高維數(shù)據(jù)中數(shù)據(jù)更加稀疏。對(duì)于j≠k，稀疏程度高將大概率導(dǎo)致xij≠xik?？梢钥吹紻CFS方法比其他方法更適合處理類似旳稀疏數(shù)據(jù)。

為了測(cè)試DCFS在數(shù)據(jù)集上的穩(wěn)定性，本文接下來研究NMI關(guān)于θ和k的變化。從θ方向改變時(shí)，網(wǎng)絡(luò)結(jié)構(gòu)會(huì)發(fā)生變化，重要的節(jié)點(diǎn)隨之變動(dòng)進(jìn)而影響實(shí)驗(yàn)精度，實(shí)驗(yàn)精度在某θ處浮動(dòng)越劇烈表明獲得的特征子集變動(dòng)越大；沿k方向變化時(shí)，精度的變化表征了冗余特征數(shù)量的增減。這個(gè)實(shí)驗(yàn)的θ和k的取值范圍維持之前對(duì)照實(shí)驗(yàn)設(shè)置，同時(shí)將θ的步長設(shè)為0.05，再使用網(wǎng)格搜索方法計(jì)算對(duì)應(yīng)于所有(θ,k)的NMI值，并繪制三維直方圖。圖5所示為6個(gè)數(shù)據(jù)集上的三維直方圖。k較小時(shí)（實(shí)驗(yàn)中取10～200），DCFS產(chǎn)生最大峰值的位置相對(duì)集中。在RELATHE集上，存在1個(gè)非常顯著的極大值，說明DCFS在RELATHE上極不穩(wěn)定；另外2個(gè)文本數(shù)據(jù)集上有限個(gè)局部取得顯著NMI值；剩余3個(gè)連續(xù)數(shù)據(jù)集上的變化比較平緩，算法對(duì)θ和k的變化不敏感。

圖 5 NMI-(θ,k)三維直方圖Fig.5 3D histogram of NMI-(θ,k)

4 結(jié)束語

本文將復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)度中心性引入特征選擇，構(gòu)建出的特征網(wǎng)絡(luò)的結(jié)構(gòu)隨閾值而變化，具有靈活適應(yīng)數(shù)據(jù)集中特征關(guān)聯(lián)結(jié)構(gòu)的能力，有助于選出同數(shù)據(jù)標(biāo)簽關(guān)聯(lián)度最大的特征子集。另一方面，閾值θ的調(diào)節(jié)還在一定程度上緩解了特征冗余現(xiàn)象。實(shí)驗(yàn)結(jié)果表明在一些高維稀疏數(shù)據(jù)集上此方法是可行的。這種將復(fù)雜網(wǎng)絡(luò)拓?fù)湫再|(zhì)和特征選擇結(jié)合的方式還有很大改進(jìn)空間。本文方法利用統(tǒng)一θ值篩除不符合條件的關(guān)聯(lián)，雖然可以處理冗余現(xiàn)象，但是也過濾掉一些有用特征。使用集成方法設(shè)置多樣性更強(qiáng)的選擇框架有望改進(jìn)這一缺陷。其次，相關(guān)系數(shù)局限于量化變量的線性關(guān)系，從而忽略數(shù)據(jù)中的大量而復(fù)雜的非線性關(guān)聯(lián)。下一階段的研究將探索一種適用性更廣的關(guān)聯(lián)度量。另外，本文算法考慮到計(jì)算成本，選擇了方便計(jì)算的節(jié)點(diǎn)度中心性來構(gòu)建特征關(guān)聯(lián)網(wǎng)絡(luò)。為更好地尋找特征網(wǎng)絡(luò)間的結(jié)構(gòu)，更細(xì)致地探索特征間可能廣泛存在的聯(lián)系，未來也將考察其他拓?fù)渲笜?biāo)的合理性。