基于相关性分组的拉普拉斯特征评分算法

朱文龙， 樊明宇， 郑　蓉

(温州大学, 浙江 温州 325035)



基于相关性分组的拉普拉斯特征评分算法

朱文龙， 樊明宇， 郑蓉

(温州大学, 浙江 温州 325035)

摘要：针对模式识别和机器学习中拉普拉斯评分的特征选择方法存在未考虑特征之间相关性信息这一缺陷，提出了一种新的评分算法。先利用特征之间的相关性对特征进行分组，再在组内按照其重要性进行评分，尽可能选择那些不相似的重要特征来表达数据。实验证明，该方法应用于多个数据集均具有较好的效果。

关键词：特征选择；特征相关性；相关性分组；拉普拉斯评分

特征选择是模式识别和机器学习的关键技术之一，选择真正有意义的特征即可获得很好的预测效果。经典的特征选择算法包括费舍尔评分(Fisher Score)[1]、稳健回归(Robust Regression)、跟踪比率(Trace Ratio)[2]等。这些特征选择算法可以按照其与后续分类算法的结合方式被分为过滤式、封装式和嵌入式[3]。过滤式特征选择算法只依据样本数据的内在关系分析特征间的差异，不依赖具体的学习器，常用的有F-statistic[4]、relieF[5]、 mRMR[6]以及信息增益(Information Gain)[7]等。封装式特征选择算法是将某种学习器嵌入特征子集的搜索过程，常用的有Lasso[8]、LARs[9]、ERFS[10]和支持向量机递归特征排除算法(SVMRFE)[11]等。封装式特征选择算法通常有很好的效果，但有很高的计算复杂度。嵌入式特征选择算法则是将特征选择模型嵌入某个特定的分类或聚类的算法当中。

在过滤式特征选择算法中，最简单的就是对单个特征的方差进行分析并给予评分[12]。在这种算法中，特征的方差越大，该特征越有意义，越值得选择。在此基础上，基于拉普拉斯评分的特征选择(Laplacian Score)[13]方法被提出，它不仅要求被选的特征有较高方差，而且要求其有较强的几何结构保留能力，拉普拉斯评分甚至可以作为评判新的无监督或者有监督的特征选择算法性能的基准算法[14]。但是，该算法有一个明显的缺点，就是忽视了特征之间的相关性[15-16]，常常会导致选择的重要特征加起来不如若干个特征合理组合的表达能力更强。因此，本文充分利用特征之间的相关性信息，在拉普拉斯评分算法的基础上，提出了一种基于相关性分组(Correlation Grouping)的拉普拉斯评分的无监督的特征选择算法(CG-Laplacian Score)。

1相关背景知识

1.1传统的拉普拉斯评分算法

拉普拉斯评分选择的特征不仅要求有较高方差，而且要求有较强的位置保留能力。

Step2：计算两个样本点之间的权重大小Sij：

(1)

其中，t是人工给定的一个值，一般取1。

(2)

则fr的方差为：

(3)

Step4:令L=D-S，S为样本之间的权重矩阵，可以得到：

(4)

因此，第r个特征的拉普拉斯评分为：

(5)

拉普拉斯评分越小代表特征越重要。

拉普拉斯评分算法有效地衡量了各个特征的权重，可优先选择权重比较小的那些。但是，这种算法没有衡量各个特征之间的相关性，有可能选取冗余特征。为了提高算法的准确度，需要对特征之间的相关性加入衡量标准。

1.2特征相关性分组

(6)

给定一个阈值θ，如果特征s和特征t的相关度Rst>θ，就认为s和t具有较大的相关度，可以归为一组；相反，如果某个特征p与其他所有特征的相关度Rpx<θ(x=1,2,…,p-1,p+1,…,d)，则认为特征p为冗余或者噪声，需要删除[17]。

2特征相关性分组的拉普拉斯评分

对新的数据集X′进行拉普拉斯评分，得到被保留的d1个特征的评分为(L1,…,Ld1)。被删除的特征对应的评分为零。

分组之后，在被分成h组特征的每一组内都有两个特征。利用拉普拉斯评分对它们进行投票，即比较这两个特征的拉普拉斯评分。给予拉普拉斯评分认为重要的那个特征一个重要性投票，另外一个不得票。最后统计每个特征得到的票数，票数越多的特征越重要，从而实现特征相关性分组的拉普拉斯评分。

