Feature selection for classification

IntelligentDataAnalysis1(1997)131–/locate/idaFeatureSelectionforClassifi1,2DepartmentofInformationSystems&ComputerScience,NationalUniversityofSingapore,Singapore119260Received24January1997;revised3March1997;accepted21March1997AbstractFeatureselectionecreationofhugedatabasesandtheconsequentrequirementsforgoodmachinelearningtechniques,rveyisacomprehensiveoverviewofmanyexistingmethodsfromthe1970’tifiesfourstepsofatypicalfeatureselectionmethod,andcategorizesthedifferentexistingmethodsintermsofgenerationproceduresandevaluationfunctions,andrevealshithertounatentativemethodsarechosarinesforapplyingfeaturesrveyidentifiesthefutureresearchareasinfeatureselection,introducesnewcomerstothisfield,andpavesthewayforpractitionerswhosearchforsuitablemethodsforsolvingdomain-specificreal-worldapplications.(IntelligentDataAnalysis,Vol.1,no.3,http:/locate/ida)©ds:Featureselection;Classification;uctionThemajorityofreal-worldclassificationproblemsrequiresupervisedlearningwheretheunderlyingclassprobabilitiesandclass-conditionalprobabilitiesareunknown,-worldsituations,ore,unatelymanyoftheseareeitherpartiallyorcompletelyirrelevant/antfeatureisneitherirrelevantnorredundanttothetargetconcept;anirrelevantfeaturedoesnotaffectthetargetconceptinanyway,andaredundantfeaturedoesnotaddanythingnewtothetargetconcept[21].Inmanyapplications,thesizeofadatasetissolargethngthenumberofirrelevant/redundantfeaturesdrasticallyreducestherunningtimeofalearning1E-mail:manoranj@.2E-mail:liuh@.1088-467X/97/$17.00©:S1088-467X(97)00008-5

,/IntelligentDataAnalysis1(1997)131–lpsingettingabetterinsightintotheunderlyingconceptofareal-worldclassificationproblem[23,24].Featureselectionmeteselectionisdefixpected,manyofthosearesimilarinintuitionand/lowingliststhosethatareconceptuallydifferentandcoverarangeofdefized:findtheminimallysizedfeaturesubsetthatisnecessaryandsufficienttothetargetconcept[22].cal:selectasubsetofMfeaturesfromasetofNfeatures,M

,/IntelligentDataAnalysis1(1997)131–tasuitablestoppingcriterionthefeatureseletionproceduresandevaluationfunctionscaninflngcriteriabasedonagenerationprocedureinclude:(i)whetherapredefinednumberoffeaturesareselected,and(ii)whetherapredefingcriteriabasedonanevaluationfunctioncanbe:(i)whetheraddition(ordeletion)ofanyfeaturedoesnotproduceabettersubset;and(ii)whpcontinuesuntilsomestoppingcriterionissatisfitureselectionprocesshremanyvariationstothisthree-stepfeatureselectionprocess,idationprocedureisnotapartofthefeatureselectionprocessitself,butafeatureselectionmethod(inpractice)stotestthevalidityoftheselectedsubsetbycarryingoutdifferenttests,andcomparingtheresultswithpreviouslyestablishedresults,orwiththeresultsofcompetingfeatureselectionmethodsusingartificialdatasets,real-worlddatasets,avebeenquiteafewattempentamongtheseareDoak’s[13]andSiedleckiandSklansky’s[46]ckiandSklanskydiscussedtheevolutionoffeatureselectionmethodsandgroupedthemethodsintopast,present,ainfocuswasthebranchandboundmethods[34]anditsvariants,[16].urveywaspublishedintheyear1987,andsincethenmanynewandeffi,Focus[2],Relief[22],LVF[28]).DoakfollowedasimilarapproachtoSiedleckiandSklansky’ssurveyandgroupedthedifferentsearchalgorithmsandevaluationfunctionsusedinfeatureselectionmethodsindependently,andranexperimenarticle,asurveyisconductedforfeatureselectionmethodsstartingfromtheearly1970’s[33]tothemostrecentmethods[28].Inthenextsection,thetwomajorstepsoffeatureselection(generationprocedureandevaluationfunction)aredividedintodifferentgroups,and32differentfeatureselectionmethodsarecategorizedbasedonthetypeofgenerationprocedureandevaluationfunctionthatisused.

