冗余性

基于鄰域互信息最大相關性最小冗余度的特征選擇

林培榕

【摘要】Featurelectionisanimportantdatapreprocessingtechnique,

wheremutualinformationhasbeenwidelystudiedininformationmeasure.

However,mutualinformationcannotdirectlycalculaterelevancyamong

paper,wefirstintroduceneighborhoodentropy

,weproponeighborhood

mutualinformationbadmaxrelevanceandminredundancyfeature

y,experimentalresultsshowthatthepropodmethodcan

effectivelylectadiscriminativefeaturesubt,andoutperformorequal

tootherpopularfeaturelectionalgorithmsinclassificationperformance.%

特征選擇是一種重要的數據預處理步驟，其中互信息是一類重要的信息度量方法。

本文針對互信息不能很好地處理數值型的特征，介紹了鄰域信息熵與鄰域互信息。

其次，設計了基于鄰域互信息的最大相關性最小冗余度的特征排序算法。最后，用

此算法選擇前若干特征進行分類并與其它算法比較分類精度。實驗結果表明本文提

出算法在分類精度方面且優于或相當于其它流行特征選擇算法。

【期刊名稱】《漳州師范學院學報（自然科學版）》

【年(卷),期】2013(000)004

【總頁數】6頁(P13-18)

【關鍵詞】特征選擇;鄰域互信息;最大相關性;最小冗余度

【作者】林培榕

【作者單位】閩南師范大學計算機科學與工程系，福建漳州363000

【正文語種】中文

【中圖分類】TP391

特征選擇作為一種重要的數據預處理步驟，廣泛應用于數據挖掘和模式識別的各個

領域[1-3].其基本思想是從樣本數據集中的原始特征空間找一個特征子集，使得該

子集比原始特征包含更多與類別相關的知識，同時又使得子集內部的冗余程度盡量

少.特征選擇算法一般分為過濾式、嵌入式和封裝式三大類，其中，過濾式與具體

算法相互獨立，且易于理解，得到許多學者的廣泛關注.

過濾式的特征選擇算法主要計算特征的重要度，然后按照特征的重要度進行排序.

過濾式的特征選擇算法主要采用信息熵或大間隔方法.對基于互信息的特征選擇算

法，一般需對數據集進行離散化，而離散化會對數據原始信息產生丟失；若不離散

化，一般采用Parzen窗口進行概率密度的估計，而該方法計算時間復雜度較高.

經典的特征選擇算法如：CFS[4]，FCBF[5]，mRMR[6]等.對基于大間隔的特征選

擇算法，主要分為三類，其一直接利用不同類別樣本的間隔最大化進行特征選擇，

如Relief[7],Simba[8]等；其二利用間隔損失函數最小化進行估算特征權重，如

Lasso[9]；其三，利用支持向量機進行訓練特征的權重，如SVM-RFE[10].

針對傳統信息熵進行特征選擇時需要離散化的缺點，本文引入了鄰域信息熵與鄰域

互信息，使其能夠很好地處理數值型或者混合型的數據.在利用鄰域互信息進行度

量信息之間相關性時，從特征與類標簽的重要性及已選特征與候選特征之間的冗余

度出發，提出了一種基于鄰域互信息最大相關性最小冗余度的特征排序算法.該算

法首先考慮特征與類標簽的重要性，選擇具有最大相關性的特征.其次，該算法考

慮已選特征與候選特征之間的冗余度，選擇與已選特征具有最小冗余度的特征.最

后，按照選入的特征順序對原始的特征空間進行排序.該算法通過改變鄰域大小可

以有效地處理名義型、數值型及混合型的數據，此外，實驗表明該算法通過選擇前

若干特征在分類精度上與其它特征算法相比有較大的提高.

綜上，本文主要內容安排如下：第二節介紹了鄰域熵與鄰域互信息的概念及相關性

質；第三節設計了基于鄰域互信息的最大相關性最小冗余度的特征排序算法；第四

節針對提出的算法進行實驗驗證，并對實驗結果的比較進行分析；第五節總結全文.

文獻[11]指出鄰域熵是Shannon熵的自然拓展.

定義1[11]給定由特征集刻畫的論域,是任意的特征子集,為該特征空間中樣本鄰域

關系.利用特征子集計算得到的鄰域記為,那么該鄰域粒子的不確定度為

鄰域近似空間<>的不確定性為

定義2[11]是描述對象的兩組特征.在特征空間的鄰域記為,那么和的聯合鄰域熵定

義為

特別地,當是輸入變量,是類標簽時,得,此時

定義3[11]是描述對象的兩組特征.已知特征后特征的條件鄰域熵為

定義4[11]是描述對象的兩組特征.和的鄰域互信息定義為

性質1給定兩組特征和,是這兩組特征的鄰域互信息,那么以下公式成立:

(1)=;

(2)=+-;

(3)=-=-.

特征選擇的目的之一在于選擇與類標簽具有最大相關性的特征子集，該方法稱為最

大相關性特征選擇.此方法的基本思想是計算每個特征與類標簽的互信息，從中選

擇一個特征子集，使得其互信息之和達到最大值.本文利用鄰域互信息代替互信息

（下面類同），其公式如下：

然而，根據公式(7)得到特征子集并未考慮到已選特征之間的冗余性.因此，在選擇

特征的時候，不僅需要考慮特征對類標簽的重要性，還需考慮候選特征與已選特征

之間的冗余度，選擇具有最小冗余度的特征子集方法稱為最小冗余性.計算兩個特

