最大化獨立有效分類信息率的屬性選擇

柳 葉，代建華+，陳姣龍

1.湖南師范大學 智能計算與語言信息處理湖南省重點實驗室，長沙410081

2.湖南師范大學 信息科學與工程學院，長沙410081

隨著科學技術的迅猛發展，人們面對的數據集往往是復雜且龐大的。在高維數據中存在著大量的冗余屬性，這給數據分析、機器學習帶來諸多干擾信息，從而導致學習效率低、分類效果差和計算量大等不利影響。因此，屬性約簡具有重要的應用價值。

粗糙集理論是波蘭學者Pawlak提出的一種研究信息系統的不確定性和不完備性的有力工具[1]。該理論已經被廣泛地應用于不確定性度量、規則提取和屬性約簡等方面[2]。在粗糙集理論模型中，現有的屬性選擇方法大致可以分為三類：（1）基于上、下近似算子的屬性選擇方法[3-7]；（2）基于差別矩陣的屬性選擇方法[8-9]；（3）基于熵理論的屬性選擇方法[10-21]。

在熵理論中，互信息作為一種度量數據相關性的有力工具，被廣泛地應用于屬性選擇之中。目前基于互信息的屬性選擇方法可大致地分為兩種策略：一是最大化待選屬性所能提供的分類信息；二是最小化待選屬性所帶來的冗余信息。然而，最大化待選屬性所提供的分類信息并不意味著冗余信息就一定少，反之亦然。實際上，在現有的屬性選擇方法中，不難發現與決策密切相關的屬性之間存在著冗余的情況并不少見。同樣地，在最小化冗余信息的同時，可能一些方法更傾向于選擇與決策相關性較低的低冗余屬性。現有的方法很難有效地衡量屬性所提供的分類信息和冗余信息，而且很少有方法考慮到新增待選屬性對已選屬性所保留的分類信息的影響。

因此，本文首先通過互信息定義了有效分類信息率，并提出了基于有效分類信息率的屬性選擇策略（attribute selection based on effective classification information ratio，ASECIR）。其次考慮到新增待選屬性對已選屬性所保留的分類信息的影響，進一步構造了獨立有效分類信息率的概念，并提出了基于獨立有效分類信息率的屬性選擇策略（attribute selection based on independent-and-effective classification information ratio，ASIECIR）。最后通過實驗驗證了本文工作的有效性。

本文的主要貢獻如下：

（1）提出了基于有效分類信息率和基于獨立有效分類信息率的兩種屬性選擇方法；

（2）提出了有效分類信息率的概念，有效分類信息率能有效地評估待選屬性所能提供的分類信息，一定程度上也對自身與類之間的冗余信息進行了評估；

（3）提出了獨立有效分類信息率的概念，有機地將待選屬性所提供的新增有效分類信息和已選屬性保留的有效分類信息與冗余信息相結合，對待選屬性的重要性評價更加合理。

1 相關工作

定義1（決策信息表DIS）[22]給定一個四元組＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維的樣本集合；C={c1,c2,…,cm}為m維的條件屬性集合，D表示決策屬性；表示屬性的值的集合，Vb是一個給定的屬性b的值域；f是一個映射函數，U×C∪D→V滿足：?b∈C∪D,xi∈U，有f(xi,b)=Vb。稱該四元組為一個決策信息系統，簡稱DIS（decision information system）。

互信息是熵理論中十分重要的信息度量結構，可以有效地描述兩個變量之間的關聯。互信息可以定義如下形式：

其中，H(P)和H(P|Q)分別表示相關變量的信息熵和條件熵。當公式中的變量P、Q分別表示決策屬性和條件屬性時，I(P;Q)則表示條件屬性Q包含決策屬性P的分類信息質量，即共享的有效分類信息量。另外，當P、Q都表示兩個任意的條件屬性時，I(P;Q)則表示條件屬性P、Q所共有的信息量，即冗余信息量。

基于互信息的特點，學者們將互信息廣泛地應用于屬性選擇中，用來評價屬性之間的相關性程度。文獻[10]提出了基于聯合互信息的屬性選擇方法（joint mutual information，JMI）：

文獻[11]提出了一種基于對稱相關性的雙輸入對稱相關屬性選擇方法（double input symmetrical relevance，DISR）。文獻[12]利用聯合互信息提出了規范化最大聯合互信息屬性選擇（normalized joint mutual information maximization，NJMIM）：

