閆泓任 馬國帥 錢宇華

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

引 言

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

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

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

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

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

以上提到的方法有效地應用在標簽數(shù)據(jù)上，但是對于無標簽或少標簽的數(shù)據(jù)，由于無法利用標簽作為評價準則，效果不夠理想[16]。文獻[17]利用進化局部搜索算法，在無監(jiān)督的情況下，能夠同時找到特征組合和聚類數(shù)目，Cai等[18]提出基于稀疏學習的多聚類特征選擇等經(jīng)典無監(jiān)督方法（詳見第1節(jié)）。這些技術之所以能夠產(chǎn)生較好的結果，是因為它們的模型把握到樣本或特征的局部關聯(lián)，卻同時因為缺失對全局關聯(lián)的考察導致選擇過程無法得到宏觀信息。

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

1 特征選擇相關工作

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

無監(jiān)督的排名方法將數(shù)據(jù)作為輸入，通過準則為特征評分，并按要求輸出高分特征，整個過程不需使用類標簽信息。根據(jù)不同的特征相關準則，這些方法大致分3類。一類是基于相似度的方法[21]，通過衡量特征維持數(shù)據(jù)在流形上的結構相似性的能力判別特征重要性。首先將數(shù)據(jù)相似性編碼成為仿射矩陣Α；其次選定k個特征；進而最大化這個集合在由Α誘導出的仿射矩陣B上的效用。這一類中的方法因矩陣B的設計方法改變而不同。常見方法是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個不同的打分準則分別為不同的關于Α的標準化拉普拉斯矩陣的矩陣。

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

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

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

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

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

2.1 預備知識

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

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

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

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

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

表1列出文章中使用的符號及其含義。

表1 符號及其含義Tab.1 Notations

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

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

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

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

2.3 方法步驟

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

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

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

(3)為了下一步構建特征網(wǎng)絡并提取這一網(wǎng)絡里的拓撲信息以便尋找有影響力的特征，需要選定篩選閾值0＜ θ＜ 1，用以過濾{ρij：ρij≥ θ}且同時保留低于閾值的關聯(lián)。其合理性在于，如果把特征視作數(shù)據(jù)聚類的參照，本文啟發(fā)式地認為正相關性較大的兩個特征觀點相近，相關性較小的兩個特征往往觀點無法比較，而負相關性較大的觀點近乎相左。在這里更關注相關性小的或負相關性大的關聯(lián)。

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

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

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

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

(7)根據(jù)特征選擇數(shù)量k,選擇排序結果最大的k個節(jié)點指標進而得到這些指標對應的特征。

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

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

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

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

3 實驗過程和分析

本文先進行對照實驗，實驗結果比照4種降維算法：PCA，LS，MCFS，SPEC。所有方法選擇的特征分別在K均值聚類(K-means)方法上進行驗證，然后使用標準互信息（Normalized mutual information,NMI）來衡量預測標簽和真實標簽之間的差距。令c標識真實類標簽向量，c'表示預測類標簽向量，它們之間的互信息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]。

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

圖3 對比實驗結果Fig.3 Compared results of proposed method and other five comparative methods

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

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

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

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

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

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

4 結束語

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