,/IntelligentDataAnalysis1(1997)131–156Thisframeworkhelpsinfindingtheuneion3webrieflydiscussthemethodsundereachcategory,andselectn4describesanempiricalcomparisonoftherepresentativemethodsusingthreeartificialdatasetssuitablychosentohighlighttheirbenefin5consistsofdiscussionsonvariousdatasetcharacteristicsthatinfluencethechoiceofasuitablefeatureselectionmethod,andsomeguidelines,regardinghowtochooseafeatureselectionmethodforanapplicationathand,aregivenbperconcludesinSection6withfurtherdiscussionsonfutureresearchbasedonthefiectiveisthatthisarticlewillassistinfifFeatureSelectionMethodsInthissectionwecategorizethetwomajorstepsoffeatureselection:fereworkispresentedinwhichatotalof32methodsaregroupedbasetionProceduresIftheoriginalfeaturesetcontainsNnumberoffeatures,redifferentapproachesforsolvingthisproblem,namely:complete,heuristic,teThisgenerationproceduredoesacompler,Schlimmer[43]arguesthat“justbecausethesearchmustbecompletedoesnotmeanthatitmustbeexhaustive.”Differentheuristicfunctionsareusedtoreducethesearchwithoutjeopardizingthechancesoffi,althoughtheorderofthesearchspaceisO(2N),imalityofthefeaturesubset,accordingtotheevaluationfunction,ackingcanbedoneusingvarioustechniques,suchas:branchandbound,bestfirstsearch,ticIneachiterationofthisgenerationprocedure,allremainingfeaturesyettobeselected(rejected)areconsideredforselection(rejection).Therearemanyvariationstothissimpleprocess,butgenerationofsubsetsisbasicallyincremental(eitherincreasingordecreasing).TheorderofthesearchspaceisO(N2)orless;someexceptionsareRelief[22],DTM[9]roceduresareverysimpletoimplementandveryfastinproducingresults,bThisgenerationprocedureisrathernewighthesearchspaceisO(2N),butthesemethodstypicallysearchfewernumberof

,/IntelligentDataAnalysis1(1997)131–mentofsuitabletionFunct,anoptimalsubsetchosenusingoneevaluationfunctionmaynotbethesameasthatwhichusesanotherevaluationfunction).Typically,anevaluationfunctiontriestomeasurethediscriminatiny[26],filterandwrapper)basedontheirdependenceontheinductivealgorithmthatwillfimethodsareindependentoftheinductivealgorithm,where-Bassat[4]groupedtheevaluationfunctionsexistinguntil1982intothreecategories:informationoruncertaintymeasures,distancemeasures,anddependencemeasures,andsuggestedthatthedependencemeasurescanbedividedbetweenthefiotconsideredtheclassificationerrorrateasanevaluationfunction,[13]dividedtheevaluationfunctionsintothreecategories:dataintrinsicmeasures,classificationerrorrate,andestimatedorincrementalerrorrate,aintrinsiccategoryincludesdistance,entropy,eringthesedivisionsandthelatestdevelopments,wedividetheevaluationfunctionsintofivecategories:distance,information(oruncertainty),dependence,consistency,andclassifiollowingsubsectionswebrieflceMeasuresItisalsoknownasseparability,divergence,o-classproblem,afeatureXispreferredtoanotherfeatureYifXinducesagreaterdifferencebetweenthetwo-classconditionalprobabilitiesthanY;ifthedifferenceiszero,ationMeasurormationgainfromafeatureXisdefinedasthedifferenceeXispreferredtofeatur,entropymeasure)[4].enceMeasuresDependencemeasuresorcorrelationmeasuresqualifficientisaclassicaldependencemeasureandcanbeusedtofiorrelationoffeatureXwithclassCishigherthanthecorrelationoffeatureYwithC,tvariationofthisistodeterminethedependenceofafeatureonotherfeatures;luationfunctionsbasedondependencemeasurescanbedividedbetweendistanceandinformation