為了提高待選屬性在自身信息量中的比重，文獻[13]利用互信息提出了一種信息增益率的啟發式屬性選擇算法（GainRatio）：

文獻[14]設計了一種基于互信息的屬性貪心選擇算法（mutual information feature selection，MIFS）。文獻[15]通過加權的方式評估待選屬性與決策標簽之間的互信息，提出了改進的屬性選擇方法（mutual information feature selector under uniform information distribution，MIFSU）。文獻[16]提出了最小冗余最大相關屬性選擇方法（maximum relevancy minimum redundancy，mRMR）。文獻[18]引入平均歸一化互信息作為屬性間冗余信息的度量方法，提出了一種歸一化互信息屬性選擇方法（normalized mutual information feature selection，NMIFS）：

上述MIFS、MIFSU、mRMR 和NMIFS 的共同特點是，都考慮到了待選屬性與已選屬性之間的冗余信息，但忽視了對待選屬性和已選屬性與決策標簽之間的類相關信息的考察，即多元互信息。

I(D;ci;cj)=I(D;ci)+I(D;cj)-I(D;ci,cj) （10）

公式描述了兩個屬性與決策類之間的關聯，當某個屬性cj被選中時，此時I(D;ci;cj)可以表示為已選屬性cj關于決策屬性提供的有利于分類的信息。而對待選屬性ci而言，I(D;ci;cj)則表示待選屬性ci所提供的聯合分類信息對決策D來說是冗余的信息量，也稱之為類相關冗余信息。

文獻[17]利用多元互信息引入類相關冗余的概念，并構造了一種條件信息屬性選擇算法（conditional informative feature extraction，CIFE）。文獻[19]提出了一種最大相關和最大獨立的屬性選擇方法（maxrelevance and max-independence，MRI）：

現有的方法對于屬性的相關性和冗余性分析存在著一定的局限性。MIFS、mRMR、MIFSU、NMIFS只關注屬性間的冗余，而忽視了待選屬性和已選屬性與決策類之間的類相關信息。另外，CIFE、GainRatio和NJMIM 在評價待選屬性的重要性時，忽視了已選屬性對決策類的貢獻度。換句話說，只著重考慮待選屬性所提供的新增分類信息，而忽視了增加待選屬性后對已選屬性所保留的有效分類信息的影響。

從上述分析來看，該如何分析待選屬性所提供的分類信息和冗余信息，以及新增待選屬性對已選屬性所保留的分類信息的影響是基于互信息的屬性選擇方法重點關注的問題。

2 基于互信息的獨立有效分類信息率

本章將引入有效分類信息率和獨立有效分類信息率的概念。

定義2（有效分類信息率）給定一決策信息系統DIS=＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維樣本集合；C={c1,c2,…,cm}為m維條件屬性集合，D表示決策屬性。已知S為已選屬性集(S≠?)，且S?C。假設ci∈C-S為待選屬性，則待選屬性ci關于決策D所提供的有效分類信息率（effective classification information ratio，ECIR）可定義如下：

ECIR主要關注的核心問題是待選屬性能提供多少新增的分類信息。待選屬性ci新增的分類信息(I(D;S∪{ci})-I(D;S))在它與決策類D所共有的互信息中的占比越大，說明該屬性所提供的新增有效分類信息越多，且與已選屬性所共有的類相關信息相對較低。ECIR從理論上有效地將待選屬性提供的分類信息和類相關冗余信息統一，有利于尋找較高分類信息和較低類相關冗余的屬性。

為了便于理解，通過一個圖來進一步說明上述定義，如圖1所示。圖1描述的是候選屬性和已選屬性關于決策類之間的關系的Venn 圖，其中黑色陰影部分表示待選屬性提供的新增有效分類信息，紅點部分表示待選屬性和已選屬性的類相關冗余信息。假設ck、ck+1表示兩個待選屬性，S代表已選屬性子集。屬性ck的黑色陰影部分面積表示待選屬性ck關于決策類所提供的新增有效分類信息(I(D;S∪{ck})-I(D;S))，紅色陰影部分表示ck和屬性子集B關于決策類的類相關冗余信息(即多元互信息，I(D;S;ck))。另外，屬性ck+1與決策類間不存在類相關冗余信息，即有I(D;S;ck+1)=0 且I(D;S∪{ck+1})-I(D;S)=I(D;ck+1)。

