鄧廷權(quán)，辛麗穎

哈爾濱工程大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 哈爾濱 150001

隨著信息時(shí)代的高速發(fā)展， 大數(shù)據(jù)成為這個(gè)時(shí)代最具代表性的標(biāo)志之一． 如何在規(guī)模龐大、結(jié)構(gòu)復(fù)雜的高維數(shù)據(jù)中挖掘出最有價(jià)值的信息是研究人員和技術(shù)工作的熱點(diǎn)關(guān)注問(wèn)題． 特征選擇是一種有效的高維數(shù)據(jù)預(yù)處理方法， 旨在去除數(shù)據(jù)中的冗余和不相關(guān)信息， 降低數(shù)據(jù)維度和學(xué)習(xí)算法的計(jì)算復(fù)雜度， 是人工智能基礎(chǔ)理論中的熱點(diǎn)研究主題．

特征選擇[1]可分為嵌入式、封裝式和過(guò)濾式等諸多方法． 嵌入式特征選擇[2]將特征選擇與學(xué)習(xí)器融合， 在學(xué)習(xí)器訓(xùn)練過(guò)程中自動(dòng)地進(jìn)行特征選擇． 該方法缺乏特征選擇的可解釋性． 封裝式特征選擇[3]通過(guò)從初始特征集合中不斷地選擇特征子集和訓(xùn)練學(xué)習(xí)器， 根據(jù)學(xué)習(xí)器的性能來(lái)對(duì)子集進(jìn)行評(píng)價(jià)， 直到選擇出最佳的子集． 多次訓(xùn)練學(xué)習(xí)器導(dǎo)致封裝式特征選擇方法的計(jì)算復(fù)雜度很高． 過(guò)濾式方法[4]通過(guò)設(shè)計(jì)特征評(píng)估度量或相關(guān)統(tǒng)計(jì)量， 通過(guò)閾值法或啟發(fā)式搜索方法選出具有代表性的特征． 常用的特征評(píng)估度量有熵、互信息、信息增益、基尼系數(shù)等等． 基于粗糙集[5]、鄰域粗糙集[6]和模糊鄰域粗糙集[7]的特征選擇方法是一類重要的啟發(fā)式特征選擇方法， 通過(guò)設(shè)計(jì)具有良好性質(zhì)的特征評(píng)價(jià)函數(shù)， 確保選出的特征子集保持甚至超過(guò)原始特征的分類能力， 因而得以廣泛研究．

啟發(fā)式特征選擇方法需要多次遍歷所有候選特征， 一些與分類無(wú)關(guān)或?qū)Ψ诸惒划a(chǎn)生影響的冗余特征可能會(huì)被反復(fù)計(jì)算， 在數(shù)據(jù)維度很高的情況下消耗大量的計(jì)算資源． 鑒于此， 基于特征聚類的特征選擇方法應(yīng)運(yùn)而生． 該類方法的主旨思想是通過(guò)構(gòu)建描述數(shù)據(jù)特征間相似性和關(guān)聯(lián)性的度量， 采用某種聚類方法對(duì)特征聚類， 并在各類簇中選擇有代表性的特征作為特征選擇子集． 文獻(xiàn)[8]利用余弦函數(shù)刻畫特征向量之間的相似性， 采用K-均值對(duì)特征聚類， 選擇每一簇的中心特征構(gòu)成特征子集． 該方法在特征聚類時(shí)僅考慮到特征間的相似性， 缺乏特征與決策間的依賴關(guān)系， 不能確保選出的特征子集具有獨(dú)立性和最強(qiáng)的辨識(shí)能力． 文獻(xiàn)[9]基于熵和信息增益概念構(gòu)建集合間不確定性度量， 描述特征間的相關(guān)性和特征與決策間的關(guān)聯(lián)性， 刪除不確定度小于某一閾值的特征， 構(gòu)建以剩余特征為頂點(diǎn)、以特征間的不確定度為邊權(quán)的最小生成樹， 通過(guò)閾值法獲得特征的簇結(jié)構(gòu)， 并在每個(gè)簇中選擇一個(gè)與決策關(guān)聯(lián)性最大的特征作為特征選擇的特征子集． 該方法既考慮了特征間的相關(guān)性， 也分析了特征與決策間的關(guān)聯(lián)性， 但缺少特征集與決策間的依賴性以及特征集中元素的冗余性等方面的探索．

