基于互信息的分類屬性數(shù)據(jù)特征選擇算法

顧文強(qiáng)，李志華

1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫 214122

2.物聯(lián)網(wǎng)應(yīng)用技術(shù)教育部工程研究中心，江蘇無錫 214122

基于互信息的分類屬性數(shù)據(jù)特征選擇算法

顧文強(qiáng)1，李志華2

1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無錫 214122

2.物聯(lián)網(wǎng)應(yīng)用技術(shù)教育部工程研究中心，江蘇無錫 214122

提出了一種針對(duì)分類屬性數(shù)據(jù)特征選擇的新算法。通過給出一種能夠直接評(píng)價(jià)分類屬性數(shù)據(jù)特征選擇的評(píng)價(jià)函數(shù)新定義，重新構(gòu)造能實(shí)現(xiàn)分類屬性數(shù)據(jù)信息量、條件互信息、特征之間依賴度定義的計(jì)算公式，并在此基礎(chǔ)上，提出了一種基于互信息較大相關(guān)、較小冗余的特征選擇（MRLR）算法。MRLR算法在特征選擇時(shí)不僅考慮了特征與類標(biāo)簽之間的相關(guān)性，而且還考慮了特征之間的冗余性。大量的仿真實(shí)驗(yàn)表明，MRLR算法在針對(duì)分類屬性數(shù)據(jù)的特征選擇時(shí)，能獲得冗余度小且更具代表性的特征子集，具有較好的高效性和穩(wěn)定性。

分類屬性數(shù)據(jù)；特征選擇；互信息

1 引言

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

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

2 互信息簡(jiǎn)介

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

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

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

通?；バ畔⒂眯畔㈧赜?jì)算成如式（2）所示。

其中，

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

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

3 基于互信息的分類屬性數(shù)據(jù)特征選擇算法

分類屬性數(shù)據(jù)的值往往具有特定的含義，并且這些數(shù)據(jù)的分布與空間距離無關(guān)、數(shù)據(jù)冗余性大[10]。同時(shí)分類屬性數(shù)據(jù)樣本集中不同類別之間的差別很微弱，因?yàn)榇蟛糠謽颖镜奶卣髦抵貜?fù)、甚至重疊，要對(duì)其進(jìn)行分類度量比較困難[5]。針對(duì)分類屬性數(shù)據(jù)特征選擇的特殊性，本文展開以下研究。

3.1 相關(guān)定義

為了有效地實(shí)現(xiàn)分類屬性數(shù)據(jù)的特征選擇，首先給出以下新定義或定義[12]的新計(jì)算。

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

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

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

定義3根據(jù)以上定義，兩個(gè)特征fi和fj的依賴度定義如下：

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

定義4分類屬性數(shù)據(jù)特征選擇對(duì)特征fi的評(píng)價(jià)函數(shù)如下：

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

3.2 算法的基本思想

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

3.3 MRLR算法

MRLR算法首先設(shè)定一個(gè)空的特征子集S、包含所有特征的候選特征集合F，然后，求出候選特征集合中每個(gè)特征與類標(biāo)簽的互信息，進(jìn)一步求出特征間的依賴度，選擇依賴度最大值的特征加入特征集合S；最后，在每一輪循環(huán)中，應(yīng)用式（8）的特征選擇評(píng)價(jià)函數(shù)選擇其計(jì)算結(jié)果最大值對(duì)應(yīng)的特征加入特征子集S，直到S中的特征維數(shù)滿足要求。MRLR算法描述如下：

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

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

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

步驟4在剩余的候選特征中，依次選擇特征fi，根據(jù)式(8)計(jì)算候選特征的評(píng)價(jià)值，選擇最大值對(duì)應(yīng)的fi作為下一個(gè)有效特征，并令F←F-{fi}，S←{fi}。

步驟5若不滿足|S|=k，轉(zhuǎn)向步驟4。

步驟6輸出特征集S。

k值的確定過程如下：當(dāng)MRLR算法在數(shù)據(jù)樣本集選擇的特征子集的分類準(zhǔn)確率出現(xiàn)拐點(diǎn)時(shí)，即加入下一個(gè)候選特征得到的分類準(zhǔn)確率等于或小于不加條件下的分類準(zhǔn)確率，此時(shí)計(jì)算該特征子集中分類準(zhǔn)確率與特征維數(shù)的比值，若大于等于原始數(shù)據(jù)集的分類準(zhǔn)確率與特征維數(shù)的比值，即

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

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

