Clustering using firefly algorithm Performance study

萤火虫算法

SwarmandEvolutionaryComputation1(2011)

164–171

ContentslistsavailableatSciVerseScienceDirect

SwarmandEvolutionaryComputation

journalhomepage:

/locate/swevo

Regularpaper

Clusteringusingfireflyalgorithm:Performancestudy

J.Senthilnath,S.N.Omkar ,V.Mani

DepartmentofAerospaceEngineering,IndianInstituteofScience,Bangalore,India

articleinfoabstract

AFireflyAlgorithm(FA)isarecentnatureinspiredoptimizationalgorithm,thatsimulatestheflashpatternandcharacteristicsoffireflies.Clusteringisapopulardataanalysistechniquetoidentifyhomogeneousgroupsofobjectsbasedonthevaluesoftheirattributes.Inthispaper,theFAisusedforclusteringonbenchmarkproblemsandtheperformanceoftheFAiscomparedwithothertwonatureinspiredtechniques—ArtificialBeeColony(ABC),ParticleSwarmOptimization(PSO),andotherninemethodsusedintheliterature.ThirteentypicalbenchmarkdatasetsfromtheUCImachinelearningrepositoryareusedtodemonstratetheresultsofthetechniques.Fromtheresultsobtained,wecomparetheperformanceoftheFAalgorithmandconcludethattheFAcanbeefficientlyusedforclustering.

CrownCopyright©2011PublishedbyElsevierLtd.Allrightsreserved.

Articlehistory:

Received10February2011Receivedinrevisedform5May2011

Accepted2June2011

Availableonline30June2011Keywords:ClusteringClassificationFireflyalgorithm

1.Introduction

Clusteringisanimportantunsupervisedclassificationtech-nique,whereasetofpatterns,usuallyvectorsinamulti-dimensionalspace,aregroupedintoclusters(orgroups)basedonsomesimilaritymetric[1–4].Clusteringisoftenusedforavari-etyofapplicationsinstatisticaldataanalysis,imageanalysis,dataminingandotherfieldsofscienceandengineering.

Clusteringalgorithmscanbeclassifiedintotwocategories:hierarchicalclusteringandpartitionalclustering[5,6].Hierarchicalclusteringconstructsahierarchyofclustersbysplittingalargeclusterintosmalleronesandmergingsmallerclusterintotheirnearestcentroid[7].Inthis,therearetwomainapproaches:(i)thedivisiveapproach,whichsplitsalargerclusterintotwoormoresmallerones;(ii)theagglomerativeapproach,whichbuildsalargerclusterbymergingtwoormoresmallerclusters.Ontheotherhandpartitionalclustering[8,9]attemptstodividethedatasetintoasetofdisjointclusterswithoutthehierarchicalstructure.Themostwidelyusedpartitionalclusteringalgorithmsaretheprototype-basedclusteringalgorithmswhereeachclusterisrepresentedbyitscenter.Theobjectivefunction(asquareerrorfunction)isthesumofthedistancefromthepatterntothecenter[6].Inthispaperweareconcernedwithpartitionalclusteringforgeneratingclustercentersandfurtherusingtheseclustercenterstoclassifythedataset.

Apopularpartitionalclusteringalgorithm—k-meansclustering,isessentiallyafunctionminimizationtechnique,wheretheobjectivefunctionisthesquarederror.However,themain

Correspondingauthor.

E-mailaddress:omkar@aero.iisc.ernet.in(S.N.Omkar).

drawbackofk-meansalgorithmisthatitconvergestoalocalminimafromthestartingpositionofthesearch[10].Inordertoovercomelocaloptimaproblems,manynatureinspiredalgorithmssuchas,geneticalgorithm[11],antcolonyoptimization[12],artificialimmunesystem[13],artificialbeecolony[9],andparticleswarmoptimization[14]havebeenused.Recently,efficienthybridevolutionaryoptimizationalgorithmsbasedoncombiningevolutionarymethodsandk-meanstoovercomelocaloptimaproblemsinclusteringareused[15–17].

TheFireflyAlgorithm(FA)isarecentnatureinspiredtech-nique[18],thathasbeenusedforsolvingnonlinearoptimizationproblems.Thisalgorithmisbasedonthebehaviorofsocialinsects(fireflies).Insocialinsectcolonies,eachindividualseemstohaveitsownagendaandyetthegroupasawholeappearstobehighlyorganized.Algorithmsbasedonnaturehavebeendemonstratedtoshoweffectivenessandefficiencytosolvedifficultoptimizationproblems.Aswarmisagroupofmulti-agentsystemssuchasfire-flies,inwhichsimpleagentscoordinatetheiractivitiestosolvethecomplexproblemoftheallocationofcommunicationtomultipleforagesitesindynamicenvironments.

Inthisstudy,theFireflyAlgorithm(FA),whichisdescribedbyYang[18]fornumericaloptimizationproblems,isappliedtoclustering.TostudytheperformanceoftheFAtoclusteringproblems,weconsiderthestandardbenchmarkproblems(13typicaltestdatabases)thatareavailableintheliterature[9,14].TheperformanceoftheFAalgorithmonclusteringiscomparedwiththeresultsofothernatureinspiredtechniques—ArtificialBeeColony(ABC)[19]andParticleSwarmIntelligence(PSO)[20]algorithmonthesametestdatasets[9,14].TheFA,ABCandPSOalgorithmsareinthesameclassofpopulation-based,natureinspiredoptimizationtechniques.Hence,wecomparetheperformanceoftheFAalgorithmwithABCandPSOalgorithms.

2210-6502/$–seefrontmatterCrownCopyright©2011PublishedbyElsevierLtd.Allrightsreserved.doi:10.1016/j.swevo.2011.06.003