針對(duì)上述現(xiàn)有特征聚類驅(qū)動(dòng)的特征選擇存在的缺陷， 本文提出一種決策依賴聚類的高維數(shù)據(jù)特征選擇方法． 首先， 在鄰域粗糙集模型基礎(chǔ)上分析了決策關(guān)于特征對(duì)的依賴度與決策關(guān)于單一特征的依賴度間的關(guān)系， 構(gòu)建了特征冗余度度量和特征冗余圖， 依據(jù)圖割理論獲得特征劃分子集． 為了獲得最優(yōu)的特征分割， 提出了一種簇內(nèi)特征冗余度最大、簇間特征冗余度最小的聚類簇?cái)?shù)評(píng)估方法． 通過(guò)分析聚類簇中特征關(guān)于決策的互信息及特征依存度度量， 提出一種中心度和依存度聯(lián)合的特征子集確定策略， 實(shí)現(xiàn)高維數(shù)據(jù)的特征選擇．

1 決策依賴特征聚類方法

基于聚類思想的特征選擇方法是通過(guò)構(gòu)建數(shù)據(jù)特征間相似性度量， 采用K-均值[10]或其他聚類方法將特征劃分為不相交的子簇． 現(xiàn)有大部分方法在構(gòu)建特征相似圖時(shí)只考慮特征間的相似性， 忽略數(shù)據(jù)的標(biāo)簽信息， 導(dǎo)致數(shù)據(jù)特征與其對(duì)應(yīng)決策類之間缺乏必要的關(guān)聯(lián)性．

本節(jié)將基于鄰域粗糙集理論構(gòu)建一種決策依賴的特征聚類方法． 在回顧?quán)徲虼植诩跋嚓P(guān)概念基礎(chǔ)上， 提出一種基于決策依賴度的鄰域依賴度增益的構(gòu)造方法， 并探討了其性質(zhì)． 基于特征間鄰域依賴度度量構(gòu)建特征相似圖， 采用譜聚類方法獲得特征的類簇結(jié)構(gòu)． 為了獲得特征的最優(yōu)聚類簇?cái)?shù)， 我們結(jié)合簇內(nèi)冗余度和簇間冗余度給出一種最優(yōu)特征簇的選擇方法．

1.1 鄰域粗糙集基本概念

設(shè)DIS=〈U，A，V，D〉為一個(gè)決策信息系統(tǒng)， 其中U={x1，x2， …，xn}為非空論域，A={a1，a2， …，am}為條件屬性集， 也稱特征集，V是對(duì)象關(guān)于屬性的(實(shí)數(shù))值集，D為決策屬性． 對(duì)?x∈U，B?A，x由B確定的δ鄰域信息粒[6]為

對(duì)任意X?U，B?A和δ>0，X的關(guān)于B的δ下近似和δ上近似[6]分別定義為

下近似可以理解為由鄰域信息粒完全包含在X中的對(duì)象構(gòu)成， 上近似包含鄰域信息粒可能屬于X的對(duì)象全體． 在知識(shí)發(fā)現(xiàn)中， 上近似和下近似被用于對(duì)集合X做逼近描述．

在決策信息系統(tǒng)DIS=〈U，A，V，D〉中， 記U關(guān)于決策屬性集D的劃分為U/D={D1，D2， …，DM}， 則對(duì)任意B?A和δ>0， 決策屬性集D的關(guān)于B的δ上近似、下近似和邊界[11]可分別表示為

決策屬性集D關(guān)于條件屬性子集B的δ正域和依賴度[11]分別定義為

1.2 決策依賴特征關(guān)聯(lián)性度量

