Python Machine Learning Tutorial #11 - How K Means Clustering Works

Key Takeaways

hey guys and welcome back from their Python machine learning tutorial so in today's video we're gonna be talking about our first unsupervised learning algorithm which is called k-means clustering now this algorithm is different than the other ones that we've been using because we don't actually have to feed the labels for our data points when we are training the model all we do is we just give it a bunch of features that make up one point we don't say which points are which so in the case of what we're gonna be doing in the next video classifying handwritten digits we don't say this digital one this digits of five this digits of six we just say this is a digit this is a digit and this is a digit and then our computer has to figure out what makes what digit okay whereas before we were giving both like let's say the same example what made up the digit and we were giving the digit and all it had to do then was be able to predict given some data what digit it was doing so it was had a lot easier job than actually having to determine what features make up for example let's say a 7 or an 8 right in the computer and you'll see this as we go through the example now what I actually want to start doing is just I'm just gonna run this script by the way this is not exactly what we're gonna be making in the next video I just stole this off the SK learn website but it gives a really good visualization as to how k-means clustering works so wait for this to run and we get a lovely photo here that might look kind of confusing but essentially decay in k-means clustering stands for how many clusters now in the case of handwritten digits which is what we're gonna be classifying we have the digits 0 through 9 which is 10 digits so in this case you can see that we have 10 X is okay 10 white X's now these white X's are known as centroids and they are what's going to determine what a given data point what cluster that belongs to so you can see we have 10 clusters and they're all represented by all these different colors here right so anything that this falls inside of this red box here is gonna be a part of the red class which could be like a 6 it could be a 7 it could be an 8 we have to determine that anything that falls inside of this Brown point here is going to be another class anything inside the green and and so on okay and that's exactly how K means works it attempts to divide our graph of data points into a bunch of different let's say sections like this and then based on what section given point is that were trying to predict we can just say that it is a part of the closest what's known as this one of these X's okay so if we had a data point let's say you got to see my mouse right up here it's gonna say it's part of this pink place because it's closest to this white X so I'm gonna go through an example here but I just want to show this so you can kind of see how it works when we were dealing with a ton of different clusters because I'm just gonna show you an example to to make it easier so you might have heard of something called centroids before so essentially the way this algorithm works is we're gonna start off by creating two centroids in a random position in our graph so typically we're going to deal with multi-dimensional graphs right where we have like ten twenty thirty different features for each of our data points right so we'll just randomly choose a place to put two centroids on our graph if we're dealing with K equals two now if we were gonna deal with K equals like five K equals ten K equals twenty that's how many centroids we would put onto our graph in a random position and you'll see how this works in a second okay so I'm just gonna put a centroid and I'm gonna mark these by triangles here and I'm gonna put a centroid this blue one up here okay just in random positions now note that I could put them like right beside each other it doesn't matter where I put them it just completely random that we're gonna generate this okay now what we're gonna do once we have these two random centroids and we're gonna do this a bunch of time so don't worry if if it's like how was this gonna work it's gonna happen a bunch of times what we're gonna do is we're gonna repeat the process that I'm just about to go through so we're gonna draw a straight line between our two centuries okay and then we're gonna try to divide all of the points that are here to be either a part of this red Sun centroid or this blue centroid okay so what we do is that we now will take a line like this and we'll draw it through the midpoint of the line connecting our centroids and anything on this side is gonna be a part of the red centroid and anything on this side is gonna be part of the blue Center okay so that's what we do first of all so I'll get rid of all this drawing and we'll just say that she will go back here then now we're gonna assign this points gonna be blue like this like all these points that were on that side of the line will be blue and then all the other points are going to be red like this so red red red red red now how does this work and why are we doing this well essentially the reason that we'd say this point here is a part of the red centroid is because it's closer to the red centroid than it is to the blue centroid now that goes for every other point we're just gonna find the points that are closest to each centroid we're gonna say okay so is this point closer to the red centroid or the blue centroid whatever one is closer to we're just going to assign it that value so in this case we give it red same thing with these points over here and you know this one actually we might want to say is probably a part of the blue one so I guess we can change that just for the purpose of the example here okay so we'll say that's blue this one might be kind of in between anyways so that's what we're gonna do now that we've done that we need to do something else we need to find the center of these points so essentially all these blue points here we want to put this centroid in the middle of these blue points so what we're gonna do is well we're gonna erase this centroid and we're gonna find the middle of these points now the way we can do this so I'm gonna say the middle is probably somewhere about like here the way that we can do this is by just simply taking the average of these points so what we do is we take x1 plus x2 plus x3 for all of our points all of our blue points and we divide it by the amount of points so we'll say the amount of points is n now that will give us the X 1 coordinate or certain like so X 1 1 X 2 1 like if you're talking about this is 2nd point this is third point I think you guys get that for like the x coordinates anyways so we'll do that that will give us the first coordinate for the centroid then what we'll do is we'll do the same thing except now we'll talk about x2 so we'll say like point 2 x2 plus point 1 x2 plus point 3 x2 and again we'll divide that by the number of points and that'll give us the next coordinate for our century and that's how we can determine the the middle of these kind of data points okay we render the exact same thing for our red centroid so what we'll do now is we'll take this and we'll draw our red centroid let's say somewhere about here okay and again the way we did that we just took the average of the coordinates for all of the points that are red and all the points that are blue so now what we're gonna do is we're gonna repeat the steps that we just did so we're gonna again we're gonna draw a line between these two centroids we're gonna find the midpoint of this line and we're just gonna draw ninety degrees down like this okay and now what we're gonna do is we're gonna reassign points so now we're gonna we're gonna forget that these points were blue and these points were red and we're gonna reassign them so in this case we need to change well this red point to blue and we need to change this blue point to red right because again now this point is closer to the red centroid that is to the blue centroid so it's gonna be red and then maybe with this one that was red before it's now close to the blue centroid so it has to be blue and we're gonna repeat this process until eventually we get no changes between our data points right so now again what we're gonna do is we're going to redraw our centroids so we need to find the average once again except this time when we find the average we're gonna use the what do you call it the new points that we just created so the red centroid maybe it goes like something like this and the blue centroid maybe goes somewhere around here like that okay and now that we have the average we render the exact same thing and we're just gonna keep going until eventually we have no change so if I do this and I find the midpoint and then I draw a straight line well let's just pretend that like this what do you call it this point is over here on this side well now there's no change between our data points none of the points here have changed to be red and now the points here have changed to be blue so we can officially say that we've clustered our points into two separate clusters right so all the points that are red here and in this side of the graph are gonna be closest to the red centroid so they're red and all the ones on this side are closest to the blue centroid so they're blue so now if we have a black point let's say like up here we say that since it's closest to the blue centroid we should predict it as blue and that's essentially how the k-means algorithm works so we keep going through a bunch of iterations of essentially creating these centroids so I'll bring this one back and then we average the centroid out and we put it in the middle of the points that we just decided were there and we just keep going and keep going until eventually we get to a point where our centroids are so good that every time we redo the calculations nothing changes and our centroid stays in the exact same place I hope that makes sense in terms of how that works in clustering now obviously if we're doing with like three clusters well what we're gonna have to do now is we'll say well this point is gonna be part of the Bloch cluster this point will be a part of the Bloch cluster as well because it's closest to the Bloch centroid and then we'll do the exact same thing except we're just gonna repeat the process with three centroids right instead of two and that is how k-means clustering works and now it's time to talk quickly about like some advantages disadvantages of it so essentially speed okay so let's think about this realistically we have two for every single point in our data set determine the distance between not only one of the centroids but the other century which means that if we have let's say we bump this up to four right now we have to do two times the amount of calculations for every single point because we got to determine the distance from this point to here to here until two other centroids and then we have to now figure out which one is closest and assign this point to that centroid right we have to do that for every single one of our points which means that we're gonna have like the number of points so let's say P multiply it I'll just do that by a dot by the number of centroids which will be C but now we don't only have to do this once we have to do this until every single data point is what do you call it not moving right until we get to a point where our centroids are so well defined that we're not moving so that's now by the number of iterations right but guess what we don't normally have to do with this many times we have to do it based on how many features we have because if we have x1 we have x2 and let's say we have up to 700 which is actually very possible that we can have that many features we now have to do this 700 times so times the number of features I think I butchered that word but anyways you guys know what I mean okay so we have to do the number of data points times the number of centroids times the number of iterations so how many times we resent are those centroids and change the data points times the amount of features so that is well it's gonna take a long time compared to some of our other machine learning algorithms but it's actually a lot slower or a lot faster sorry then some other clustering algorithms so you can imagine though like if you have a ton of features and a ton of data points this is gonna take a decent amount of time to perform for us it's not gonna take more than like 30 seconds but if you have a ton of features and a ton of data points then it's gonna take a long time because right si is probably not gonna change that many that much because it's probably only gonna be up to like 10 or 20 for the amount of centroids because you're not gonna have that many different classes and the number of iterations well this could be enough like a few hundred but our data points is probably gonna be the most influential parameter here right so yeah so anyways let's just go back to this example really quickly I'll talk about it one last time with the image here okay so it's having some weird issue with my mouse but anyways we'll run this now and let's look at the centroids and now we hopefully have a better idea of exactly what we've done here right so these centroids started off in random positions maybe we had one up here we had one down here we had them all over and essentially we found the points of her closest to them we said that it's gonna be that centroid like it's gonna be a part of that we average them out so we move the centroid to be in the middle of all those points that are belonging to that centroid then what we did was we perform that operation again and again and again and again until eventually we get something that looks like this where every time that we find points that are closest to each centroid and we average them out we're not we're not moving the centroid at all right so here like final points all these points that are here if we take the average of all of these points and we move the centroid it doesn't move and that's how we know that we essentially found the best possible cluster for our data set and this is just done in two dimensions just so you can see but obviously this is happening in like a crazy high dimension that's just impossible to visualize so anyways that is how K means clustering works as always if you guys have questions please don't hesitate to ask me in the comments you can join my discord server ask for help on there as well and make sure to follow my Twitter in the next video we're gonna get into actually using the k-means clustering algorithm and then we'll be done with machine learning at least for like a week or so until we move into some more neural networks [Music]