基于互信息的分類屬性數據特征選擇算法

顧文強，李志華

1.江南大學物聯網工程學院輕工過程先進控制教育部重點實驗室，江蘇無錫 214122

2.物聯網應用技術教育部工程研究中心，江蘇無錫 214122

基于互信息的分類屬性數據特征選擇算法

顧文強1，李志華2

1.江南大學物聯網工程學院輕工過程先進控制教育部重點實驗室，江蘇無錫 214122

2.物聯網應用技術教育部工程研究中心，江蘇無錫 214122

提出了一種針對分類屬性數據特征選擇的新算法。通過給出一種能夠直接評價分類屬性數據特征選擇的評價函數新定義，重新構造能實現分類屬性數據信息量、條件互信息、特征之間依賴度定義的計算公式，并在此基礎上，提出了一種基于互信息較大相關、較小冗余的特征選擇（MRLR）算法。MRLR算法在特征選擇時不僅考慮了特征與類標簽之間的相關性，而且還考慮了特征之間的冗余性。大量的仿真實驗表明，MRLR算法在針對分類屬性數據的特征選擇時，能獲得冗余度小且更具代表性的特征子集，具有較好的高效性和穩定性。

分類屬性數據；特征選擇；互信息

1 引言

所謂特征選擇，即從已知一組數據樣本集中按照某種準則選取出一組最有效的特征以達到降低特征空間維數的目的[1]。特征選擇是復雜數據樣本降維處理的主要手段之一，已有多種特征選擇算法見諸各種文獻，如文獻[2]的基于信息論的特征選擇算法、文獻[3]的基于關聯規則的特征選擇算法、文獻[4]的基于決策樹的特征選擇算法和文獻[5-6]的基于粗糙集的特征選擇算法等。其中尤以基于信息論的特征選擇算法最受關注，Fano在文獻[7]中證明了通過優化變換數據和類標簽之間的互信息最大化，可以得到所選特征與原樣本集之間較小的誤差概率；文獻[8]Battiti在此基礎上提出了基于互信息的特征選擇算法（M IFS），該算法采用貪婪選擇算法選擇滿足評價函數的候選特征作為有效特征；Kwak和Choi在文獻[9]中對M IFS算法中可能導致評價函數失去平衡的情況進行了研究，提出了改進的M IFS-U算法。但這些算法或多或少也存在一些不足，如文獻[7]沒有考慮特征間的關聯關系，導致了選取的特征之間冗余性過大；文獻[8-9]用于特征選擇時沒有考慮到候選特征加入特征子集后與類別標簽的互信息、對分類結果可能產生的影響，并且這些算法中有關互信息的估算方法無法直接處理連續屬性數據。

分類屬性數據（Nominal Data）廣泛存在于各種應用領域，由于其數據分布的無序性、不可度量性，不同類別數據的特征甚至互相交錯[10]，導致大多數特征選擇算法不適用于這類數據的特征提取。針對以上缺點，本文以分類屬性數據的特征選擇為目的，考慮到分類屬性數據的特殊性，重新構造了適用于分類屬性數據計算的特征信息量、特征之間依賴度、條件互信息三個基本概念的計算公式，同時給出了基于互信息的分類屬性數據特征選擇評價函數的新定義，這些創新不僅考慮了特征與類別之間的關系，同時也考慮了特征間的相互關系，較好地解決了分類屬性數據特征之間互信息的估算問題。在此基礎上，提出了基于互信息的較大相關較小冗余的特征選擇（M ore Relevance Less Redundancy，MRLR）算法。MRLR算法在分類屬性樣本集上進行了仿真實驗，實驗結果表明算法針對分類屬性數據的特征選擇有效，并且不論在特征選擇的高效性和用于分類性能評價方面都具有良好的表現。

2 互信息簡介

互信息（M utual Information，M I）是信息論中的一個基本概念，其本質是表示兩個變量間共同擁有信息的含量，能夠用來評估任意變量之間的相互依賴關系[11]。

給定兩個離散變量X和Y，若它們的邊緣概率分布分別為p(x)和p(y)，則它們之間的互信息I(X;Y)定義為：

