K-Means Clustering From Scratch in Python (Mathematical)

Key Takeaways

what is going on guys welcome back in this video today we're going to learn how to implement k-means clustering from scratch in Python so let us get right into it [Music] all right so we're going to implement the k-means clustering algorithm from scratch in this video today and we're going to start here with a theoretical background first so understanding what k-means clustering is how it works how it is computed mathematically what the different steps are and then we're going to put all of this into python code from scratch meaning we're only going to use numpy so that we can work with arrays efficiently but we're not going to use any machine learning modules or packages like scikit-learn for example we're going to use core Python and numpy so we're going to get started here briefly with a theoretical part so I'm going to open up my paint here and I think a lot of you guys will probably have an idea of what k-means clustering is or at least what clustering is it is a an unsupervised machine learning algorithm meaning we have unlabeled data and we try to find clusters in that data now maybe you know what classification is so classification we already implemented the K nearest Neighbors classifier from scratch on this channel uh classification is I have some data points here let's say in two dimensions and um I know for example that all of these points are the red class and I know that all of these points here are the yellow class and I know that all of these points here are the turquoise class and so on so I already know what these points are and then I get a new point for example this one here and I don't know what it is and I ask my model which in this case would be very easy to to answer um which class does this probably belong to and then K nearest neighbors would tell me okay this is probably turquoise so I classified it now with clustering we have a slightly different approach because we Have No Label so in clustering clustering we have still data points here again in two Dimensions but they are unlabeled so they're not having a class assigned to them and of course real real data doesn't look like that first of all real data is oftentimes High dimensional but also not that well separated you will usually not find data where you can find clusters so easily you will oftentimes have more chaotic data more noisy data uh but that would be clustering right here so I don't have any labels here but I want to find clusters so I want to end up with cluster one cluster two cluster three now I don't know what these are but I know that there's separate clusters I detect the Clusters here um and K means K means clustering is essentially a method to do that so what we do with k-means is we Define how many clusters are we looking for this is the K here so K clusters is what we're looking for in this case for example uh we could try to find three clusters which would be a very obvious example but we could also try to find five clusters or two clusters it doesn't matter we can Define K how we want of course there are strategies to choose K efficiently you can try to to evaluate different case with certain metrics this is beyond the scope of this video here I can make another video on that in the future but there are strategies on choosing the correct K but essentially you just choose a k based on whatever strategy you have so for example we could say we're looking for three clusters here and how do we find these clusters here mathematically is we initialize the centroids so the cluster centers randomly so I can say okay the first cluster has its Center here which of course doesn't make sense because there's no data here then the second one has the cluster Center here and the third one has the cluster Center here for example just randomly it could also be all of them down here doesn't matter now those are just randomly initialized centroids and what we can do now is or what we do in k-means is we calculate for each data point here the distance between these cluster centers so I take this point here for example and I calculate the distance to this yellow centroid and I do the same thing with a turquoise centroid I do the same thing with a red centroid and I do this for every single data point so I compute the distances here and then I say okay which one of those three centroids is the closest to this point and I say okay in this case it's the yellow one so this point will now have a yellow class you could say or this is part of the yellow cluster and maybe all of these are part of the yellow cluster here maybe some of these here are actually part of the uh where's my turquoise some of these might be part of the turquoise cluster down here maybe and those are again yellow then all of these are probably going to be red and all these are going to be turquoise right so that is the first step now the next step is we take the centroids with these assignments that we have now so knowing that these are now red knowing that these up here are yellow some of these are turquoise down here we have only turquoise we take the centroids and we reposition them at the mean position between all these points so for example for yellow since all the yellow points are here the new yellow centroid would be probably here in the middle now for red it's quite similar and quite simple as well we put red in here this is now the new cluster Center this one does not exist anymore and this one does not exist anymore either for the turquoise one we cannot just put it down here even though we know that this would be a correct solution here or the desired solution at least but we do have some turquoise points up here so we put it maybe somewhere here so closer to this one because we have more data here but we still have some data here so we put the the centroid here in between so that is one iteration what we do next is we do the same thing we take every data point we calculate the distance between all the centroids so I take this data point up here for example and I ask how far away is it from turquoise this far away how far away is it from uh from this yellow Point here this far away okay how far away is it from the red point there you go okay so now all of these would become yellow and these would stay red these would stay uh turquoise and then we again reposition the centroid so now we have no turquoise points up here so the turquoise centroid would be down here and we do this as long as we uh or until we reach the max iteration number so we can say okay do this a maximum of 200 times so do it less or equal to 200 times or we can also abort earlier if there is no change so if I already have this result here I can run this for a thousand times these centroids won't move a lot if they they will probably not move at all so this would also be a a reason to stop so either because you reach the max iteration or because there's no change happening really that is the basic idea of k-means clustering and this is what we're going to implement in Python so as I mentioned we're going to need numpy so pip install numpy if you don't have it on your system and we're also going to install matplotlib now matplotlibs just for visualization so it doesn't help us to implement anything so we are going to use it numpy mat.lib and then we're going to say import numpy S and P import matplotlib dot Pi plot splt and then we're going to create a class called K means clustering and we're going to say that want to have a Constructor where we're going to set the cape so we're going to set the K by default to 3 but we can also change it when we create an instance of this class so self.k is going to be K and self Dot centroids in the beginning is going to be none so we don't have any centroids yet now all the magic is going to happen in our fit method so for the fit method all we want is we want data points because again remember we're doing unsupervised learning we don't have X and Y we don't have a Target variable we only have data that we want to Cluster so we want to have X as an input here and then we want to have a Max iterations let's say 200 here what we do now is exactly what we said so just remember what we drew here now maybe you cannot really maybe it was a good image something like this here what we do is we randomly initialize the centroids first this is the first thing we want to do so we say self Dot centroids equals and we're going to use numpy to Generate random centroids now you have to do this intelligently or you don't have to but it's it's reasonable to do this intelligently let's say here um maybe I'll move this a little bit so let's say I have a coordinate system here for my data that goes from 0 to 200 on the x-axis or on the X1 axis we could call this and goes from uh from negative 5 to 5 on the y-axis or on the X2 axis if I randomly initialize the centroids I don't want to just pick any random position between 0 and 1 or between 0 and 200. for each axis I want to have a random position within the Min and the max of the data so if I have data points here and here and and here and all that I don't want to generate a random centroid up here because it's going to be wrong definitely because there is no data up there so I want to keep the centroids in the boundaries of the data that I already have so what we're going to do is we're going to say NP random uniform a uniform distribution is just you give it a Min and a Max and every value in between is equally likely to be the result so we're going to pass for every single dimension of our X data the minimum and the maximum for the respective Dimension so we were constantly talking about two Dimensions here you can also do k-means clustering with three dimensions or with 10 000 Dimensions so if I have three dimensions here I would have maybe x y and z then I would have a data point here and every single axis here has a Min and a Max and this of course means that um that this is also the case for 5000 Dimensions now we cannot really visualize that but for 5000 Dimensions you would also have um you would also have 5 000 different min max ranges so we're going to say here NP random uniform and then we're going to say NP A Min I think this stands for axis minimum probably um and this will give us 4X at axis zero um the minimum so for each Dimension the minimum value in x and then we're going to also get NPA Max X is zero so the maximum for every Dimension and those two values that we're passing here those are the boundaries for the uniform distribution so for for every single centroid we're going or or for the centroids that we generate on every Dimension we're going to keep the the coordinates of the centroids within the Min and Max of this respective Dimension I hope this makes sense uh and then we're going to say in general the size is just how many centroids we want to have K because K clusters right and X shape one so we want to have uh X is the data that we already have those or the data points one data point has a certain shape um and this shape the same shape is the shape of a centroid so a center a centroid is just a data point but it's a centroid right so we treat it differently so just to make sure that you understand this it's important or important it's it's intelligent to keep the centroids within the boundaries of the data because it doesn't make sense if I have again in two Dimensions if I have all the data here right and I initialize a random centroid down here now it will probably find its way into into the data but there's no reason to do that I can just keep it in here by default right so that's the idea here we're generating that for every single Dimension we consider the minimum and the maximum of that Dimension so for the x-axis for the y-axis for the z-axis and for the 5000 other dimensions that you potentially have you consider the min max of this particular dimension uh what we do next is we iterate for placeholder that we don't need to name in range Max iterations um and what we're going to do now is we're going to create our cluster uh labels so the Y's even though it's not a Target variable what we have now the Y labels for the for all the X data points in the beginning an empty list now for every data point that we have in x what we want to do is we want to compute the distances between every single data point and all the centroids now we haven't talked about the distance measure uh mathematically yet so how do I actually calculate the distance now we we just drew the lines here but what uh what are these lines so wrong color if I have a coordinate system here again in two dimensions and I have a point a here and a point B here I think it's quite easy to understand if I have X here and Y here how to calculate this distance here this distance here is just this is the Pythagorean theorem so we have the Delta X the Delta y uh or It's A and B and we have C here and we know that c is the square root of a squared plus b squared this is just the Pythagorean theorem and this results in the euclidean so this is the euclidean distance that we're using here the euclidean distance measure tells us how far is a from B uh what's the distance here and we do that by taking the X difference and the Y difference squaring those summing them up and then taking the square root of that this is how we do it in two dimensions in three dimensions the process is the same and I hope I can draw this somehow intuitively here so that you actually understand what I'm talking about if this is not obvious to you so x y z what we do is we have a data point here so maybe it's just one in the y direction maybe it's three in the X Direction and zero in the Z Direction then I have a point here which is Maybe uh zero on the x-axis then it is 5 or so on the Z axis and then it's also 10 or so on the y-axis so how do we get the distance between those two points well we do the same thing we just um we take the difference I'm going to now I don't know if that's correct Delta X the difference in X between those two points so how much do I have to go into or this is actually Y how much do I have to go into this direction how much do I have to go into this direction and how much do I have to go into this direction we Square all these and we take uh the square root so it's actually the sum of these differences so of a i minus b i where I is the dimension we Square the differences here we sum them up and we take the square root that is the euclidean distance in every Dimension so I is 1 up until n for n Dimensions that is how you say that how you write that so yeah I hope the notation doesn't confuse you too much it's basically the same thing if I go five steps into the X direction that would be Delta X that would be uh maybe the First Dimension so a in the First Dimension which is the x-axis how much do I have to move to B maybe negative five square that and sum all the dimensions up and then take the square root this is the euclidean distance so actually what we're going to do here in Python now is we're going to say going to define a static method so we don't need the self keyword it's just a calculation euclidean distance between data points and centroids and the idea here is to actually not compute the euclidean distance between two points so not one data point in one centroid but one data point and all the centroids so actually we're doing return numpy square root remember again the formula what was it square root of the sum of the squared differences so the first thing is square root so if you call it in functions the first thing you actually do is you do the subtraction then you square it then you you just create a difference then you sum all these squares up and then you take the square root but when you write it in Python you first do the square root in terms of what you mentioned first so we do the square root of what of something that's already calculated inside of this so NP dot sum of what of the square differences so centroids minus the data point squared this is summed up on axis one and then from this sum we take the square root this is how we compute the eucliding distance if we have one data point and N centroids no matter how many they are and this is just a thing in numpy right if you have um 500 here so 500 vectors here or 500 points here and then you have one point here you're going to just subtract the same point from all the centroids so you're going to calculate this for all these centroids this is just how numpy is implemented um so what I'm going to do here now remember we are in the fit function in the loop for data point in X what we want to do is we want to calculate the distances between the centroids and this data point so K means clustering dot euclidean distance uh let me just make sure I'm not blocking this here eucliding distance between this particular data point we're looking at right now and then self Dot centroids and then we assign a cluster number to it and the cluster number that this point will get is the arc Min so NP Arc Min this function returns to us the index of the smallest value so this what this line here returns to us is a list of distances so we have now a list or a numpy array with the distances between this point and all the centroids and I want to know which centroid has the smallest distance to this point and I want to know the index of that centroid of the index of this distance here so I take the arc Min the minimum value which index does it have in the distance list and this is my cluster number and this is what I append to why the cluster labels all right and then we're going to turn I into a numpy array and that's it so this is now the first step that we talked about this is actually just uh what we did in the beginning this year we randomly initialized them and now we assigned every point to a centroid this is all we did up until this point now what we want to do is we want to readjust the centroid position so we want to reposition the centroids based on these labels and we do that by saying cluster indices um equals empty list and then 4i in range self.k so for every cluster what we're going to do is we're going to say cluster indices append NP Arc where and uh basically what we're doing here now is we're preparing for the next evaluation so what we have in y is now for every point for every point in X which cluster does it have but we also want to know uh for each cluster which indices belong to that cluster so we say cluster indices Arc where so give me the indices where something is true where Y is equal to I so this is how we do that and then we say four uh or actually we say cluster centers and here we now recompute the cluster Center so we get an empty list and we now reposition the centroids so we say 4i indices in enumerate so that we have the I uh cluster indices and we say if the length of the indices is zero so because sometimes you might have if you have some if you have two clusters obviously but you use 100 centroids some of them are gonna just have no data belonging to them so they're going to have empty cluster indices um yeah so so you will have basically what we have here in the cluster indices we have a list of lists so we have for each cluster which of the data points belong to that cluster so for the first cluster with index 0 we're going to have a list of all the indices in X where for the data points that belong to that cluster some of them might be empty because some clusters might have zero members if we have too many clusters if K is too high so if that is the case we're just going to say cluster Center will stay the same so cluster centers we're going to just append to it what it already is centroids I cluster Central centers is basically just a new centroid so if there is no member we're not going to reposition it we're just going to take the current centroid and set it as the new centroid same thing otherwise cluster centers dot append and we're going to take the average position so NP mean of X indices so the indices of the elements belonging to that cluster take all their positions compute the mean position and we do that by specifying axis equals zero and take the mean so the first value here there you go this is our new cluster position and now the only thing that we need to do here is we need to say if NP Max self centroids minus numpy array cluster centers if the difference here is less than 0.001 for example you can choose your own threshold if that is the case we're going to break this basically just says okay if the difference between the centroid position as it is right now and the new centroids if the maximum difference on all the centroids so if there's no centroid in the whole list that has more change than this we can just break and we can just say it's done otherwise we're going to do it um we're going to just say self centroids equals MP array cluster centers so we reposition the cluster centers there you go and then finally what we get as a result here is y the cluster labels once we're done all right so that is the full implementation let's see if it works let's see how it works we're going to save for this random underscore points equals nprandom Dot randint between 0 and 100 and want to have the shape 102 so one half 100 two-dimensional uh arrays so that we have two dimensional points then we're going to say k means equals k mean clustering K means clustering k equals three which is actually the default and the labels is now going to be equal the labels are not going to be equal to K means fit on the random points now every Point has a label and all we have to do now is have we have to visualize this PLT scatter random points plot the X values plot the Y values the color is going to be determined by the labels and then we also want to scatter the centroids so k-means dot centroids X values K means Dot centroids y values C equals range length K means Dot centroids so for the colors and then oh actually now I'm blocking again with my camera and then we're going to say marker so that we can distinguish them it's going to be this star and we're going to say the size is going to be 200 so we can actually see the centroids clearly uh what's the problem here let's just ran into I think I'm using one bracket too much here there you go so now what we have here is we have data points those are the cluster centers and this is the clustering result here uh this looks reasonable and every time we run this actually we're going to get a different result so because we also get different data points and also k-means can have different results in general so you'll not you're you're not always going to end up with the same clustering um yeah so that's that what we can do as well is we can use scikit-learn to generate data now the implementation is done we didn't use cycle learn for the implementation but we can use scikit-learn uh to have a data set that we can play on so we're going to actually if you don't have it pip install scikit Dash learn I have it in my uh case and then we're going to say from sklearn.datasets import make blobs because this is actually a function that creates data that is um well separated so we can say data or actually we can keep the name random points but we're not going to generate it like that we're going to say make blobs and we're going to say um n samples 100 you want to have 100 data points you want to have two features two dimensions um and actually we want to just get the uh maybe we're gonna say here data equals I'm going to say data equals that and the random points without the labels because what this function does is it generates the data points and it also generates the classes the correct classes um we want to actually uh we want to only have the data point so we're going to say data zero is going to be the data and in this case we only get two blobs this is actually what we wanted to do I don't think so uh let me just see here make plops I think we can is there a parameter for this let me just see in the function here uh Center Shuffle number of features notice the different thing I think maybe the centers maybe centers equals three will do it yeah there you go so now we have blobs with three clusters or do we I don't know yeah looks like it's or maybe it's just random I'm not sure but you can see the clustering works this is the important thing it doesn't matter how to make blobs function Works uh you can see that our clustering finds reasonable clusters probably the optimal clusters and we can actually confirm that this is the case by um Computing something called the Ari score the adjusted random score or Randomness score so the reason we have to use a specific score for this is because the so so let me just show this to you if I print random points or actually data one we're going to get the actual labels and I can also print the actual labels then our k-means clustering generated and you can see in this case this is a good example I think all these points are exactly the same but they have different values so one is two and two is one but we can see that all ones are all twos here so the clustering is correct we just use different names and if we want to consider if we want to take that into account if I because if I just say now okay are the labels equal to the data I will get a terrible score even though the clustering is exactly the same because it doesn't matter if it's called one or two it's the same so that's the important thing um and for this we can actually say here from sklearn.metrix import the adjusted range score and we can say here Ari equals adjusted Rand score for data one and labels and When I close this here we have to print it of course okay in this case it's 0.5 0.77 0.461 in this case one means it's exactly the same all the clustering is exactly the same here one again 0.57 and so on one again there you go so this is how you implement K means clustering from scratch I'm going to go through the explanation one more time in a faster way here so we initialize the centroids randomly for each Dimension we consider the range from Min to Max um we generate case Androids we have an empty list of labels we go through the data points we calculate the distance between every data point and the Clusters or the cluster centers that we initialized randomly in the beginning we assign to each data point the closest cluster the closest centroid um and we then reposition the centroids so that they line up exactly in the middle of all the points that are assigned to this cluster and we do that all the time so that the centroids get closer and closer to the middle of the cluster and the data points then are assigned of course to the centroids that's the basic idea and we use the eucliding distance which is just like the Pythagorean theorem in N Dimension so written like this mathematically here so that's it for today's video I hope you enjoyed it and hope you learned something if so let me know by hitting a like button and leaving a comment in the comment section down below and of course don't forget to subscribe to this Channel and hit the notification Bell to not miss a single future video for free other than that thank you much for watching see you next video and bye