基于信息粒度與交互信息的屬性約簡改進算法

張清華,李新太,2,趙 凡,2,高 滿,2

（1.計算智能重慶市重點實驗室（重慶郵電大學），重慶400065；2.重慶郵電大學計算機科學與技術學院，重慶400065）

1982年,波蘭學者Pawlak提出粗糙集理論[1]，該理論用于處理不精確、不一致、不完備信息和知識的有效數學工具，目前已經在故障診斷、圖像處理、海量數據處理、智能控制等研究領域得到廣泛應用[2].

屬性約簡作為粗糙集理論的一個重要研究課題，其主要思想是在滿足一定約束的前提下，通過刪除不重要或冗余的屬性，找到與原始信息系統具有相同分類能力的屬性子集，從而提高數據處理與挖掘的效率[3-4].目前，經典的屬性約簡算法主要有:基于差別矩陣的屬性約簡算法[5-6]、基于正域的屬性約簡算法[7-8]和基于信息熵的屬性約簡算法[9-10].基于差別矩陣的屬性約簡算法，主要利用差別矩陣導出區分函數，并求解區分函數的析取范式，所有析取項均是約簡結果，該方法可以找到所有約簡結果，但計算復雜度較高.基于正域的屬性約簡算法，利用分類質量衡量屬性重要度，主要保持約簡結果劃分到正域集合中的對象個數與全集一致，該方法時空復雜度較低.基于信息熵的屬性約簡算法，主要從信息觀的角度計算屬性重要度，利用啟發式搜索策略迭代選擇重要度大的屬性，直到得到的屬性集合與原信息系統的分類能力相同.

進一步地，隨著基于粗糙集理論的屬性約簡研究不斷深入，眾多學者也從多個不同的角度對此研究進行了探索.Chen 等[11]為減少待選擇屬性的迭代次數從而提升約簡算法的效率，提出一種基于屬性組的加速策略；Jia等[12]從聚類的角度，考慮了約簡過程中對象之間的屬性變化，提出一種基于相似度的屬性約簡算法；Jiang等[13]將多粒度思想引入屬性約簡算法中，提出一種加速多粒度約簡算法，以減少尋找約簡結果的時間消耗；Yang 等[14]為提升屬性約簡的穩定性，考慮多個適應度函數，提出一種屬性約簡的集成選擇器.此外，也有學者在選擇候選屬性時，考慮到條件屬性之間的相關性對分類結果和分類準確率產生的影響，姚晟等[15]引入秩相關系數度量條件屬性之間的相關性，翟俊海等[16]引入互信息來度量，提出一種最小相關性最大依賴度的屬性約簡算法.

經典粗糙集理論下，前向啟發式正域約簡算法[17]通常從空集開始構建約簡集合，每一次的迭代過程都將選擇候選屬性集合中重要度最大的屬性加入約簡集合中，然而這種策略沒有充分考慮到存在多個重要度最大的候選屬性如何合理選擇的情況，如果僅采取默認或隨機選擇的策略，可能導致約簡集合的屬性數目偏多且泛化能力較弱；同時，在剔除冗余屬性時，僅用互信息度量條件屬性之間的關聯程度，忽略了決策屬性對屬性之間相關性的影響，從而影響約簡結果與分類準確率.

針對以上問題，本文提出了一種基于信息粒度與交互信息的屬性約簡改進算法.對于選擇候選屬性過程中存在多個重要度最大的屬性時，引入信息粒度衡量每一候選屬性本身的信息量，提出一種基于信息粒度的候選屬性選擇優化策略；其次，對于互信息度量屬性之間的關聯程度存在一定不足的問題，引入信息論中交互信息的概念，在度量屬性之間的關聯程度時考慮決策屬性提供的信息，從而更好地剔除冗余屬性；然后，為了合理地設定屬性冗余閾值，從數據驅動的角度，考慮全集中兩兩不相同的條件屬性之間與決策屬性的交互信息的均值作為閾值.實驗結果表明，本文提出的約簡算法能夠獲得泛化能力較強和分類準確率較高的約簡結果.