圖1 Venn圖（待選特征和已選特征關于決策類的聯系）Fig.1 Venn diagram(relationship between candidate and selected attributes about decision-class)

假設I(D;S∪{ck})-I(D;S)=I(D;ck+1)，即在圖1中屬性ck、ck+1的黑色陰影部分的面積是相等的。換句話說，屬性ck、ck+1可提供的有效分類信息量是等同的。在這種情況下，現有的屬性選擇機制很難做出合理的判斷。例如MIFS、MIFSU、mRMR和NMIFS在過度強調屬性間的冗余信息時，權重的取值會影響到評價指標傾向于選擇哪個屬性。當權重越大時，評價指標更傾向于選擇屬性ck+1，反之，則傾向于選擇屬性ck。再比如屬性選擇指標CIFE，當已選擇的屬性只有一個時，CIFE評估屬性ck、ck+1的重要性是等同的，此時CIFE會根據序號優先級，直接選擇ck。

然而，定義的ECIR 卻能緩解這種現象的發生。根據定義2，可分別計算出待選屬性ck、ck+1的有效分類信息率：ECIR(ck+1;S;D)＞ECIR(ck;S;D)，說明待選屬性ck+1提供的有效分類信息率大于待選屬性ck。

考慮到ECIR 只關注待選屬性所提供的有效分類信息，而忽視了加入待選屬性后對已選屬性所保留的分類信息的影響，因此，本文進一步提出了獨立有效分類信息率的概念。

定義3（獨立有效分類信息率）給定一決策信息系統DIS=＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維的樣本集合；C={c1,c2,…,cm}為m維的條件屬性集合，D表示決策屬性。已知S為已選屬性集(S≠?)，且S?C。假設ci∈C-S為待選屬性，則獨立有效分類信息率（independent-and-effective classification information ratio，IECIR）可定義如下：

IECIR 有效地將待選屬性所提供的分類信息和冗余信息以及新增待選屬性對已選屬性所保留的分類信息之間的關聯進行了統一。IECIR 有助于增強屬性的有效分類信息和冗余信息的取舍。通過最大化待選屬性和已選屬性的有效分類信息率，在一定程度上也降低了屬性的冗余性，進一步提高了屬性子集的整體識別能力。

3 屬性選擇方法

在前文，本文分析了現有方法所存在的問題，即無法權衡待選屬性所提供的分類信息和冗余信息，以及新增待選屬性時對已選屬性所保留的分類信息的影響。針對這些問題，本文提出了有效分類信息率ECIR和獨立有效分類信息率IECIR的概念。本章依據上述定義的ECIR 和IECIR，提出了兩種屬性選擇方法。

3.1 基于有效分類信息率的屬性選擇方法

定義4（特征重要性評估函數1）給定一決策信息系統DIS=＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維的樣本集合；C={c1,c2,…,cm}為m維的條件屬性集合，D表示決策屬性。假設已知S為已選屬性子集，ci為待選屬性且ci∈C-S。在基于有效分類信息率的屬性選擇方法下，待選屬性ci的重要性的計算如下所示：

本文通過式（15）來計算候選屬性的重要性，Sig1(ci;S;D)值越大說明該候選屬性越重要。

根據定義4，本文設計了一個啟發式屬性選擇算法，具體的實現步驟在算法1中給出。

算法1基于有效分類信息率的屬性選擇算法

輸入：一個決策信息系統DIS=＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維的樣本集合，C={c1,c2,…,cm}為m維的條件屬性集合，D表示決策屬性。

輸出：S為已選屬性子集。

首先，計算等價類的時間復雜度為O(|U|2|C|)。因此，計算互信息等熵度量的時間復雜度為O(|U|2|C|+|U|2)。進而，屬性選擇算法的時間復雜度為O(|S||C|(|U|2|C|+|U|2))。

3.2 基于獨立有效分類信息率的屬性選擇方法

考慮到ASECIR 只關注待選屬性所提供的新增的有效分類信息，而忽視了加入待選屬性后對已選屬性所保留的分類信息的影響，本文進一步提出基于獨立有效分類信息率的屬性選擇方法。