依賴度反映的是決策屬性與條件屬性間的依賴關(guān)系． 為了探討屬性對(duì)間的關(guān)系及其對(duì)決策產(chǎn)生的影響， 本文構(gòu)建決策依賴屬性(特征)間的相似度度量． 該度量既描述決策屬性與特征對(duì)的依賴性， 又刻畫特征間的關(guān)聯(lián)性和相似性．

(1)

為特征ai和aj的平均鄰域依賴度增益．

證明： 顯然．

性質(zhì)3表明： 特征ai，aj以及二者的聯(lián)合{ai，aj}產(chǎn)生的鄰域信息粒關(guān)于決策的認(rèn)識(shí)是相同的(下近似相同)． 在這種情況下， 兩個(gè)特征存在冗余性， 最多僅需一個(gè)特征即可刻畫對(duì)象的決策特性．

1.3 基于冗余度的特征聚類

基于1.2節(jié)的分析， 如果兩個(gè)特征的聯(lián)合依賴度增益低， 該特征對(duì)具有高的冗余度． 反之， 如果其聯(lián)合依賴度增益越高， 則特征對(duì)決策分類越是必要的， 且這兩個(gè)特征的冗余性越低． 鑒于此， 本文構(gòu)建特征冗余圖， 并借助圖割理論對(duì)特征做劃分， 形成特征冗余簇．

定義2給定一個(gè)決策信息系統(tǒng)DIS=〈U，A，V，D〉，δ>0， 記W=(wij)m×m， 其中

(2)

稱W為特征冗余度矩陣．

顯然，W是一個(gè)相似矩陣， 也可修正W， 將其對(duì)角線元素全賦值為0， 表明特征和自身不存在冗余性問(wèn)題． 在后續(xù)的特征冗余圖圖割劃分中， 特征冗余度矩陣修正與否對(duì)后續(xù)結(jié)果沒(méi)有實(shí)質(zhì)影響． 將特征集A中的元素作為頂點(diǎn)， 將任意兩個(gè)特征間的冗余度wij作為對(duì)應(yīng)頂點(diǎn)間的邊權(quán)值， 形成一個(gè)特征冗余圖G． 該圖是一個(gè)加權(quán)無(wú)向圖．

假設(shè)將特征冗余圖G劃分成k個(gè)連通子圖A1，A2，…，Ak， 構(gòu)建圖割損失函數(shù)[12]

(3)

稱H=(hij)m×k為指標(biāo)矩陣， 其滿足H′H=Ik×k． 這樣， (3)式可轉(zhuǎn)化為如下的矩陣形式

Loss(A1， …，Ak)=tr(H′LH)

(4)

其中L=Λ-W， 稱之為圖G的拉普拉斯矩陣，Λ為對(duì)角矩陣， 其對(duì)角線元素分別為冗余度矩陣W對(duì)應(yīng)的行元素之和．

求解(3)式或(4)式的極小值問(wèn)題是一個(gè)NP難問(wèn)題． 將損失函數(shù)(4)連續(xù)化， 根據(jù)Rayleigh-Ritz定理[13]， 目標(biāo)函數(shù)(4)的最優(yōu)解H為L(zhǎng)的前k個(gè)最小非零特征值對(duì)應(yīng)的特征向量按列組成的矩陣．

矩陣H的每個(gè)列向量實(shí)質(zhì)上就是圖G頂點(diǎn)被分割后的簇標(biāo)． 為了獲取明確的簇標(biāo)特征， 采用常用的K-均值聚類方法對(duì)矩陣H的行向量聚類． K-均值聚類結(jié)果代表了特征的類簇結(jié)構(gòu)．

1.4 最優(yōu)特征簇結(jié)構(gòu)

由于K-均值聚類方法需要事先給定類簇?cái)?shù)， 但數(shù)據(jù)特征的類簇?cái)?shù)并不明確． 為了獲得特征的最優(yōu)聚類結(jié)果， 引入一種特征聚類簇?cái)?shù)的評(píng)估度量方法指導(dǎo)特征類簇?cái)?shù)的選?。?/p>