,/IntelligentDataAnalysis1(1997)131–156Table1AComparisonofEvaluationFunctionsEvaluationFunctionDistanceMeasureInformationMeasureDependenceMeasureConsistencyMeasureClassifierErrorRateGeneralityYesYesYesYesNoTimeComplexityLowLowLowModerateHighAccuracy––––,thesearestillkeptasaseparatecategory,becauseconceptually,theyrepresentadifferentviewpoint[4].MoreabouttheabovethreemeasurescanbefoundinBen-Basset’s[4]tencyrecharacteristicallydifferentfromothermeasures,becauseoftheirheavyrelianceonthetrainingdatasetandtheuseoftheMin-Featuresbiasinselectingasubsetoffeatures[3].Min-Featuresbiasprefersconsistenthypothesesdefieasuresfindouttheminimallysizedsubsetthatsatisfiestheacceptableinconsistencyrate,fierErrorRateMeasuresThemethodsusingthistypeofevaluationfunctionarecalled“wrappermethods”,(i.e.,theclassifieristheevaluationfunction).Asthefeaturesareselectedusingtheclassifierthatlateronusestheseselectedfeaturesinpredictingtheclasslabelsofunseeninstances,theaccuracylevelisveryhighalthoughcomputationallyquitecostly[21].Table1showsacomparisonofvariousevferentparametersusedforthecomparisonare:lity:howsuitableistheselectedsubsetfordifferentclassifiers(notjustforoneclassifier);mplexity:timetakenforselectingthesubsetoffeatures;cy:‘–’inthelastcolumnmeansthatnothingcan‘classifiererrorrate,’theaccuracyofallotherevaluationfunctionsdependsonthedatasetandtheclassifier(forclassificationafterfeatureselection),themoretimespent,thehighertheaccuracy).Thetablealsotellsuswhichmeasureshouldbeusedunderdifferentcircumstances,forexample,withtimeconstraints,givenseveralclassifierstochoosefrom,classifimeworkInthissubsection,westionproceduresandevaluationfunctionsareconsideredastwodimensions,andeachmethodis

,/IntelligentDataAnalysis1(1997)131–156Table2TwoDimensionalCategorizationofFeatureSelectionMethodsEvaluationMeasuresDistanceMeasureHeuristicI—Sec3.1ReliefRelief-FSege84GenerationCompleteII—Sec3.2BranchandBoundBFFBobr88V—Sec3.4MDLMVIIIXI—Sec3.6FocusSch193MIFES-1XIV—Sec3.8Ichi-Skla84aIchi-Skla84bAMB&BBSIIIRandom137InformationMeasureDependencyMeasureConsistencyMeasureClassifierErrorRateIV—Sec3.3DTMKoll-Saha96VII—Sec3.5POE1ACCPRESETXXII—Sec3.8SBSSFSSBS-SLASHPQSSBDSMoor-Lee94RCQuei-Gels84VIIXXII—Sec3.7LVFXV—Sec3.8LVWGASARGSSRMHC-PF1groupeddnowledge,,wehavechosenatotalof32methodsfromtheliterature,andthenthesearegroupedaccordingtothecombinationofgenerationprocedureandevaluationfunctionused(seeTable2).Adistinctachievementofthisframeworkisthefindingofanumberofcombinationsofgenerationprocedureandevaluationfunction(theemptyboxesinthetable)thatdonotappearinanyexistingmethodyet(tothebestofourknowledge).Intheframework,acolumnstandsforatypignmentofevaluationfunctionswithinthecategoriesmaybeequivocal,becauseseveralevaluationfunctionsmaybeplacedindifferentcategorieswhenconsideringthemindifferentperspectives,andoneevaluationfunctionmaybeobtainedasamathematicaltransformationofanotherevaluationfunction[4].exttwosectionsweexplaineachcategoryandmethods,andchooseamethodineachcategory,foradetaileddiscussionusingpseudocodeandamini-dataset(Section3),andforanempiricalcomparison(Section4).,5typesofevaluationfunctionsand3typesofgenerationprocedures)combinationsofgenerationprocedures,section,wediscusseachcategory,bybrieflydescribingthemethodsunderit,andthen,ainitindetaihodsinthelastrowrepresentthe“wrapper”methods,wheretheevaluationfunctionisthe“classifiererrorrate”.Atypicalwrappermethodcanusedifferent

