������������������������ ���������� ��������������������������� ��������������������������� �������������� Jason Brownlee Master Machine Learning Algorithms Discover How They Work and Implement Them From Scratch i Master Machine Learning Algorithms ' Copyright 2016 Jason Brownlee. All Rights Reserved. Edition, v1.1 http://MachineLearningMastery.com Contents Preface iii I Introduction 1 1 Welcome 2 1.1 Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Algorithm Descriptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Book Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 What This Book is Not . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 How To Best Use this Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 II Background 6 2 How To Talk About Data in Machine Learning 7 2.1 Data As you Know It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Statistical Learning Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Computer Science Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Models and Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Algorithms Learn a Mapping From Input to Output 11 3.1 Learning a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Learning a Function To Make Predictions . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Techniques For Learning a Function . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Parametric and Nonparametric Machine Learning Algorithms 13 4.1 Parametric Machine Learning Algorithms . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Nonparametric Machine Learning Algorithms . . . . . . . . . . . . . . . . . . . 14 4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Supervised, Unsupervised and Semi-Supervised Learning 16 5.1 Supervised Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Unsupervised Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 ii iii 5.3 Semi-Supervised Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 6 The Bias-Variance Trade-Off 19 6.1 Overview of Bias and Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.2 Bias Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.3 Variance Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.4 Bias-Variance Trade-Off . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 7 Overfitting and Underfitting 22 7.1 Generalization in Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . 22 7.2 Statistical Fit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 7.3 Overfitting in Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7.4 Underfitting in Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7.5 A Good Fit in Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7.6 How To Limit Overfitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 III Linear Algorithms 25 8 Crash-Course in Spreadsheet Math 26 8.1 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 8.2 Statistical Summaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 8.3 Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 8.4 Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 8.5 More Help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 9 Gradient Descent For Machine Learning 30 9.1 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 9.2 Batch Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 9.3 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 9.4 Tips for Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 10 Linear Regression 34 10.1 Isn’t Linear Regression from Statistics? . . . . . . . . . . . . . . . . . . . . . . . 34 10.2 Many Names of Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . 34 10.3 Linear Regression Model Representation . . . . . . . . . . . . . . . . . . . . . . 35 10.4 Linear Regression Learning the Model . . . . . . . . . . . . . . . . . . . . . . . 35 10.5 Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 10.6 Making Predictions with Linear Regression . . . . . . . . . . . . . . . . . . . . . 37 10.7 Preparing Data For Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . 37 10.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 iv 11 Simple Linear Regression Tutorial 40 11.1 Tutorial Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 11.2 Simple Linear Regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 11.3 Making Predictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 11.4 Estimating Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 11.5 Shortcut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 11.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 12 Linear Regression Tutorial Using Gradient Descent 46 12.1 Tutorial Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 12.2 Stochastic Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 12.3 Simple Linear Regression with Stochastic Gradient Descent . . . . . . . . . . . . 47 12.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 13 Logistic Regression 51 13.1 Logistic Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 13.2 Representation Used for Logistic Regression . . . . . . . . . . . . . . . . . . . . 52 13.3 Logistic Regression Predicts Probabilities . . . . . . . . . . . . . . . . . . . . . . 52 13.4 Learning the Logistic Regression Model . . . . . . . . . . . . . . . . . . . . . . . 53 13.5 Making Predictions with Logistic Regression . . . . . . . . . . . . . . . . . . . . 54 13.6 Prepare Data for Logistic Regression . . . . . . . . . . . . . . . . . . . . . . . . 54 13.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 14 Logistic Regression Tutorial 56 14.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 14.2 Logistic Regression Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 14.3 Logistic Regression by Stochastic Gradient Descent . . . . . . . . . . . . . . . . 57 14.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 15 Linear Discriminant Analysis 61 15.1 Limitations of Logistic Regression . . . . . . . . . . . . . . . . . . . . . . . . . . 61 15.2 Representation of LDA Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 15.3 Learning LDA Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 15.4 Making Predictions with LDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 15.5 Preparing Data For LDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 15.6 Extensions to LDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 15.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 16 Linear Discriminant Analysis Tutorial 65 16.1 Tutorial Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 16.2 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 16.3 Learning The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 16.4 Making Predictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 16.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 v IV Nonlinear Algorithms 71 17 Classification and Regression Trees 72 17.1 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 17.2 CART Model Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 17.3 Making Predictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 17.4 Learn a CART Model From Data . . . . . . . . . . . . . . . . . . . . . . . . . . 74 17.5 Preparing Data For CART . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 17.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 18 Classification and Regression Trees Tutorial 76 18.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 18.2 Learning a CART Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 18.3 Making Predictions on Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 18.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 19 Naive Bayes 82 19.1 Quick Introduction to Bayes’ Theorem . . . . . . . . . . . . . . . . . . . . . . . 82 19.2 Naive Bayes Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 19.3 Gaussian Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 19.4 Preparing Data For Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 19.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 20 Naive Bayes Tutorial 88 20.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 20.2 Learn a Naive Bayes Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 20.3 Make Predictions with Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . 91 20.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 21 Gaussian Naive Bayes Tutorial 93 21.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 21.2 Gaussian Probability Density Function . . . . . . . . . . . . . . . . . . . . . . . 94 21.3 Learn a Gaussian Naive Bayes Model . . . . . . . . . . . . . . . . . . . . . . . . 95 21.4 Make Prediction with Gaussian Naive Bayes . . . . . . . . . . . . . . . . . . . . 96 21.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 22 K-Nearest Neighbors 98 22.1 KNN Model Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 22.2 Making Predictions with KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 22.3 Curse of Dimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 22.4 Preparing Data For KNN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 22.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 23 K-Nearest Neighbors Tutorial 102 23.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 23.2 KNN and Euclidean Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 23.3 Making Predictions with KNN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 23.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 vi 24 Learning Vector Quantization 106 24.1 LVQ Model Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 24.2 Making Predictions with an LVQ Model . . . . . . . . . . . . . . . . . . . . . . 107 24.3 Learning an LVQ Model From Data . . . . . . . . . . . . . . . . . . . . . . . . . 107 24.4 Preparing Data For LVQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 24.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 25 Learning Vector Quantization Tutorial 110 25.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 25.2 Learn the LVQ Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 25.3 Make Predictions with LVQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 25.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 26 Support Vector Machines 115 26.1 Maximal-Margin Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 26.2 Soft Margin Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 26.3 Support Vector Machines (Kernels) . . . . . . . . . . . . . . . . . . . . . . . . . 116 26.4 How to Learn a SVM Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 26.5 Preparing Data For SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 26.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 27 Support Vector Machine Tutorial 119 27.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 27.2 Training SVM With Gradient Descent . . . . . . . . . . . . . . . . . . . . . . . 120 27.3 Learn an SVM Model from Training Data . . . . . . . . . . . . . . . . . . . . . 121 27.4 Make Predictions with SVM Model . . . . . . . . . . . . . . . . . . . . . . . . . 123 27.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 V Ensemble Algorithms 125 28 Bagging and Random Forest 126 28.1 Bootstrap Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 28.2 Bootstrap Aggregation (Bagging) . . . . . . . . . . . . . . . . . . . . . . . . . . 127 28.3 Random Forest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 28.4 Estimated Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 28.5 Variable Importance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 28.6 Preparing Data For Bagged CART . . . . . . . . . . . . . . . . . . . . . . . . . 129 28.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 29 Bagged Decision Trees Tutorial 130 29.1 Tutorial Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 29.2 Learn the Bagged Decision Tree Model . . . . . . . . . . . . . . . . . . . . . . . 131 29.3 Make Predictions with Bagged Decision Trees . . . . . . . . . . . . . . . . . . . 132 29.4 Final Predictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 29.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 vii 30 Boosting and AdaBoost 136 30.1 Boosting Ensemble Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 30.2 Learning An AdaBoost Model From Data . . . . . . . . . . . . . . . . . . . . . 136 30.3 How To Train One Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 30.4 AdaBoost Ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 30.5 Making Predictions with AdaBoost . . . . . . . . . . . . . . . . . . . . . . . . . 138 30.6 Preparing Data For AdaBoost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 30.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 31 AdaBoost Tutorial 140 31.1 Classification Problem Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 31.2 Learn AdaBoost Model From Data . . . . . . . . . . . . . . . . . . . . . . . . . 141 31.3 Decision Stump: Model #1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 31.4 Decision Stump: Model #2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 31.5 Decision Stump: Model #3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 31.6 Make Predictions with AdaBoost Model . . . . . . . . . . . . . . . . . . . . . . 147 31.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 VI Conclusions 149 32 How Far You Have Come 150 33 Getting More Help 151 33.1 Machine Learning Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 33.2 Forums and Q&A Websites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 33.3 Contact the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Preface Machine learning algorithms dominate applied machine learning. Because algorithms are such a big part of machine learning you must spend time to get familiar with them and really understand how they work. I wrote this book to help you start this journey. You can describe machine learning algorithms using statistics, probability and linear algebra. The mathematical descriptions are very precise and often unambiguous. But this is not the only way to describe machine learning algorithms. Writing this book, I set out to describe machine learning algorithms for developers (like myself). As developers, we think in repeatable procedures. The best way to describe a machine learning algorithm for us is: 1. In terms of the representation used by the algorithm (the actual numbers stored in a file). 2. In terms of the abstract repeatable procedures used by the algorithm to learn a model from data and later to make predictions with the model. 3. With clear worked examples showing exactly how real numbers plug into the equations and what numbers to expect as output. This book cuts through the mathematical talk around machine learning algorithms and shows you exactly how they work so that you can implement them yourself in a spreadsheet, in code with your favorite programming language or however you like. Once you possess this intimate knowledge, it will always be with you. You can implement the algorithms again and again. More importantly, you can translate the behavior of an algorithm back to the underlying procedure and really know what is going on and how to get the most from it. This book is your tour of machine learning algorithms and I’m excited and honored to be your tour guide. Let’s dive in. Jason Brownlee Melbourne, Australia 2016 viii