特征相关性分组的拉普拉斯评分算法如下：

输出： 所有特征的评分向量W

(1)计算输入数据集特征之间的相关性Rst，得到相关性矩阵R。

(2)选取分组的阈值：θ=min(R)+0.9×(max(R)-min(R))。这是一个经验上效果非常好的参数取值。

(3)根据式(6)对特征分组，得到分组矩阵：

(5)对新的数据集进行拉普拉斯评分，得到d1个特征的评分(L1,L2,…,Ld1)，然后，将此前删除的特征评分设为零，即可得到所有特征的评分。

(6)h为相似度大于θ的特征对数目,即h组的每一组内都有两个特征。利用拉普拉斯评分对它们进行投票，即比较这两个特征的拉普拉斯评分。对拉普拉斯评分算法认为重要的那个特征给予一个重要性投票，另外一个不得票。

(7)最后统计每个特征得到的票数，票数越多的特征越重要，从而实现特征相关性分组的拉普拉斯评分。

3实验测试

为了验证特征相关性分组的拉普拉斯评分算法的效果，对目前UCI机器学习库中比较流行的几个数据集以及特征选择中比较常用的COIL20和COIL100数据集进行了测试。这些数据库的基本信息如表1所示。

采用十折交叉验证法对每个数据集进行测试，每次测试都用拉普拉斯评分、特征相关性分组的拉普拉斯评分(CG-LaplacianScore)、费舍尔评分(FisherScore)、EfficientandRobustFeatureSelection(ERFS)以及UnsupervisedLocalDiscriminativeAnalysis(UDFS)等5种算法对同一数据集的特征进行评分，选出的特征从测试数据上进行分类，用分类的准确率来衡量算法的效果(见图1)。

表1　数据集的特征信息

从图1可以看出，在多数情况下，本文算法大大改进了拉普拉斯算法。diabetes和glass数据集的特征数比较少，对特征选择算法的要求比较高。比较图1(a)和图1(b)可以发现，特征相关性分组的拉普拉斯评分算法在这两个数据集上有明显的优势。值得注意的是，在图1(b)中，拉普拉斯评分和费舍尔评分的结果完全相同，而特征相关性分组的拉普拉斯评分结果却优于这两种评分结果。对于Vehicle和Ionosphere数据集，由于它们的类别数比较少，利用特征选择算法的效果起伏很大。在图1(c)中，尽管所有算法的结果都不稳定，特征相关性分组的拉普拉斯评分的结果却能始终优于其他算法。而且，在选择最重要的10个特征时能达到最高的准确率，这是其他算法达不到的。图1(d)显示，特征相关性分组的拉普拉斯评分算法除了依然具备在图1(c)中的优点以外，对于原始的拉普拉斯评分算法也有较大改善。图1(e)和图1(f)分别对应于COIL20和COIL100数据集，它们的特征数和类别数都比较多，算法效果比较平稳。在这种情况下，加入特征相关性分组后的拉普拉斯评分算法的改善效果依然很明显，而且在选择较少特征时就能达到很高的准确率。

4结语

为了弥补拉普拉斯评分算法中没有考虑特征之间的相关性这一明显缺陷，提出了一种基于特征相关性分组的拉普拉斯评分算法。这是一种新的过滤式无监督学习的特征选择算法。拉普拉斯评分算法选出的特征不仅有较高的方差，而且有较强的几何结构保留能力，能够很好地代表原始特征全体，很多特征之间的相关性较高。这些特征重复表达了原始数据集中的某些信息，影响了算法的运行速度和准确率。在此基础上，加入特征相关性分组之后，评分算法所选出的特征不仅能够满足拉普拉斯评分的要求，而且在特征分组后删除了冗余和噪声。新的数据集的拉普拉斯评分不受这些冗余和噪声的影响，使评分变得更加准确。此外，删除冗余和噪声相当于降低了数据集的维数，能够加快拉普拉斯评分的速度，降低算法的复杂度。在6种数据集上的实验结果表明，新算法的结果准确率优于普通的拉普拉斯算法。

(a)diabetes(b)glass

参考文献：