假設(shè)特征集A的聚類結(jié)果為FC={A1，A2， …，Ak}， 其中Ai={ai1，ai2， …，ai|Ai|}為A的第i簇特征集， 稱

(5)

為Ai的簇內(nèi)平均冗余度； 稱

(6)

為兩個(gè)特征簇Ai={ai1，ai2， …，ai|Ai|}和Aj={aj1，aj2， …，aj|Aj|}的簇間平均冗余度．

最優(yōu)聚類結(jié)果應(yīng)具有簇內(nèi)特征冗余度最大而簇間特征最不相關(guān)的特點(diǎn)， 也即簇內(nèi)平均冗余度最大而簇間平均冗余度最?。?因此， 構(gòu)造如下最優(yōu)類簇結(jié)構(gòu)評(píng)估指標(biāo)：

(7)

2 簇內(nèi)特征選擇機(jī)制

在特征聚類基礎(chǔ)上， 本節(jié)將探討簇內(nèi)特征選擇策略． 互信息是度量?jī)蓚€(gè)隨機(jī)變量間相關(guān)性的重要指標(biāo)[14]； 本文提出一種基于互信息的簇內(nèi)特征選擇方法．

假設(shè)特征集A的聚類結(jié)果為FC={A1，A2， …，Ak}， 對(duì)任意特征ai∈A， 存在唯一類簇Aj， 使得ai∈Aj， 稱

(8)

為特征ai的依存度．

特征的依存度表示該特征與其簇內(nèi)其他特征的平均冗余度． 特別地， 如果某一特征簇中僅有一個(gè)元素， 則該元素的依存度為0．

設(shè)對(duì)象集關(guān)于決策屬性D的劃分為U/D={D1，D2， …，DM}， 對(duì)任意特征ai∈A， 存在唯一類簇Aj， 使得ai∈Aj，ai關(guān)于決策D的互信息可表示為

(9)

中心特征是與決策具有最大互信息的特征， 是該簇中最具代表性特征． 根據(jù)聚類思想， 中心特征與該簇中其余特征間具有最大的冗余性． 另一方面， 不同簇中的中心特征具有最小的冗余性和最大的獨(dú)立性， 而且， 由于特征類簇是按照特征簇內(nèi)冗余度最大、簇間冗余度最小確定的最優(yōu)特征分割模式， 將每個(gè)簇的中心特征作為特征選擇子集是合理的， 也是足夠的． 簡(jiǎn)記這種特征選擇方法為RDCFS．

下面我們以一個(gè)具體實(shí)例說(shuō)明中心特征與其依存度和中心度間的關(guān)聯(lián)性． 從UCI數(shù)據(jù)庫(kù)中選取glass數(shù)據(jù)集， 并從中隨機(jī)抽取6個(gè)樣本， 如下表1．

表1 glass數(shù)據(jù)集中部分?jǐn)?shù)據(jù)

記其特征為A={a1，a2， …，a10}， 將數(shù)據(jù)歸一化后， 按照第1節(jié)方法得到特征聚類結(jié)果：A1={a1，a6}，A2={a2，a4，a7，a9，a10}，A3={a3，a5，a8}． 根據(jù)式(8)和(9)分別計(jì)算10個(gè)特征的依存度和中心度， 見(jiàn)圖1． 在該圖中， 同一個(gè)類簇中的特征用同一種符號(hào)和相同顏色的點(diǎn)表示， 不同簇中特征用不同符號(hào)和不同顏色表示．

圖1 特征依存度和中心度分布

從圖1可以看出， 在同一個(gè)簇內(nèi)， 中心度越大的特征， 在該簇內(nèi)的依存度也越大， 中心特征的依存度最大． 易見(jiàn)，a6，a2和a3的中心度和依存度在對(duì)應(yīng)簇中最大， 它們分別就是簇A1，A2和A3的中心特征． 因此， {a2，a3，a6}是A的最優(yōu)特征選擇子集．

綜合上述分析， 下面給出決策系統(tǒng)的基于決策依賴聚類的特征選擇算法．

