1 00:00:00,430 --> 00:00:01,400 Hello, everyone. 2 00:00:01,400 --> 00:00:03,790 Welcome back to Mining of Massive Datasets. 3 00:00:03,790 --> 00:00:05,920 We're going to continue our discussion of Clustering today, 4 00:00:05,920 --> 00:00:07,940 by looking at the k-Means Algorithm. 5 00:00:07,940 --> 00:00:10,130 Recall that we previously, looked at another means, 6 00:00:10,130 --> 00:00:14,550 way of doing clustering called Agglomerative Hierarchical Clustering. 7 00:00:14,550 --> 00:00:17,980 Now, that algorithm worked very well in terms of producing clusters, but 8 00:00:17,980 --> 00:00:19,730 unfortunately, it doesn't work very well for 9 00:00:19,730 --> 00:00:23,450 large da, datasets because of its computational complexity. 10 00:00:23,450 --> 00:00:26,740 The k-Means Algorithm, or the k-Means family of Algorithms actually, 11 00:00:26,740 --> 00:00:30,800 is a way of addressing that problem, of creating Algorithms that 12 00:00:30,800 --> 00:00:34,068 are computational tractable and work with very large datasets. 13 00:00:34,068 --> 00:00:39,704 Now the k-means Algorithm assumes, a Euclidean space and 14 00:00:39,704 --> 00:00:42,740 the Euclidean distance. 15 00:00:42,740 --> 00:00:46,790 And the first step, is to pick k, the number of clusters. 16 00:00:46,790 --> 00:00:50,680 Now, for now let's assume that we pick a number k, and 17 00:00:50,680 --> 00:00:53,520 say that's the number of clusters that we finally want. 18 00:00:53,520 --> 00:00:57,940 Towards the end, I'll ca, I'll show you how to actually, pick this this value k. 19 00:00:57,940 --> 00:01:00,200 For now, let's just assume that k is the given. 20 00:01:01,270 --> 00:01:05,970 Now, we're going to initialize k clusters, by picking one point per cluster. 21 00:01:05,970 --> 00:01:09,250 For example, we could just pick k points at random, one, and 22 00:01:09,250 --> 00:01:10,830 assign one point to each cluster. 23 00:01:10,830 --> 00:01:15,280 And that would be the one way of picking the points. 24 00:01:15,280 --> 00:01:18,660 Later on we'll examine other ways of doing this much better. 25 00:01:22,460 --> 00:01:26,560 Now that we have clusters populated with these k-points picked at random, 26 00:01:26,560 --> 00:01:28,750 here's how we're going to proceed. 27 00:01:28,750 --> 00:01:31,490 We're really go through all the points in our datasets. 28 00:01:31,490 --> 00:01:35,010 And for each point, we're going to place it in the cluster. 29 00:01:35,010 --> 00:01:37,480 To whose centroid it's closest. 30 00:01:37,480 --> 00:01:41,830 So, you're going to find the cluster with the closest centroid to the data point, 31 00:01:41,830 --> 00:01:45,230 and then we'll assign that data point to that cluster. 32 00:01:45,230 --> 00:01:47,010 Okay? And we're going to do this for 33 00:01:47,010 --> 00:01:48,690 each data point. 34 00:01:48,690 --> 00:01:53,360 Now, when we assign a whole bunch of new data points to a cluster, 35 00:01:53,360 --> 00:01:55,630 the centroid of a cluster might change. 36 00:01:55,630 --> 00:01:58,668 Because of all the new data points that have been added with the cluster. 37 00:01:58,668 --> 00:01:59,510 So, we're going to go up, 38 00:01:59,510 --> 00:02:03,260 update the locations of the centroids of each of the k clusters, 39 00:02:03,260 --> 00:02:07,750 by taking into account the new data points that have been added to those clusters. 40 00:02:07,750 --> 00:02:12,860 Now, once we do this, we'll find that the centroids of, 41 00:02:12,860 --> 00:02:14,810 of the k clusters have moved, and 42 00:02:14,810 --> 00:02:18,490 now a point that was close to one cluster may be closer to another cluster. 43 00:02:18,490 --> 00:02:22,380 So, we need to go through and reassign all points to their closest centroid. 44 00:02:22,380 --> 00:02:24,800 And sometimes this moves points between the clusters. 45 00:02:25,870 --> 00:02:30,370 And notice that we, we may have to do poi, you know, steps 2 and 3 again and again. 46 00:02:30,370 --> 00:02:32,960 And it, thi, this is exactly, what we're going to do. 47 00:02:32,960 --> 00:02:35,990 We're going to repeat steps 2 and 3, until Convergence. 48 00:02:35,990 --> 00:02:40,620 And what we mean by Convergence, is that the k centroids don't move any further, 49 00:02:40,620 --> 00:02:45,600 and the point don't move en, any further across the across the centroids. 50 00:02:45,600 --> 00:02:48,215 At that point, we have a stable k-means clustering. 51 00:02:49,400 --> 00:02:50,800 So let's look at an example. 52 00:02:50,800 --> 00:02:55,486 So, here's a set of points and we are going to do obviously, 53 00:02:55,486 --> 00:03:02,200 say that k is equal to 2, so we're looking to find two clusters in this dataset. 54 00:03:02,200 --> 00:03:08,210 Now in, in Round 1, I'm at random going to pick two points since k equal 2 and 55 00:03:08,210 --> 00:03:10,630 call those a centroid of two clusters. 56 00:03:10,630 --> 00:03:13,200 Let's say, I pick these two points so 57 00:03:13,200 --> 00:03:16,860 the, the point that I've highlighted with the in pink here and 58 00:03:16,860 --> 00:03:20,260 the point that I've highlighted in blue here as the two centroids. 59 00:03:20,260 --> 00:03:22,260 I've picked this totally arbitrarily and at random. 60 00:03:23,670 --> 00:03:28,070 Now, what I'm going to do is I'm going to go through, all the data points and for 61 00:03:28,070 --> 00:03:33,730 each data point, I'm going to assign it to the centroid that it's closest to. 62 00:03:33,730 --> 00:03:38,700 So, observe that this point for example here, is close to the red cluster. 63 00:03:38,700 --> 00:03:40,630 So, I'm going to assign it to the red cluster. 64 00:03:40,630 --> 00:03:44,830 Whereas, this point here is closer to the blue cluster than to the red cluster, so 65 00:03:44,830 --> 00:03:46,820 I'm going to assign it to the blue cluster. 66 00:03:46,820 --> 00:03:51,680 And, you know, when I go through all the data points and do this. 67 00:03:51,680 --> 00:03:54,060 Here is the clustering that I end up with. 68 00:03:54,060 --> 00:04:00,090 These two points here end up in the you know, in, in the pink cluster here and 69 00:04:00,090 --> 00:04:04,240 this set of points are closer to the the blue point here, and so 70 00:04:04,240 --> 00:04:05,320 they end up in a blue cluster. 71 00:04:06,650 --> 00:04:09,350 So, that's round 1 of k-means clustering. 72 00:04:09,350 --> 00:04:11,980 Now, what I'm going to do now is, because I've 73 00:04:11,980 --> 00:04:16,530 created these two new clusters I'm going to compute the new centroids. 74 00:04:16,530 --> 00:04:19,940 And when I compute the new centroids, the the centroid of 75 00:04:19,940 --> 00:04:25,600 the pink cluster moves over a little bit to the left to this new position here. 76 00:04:25,600 --> 00:04:28,800 And the centroid of the blue cluster moves to that new position. 77 00:04:28,800 --> 00:04:33,583 Now, is because I have new centroids, I'm going to go through in round 2, I'm 78 00:04:33,583 --> 00:04:37,830 going to go through each data point again and assign it to it's closest centroid. 79 00:04:37,830 --> 00:04:42,880 And when I do that,observe that, point for example this point here 80 00:04:42,880 --> 00:04:47,750 is now closer to the the pink cluster than it is to the blue cluster. 81 00:04:47,750 --> 00:04:50,186 And so it moves from the blue cluster to the pink cluster. 82 00:04:50,186 --> 00:04:50,909 Okay? 83 00:04:50,909 --> 00:04:56,343 [SOUND] And so we have this new clustering and the end of round 2. 84 00:04:56,343 --> 00:05:00,398 Now that, we have the new clustering, I'm going to recompute the centroids once 85 00:05:00,398 --> 00:05:05,180 again, and when I recompute the centroids, the the centroids migrate further. 86 00:05:06,960 --> 00:05:09,480 And because the centroids are migrated further, 87 00:05:09,480 --> 00:05:14,100 I have to recompute the, the assignment of points to the centroids again. 88 00:05:14,100 --> 00:05:19,370 And when I do that these two points here are then 89 00:05:19,370 --> 00:05:25,432 are closer to the the pink cluster, so they move to the to the pink cluster and 90 00:05:26,477 --> 00:05:30,429 and we end up with the clustering show here at the end of Round 3. 91 00:05:31,740 --> 00:05:32,280 Okay? 92 00:05:32,280 --> 00:05:36,761 Now, as it turns out, in this case, Round 3 is the last round. 93 00:05:36,761 --> 00:05:39,170 a, at this point, the centroids and 94 00:05:39,170 --> 00:05:43,290 the, points don't migrate any further, and we have a stable clustering. 95 00:05:43,290 --> 00:05:49,080 So, what we have here is the, clustering, the k-means clustering for 96 00:05:49,080 --> 00:05:53,080 k is equal to 2, for, for this dataset. 97 00:05:53,080 --> 00:05:57,910 Observe that I started from a completely random assignment of you know, of, 98 00:05:57,910 --> 00:06:02,360 of centroids and actually migrated the centroids to where they finally ended up. 99 00:06:05,060 --> 00:06:08,800 Now, the important question here is, how to we pick the right value of k? 100 00:06:08,800 --> 00:06:12,290 In the previous example, we arbitrarily picked k is equal to 2 and 101 00:06:12,290 --> 00:06:15,610 that actually turned out to be the right value for that datasets because you 102 00:06:15,610 --> 00:06:21,240 can see that there are roughly, two different clusters of data points here. 103 00:06:21,240 --> 00:06:24,680 But in general, how do we know what the right value of k is up front? 104 00:06:24,680 --> 00:06:27,360 So that we can pick the number of clusters up front. 105 00:06:28,750 --> 00:06:30,370 So, since we don't know the right value of k, 106 00:06:30,370 --> 00:06:33,540 the obvious answer is to try different values of k. 107 00:06:35,220 --> 00:06:37,390 And see what looks good. 108 00:06:37,390 --> 00:06:38,970 Now the question, now we have to decide. 109 00:06:38,970 --> 00:06:40,380 What do we mean, by what looks good? 110 00:06:41,440 --> 00:06:45,330 One obvious answer is to look at the average distance of points from 111 00:06:45,330 --> 00:06:47,950 the centroid as k increases. 112 00:06:47,950 --> 00:06:48,490 Right? And 113 00:06:48,490 --> 00:06:52,500 let's see let's look at an example to see what we mean here. 114 00:06:52,500 --> 00:06:55,260 So here's here's an example with a bunch of data points, and 115 00:06:55,260 --> 00:06:57,500 they've actually picked k is equal to 2. 116 00:06:57,500 --> 00:07:00,790 Because I pi, pick k equal 2, we have two clusters. 117 00:07:00,790 --> 00:07:04,920 And you, you can see that, that's a centroid off of the first cluster. 118 00:07:04,920 --> 00:07:08,350 And you can see, there's a lot of points that are very far away 119 00:07:08,350 --> 00:07:10,450 from the centroid in this case. 120 00:07:10,450 --> 00:07:10,980 Right? 121 00:07:10,980 --> 00:07:15,270 Now, if, if k is too small, as in this case, then there are going to be lots of 122 00:07:15,270 --> 00:07:18,150 points that are a large distance away from the centroid. 123 00:07:18,150 --> 00:07:21,090 So, the average distance from the distance is going to be fairly large. 124 00:07:23,700 --> 00:07:25,620 Now, I made k equal 3. 125 00:07:25,620 --> 00:07:28,230 and, as it turns out, this is the right value for 126 00:07:28,230 --> 00:07:32,620 this dataset, and you can see that the, distances to the, 127 00:07:32,620 --> 00:07:37,220 centroid shrink quite a lot, when I went from, k equal 2 to k equal 3. 128 00:07:37,220 --> 00:07:42,360 That splits the, top cluster into two, and that shrinks the average value, or the, 129 00:07:42,360 --> 00:07:45,330 or the average distance of the centroid significantly. 130 00:07:45,330 --> 00:07:46,330 Right? 131 00:07:46,330 --> 00:07:50,120 And the and but if I increase k, further. 132 00:07:50,120 --> 00:07:53,310 Let's say, I make k equal 4 and that splits that cluster, further. 133 00:07:53,310 --> 00:07:56,570 Now, that does shrink the average sums of the centroid, but 134 00:07:56,570 --> 00:08:01,740 not as much as when we went from k equal 2, to k equal 3. 135 00:08:01,740 --> 00:08:03,799 Right? So, when we make k, too large,. 136 00:08:05,020 --> 00:08:08,790 It does decrease the average distance of the centroid. 137 00:08:08,790 --> 00:08:10,920 But not, by not as much. 138 00:08:10,920 --> 00:08:13,270 Now, we can see this very clearly if I plot a graph. 139 00:08:13,270 --> 00:08:16,740 Right, if I plot a graph, where the x axis is k, the number of clusters. 140 00:08:16,740 --> 00:08:19,400 And the y axis is the average distance to the centroid. 141 00:08:19,400 --> 00:08:21,440 You can see that as k increases. 142 00:08:21,440 --> 00:08:24,080 The average distance to the centroid keeps falling. 143 00:08:24,080 --> 00:08:28,760 But, at some point, it's, it, you know, the, there's a knee of the curve and 144 00:08:28,760 --> 00:08:31,860 the average distance to the centroid falls very slowly. 145 00:08:33,120 --> 00:08:35,870 The obvious thing to do is to pick a value of k, 146 00:08:35,870 --> 00:08:39,587 that's close to the knee of the curve, where you get a more, 147 00:08:39,587 --> 00:08:43,820 you know, a fairly low distance to the average distance to the centroid. 148 00:08:43,820 --> 00:08:45,450 Without too high, a value of k. 149 00:08:46,470 --> 00:08:51,000 So, in this case, the best value of k, is the one that's, that's shown in this, 150 00:08:51,000 --> 00:08:51,750 shown in the picture. 151 00:08:53,020 --> 00:08:56,720 The final question we need to address, with k-means clustering is the picking of 152 00:08:56,720 --> 00:09:00,100 the k initial point to initialize the k clusters. 153 00:09:00,100 --> 00:09:02,610 In the examples, that we've seen so far, we've picked the. 154 00:09:02,610 --> 00:09:05,390 The initial k points entire completely at random. 155 00:09:05,390 --> 00:09:09,410 Now that model not a very bad example, but in general it might not work for 156 00:09:09,410 --> 00:09:10,250 quite so bad. 157 00:09:10,250 --> 00:09:15,330 If you make for example pick k point that all happen to be in the same cluster. 158 00:09:15,330 --> 00:09:20,180 In which case the final clustering, won't reflect the actual clustering of the data. 159 00:09:20,180 --> 00:09:23,475 Right, or we might pick points that are outliers that are not near, 160 00:09:23,475 --> 00:09:24,890 near any of the near clusters. 161 00:09:24,890 --> 00:09:29,720 So, the the final clustering depends on the initial k point that they picked. 162 00:09:29,720 --> 00:09:33,170 And so it's important that they pick the right 163 00:09:33,170 --> 00:09:35,150 k points to start the clustering from. 164 00:09:39,150 --> 00:09:43,440 The first approach, to picking the initial k point is Sampling. 165 00:09:43,440 --> 00:09:46,290 So remember that the data set is very large and so we 166 00:09:46,290 --> 00:09:50,710 can't actually run a complicated algorithm like hierarchical clustering on it. 167 00:09:50,710 --> 00:09:55,360 But what we can do is to sample the data and take a smaller sample of the data. 168 00:09:55,360 --> 00:09:58,980 And then using the sample of the data, we can then another algorithm like 169 00:09:58,980 --> 00:10:02,340 Hierarchical Agglomerative Clustering, in which we covered in the last lecture. 170 00:10:02,340 --> 00:10:05,940 And we can run that algorithm until we obtain k clusters. 171 00:10:05,940 --> 00:10:09,050 And then we can pick a point from each of the k clusters. 172 00:10:09,050 --> 00:10:13,030 For example, we could pick the point that's closest to the centroid for 173 00:10:13,030 --> 00:10:14,250 each cluster. 174 00:10:14,250 --> 00:10:17,930 And we could call those, our initial k k centroids. 175 00:10:19,140 --> 00:10:23,820 Another approach is to not resort to another clustering algorithm, but 176 00:10:23,820 --> 00:10:25,860 to just pick a dispersed set of points. 177 00:10:25,860 --> 00:10:28,490 Points that are as far away from each other. 178 00:10:28,490 --> 00:10:30,140 In the dataset, as possible. 179 00:10:30,140 --> 00:10:34,660 So, one approach to this, is to first pick a, the first point entirely at random. 180 00:10:34,660 --> 00:10:37,890 Now, the second point, we pick to 181 00:10:37,890 --> 00:10:43,630 be the point that's as far away from the first point as possible, in the dataset. 182 00:10:43,630 --> 00:10:48,180 The third point, we pick to be the point that is as far away from both 183 00:10:48,180 --> 00:10:50,400 point one and point two as possible. 184 00:10:50,400 --> 00:10:52,390 In general, we pick you know, 185 00:10:52,390 --> 00:10:56,150 once we've picked the first few points, we pick the next point to be the one 186 00:10:56,150 --> 00:11:00,120 who's minimum distance from the already selected points, is as large as possible. 187 00:11:01,260 --> 00:11:03,280 And then, we repeat this, until we pick k points. 188 00:11:04,750 --> 00:11:08,770 So, this ensures that the k point, that's we've picked, are as far apart or 189 00:11:08,770 --> 00:11:12,280 as disperse as possible, you, you know, in the, in the data set. 190 00:11:12,280 --> 00:11:15,172 And that gives us a better chance of finding the right clustering. 191 00:11:20,888 --> 00:11:26,470 Let's consider the Complexity of k-means clustering. 192 00:11:26,470 --> 00:11:30,230 Now in each round, we have to examine each input point exactly, 193 00:11:30,230 --> 00:11:34,290 once to find the closest centroid to that point and assign it to that centroid. 194 00:11:35,830 --> 00:11:41,050 Now, since there are endpoints and there are k centroids, right? 195 00:11:41,050 --> 00:11:45,380 We have to compute the distance of each point from each centroid, so 196 00:11:45,380 --> 00:11:49,890 the algorithm is order k times N for endpoints and k clusters. 197 00:11:49,890 --> 00:11:56,600 Now each round is it's, it's it's it's a Complexity k times N. 198 00:11:56,600 --> 00:12:00,990 Now this is actually, not bad because you know when N is really large and 199 00:12:00,990 --> 00:12:04,750 k is fairly small, we have a linear algorithm in N. 200 00:12:04,750 --> 00:12:06,980 Each round is actually, linear in N. 201 00:12:06,980 --> 00:12:11,180 But the real problem is that, the number of rounds to convergence can be really, 202 00:12:11,180 --> 00:12:12,500 really large. 203 00:12:12,500 --> 00:12:15,800 There is actually, no theoretical limit on the number of rounds to for 204 00:12:15,800 --> 00:12:17,810 the algorithms to convert to converge. 205 00:12:17,810 --> 00:12:19,940 And the number of rounds can be really, really large. 206 00:12:19,940 --> 00:12:21,440 So, the algorithm could spend actually, 207 00:12:21,440 --> 00:12:24,840 a really long time getting to getting to convergence. 208 00:12:26,990 --> 00:12:28,960 So the question is, if the dataset is really, 209 00:12:28,960 --> 00:12:34,840 really large and we don't want to go through this large number of rounds? 210 00:12:34,840 --> 00:12:40,160 Can we actually, do something like k-means clustering in a single pass over the data? 211 00:12:40,160 --> 00:12:41,500 Because we have a really large dataset, 212 00:12:41,500 --> 00:12:43,580 and we don't want to scan it multiple times. 213 00:12:44,800 --> 00:12:47,300 We're going to answer this question in the next segment.