利用混雜核模糊補互信息選擇特征

袁鐘 陳紅梅 王志紅 李天瑞

（西南交通大學計算機與人工智能學院 成都 611756）

（綜合交通大數據應用技術國家工程實驗室（西南交通大學）成都 611756）

特征選擇是一種有效的預處理方法，已經廣泛應用于數據挖掘、機器學習和模糊識別等領域[1-6].其目的是剔除冗余特征以提高學習任務的泛化能力.特征選擇方法的關鍵步驟是如何構建一個用于評價特征重要性的函數[7].這個函數可以被使用來從原始高維數據中選擇一個最小的特征子集，使得數據類的概率分布盡可能地接近使用原始特征得到的分布.目前，已經有許多特征評價函數被提出，如一致性[8]、依賴度[9]和不確定性度量[10]等.

模糊粗糙集理論首先由Dubois 等人[11]提出，它是一種能處理模糊和不確定數據的有效數學工具.模糊粗糙集理論的基本思想是使用模糊相似關系來誘導模糊信息粒，這使得它克服了經典粗糙集理論處理數值屬性數據需要做離散化處理的問題.因而，該理論可以直接應用于數值或混合特征數據.模糊粗糙集理論主要包括模型的擴展和應用.受原始模糊粗糙集模型的啟發，提出了一系列模糊粗糙集的擴展[12-14].此外，模糊粗糙集理論也已經被應用于很多領域.特征選擇是模糊粗糙集理論最重要的應用之一，已經提出了有許多基于模糊粗糙集理論的特征選擇方法[15-18].這些方法可以大致分為基于模糊依賴度的[15]、基于模糊不確定性度量的[16]和模糊區分矩陣的方法[17].

信息熵起源于信息論，它能夠建立一種衡量不確定性的有效機制.針對模糊關系的重要性，Yager[19]首先將信息熵的概念引入模糊相似關系中，然后討論了模糊信息的不確定性測度.至此，在模糊粗糙集中提出了不同形式的模糊不確定性度量，如模糊信息熵[20]，模糊補熵[21]、模糊粗糙熵[22]和模糊鄰域決策熵[23]等.許多模糊不確定性度量已經被應用到特征選擇[10,16,24-25].例如，Hu 等人[20]提出了在模糊近似空間和模糊概率近似空間中計算信息熵的廣義公式并將模糊條件熵應用于混合屬性約簡；Qian 等人[21]將補熵引入模糊粗糙集，并提出模糊補熵的定義，但所提的模糊補熵尚未應用到屬性約簡中.Zhao 等人[26]在模糊粗糙集中提出了一種基于任意模糊關系的補熵模型，并將該信息熵應用于特征選擇.然而，由模糊不確定性度量所定義的模糊互信息大部分都是非單調的，這可能導致一個不收斂的學習算法.此外，模糊不確定性度量的定義也不能很好地反映系統的不確定性.其原因是在計算模糊熵時，采用交運算來計算模糊相似關系.這樣的計算策略可能會降低高維樣本空間中模糊相似關系的辨別能力[27].因此，它可能不能真實反映樣本之間的關系.

核方法把低維空間中的非線性學習問題轉化為高維空間中的線性學習問題，該方法可以彌補模糊關系計算中交運算帶來的不足.為此，文獻[28]利用核函數生成的模糊關系粒化論域，進而構造了不同的基于核的模糊粗糙集.進一步，文獻[29-30]研究了基于核模糊粗糙集的屬性約簡.文獻[31]提出了一種基于混雜核的模糊補熵，并將其應用于無監督屬性約簡.然而，該文獻并未定義關于決策的混雜核模糊補互信息.

基于上述討論，本文基于混雜核模糊補熵，定義關于決策的混雜核模糊補互信息.進一步，基于所提關于決策的混雜核模糊補互信息，構建了一種考慮內外重要度的混雜特征選擇評價函數.進而設計了基于混雜核模糊補互信息（kernel-based fuzzy complementary mutual information,KFCMI）的特征選擇算法.最后，數據實驗結果表明在大多數情況下所提算法可以選取更少的特征且能保持或提高分類準確率.

1 預備知識

