Lecture 06 Decision Trees STAT 479: Machine Learning, Fall 2018 Sebastian Raschka http://stat.wisc.edu/~sraschka/teaching/stat479-fs2018/ 1 Decision Tree Terminology Internal node Work to do? Yes Root node No Stay in Outlook? Sunny Branch Rainy Overcast Go to beach Go running Friends busy? Yes Leaf node Stay in 2 No Go to movies Decision Trees as Rulesets IF _________________________ ___ ___ ______________________ THEN ________ ___ ___________ 3 ______________________ 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 Recursion / Recursive Algorithms Divide-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 5 else: 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 thisdivide-and-conquer function do? Usually, can be implemented usin 5 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 10 11 12 smaller.append(ele) else: bigger.append(ele) return quicksort(smaller) + [pivot] + quicksort(bigger) 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 10 11 12 smaller.append(ele) else: bigger.append(ele) return quicksort(smaller) + [pivot] + quicksort(bigger) 7 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 small