Exemplar learning in fuzzy decision trees

Decision-tree algorithms provide one of the most popular methodologies for symbolic knowledge acquisition. The resulting knowledge, a symbolic decision tree along with a simple inference mechanism, has been praised for comprehensibility. The most comprehen

ExemplarLearninginFuzzyDecisionTrees

C.Z.Janikow

MathematicsandComputerScience

UniversityofMissouriSt.Louis,MO63121

Abstract

Decision-treealgorithmsprovideoneofthemostpopu-larmethodologiesforsymbolicknowledgeacquisition.Theresultingknowledge,asymbolicdecisiontreealongwithasimpleinferencemechanism,hasbeenpraisedforcompre-hensibility.Themostcomprehensibledecisiontreeshavebeendesignedforperfectsymbolicdata.Overtheyears,additionalmethodologieshavebeeninvestigatedandpro-posedtodealwithcontinuousormulti-valueddata,andwithmissingornoisyfeatures.Recently,withthegrowingpop-ularityoffuzzyrepresentation,afewresearchersindepend-entlyhaveproposedtoutilizefuzzyrepresentationinde-cisiontreestodealwithsimilarsituations.Fuzzyrepresent-ationbridgesthegapbetweensymbolicandnon-symbolicdatabylinkingqualitatitivelinguistictermswithquantitat-ivedata.Inthispaper,weoverviewourfuzzydecisiontreeandproposeafewnewinferencesbasedonexemplarlearn-ing.

1.Introduction

Withtheincreasingamountofdatareadilyavailable,automaticknowledgeacquisitioncapabilitiesarebecom-ingmoreandmoreimportant.Whenalldataelementsarepreclassi ed,noextensivedomainknowledgeisavailable,andtheobjectiveistoacquireknowledgedescribingthoseclasses(astoreasonaboutthemorsimplytoclassifyfu-turedata),theknowledgeacquisitionprocessiscalledsu-pervisedlearningfromexamples.Becausetheobjectiveistoinfernewknowledge,inductionmustbeemployed.Whenboththelanguagedescribingthetrainingdataandthatde-scribingtheresultingknowledgeusesymbolicfeatures,wespeakofsymboliclearning.

Decision-treealgorithmsprovideoneofthemostpopu-larmethodologiesforsymbolicknowledgeacquisitionfromfeature-basedexamples.Amongthem,Quinlan’sID3isthemostwidelyknown.Itwasoriginallydesignedforsymbolicdatawhenalltheneededinformationisavailable.Theac-

quiredknowledgeisexpressedwithahighlycomprehens-iblesymbolicdecisiontree(amodel),whichpairedwithasimpleinferencemechanismassignssymbolicdecisions(classassignments)tonewdata.Becauseofthenaturalin-terpretationoftheknowledge,symbolicdecisiontreescanbeeasilytranslatedtoasetofrulessuitableforuseinrule-basedsystems[10].

Analternativelearningscenariomayinvolveasimplestatisticalinferenceonthedata,orselectionofdataele-mentstobeusedinaproximitymodel.Quinlanhasrecentlyproposedtocombinestandarddecision-treereasoningwithsuchinstance-basedscenarios[9].Exemplar-basedlearn-ing[1]isadi erentcombinationofinstance-andmodel-basedlearning.There,specialexamples(exemplars)arese-lectedfromdatatobeusedwithaproximitymeasure,buttheseexamplescanalsobegeneralized.

Inreal-worldapplications,dataishardlyeverperfectlyttedtoagivenalgorithm.Thisimperfectnesscanbemani-festedinanumberofways.Symbolicinductivelearn-ingrequiressymbolicdomains,whilesomeorallattrib-utesmaybedescribedbymulti-valuedorcontinuousfea-tures.Somefeaturesmaybemissingfromdatadescriptions,andthismayhappenbothintrainingorindecision-making.Intraining,suchincompletedatacanbedisregarded,butthismayunnecessarilyoverlooksomeavailableinforma-tion.Indecision-making,adecisionmustbemadebasedonwhateverinformationisavailable(oranewtestmaybesug-gested).Datacanalsobenoisyorsimplyerroneous.Whilethelatterproblemcanbeminimized,theformermustbead-dressed,especiallyincontinuousdomainsfromsomesens-orydata.Finally,featuresmayinvolveinherentlysubjectivelinguisticterms,withoutunambiguousde nitions.

Someofsuchproblemshavebeenexploredinthecon-textofdecisiontrees,resultingintheproposalofanum-berofmethodologicaladvancements.Todealwithcontinu-ousdata,CARTalgorithmshavebeenproposed[2].Un-fortunately,thesetreessu erfromreducedcomprehensib-ility,whichisnotalwaysawelcometrade-o .Insym-bolicdecisiontreesinvolvingmulti-valuedorcontinuousdomains,ithasbeenproposedtousedomainpartitionblocks

Decision-tree algorithms provide one of the most popular methodologies for symbolic knowledge acquisition. The resulting knowledge, a symbolic decision tree along with a simple inference mechanism, has been praised for comprehensibility. The most comprehen

asfeatures.Incaseswhensuchblocksoverlap(coverings),aprobabilisticinferencecanbeused.Methodsfordeal-ingwithmissingfeaturesandnoisehavealsobeenstudied[6,8,10].

Inrecentyears,analternativerepresentationhasgrowninpopularity.Thisrepresentation,basedonfuzzysetsandusedinapproximatereasoning,isespeciallyapplicabletobridgingtheconceptualgapbetweensubjective/ambiguousfeaturesandquantitativedata[3,13].Becauseofthegrace-fulnessofgradualfuzzysetsandapproximatereasoningmethodsused,fuzzyrepresentationisalsowellsuitedfordealingwithinexactandnoisydata.Fuzzyrules,basedonfuzzysets,utilizethosequalitiesoffuzzyrepresentationinacomprehensiblestructureofrulebases.

Recently,afewresearchershaveproposedtocom-binefuzzyrepresentationwiththepopulardecisiontreeal-gorithms.Whentheobjectiveishighcomprehensibilityratherthan"best"fuzzypartitioningofthedescriptionspace,thecombinationinvolvessymbolicdecisiontrees[4,5,11].Theresultingfuzzydecisiontreesexhibithighcomprehens-ibility,yetfuzzysetsandapproximatereasoningmethodsprovidenaturalmeansfordealingwithcontinuousdomains,subjectivelinguisticterms,andnoisymeasurements.Sincemethodologiesfordealingwithmissingfeaturesarereadilyavailableinsymbolicdecisiontrees,suchcanalsobeeasilyincorporatedintothosefuzzydecisiontrees.Andsincetreescanbeinterpretedasrule-bases,fuzzydecisiontreescanbeseenasameansforlearningfuzzyrules.Thismakesfuzzydecisiontreesanattractivealternativetootherrecentlypro-posedlearningmethodsforfuzzyrules(forexample,[12]).Adecision-treelearningalgorithmhastwomajorcom-ponents:tree-buildingandinference.Ourfuzzydecisiontreeisamodi cationoftheID3algorithm,withbothcomponentsadaptingfuzzyrepresentationandapproxim-atereasonin …… 此处隐藏：23095字，全部文档内容请下载后查看。喜欢就下载吧 ……