Page 1
Lecture 06 Decision Trees STAT 479: Machine Learning, Fall 2018 Sebastian Raschka http://stat.wisc.edu/~sraschka/teaching/stat479-fs2018/ 1
Page 2
Decision Tree Terminology Work to do? Internal node Yes No Root node Stay in Outlook? Branch Sunny Rainy Over- cast Go to beach Go running Friends busy? Yes No Leaf node Stay in Go to movies 2
Page 3
Decision Trees as Rulesets IF _________________________ ___ ______________________ ___ ______________________ THEN ________ ___ ___________ 3
Page 4
Decision Trees and ML Categories • Supervised vs. unsupervised learning algorithm • classification vs. regression • Optimization method: ______ • Eager vs. lazy learning algorithm • Batch vs. online learning algorithm • Parametric vs. nonparametric model • Deterministic vs. stochastic 4
Page 5
Recursion / Recursive AlgorithmsDivide-and-Conquer and Recu Simple recursive algorithms to compute the length of 1 def array_len(x):some_func 2 if x == []: 3 return 0 4 else: 5 return 1 + array_len(x[1:])some_func Divide-and-conquer is a concept in computer science divide a problem into subproblems of the same type. What does this function do?Usually, divide-and-conquer can be implemented usin 5
Page 6
Divide & Conquer Algorithms 1 def quicksort(array): 2 if len(array) < 2: 3 return array 4 else: 5 pivot = array[0] 6 smaller, bigger = [], [] 7 for ele in array[1:]: 8 if ele <= pivot: 9 smaller.append(ele) 10 else: 11 bigger.append(ele) 12 return quicksort(smaller) + [pivot] + quicksort(bigger) 6
Page 7
Divide & Conquer Algorithms 1 def quicksort(array): 2 if len(array) < 2: 3 return array 4 else: 5 pivot = array[0] 6 smaller, bigger = [], [] 7 for ele in array[1:]: 8 if ele <= pivot: 9 smaller.append(ele) 10 else: 11 bigger.append(ele) 12 return quicksort(smaller) + [pivot] + quicksort(bigger) 7
Page 8
Time complexity of quicksort: _____________ ("on average") 1 def quicksort(array): 2 if len(array) < 2: 3 return array 4 else: 5 pivot = array[0] 6 smaller, bigger = [], [] 7 for ele in array[1:]: 8 if ele <= pivot: 9 smaller.append(ele) 10 else: 11 bigger.append(ele) 12 return quicksort(smaller) + [pivot] + quicksort(bigger) 8
Page 10
Time Complexity ("Big-O") Growing the tree: Tip: It can be shown that optimal split is on boundary between adjacent examples (similar feature value) with different class labels. Fayyad, Usama Mohammad. "On the induction of decision trees for multiple concept learning." (1992). 10
Page 12
More formal: GenerateTree( ): if or : return Tree else: Pick best feature : at at return Node( , GenerateTree( ), GenerateTree( )) 12
Page 13
Generic Tree Growing Algorithm 1) Pick the feature that, when parent node is split, results in the largest information gain 2) Stop if child nodes are pure or information gain <= 0 3) Go back to step 1 for each of the two child nodes 13
Page 14
Generic Tree Growing Algorithm 1) Pick the feature that, when parent node is split, results in the largest information gain 2) Stop if child nodes are pure or information gain <= 0 3) Go back to step 1 for each of the two child nodes • How make predictions of features in dataset not sufficient to make child nodes pure? ____________________________ 14
Page 15
Design choices • How to split ◦ what measurement/criterion as measure of goodness ◦ binary vs multi-category split • When to stop ◦ if leaf nodes contain only examples of the same class ◦ feature values are all the same for all examples ◦ statistical significance test 15
Page 16
ID3 -- Iterative Dichotomizer 3 • one of the earlier/earliest decision tree algorithms • Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81-106. • cannot handle numeric features • no pruning, prone to overfitting • short and wide trees (compared to CART) • maximizing information gain/minimizing entropy • discrete features, binary and multi-category features 16
Page 17
C4.5 • continuous and discrete features • Ross Quinlan 1993, Quinlan, J. R. (1993). C4. 5: Programming for machine learning. Morgan Kauffmann, 38, 48. • continuous is very expensive, because must consider all possible ranges • handles missing attributes (ignores them in gain compute) • post-pruning (bottom-up pruning) • Gain Ratio 17
Page 18
CART • Breiman, L. (1984). Classification and regression trees. Belmont, Calif: Wadsworth International Group. • continuous and discrete features • strictly binary splits (taller trees than ID3, C4.5) • binary splits can generate better trees than C4.5, but tend to be larger and harder to interpret; k-attributes has a ways to create a binary partitioning • variance reduction in regression trees • Gini impurity, twoing criteria in classification trees • cost complexity pruning 18
Page 19
Others • CHAID (CHi-squared Automatic Interaction Detector); Kass, G. V. (1980). "An exploratory technique for investigating large quantities of categorical data". Applied Statistics. 29 (2): 119– 127. • MARS (Multivariate adaptive regression splines); Friedman, J. H. (1991). "Multivariate Adaptive Regression Splines". The Annals of Statistics. 19: 1 • C5.0 (patented) • ... 19
Page 20
Finding a Decision Rule x1 x2 x3 y 6 cm 8 cm 9 cm 1 4 cm 11 cm 2 cm 0 6 cm 12 cm 4 cm 0 10 cm 9 cm 3 cm 1 5 cm 7 cm 8 cm 0 8 cm 9 cm 3 cm 1 3 cm 11 cm 5 cm 0 20
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !