ABSTRACT Classifier Selection for Majority Voting

ClassifierSelectionforMajorityVotingDymitrRuta∗andBogdanGabrys†ABSTRACTIndividualclassificationmodelsarerecentlychallengedbycombinedpatternrecognitionsystems,whichoftenshowbetterperformance.Insuchsystemstheoptimalsetofclassifiersisfirstselectedandthencombinedbyaspecificfusionmethod.Forasmallnumberofclassifiersoptimalensemblescanbefoundexhaustively,buttheburdenofexponentialcomplexityofsuchsearchlimitsitspracticalapplicabilityforlargersystems.Asaresult,simplersearchalgorithmsand/orselectioncriteriaareneededtoreducethecomplexity.Thisworkprovidesarevisionoftheclassifierselectionmethodologyandevaluatesthepracticalapplicabilityofdiversitymeasuresinthecontextofcombiningclassifiersbymajorityvoting.Anumberofsearchalgorithmsareproposedandadjustedtoworkproperlywithanumberofselectioncriteriaincludingmajorityvotingerrorandvariousdiversitymeasures.Extensiveexperimentscarriedoutwith15classifierson27datasetsindicateinappropriatenessofdiversitymeasuresusedasselectioncriteriainfavourofthedirectcombinererrorbasedsearch.Furthermore,theresultspromptedanoveldesignofmultipleclassifiersystemsinwhichselectionandfusionarerecurrentlyappliedtoapopulationofbestcombinationsofclassifiersratherthantheindividualbest.Theimprovementofthegeneralisationperformanceofsuchsystemisdemonstratedexperimentally.KEYWORDSClassifierFusion,ClassifierSelection,Diversity,SearchAlgorithms,MajorityVoting,Generalisation1IntroductionGivenalargepoolofdifferentclassifiersthereareanumberofpossiblecombiningstrategiestofollowanditisusuallynotclearwhichonemaybetheoptimalforaparticularproblem.Thesimpleststrategycouldbe∗ComputationalIntelligenceGroup,BTExactTechnologies,OrionBuilding1stfloor,pp12,AdastralPark,MartleshamHeath,IpswichIP53RE,UK,[e-mail]†ComputationalIntelligenceResearchGroup,BournemouthUniversity,SchoolofDesign,Engineering&Computing,PooleHouse,TalbotCampus,FernBarrowPooleBH125BB,UnitedKingdom,[e-mail],bestperformingclassifieronthetrainingdataandapplyingittothepreviouslyunseenpatterns[26].Suchanapproach,althoughthesimplest,doesnotguaranteetheoptimalperformance[28].Moreover,thereisapossibilitythatatleastsomesubsetsofclassifierscouldjointlyoutperformthebestclassifierifsuitablycombined.Toensuretheoptimalperformance,amultipleclassifierdesignshouldbeabletoselectthesubsetofclassifiersthatisoptimalinthesensethatitproducesthehighestpossibleperformanceforaparticularcombiner.Ononehand,itisclearthatcombiningthesameclassifiersdoesnotcontributetoanythingbuttheincreasedcomplexityofasystem.Ontheotherhand,differentbutmuchworseperformingclassifiersareunlikelytobringanybenefitsincombinedperformance.Itisbelievedthattheoptimalcombinationsofclassifiersshouldhavegoodindividualperformancesandatthesametimesufficientlevelofdiversity[35].Inmanyrecentworksithasbeenshownhoweverthatneitherindividualperformances[27],[40]nordiversity[37],[29]ontheirownprovideareliablediagnostictoolabletodetectwhencombineroutperformstheindividualbestclassifier.AsnotedbyRogova[27],individualclassifierperformancesdonotrelatewelltocombinedperformanceastheymissouttheimportantinformationabouttheteamstrengthoftheclassifiers.Inturn,diversity,duetoproblemswithmeasuringandevenperceivingit,alsodoesnotprovideareliableselectioncriterionthatwouldbewellcorrelatedwithcombinerperformance[31].Someattemptsatincludingbothcomponentsjointlyguidingselectionprovedtobehighlycomplexwhileofferingonlyrelativelysmallimprovements[40],[30].Alittlemoresuccessfulhavebeenselectionattemptsbasedonspecificsimilaritymeasuresdevisedinconjunctionwiththecombinerforwhichtheclassifiersareselected.Thefaultmajoritypresentedin[29]orsimilarityS3hmeasurepresentedin[16]arejusttwoexamplesthathaveshownhighcorrelationwithmajorityvotingperformance.Unlikegeneralstatisticallydrivendiversitymeasures,measuresexploitingcombinerdefinitiontakeintoaccountinformationofwhatmakesaparticularcombinerworkandselectionguidedbysuchacombinernaturallyhavegreaterchancesofbeingsuccessful.Allthesefindingspointtothecombinedperformanceasarelevantselectioncriterion.Effectivelythemostreliablestrategyseemstobeevaluationofasmanydifferentdesignsaspossibleandsubsequentselectionofthebestperformingmodel.Adifficultyhoweveristhatsuchawideopenscaleofevaluationiscomputationallyintractable.Torealisethis,itissufficienttonotethatassumingachosencombiner,evaluationofallsubsetsfromanensembleofredundantclassifiersisaprocessgrowingexponentiallywiththenumberofclassifiers.Ontopofthat,forlargenumbersofclassifierstheperfor-mancebasedsearchspacebecomesincreasinglyflatwhichmakesselectionevenmoredifficult[40].Inthelightofsuchdifficulties,amodulardecompositionmodelofcombiningseemsadvisable,particularly2ifonlyonelocallybestclassifieristobeselectedforaparticularsubtaskorlocalinputsubspace.Anum-berofdynamicselectionmodels[7],[8],[10]orclusterandselectbasedapproaches[18],[24]illustratethatadvantageandinsomecasesshowevensubstantialimprovementcomparedwiththeindividualbestclassifier.However,byanalogytoredundantcombining,ingeneral,improvementmaybealsosoughtincombiningmanyclassifierswithineachsubtaskorinputsubspace,whichcom