其中，p(x)和p(y)是x，y的邊緣概率分布，p(x，y)是聯合概率分布。

通常互信息用信息熵計算成如式（2）所示。

其中，

其中，H(X)表示變量X的信息熵；H(X|Y)表示X關于Y的條件熵。

由上式可知，當變量X和Y完全無關或相關獨立時，它們的互信息為0，達到最小，說明二者不存在任何依賴關系；反之，當他們相互依賴程度越高時，互信息I(X;Y)的值也就越大。

3 基于互信息的分類屬性數據特征選擇算法

分類屬性數據的值往往具有特定的含義，并且這些數據的分布與空間距離無關、數據冗余性大[10]。同時分類屬性數據樣本集中不同類別之間的差別很微弱，因為大部分樣本的特征值重復、甚至重疊，要對其進行分類度量比較困難[5]。針對分類屬性數據特征選擇的特殊性，本文展開以下研究。

3.1 相關定義

為了有效地實現分類屬性數據的特征選擇，首先給出以下新定義或定義[12]的新計算。

定義1假設樣本集中的第i維特征fi有n個不同的值a1，a2，…，an，則特征fi的信息量為：

定義2兩個不同的特征fi和fj之間的條件互信息：

其中，E(fi;fj)表示在特征fj確定的情況下，特征fi依賴于fj程度的強弱程度。m表示fj有m個不同的取值。

定義3根據以上定義，兩個特征fi和fj的依賴度定義如下：

得出兩個特征之間的依賴度滿足對稱性。其中，I(fi)按式（5）計算，E(fj;fi)按式（6）計算。

定義4分類屬性數據特征選擇對特征fi的評價函數如下：

其中，G(S∪fi;C)表示將候選特征fi加入特征子集S后與類別標簽C的依賴度；同時為了克服M IFS算法與M IFS-U算法中評價函數的懲罰因子β的難以確定的局限。本文將β用1|S|代替，其中|S|為特征子集特征個數（或一階范數）。

3.2 算法的基本思想

鑒于分類屬性數據的特殊性，算法應該選擇那些與類標簽屬性具有最大互信息的特征，同時算法也應該考慮不同特征之間的互信息，避免出現過大的特征冗余，從而最大程度地降低其他特征的不確定性。該特征選擇算法首先選擇與類標簽相關度最大的特征，接著將候選特征與已選特征、類標簽分別進行依賴度計算，選取與類標簽具有較大相關度、同時與已選特征具有較小冗余度的特征，經過多次迭代直到得到滿足條件的特征子集。

3.3 MRLR算法

MRLR算法首先設定一個空的特征子集S、包含所有特征的候選特征集合F，然后，求出候選特征集合中每個特征與類標簽的互信息，進一步求出特征間的依賴度，選擇依賴度最大值的特征加入特征集合S；最后，在每一輪循環中，應用式（8）的特征選擇評價函數選擇其計算結果最大值對應的特征加入特征子集S，直到S中的特征維數滿足要求。MRLR算法描述如下：

步驟1（初始化）將F設為包含所有特征的全集，S設為空集，初始化k的值，k表示特征選擇算法要選擇的特征子集的維數。

步驟2根據公式（7）計算依賴度，對F中的每一個特征fi∈F，計算G(fi;C)。

步驟3選取第一個有效特征：根據步驟2的計算結果，選擇其中最大的依賴度值G(fi;C)，并且設置F←F-{f}，S←{f}。

步驟4在剩余的候選特征中，依次選擇特征fi，根據式(8)計算候選特征的評價值，選擇最大值對應的fi作為下一個有效特征，并令F←F-{fi}，S←{fi}。

步驟5若不滿足|S|=k，轉向步驟4。

步驟6輸出特征集S。

k值的確定過程如下：當MRLR算法在數據樣本集選擇的特征子集的分類準確率出現拐點時，即加入下一個候選特征得到的分類準確率等于或小于不加條件下的分類準確率，此時計算該特征子集中分類準確率與特征維數的比值，若大于等于原始數據集的分類準確率與特征維數的比值，即

