8.5 Clustering | Optimization objective-- [Machine Learning | Andrew Ng]
 In the earlier courses, courses one and two of the specialization, you saw a lot of supervised learning algorithms as ticket training set, posing a cost function, and then using gradient descent or some other algorithms to optimize that cost function. It turns out that the Q means algorithm that you saw in the last video is also optimizing a specific cost function. Although the optimization algorithm that it uses to optimize that is not gradient descent, it's actually the algorithm that you already saw in the last video. Let's take a look at what all this means. Let's take a look at what is the cost function for K means. To get started, as a reminder, this is the notation we've been using where Ci is the index of the cluster, so Ci is some number from 1 through K, of the index of the cluster to which training example Xi is currently assigned, and mu K is the location of cluster centroid K. Let me introduce one more piece of notation, which is when lowercase k equals Ci, so mu subscript Ci is the cluster centroid of the cluster to which example Xi has been assigned. So for example, if I were to look at some training example, say training example 10, and I were to ask, what's the location of the cluster centroid to which the 10th training example has been assigned? Well, I would then look up C10. This would give me a number from 1 to K that tells me was example 10 assigned to the red or the blue or some other cluster centroid, and then mu subscript C10 is the location of the cluster centroid to which X10 has been assigned. So armed with this notation, let me now write out the cost function that K means turns out to be minimizing. The cost function J, which is a function of C1 through CM, these are all the assignments of points to cluster centroids, as well as mu 1 through mu K. These are the locations of all the cluster centroids as defined as this expression on the right. It is the average, so 1 over M of sum from i equals 1 to M of the squared distance between every training example Xi as i goes from 1 through M. It is the square distance between Xi and mu subscript Ci. So this quantity up here. In other words, the cost function for K means is the average squared distance between every training example Xi and the location of the cluster centroid to which the training example Xi has been assigned. So for this example up here, we would be measuring the distance between X10 and mu subscript C10, the cluster centroid to which X10 has been assigned, and taking the square of that distance. And that would be one of the terms over here that we're averaging over. And it turns out that what the K means algorithm is doing is trying to find assignments of points to cluster centroids, as well as find locations of cluster centroids that minimizes the squared distance. Visually, here's what you saw part way into the run of K means in an earlier video. And at this step, the cost function, if you were to compute it, would be to look at every one of the blue points and measure these distances and compute the square. And then also similarly look at every one of the red points and compute these distances and compute the square. And then the average of the squares of all of these differences for the red and the blue points is the value of the cost function J at this particular configuration of the parameters for K means. And what it will do on every step is try to update the cluster assignments C1 through C30 in this example, or update the positions of the cluster centroids mu1 and mu2 in order to keep on reducing this cost function J. Oh, and by the way, this cost function J also has a name in the literature. It's called the distortion function. I don't know that this is a great name, but if you hear someone talk about the K means algorithm and the distortion or the distortion cost function, that's just what this formula J is computing. Let's now take a deeper look at the algorithm and why the algorithm is trying to minimize this cost function J or why it's trying to minimize the distortion. Here on top of copied over the cost function from the previous slide. It turns out that the first part of K means where you assign points to cluster centroids, that turns out to be trying to update C1 through CM to try to minimize the cost function J as much as possible while holding mu1 through muK fix. And the second step in contrast, where you move the cluster centroid, it turns out that that is trying to leave C1 through CM fix, but to update mu1 through muK to try to minimize the cost function or the distortion as much as possible. Let's take a look at why this is the case. During the first step, if you want to choose the values of C1 through CM or save a particular value of Ci to try to minimize this, well, what would make Xi minus mu Ci as small as possible? This is the distance or the square distance between a training example Xi and the location of the cluster centroid to which it's been assigned. So if you want to minimize this distance or the square distance, what you should do is assign Xi to the closest cluster centroid. So to take a simplified example, if you have two cluster centroids, say cluster centroids one and two, and just a single training example Xi, if you were to assign it to cluster centroid one, this square distance here would be this large distance, well, squared. And if you were to assign it to cluster centroid two, then this squared distance would be the square of this much smaller distance. So if you want to minimize this term, you would take Xi and assign it to the closer cluster centroid, which is exactly what the algorithm is doing up here. So that's why the step where you assign points to cluster centroids is choosing the values for Ci to try to minimize J without changing mu1 through muK for now, but just choosing the values of C1 through Cm to try to make these terms as small as possible. How about the second step of the K-means algorithm? That is to move the cluster centroids. It turns out that choosing muK to be average at the mean of the points assigned is the choice of these terms mu that will minimize this expression. To take a simplified example, say you have a cluster with just two points assigned to it, shown as follows. And so with the cluster centroid here, the average of the squared distances would be a distance of one here squared plus this distance here, which is nine squared. And then you take the average of these two numbers. And so that turns out to be one half of one plus 81, which turns out to be 41. But if you were to take the average of these two points, so one plus 11 over two, that's equal to six. And if you were to move the cluster centroid over here to the middle, then the average of these two squared distances turns out to be a distance of five and five here. So you end up with one half of five squared plus five squared, which is equal to 25. And this is a much smaller average squared distance than 41. And in fact, you can play around with the location of this cluster centroid and maybe convince yourself that taking this mean location, this average location in the middle of these two training samples, that is really the value that minimizes the squared distance. So the fact that the k-means algorithm is optimizing a cost function j means that it is guaranteed to converge. That is, on every single iteration, the distortion cost function should go down or stay the same. But if it ever fails to go down or stay the same in the worst case, if it ever goes up, that means there's a bug in the code. It should never go up because every single step of k-means is setting the value c i and mu k to try to reduce the cost function. Also if the cost function ever stops going down, that also gives you one way to test if k-means has converged. Once there's a single iteration where it stays the same, that usually means k-means has converged and you should just stop running the algorithm even further. Or in some rare cases, you will run k-means for a long time and the cost function or the distortion is just going down very, very slowly. And that's a bit like gradient descent where maybe running it even longer might help a bit. But if the rate at which the cost function is going down has become very, very slow, you might also just say, this is good enough, I'm just going to say it's close enough to convergence and not spend even more compute cycles running the algorithm for even longer. So these are some of the ways that computing the cost function is helpful. It helps you figure out if the algorithm has converged. It turns out that there's one other very useful way to take advantage of the cost function, which is to use multiple different random initializations of the cluster centroids. It turns out if you do this, you can often find much better clusters using k-means. Let's take a look at the next video of how to do that.