1 基礎知識

本節簡要介紹粗糙集理論的基本概念及互信息的基礎知識.

1.1 粗糙集理論

本小節簡要介紹粗糙集理論等相關基礎知識.

定義1（決策信息系統）[17]四元組DIS=＜U,C?D,V,f＞稱為決策信息系統.其中U={x1,x2,…,xp}是由p個對象組成的非空有限集合，稱為論域；C={c1,c2,…,cn}是由n個條件屬性組成的非空有限集合；D={d}表示決策屬性集合，且C?D= ?；V=表示屬性a的值域，f:U×AT→V是一個信息函數，f(x,a)表示為對象x的屬性a賦予一個屬性值，且f(x,a)∈Va，AT=C?D.

定義2（不可分辨關系）[17]給定一個決策信息系統DIS=＜U,C?D,V,f＞，對于任意屬性子集B(B?C?D)，論域U上的一個不可分辨關系IND(B)定義為：

定義3（上下近似集）[17]給定一個決策信息系統DIS=＜U,C?D,V,f＞，B?C，X?U，在B上的不可分辨關系為IND(B)，則X關于B的上近似集、下近似集分別定義為：

其中，U/IND(B)={X|X?U∧?x,y∈X∧?b∈B∧(b(x)=b(y))}表示由不可分辨關系IND(B)在論域U上誘導的劃分.進一步，關于X的正域POSB(X)、邊界域BNDB(X)和負域NEGB(X)分別定義為：

定義4（約簡）[17]給定一個決策信息系統DIS=＜U,C?D,V,f＞，B?C，非空子集B是關于C相對于決策屬性D的一個約簡，當且僅當B滿足如下條件：

1)POSB(D)=POSC(D);

2)對于?b∈B，都有POSB-(D)≠POSC(D).

定義5（依賴度）[17]給定一個決策信息系統DIS=＜U,C?D,V,f＞，對于任意屬性集合B?C，決策屬性D依賴于條件屬性集合B的依賴度定義為γB(D)=|POSB(D)|/|U|，其中 ||?表示集合的基數.

在經典粗糙集下的前向啟發式正域約簡算法中，依賴度通常為條件屬性重要度的衡量指標.

1.2 互信息

本節簡要介紹熵與互信息等相關概念.

定義6（Shannon 熵）[18]給定一個離散隨機變量X，其值域為Vx，p(x)表示變量X取值為x的概率，x∈Vx，那么Shannon熵H(X)的定義為

定義7（條件熵）[18]給定隨機離散變量X的條件下，隨機離散變量Y的不確定性程度可用條件熵H(Y|X)度量，其定義為，其中p(x,y)表示變量X和Y的聯合概率分布.

定義8（互信息）[18]給定兩個隨機離散變量X和Y，則該兩個變量之間的相關程度可用互信息度量，其互信息I(X;Y)定義為I(X;Y)=H(Y)-H(Y|X)=H(X)-H(X|Y).

2 基于信息粒度與交互信息的屬性約簡改進算法

為了有效處理前向啟發式正域約簡算法中存在的不足，本文基于信息粒度與交互信息提出了一種新的屬性約簡算法.接下來，將詳細闡述算法的相關內容與實現框架.

2.1 基于信息粒度的候選屬性選擇優化策略

前向啟發式正域約簡算法在選擇候選屬性的過程中，忽略了存在相同依賴度大小的條件屬性，即表示存在多個依賴度最大的條件屬性，如果僅從依賴度去考察屬性的重要程度，可能并未知曉如何去選擇屬性；同時，若采用隨機選擇或默認選擇候選屬性的策略，可能得到的屬性集合數目過多且泛化能力較弱.因此，本文引入信息粒度的計算方法，進一步優化候選屬性的選擇策略.首先給出信息粒度的相關定義及其性質.