算法1 基于決策依賴聚類的特征選擇算法(RDCFS)

輸入: 訓(xùn)練數(shù)據(jù)集IS=, m為特征數(shù), 鄰域參數(shù)δ, 指定聚類個(gè)數(shù)范圍Ξ; 輸出: 特征子集S. BEGIN1.初始化被選特征子集S=Φ, 全部特征集合為F; 2.for each k∈Ξ; // Ξ: 指定聚類個(gè)數(shù)范圍3.基于公式(4)實(shí)現(xiàn)特征聚類; 4.計(jì)算公式(5),(6),(7); 5.end for6.k'=arg minkC(k)index ; // 選出最優(yōu)簇類數(shù)7.FC={A1, A2, …, Ak'}; 8.for each Ai∈FC9.for each ai∈Aj, 計(jì)算中心度(9); 10. bi=arg maxai∈Aj I(ai; D); // 選出每個(gè)簇內(nèi)中心度最大的特征11. end for12.end for13.特征子集S={b1, b2, …, bk'}.END

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

為了驗(yàn)證本文提出的特征選擇方法的合理性和有效性， 從UCI數(shù)據(jù)庫(kù)中選取8個(gè)數(shù)值型數(shù)據(jù)集， 詳細(xì)信息見(jiàn)表2． 利用這8個(gè)數(shù)據(jù)集驗(yàn)證本文所提特征選擇方法選出的特征子集在分類精度上的性能．

表2 數(shù)據(jù)描述及特征選擇結(jié)果

首先以表2中前4個(gè)數(shù)據(jù)集為例驗(yàn)證根據(jù)式(7)選取聚類數(shù)的合理性． 實(shí)驗(yàn)采取十折交叉驗(yàn)證的方法． 根據(jù)鄰域粗糙集特征選擇方法鄰域參數(shù)的一般選取規(guī)則， 本文中δ在區(qū)間[0.01， 0.5]內(nèi)取值． 給定類簇?cái)?shù)的取值范圍， 以一定步長(zhǎng)通過(guò)遍歷方法得到使式(7)達(dá)到最小的聚類數(shù)目． 在聚類基礎(chǔ)上， 在每個(gè)簇內(nèi)選擇中心度最高的特征形成特征子集． 采用如下所述鄰域投票精度作為特征選擇有效性的度量指標(biāo)．

(10)

圖2繪出了表2中前4個(gè)數(shù)據(jù)集特征對(duì)的不同聚類數(shù)目對(duì)應(yīng)的類簇結(jié)構(gòu)評(píng)價(jià)指標(biāo)和鄰域投票精度的變化情況． 其中不同線形、 不同顏色分別代表數(shù)據(jù)的類簇結(jié)構(gòu)評(píng)價(jià)指標(biāo)和鄰域投票精度的變化情況．

由圖2分析可知， 給定一定的聚類數(shù)目范圍： 在CT和wpbc兩個(gè)數(shù)據(jù)集上， 類簇結(jié)構(gòu)評(píng)價(jià)指標(biāo)達(dá)到極小， 即將特征分別聚成17類和14類時(shí)， 鄰域投票精度達(dá)到最高； 在sonar和autovalve_B兩個(gè)數(shù)據(jù)集的類簇結(jié)構(gòu)評(píng)價(jià)指標(biāo)達(dá)到極小時(shí)， 所選特征的鄰域投票精度達(dá)到次最高， 且當(dāng)聚類數(shù)目逐漸增加時(shí)， 鄰域投票精度呈現(xiàn)下降趨勢(shì)． 這說(shuō)明， 我們構(gòu)造的類簇結(jié)構(gòu)評(píng)價(jià)指標(biāo)能夠驅(qū)動(dòng)確定有效的聚類數(shù)目， 從而促進(jìn)特征選擇的精度提高．

圖2 類簇結(jié)構(gòu)評(píng)價(jià)指標(biāo)和精度的變化

