8.7 Clustering | Choosing the number of clusters -- [Machine Learning | Andrew Ng]
 The k-means algorithm requires as one of its inputs k, the number of clusters you want it to find. But how do you decide how many clusters to use? Do you want two clusters or three clusters or five clusters or ten clusters? Let's take a look. For a lot of clustering problems, the right value of k is truly ambiguous. If I were to show different people the same data set and ask how many clusters do you see, there will definitely be people that will say, oh, looks like there are two distinct clusters and they would be right. And there would also be others that will see actually four distinct clusters and they would also be right. Because clustering is an unsupervised learning algorithm, you're not given the quote right answers in the form of specific labels to try to replicate. And so there are a lot of applications where the data itself does not give a clear indicator for how many clusters there are in it. And I think it truly is ambiguous if this data has two or four or maybe three clusters. If you take, say, the red one here and the two blue ones here, say. If you look at the academic literature on k-means, there are a few techniques to try to automatically choose the number of clusters to use for a certain application. I'll briefly mention one here that you may see others refer to, although I have to say I personally do not use this method myself. But one way to try to choose the value of k is called the elbow method. And what that does is you would run k-means with a variety of values of k and plot the cost function or the distortion function j as a function of the number of clusters. What you find is that when you have very few clusters, say one cluster, the distortion function of the cost function j will be high. And as you increase the number of clusters, it will go down, maybe as follows. And one method for trying to choose the number of clusters is called the elbow method. And what that does is look at the cost function as a function of the number of clusters and see if there's a bend in the curve. And we call that an elbow. And if the curve looks like this, you say, well, it looks like the cost function is decreasing rapidly until we get to three clusters, but it decreases more slowly after that. So let's choose k equals three. And this is called an elbow, by the way, because think of it as analogous to that's your hand and that's your elbow over here. So plotting the cost function as a function of k could help. It could help you gain some insight. I personally hardly ever use the elbow method myself to choose the right number of clusters because I think for a lot of applications, the right number of clusters is truly ambiguous. And you find that a lot of cost functions look like this, where it just decreases smoothly and it doesn't have a clear elbow by which you could use to pick the value of k. By the way, one technique that does not work is to choose k so as to minimize the cost function j because doing so would cause you to almost always just choose the largest possible value of k because having more clusters will pretty much always reduce the cost function j. So choosing k to minimize the cost function j is not a good technique. So how do you choose the value of k in practice? Then you're running k-means in order to get clusters to use for some later or some downstream purpose. That is, you're going to take the clusters and do something with those clusters. So what I usually do and what I recommend you do is to evaluate k-means based on how well it performs for that later downstream purpose. Let me illustrate the example of t-shirt sizing. One thing you could do is run k-means on this data set to find three clusters, in which case you may find clusters like that. And this would be how you size your small, medium, and large t-shirts. But how many t-shirt sizes should there be? Well it's ambiguous. If you were to also run k-means with five clusters, you might get clusters that look like this, and this would let you size t-shirts according to extra small, small, medium, large, and extra large. And so both of these are completely valid and completely fine groupings of the data into clusters. But whether you want to use three clusters or five clusters can now be decided based on what makes sense for your t-shirt business. There's a trade-off between how well the t-shirts will fit depending on whether you have three sizes or five sizes, but there will be extra costs as well associated with manufacturing and shipping five types of t-shirts instead of three different types of t-shirts. So what I would do in this case is to run k-means with k equals three and k equals five, and then look at these two solutions to see based on the trade-off between fit of t-shirts with more sizes results in better fit versus the extra cost of making more t-shirts where making fewer t-shirts is simpler and less expensive to try to decide what makes sense for the t-shirt business. When you get to the programming exercise, you also see there an application of k-means to image compression. This is actually one of the most fun visual examples of k-means. And there you see that there'll be a trade-off between the quality of the compressed image, that is how good the image looks versus how much you can compress the image, that is the size of the image. And there you see that there will be a trade-off between the quality of the compressed image, that is how good the image looks versus how much you can compress the image to save this space. And in that programming exercise, you see that you can use that trade-off to maybe manually decide what's the best value of k based on how good you want the image to look versus how large you want the compressed image size to be. So that's it for the k-means clustering algorithm. Congrats on learning your first unsupervised learning algorithm. You now know not just how to do supervised learning, but also unsupervised learning. And I hope you also have fun with the practice lab. It's actually one of the most fun exercises I know of for k-means. And with that, we're ready to move on to our second unsupervised learning algorithm, which is anomaly detection. How do you look at a data set and find unusual or anomalous things in it? This turns out to be another one of the most commercially important applications of unsupervised learning. I've used this myself many times in many different applications. Let's go on to the next video to talk about anomaly detection.