定義5（特征重要性評估函數2）給定一個決策信息系統DIS=＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維的樣本集合；C={c1,c2,…,cm}為m維的條件屬性集合，D表示決策屬性。假設已知S為已選屬性子集，ci為待選屬性且ci∈C-S。在基于獨立有效分類信息率的屬性選擇方法下，待選屬性ci的重要性定義如下所示：

若S=?，Sig2(ci;S;D)=I(D;ci)/H(D)。

通過式（16）來計算候選屬性的重要性，Sig2(ci;S;D)值越大說明該候選屬性越重要。

根據定義5，本文設計了一個啟發式屬性選擇算法，具體的實現步驟在算法2中給出。

算法2基于獨立有效分類信息率的屬性選擇算法

輸入：一個決策信息系統DIS=＜U,C∪D,V,f＞，其中U={x1,x2,…,xn}為n維的樣本集合，C={c1,c2,…,cm}為m維的條件屬性集合，D表示決策屬性。

輸出：S為已選屬性子集。

首先，計算等價類的時間復雜度為O(|U|2|C|)。因此，計算互信息等熵度量的時間復雜度為O(|U|2|C|+|U|2) 。進而，屬性選擇算法的時間復雜度為O(|S||C|(|U|2|C|+|U|2))。與屬性選擇算法GainRatio的時間復雜度較為相近，但總體要低于mRMR、MIFS、CIFE、MRI 等具有代表性的屬性選擇算法的時間復雜度，其原因在于mRMR、MIFS 等方法的屬性重要性計算中需要重復計算已選屬性的互信息。

4 實驗與結果

本章將通過與現有的方法進行對比實驗，進一步說明本文提出的兩種屬性選擇方法（ASECIR 和ASIECIR）的合理性。

4.1 實驗準備

為了綜合地對比ASECIR和ASIECIR的有效性，本文選取8種具有代表性的基于互信息的屬性特征選擇算法進行實驗比較，包括DISR[11]、NJMIM[12]、GainRatio[13]、MIFS[14]、mRMR[16]、NMIFS[18]、CIFE[17]、MRI[19]。用 于本文的實驗基準數據均來自UCI數據庫，數據集的詳細信息展示在表1 中。考慮到部分實驗數據是實值型數據，因此采用離散化技術對實值數據進行離散化處理。

表1 基準數據的描述Table 1 Description of benchmark dataset

為了公平地判斷所選屬性子集的分類精度，本文使用了KNN分類器(K=3)、C4.5分類器以及SVM分類器對所選的屬性子集進行10次10折交叉驗證，并取10次結果的平均值作為算法分類精度的評估值。

本文所有的實驗都是在相同的軟硬件環境下進行的。軟硬件環境：Windows 7系統、Intel?CoreTMi5-5200U CPU@2.20 GHz處理器、8.00 GB內存、MATLAB2019a、WEKA 3.8。

4.2 實驗和結果

表2～表4 分別展示了在KNN(K=3)、C4.5 以及SVM 分類器下分類精度的實驗結果，每一行中的最優分類精度值用粗體以及下劃線突出顯示，最后兩行代表每個算法在所有基準數據下的平均分類精度（Avg.Acc）和平均序值（Avg.Rank）。

在表2 中，ASIECIR 和ASECIR 在所有方法中取得了最好和次優的平均分類精度，分別達到了83.36%和82.66%，且ASIECIR 的平均序值低于其他方法。在表3 中，ASIECIR 和ASECIR 在所有數據集上獲得了最好和次優的次數最多，且兩種方法的平均分類精度值（82.13%、81.78%）高于其他方法，ASIECIR 的平均序值也優于其他方法。此外，在所有對比方法中，除MRI 之外的其他對比方法的平均分類精度均低于80.00%。在表4 中，ASIECIR 和ASECIR 在所有方法中取得了最好和次優的平均分類精度，分別達到了81.38%和81.01%，且ASIECIR的平均序值低于其他方法。此外，在所有對比方法中，MRI 和DISR 方法的總體表現優于其他6 種對比方法。

表2 在KNN分類器上不同方法的分類精度Table 2 Classification accuracy with different methods by KNN classifier

表3 在C4.5分類器上不同方法的分類精度Table 3 Classification accuracy with different methods by C4.5 classifier

