一种快速的Wrapper式特征子集选择新方法-叶吉祥

74201012()JournalofChangshaUniversityofScienceandTechnology(NaturalScience)Vol.7No.4Dec.2010　　　　　　　　　　　:2010-11-30:(10JJ2050):(1963-),,,,.　　:1672-9331(2010)04-0069-06Wrapper叶吉祥,龚希龄(,　410004)　:Wrapper,Wrapper(FastFeatureSubsetRanking,FFSR).,FFSR,.FFSR,SequentialFloatingForwardSelection(SFFS).FFSRSFFS,SFFS.:;;;:TP18;TP391:AAnovelfastWrapperforfeaturesubsetselectionYEJi-xiang,GONGXi-ling(SchoolofComputerandCommunicationEngineering,ChangshaUniversityofScienceandTechnology,Changsha410004,China)Abstract:Wrapperfeatureselectionmethodsareverytime-consuming.ThispaperproposesanovelfastWrappermethod,namelyFastFeatureSubsetRanking(FFSR).Incontrastwithconventionalmethodstakesinglefeature,thebasicevaluationunitofFFSRisfeaturesubsetandthecriterionistheconvergenceabilityofthesubset.FFSRanalysesconvergenceabilityfrombothaspectofspeedandextremum,andemploysSequentialFloatingForwardSelection(SFFS)toconstructandevaluatefastconvergentsubset.ComparedwithSFFS,FFSRcansignificantlyreducethetimerequiredwhilejustslightlylowthefeatureability.Keywords:featureselection;fastfeatureselection;Wrapper;featureevaluation　　DFd,FdJ[1].[2].NP[3],,FilterWrapper[4].Fil-ter,.Wrapper,.Filter,.Wrapper,.Wrapper.长沙理工大学学报(自然科学版)2010年12月,[5-9].,Filter,Filter.Wrapper(FastFeatureSubsetRanking,FF-SR).,FFSR,.,.SequentialFloatingForwardSelection(SFFS),,FFSR.FFSRSFFS、ReliefF,FFSRSFFS,.1　SFFSSFFSWrapper.SFFS,,,.F={f1,f2,…,fN},J(subset),T(),SFFS(F,J,T).SFFS:SetselF=WhileNotTStep1(Inclusion)　　x+=argmax{J(selF∪fi)fi∈F-selF}　　selF=selF∪x+Step2(ConditionalExclusion)　　x-=argmax{J(selF-fi)fi∈selF}　　if(J(selF-x-)J(selF))　　　selF=selF-x-　　　GotoStep2　　Else　　　GotoStep1returnselF2　FFSRWindowsXP,Matlab7.0,CPU1.6GHz,512M.UCIMachineLearningRepository,.、Musk.Musk1666598.(SVM)LibSVM.J(SVM)K(K-Fold-CrossValidationAccuracy,CVA)K(K-NearNeighbor,K-NN)(Leave-One-OutAccura-cy,LOOA).2.1　subsetF,J,card(subset)subset,1　subsetAbility(subset)=(card(subset),J(subset)),,card(subset),J(subset).2　(MaxSelCnt,JThresh-old),card(subset)MaxSelCnt,J(subset)JThreshold,subset(MaxSelCnt,JThreshold).3　subset(MaxSelCnt,JThreshold),subset(MaxSelCnt,JThreshold)..,JThreshold、J,JThreshold.,JThresholdSFFS,Division.Division,.JThreshold,Division,.70　第7卷第4期叶吉祥,等:一种快速的Wrapper式特征子集选择新方法2.2　1)SFFS.1,SVMCVA,10J0.95,J.K-NNLOOA,15J0.80.,SFFS.1　迭代次数与准则函数值Fig.1　IterationcountVS.J2)SFFS.,,,,Division(F,JThreshold,MaxSelCnt,T).Division:　SetM　SetJThreshold　SetMaxSelCnt　Setsubset1=…=subsetM=　Seti=0　WhileNOTT　　i=i+1　　S=subset1∪…∪subsetM　　T1=JJThreshold　　T2=card(selF)MaxSelCnt　　subseti=SFFS(F-S,J,T1+T2)　return{subset1,…,subsetM}M{subset1,subset2,…,subsetM}.Max-SelCnt=20,JThreshold=76,SVMCVAJ,2.2,7,subset8,MaxSelCnt.2　多个子集的迭代次数与准则函数值Fig.2　IterationcountVSJofMulti-Subset2.3　FFSRJThreshold,JThreshold,FastFeatureSubsetRankingFFSR(F,InitJ,MaxSelCnt,T),.FFSR:　SetFRank1=…=FRankk=Set　MaxSelCntSet　i=0SetcurJ=InitJWhileNotT　i=i+1　S=FRank1∪…∪FRankk　T1=J(subseti)curJ　{subset1,…,subsetn}=　　Division(F-S,curJ,MaxSelCnt,T1)　FRanki=subset1∪…∪subsetn　curJ=min{J(subset)subset∈FRanki}S=FRank1∪…∪FRankkselF=SFFS(S,,T)returnselF,MaxSelCntInitJ.,MaxSelCnt,JThreshold.MaxSelCnt,,JThreshold.:28,subset1subset7,subset8.,71长沙理工大学学报(自然科学版)2010年12月,,SFFRSFFS,,“”.:200,60,SFFS6030.SFFS,1,MaxSelCnt.T,J.3　FFSR3.1　FFSRSFFS,(3).3,FF-SR,SFFS.3　FFSR与SFFS算法时间比较Fig.3　Timecomparison(FFSRVS.SFFS)FFSR.FFSRDivisionSFFS,SFFSSFFS.DivisionSFFS,,SFFS,J,.JThreshold,,SFFS.3.2　,,.FFSR:,,..,SFFS.FFSRSFFS,JSVMCVA,30,4.4,FFSRJSFFS.4,FFSRReliefF[11].ReliefFFilter,,[12].ReliefF,J.3,FFSRReliefF.,FFSR,,FFSR.4　FFSR和SFFS,ReliefF特征能力比较Fig.4　Featureabilitycomparison(FFSR,SFFS,ReliefF)4FFSRFFSR.4,,FFSRSFFS2%,SFFS.,SFFS72　第7卷第4期叶吉祥,等:一种快速的Wrapper式特征子集选择新方法,.4　FFSRSFFS,.FFSR.FFSR,.,.,Filter,.〔〕[1]　PMNarendra,KFukunaga.Abranchandboundal-gorithmforfeaturesubsetselection[J].IEEETrans-actionsonComputers,1977,C-26(9):917-922.[2]　DashM,LIUH.Featureselectionforclassification[J].IntelligentDataAnalysis,1997(1):131-156.[3]　AmaldiE,KannV.Ontheapproximabilityofmini-mizingnonzerovariablesorunsatisfiedrelationsinlinearsystems[J].TheoreticalComputerScience,1998(209):237-260.[4]　KohaviR,JohnGH.Wrappersforfeaturesubsetse-lection[J].ArtificialIntelligence,1997,97(1-2):273-324.[5]　.[D].:,2010.LIUHua-wen.Astudyonfeatureselectionalgo-rithmsusinginformationentropy[D].Jilin:JilinUni-versity,2010.[6]　.[D].:,2010.CAOJin.Featureselectionresearchbasedonmaxi-mumrelevanceminimumredundancy[D].Qinhuang-dao:YanshanUniversity,2010.[7]　,,.[J].,2009(10):49-52.WANGBo,JIAYan,TIANLi.Semi-supervisedfea-tureselectionalgorithmbasedonextensionoflabel[J].ComputerScience,2009(10):49-52.[8]　QIANY,LiangJ,WeiW.Acceleratingincompletefeatureselection[A].ProceedingsoftheEighthIn-ternationalConferenceonMachineLearningandCy-bernetics[C].LosAlamitos,CA:IEEEComputerSocietyPress,2009:350-358.[9]　GUOB,DamperRI,GunnSR,etal.Afastsepara-bility-basedfeature-selectionmethodforhigh-dimen-sionalremotelysensedimageclassification[J].Pat-ternRecognition,2008,41(5):1653-1662.[10]　PudilP,FerriFJ,NovovicovaJ,etal.Floatingsearchmethodsforfeatureselectionwit