此時，k的值就是|S|，S即選擇的特征子集。

MRLR算法的時間開銷主要來自兩部分：一是計算兩兩特征之間的依賴度，其時間復雜度為mnlbn；二是為了最終得到k維的特征子集，需要經過k輪循環計算，因此其時間復雜度為kmnlbn，所以算法總的時間復雜度為O(mnlbn)。與文獻M IFS和M IFS-U算法的時間復雜度相同。充分說明MRLR算法在不增加時間復雜度的前提下，實現了對分類屬性樣本集的特征選擇。

4 仿真實驗及分析

4.1 實驗樣本集

實驗環境：M atlab7.9開發平臺，W indow s7操作系統。實驗采用文獻[13]UCI中的4個標準樣本集進行，4個標準樣本集都是分類屬性數據[14]，標準樣本集的組成見表1所示。

表1 實驗樣本集

對于以上樣本集，由于部分特征太具體化，不適合分類，在實驗中首先把它們去掉，以防止在構造分類模型時出現過擬合現象。Zoo樣本集中animal name特征，由于僅表示動物名字，不適合分類，所以在實驗中被去除；樣本集Dermatology的age特征也不適合分類，被去除。

4.2 實驗結果及分析

實驗中選用文獻[15]的LibSVM作為特征選擇算法的最終性能評價分類器。LibSVM是臺灣大學林智仁（Lin Chih-Jen）博士等通過對SVM的深入研究開發設計的一種簡單、易用、快速高效的多重分類支持向量機[15]。為了評估MRLR算法的實用性和有效性，并與文獻[8] M IFS算法、文獻[9]M IFS-U算法進行以下三方面的指標比較：（1）特征選擇結果中包含的特征數量；（2）所選特征子集在分類器LibSVM上的分類精度；（3）使用LibSVM分類器建立分類模型，在MRLR、M IFS與M IFS-U算法所選擇特征子集基礎上、進行逐一特征增加直到達到完全數據樣本集，分別進行分類實驗，以評價算法的性能。

實驗1：為了驗證MRLR算法的可用性，分別用MRLR、M IFS和M IFS-U三個算法在四個標準樣本集上進行實驗，按照算法描述，最終確定最優特征個數，即確定k的大小，MRLR算法k值確定如表2所示；同時比較各自所選特征子集的大小，如表3所示。

表2 MRLR算法中k值的確定

表3 MRLR算法與M IFS、M IFS-U得到的特征子集大小

從表3不難看出，MRLR算法對于樣本集House-votes、Zoo所選特征數量在三個參加比較的算法中最少，這是因為MRLR考慮了候選特征加入特征子集后與類別標簽的綜合影響，這證明了MRLR算法的科學性和有效性；對于M ushroom樣本集，MRLR所選特征與算法M IFS-U相同，但低于M IFS算法，這說明M IFS-U、MRLR兩個算法都克服了M IFS算法中評價函數可能失衡的影響；對于Dermatology樣本集，MRLR算法所選特征數量為15個，高于M IFS、M IFS-U算法的14個，這是因為MRLR算法在該樣本集中選擇的特征造成的誤差要大于其他兩種算法。另外，上述每個算法在每個樣本集上所選擇的特征重新組成一組樣本子集，分別記作：X1，X2，…，X12，為后續實驗做準備。

實驗2：本實驗主要為了驗證MRLR算法的高效性。在實驗1的基礎上，對三種算法所選取的特征子集X1，X2，…，X12在分類器LibSVM上進行訓練，比較最后的分類準確率。為了降低樣本偏差，本實驗采用十折交叉驗證法，將每個樣本集分成10份，輪流將其中9份做訓練1份做測試，10次結果的均值作為分類精度的估計。為了提高精確率，本實驗對每個算法下的數據集采用10次交叉驗證，并重復三次，求得分類精度的平均值和標準差，結果見表4所示。

表4 LibSVM在各4個特征子集上的分類精度（%）