,/IntelligentDataAnalysis1(1997)131–156Table3SixteenInstancesofCorrAL#12345678A000000000A100001111B000110011B101010101I01000110C11101100Class00010001#916A011111111A100001111B000110011B101010101I11000010C10100100Class00011111kindsofclassifiersforevaluation;hencenorepresendtheyarediscussedbriefltotypicaldatasetusedforhand-runoftherepresentativemethodsisshowninTable3whichconsistsof16instances(originally32instances)ni-datasethasbinaryclasses,andsixbooleanfeatures(A0,A1,B0,B1,I,C)wherefeatureIisirrelevant,featureCiscorrelatedtotheclasslabel75%ofthetime,andtheotherfourfeaturesarerelevanttothebooleantargetconcept:(A0QA1)∼(B0QB1).Inallthepseudocodes,Ddenotesthetrainingset,Sistheoriginalfeatureset,Nisthenumberoffeatures,Tistheselectedsubset,andMisthenumberofselected(orrequired)ryI:Generation—Heuristic,Evaluation—escriptionofVariousMethodsAsseenfromTable2,themostprominentmethodinthiscategoryisRelief[22].Wefirstdiscueatureweight-basedalgorithminspiredbyinstance-basedlearningalgorithms([1,8]).Fromthesetoftraininginstances,itfirstchoosesasampleofinstances,itfirstchoosesasampleofinstances;theusermustprovidethenumberofinstances(NoSample)randomlypicksthissampleofinstances,andforeachinstanceinitfitistheinstancehavingminimumEuclideandistanceamongallinstancesofthesameclassasthatofthechoseninstance;nearMissistheinstancetestheweightsofthefeaturesthatareinitializedtozerointhebeginningbasedonanintuitiveideathatafeatureismorerelevantifitdistinguishesbetweenaninstanceanditsnearMiss,xhaustingallinstancesinthesample,resholdcanbeautomaticallyevaluatedusingafunctionthatusesthenumberofinstancesinthesample;itcanalsobedeterminedbyinspection(allfeatureswithpositiveweightsareselected).Reliefworksfornoisyandcorrelatedfeatures,orlimitationisthatitdoesnothelpwithredundant

,/IntelligentDataAnalysis1(1997)131–esand,hence,gennbeovercomebyasubseqmitationisovercomebyRelief-F[25]firlimitationisthattheusermayfinddiffiegen’s[44]methodusesanevaluationfunctionthatminimizesthesumofastatisticaldiscrepancymeasureandthefeaturecomplexitymeasure(inbits).Itfindsthefirstfeaturethatbestdistinguishestheclasses,anditerativelylooksforadditionalfeatureswhichincombi-RunofCorrALDataset(seeFigure2)ssumeinstance#,[0,1,0,0,0,1]ischosen).Itfindsthenferencebetweentwodichoseninstance#5,theinstance#1isthenearHit(Difference51),andinstance#13and#14arethenearMiss(difference52).Letuschooseinstance#,iteratedNoSampletimesspecifiy,theweightsarenegativeforirrelevantfeatures,rALdatasetisselects{A0,B0,B1,C}(moreaboutthisinSection4.3).ryII:Generation—Complete,Evaluation—escriptionofVariousMethodsThiscombinationisfoundinoldmethodssuchasbranchandbound[34].Othermethodsinthiscategoryarevariationsofbranchandbound(B&B)methodconsideringthegenerationprocedureused(BFF[50]),ortheevaluationfunctionused(Bobrowski’smethod[5]).Wefirstdiscussthebranchandboundmethod,followedbyabriefdiscussionoftheothertwomethods.

,/IntelligentDataAnalysis1(1997)131–156NarendraandFukunagahavedefinedfeatureselectioninaclassicalway(seedefinition2inSection1),asubsetoffeaturesshouldnotbebetterthananylargersetthatcontainsthesubset).Thisdefinitionhasaseveredrawbackforreal-worldproblemsbecasdefinitioncanbeslightlymodifiedtomakeitapplicableforgeneralproblemsaswell,bysayingthatB&Battemptstosatisfytwocriteria:(i)theselectedsubsetbeassmallaspossible;and(ii)aboundbeplacedonthevaluecalculatedbytheevaluationfunction[13].Asperthismodification,B&Bstartssearchinvaluationfunctionobeysthemonotonicityprinciple,anysub,allsubsetsofitarediscardedfromthesearchspace).Evaluationfunctionsgenerallyusedare:Mahalanobisdistance[15],thediscriminantfunction,theFishercriterion,theBhattacharyadistance,andthedivergence[34].Xu,Yan,andChang[50]proposedasimilaralgorithm(BFF),wherethesearchprocedureismodifiedtosolvetheproblemofsearchinganoptimalpathinaweightedtreewiththeinformedbestfirstsearchstrategyinartifigorithmguaranteesthebestglobalorsubsetwithoutexhaustiveenumeration,ski[5]provesthatthehomogeneitycoefficientf∗Ikcanbeusedinmeasuringthedegreeoflineardependenceamongsomemeasurements,andshowsthatitisappl,ifS1,S2thenf∗Ik(S1)>f∗Ik(S2)).Hence,thiscanbesuitablyconvertedtoafeatureselectionmethodbyimplementingitasanevaluationfunctionforbranchandboundwithbacktrackingorabetterfitthatanevaluationfunctionmustbemonotonictobeapplicabletothesemethods,oblemispartiallysolvedbyrelaxingthemonotonicitycriterionandintroducingtheapproximatemonotonicityconcept[16].-runofCorrALDataset(seeFigure3)orithmneedsinputoftherequirednumberoffeatures(M)anditattemptstofiandbound.

