8.3 Clustering | K-means intuition-- [Machine Learning | Andrew Ng]
 Let's take a look at what the k-means clustering algorithm does. Let me start with an example. Here I've plotted a dataset with 30 unlabeled training examples. So there are 30 points. And what we'd like to do is run k-means on this dataset. The first thing that the k-means algorithm does is it will take a random guess at where might be the centers of the two clusters that you might ask it to find. In this example, I'm going to ask it to try to find two clusters. Later in this week, we'll talk about how you might decide how many clusters to find. But the very first step is it will randomly pick two points, which I've shown here as a red cross and a blue cross at where might be the centers of two different clusters. This is just a random initial guess and they're not particularly good guesses, but it's a start. One thing I hope you take away from this video is that k-means will repeatedly do two different things. The first is assign points to cluster centroids and the second is move cluster centroids. Let's take a look at what this means. The first of the two steps is it will go through each of these points and look at whether it is closer to the red cross or to the blue cross. The very first thing that k-means does is it will take a random guess at where are the centers of the cluster. And the centers of the cluster are called cluster centroids. After it's made an initial guess at where are the cluster centroids, it will go through all of these examples, x1 through x30 by 30 data points, and for each of them it will check if it is closer to the red cluster centroid, shown by the red cross, or if it's closer to the blue cluster centroid, shown by the blue cross, and it will assign each of these points to whichever of the cluster centroids it is closer to. I'm going to illustrate that by painting each of these examples, each of these little round dots, either red or blue, depending on whether that example is closer to the red or to the blue cluster centroid. So this point up here is closer to the red centroid, which is why it's painted red, whereas this point down there is closer to the blue cluster centroid, which is why I've now painted it blue. So that was the first of the two things that k-means does over and over, which is assign points to cluster centroids. And all that means is it will associate, which I'm illustrating here with the color, every point of one of the cluster centroids. The second of the two steps that k-means does is it will look at all of the red points and take an average of them, and it will move the red cross to whatever is the average location of the red dots, which turns out to be here. And so the red cross, that is the red cluster centroid, will move here. And then we do the same thing for all the blue dots. Look at all the blue dots and take an average of them and move the blue cross over there, so you now have a new location for the blue cluster centroid as well. In the next video, we'll look at the mathematical formulas for how to do both of these steps. But now that you have these new and hopefully slightly improved guesses for the locations of the two cluster centroids, we'll look through all of the 30 training examples again and check for every one of them, whether it's closer to the red or the blue cluster centroid for the new locations, and then we will associate them, which are indicated by the color again, every point to the closer cluster centroid. And if you do that, you see that a few of the points change color. So for example, this point is colored red because it was closer to the red cluster centroid previously, but if we now look again, it's now actually closer to the blue cluster centroid because the blue and red cluster centroids have moved. So if we go through and associate each point with the closer cluster centroid, you end up with this. And then we just repeat the second part of k-means again, which is look at all of the red dots and compute the average, and also look at all of the blue dots and compute the average location of all of the blue dots. And it turns out that you end up moving the red cross over there and the blue cross over here. And we repeat, let's look at all of the points again and we color them either red or blue, depending on which cluster centroid it is closer to. So you end up with this. And then again, look at all of the red dots and take the average location and look at all the blue dots and take the average location and move the clusters to the new locations. And it turns out that if you were to keep on repeating these two steps, that is, look at each point and assign it to the nearest cluster centroid, and then also move each cluster centroid to the mean of all the points with the same color, if you keep on doing those two steps, you find that there are no more changes to the colors of the points or to the locations of the cluster centroids. And so this means that at this point, the k-means clustering algorithm has converged because applying those two steps over and over results in no further changes to either the assignment of points to the centroids or to the location of the cluster centroids. In this example, it looks like k-means has done a pretty good job. It has found that these points up here correspond to one cluster and these points down here correspond to a second cluster. So now you've seen an illustration of how k-means works. The two key steps are assign every point to cluster centroid, depending on what cluster centroid is nearest to, and second, move each cluster centroid to the average or the mean of all the points that were assigned to it. In the next video, we'll look at how to formalize this and write out the algorithm that does what you just saw in this video. Let's go on to the next video.