征之間的冗余性如公式(8)所示：

特征選擇過程中，聯合最大相關性與最小冗余性能夠有效地獲取重要的特征，而且

可以盡力刪除冗余的特征.利用公式(7)與(8)，可得公式(9)：

對于公式(9),其中代表所有特征，代表已選個特征，代表候選特征.

本文在對特征的重要性及特征之間的冗余性分析的基礎上，用改進的鄰域互信息計

算特征之間及特征與類標簽之間的相關性，設計基于鄰域互信息的最大相關性最小

冗余度的特征排序算法.該算法利用公式(9)將中的特征進行排序，中的特征排序算

法如下：

算法1.基于鄰域互信息的最大相關性最小冗余度的特征選擇算法（NMImRMR)

輸入：數據集，閾值.

輸出：特征排序.

初始化；

While

尋找候選特征使得公式(10)取最大值；

；

；

End

按照的選入順序排序

返回.

為了驗證所提出算法的有效性，我們從UCI數據集中挑選了四個常用數據集.為了

驗證算法的適用性，數據集的特征數量從13到34個，類別從兩類到三類，具體

描述信息見表1.同時，我們進行兩組實驗，第一組實驗與經典的特征選擇算法

Relief及NFARNRS[12]進行比較測試特征選擇后的分類精度；另一組檢測

NMImRMR與Relief隨著已選特征數量變化時其分類精度的變化.最后評價采用

十折交叉驗證法，其中分類器分別采用LSVM和KNN(K=1).

實驗一：為了驗證NMImRMR的特征選擇效果，本實驗中，與其它流行的特征選

擇算法進行了比較，其中將NMImRMR，NFARNRS涉及到的參數統一設置為

0.1.由于NFARNRS直接得到特征選擇結果，而NMImRMR與Relief得到是特

征的排序.為了統一比較，利用NFARNRS得到的特征個數統一作為NMImRMR

與Relief最后得到的特征個數，表2顯示這三種算法得到的特征子集.為了比較不

同特征選擇算法在四個UCI數據集上進行特征選擇后的分類精度，在表3及4中

加粗的單元格代表分類精度最高.另外，最后一行顯示不同特征選擇算法的平均分

類精度.從表3與4可以看出，不管是LSVM還是KNN分類器，NMImRMR的

平均分類精度都取得最高，且當分類器為LSVM時，NMImRMR在四個數據集上

都取得最優.因此，從本實驗可以看出，與其它流行的直接處理數值型特征的特征

選擇算法相比，說明了本文提出的NMImRMR算法具有較為優越的性能.

實驗二：由于NMImRMR與Relief都屬于過濾式的特征選擇算法，最終得到是特

征的排序.為了比較實驗比較，取前K個特征作為最終的特征選擇結果比較

NMImRMR與Relief的性能.本實驗采用LSVM作為分類器，檢驗在不同特征子

集上的分類精度.圖1中X軸表示取前K個特征為最終特征選擇結果，Y軸表示分

類精度.圖1中可以看出，在取前K個特征作為特征選擇結果時，NMImRMR基

本上取得比Relief更好的分類結果.因此NMImRMR在處理數值型或者混合型的

數據時，能有效地進行特征選擇.

針對傳統的信息熵不能處理數值型或者混合型的數據，本文引入鄰域信息熵和鄰域

互信息.從特征與類標簽的重要性及特征之間的冗余度出發，提出了一種基于鄰域

互信息的最大相關性最小冗余度的特征排序算法NMImRMR.該方法不僅拓展了

信息熵的使用范圍，而且能有效地針對各種類型數據集進行特征選擇.在公開UCI

數據集上的實驗結果表明，本文方法的特征選擇結果優于或相當于其他相關特征選

擇算法.

[1],oductiontovariableandfeaturelection[J].

JournalofMachineLearningRearch,2003,(3):1157-1182.

[2],electionforclassification[J].IntelligentData

Analysis,1997,(1):131-156.

[3],,,orhoodeffective

informationratioforhybridfeaturesubtevaluationandlection[J].

Neurocomputing,2013,(99):25-37.

[4]ation-badFeatureSelectionforDiscreteand

NumericClassMachineLearning[C]//ProceedingsoftheSeventh

InternationalConferenceonMachineLearning,2003:359-366.

[5],electionforhigh-dimensionaldata:afast

correlationbadfiltersolution[C]//ProceedingsoftheTwentieth

InternationalConferenceonMachineLearning,2003:856-863.

[6],,electionbadonmutual

information:criteriaofMax-Dependency,Max-Relevance,andMin-

Redundancy[C]//IEEETransactionsonPatternAnalysisandMachine

Intelligence,2005,(27):1226-1238.

[7]tingattributes:analysisandextensionsof

RELIEF[C]//ProceedingsEuropeanConferenceMachineLearning,1994:

171-182.

[8]-Bachrach,,badfeaturelection-

theoryandalgorithms[C]//proceedingsofthe21stInternational

ConferenceonMachineLearning,2004:40-48.

[9]sionshrinkageandlectionviathelasso[J].

B,1996,(58):267-288.

[10],,ll,lectionforCancer

ClassificationusingSupportVectorMachines[J].MachineLearning,2002,

(46):389-422.

[11],,,ingrelevancebetween

discreteandcontinuousfeaturesbadonneighborhoodmutual

information[J].ExpertSystemswithApplications,2011,(38):10737-10750.

[12],,,orhoodroughtbad

heterogeneousfeaturelection[J].InformationSciences,2008,(178):

3577-3594.