8.6 Clustering | Initializing K-means-- [Machine Learning | Andrew Ng]
 The very first step of the k-means clustering algorithm was to choose random locations as the initial guesses for the cluster centroids mu1 through mu k. But how do you actually take that random guess? Let's take a look at that in this video, as well as how you can take multiple attempts at the initial guesses for mu1 through mu k that will result in you finding a better set of clusters. Let's take a look. Here again is the k-means algorithm and in this video, let's take a look at how you can implement this first step. When running k-means, you should pretty much always choose the number of cluster centroids k to be less than the training examples m. It doesn't really make sense to have k greater than m because then there won't even be enough training examples to have at least one training example per cluster centroid. So in our earlier example, we had k equals 2 and m equals 30. In order to choose the cluster centroids, the most common way is to randomly pick k training examples. So here is a training set where if I were to randomly pick two training examples, maybe I end up picking this one and this one and then we would set mu1 through mu k equal to these k training examples. So I might initialize my red cluster centroid here and initialize my blue cluster centroid over here in the example where k was equal to 2. And it turns out that if this was your random initialization and you were to run k-means, you probably end up with k-means deciding that these are the two clusters in the data set. Note that this method of initializing the cluster centroids is a little bit different than what I had used in the illustration in the earlier videos where I was initializing the cluster centroids mu1 and mu2 to be just random points rather than sitting on top of specific training examples. I've done that to make the illustrations clearer in the earlier videos, but what I'm showing in this slide is actually the much more commonly used way of initializing the cluster centroids. Now with this method, there is a chance that you will end up with an initialization of the cluster centroids where the red crosses here and maybe the blue crosses here. And depending on how you choose the random initial cluster centroids, k-means will end up picking a different set of clusters for your data set. Let's look at a slightly more complex example where we're going to look at this data set and try to find three clusters. So k equals 3 in this data. If you were to run k-means with one random initialization of the cluster centroids, you may get this result up here. And this looks like a pretty good choice, pretty good clustering of the data into three different clusters. But with a different initialization, say you had happened to initialize two of the cluster centroids within this group of points and one within this group of points, after running k-means, you might end up with this clustering, which doesn't look as good. And this turns out to be a local optima in which k-means is trying to minimize the distortion cost function, that cost function j of c1 through cm and mu1 through mu k that you saw in the last video. But with this less fortunate choice of random initialization, it had just happened to get stuck in a local minima. And here's another example of a local minima, where a different random initialization calls k-means to find this clustering of the data into three clusters, which again doesn't seem as good as the one that you saw up here on top. So if you want to give k-means multiple shots at finding the best local optima, if you want to try multiple random initializations to give it a better chance of finding this good clustering up on top, one other thing you could do with the k-means algorithm is to run it multiple times and then to try to find the best local optima. And it turns out that if you were to run k-means three times, say, and end up with these three distinct clusterings, then one way to choose between these three solutions is to compute the cost function j for all three of these solutions, all three of these choices of clusters found by k-means, and then to pick one of these three according to which one of them gives you the lowest value for the cost function j. And in fact, if you look at this grouping of clusters up here, this green cross has relatively small square distances, all the green dots. The red cross is relatively small distance in the red dots, and similarly the blue cross. And so the cost function j would be relatively small for this example on top. But here, the blue cross has larger distances to all of the blue dots. And here, the red cross has larger distances to all of the red dots, which is why the cost function j for these examples down below would be larger, which is why if you pick from these three options, the one with the smallest distortion, the smallest cost function j, you end up selecting this choice of the three cluster centroid. So let me write this out more formally into an algorithm in which you would run k-means multiple times using different random initializations. Here's the algorithm. If you want to use 100 random initializations for k-means, then you would run 100 times randomly initialized k-means using the methods that you saw earlier in this video. Pick k-training examples and let the cluster centroid initially be the locations of those k-training examples. Using that random initialization, run the k-means algorithm to convergence, and that will give you a choice of cluster assignments and cluster centroids. And then finally, you would compute the distortion, compute the cost function as follows. After doing this, say, 100 times, you would finally pick the set of clusters that gave the lowest cost. And it turns out that if you do this, it will often give you a much better set of clusters with a much lower distortion function than if you were to run k-means only a single time. I plugged in the number up here as 100. When I'm using this method, doing this somewhere between, say, 50 to 1,000 times would be pretty common where if you run this procedure a lot more than 1,000 times, it tends to get computationally expensive and you tend to have diminishing returns when you run it a lot of times. Whereas trying at least maybe 50 or 100 random initializations will often give you a much better result than if you only had one shot at picking a good random initialization. But with this technique, you are much more likely to end up with this good choice of clusters on top than these less superior local minima down at the bottom. So that's it. When I'm using the k-means algorithm myself, I will almost always use more than one random initialization because it just causes k-means to do a much better job minimizing the distortion cost function and finding a much better choice for the cluster centroids. Before we wrap up our discussion of k-means, there's just one more video in which I hope to discuss with you the question of how do you choose the number of cluster centroids? How do you choose the value of k? Let's go on to the next video to take a look at that.