[{"start": 0.0, "end": 5.8, "text": " Let's take a look at what the k-means clustering algorithm does."}, {"start": 5.8, "end": 8.6, "text": " Let me start with an example."}, {"start": 8.6, "end": 13.58, "text": " Here I've plotted a dataset with 30 unlabeled training examples."}, {"start": 13.58, "end": 15.56, "text": " So there are 30 points."}, {"start": 15.56, "end": 20.12, "text": " And what we'd like to do is run k-means on this dataset."}, {"start": 20.12, "end": 25.84, "text": " The first thing that the k-means algorithm does is it will take a random guess at where"}, {"start": 25.84, "end": 31.56, "text": " might be the centers of the two clusters that you might ask it to find."}, {"start": 31.56, "end": 36.480000000000004, "text": " In this example, I'm going to ask it to try to find two clusters."}, {"start": 36.480000000000004, "end": 41.84, "text": " Later in this week, we'll talk about how you might decide how many clusters to find."}, {"start": 41.84, "end": 47.92, "text": " But the very first step is it will randomly pick two points, which I've shown here as"}, {"start": 47.92, "end": 56.64, "text": " a red cross and a blue cross at where might be the centers of two different clusters."}, {"start": 56.64, "end": 61.96, "text": " This is just a random initial guess and they're not particularly good guesses, but it's a"}, {"start": 61.96, "end": 62.96, "text": " start."}, {"start": 62.96, "end": 69.36, "text": " One thing I hope you take away from this video is that k-means will repeatedly do two different"}, {"start": 69.36, "end": 70.36, "text": " things."}, {"start": 70.36, "end": 76.36, "text": " The first is assign points to cluster centroids and the second is move cluster centroids."}, {"start": 76.36, "end": 78.36, "text": " Let's take a look at what this means."}, {"start": 78.36, "end": 84.6, "text": " The first of the two steps is it will go through each of these points and look at whether it"}, {"start": 84.6, "end": 92.08, "text": " is closer to the red cross or to the blue cross."}, {"start": 92.08, "end": 97.2, "text": " The very first thing that k-means does is it will take a random guess at where are the"}, {"start": 97.2, "end": 100.12, "text": " centers of the cluster."}, {"start": 100.12, "end": 106.08, "text": " And the centers of the cluster are called cluster centroids."}, {"start": 106.08, "end": 110.14, "text": " After it's made an initial guess at where are the cluster centroids, it will go through"}, {"start": 110.14, "end": 119.08, "text": " all of these examples, x1 through x30 by 30 data points, and for each of them it will"}, {"start": 119.08, "end": 124.48, "text": " check if it is closer to the red cluster centroid, shown by the red cross, or if it's closer"}, {"start": 124.48, "end": 130.24, "text": " to the blue cluster centroid, shown by the blue cross, and it will assign each of these"}, {"start": 130.24, "end": 135.28, "text": " points to whichever of the cluster centroids it is closer to."}, {"start": 135.28, "end": 140.64000000000001, "text": " I'm going to illustrate that by painting each of these examples, each of these little round"}, {"start": 140.64000000000001, "end": 148.32, "text": " dots, either red or blue, depending on whether that example is closer to the red or to the"}, {"start": 148.32, "end": 150.56, "text": " blue cluster centroid."}, {"start": 150.56, "end": 155.24, "text": " So this point up here is closer to the red centroid, which is why it's painted red, whereas"}, {"start": 155.24, "end": 160.0, "text": " this point down there is closer to the blue cluster centroid, which is why I've now painted"}, {"start": 160.0, "end": 162.1, "text": " it blue."}, {"start": 162.1, "end": 168.51999999999998, "text": " So that was the first of the two things that k-means does over and over, which is assign"}, {"start": 168.51999999999998, "end": 170.38, "text": " points to cluster centroids."}, {"start": 170.38, "end": 176.28, "text": " And all that means is it will associate, which I'm illustrating here with the color, every"}, {"start": 176.28, "end": 178.88, "text": " point of one of the cluster centroids."}, {"start": 178.88, "end": 186.24, "text": " The second of the two steps that k-means does is it will look at all of the red points and"}, {"start": 186.24, "end": 194.8, "text": " take an average of them, and it will move the red cross to whatever is the average location"}, {"start": 194.8, "end": 198.48000000000002, "text": " of the red dots, which turns out to be here."}, {"start": 198.48000000000002, "end": 203.60000000000002, "text": " And so the red cross, that is the red cluster centroid, will move here."}, {"start": 203.60000000000002, "end": 205.86, "text": " And then we do the same thing for all the blue dots."}, {"start": 205.86, "end": 212.28, "text": " Look at all the blue dots and take an average of them and move the blue cross over there,"}, {"start": 212.28, "end": 218.24, "text": " so you now have a new location for the blue cluster centroid as well."}, {"start": 218.24, "end": 223.84, "text": " In the next video, we'll look at the mathematical formulas for how to do both of these steps."}, {"start": 223.84, "end": 228.52, "text": " But now that you have these new and hopefully slightly improved guesses for the locations"}, {"start": 228.52, "end": 236.16, "text": " of the two cluster centroids, we'll look through all of the 30 training examples again and"}, {"start": 236.16, "end": 241.44, "text": " check for every one of them, whether it's closer to the red or the blue cluster centroid"}, {"start": 241.44, "end": 247.92, "text": " for the new locations, and then we will associate them, which are indicated by the color again,"}, {"start": 247.92, "end": 251.64, "text": " every point to the closer cluster centroid."}, {"start": 251.64, "end": 255.9, "text": " And if you do that, you see that a few of the points change color."}, {"start": 255.9, "end": 262.0, "text": " So for example, this point is colored red because it was closer to the red cluster centroid"}, {"start": 262.0, "end": 266.84, "text": " previously, but if we now look again, it's now actually closer to the blue cluster centroid"}, {"start": 266.84, "end": 270.92, "text": " because the blue and red cluster centroids have moved."}, {"start": 270.92, "end": 276.8, "text": " So if we go through and associate each point with the closer cluster centroid, you end"}, {"start": 276.8, "end": 278.88, "text": " up with this."}, {"start": 278.88, "end": 285.28000000000003, "text": " And then we just repeat the second part of k-means again, which is look at all of the"}, {"start": 285.28000000000003, "end": 292.0, "text": " red dots and compute the average, and also look at all of the blue dots and compute the"}, {"start": 292.0, "end": 295.36, "text": " average location of all of the blue dots."}, {"start": 295.36, "end": 301.8, "text": " And it turns out that you end up moving the red cross over there and the blue cross over"}, {"start": 301.8, "end": 302.96000000000004, "text": " here."}, {"start": 302.96000000000004, "end": 308.04, "text": " And we repeat, let's look at all of the points again and we color them either red or blue,"}, {"start": 308.04, "end": 311.44, "text": " depending on which cluster centroid it is closer to."}, {"start": 311.44, "end": 313.64, "text": " So you end up with this."}, {"start": 313.64, "end": 317.8, "text": " And then again, look at all of the red dots and take the average location and look at"}, {"start": 317.8, "end": 325.22, "text": " all the blue dots and take the average location and move the clusters to the new locations."}, {"start": 325.22, "end": 330.20000000000005, "text": " And it turns out that if you were to keep on repeating these two steps, that is, look"}, {"start": 330.20000000000005, "end": 334.76000000000005, "text": " at each point and assign it to the nearest cluster centroid, and then also move each"}, {"start": 334.76000000000005, "end": 340.32000000000005, "text": " cluster centroid to the mean of all the points with the same color, if you keep on doing"}, {"start": 340.32000000000005, "end": 345.48, "text": " those two steps, you find that there are no more changes to the colors of the points or"}, {"start": 345.48, "end": 348.48, "text": " to the locations of the cluster centroids."}, {"start": 348.48, "end": 354.02000000000004, "text": " And so this means that at this point, the k-means clustering algorithm has converged"}, {"start": 354.02, "end": 360.44, "text": " because applying those two steps over and over results in no further changes to either"}, {"start": 360.44, "end": 365.68, "text": " the assignment of points to the centroids or to the location of the cluster centroids."}, {"start": 365.68, "end": 369.47999999999996, "text": " In this example, it looks like k-means has done a pretty good job."}, {"start": 369.47999999999996, "end": 376.84, "text": " It has found that these points up here correspond to one cluster and these points down here"}, {"start": 376.84, "end": 380.02, "text": " correspond to a second cluster."}, {"start": 380.02, "end": 384.44, "text": " So now you've seen an illustration of how k-means works."}, {"start": 384.44, "end": 389.64, "text": " The two key steps are assign every point to cluster centroid, depending on what cluster"}, {"start": 389.64, "end": 396.56, "text": " centroid is nearest to, and second, move each cluster centroid to the average or the mean"}, {"start": 396.56, "end": 399.91999999999996, "text": " of all the points that were assigned to it."}, {"start": 399.91999999999996, "end": 404.78, "text": " In the next video, we'll look at how to formalize this and write out the algorithm that does"}, {"start": 404.78, "end": 407.28, "text": " what you just saw in this video."}, {"start": 407.28, "end": 410.4, "text": " Let's go on to the next video."}]