定義9（信息粒度）[19]給定一個決策信息系統DIS=＜U,C?D,V,f＞，B?C，論域U在屬性子集B上形成的等價關系劃分為U/B={X1,X2,…,Xm}，那么條件屬性B的信息粒度GK(B) 定義為決定的等價關系中元素的個數.

定義10（信息熵）[20]給定一個決策信息系統DIS=＜U,C?D,V,f＞，B?C，論域U在屬性子集B上形成的等價關系劃分為U/B={X1,X2,…,Xm}，那么條件屬性B的信息熵E(B) 定義為E(B)=

那么，優化后的前向啟發式正域約簡算法中選擇候選屬性的策略分別為：

策略1若候選屬性集合中存在唯一的依賴度較大的條件屬性，則優先選擇該屬性加入約簡集合中；

策略2若候選屬性集合存在多個依賴度較大而且相同的條件屬性，此時從候選屬性本身具有的知識量去選擇，利用信息粒度值的大小刻畫屬性知識量的多少，選擇信息粒度值較小的候選屬性加入約簡集合中.

定理1[19]給定一個決策信息系統DIS=＜U,C?D,V,f＞，B?C，論域U在屬性子集B上形成的等價關系劃分為U/B={X1,X2,…,Xm}，那么信息熵E(B)與信息粒度GK(B)具有下面的關系：

由定理1可知，某一屬性的信息粒度與其信息熵成反比，即信息粒度較小的屬性，表示其信息熵較大，則其屬性本身的混亂程度越高，從而可以提供更多有價值的信息.由此基于信息粒度的候選屬性優化策略使得選擇的屬性往往能夠朝著不確定性較低的方向發展.

2.2 基于交互信息的屬性相關性度量

在約簡算法中，部分學者[15-16]考慮約簡集合中條件屬性間的相關程度，大多以互信息指標去度量.通過考察候選屬性與已選屬性之間的相關性，根據預先設定的冗余閾值，從而判斷是否選擇保留該屬性，進而使得選擇的屬性集合相對于決策屬性的依賴度較大，而條件屬性之間的相關性較小.但如果僅以互信息度量屬性之間的相關程度，卻忽略了決策屬性的重要性，存在夸大條件屬性之間相關程度的問題，使得度量的數值并不準確.如圖1所示，條件屬性f1和f2之間的相關程度大小為a+b，但實際上，在決策屬性D下，其相關程度大小為b.

圖1 互信息與交互信息示意圖Fig.1 The schematic diagram of mutual and interaction information

為了更好地刻畫屬性之間的相關性，避免因互信息過度夸大屬性與屬性之間的相關程度帶來的問題，本文引入信息論中的交互信息作為計算條件屬性間相關程度的方法，從而達到準確去除冗余屬性的目的.下面給出條件互信息與交互信息的相關定義.

定義11（條件互信息）[18]在給定隨機變量Z的情況下，其余兩個隨機變量X和Y的相關程度可用條件互信息度量，其定義為I(X;Y|Z)=H(X|Z)+H(Y|Z)-H(X,Y|Z).

定義12（交互信息）[21]在給定隨機變量Z的情況下，與其余兩個隨機變量X和Y之間的共同相互作用可用交互信息度量，其定義為I(X;Y;Z)=I(X;Y)-I(X;Y|Z).

交互信息的數值大小可以是正數、零或負數.當為正數時，表示變量X和Y提供相同的信息量；當為零時，表示變量X和Y在變量Z的情況下是獨立的；當為負數時，表示變量X和Y提供比他們單獨提供的信息量更多.

在考慮是否刪除候選屬性時，人為預先設定屬性間統一的冗余閾值存在一定的不足，因為在不同的數據集下，其屬性間的冗余閾值是有一定差異的.因此，從數據驅動角度，給出了一種確定屬性之間冗余閾值的計算方法.

定義13（冗余閾值）給定一個決策信息系統DIS=＜U,C?D,V,f＞，其屬性間的冗余閾值θ定義為θ=其中，n表示屬性集合C的屬性總個數，ci表示屬性集合C中的第i個屬性，num表示屬性之間的計算總次數，即num=(n*(n- 1))/2.