為了進(jìn)一步驗(yàn)證本文提出方法的優(yōu)勢(shì)， 分別與聯(lián)合譜聚類與鄰域互信息的特征選擇算法(SCNMI)[15]、基于特征聚類的特征選擇方法(FSFC)[16]、模糊粗糙測(cè)度特征選擇(FRSE)[17]和模糊鄰域粗糙集特征選擇(FNRS)[7]4種特征選擇方法在8個(gè)數(shù)據(jù)集上進(jìn)行模擬實(shí)驗(yàn)比較． 表3給出了5種特征選擇方法對(duì)8個(gè)數(shù)據(jù)集做出的特征選擇結(jié)果， 其中的數(shù)值代表最終特征選擇子集中的特征數(shù)．

從表3可以看出， 在8個(gè)數(shù)據(jù)集的實(shí)驗(yàn)中， 本文所提方法(RDCDS)在7個(gè)數(shù)據(jù)集上都選出了最優(yōu)(最小)特征子集， 尤其對(duì)高維數(shù)據(jù)集具有更好的降維作用．

表3 特征子集中的特征數(shù)

為了驗(yàn)證特征子集的分類能力， 分別采用KNN分類器(本文取K=3)和支持向量機(jī)分類器(SVM)對(duì)數(shù)據(jù)集在特征選擇前后的分類效果進(jìn)行了對(duì)比實(shí)驗(yàn)， 各個(gè)方法在不同數(shù)據(jù)集上的分類精度如表4和表5所示．

從表4和表5可以看出， 不論采用KNN分類器還是SVM分類器， 在8個(gè)數(shù)據(jù)集的實(shí)驗(yàn)中本文所提方法(RDCDS)在5個(gè)數(shù)據(jù)集上取得了最高的分類精度． FNRS在2個(gè)數(shù)據(jù)集上取得了最高KNN分類精度， FSFC只在一個(gè)數(shù)據(jù)集上取得最高KNN分類精度， 而SCNMI和FRSE表現(xiàn)最差． 同時(shí)， FSFC，F(xiàn)RSE和FNRS分別僅在一個(gè)數(shù)據(jù)集上取得最高的SVM分類精度， SCNMI依然表現(xiàn)最差．

表4 KNN分類器(K=3)下的分類精度

表5 SVM分類器下的分類精度

盡管如此， 特征選擇后的數(shù)據(jù)分類精度都高于原始數(shù)據(jù)的分類精度． 這一事實(shí)說(shuō)明原始數(shù)據(jù)包含冗余和不相關(guān)信息， 擾亂了對(duì)數(shù)據(jù)的分類學(xué)習(xí)， 進(jìn)一步證實(shí)特征選擇的必要性． 上述對(duì)比實(shí)驗(yàn)表明， 從統(tǒng)計(jì)學(xué)意義上講， 本文提出的特征選擇方法得到的特征子集不僅緊湊， 數(shù)據(jù)分類精度還得以顯著提高．

4 結(jié)論

本文基于鄰域粗糙集模型建立了一種特征聚類驅(qū)動(dòng)的特征選擇方法． 該方法不同于現(xiàn)有啟發(fā)式特征選擇和基于特征聚類的特征選擇， 從特征依賴度出發(fā)構(gòu)建了特征冗余圖， 給出了最優(yōu)特征冗余圖聚類準(zhǔn)則和聚類方法． 在此基礎(chǔ)上， 通過(guò)引入簇內(nèi)特征依存度和中心度的概念， 給出了特征依賴聚類的特征選擇算法． 理論分析和多個(gè)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果表明新提出的特征選擇方法不僅可以選出特征數(shù)更小的特征子集， 其對(duì)應(yīng)的分類精度還得以提高．

本文中最優(yōu)特征簇結(jié)構(gòu)的評(píng)估指標(biāo)通過(guò)遍歷方式得到， 探索一種特征類簇?cái)?shù)自適應(yīng)確定方法是很有意義的． 通過(guò)分析特征與特征間的因果關(guān)聯(lián)， 基于有向特征圖圖割的特征選擇方法是一個(gè)值得深入研究的問(wèn)題．