1 00:00:07,161 --> 00:00:11,990 Let's revisit the first example of machine learning that we encountered in week one, 2 00:00:11,990 --> 00:00:13,720 k-Nearest Neighbor models. 3 00:00:15,060 --> 00:00:18,890 Those were a good starting point to continue our exploration of supervised 4 00:00:18,890 --> 00:00:21,840 learning because they're simple to understand and can be used for 5 00:00:21,840 --> 00:00:23,690 both classification and regression. 6 00:00:25,020 --> 00:00:26,882 Let's recall that, for classification, 7 00:00:26,882 --> 00:00:30,319 the k-Nearest Neighbor Classifier simply memorizes the entire training set. 8 00:00:30,319 --> 00:00:34,470 And then to classify a new instance does 3 steps. 9 00:00:35,790 --> 00:00:40,290 First, it finds the k-Nearest most similar instances to the new instance in 10 00:00:40,290 --> 00:00:40,830 the training set. 11 00:00:41,930 --> 00:00:45,210 Then it gets the labels of those training instances. 12 00:00:45,210 --> 00:00:48,740 And then it predicts the label of the new instance as a function of the nearby 13 00:00:48,740 --> 00:00:51,650 training labels typically by a simple majority vote. 14 00:00:53,170 --> 00:00:57,792 Here's how a k-Nearest Neighbor Classifier using only one nearest neighbor, that is 15 00:00:57,792 --> 00:01:02,365 with k equal to 1, makes these predictions for the simple binary synthetic dataset. 16 00:01:02,365 --> 00:01:07,240 So as you might recall from week one where we applied a nearest neighbors 17 00:01:07,240 --> 00:01:10,580 classifier to our multi-class fruit dataset. 18 00:01:10,580 --> 00:01:13,580 Here we're applying the nearest neighbors classifier 19 00:01:13,580 --> 00:01:15,800 to our simple binary classification problem. 20 00:01:15,800 --> 00:01:20,570 Where the points in class zero are labeled with yellow dots and 21 00:01:20,570 --> 00:01:23,079 the points in class one are labeled with black dots. 22 00:01:24,510 --> 00:01:29,062 And just as we did for the week one problem with fruit classification, 23 00:01:29,062 --> 00:01:32,820 here we're also showing how the entire feature space 24 00:01:34,300 --> 00:01:38,750 is broken up into different decision regions according to the predictions that 25 00:01:38,750 --> 00:01:42,860 the k-Nearest Neighbor Classifier would make at each point in the decision space. 26 00:01:42,860 --> 00:01:48,550 So for example, a point out here in the yellow region 27 00:01:48,550 --> 00:01:52,810 represents a point that the classifier would classify as class zero. 28 00:01:52,810 --> 00:01:58,560 And a point, let's say, over here, the classifier would classify as class one. 29 00:02:00,600 --> 00:02:03,110 So because this is a one nearest neighbors classifier, 30 00:02:04,600 --> 00:02:08,090 to make a classification prediction for any given query point, 31 00:02:08,090 --> 00:02:11,110 the Classifier simply looks back into its trading set. 32 00:02:11,110 --> 00:02:14,820 So these points here represent all the points on the training set. 33 00:02:14,820 --> 00:02:20,426 So for any given point, let's say here, The Classifier would 34 00:02:20,426 --> 00:02:25,031 simply find the training point that's closest, namely this one, and assign 35 00:02:25,031 --> 00:02:30,540 the predict a class to simply the class of the nearest point in the training set. 36 00:02:30,540 --> 00:02:32,710 Likewise, if we have a point over here. 37 00:02:34,680 --> 00:02:39,220 The nearest point in the training says actually this point right here that 38 00:02:39,220 --> 00:02:44,110 has a class zero label and so that point would get assigned a class zero. 39 00:02:44,110 --> 00:02:49,040 And in fact, this whole region right here represents all the points that are closer 40 00:02:49,040 --> 00:02:56,940 to the class zero training point than any of the other class one training points. 41 00:02:56,940 --> 00:03:00,630 So this whole region here represents a one nearest neighbors 42 00:03:01,780 --> 00:03:03,278 prediction of class zero. 43 00:03:03,278 --> 00:03:07,768 So the k-Nearest Neighbor's Classifier with k = 1, 44 00:03:07,768 --> 00:03:12,447 you can see that the decision boundaries that derived from 45 00:03:12,447 --> 00:03:17,140 that prediction are quite jagged and have high variance. 46 00:03:18,460 --> 00:03:21,020 This is an example of a model, classification model, 47 00:03:21,020 --> 00:03:22,760 it has high model complexity. 48 00:03:24,170 --> 00:03:27,453 And in fact, you can see that the one nearest neighbors classifier is 49 00:03:27,453 --> 00:03:29,726 over-fitting the training data in this case. 50 00:03:29,726 --> 00:03:34,737 It's trying to get correct predictions for every single training 51 00:03:34,737 --> 00:03:40,016 point while ignoring the general this trend between the two classes, 52 00:03:40,016 --> 00:03:45,652 namely that most of the yellow points are in this side of the future space and 53 00:03:45,652 --> 00:03:48,810 most of the black points are on this side. 54 00:03:50,790 --> 00:03:54,890 So the one nearest neighbor's classifier can be said to be over-fitting 55 00:03:54,890 --> 00:03:55,580 in this case. 56 00:03:57,580 --> 00:04:00,804 And here is what happens when we increase k from 1 to 11. 57 00:04:02,450 --> 00:04:07,630 Now the classifier must combine the votes of the 11 nearest points, not just 1. 58 00:04:07,630 --> 00:04:11,830 So single training data points no longer have as dramatic an influence on 59 00:04:11,830 --> 00:04:12,410 the prediction. 60 00:04:13,450 --> 00:04:18,170 The result is a much smoother decision boundary, which represents a model with 61 00:04:18,170 --> 00:04:22,170 lower model complexity where the decision boundary has much less variance. 62 00:04:23,760 --> 00:04:27,510 Actually if we increased k even higher to be the total number of points in 63 00:04:27,510 --> 00:04:31,420 the training set, the result would be a single decision region where all 64 00:04:31,420 --> 00:04:36,770 predictions would be the most frequent class in the training data. 65 00:04:36,770 --> 00:04:40,260 As we saw for the fruit data set, k-Nearest Neighbor Classifiers can be 66 00:04:40,260 --> 00:04:42,609 applied to any number of classes, not just 2. 67 00:04:44,650 --> 00:04:47,850 The code for this example in the notebook uses a special function, 68 00:04:47,850 --> 00:04:54,230 in the shared utilities library for this course, called plot_two_class_knn. 69 00:04:54,230 --> 00:04:58,230 If you run this code and compare the resulting training and test scores for 70 00:04:58,230 --> 00:05:03,240 k equals 1, 3, and 11, which are shown in the title of each plot, 71 00:05:03,240 --> 00:05:07,770 you can see the effect of model complexity on a models ability to generalize. 72 00:05:09,170 --> 00:05:12,150 In the k = 1 case, the training score is a perfect 1.0. 73 00:05:12,150 --> 00:05:16,080 But the test score is only 0.80. 74 00:05:16,080 --> 00:05:22,580 As k increases to 3, the training score drops to 0.88 but the test score rises 75 00:05:22,580 --> 00:05:27,498 slightly 2.88, indicating the model is generalizing better to new data. 76 00:05:27,498 --> 00:05:32,538 When k = 11, the training score drops a bit further to 0.81, but 77 00:05:32,538 --> 00:05:37,830 the test score even better at 0.92, indicating that this simple model 78 00:05:37,830 --> 00:05:42,878 is much more effective at ignoring minor variations in training data. 79 00:05:42,878 --> 00:05:47,402 And instead capturing the more important global trend in where the classes 80 00:05:47,402 --> 00:05:52,370 tend to be located with the best overall generalization performance as a result. 81 00:05:54,410 --> 00:05:57,740 The nearest neighbors approach isn't useful just for classification. 82 00:05:57,740 --> 00:05:59,380 You can use it for regression too. 83 00:05:59,380 --> 00:06:04,101 So here are three plots that show the same simple regression problem with one 84 00:06:04,101 --> 00:06:08,690 input feature and the corresponding target values in the training data. 85 00:06:10,650 --> 00:06:18,799 The left most plot here, this one, shows just the original training data points. 86 00:06:20,750 --> 00:06:24,010 And the middle and right plots show the predictions made by k and 87 00:06:24,010 --> 00:06:27,680 n regression algorithm, when k = 1 and k = 3. 88 00:06:27,680 --> 00:06:32,480 So in these plots, you can see the training points are actually in green. 89 00:06:32,480 --> 00:06:37,632 These green circles are the training points and the blue triangles 90 00:06:37,632 --> 00:06:44,980 are the output of the k-nearest neighbor regression for any given input value of x. 91 00:06:44,980 --> 00:06:48,680 So for example the knn regression prediction for 92 00:06:48,680 --> 00:06:53,050 this point here is this y value here. 93 00:06:54,170 --> 00:06:59,680 So how did the nearest neighbors regressor compute this value. 94 00:06:59,680 --> 00:07:02,760 Well I did it in similar way to what we saw for classification. 95 00:07:06,190 --> 00:07:11,260 So if the query point we're interested in is predicting value 96 00:07:11,260 --> 00:07:18,200 associated with this x value, we simply 97 00:07:18,200 --> 00:07:22,780 find the training point that has the X value that's closest to this query point. 98 00:07:22,780 --> 00:07:25,750 So in this case, that would be this training point. 99 00:07:25,750 --> 00:07:28,545 And because this is a one nearest neighbor problem, 100 00:07:28,545 --> 00:07:32,357 we simply take the target value associated with this training point and 101 00:07:32,357 --> 00:07:35,040 use that as the output target for the query point. 102 00:07:36,166 --> 00:07:41,129 Similarly, if this were the query point here then the nearest 103 00:07:41,129 --> 00:07:45,530 neighbor in the training set would be this point here. 104 00:07:47,220 --> 00:07:52,507 And so the output prediction for this particular X-value would be the target 105 00:07:52,507 --> 00:07:57,398 value of the nearest neighbor or this value that's just above 100. 106 00:07:57,398 --> 00:08:01,013 And so, if we do that for all these different X values, 107 00:08:01,013 --> 00:08:07,480 we'll get these different predictions using the one nearest neighbor approach. 108 00:08:07,480 --> 00:08:12,604 Similarly, if we look at the k = 3 case, where we now look at three 109 00:08:12,604 --> 00:08:18,842 nearest neighbors, let's take this example here of -1.25, let's say. 110 00:08:18,842 --> 00:08:25,080 Well, what are the three training points that have x values closest to -1.25? 111 00:08:25,080 --> 00:08:30,040 They would be this training point, that training point and this training point. 112 00:08:31,160 --> 00:08:35,740 Now with regression, what we do is instead of taking a majority vote, 113 00:08:35,740 --> 00:08:38,870 we don't have class values here as targets, we have continuous values. 114 00:08:39,880 --> 00:08:43,450 So we can average these three target values. 115 00:08:43,450 --> 00:08:46,174 And if we do that, we find that the output, 116 00:08:46,174 --> 00:08:50,264 when the query point is this X-value, is going to be the average 117 00:08:50,264 --> 00:08:55,140 of the y-values of the three nearest training points, or this value here. 118 00:08:55,140 --> 00:09:01,407 Similarly, if we have a training point, sorry, query point that is here. 119 00:09:01,407 --> 00:09:06,415 Then the three nearest neighbor 120 00:09:06,415 --> 00:09:11,620 points are here, here and here. 121 00:09:11,620 --> 00:09:16,520 And the average target value of these three training 122 00:09:16,520 --> 00:09:19,532 points is something like this. 123 00:09:22,843 --> 00:09:26,480 Here's the corresponding code in the notebook that produced these 124 00:09:26,480 --> 00:09:28,440 regression plots. 125 00:09:28,440 --> 00:09:32,910 These use the k- Neighbors Regressor Class, which like the classification case, 126 00:09:32,910 --> 00:09:35,670 takes the end neighbor setting as a key parameter. 127 00:09:36,960 --> 00:09:40,560 Because the target values in a regression problem are continuous 128 00:09:40,560 --> 00:09:46,280 as compared to the discrete values that we see for classifier target labels. 129 00:09:46,280 --> 00:09:48,690 To assess how well a regression model fits the data, 130 00:09:48,690 --> 00:09:52,760 we use a regression score called r-squared that's between 0 and 1. 131 00:09:52,760 --> 00:09:57,130 We'll cover some additional types of regression evaluation scores later in 132 00:09:57,130 --> 00:09:57,877 the course. 133 00:09:57,877 --> 00:09:59,934 For the r-squared value, 134 00:09:59,934 --> 00:10:05,090 a value of 1 corresponds to the best possible performance. 135 00:10:05,090 --> 00:10:06,880 A model that makes perfect predictions. 136 00:10:07,920 --> 00:10:12,010 A value of 0 corresponds to a model that makes a constant value prediction that's 137 00:10:12,010 --> 00:10:14,870 always just a mean value of all the training target values. 138 00:10:16,410 --> 00:10:20,370 The r-squared value is sometimes known as the coefficient of determination. 139 00:10:22,740 --> 00:10:25,990 Just as we did for classification, let's look at the connection between model 140 00:10:25,990 --> 00:10:30,860 complexity and generalization ability as measured by the r-squared training and 141 00:10:30,860 --> 00:10:33,970 test values on the simple regression dataset. 142 00:10:33,970 --> 00:10:40,226 The series of plots on the notebook shows how the KNN regression algorithm fits 143 00:10:40,226 --> 00:10:45,933 the data for k = 1, 3, 7, 15, and in an extreme case of k = 55. 144 00:10:45,933 --> 00:10:49,250 It represents almost half the training points. 145 00:10:49,250 --> 00:10:52,140 We can see the same pattern in model complexity for k and 146 00:10:52,140 --> 00:10:56,070 N regression that we saw for k and N classification. 147 00:10:56,070 --> 00:11:01,090 Namely, that small values of k give models with higher complexity. 148 00:11:01,090 --> 00:11:04,730 And large values of k result in simpler models with lower complexity. 149 00:11:05,910 --> 00:11:10,035 Starting on the left when k = 1, the regression model fits the training data 150 00:11:10,035 --> 00:11:12,518 perfectly with a r-squared score of 1.0. 151 00:11:12,518 --> 00:11:17,964 But it's very bad at predicting the target values for new data samples, 152 00:11:17,964 --> 00:11:22,705 as reflected in the r-squared test score of only 0.155. 153 00:11:24,570 --> 00:11:29,040 As the value of k increases, which we can see acts to smooth out these local 154 00:11:29,040 --> 00:11:31,540 variations to capture more of the global trend. 155 00:11:32,730 --> 00:11:36,390 Again the training set score drops, but the model gets better at generalizing to 156 00:11:36,390 --> 00:11:40,250 new data and the test score goes up as K increases. 157 00:11:41,670 --> 00:11:47,498 Finally in this series, the model with k = 15 has the best test set performance, 158 00:11:47,498 --> 00:11:50,450 with an r-squared score of 0.485. 159 00:11:50,450 --> 00:11:54,133 Increasing k much further however to k = 55, 160 00:11:54,133 --> 00:11:58,920 results in both the training and test set scores dropping back 161 00:11:58,920 --> 00:12:03,719 down to lower levels, as the model now starts to under-fit. 162 00:12:03,719 --> 00:12:07,420 In other words, it's too simple to do well, even on the training data. 163 00:12:09,680 --> 00:12:13,050 The pro's of the nearest neighbor approach are that it's simple and 164 00:12:13,050 --> 00:12:15,670 easy to understand why a particular prediction is made. 165 00:12:16,800 --> 00:12:21,110 A k-nearest neighbor approach can be a reasonable baseline against what you can 166 00:12:21,110 --> 00:12:23,229 compare more sophisticated methods. 167 00:12:24,280 --> 00:12:28,730 When the training data has many instances, or each instance has lots of features, 168 00:12:28,730 --> 00:12:32,810 this can really slow down the performance of a k-nearest neighbors model. 169 00:12:32,810 --> 00:12:36,620 So in general, if your data set has hundreds or thousands of features, 170 00:12:36,620 --> 00:12:39,500 you should consider alternatives to k-nearest neighbors models, 171 00:12:39,500 --> 00:12:41,870 especially if your data is sparse. 172 00:12:41,870 --> 00:12:44,970 Meaning that each instance has lots of features, but most of them are zero. 173 00:12:47,120 --> 00:12:50,670 So to sum up, and as a review of what we saw in week one. 174 00:12:50,670 --> 00:12:54,450 The two key parameters for both regression and classification 175 00:12:54,450 --> 00:12:59,700 in nearest neighbors models are naturally n-neighbors which controls the value 176 00:12:59,700 --> 00:13:04,160 of the number of neighbors to consider and thus the model complexity, as we saw. 177 00:13:05,600 --> 00:13:11,390 And the metric parameter which controls the distance function between points and 178 00:13:11,390 --> 00:13:15,110 thus which points are considered as nearest in finding neighbors. 179 00:13:16,330 --> 00:13:18,230 We didn't explore the metric parameter here and 180 00:13:18,230 --> 00:13:19,940 that's beyond the scope of this course. 181 00:13:19,940 --> 00:13:21,076 But in most cases, 182 00:13:21,076 --> 00:13:25,270 the default Euclidean setting words pretty well with most datasets.