第 1 页
Lecture 06 Decision Trees STAT 479: Machine Learning, Fall 2018 Sebastian Raschka http://stat.wisc.edu/~sraschka/teaching/stat479-fs2018/ 1
第 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
第 3 页
Decision Trees as Rulesets IF _________________________ ___ ______________________ ___ ______________________ THEN ________ ___ ___________ 3
第 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
第 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
第 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
第 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
第 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
第 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
第 12 页
More formal: GenerateTree( ): if or : return Tree else: Pick best feature : at at return Node( , GenerateTree( ), GenerateTree( )) 12
第 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
第 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
第 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
第 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
第 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
第 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
第 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
第 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
评论 (0)
暂无评论。快来抢沙发吧！