资源描述:
《[推荐]决策树生成原理.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、决策树生成原理AbstractThispaperdetailstheID3classificationalgorithm.Verysimply,ID3buildsadecisiontreefromafixedsetofexamples.Theresultingtreeisusedtoclassifyfuturesamples.Theexamplehasseveralattributesandbelongstoaclass(likeyesorno).Theleafnodesofthedecisiont
2、reecontaintheclassnamewhereasanon-leafnodeisadecisionnode・Thedecisionnodeisanattributetestwitheachbranch(toanotherdecisiontree)beingapossiblevalueoftheattribute.ID3usesinformationgaintohelpitdecidewhichattributegoesintoadecisionnode・Theadvantageoflearn
3、ingadecisiontreeisthataprogram,ratherthanaknowledgeengineer,elicitsknowledgefromanexpert・IntroductionJ.RossQuinlanoriginallydevelopedID3attheUniversityofSydney・HefirstpresentedID3in1975inabook,MachineLearning,vol.1,no.1.ID3isbasedofftheConceptLearningS
4、ystem(CLS)algorithm.ThebasicCLSalgorithmoverasetoftraininginstancesC:Step1:IfallinstancesinCarcpositive,thencreateYESnodeandhalt.IfallinstancesinCarenegative,createaNOnodeandhalt.Otherwiseselectafeature,Fwithvaluesvl,vnandcreateadecisionnode・Step2:Part
5、itionthetraininginstancesinCintosubsetsCl,C2,…,CnaccordingtothevaluesofV.Step3:applythealgorithmrecursivelytoeachofthesetsCi.Note,thetrainer(theexpert)decideswhichfeaturetoselect.ID3improvesonCLSbyaddingafeatureselectionheuristic・ID3searchesthroughthea
6、ttributesofthetraininginstancesandextractstheattributethatbestseparatesthegivenexamples・IftheattributeperfectlyclassifiesthetrainingsetsthenID3stops;otherwiseitrecursivelyoperatesonthen(wheren=numberofpossiblevaluesofanattribute)partitionedsubsetstoget
7、their”best”attribute.Thealgorithmusesagreedysearch,thatis,itpicksthebestattributeandneverlooksbacktoreconsiderearlierchoices・DiscussionID3isanonincrementalalgorithm,meaningitderivesitsclassesfromafixedsetoftraininginstances-Anincrementalalgorithmrevise
8、sthecurrentconceptdefinition,ifnecessary,withanewsample・Theclassescreatedby1D3areinductive,thatis,givenasmallsetoftraininginstances,thespecificclassescreatedbyID3areexpectedtoworkforallfutureinstances・Thedistributionoftheunknownsmustbet