在模糊信息理論中，數據表定義為一個信息系統IS=〈U,A〉.其中：U={x1,x2,…,xn}是一個非空有限對象集；A是非空有限屬性集合.

設A:U→[0,1]是一個映射，則稱 A是U上的模糊集.?x∈U，A(x)稱為x對 A的隸屬度.論域U上全體模糊集的集合，記為F(U).設A,B ∈F(U)，對任意x∈U，一些運算定義為:

一個關于U的模糊關系 R定義為U×U的一個模糊集，即R:U×U→[0,1].?x,y∈U，如果滿足：自反性(R(x,x)=1)和對稱性(R(x,y)=R(y,x))，則稱 R是U上的模糊相似關系.

信息熵被引入模糊粗糙集理論進行相關的不確定性測量與表示，產生了不同形式[21-22,32].Qian 等人[21]提出了一種形式的模糊補熵.設 R是U上的一個模糊關系且[xi]R表示由 R生成的廣義模糊類.關于 R的模糊補熵定義為

式（1）所示的模糊補熵通過交運算來定義模糊信息粒.這樣的策略可能會降低高維樣本空間中模糊相似度的差異[27].因此，模糊信息粒可能不能真實反映對象的粒結構.此外，由上述模糊補熵定義的模糊補互信息是非單調的.為此，本文定義關于決策的混雜核模糊補互信息，進而構建了一種考慮內外重要度的有監督特征選擇評價函數.

2 利用混雜核模糊補互信息選擇特征

2.1 混雜核函數

假設U={x1,x2,…,xn}，E?A={a1,a2,…,am}且?xi∈U和a∈A，a(xi)表示xi在a下的取值.

現在生活中存在大量的分類、數值和混合屬性數據.對于分類屬性子集Ec?A，利用匹配核[30]來計算xi和xj關于Ec的模糊相似關系，其定義為

對于數值屬性子集En?A，高斯核[31]被使用來抽取xi和xj關于En的模糊相似關系，其計算方式為是xi和xj之間關于En的歐氏距離；σ用于

其中調整基于混雜核的模糊近似空間的粒度，它反映了人們對數值屬性中數據噪聲的容忍程度.

性質1.對?E?A,有

性質2.如果E1?E2?C,則

容易看到上述混雜核函數滿足自反和對稱的性質.因此，通過上述這些核函數計算的關系是模糊相似關系.

2.2 不確定性度量

從性質4 可以看出，在相同的屬性下，較大的核參數 σ會導致更粗的粒度.σ的取值越大，則任意一對對象之間的相似程度也越大.在這種情況下，很難將任意的對象與其他對象區分開來.結果，模糊補熵越低.

當A=C∪D且C∩D=?時，該信息系統被稱為決策系統（decision system,DS），其中C表示條件屬性集，D表示決策屬性集.基于上述模糊補熵，?B?C，以下給出關于決策屬性集D的模糊補聯合熵、模糊補條件熵和模糊補互信息的概念.

定義3.B和D的 模糊補聯合熵定義為

定義4.D關于B的模糊補條件熵定義為

性質5.CH(D|B)=CH(B,D)-CH(B).

證明.根據定義2 和定義3，有

性質6.如果B1?B2?C，則CH(D|B1)≥CH(D|B2).

定義5.B和D的模糊補互信息定義為

性質7.設B?C，有3 個等式成立：

證明.由定義5，顯然有CMI(B;D)=CMI(D;B)，因此性質7 的等式1）成立.因為

所以，性質7 的等式2）成立.由性質5，易證性質7 的等式3）成立. 證畢.

在性質7 的等式2）中,B和D的模糊補互信息為D的模糊補熵減去D關于B的模糊補條件熵，因此B和D的模糊補互信息反映了B和D共同含有的模糊補信息量，體現了2 個屬性集B和D之間相關性程度，這與其他形式互信息熵的結論是完全一致的.

性質8.如果B1?B2?C，則CMI(B1;D)≤CMI(B2;D).

證明.設B1?B2?C，則有kB1?kB2.由性質6 和性質7 的等式2），易證CMI(B1;D)≤CMI(B2;D).證畢.

性質8 表明模糊補互信息與特征子集大小的單調性變化.這些性質對設計一個啟發式搜索算法是至關重要的.因為這保證了向已選取的特征子集中添加候選特征不會減少新特征子集的信息.因此，上述定義的模糊補互信息可以用來作為特征選擇的標準.

