Foundations of Machine Learning Decision TreeTop 10 algorithms in data miningC4.5K-MeansSVMAprioriEM (Maximum Likelihood)PageRankAdaBoostKNNNaïveBayesCARTMain Classification MethodsLogistic RegressionLinear Discriminant AnalysisDecision Tree InductionNearest Neighbor Bayes Classification MethodsClassification by BackpropagationSupport Vector MachinesEnsemble Methods…Illustrating Classification Task Example of a Decision Tree Another Example of Decision Tree Decision Tree Classification Task Apply Model to Test Data Decision Tree Classification Task 10Algorithm for Decision Tree InductionMany Algorithms: Hunt’s Algorithm (one of the earliest) ID3 (Iterative Dichotomiser)C4.5 CART (Classification and Regression Tree)SLIQ (Supervised Learning In Quest)SPRINT (Scalable PaRallelizable INduction of decision Trees)…… 11Algorithm for Decision Tree InductionBasic algorithm (a greedy algorithm)Tree is constructed in a top-down recursive divide-and-conquer mannerAt start, all the training examples are at the rootAttributes are categorical (if continuous-valued, they are discretized in advance)Examples are partitioned recursively based on selected attributesTest attributes are selected on the basis of a heuristic or statistical measure (e.g., information gain)Conditions for stopping partitioningAll samples for a given node belong to the same classThere are no remaining attributes for further partitioning – majority voting is employed for classifying the leafThere are no samples left…12Algorithm for Decision Tree Induction13Algorithm for Decision Tree InductionGreedy strategy Split the records based on an attribute test that optimizes certain criterion ( 根据最优划分属性进行划分 )Issues Determine how to select the best attribute? How to split to records? How to...