因此，在確定是否保留候選屬性的過程中，如果此時選擇的候選屬性與約簡集合中的屬性兩兩之間交互信息的均值小于閾值θ，則將該候選屬性加入到約簡集合中，否則將其刪除.

2.3 基于信息粒度和交互信息的屬性約簡改進算法（IG2IAR）

IG2IAR 算法從空集開始構建約簡集合，首先根據定義13 確定條件屬性間的冗余閾值θ，然后根據定義5依次計算條件屬性與決策屬性之間的依賴度數值，選取依賴度最大的條件屬性加入約簡集合中；如果此時存在多個依賴度最大的條件屬性，則根據定義9計算條件屬性的信息粒度值，選取信息粒度值最小的條件屬性加入約簡集合中；加入約簡集合之前，要對擬加入的條件屬性和約簡集合中的所有條件屬性進行冗余閾值的判斷，如果擬加入的條件屬性和約簡集合中其他條件屬性的交互信息數值的平均值小于θ，則將該條件屬性加入到約簡集合中，反之，刪除該條件屬性，繼續遍歷除約簡集合以外其他的條件屬性，直至全集下劃分到正域的對象個數與約簡集合下劃分到正域的對象個數保持一致.

下面給出IG2IAR算法的詳細步驟：

算法1IG2IAR算法

輸入：決策信息系統DIS=＜U,C?D,V,f＞；

輸出：一個約簡子集R.

Step 1R= ?，R′=C-R.

Step 2對于任意的條件屬性e,f∈C，計算2 個互不相同的條件屬性與決策屬性D之間的交互信息數值I(e;f;D)，根據定義13計算出冗余閾值θ；

Step 3重復以下步驟，直到POSC(D)=POSR(D).

Step 3.1對于R′中所有的條件屬性a′∈R′，根據定義5依次計算a′相對于決策屬性D的依賴度，選出依賴度最大的條件屬性b= argmax{γ{a′?R}(D)}，仍記為a′，轉到Step 3.3；若存在多個依賴度最大的屬性，轉到Step 3.2；

Step 3.2對于R′中所有的條件屬性a′∈R′，根據定義9 依次計算a′的信息粒度，選出信息粒度最小的條件屬性c= argmin{GK({a′?R})}，仍記為a′，轉到Step 3.3；

Step 3.3對于所有已選條件屬性a∈R，利用交互信息計算其相關程度大小I(a′;a;D)；

Step 3.4如果，則R′=R′-{a′}，轉到Step 3；否則R=R?{a′}，R′=R′-{a′}，轉到Step 3；

Step 4返回約簡R.

3 實驗分析

3.1 數據集和實驗設計

為了驗證提出方法的有效性，本文在10 個高維微陣列基因表達數據集[22-23]上進行了實驗.基本信息由表1所示，數據集可從http://featureselection.asu.edu/datasets.php和http://csse.szu.edu.cn/staff/zhuzx/Data‐sets.html下載得到.

所有實驗均在Matlab 2014b 實驗平臺完成，環境為PC 機，Intel(R)Core(TM)i7-7700 CPU@3.60GHz&8.0 GΒ RAM，采用SVM、KNN以及隨機森林(Random Forests，RF)算法求分類準確率，設置KNN參數K為1，隨機森林的樹個數為10.實驗采用十折交叉驗證的方法進行分類，通過訓練數據集進行模型訓練，在測試數據集上獲得分類準確率.因為本文所提方法僅處理離散型數據，所以利用公式a′(x)=將條件屬性的連續型數值轉化為離散值，其中，a表示低于特征a屬性值的最大整數值，a(x)、mina和σa分別表示在屬性a下的真實值、最小值和標準偏差值.

3.2 屬性降維的參數確定