2.3 屬性重要度

特征選擇的關鍵問題是建立屬性質量的評價函數.B和D的模糊補互信息體現了B和D之間相關性程度.因此，基于模糊補互信息，分別構建了2 種屬性重要度評價函數.

定義6.對?b∈B，屬性b在B中相對于D的 內重要度定義為

定義7.對?b∈C-B，屬性b在B中相對于D的 外重要度定義為

由性質8，sigin(a,B,D)越高，表示a越重要.

如果sigin(c,C,D)＞ε，屬性c是 ε-必不可少的，也就是說，c是一個 ε-核屬性.

定義8.C的核屬性集定義為

基于核屬性的啟發式屬性約簡算法可以通過將選定的屬性逐步添加到核屬性集中來找到一個屬性約簡.下面是基于模糊補互信息的約簡定義.

定義9.設B?C，B稱為C的一個 ε-約簡，如果B滿足2 個條件：

其中：條件1）保證所選屬性子集與整個屬性集在ε-誤差之內具有相同的區分能力；條件2）通過刪除選定屬性子集中的每個屬性，確保其所有屬性在 ε-誤差之內都是不可缺少的.

2.4 相關算法

基于定義6 和定義7 的2 種重要度，設計一種用于特征選擇的啟發式算法并分析其運行的復雜度.算法1 以空集為起點，首先通過內重要度計算核屬性集；然后以核屬性集為基礎，每次計算全部剩余屬性的屬性重要度，從中選擇重要度值最大的屬性加入核屬性集中，直到所有條件屬性集和約簡集的決策模糊補互信息之差小于等于ε.

算法1.KFCMI 算法.

在算法1 中，步驟②～④的循環次數為m，步驟③的循環次數為n×n，步驟⑤～?的循環次數為m，步驟?～?的循環次數為h.從而，算法1 總的循環次數為m×n×n+m+h.因此，在最壞的情況下，算法1 的時間復雜度為O(mn2).

3 實 驗

在這部分，為了驗證所提算法的可行性和有效性，將本文所提算法與基于模糊信息熵（fuzzy information entropy,FIE）[17]的算法、基于模糊粗糙集的特征選擇（fuzzy rough-based feature selection,FRFS）[33]、基于模糊區分矩陣的屬性約簡（fuzzy discernibility matrix-based attribute reduction,FDMAR）[34]、適應模糊粗糙集（fitting fuzzy rough sets,FFRS）[18]和基于區分鄰域數的特征選擇（discernible neighborhood countingbased feature selection,DNCFS）[35]進行了分類實驗的對比分析.

3.1 實驗準備

實驗使用了15 個數據集，它們是從UCI 機器學習庫①http://archive.ics.uci.edu/ml中挑選出來的.這些數據集的基本信息如表1所示.對于一些數據集中存在的缺失值，本文采用最大概率值法來填補缺失值.此外，所有的數值屬性值通過最小-最大標準化歸一化為區間[0,1].

分類回歸樹（classification and regression tree,CART）、樸素貝葉斯（naive Bayes,NB）和k-最近鄰（k-nearest neighbor,kNN）被使用來評估這些對比算法的分類效果.所有分類實驗通過10 折交叉驗證來實施，分類準確率的平均值和標準差作為最終結果.

Table 1 Basic Information of Datasets表 1 數據集的基本信息

在實驗中，KFCMI 算法中有2 個參數 σ和ε.引入參數 σ控制樣本模糊相似度，這對算法的性能有很大的影響；而參數 ε為算法的停止條件.對于給定的數據集，如果參數 ε的值變小，所選特征數不會減少.一般來說，不同的 σ和 ε會導致不同的分類準確率.因此，通過調整參數值，使 σ在0～1 之間變化，步長為0.02，且ε ∈{10-3,10-4}，為每個數據集選擇一個最優特征子集.在FFRS 算法中引入了2 個參數 ε和 λ.遵循文獻[19]的參數設置，以0.05 的步長將 ε設置為0.1～0.5 之間的值，以0.1 的步長將 λ設置為0.1～0.6 之間的值.DNCFS 算法涉及鄰域半徑參數δ,其調節范圍為[0,1]，步長為0.02.所有實驗結果都是在最高分類準確率的情況下給出的.