由表4不難看出，三個算法獲得的各個特征子集在LibSVM分類器上都取得了比較好的分類精度。對于Dermatology樣本集，由于MRLR算法選擇的特征子集的特征維數比其他兩種算法高1維，所以分類精度明顯高于其他兩種算法，這是因為增加的這一維特征對類標簽的分類能力大于對特征子集造成的冗余；對于M ushroom和House-votes樣本集，三種算法所產生的特征子集的分類精度相同，其中對于M ushroom樣本集，MRLR算法和M IFS-U算法所選特征子集的維數低于M IFS算法，對于House-votes樣本集，MRLR算法所選的特征子集小于其他兩個參與對比的算法，說明在使用MRLR算法時，可以選擇更少的特征，同樣能達到與其他兩個算法相同的分類精度；對于Zoo樣本集，MRLR和M IFS-U算法所選的特征子集在LibSVM上的分類精度相同，高于M IFS算法的特征子集在LibSVM上的分類精度，另外，MRLR算法所選的特征子集的維數要低于M IFS-U算法所選的特征子集的維數。實驗2充分說明了MRLR算法在特征選擇時的高效性，即通過選擇更少的特征同樣可以取得比較好的分類效果。

實驗3：本實驗為了驗證算法的可靠性和有效性。實驗以各特征子集X1，X2，…，X12為基礎，通過按樣本集特征的原始順序逐一添加落選特征，直到所有的特征被完全選取為止。分別得出LibSVM分類器在各子集上的分類準確率。圖1、圖2、圖3和圖4分別是在樣本集Dermatology、Mushroom、House-votes和Zoo的特征子集上，分類準確率隨特征維變化的情況。

圖1 分類準確率隨特征子集的變化情況（Dermatology樣本集）

圖2 分類準確率隨特征子集的變化情況（M ushroom樣本集）

圖3 分類準確率隨特征子集的變化情況（House-votes樣本集）

圖4 分類準確率隨特征子集的變化情況（Zoo樣本集）

從圖1到圖4得出，四個樣本集中分類準確率在最小特征子集到完全樣本集的變化趨勢，當然，由于每個樣本集自身的特殊性，樣本集的變化趨勢也不盡相同，而且在不同的算法中的表現也有很大不同。

（1）圖1中的MRLR算法在所選15維特征子集上的分類準確率為94.651 2%，而在完全34維特征上的分類準確率為96.368 7%；同樣的，圖4中的MRLR算法在選擇7維特征子集上取得的分類準確率達到91.089 1%，與完全特征集的準確率相同。因此對于分類數較大的實驗樣本集Dermatology和Zoo，采用新算法MRLR能夠通過選取較低維的特征子集得到較高的準確率。

（2）從圖2和圖3的整個過程中分類準確率變化趨勢可以看出，在MRLR算法中特征數量的多少并沒有引起分類準確率太大的變化。說明其穩定性要優于M IFS算法和M IFS-U算法。

（3）從上述四圖中，可以看出：四個樣本集采用MRLR算法得到的分類準確率變化趨勢也不會超過10%，因此MRLR算法也可以保證在特征子集中加入的新特征后產生的相關性與冗余性的影響相抵消，確保較高的分類準確率。

通過以上實驗的對比可以得出，MRLR算法在四個標準樣本集上的仿真實驗效果總體上要優于M IFS、M IFS-U算法。這充分說明，通過在選擇過程中剔除冗余性過大的特征，可以選擇相對較少的特征就幾乎可以完全表征整個樣本集，而其他兩種算法會選擇更多的特征。這同時說明在文獻[8-9]兩算法中，冗余特征甚至是不相關特征都被賦予了很高的重要性，這從另一方面證明了MRLR算法的實用性及有效性。

5 結論

本文通過對互信息和分類屬性數據的研究，重新定義了特征信息量、特征依賴度等概念的計算，提出了一種改進的基于互信息的分類屬性數據特征選擇算法MRLR，算法考慮了候選特征加入特征子集后與類別標簽的互信息對分類結果可能產生的影響，并在分類屬性數據樣本集上進行了仿真實驗，實驗結果表明了MRLR算法對于分類屬性數據特征選擇的可靠性和高效性。