[{"start": 0.0, "end": 7.84, "text": " In the earlier courses, courses one and two of the specialization, you saw a lot of supervised"}, {"start": 7.84, "end": 14.52, "text": " learning algorithms as ticket training set, posing a cost function, and then using gradient"}, {"start": 14.52, "end": 18.56, "text": " descent or some other algorithms to optimize that cost function."}, {"start": 18.56, "end": 24.52, "text": " It turns out that the Q means algorithm that you saw in the last video is also optimizing"}, {"start": 24.52, "end": 26.68, "text": " a specific cost function."}, {"start": 26.68, "end": 31.8, "text": " Although the optimization algorithm that it uses to optimize that is not gradient descent,"}, {"start": 31.8, "end": 36.04, "text": " it's actually the algorithm that you already saw in the last video."}, {"start": 36.04, "end": 38.519999999999996, "text": " Let's take a look at what all this means."}, {"start": 38.519999999999996, "end": 43.0, "text": " Let's take a look at what is the cost function for K means."}, {"start": 43.0, "end": 48.96, "text": " To get started, as a reminder, this is the notation we've been using where Ci is the"}, {"start": 48.96, "end": 57.72, "text": " index of the cluster, so Ci is some number from 1 through K, of the index of the cluster"}, {"start": 57.72, "end": 64.72, "text": " to which training example Xi is currently assigned, and mu K is the location of cluster"}, {"start": 64.72, "end": 66.92, "text": " centroid K."}, {"start": 66.92, "end": 76.08, "text": " Let me introduce one more piece of notation, which is when lowercase k equals Ci, so mu"}, {"start": 76.08, "end": 84.84, "text": " subscript Ci is the cluster centroid of the cluster to which example Xi has been assigned."}, {"start": 84.84, "end": 91.28, "text": " So for example, if I were to look at some training example, say training example 10,"}, {"start": 91.28, "end": 97.16, "text": " and I were to ask, what's the location of the cluster centroid to which the 10th training"}, {"start": 97.16, "end": 98.75999999999999, "text": " example has been assigned?"}, {"start": 98.75999999999999, "end": 102.03999999999999, "text": " Well, I would then look up C10."}, {"start": 102.04, "end": 107.84, "text": " This would give me a number from 1 to K that tells me was example 10 assigned to the red"}, {"start": 107.84, "end": 117.0, "text": " or the blue or some other cluster centroid, and then mu subscript C10 is the location"}, {"start": 117.0, "end": 120.94000000000001, "text": " of the cluster centroid to which X10 has been assigned."}, {"start": 120.94000000000001, "end": 129.20000000000002, "text": " So armed with this notation, let me now write out the cost function that K means turns out"}, {"start": 129.20000000000002, "end": 131.04000000000002, "text": " to be minimizing."}, {"start": 131.04, "end": 140.6, "text": " The cost function J, which is a function of C1 through CM, these are all the assignments"}, {"start": 140.6, "end": 148.26, "text": " of points to cluster centroids, as well as mu 1 through mu K. These are the locations"}, {"start": 148.26, "end": 155.23999999999998, "text": " of all the cluster centroids as defined as this expression on the right."}, {"start": 155.24, "end": 165.20000000000002, "text": " It is the average, so 1 over M of sum from i equals 1 to M of the squared distance between"}, {"start": 165.20000000000002, "end": 171.64000000000001, "text": " every training example Xi as i goes from 1 through M. It is the square distance between"}, {"start": 171.64000000000001, "end": 175.8, "text": " Xi and mu subscript Ci."}, {"start": 175.8, "end": 178.72, "text": " So this quantity up here."}, {"start": 178.72, "end": 184.52, "text": " In other words, the cost function for K means is the average squared distance between every"}, {"start": 184.52, "end": 191.72, "text": " training example Xi and the location of the cluster centroid to which the training example"}, {"start": 191.72, "end": 193.24, "text": " Xi has been assigned."}, {"start": 193.24, "end": 200.08, "text": " So for this example up here, we would be measuring the distance between X10 and mu subscript"}, {"start": 200.08, "end": 205.48000000000002, "text": " C10, the cluster centroid to which X10 has been assigned, and taking the square of that"}, {"start": 205.48000000000002, "end": 206.48000000000002, "text": " distance."}, {"start": 206.48000000000002, "end": 210.36, "text": " And that would be one of the terms over here that we're averaging over."}, {"start": 210.36, "end": 217.68, "text": " And it turns out that what the K means algorithm is doing is trying to find assignments of"}, {"start": 217.68, "end": 223.54000000000002, "text": " points to cluster centroids, as well as find locations of cluster centroids that minimizes"}, {"start": 223.54000000000002, "end": 225.20000000000002, "text": " the squared distance."}, {"start": 225.20000000000002, "end": 233.48000000000002, "text": " Visually, here's what you saw part way into the run of K means in an earlier video."}, {"start": 233.48000000000002, "end": 238.60000000000002, "text": " And at this step, the cost function, if you were to compute it, would be to look at every"}, {"start": 238.6, "end": 243.6, "text": " one of the blue points and measure these distances and compute the square."}, {"start": 243.6, "end": 250.28, "text": " And then also similarly look at every one of the red points and compute these distances"}, {"start": 250.28, "end": 252.14, "text": " and compute the square."}, {"start": 252.14, "end": 256.8, "text": " And then the average of the squares of all of these differences for the red and the blue"}, {"start": 256.8, "end": 267.48, "text": " points is the value of the cost function J at this particular configuration of the parameters"}, {"start": 267.48, "end": 270.64000000000004, "text": " for K means."}, {"start": 270.64000000000004, "end": 275.6, "text": " And what it will do on every step is try to update the cluster assignments C1 through"}, {"start": 275.6, "end": 282.20000000000005, "text": " C30 in this example, or update the positions of the cluster centroids mu1 and mu2 in order"}, {"start": 282.20000000000005, "end": 284.76, "text": " to keep on reducing this cost function J."}, {"start": 284.76, "end": 290.72, "text": " Oh, and by the way, this cost function J also has a name in the literature."}, {"start": 290.72, "end": 294.48, "text": " It's called the distortion function."}, {"start": 294.48, "end": 298.54, "text": " I don't know that this is a great name, but if you hear someone talk about the K means"}, {"start": 298.54, "end": 304.32, "text": " algorithm and the distortion or the distortion cost function, that's just what this formula"}, {"start": 304.32, "end": 307.20000000000005, "text": " J is computing."}, {"start": 307.20000000000005, "end": 311.96000000000004, "text": " Let's now take a deeper look at the algorithm and why the algorithm is trying to minimize"}, {"start": 311.96000000000004, "end": 316.56, "text": " this cost function J or why it's trying to minimize the distortion."}, {"start": 316.56, "end": 321.94, "text": " Here on top of copied over the cost function from the previous slide."}, {"start": 321.94, "end": 328.28, "text": " It turns out that the first part of K means where you assign points to cluster centroids,"}, {"start": 328.28, "end": 335.64, "text": " that turns out to be trying to update C1 through CM to try to minimize the cost function J"}, {"start": 335.64, "end": 341.2, "text": " as much as possible while holding mu1 through muK fix."}, {"start": 341.2, "end": 346.15999999999997, "text": " And the second step in contrast, where you move the cluster centroid, it turns out that"}, {"start": 346.16, "end": 354.8, "text": " that is trying to leave C1 through CM fix, but to update mu1 through muK to try to minimize"}, {"start": 354.8, "end": 358.48, "text": " the cost function or the distortion as much as possible."}, {"start": 358.48, "end": 360.64000000000004, "text": " Let's take a look at why this is the case."}, {"start": 360.64000000000004, "end": 366.88, "text": " During the first step, if you want to choose the values of C1 through CM or save a particular"}, {"start": 366.88, "end": 378.84, "text": " value of Ci to try to minimize this, well, what would make Xi minus mu Ci as small as"}, {"start": 378.84, "end": 380.26, "text": " possible?"}, {"start": 380.26, "end": 387.32, "text": " This is the distance or the square distance between a training example Xi and the location"}, {"start": 387.32, "end": 391.4, "text": " of the cluster centroid to which it's been assigned."}, {"start": 391.4, "end": 396.7, "text": " So if you want to minimize this distance or the square distance, what you should do is"}, {"start": 396.7, "end": 402.52, "text": " assign Xi to the closest cluster centroid."}, {"start": 402.52, "end": 409.08, "text": " So to take a simplified example, if you have two cluster centroids, say cluster centroids"}, {"start": 409.08, "end": 415.96, "text": " one and two, and just a single training example Xi, if you were to assign it to cluster centroid"}, {"start": 415.96, "end": 424.76, "text": " one, this square distance here would be this large distance, well, squared."}, {"start": 424.76, "end": 429.36, "text": " And if you were to assign it to cluster centroid two, then this squared distance would be the"}, {"start": 429.36, "end": 432.12, "text": " square of this much smaller distance."}, {"start": 432.12, "end": 436.48, "text": " So if you want to minimize this term, you would take Xi and assign it to the closer"}, {"start": 436.48, "end": 442.02, "text": " cluster centroid, which is exactly what the algorithm is doing up here."}, {"start": 442.02, "end": 447.15999999999997, "text": " So that's why the step where you assign points to cluster centroids is choosing the values"}, {"start": 447.15999999999997, "end": 454.28, "text": " for Ci to try to minimize J without changing mu1 through muK for now, but just choosing"}, {"start": 454.28, "end": 460.71999999999997, "text": " the values of C1 through Cm to try to make these terms as small as possible."}, {"start": 460.71999999999997, "end": 463.64, "text": " How about the second step of the K-means algorithm?"}, {"start": 463.64, "end": 466.65999999999997, "text": " That is to move the cluster centroids."}, {"start": 466.65999999999997, "end": 474.2, "text": " It turns out that choosing muK to be average at the mean of the points assigned is the"}, {"start": 474.2, "end": 480.73999999999995, "text": " choice of these terms mu that will minimize this expression."}, {"start": 480.74, "end": 487.04, "text": " To take a simplified example, say you have a cluster with just two points assigned to"}, {"start": 487.04, "end": 489.44, "text": " it, shown as follows."}, {"start": 489.44, "end": 495.92, "text": " And so with the cluster centroid here, the average of the squared distances would be"}, {"start": 495.92, "end": 503.92, "text": " a distance of one here squared plus this distance here, which is nine squared."}, {"start": 503.92, "end": 506.72, "text": " And then you take the average of these two numbers."}, {"start": 506.72, "end": 515.94, "text": " And so that turns out to be one half of one plus 81, which turns out to be 41."}, {"start": 515.94, "end": 522.96, "text": " But if you were to take the average of these two points, so one plus 11 over two, that's"}, {"start": 522.96, "end": 524.4, "text": " equal to six."}, {"start": 524.4, "end": 529.48, "text": " And if you were to move the cluster centroid over here to the middle, then the average"}, {"start": 529.48, "end": 537.4, "text": " of these two squared distances turns out to be a distance of five and five here."}, {"start": 537.4, "end": 545.3000000000001, "text": " So you end up with one half of five squared plus five squared, which is equal to 25."}, {"start": 545.3000000000001, "end": 549.5600000000001, "text": " And this is a much smaller average squared distance than 41."}, {"start": 549.5600000000001, "end": 554.24, "text": " And in fact, you can play around with the location of this cluster centroid and maybe"}, {"start": 554.24, "end": 559.72, "text": " convince yourself that taking this mean location, this average location in the middle of these"}, {"start": 559.72, "end": 565.4, "text": " two training samples, that is really the value that minimizes the squared distance."}, {"start": 565.4, "end": 571.84, "text": " So the fact that the k-means algorithm is optimizing a cost function j means that it"}, {"start": 571.84, "end": 573.84, "text": " is guaranteed to converge."}, {"start": 573.84, "end": 580.34, "text": " That is, on every single iteration, the distortion cost function should go down or stay the same."}, {"start": 580.34, "end": 585.94, "text": " But if it ever fails to go down or stay the same in the worst case, if it ever goes up,"}, {"start": 585.94, "end": 587.12, "text": " that means there's a bug in the code."}, {"start": 587.12, "end": 594.36, "text": " It should never go up because every single step of k-means is setting the value c i and"}, {"start": 594.36, "end": 599.08, "text": " mu k to try to reduce the cost function."}, {"start": 599.08, "end": 604.36, "text": " Also if the cost function ever stops going down, that also gives you one way to test"}, {"start": 604.36, "end": 606.5600000000001, "text": " if k-means has converged."}, {"start": 606.56, "end": 612.2399999999999, "text": " Once there's a single iteration where it stays the same, that usually means k-means has converged"}, {"start": 612.2399999999999, "end": 616.3199999999999, "text": " and you should just stop running the algorithm even further."}, {"start": 616.3199999999999, "end": 621.54, "text": " Or in some rare cases, you will run k-means for a long time and the cost function or the"}, {"start": 621.54, "end": 625.1199999999999, "text": " distortion is just going down very, very slowly."}, {"start": 625.1199999999999, "end": 628.88, "text": " And that's a bit like gradient descent where maybe running it even longer might help a"}, {"start": 628.88, "end": 629.88, "text": " bit."}, {"start": 629.88, "end": 634.5799999999999, "text": " But if the rate at which the cost function is going down has become very, very slow,"}, {"start": 634.58, "end": 638.2, "text": " you might also just say, this is good enough, I'm just going to say it's close enough to"}, {"start": 638.2, "end": 644.76, "text": " convergence and not spend even more compute cycles running the algorithm for even longer."}, {"start": 644.76, "end": 648.6, "text": " So these are some of the ways that computing the cost function is helpful."}, {"start": 648.6, "end": 652.48, "text": " It helps you figure out if the algorithm has converged."}, {"start": 652.48, "end": 659.2, "text": " It turns out that there's one other very useful way to take advantage of the cost function,"}, {"start": 659.2, "end": 665.0400000000001, "text": " which is to use multiple different random initializations of the cluster centroids."}, {"start": 665.0400000000001, "end": 669.88, "text": " It turns out if you do this, you can often find much better clusters using k-means."}, {"start": 669.88, "end": 689.92, "text": " Let's take a look at the next video of how to do that."}]