針對10 個高維基因數據集，為有效降低模型訓練與分類的時間成本，采用Fisher Score[24]先對基因屬性采取初步降維的策略.選擇Fisher Score作為此度量方法的主要原因是計算量少，精度高，能有效降低計算的復雜度.通過計算每個基因屬性的Fisher Score 值，根據需求將n個基因屬性選擇出來組成一個屬性子集.算法2如下.

算法2基于Fisher Score的屬性選擇算法

輸入：一個具有p個對象和n個基因屬性的決策信息系統DIS=＜U,C?D,V,f＞；選擇的期望屬性數fnum；

輸出：屬性子集S.

Step 1獲取所有基因屬性的Fisher Score值；

Step 2根據每個基因屬性的Fisher Score值利用排序算法對基因屬性進行降序排序；

Step 3選擇前fnum個Fisher Score值較大的基因特征，將該基因特征放入集合T中；

Step 4通過集合T獲得降維后的基因屬性子集S；

Step 5返回選擇的基因屬性子集S.

為了合理設置所有基因表達數據集的降維個數，采用算法2 在7 個特征維度（10，50，100，150，200，250，300）上利用10 折交叉驗證在SVM 分類器上獲得相應的平均分類準確率.圖2 展示了10 個微陣列基因表達數據集在不同維度的基因屬性子集下SVM 分類器準確率的變化趨勢.由圖2 可知，隨著基因屬性子集大小的變化，準確率在多數情況下也有所變化，但同時多數數據集在選擇150維度的基因屬性子集的情況下可以獲得較高的分類準確率.因此，將所有數據集的fnum統一設置為150維.

圖2 在10個數據集上基因特征維度變化的分類準確率的變化趨勢圖Fig.2 The classification accuracy via the size of gene subset on 10 gene data sets

3.3 基于信息粒度的候選屬性選擇優化策略的有效性驗證

為了驗證基于信息粒度的候選屬性選擇優化策略（GK_opt）的有效性，本文與傳統的前向啟發式搜索正域約簡算法[17]（Pos_For）進行了實驗對比.在10 個微陣列基因表達數據集上利用KNN 分類器，并以10折交叉驗證的平均分類準確率和屬性子集的平均長度來評價所選屬性的質量，同時采用Wilcoxon符號秩檢驗[25]測試分析兩種算法之間的差異性，實驗結果由表2所示.

表2 Pos_For 與GK_opt之間的結果對比Tab.2 Comparison results between Pos_For and GK_opt

從表2 可以看出，在分類準確率上，在大部分基因數據集上均獲得了較高的分類準確率，同時在AL‐LAML、SMK_CAN_187、Prostate_GE 和MLL 基因數據集上，雖然與Pos_For 算法選擇的屬性子集長度相同，但分類準確率明顯優于Pos_For 算法，這表明基于信息粒度的候選屬性選擇優化策略，在存在多個依賴度最大的屬性情況下，其屬性結果的泛化能力更好.此外，在選擇的屬性子集長度上，TOX_171、lung、GLI_85 和CLL_SUΒ_111 基因數據集明顯優于Pos_For 算法.與Pos_For 算法相比，基于信息粒度的候選屬性選擇優化策略的約簡算法，平均準確率提升了3.07%，平均選擇的特征長度降低了1.06%.進一步地，利用Wilcoxon 符號秩檢驗測試分析平均分類準確率的差異性，p 值為0.020 9，表明在0.05 顯著性水平下，傳統的前向啟發式搜索正域約簡算法與基于信息粒度的候選屬性選擇優化策略的約簡算法存在顯著性差異.因此，基于信息粒度的候選屬性選擇優化策略不僅可以使得選擇的屬性子集數目更少，而且屬性子集的泛化能力更好，分類準確率也有一定的提升.

3.4 IG2IAR約簡算法與傳統的約簡算法對比