[1]邊肇祺，張學工.模式識別[M].2版.北京：清華大學出版社，2000.

[2]Last M，Kandel A，Maimon O.Information theoretic algorithm for feature selection[J].Pattern Recognation，2001，34（22）：799-811.

[3]Agrawal R，Imilinski T，Swam i A.M ining association rules between sets of items in large database[C]//Proc of the ACM SIGMOD Conference on Management of Data，1993.

[4]Hu Qinghua，Xie Zongxia，Yu Daren.Hybrid attribute reduction based on a novel fuzzy rough model and information granulation[J].Pattern Recognition，2007，40（12）：3509-3521.

[5]陳思睿，張永.基于粗糙集的特征選擇方法的研究[J].計算機工程與應用，2006，42（21）：159-162.

[6]唐亮，段建國.基于互信息最大化的特征選擇算法及應用[J].計算機工程與應用，2008，44（13）：130-133.

[7]Fano R.Transm ission of information：a statistical theory of communications[M].New York：Wiley，1961.

[8]Battiti R.Using mutual information for selecting features in Supervised neural net learning[J].IEEE Transactions on Neural Networks，1994，5：537-550.

[9]Kwak N，Choi C H.Input feature selection by mutual information based on Parzen window[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（12）：1667-1671.

[10]Minho Kim，Ramakrishna R S.Projected clustering for categorical datasets[J].Pattern Recognition Letters，2006，27：1405-1417.

[11]Amiri F，Rezaei M.Mutual information-based feature selection for intrusion detection systems[J].Journal of Network and Computer Applications，2011，34：1184-1199.

[12]劉震.基于互信息的Bayes網絡分類器的構建[D].上海：復旦大學，2003：23-25.

[13]Blake C，Merz C.UCI repository of machine learning database[EB/OL].[2012-04-21].http：//www.ics.uci.edu/～m learn/ M LRepository.

[14]Chert J，Yang Zhim in.An incremental clustering with attribute unbalance considered for categorical data[C]// 4th International Symposium on Computational Intelligence and Intelligent Systems，Huangshi，China，October 23-25，2009.

[15]Hsu C V，Chang C C，Lin C J.LIBSVM：a library for support vector machines[EB/OL].[2012-04-21].http：//www. csie.ntu.edu.tw/～cjlin/libsvm.

GU Wenqiang1,LI Zhihua2

1.Key Laboratory of Advanced Process Control for Light Industry Ministry of Education,School of IoT Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China
2.Engineering Research Center of IoT Technology Application,M inistry of Education,Wuxi,Jiangsu 214122,China

In this paper,a novel feature selection approach based on mutual information called More Relevance Less Redundancy（MRLR）algorithm for nominal data is proposed.By reconstructing the computation method of the amount of information,the conditional mutual information,the dependence between the features so that which can be suitable for computation related the nominal data,and a new definition of the evaluation function of feature selection is given,as well as a new feature selection criterion is used to evaluate the importance of each feature,which takes into account both relevance and redundancy.In MRLR,experimental results show that the relevance and redundancy respectively use mutual information to measure the dependence of features on the latent class and the dependence between features,and it also enhance the correctness and the effectiveness of MRLR algorithm.

nominal data;feature selection;mutual information

A

TP391.1

10.3778/j.issn.1002-8331.1209-0299

GU Wenqiang,LI Zhihua.Mutual in formation-based feature selection algorithm for nominal data.Computer Engineering and Applications,2014,50（16）：135-139.

顧文強（1987—），男，碩士研究生，研究方向為數據挖掘、信息安全；李志華（1969—），男，博士，副教授，碩士生導師，研究方向為智能信息處理、模式識別和網絡安全。E-mail：guwenqiang2010@yahoo.cn

2012-09-25

2013-01-06

1002-8331（2014）16-0135-05

CNKI網絡優先出版：2013-01-22,http://www.cnki.net/kcms/detail/11.2127.TP.20130122.1437.004.htm l