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)
まだコメントはありません。最初のコメントを書きましょう！