4 仿真實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)樣本集

實(shí)驗(yàn)環(huán)境：M atlab7.9開發(fā)平臺(tái)，W indow s7操作系統(tǒng)。實(shí)驗(yàn)采用文獻(xiàn)[13]UCI中的4個(gè)標(biāo)準(zhǔn)樣本集進(jìn)行，4個(gè)標(biāo)準(zhǔn)樣本集都是分類屬性數(shù)據(jù)[14]，標(biāo)準(zhǔn)樣本集的組成見表1所示。

表1 實(shí)驗(yàn)樣本集

對(duì)于以上樣本集，由于部分特征太具體化，不適合分類，在實(shí)驗(yàn)中首先把它們?nèi)サ?，以防止在?gòu)造分類模型時(shí)出現(xiàn)過擬合現(xiàn)象。Zoo樣本集中animal name特征，由于僅表示動(dòng)物名字，不適合分類，所以在實(shí)驗(yàn)中被去除；樣本集Dermatology的age特征也不適合分類，被去除。

4.2 實(shí)驗(yàn)結(jié)果及分析

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

實(shí)驗(yàn)1：為了驗(yàn)證MRLR算法的可用性，分別用MRLR、M IFS和M IFS-U三個(gè)算法在四個(gè)標(biāo)準(zhǔn)樣本集上進(jìn)行實(shí)驗(yàn)，按照算法描述，最終確定最優(yōu)特征個(gè)數(shù)，即確定k的大小，MRLR算法k值確定如表2所示；同時(shí)比較各自所選特征子集的大小，如表3所示。

表2 MRLR算法中k值的確定

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

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

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

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

由表4不難看出，三個(gè)算法獲得的各個(gè)特征子集在LibSVM分類器上都取得了比較好的分類精度。對(duì)于Dermatology樣本集，由于MRLR算法選擇的特征子集的特征維數(shù)比其他兩種算法高1維，所以分類精度明顯高于其他兩種算法，這是因?yàn)樵黾拥倪@一維特征對(duì)類標(biāo)簽的分類能力大于對(duì)特征子集造成的冗余；對(duì)于M ushroom和House-votes樣本集，三種算法所產(chǎn)生的特征子集的分類精度相同，其中對(duì)于M ushroom樣本集，MRLR算法和M IFS-U算法所選特征子集的維數(shù)低于M IFS算法，對(duì)于House-votes樣本集，MRLR算法所選的特征子集小于其他兩個(gè)參與對(duì)比的算法，說明在使用MRLR算法時(shí)，可以選擇更少的特征，同樣能達(dá)到與其他兩個(gè)算法相同的分類精度；對(duì)于Zoo樣本集，MRLR和M IFS-U算法所選的特征子集在LibSVM上的分類精度相同，高于M IFS算法的特征子集在LibSVM上的分類精度，另外，MRLR算法所選的特征子集的維數(shù)要低于M IFS-U算法所選的特征子集的維數(shù)。實(shí)驗(yàn)2充分說明了MRLR算法在特征選擇時(shí)的高效性，即通過選擇更少的特征同樣可以取得比較好的分類效果。

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

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

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

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

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

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

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

（2）從圖2和圖3的整個(gè)過程中分類準(zhǔn)確率變化趨勢(shì)可以看出，在MRLR算法中特征數(shù)量的多少并沒有引起分類準(zhǔn)確率太大的變化。說明其穩(wěn)定性要優(yōu)于M IFS算法和M IFS-U算法。

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

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

5 結(jié)論

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

[1]邊肇祺，張學(xué)工.模式識(shí)別[M].2版.北京：清華大學(xué)出版社，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].計(jì)算機(jī)工程與應(yīng)用，2006，42（21）：159-162.

[6]唐亮，段建國.基于互信息最大化的特征選擇算法及應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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網(wǎng)絡(luò)分類器的構(gòu)建[D].上海：復(fù)旦大學(xué)，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.

顧文強(qiáng)（1987—），男，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、信息安全；李志華（1969—），男，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)橹悄苄畔⑻幚怼⒛Ｊ阶R(shí)別和網(wǎng)絡(luò)安全。E-mail：guwenqiang2010@yahoo.cn

2012-09-25

2013-01-06

1002-8331（2014）16-0135-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-22,http://www.cnki.net/kcms/detail/11.2127.TP.20130122.1437.004.htm l