STAT 479: Machine Learning Lecture Notes Sebastian Raschka Department of Statistics University of Wisconsin–Madison http://stat.wisc.edu/∼sraschka/teaching/stat479-fs2018/ Fall 2018 Contents 6 Decision Trees 6.1 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6.1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6.1.2 Machine Learning Categories . . . . . . . . . . . . . . . . . . . . . . . 2 6.1.3 Relationship Between Decision Trees and Rule-based Learning . . . . 2 6.2 Divide-and-Conquer and Recursion . . . . . . . . . . . . . . . . . . . . . . . . 3 6.3 General Decision Tree Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 4 6.4 Time Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6.5 ID3, C4.5, CART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6.5.1 General Differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 6.5.2 ID3 – Iterative Dichotomizer 3 . . . . . . . . . . . . . . . . . . . . . . 6 6.5.3 C4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.5.4 CART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.5.5 Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.6 Information Gain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.7 Information Theory and Entropy . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.8 Why Growing Decision Trees via Entropy or Gini Impurity instead of Misclassification Error? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.9 Gini Impurity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.10 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.10.1 Grain Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.1

… Tải file gốc để đọc toàn bộ tài liệu.