[{"start": 0.0, "end": 7.96, "text": " The k-means algorithm requires as one of its inputs k, the number of clusters you want it"}, {"start": 7.96, "end": 8.96, "text": " to find."}, {"start": 8.96, "end": 11.96, "text": " But how do you decide how many clusters to use?"}, {"start": 11.96, "end": 15.88, "text": " Do you want two clusters or three clusters or five clusters or ten clusters?"}, {"start": 15.88, "end": 17.38, "text": " Let's take a look."}, {"start": 17.38, "end": 24.2, "text": " For a lot of clustering problems, the right value of k is truly ambiguous."}, {"start": 24.2, "end": 29.52, "text": " If I were to show different people the same data set and ask how many clusters do you"}, {"start": 29.52, "end": 35.68, "text": " see, there will definitely be people that will say, oh, looks like there are two distinct"}, {"start": 35.68, "end": 39.2, "text": " clusters and they would be right."}, {"start": 39.2, "end": 48.120000000000005, "text": " And there would also be others that will see actually four distinct clusters and they would"}, {"start": 48.120000000000005, "end": 50.8, "text": " also be right."}, {"start": 50.8, "end": 56.92, "text": " Because clustering is an unsupervised learning algorithm, you're not given the quote right"}, {"start": 56.92, "end": 61.6, "text": " answers in the form of specific labels to try to replicate."}, {"start": 61.6, "end": 68.16, "text": " And so there are a lot of applications where the data itself does not give a clear indicator"}, {"start": 68.16, "end": 70.96000000000001, "text": " for how many clusters there are in it."}, {"start": 70.96000000000001, "end": 78.76, "text": " And I think it truly is ambiguous if this data has two or four or maybe three clusters."}, {"start": 78.76, "end": 83.0, "text": " If you take, say, the red one here and the two blue ones here, say."}, {"start": 83.0, "end": 88.36, "text": " If you look at the academic literature on k-means, there are a few techniques to try"}, {"start": 88.36, "end": 94.32, "text": " to automatically choose the number of clusters to use for a certain application."}, {"start": 94.32, "end": 100.16, "text": " I'll briefly mention one here that you may see others refer to, although I have to say"}, {"start": 100.16, "end": 105.8, "text": " I personally do not use this method myself."}, {"start": 105.8, "end": 112.32, "text": " But one way to try to choose the value of k is called the elbow method."}, {"start": 112.32, "end": 120.75999999999999, "text": " And what that does is you would run k-means with a variety of values of k and plot the"}, {"start": 120.75999999999999, "end": 126.96, "text": " cost function or the distortion function j as a function of the number of clusters."}, {"start": 126.96, "end": 132.44, "text": " What you find is that when you have very few clusters, say one cluster, the distortion"}, {"start": 132.44, "end": 135.4, "text": " function of the cost function j will be high."}, {"start": 135.4, "end": 143.52, "text": " And as you increase the number of clusters, it will go down, maybe as follows."}, {"start": 143.52, "end": 149.20000000000002, "text": " And one method for trying to choose the number of clusters is called the elbow method."}, {"start": 149.20000000000002, "end": 154.84, "text": " And what that does is look at the cost function as a function of the number of clusters and"}, {"start": 154.84, "end": 159.28, "text": " see if there's a bend in the curve."}, {"start": 159.28, "end": 162.20000000000002, "text": " And we call that an elbow."}, {"start": 162.2, "end": 168.11999999999998, "text": " And if the curve looks like this, you say, well, it looks like the cost function is decreasing"}, {"start": 168.11999999999998, "end": 173.35999999999999, "text": " rapidly until we get to three clusters, but it decreases more slowly after that."}, {"start": 173.35999999999999, "end": 176.44, "text": " So let's choose k equals three."}, {"start": 176.44, "end": 183.39999999999998, "text": " And this is called an elbow, by the way, because think of it as analogous to that's your hand"}, {"start": 183.39999999999998, "end": 187.6, "text": " and that's your elbow over here."}, {"start": 187.6, "end": 191.88, "text": " So plotting the cost function as a function of k could help."}, {"start": 191.88, "end": 194.68, "text": " It could help you gain some insight."}, {"start": 194.68, "end": 201.48, "text": " I personally hardly ever use the elbow method myself to choose the right number of clusters"}, {"start": 201.48, "end": 207.32, "text": " because I think for a lot of applications, the right number of clusters is truly ambiguous."}, {"start": 207.32, "end": 214.04, "text": " And you find that a lot of cost functions look like this, where it just decreases smoothly"}, {"start": 214.04, "end": 220.28, "text": " and it doesn't have a clear elbow by which you could use to pick the value of k."}, {"start": 220.28, "end": 226.32, "text": " By the way, one technique that does not work is to choose k so as to minimize the cost"}, {"start": 226.32, "end": 232.6, "text": " function j because doing so would cause you to almost always just choose the largest possible"}, {"start": 232.6, "end": 238.2, "text": " value of k because having more clusters will pretty much always reduce the cost function"}, {"start": 238.2, "end": 239.2, "text": " j."}, {"start": 239.2, "end": 244.48, "text": " So choosing k to minimize the cost function j is not a good technique."}, {"start": 244.48, "end": 249.04, "text": " So how do you choose the value of k in practice?"}, {"start": 249.04, "end": 254.67999999999998, "text": " Then you're running k-means in order to get clusters to use for some later or some downstream"}, {"start": 254.67999999999998, "end": 256.2, "text": " purpose."}, {"start": 256.2, "end": 260.96, "text": " That is, you're going to take the clusters and do something with those clusters."}, {"start": 260.96, "end": 266.92, "text": " So what I usually do and what I recommend you do is to evaluate k-means based on how"}, {"start": 266.92, "end": 272.4, "text": " well it performs for that later downstream purpose."}, {"start": 272.4, "end": 276.65999999999997, "text": " Let me illustrate the example of t-shirt sizing."}, {"start": 276.66, "end": 281.92, "text": " One thing you could do is run k-means on this data set to find three clusters, in which"}, {"start": 281.92, "end": 285.92, "text": " case you may find clusters like that."}, {"start": 285.92, "end": 290.88000000000005, "text": " And this would be how you size your small, medium, and large t-shirts."}, {"start": 290.88000000000005, "end": 293.92, "text": " But how many t-shirt sizes should there be?"}, {"start": 293.92, "end": 295.68, "text": " Well it's ambiguous."}, {"start": 295.68, "end": 303.38, "text": " If you were to also run k-means with five clusters, you might get clusters that look"}, {"start": 303.38, "end": 310.36, "text": " like this, and this would let you size t-shirts according to extra small, small, medium, large,"}, {"start": 310.36, "end": 312.24, "text": " and extra large."}, {"start": 312.24, "end": 317.6, "text": " And so both of these are completely valid and completely fine groupings of the data"}, {"start": 317.6, "end": 319.68, "text": " into clusters."}, {"start": 319.68, "end": 325.44, "text": " But whether you want to use three clusters or five clusters can now be decided based"}, {"start": 325.44, "end": 329.71999999999997, "text": " on what makes sense for your t-shirt business."}, {"start": 329.72, "end": 334.12, "text": " There's a trade-off between how well the t-shirts will fit depending on whether you have three"}, {"start": 334.12, "end": 341.52000000000004, "text": " sizes or five sizes, but there will be extra costs as well associated with manufacturing"}, {"start": 341.52000000000004, "end": 346.52000000000004, "text": " and shipping five types of t-shirts instead of three different types of t-shirts."}, {"start": 346.52000000000004, "end": 352.68, "text": " So what I would do in this case is to run k-means with k equals three and k equals five,"}, {"start": 352.68, "end": 360.48, "text": " and then look at these two solutions to see based on the trade-off between fit of t-shirts"}, {"start": 360.48, "end": 367.0, "text": " with more sizes results in better fit versus the extra cost of making more t-shirts where"}, {"start": 367.0, "end": 372.08, "text": " making fewer t-shirts is simpler and less expensive to try to decide what makes sense"}, {"start": 372.08, "end": 374.08, "text": " for the t-shirt business."}, {"start": 374.08, "end": 379.92, "text": " When you get to the programming exercise, you also see there an application of k-means"}, {"start": 379.92, "end": 387.28000000000003, "text": " to image compression. This is actually one of the most fun visual examples of k-means."}, {"start": 387.28000000000003, "end": 393.18, "text": " And there you see that there'll be a trade-off between the quality of the compressed image,"}, {"start": 393.18, "end": 399.48, "text": " that is how good the image looks versus how much you can compress the image, that is the"}, {"start": 399.48, "end": 401.44, "text": " size of the image."}, {"start": 401.44, "end": 405.84000000000003, "text": " And there you see that there will be a trade-off between the quality of the compressed image,"}, {"start": 405.84, "end": 412.11999999999995, "text": " that is how good the image looks versus how much you can compress the image to save this"}, {"start": 412.11999999999995, "end": 419.15999999999997, "text": " space. And in that programming exercise, you see that you can use that trade-off to maybe"}, {"start": 419.15999999999997, "end": 424.84, "text": " manually decide what's the best value of k based on how good you want the image to look"}, {"start": 424.84, "end": 429.64, "text": " versus how large you want the compressed image size to be."}, {"start": 429.64, "end": 435.59999999999997, "text": " So that's it for the k-means clustering algorithm. Congrats on learning your first"}, {"start": 435.6, "end": 440.40000000000003, "text": " unsupervised learning algorithm. You now know not just how to do supervised learning, but"}, {"start": 440.40000000000003, "end": 445.92, "text": " also unsupervised learning. And I hope you also have fun with the practice lab. It's"}, {"start": 445.92, "end": 451.24, "text": " actually one of the most fun exercises I know of for k-means."}, {"start": 451.24, "end": 456.64000000000004, "text": " And with that, we're ready to move on to our second unsupervised learning algorithm, which"}, {"start": 456.64000000000004, "end": 463.02000000000004, "text": " is anomaly detection. How do you look at a data set and find unusual or anomalous things"}, {"start": 463.02, "end": 468.47999999999996, "text": " in it? This turns out to be another one of the most commercially important applications"}, {"start": 468.47999999999996, "end": 473.96, "text": " of unsupervised learning. I've used this myself many times in many different applications."}, {"start": 473.96, "end": 493.96, "text": " Let's go on to the next video to talk about anomaly detection."}]