為了驗證IG2IAR 算法比其余傳統的約簡算法的優越性，本文在10 個高維基因數據集上采用十倍交叉驗證方法從SVM、KNN 與隨機森林分類器的平均分類準確率與選擇的屬性子集平均長度方面來對比其余約簡算法.算法主要包括傳統的前向啟發式搜索正域約簡算法（Pos_For）、最小相關性最大依賴度屬性約簡算法[16]（MS）以及最小相關性最大依賴度屬性約簡的改進算法[26]（MM），MS 約簡算法屬性之間的冗余閾值為0.65，與文獻[16]相同.在SVM、KNN 和隨機森林分類器下，4 個約簡算法所選屬性子集的平均分類準確率與約簡子集的平均屬性長度在表3和表4展示.

由表3 和表4 可以看出，IG2IAR 算法的分類準確率在大部分基因數據集上明顯優于其他方法，而且IG2IAR算法的平均分類準確率在這三個分類器上均達到最高，同時在SVM、KNN 及隨機森林分類器上，IG2IAR 算法在平均準確率上分別比其他方法高4.08%～4.46%，1%～3.84%和2.67%～4.09%.由表7可以看出，在TOX_171 和lung 數據集上，IG2IAR 算法明顯優于其余三種方法，但在ALLMAL、GLI_85、Cen‐tral_Nervous_System和Ovarian_Cancer數據集上，Pos_For算法和MS算法選擇的屬性子集個數更少.盡管IG2IAR算法、Pos_For算法和MS算法在SMK_CAN_187、CLL_SUΒ_111、Prostate_GE和MLL數據集上選擇相同數目的屬性子集，除了KNN分類器上的MLL數據集與隨機森林分類器下的CLL_SUΒ_111數據集以外，IG2IAR 算法均可在所有分類器上獲得較高的分類準確率，由此可知IG2IAR 算法選擇的屬性子集，具有更好地泛化能力，可以獲得較高的分類準確率.此外，本文提出的方法，所選屬性子集的平均長度均值參數僅比Pos_For 算法與MS 算法小0.04，差異性較小.因此，本文提出的方法選擇的屬性子集長度較短，而且泛化能力更好，分類準確率也有一定的提升.

表3 SVM和KNN分類器下分類準確率的對比結果Tab.3 The comparison of classification accuracy on SVM and KNN classifier

表4 隨機森林分類器下分類準確率與選擇的屬性子集平均長度的對比Tab.4 The comparison of classification accuracy on Random Forests classifier and the average length of selected subsets

3.5 統計分析

為了系統地探討所有對比算法在分類準確率方面的統計性能，將采用Friedman測試[25]和Wilcoxon符號秩檢驗測試進行統計分析.

由表5 可知，IG2IAR 算法的平均排名優于其余三種方法.進一步地，當顯著性水平為0.1 時，SVM、KNN 和隨機森林分類器上的p-value 均小于0.1，即表示在顯著性水平為0.1 下，所有算法在SVM、KNN與隨機森林分類器下的分類準確率存在顯著性差異.同時，利用Wilcoxon符號秩檢驗測試對比IG2IAR算法與其余算法兩兩之間的顯著性差異，當顯著性水平為0.1 時，在SVM 與隨機森林分類器下，IG2IAR 算法的性能明顯優于其余三種約簡方法，但在KNN 分類器下，IG2IAR 算法與MM 算法之間沒有顯著性差異.總之，本文提出的算法總體上優于其他三種算法.

表5 所有算法在三種分類器上的Friedman測試與Wilcoxon秩和檢驗測試結果Tab.5 The Friedman test and Wilcoxon sign rank sum test results of all algorithms on the three classifiers

4 結論

基于前向啟發式正域約簡算法無法合理選擇存在多個重要度最大的條件屬性，同時在考慮約簡集合中條件屬性之間的相關性時，忽略了決策屬性對條件屬性之間相關性的影響程度，因此，本文提出了一種基于信息粒度的候選屬性優化策略，并引入信息論中交互信息的概念度量條件屬性之間的相關程度以進一步剔除冗余屬性，從而保證約簡集合的泛化能力，進而提出一種基于信息粒度與交互信息的屬性約簡改進算法.實驗結果表明，本文提出的算法有較好的屬性約簡結果和分類準確率.