,/IntelligentDataAnalysis1(1997)131–ontreemethod(DTM).nswiththefullsetoffeaturesS0,removesonefeaturefromSjˆ2inturntogeneratesubsetslll1lSj,wherelisthecurrentlevelandjspecifi(Sj).U(Sjˆ2),Sjstopsgrowing(itsbranchispruned),otherwise,,heCorrALdataset,Missetto4,thensubset(A0,A1,B0,I)ryIV:Generation—Heuristic,Evaluation—escriptionofVariousMethodsWehavefoundtwomethodsunderthiscategory:decisiontreemethod(DTM)[9],andKollerandSahami’s[24]methodfeatureselectionisusedinanapplicationonnaturallanguageprocessing.C4.5[39]isrunoverthetrainingset,rwords,theunionofthesubsetsoffeatures,appearinginthepathstoanyleafnodeintheprunedtree,ondmethod,whichisveryrecent,isbasedontheintuitionthatanyfeature,givenlittleornoadditionalinformationbeyondthatsubsumedbytheremainingfeatures,iseitherirrelevantorredundant,izethis,KollerandSahamitrytoapproximatetheMarkovblanketwhereasubsetTisaMarkovblanketforfeaturefiif,givenT,fiisconditionallyindependentbothoftheclasslabelandofallfeaturesnotinT(includingfiitself).TheimplementationoftheMarkovblanketissuboptimalinmanyways,-RunofCorrALDataset(seeFigure3)C4.5usesaninformation-basedheuristic,asimpleformofwhichfortwoclassproblem(asourexample)is−ppnnI(p,n)=log2−log2,p+np+np+np+nwherepisthenumberofinstancthatusinganattributeF1astherootinthetreewillpartitionthetrainingsetintoT0andT1(becauseeachfeaturetakesbinaryvaluesonly).EntropyoffeatureF1isp0+n0p1+n1E(F1)=I(p0,n0)+I(p1,n1).p+np+nConsideringtheCorrALdataset,kesvalue‘0’,thenoneinstanceispositive(class51)andseveninstancesarenegative(class50,andforvalue‘1’,sixinstancesarepositive(class51)andtwoarenegative(class50).Hence

,/IntelligentDataAnalysis1(1997)131–1561+76+2I(1,7)+I(6,2)thisvalueisminimumamongallfeatures,ginaltrainingsetofsixteeninstancesisdividedintotwonodes,setwonodes,againfeatureshavingtheleastentropyareselected,ocesshaltswheneachpartitioncontainsinstancesofasingleclass,isiontreeconstructed,thusisprunedbasicallytoavoidover-fi,A0,A1,B0,B1,C).E(C)=ryV:Generation—Complete,Evaluation—InformationUnderthiscategorywefoundMinimumDescriptionLengthMethod(MDLM)[45].Inthismethod,theauthorshaveattemptedtoeliminatealluseless(irrelevantand/orredundant)ingtotheauthors,ifthefeaturesinasubsetVcanbeexpressedasafixednon-class-dependentfunctionFofthefeaturesinanothersubsetU,thenoncethevaluesofthefeaturesinsubsetUareknown,tureselection,UandVtogeethis,theauthorsusetheminimumdescriptionlengthcriterion(MDLC)introducedbyRissanen[40].Theyformulatedanexpressionthatcanbeinterpretedasthenumberofbitsrequiredtotransmittheclassesoftheinstances,theoptimalparameters,theusefulfeatures,and(finally)orithmexhaustivelysearchesallthepossiblesubsets(2N)thodcanfi-Gaussiancases,itmaynotbeabletofindtheusefulfeatures(moreaboutthisinSection4.3).-RunofCorrALDatasetAsseeninFigure5,MDLMisbasicallytheevaluationofanequationthatatethecovariancematriceinethedeterminantsofthesub-matricesDL(i)andDLforequationasshowninFigure5,andfiCorrALdatasetthechosenfeaturesubsetis{C}ryVII:Generation—Heuristic,Evaluation—escriptionofVariousMethodsWefoundPOE1ACC(ProbabilityofERROR&AverageCorrelationCoefficient)method[33]andPRESET[31]asseventechniquesoffeatureselectionarepresentedinPOE1ACC,,seventh)method,method,thefirstfeatureselectedisthefeaturewiththesmallestprobabilityoferror(Pe).ThenextfeatureselectedisthefeaturethatproducestheminimumweightedsumofPeandaveragecorrelationcoefficient(ACC),hemeanofthecorrelationcoefficientsofthodcanrankallthefeaturesbasedon

