萤火虫算法

170J.Senthilnathetal./SwarmandEvolutionaryComputation1(2011)164–171

Table7

Table8

Resultsofnatureinspiredtechniquesafter20runsforoptimalclustercentersusing

Table9

ComparisonofclassificationefficiencyforIrisdataset.evaluationiseffectivelyscannediterativelytillalltheparticlesconvergetoanoptimalresulti.e.intheformofclustercenters.IntheFAalgorithm,afireflyparticlemovestowardanotherfireflyparticle,whichhasabetterobjectivefunctionvalue(fitness).Thedistancemovedbythefireflyineachinstanceisgivenbythedistancebetweenthetwofireflyparticles(r).Whenthevalueofrislarge/small,thefireflywillmoveasmall/largedistance.Thiswillaffectthecomputationtimeofthisalgorithm.InPSOeachparticlewillmoveadistancebasedonitspersonalbestandtheglobalbest.InABCeachbeeparticlepositionwillbecomparedtwicewithbestparticleposition.Furthertheclustercentersgeneratedbythesealgorithmisanalyzedusingthedistancesbetweenthegivendataandtheclustercentersarecomputed.Thedataisassignedtotheclustercenter(class)thathastheminimumdistance.Theperformancemeasurewillhelpsustoexaminewhichmethodhasgeneratedtheoptimalclustercenters.

TheclassificationmatrixfortheentireIrisdatasetareshowninTable9.Fromthistable,wecanobservethat,forallthenatureinspiredalgorithms,samplesbelongingtoClass2andClass3aregettingmisclassifiedasClass3andClass2respectively.FortheFAandABCgeneratedoptimalclustercenters,theperformanceofindividualefficiencyofClass2is96%whereasPSOhas92%.TheindividualefficiencyofClass3usingFAis88%whichisbetterincomparisonwiththatofABCandPSOwith72%and74%respectively.Inallthealgorithms,Class1isclassifiedwithoutanymisclassificationandhencehaveindividualefficiencyof100%,asitislinearlyseparableincomparisonwiththatofother2classes.Also,theaverageandoverallefficiencyisbetterinthecaseoftheFAwith94.7%incomparisontoABCandPSOis89.3%and88.7%respectively.Henceitisimportanttoconsidertheindividual,averageandoverallefficiencyinmulti-classclassificationproblemforageneratedclustercenters.

Itisimportanttonotethattheperformanceofclusteringmainlydependsonthesizeandqualityoftrainingdataset.Therearesomemethodsavailableintheliteraturefortheselectionoftrainingdata

set[36].Earlierstudyshowedthattheproperselectionoftrainingdatasetimprovestheperformancemeasure[36].Inourstudy,wehaveselected75%oftrainingdatasetrandomlyandtabulatedtheresultbasedonthemostfavorableperformancemeasurefortheselectedtrainingdataset.

Inoverallformostofthedataset,theFAhasgoodglobalperformance.WecanclaimthatbylookingattheaccuracyandrobustnessofFA,itcanbeusedforclusteringproblemsstudiedinthispaper.

6.Discussionsandconclusions

Thispaperinvestigatesanewnatureinspiredalgorithm—theFAisusedforclusteringandevaluatingitsperformance.TheFAalgorithmiscomparedwithABCandPSOasallthesemethodsareinthesameclassofpopulation-based,natureinspiredoptimizationtechniques.Asinotherpopulation-basedalgorithms,theγperformanceoftheFAdependsonthepopulationsize,β,and.IntheFAalgorithm,afireflyparticlemovetowardanotherfireflyparticle,whichhasabetterobjectivefunctionvalue(fitness).Thedistancemovedbythefireflyineachinstanceisgivenbythedistancebetweenthetwofireflyparticles(r).Theeffectofthevaluesofβandγarediscussedin[18].Whenthevalueofrislarge/small,thefireflywillmoveasmall/largedistance.Thiswillaffectthecomputationtimeofthisalgorithm.InPSOeachparticlewillmoveadistancebasedonitspersonalbestandtheglobalbest.InABCeachbeeparticlepositionwillbecomparedtwicewithbestparticleposition.IntheFAalgorithmonlythedistanceisnecessaryforthemovement.Theperformancemeasure(CEP),willhelpsustoexaminewhichmethodhasgeneratedtheoptimalclustercenters.Theclusteringtaskof13benchmarkdatasetsareaccomplishedsuccessfullybytheprocedureofpartitionalclusteringusingare-centnatureinspiredtechnique—FireflyAlgorithm(FA).Clusteringisanimportanttechniquetoidentifyhomogeneousclusters(orclasses)suchthatthepatternsforaclustercentershareahighdegreeofaffinitywhilebeingverydissimilarforotherclusters.TheperformanceoftheFAusingclassificationerrorpercentageiscomparedwithothertwonatureinspiredtechniques—ArtificialBeeColony(ABC)andParticleSwarmOptimization(PSO)andotherninemethodswhicharewidelyusedbytheresearchers.Theper-formancemeasureusingclassificationefficiency—individual,aver-ageandoverallefficiencyoftheFAisanalyzedusing13benchmarkproblems.Fromtheresultsobtained,wecanconcludethattheFAisanefficient,reliableandrobustmethod,whichcanbeappliedsuccessfullytogenerateoptimalclustercenters.Acknowledgments

Theauthorswouldliketothankthereviewersfortheircommentswhichwereusefulduringtherevisionofthisstudy.References

[1]M.R.Anderberg,ClusterAnalysisforApplication,AcademicPress,NewYork,

1973.

[2]J.A.Hartigan,ClusteringAlgorithms,Wiley,NewYork,1975.

[3]P.A.Devijver,J.Kittler,PatternRecognition:AStatisticalApproach,Prentice-Hall,London,1982.

[4]A.K.Jain,R.C.Dubes,AlgorithmsforClusteringData,Prentice-Hall,Englewood

Cliffs,1988.

[5]H.Frigui,R.Krishnapuram,Arobustcompetitiveclusteringalgorithmwith

applicationsincomputervision,IEEETransactionsonPatternAnalysisandMachineIntelligence21(1999)450–465.

[6]Y.Leung,J.Zhang,Z.Xu,Clusteringbyscale-spacefiltering,IEEETransactions

onPatternAnalysisandMachineIntelligence22(2000)1396–1410.

[7]D.Chris,XiaofengHe,Clustermergingandsplittinginhierarchicalclustering

algorithms,in:Proc.IEEEICDM,2002,pp.1–8.

[8]B.Mirkin,MathematicalClassificationandClustering,KluwerAcademic

Publishers,Dordrecht,1996.

[9]D.Karaboga,C.Ozturk,Anovelclusterapproach:ArtificialBeeColony(ABC)

algorithm,AppliedSoftComputing11(1)(2010)652–657.