表4 在SVM分類器上不同方法的分類精度Table 4 Classification accuracy with different methods by SVM classifier

從上述結果總結如下：（1）ASECIR 和ASIECIR的平均分類精度高于其他對比算法，且ASECIR低于ASIECIR。此外，在對比方法中，MRI 的總體性能雖然低于本文所提出的兩種屬性選擇算法，但優于其他對比方法。由此可以發現，本文設計的獨立分類信息率能夠有效地提高特征選擇的性能；（2）ASIECIR的平均序值低于其他方法，且ASECIR和ASIECIR在所有方法中是獲得最優結果最多的兩種方法，其中ASIECIR 的表現更好。總體取得了較為理想的分類性能。

綜合上述分析，可以發現在對特征的相關性和冗余性的分析研究上，本文所設計的有效分類信息率和獨立有效分類信息率對待選屬性的重要性評估總體上表現得更為出色，也從實驗上進行驗證所提出的理論模型的合理性。

為了進一步分析所提出的屬性選擇方法與其他方法之間分類性能效果上的差異性，本文利用在三種分類器上得到的分類結果進行Bonferroni-Dunn后續檢驗測試。Bonferroni-Dunn 測試方法是通過比較對比方法與一個核心方法的平均序值差值和臨界差值的大小來分析對比方法與核心方法之間的關聯。在該實驗中，以ASIECIR為核心方法和對比的8種方法進行Bonferroni-Dunn后續檢驗。臨界差值（critical difference，CD）的計算如下公式所示：

其中，K表示實驗方法的個數（K=9），N為實驗數據集的個數（N=13）。pα表示在顯著性水平為α下的臨界值。在本文中，首先令顯著性水平α=0.05，通過文獻[23]可知pα=2.724，故CDα=2.926。若某個方法的平均序值與ASIECIR的平均序值的差值越大，則說明ASIECIR 的效果顯著優于該方法的程度越大。特別地，若該方法的平均序值與ASIECIR 的差值超過CD值，則說明ASIECIR的性能效果顯著優于該方法。

Bonferroni-Dunn 檢驗的相關實驗結果展示于圖2中，其中圖（a）～（c）分別表示在KNN、C4.5以及SVM分類器上的Bonferroni-Dunn檢驗結果。從圖2（a）中可以發現ASIECIR 方法的性能顯著優于CIFE。除CIFE以外的其他對比方法雖然都與ASIECIR在一個CD 值范圍內，但距離最近的對比方法NJMIM 和MRI 仍與ASIECIR 存在著較大的差異，差值至少超過1.5。由此進一步說明ASIECIR 的性能優于其他對比方法的程度很大。在圖2（b）中，ASIECIR 的性能優于對比方法MIFS、CIFE 和NMIFS。同時，距離最近的對比方法GainRatio 與ASIECIR 方法的平均序值的差值至少超過1.5。在圖2（c）中，ASIECIR 方法在SVM 分類器上的性能顯著優于對比方法NJMIM和MIFS。其中，距離ASIECIR方法最近的對比方法NMIFS和MRI方法的平均序值仍與ASIECIR方法有著較為明顯的差距。

圖2 Bonferroni-Dunn檢驗Fig.2 Bonferroni-Dunn test

綜合上述結果分析可以發現，本文所提出的ASIECIR 與現有的一些屬性選擇方法之間存在著一定的性能差異，且ASIECIR 表現總體更優。由此說明，本文所設計的獨立分類有效信息率的屬性重要性評估函數在一定程度上具備很好的區分屬性相關性和冗余性的能力，可以作為一種可行的屬性重要性評估策略用于屬性選擇的研究中。

5 結束語

本文提出了基于有效分類信息率的屬性選擇方法，可以有效地選擇能提供大量有效分類信息同時攜帶較少冗余信息的待選屬性。考慮到新增的待選屬性對已選屬性所保留的分類信息的影響，進一步提出了基于獨立有效分類信息率的屬性選擇方法。實驗結果表明，所提出的屬性選擇方法在選擇重要屬性的機制、分類精度上都明顯地優于許多現有的屬性選擇方法。在未來的工作中，將進一步深入探討更復雜情況下（例如，動態的決策信息系統和存在決策部分缺失的數據）的屬性相關性和冗余性的關聯，并設計出有效的屬性選擇方法。