[{"start": 0.0, "end": 7.44, "text": " The very first step of the k-means clustering algorithm was to choose random locations as"}, {"start": 7.44, "end": 12.280000000000001, "text": " the initial guesses for the cluster centroids mu1 through mu k."}, {"start": 12.280000000000001, "end": 15.72, "text": " But how do you actually take that random guess?"}, {"start": 15.72, "end": 21.080000000000002, "text": " Let's take a look at that in this video, as well as how you can take multiple attempts"}, {"start": 21.080000000000002, "end": 26.26, "text": " at the initial guesses for mu1 through mu k that will result in you finding a better"}, {"start": 26.26, "end": 27.26, "text": " set of clusters."}, {"start": 27.26, "end": 29.02, "text": " Let's take a look."}, {"start": 29.02, "end": 35.519999999999996, "text": " Here again is the k-means algorithm and in this video, let's take a look at how you can"}, {"start": 35.519999999999996, "end": 38.26, "text": " implement this first step."}, {"start": 38.26, "end": 43.42, "text": " When running k-means, you should pretty much always choose the number of cluster centroids"}, {"start": 43.42, "end": 47.08, "text": " k to be less than the training examples m."}, {"start": 47.08, "end": 53.28, "text": " It doesn't really make sense to have k greater than m because then there won't even be enough"}, {"start": 53.28, "end": 58.68, "text": " training examples to have at least one training example per cluster centroid."}, {"start": 58.68, "end": 65.12, "text": " So in our earlier example, we had k equals 2 and m equals 30."}, {"start": 65.12, "end": 75.16, "text": " In order to choose the cluster centroids, the most common way is to randomly pick k"}, {"start": 75.16, "end": 77.28, "text": " training examples."}, {"start": 77.28, "end": 83.88, "text": " So here is a training set where if I were to randomly pick two training examples, maybe"}, {"start": 83.88, "end": 92.52, "text": " I end up picking this one and this one and then we would set mu1 through mu k equal to"}, {"start": 92.52, "end": 95.44, "text": " these k training examples."}, {"start": 95.44, "end": 105.5, "text": " So I might initialize my red cluster centroid here and initialize my blue cluster centroid"}, {"start": 105.5, "end": 109.8, "text": " over here in the example where k was equal to 2."}, {"start": 109.8, "end": 115.52, "text": " And it turns out that if this was your random initialization and you were to run k-means,"}, {"start": 115.52, "end": 122.12, "text": " you probably end up with k-means deciding that these are the two clusters in the data"}, {"start": 122.12, "end": 123.12, "text": " set."}, {"start": 123.12, "end": 127.32, "text": " Note that this method of initializing the cluster centroids is a little bit different"}, {"start": 127.32, "end": 132.24, "text": " than what I had used in the illustration in the earlier videos where I was initializing"}, {"start": 132.24, "end": 137.51999999999998, "text": " the cluster centroids mu1 and mu2 to be just random points rather than sitting on top of"}, {"start": 137.51999999999998, "end": 139.64, "text": " specific training examples."}, {"start": 139.64, "end": 144.6, "text": " I've done that to make the illustrations clearer in the earlier videos, but what I'm showing"}, {"start": 144.6, "end": 151.35999999999999, "text": " in this slide is actually the much more commonly used way of initializing the cluster centroids."}, {"start": 151.35999999999999, "end": 159.27999999999997, "text": " Now with this method, there is a chance that you will end up with an initialization of"}, {"start": 159.27999999999997, "end": 165.51999999999998, "text": " the cluster centroids where the red crosses here and maybe the blue crosses here."}, {"start": 165.52, "end": 172.56, "text": " And depending on how you choose the random initial cluster centroids, k-means will end"}, {"start": 172.56, "end": 177.20000000000002, "text": " up picking a different set of clusters for your data set."}, {"start": 177.20000000000002, "end": 182.64000000000001, "text": " Let's look at a slightly more complex example where we're going to look at this data set"}, {"start": 182.64000000000001, "end": 185.28, "text": " and try to find three clusters."}, {"start": 185.28, "end": 188.42000000000002, "text": " So k equals 3 in this data."}, {"start": 188.42000000000002, "end": 195.24, "text": " If you were to run k-means with one random initialization of the cluster centroids, you"}, {"start": 195.24, "end": 197.92000000000002, "text": " may get this result up here."}, {"start": 197.92000000000002, "end": 202.44, "text": " And this looks like a pretty good choice, pretty good clustering of the data into three"}, {"start": 202.44, "end": 204.68, "text": " different clusters."}, {"start": 204.68, "end": 210.8, "text": " But with a different initialization, say you had happened to initialize two of the cluster"}, {"start": 210.8, "end": 216.32000000000002, "text": " centroids within this group of points and one within this group of points, after running"}, {"start": 216.32000000000002, "end": 222.54000000000002, "text": " k-means, you might end up with this clustering, which doesn't look as good."}, {"start": 222.54, "end": 229.42, "text": " And this turns out to be a local optima in which k-means is trying to minimize the distortion"}, {"start": 229.42, "end": 236.72, "text": " cost function, that cost function j of c1 through cm and mu1 through mu k that you saw"}, {"start": 236.72, "end": 238.66, "text": " in the last video."}, {"start": 238.66, "end": 246.23999999999998, "text": " But with this less fortunate choice of random initialization, it had just happened to get"}, {"start": 246.23999999999998, "end": 249.82, "text": " stuck in a local minima."}, {"start": 249.82, "end": 254.92, "text": " And here's another example of a local minima, where a different random initialization calls"}, {"start": 254.92, "end": 263.68, "text": " k-means to find this clustering of the data into three clusters, which again doesn't seem"}, {"start": 263.68, "end": 268.12, "text": " as good as the one that you saw up here on top."}, {"start": 268.12, "end": 275.5, "text": " So if you want to give k-means multiple shots at finding the best local optima, if you want"}, {"start": 275.5, "end": 281.12, "text": " to try multiple random initializations to give it a better chance of finding this good"}, {"start": 281.12, "end": 286.76, "text": " clustering up on top, one other thing you could do with the k-means algorithm is to"}, {"start": 286.76, "end": 292.44, "text": " run it multiple times and then to try to find the best local optima."}, {"start": 292.44, "end": 299.12, "text": " And it turns out that if you were to run k-means three times, say, and end up with these three"}, {"start": 299.12, "end": 305.72, "text": " distinct clusterings, then one way to choose between these three solutions is to compute"}, {"start": 305.72, "end": 313.2, "text": " the cost function j for all three of these solutions, all three of these choices of clusters"}, {"start": 313.2, "end": 319.44, "text": " found by k-means, and then to pick one of these three according to which one of them"}, {"start": 319.44, "end": 324.24, "text": " gives you the lowest value for the cost function j."}, {"start": 324.24, "end": 330.68, "text": " And in fact, if you look at this grouping of clusters up here, this green cross has"}, {"start": 330.68, "end": 334.2, "text": " relatively small square distances, all the green dots."}, {"start": 334.2, "end": 339.3, "text": " The red cross is relatively small distance in the red dots, and similarly the blue cross."}, {"start": 339.3, "end": 345.24, "text": " And so the cost function j would be relatively small for this example on top."}, {"start": 345.24, "end": 351.88, "text": " But here, the blue cross has larger distances to all of the blue dots."}, {"start": 351.88, "end": 358.32, "text": " And here, the red cross has larger distances to all of the red dots, which is why the cost"}, {"start": 358.32, "end": 365.36, "text": " function j for these examples down below would be larger, which is why if you pick from these"}, {"start": 365.36, "end": 372.32, "text": " three options, the one with the smallest distortion, the smallest cost function j, you end up selecting"}, {"start": 372.32, "end": 375.9, "text": " this choice of the three cluster centroid."}, {"start": 375.9, "end": 381.91999999999996, "text": " So let me write this out more formally into an algorithm in which you would run k-means"}, {"start": 381.91999999999996, "end": 386.88, "text": " multiple times using different random initializations."}, {"start": 386.88, "end": 388.65999999999997, "text": " Here's the algorithm."}, {"start": 388.65999999999997, "end": 398.4, "text": " If you want to use 100 random initializations for k-means, then you would run 100 times"}, {"start": 398.4, "end": 405.15999999999997, "text": " randomly initialized k-means using the methods that you saw earlier in this video."}, {"start": 405.16, "end": 411.52000000000004, "text": " Pick k-training examples and let the cluster centroid initially be the locations of those"}, {"start": 411.52000000000004, "end": 414.24, "text": " k-training examples."}, {"start": 414.24, "end": 419.96000000000004, "text": " Using that random initialization, run the k-means algorithm to convergence, and that"}, {"start": 419.96000000000004, "end": 425.8, "text": " will give you a choice of cluster assignments and cluster centroids."}, {"start": 425.8, "end": 431.96000000000004, "text": " And then finally, you would compute the distortion, compute the cost function as follows."}, {"start": 431.96, "end": 438.91999999999996, "text": " After doing this, say, 100 times, you would finally pick the set of clusters that gave"}, {"start": 438.91999999999996, "end": 442.0, "text": " the lowest cost."}, {"start": 442.0, "end": 448.56, "text": " And it turns out that if you do this, it will often give you a much better set of clusters"}, {"start": 448.56, "end": 454.91999999999996, "text": " with a much lower distortion function than if you were to run k-means only a single time."}, {"start": 454.91999999999996, "end": 458.56, "text": " I plugged in the number up here as 100."}, {"start": 458.56, "end": 465.08, "text": " When I'm using this method, doing this somewhere between, say, 50 to 1,000 times would be pretty"}, {"start": 465.08, "end": 472.0, "text": " common where if you run this procedure a lot more than 1,000 times, it tends to get computationally"}, {"start": 472.0, "end": 478.2, "text": " expensive and you tend to have diminishing returns when you run it a lot of times."}, {"start": 478.2, "end": 484.48, "text": " Whereas trying at least maybe 50 or 100 random initializations will often give you a much"}, {"start": 484.48, "end": 490.6, "text": " better result than if you only had one shot at picking a good random initialization."}, {"start": 490.6, "end": 495.08000000000004, "text": " But with this technique, you are much more likely to end up with this good choice of"}, {"start": 495.08000000000004, "end": 500.48, "text": " clusters on top than these less superior local minima down at the bottom."}, {"start": 500.48, "end": 501.48, "text": " So that's it."}, {"start": 501.48, "end": 506.12, "text": " When I'm using the k-means algorithm myself, I will almost always use more than one random"}, {"start": 506.12, "end": 512.24, "text": " initialization because it just causes k-means to do a much better job minimizing the distortion"}, {"start": 512.24, "end": 518.16, "text": " cost function and finding a much better choice for the cluster centroids."}, {"start": 518.16, "end": 522.88, "text": " Before we wrap up our discussion of k-means, there's just one more video in which I hope"}, {"start": 522.88, "end": 527.8, "text": " to discuss with you the question of how do you choose the number of cluster centroids?"}, {"start": 527.8, "end": 530.5600000000001, "text": " How do you choose the value of k?"}, {"start": 530.56, "end": 543.4399999999999, "text": " Let's go on to the next video to take a look at that."}]