決策依賴聚類的高維數據特征選擇①

鄧廷權，辛麗穎

哈爾濱工程大學 數學科學學院， 哈爾濱 150001

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

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

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

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

1 決策依賴特征聚類方法

基于聚類思想的特征選擇方法是通過構建數據特征間相似性度量， 采用K-均值[10]或其他聚類方法將特征劃分為不相交的子簇． 現有大部分方法在構建特征相似圖時只考慮特征間的相似性， 忽略數據的標簽信息， 導致數據特征與其對應決策類之間缺乏必要的關聯性．

本節將基于鄰域粗糙集理論構建一種決策依賴的特征聚類方法． 在回顧鄰域粗糙集及相關概念基礎上， 提出一種基于決策依賴度的鄰域依賴度增益的構造方法， 并探討了其性質． 基于特征間鄰域依賴度度量構建特征相似圖， 采用譜聚類方法獲得特征的類簇結構． 為了獲得特征的最優聚類簇數， 我們結合簇內冗余度和簇間冗余度給出一種最優特征簇的選擇方法．

1.1 鄰域粗糙集基本概念

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

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

下近似可以理解為由鄰域信息粒完全包含在X中的對象構成， 上近似包含鄰域信息粒可能屬于X的對象全體． 在知識發現中， 上近似和下近似被用于對集合X做逼近描述．

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

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

1.2 決策依賴特征關聯性度量

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

(1)

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

證明： 顯然．

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

1.3 基于冗余度的特征聚類

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

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

(2)

稱W為特征冗余度矩陣．

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

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

(3)

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

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

(4)

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

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

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

1.4 最優特征簇結構

由于K-均值聚類方法需要事先給定類簇數， 但數據特征的類簇數并不明確． 為了獲得特征的最優聚類結果， 引入一種特征聚類簇數的評估度量方法指導特征類簇數的選取．

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

(5)

為Ai的簇內平均冗余度； 稱

(6)

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

最優聚類結果應具有簇內特征冗余度最大而簇間特征最不相關的特點， 也即簇內平均冗余度最大而簇間平均冗余度最小． 因此， 構造如下最優類簇結構評估指標：

(7)

2 簇內特征選擇機制

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

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

(8)

為特征ai的依存度．

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

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

(9)

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

下面我們以一個具體實例說明中心特征與其依存度和中心度間的關聯性． 從UCI數據庫中選取glass數據集， 并從中隨機抽取6個樣本， 如下表1．

表1 glass數據集中部分數據

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

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

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

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

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

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

3 模擬實驗及結果分析

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

表2 數據描述及特征選擇結果

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

(10)

圖2繪出了表2中前4個數據集特征對的不同聚類數目對應的類簇結構評價指標和鄰域投票精度的變化情況． 其中不同線形、 不同顏色分別代表數據的類簇結構評價指標和鄰域投票精度的變化情況．

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

圖2 類簇結構評價指標和精度的變化

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

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

表3 特征子集中的特征數

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

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

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

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

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

4 結論

本文基于鄰域粗糙集模型建立了一種特征聚類驅動的特征選擇方法． 該方法不同于現有啟發式特征選擇和基于特征聚類的特征選擇， 從特征依賴度出發構建了特征冗余圖， 給出了最優特征冗余圖聚類準則和聚類方法． 在此基礎上， 通過引入簇內特征依存度和中心度的概念， 給出了特征依賴聚類的特征選擇算法． 理論分析和多個數據集上的對比實驗結果表明新提出的特征選擇方法不僅可以選出特征數更小的特征子集， 其對應的分類精度還得以提高．

本文中最優特征簇結構的評估指標通過遍歷方式得到， 探索一種特征類簇數自適應確定方法是很有意義的． 通過分析特征與特征間的因果關聯， 基于有向特征圖圖割的特征選擇方法是一個值得深入研究的問題．