冗余性

基于邻域互信息最大相关性最小冗余度的特征选择

林培榕

【摘要】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.