3.2 實驗結果

表2 給出了不同算法下所選特征的平均數.從表2 可見，KFCMI 算法大多數情況下取得了較小的特征平均數；FIE，FRFS，FDMAR 算法在一些數據集上得到的是整個屬性集，這說明FIE，FRFS，FDMAR算法在一些數據集上無法有效地去除冗余特征.此外，對于平均值而言，KFCMI 算法小于FIE，FDMAR，DNCFS 算法，但略大于FRFS 和DNCFS 算法.表3～5分別展示了原始數據和基于這6 種算法的約簡數據的分類準確率.

Table 2 Average Number of Features Selected by Different Algorithms表 2 不同算法所選特征的平均數

從表3～5 中可以看到，算法KFCMI 在所有數據集上都能提高或保持原始數據的分類準確率.在表3～5 中45 條記錄中，KFCMI 算法有29 條記錄實現了最佳分類準確率.然而，對于FIE，FRFS，FDMAR，FFRS，DNCFS 算法，分別僅有2，0，0，8，8 條記錄實現了最佳分類準確率.更多的是，KFCMI 算法的平均分類準確率在3 種分類算法上均優于其他所有特征選擇算法.

Table 3 Classification Accuracy of Different Algorithms Based on CART Algorithm表 3 基于CART 算法的不同算法分類準確率 %

續表 3

Table 4 Classification Accuracy of Different Algorithms Based on NB Algorithm表 4 基于NB 算法的不同算法分類準確率 %

Table 5 Classification Accuracy of Different Algorithms Based on kNN Algorithm表 5 基于kNN 算法的不同算法分類準確率 %

綜上，KFCMI 算法實現了較優的分類準確率.KFCMI 算法可以選出相對較小的特征子集并提高或保持分類準確率.而這15 個數據集包括數值和混合屬性數據集，因此，KFCMI 算法適用于多種屬性類型的特征選擇.

3.3 實驗參數

為了分析本文所提算法KFCMI 的性能對參數的敏感性，3 種分類算法的所選特征數及分類準確率隨參數的變化如圖1 所示.顯然，可以看到不同參數可能導致不同的特征數及分類準確率.下面從所選特征數和分類準確率2 方面來進行分析.

Fig.1 Average classification accuracy varies with parameters圖 1 平均分類準確率隨參數的變化

1）就特征數而言.通過圖1 可以看到，在大多數數據集上，隨著 σ的增加，所選特征數均呈遞增的趨勢，最后趨于平衡.例如，Arrh，Ecoli，Move 等數據集.然而，對于Autos，Credit，Heart 等數據集，所選特征數隨著 σ的增加而增加，然后減小并開始波動，最后并未趨于平穩.

2）就分類準確率而言.從圖1 可以看到大多數數據集可以在多個參數 σ值下取得最優值.對于每個數據集，可以根據圖1 選擇合適的 σ值來獲得較優的分類準確率.此外，從3 種分類算法的分類準確率變化曲線來看，可以看到3 種分類算法獲得的結果基本上一致.

通過上述分析可以看到，實驗性能對參數σ具有一定的敏感性.因此，在所提的算法中調節參數是很有必要的.但是，在合適的參數值的條件下，KFCMI算法在大多數情況下也可以獲得較優的結果.

綜上，KFCMI 算法對于數值和混合屬性分類算法的特征選擇是可行且有效的.

4 結 論

本文基于混雜核函數定義了關于決策的模糊補互信息，并證明了其關于特征呈單調性變化.進而提出了基于混雜核模糊補互信息的特征選擇方法，且設計了相應的啟發式算法.最后，在15 個實際數據集上對所提算法與現有算法進行了實驗對比分析.實驗結果表明所提算法是混合特征選擇的一種有效方案.在將來的工作中，可以進一步考慮特征的交互性.

作者貢獻聲明：袁鐘負責算法思路和實驗方案的提出，以及完成實驗并撰寫論文；陳紅梅提出指導意見并修改論文；王志紅負責論文實驗分析；李天瑞提出指導意見并修改論文.