決策依賴聚類的高維數(shù)據(jù)特征選擇①

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

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

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

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

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

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

1 決策依賴特征聚類方法

基于聚類思想的特征選擇方法是通過構(gòu)建數(shù)據(jù)特征間相似性度量， 采用K-均值[10]或其他聚類方法將特征劃分為不相交的子簇． 現(xiàn)有大部分方法在構(gòu)建特征相似圖時只考慮特征間的相似性， 忽略數(shù)據(jù)的標(biāo)簽信息， 導(dǎo)致數(shù)據(jù)特征與其對應(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)聚類簇數(shù)， 我們結(jié)合簇內(nèi)冗余度和簇間冗余度給出一種最優(yōu)特征簇的選擇方法．

1.1 鄰域粗糙集基本概念

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

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

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

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

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

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

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

(1)

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

證明： 顯然．

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

1.3 基于冗余度的特征聚類

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

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

(2)

稱W為特征冗余度矩陣．

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

假設(shè)將特征冗余圖G劃分成k個連通子圖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的拉普拉斯矩陣，Λ為對角矩陣， 其對角線元素分別為冗余度矩陣W對應(yīng)的行元素之和．

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

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

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

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

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

(5)

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

(6)

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

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

(7)

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

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

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

(8)

為特征ai的依存度．

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

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

(9)

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

下面我們以一個具體實例說明中心特征與其依存度和中心度間的關(guān)聯(lián)性． 從UCI數(shù)據(jù)庫中選取glass數(shù)據(jù)集， 并從中隨機抽取6個樣本， 如下表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)分別計算10個特征的依存度和中心度， 見圖1． 在該圖中， 同一個類簇中的特征用同一種符號和相同顏色的點表示， 不同簇中特征用不同符號和不同顏色表示．

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

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

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

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

輸入: 訓(xùn)練數(shù)據(jù)集IS=, m為特征數(shù), 鄰域參數(shù)δ, 指定聚類個數(shù)范圍Ξ; 輸出: 特征子集S. BEGIN1.初始化被選特征子集S=Φ, 全部特征集合為F; 2.for each k∈Ξ; // Ξ: 指定聚類個數(shù)范圍3.基于公式(4)實現(xiàn)特征聚類; 4.計算公式(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, 計算中心度(9); 10. bi=arg maxai∈Aj I(ai; D); // 選出每個簇內(nèi)中心度最大的特征11. end for12.end for13.特征子集S={b1, b2, …, bk'}.END

3 模擬實驗及結(jié)果分析

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

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

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

(10)

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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