[1]RichardOD,PeterEH,DavidGS.PatternClassification[M].Cairo:Wiley-InterSciencePublication, 2000:44-47.

[2]NieF,XiangS,JiaY,etal.TraceRatioCriterionforFeatureSelection[C]//ProceedingsoftheTwenty-ThirdAAAIConferenceonArtificialIntelligence.Chicago:AAAI,2008:671-676.

[3]GuyonI,ElisseeffA.AnIntroductiontoVariableandFeatureSelection[J].JournalofMachineLearningResearch, 2003(3):1157-1182.

[4]LiuH,MotodaH.FeatureSelectionforKnowledgeDiscoveryandDataMining[M].BerlinHeidelberg:SpringerInternational, 1998:95-97.

[5]RobnikIM,KononenkoI.TheoreticalandEmpiricalAnalysisofReliefFandRRelief[J].MachineLearning, 2003, 53(1-2):23-69.

[6]DingC,PengH.MinimumRedundancyFeatureSelectionfromMicroarrayGeneExpressionData[J].BioinformaticsandComputationalBiology,2005,3(2):185-205.

[7]RaileanuLE,StoffelK.TheoreticalComparisonBetweentheGiniIndexandInformationGain[J].AnnalsofMathematics&ArtificialIntelligence, 2001, 41(1):77-93.

[8]TibshiraniR.RegressionShrinkageAndSelectionViaTheLasso[J].JournaloftheRoyalStatisticalSociety, 1994, 58(1):267-288.

[9]TrevorBE,HastieT,JohnstoneL,etal.LeastAngleRegression[J].AnnalsofStatistics, 2002, 32(2):407-499.

[10]NieF,HuangH,CaiX,etal.EfficientandRobustFeatureSelectionViaJoint612, 1-NormsMinimization[M].Massachusetts:MITPress,2010:1813-1821.

[11]GuyonI,WestonJ,BarnhillS,etal.GeneSelectionforCancerClassificationUsingSupportVectorMachines[J].MachineLearning, 2002, 46(1-3):389-422.

[12]LiuJ,LiB,ZhangWS.FeatureExtractionUsingMaximumVarianceSparseMapping[J].NeuralComputing&Applications, 2012, 21(8):1827-1833.

[13]HeX,CaiD,NiyogiP.LaplacianScoreforFeatureSelection[J].NIPS, 2005(18):507-514.

[14]ZhangD,ChenS,ZhouZH.ConstraintScore:ANewFilterMethodforFeatureSelectionwithPairwiseConstraints[J].PatternRecognition, 2008, 41(5):1440-1451.

[15]CaiD,ZhangC,HeX.UnsupervisedFeatureSelectionforMulti-clusterData[C]//Proceedingsofthe16thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.Washington:ACM, 2010:333-342.

[16]张莉,孙钢,郭军. 基于K-均值聚类的无监督的特征选择方法[J]. 计算机应用研究,2005(3):23-24,42.

[17]KongD,FujimakiR,LiuJ,etal.ExclusiveFeatureLearningonArbitraryStructuresViaL2,1-norm[M].Massachusetts:MITPress,2014:1655-1663.

(责任编辑：王长通)

A New Laplacian Score for Feature Selection Based on Feature’s Correlation Grouping

ZHU Wen-long, FAN Ming-yu, ZHENG Rong

(Wenzhou University, Wenzhou 325035, China)

Abstract：One problem to be solved in pattern recognition and machine learning is feature selection. Laplacian score is one of the representatives of filter feature selection. But this method doesn’t consider the correlations between features. In this paper, a feature selection algorithm based on Laplacian score and the correlations between features is proposed. Firstly, group the features by correlations between them, then calculate the Laplacian score in the same group, and calculated the total score of each feature in all groups as the final score. This ensures that the data are expressed as the key features which are not similar to each other. The experimental results signify that the performance of our proposed technique is obviously better than those from the other techniques.

Key words：feature selection； feature correlation； correlation grouping； Laplacian score

中图分类号：TP181

文献标志码：A

DOI:10.3969/j.issn.1671-6906.2016.01.019

文章编号：1671-6906(2016)01-0079-05

作者简介：朱文龙(1991-)，男，河南禹州人，硕士生，主要研究方向为模式识别和机器学习。

收稿日期：2015-07-27