web数据挖掘__3监督学习1

Chapter3:SupervisedLearningRoadMapBasicconceptsDecisiontreeinductionEvaluationofclassifiersClassificationusingassociationrulesNaïveBayesianclassificationNaïveBayesfortextclassificationSupportvectormachinesK-nearestneighborEnsemblemethods:BaggingandBoostingSummary2AnexampleapplicationAnemergencyroominahospitalmeasures17variables(e.g.,bloodpressure,age,etc)ofnewlyadmittedpatients.Adecisionisneeded:whethertoputanewpatientinanintensive-careunit.DuetothehighcostofICU,thosepatientswhomaysurvivelessthanamontharegivenhigherpriority.Problem:topredicthigh-riskpatientsanddiscriminatethemfromlow-riskpatients.3AnotherapplicationAcreditcardcompanyreceivesthousandsofapplicationsfornewcards.Eachapplicationcontainsinformationaboutanapplicant,ageMaritalstatusannualsalaryoutstandingdebtscreditratingetc.Problem:todecidewhetheranapplicationshouldapproved,ortoclassifyapplicationsintotwocategories,approvedandnotapproved.4MachinelearningandourfocusLikehumanlearningfrompastexperiences.Acomputerdoesnothave“experiences”.Acomputersystemlearnsfromdata,whichrepresentsome“pastexperiences”ofanapplicationdomain.Ourfocus:learnatargetfunctionthatcanbeusedtopredictthevaluesofadiscreteclassattribute,e.g.,approveornot-approved,andhigh-riskorlowrisk.Thetaskiscommonlycalled:Supervisedlearning,classification,orinductivelearning.5ThedataandthegoalData:Asetofdatarecords(alsocalledexamples,instancesorcases)describedbykattributes:A1,A2,…Ak.aclass:Eachexampleislabelledwithapre-definedclass.Goal:Tolearnaclassificationmodelfromthedatathatcanbeusedtopredicttheclassesofnew(future,ortest)cases/instances.6Anexample:data(loanapplication)Approvedornot7Anexample:thelearningtaskLearnaclassificationmodelfromthedataUsethemodeltoclassifyfutureloanapplicationsintoYes(approved)andNo(notapproved)Whatistheclassforfollowingcase/instance?8Supervisedvs.unsupervisedLearningSupervisedlearning:classificationisseenassupervisedlearningfromexamples.Supervision:Thedata(observations,measurements,etc.)arelabeledwithpre-definedclasses.Itislikethata“teacher”givestheclasses(supervision).Testdataareclassifiedintotheseclassestoo.Unsupervisedlearning(clustering)ClasslabelsofthedataareunknownGivenasetofdata,thetaskistoestablishtheexistenceofclassesorclustersinthedata9Supervisedlearningprocess:twostepsLearning(training):LearnamodelusingthetrainingdataTesting:Testthemodelusingunseentestdatatoassessthemodelaccuracy,casestestofnumberTotaltionsclassificacorrectofNumberAccuracy10Whatdowemeanbylearning?GivenadatasetD,ataskT,andaperformancemeasureM,acomputersystemissaidtolearnfromDtoperformthetaskTifafterlearningthesystem’sperformanceonTimprovesasmeasuredbyM.Inotherwords,thelearnedmodelhelpsthesystemtoperformTbetterascomparedtonolearning.11AnexampleData:LoanapplicationdataTask:Predictwhetheraloanshouldbeapprovedornot.Performancemeasure:accuracy.Nolearning:classifyallfutureapplications(testdata)tothemajorityclass(i.e.,Yes):Accuracy=9/15=60%.Wecandobetterthan60%withlearning.12FundamentalassumptionoflearningAssumption:Thedistributionoftrainingexamplesisidenticaltothedistributionoftestexamples(includingfutureunseenexamples).Inpractice,thisassumptionisoftenviolatedtocertaindegree.Strongviolationswillclearlyresultinpoorclassificationaccuracy.Toachievegoodaccuracyonthetestdata,trainingexamplesmustbesufficientlyrepresentativeofthetestdata.13RoadMapBasicconceptsDecisiontreeinductionEvaluationofclassifiersClassificationusingassociationrulesNaïveBayesianclassificationNaïveBayesfortextclassificationSupportvectormachinesK-nearestneighborEnsemblemethods:BaggingandBoostingSummary14IntroductionDecisiontreelearningisoneofthemostwidelyusedtechniquesforclassification.Itsclassificationaccuracyiscompetitivewithothermethods,anditisveryefficient.Theclassificationmodelisatree,calleddecisiontree.C4.5byRossQuinlanisperhapsthebestknownsystem.ItcanbedownloadedfromtheWeb.15Theloandata(reproduced)Approvedornot16AdecisiontreefromtheloandataDecisionnodesandleafnodes(classes)17UsethedecisiontreeNo18Isthedecisiontreeunique?No.Hereisasimplertree.Wewantsmallertreeandaccuratetree.Easytounderstandandperformbetter.FindingthebesttreeisNP-hard.Allcurrenttreebuildingalgorithmsareheuristicalgorithms19FromadecisiontreetoasetofrulesAdecisiontreecanbeconvertedtoasetofrulesEachpathfromtheroottoaleafisarule.20AlgorithmfordecisiontreelearningBasicalgorithm(agreedydivide-and-conqueralgorithm)Assumeattributesarecategoricalnow(continuousattributescanbehandledtoo)Treeisconstructedinatop-downrecursivemannerAtstart,allthetrainingexamplesareattherootExamplesarepartitionedrecursivelybasedonselectedattributesAttributesareselectedonthebasisofanimpurityfunction(e.g.,informationgain)ConditionsforstoppingpartitioningAllexamplesforagivennodebelongtothesameclassTherearenoremainingattributesforfurtherpartitioning–majorityclassistheleafTherearenoexamplesleft21Decisiontreelearningalgorithm22ChooseanattributetopartitiondataThekeytobuildingadecisiontree