,/IntelligentDataAnalysis1(1997)131–mdescriptionlengthmethod(MDLM).+ghtedsum,andarequirednumberoffeatures(M)usestheconceptofroughset;itfirstfi,areductRofasetPclassifiesinstancesequallywellasPdoes)ranksthefeaturesbasedontheirsignifinificanceofafeatureisameasureexpressinghowimportantafeatureisregardingclassifi-RunofCorrALDataset(seeFigure6)ThefirstfeaturechosenisthefeaturehavingminimumPe,andineachiterationthereafter,thefeaturehavingminimumw1(Pe)1w2(ACC)xperiments,weconsiderw1tobe0.1andw2tobe0.9(authorssuggestthesevaluesfortheircasestudy).TocalculatePe,mini-dataset,itis9/16forclass0and7/,foreachfeature,findthatforclasslabel0,theclass-conditionalprobabilityoffeatureChavingthevalue0is2/9andthatofvalue1is7/9,andforclasslabel1,theclass-conditionalprobabilityoffeatureChavingthevalue0is6/7andthatofvalue1is1/

,/IntelligentDataAnalysis1(1997)131–,featureCtakingvalue0),wefindouttheclasslabelfortheproductofaprioriclassprobabilitatureCtakesthevalue0,thepredictionisclass1,andwhenfeatureCtakesvalue1,instances,wecounteChas3/16fractionofmismatches(Pe).Infact,amongallfeatures,ChastheleastPeandhence,isselectedasthefiecondstep,correlationsofallremainingfeatures(A0,A1,B0,B1,I)heexpressionw1(Pe)1w2(ACC)wefindthatfeatureA0hastheleastvalueamongthefi(requirednumber)is4,thensubset(C,A0,B0,I)ryXI:Generation—Complete,Evaluation—escriptionofVariousMeussFocus[2],andSchlimmer’s[43]method,andMIFES1[35],andselectFocusasthemplementstheMin-Featuresbiasthatprefersconsistenthypothesesdefiimplestimplementation,itdoesabreadth-firstsearchandchecklyspeaking,Focusisunabletohandlenoise,butasimplemodificationthatallowsacertainpercentageofinconsistencywillenableittofimer’smethodusesasystematicenumerationschemeasgeneraturisticfunctionisareliabilitymeasure,basedontheintuitionthattheprobabilitythataninconsistencywillbeobserved,isproportionaltothepercentageofvaluesthaesentsthesetofinstancesintheformofamatrix1,eachelementofwhichstandsforauniquecombinationofapositiveinstance(class51)andanegativeinstance(class50).AfeaturefissaidtocoveranelementofthematrixifitassumesoppositevaluesfchesforacoverwithN21featuresstartingfromonewithallNfeatures,-RunofCorrALDataset(seeFigure7)AsFocususesbreadth-firstgenerationprocedure,itfi,{A0},{A1},{B0},{B1},{I},{C}),followedbyallsubsetsofsizetwo,hsubsetgenerated,thus,itcheckswhetherthereareatleasttwoinstancesinthedatasethavingeq,inconsistency).Ifsuchacasearises,itrejectsthesubsetsayinginconsistent,ntinuesuntilitfi,allpossiblesubsetsarefoundinconsistent).Forsubset{A0},instance#,0),,0and11MIFES1canonlyhandlebinaryclassesandbooleanfeatures.

,/IntelligentDataAnalysis1(1997)131–tively).Henceitrejectsitandmovesontothenextsubset{A1}.Itevaluatesatotalof41subsets