In the previous segment, we learned about K-means clustering and how the algorithm works using a simple example. We learned about how assignment and the optimisation work in K Means clustering, Now in this lecture, we will look K-means more algorithmically. We will be learning how the K Means algorithm proceeds with the assignment step and then with the optimisation step and will also be looking at the cost of function for the K-means algorithm.
Let’s understand the K-means algorithm in more detail.
From the previous lecture, we understood that the algorithm’s inner-loop iterates over two steps:
- Assign each observation Xi to the closest cluster centroid μk.
- Update each centroid to the mean of the points assigned to it.
In the next lecture, we will learn about the Kmeans cost function and will also see how to compute the cost function for each iteration in the K-means algorithm.
So the cost function for the K-Means algorithm is given as:
Now in the next video, we will learn what exactly happens in the assignment step? and we will also look at how to assign each data point to a cluster using the K-Means algorithm assignment step.
[Note: At 1:43 where the Prof explains the optimisation step, the values in the column – μ1 and μ2 should be X1 and X2 ]
In the assignment step, we assign every data point to K clusters. The algorithm goes through each of the data points and depending on which cluster is closer, in our case, whether the green cluster centroid or the blue cluster centroid; It assigns the data points to one of the 2 cluster centroids.
The equation for the assignment step is as follows:
In the optimisation step, the algorithm calculates the average of all the points in a cluster and moves the centroid to that average location.
The equation for optimisation is as follows:
Zi=argmin||Xi−μk||2
Now having assigned each data point to a cluster, now we need to recompute the cluster centroids. In the next lecture, Prof.Dinesh will explain how to recompute the cluster centroids or the mean of each cluster.
In the optimisation step, the algorithm calculates the average of all the points in a cluster and moves the centroid to that average location.
The equation for optimisation is as follows:
μk=1nk∑i:zi=kXi
The process of assignment and optimisation is repeated until there is no change in the clusters or possibly until the algorithm converges.
In the next segment, we will learn how to optimise the K-Means algorithm even further using the K-Means ++ algorithm
Additional Reading
- You can also look K-Means algorithm as a coordinate descent problem and how to achieve global minima in the K-Means cost function. Please take a look at this optional segment to learn further.