MNIST Clustering using K-Means
This video builds K-Means clustering from scratch on the MNIST digit dataset, covering centroid initialization, the elbow method, and achieved accuracy.
Clustering handwritten digits without ever telling the algorithm what a "3" or a "7" looks like sounds difficult, but it is exactly what K-Means clustering is built to do. This video works through K-Means from first principles and then applies it to the MNIST dataset of handwritten digit images, building the algorithm from scratch rather than relying entirely on a library implementation.
What K-Means clustering is
K-Means is a popular, widely used clustering algorithm in machine learning and data mining. It is unsupervised, meaning it does not need labeled data for training. Instead, it partitions a set of data into K clusters based on the features or attributes of the data points themselves.
How the algorithm works
The mechanics start with choosing a value for K, the number of clusters you want in the final result. The algorithm then initializes by selecting K initial cluster centroids, often randomly. Every data point is then assigned to the nearest centroid based on distance, and once all points are assigned, new centroids are calculated as the center of each resulting cluster. This process of assigning points and updating centroids repeats until the clusters stop changing significantly, or until a specified number of iterations is reached. Throughout this process, the algorithm aims to minimize the variance within each cluster while keeping the clusters as distinct from each other as possible. K-Means shows up in applications like customer segmentation, image compression, document clustering, and anomaly detection.
Choosing the right value of K
Picking K is often the trickiest part of using K-Means. If you already have domain knowledge, you can set K directly, and for MNIST that is straightforward: since the dataset contains digits 0 through 9, K is set to 10. Other approaches include cross-validation or the elbow method, a widely used technique for finding an appropriate K value.
The elbow method explained
The elbow method works by plotting the within-cluster sum of squares (WCSS) against the number of clusters and identifying the point where the rate of decrease in WCSS slows down noticeably, forming a visible "elbow" in the plot. That point is typically treated as the optimal K value. The process involves choosing a range of possible K values based on domain knowledge or intuition about the dataset, running K-Means for each value in that range, and calculating WCSS for each result before plotting them together.
It is worth noting that the elbow method is a heuristic and does not always produce a clean, obvious elbow, particularly with large or complex datasets. When that happens, other methods can be used, and running multiple trials with different initializations can help confirm the robustness of the chosen K.
Implementing K-Means on MNIST
For the implementation, the MNIST dataset is loaded from a tensor library, the training data is reshaped, and the images are visualized to get a sense of what the digit images actually look like. Before running K-Means, dimensionality reduction is applied to the data. K centroids are initialized, clusters are assigned based on those centroids, and centroids are updated iteratively, with a maximum of 100 iterations defined for the run. To check whether the clustering is working, a "matched cluster label" check compares whether each data point landed in the cluster corresponding to its actual digit.
With K set to 10, matching MNIST's 10 digit classes, the resulting accuracy came out to around 77.9%. The video notes there are ways to improve on that accuracy, which could be explored in future work. The final results are visualized with each cluster shown in a different color, with the centroid of each cluster marked separately.
Key takeaways
- K-Means is an unsupervised algorithm that partitions data into K clusters without needing labeled training data.
- The algorithm alternates between assigning points to the nearest centroid and updating centroids until the clusters stabilize.
- Domain knowledge can set K directly; for MNIST, K equals 10 to match the digit classes 0 through 9.
- The elbow method finds an optimal K by plotting WCSS against cluster count and locating where the decrease slows down.
- The from-scratch K-Means implementation on MNIST achieved roughly 77.9% clustering accuracy, with room for improvement.
Who this is for
This video is useful for anyone learning unsupervised clustering fundamentals or wanting to see K-Means implemented from scratch rather than as a black-box library call. It is part of a Humanitarians AI series that also covers PCA and t-SNE dimensionality reduction on the same MNIST dataset.
Full transcript(auto-generated, with timestamps)
[0:02]Hello everyone today let us see how we can cluster the MS data using K means clustering what is K means clustering K means is a popular clustering algorithm which is used in machine learning and data mining it is an unsupervised machine learning algorithm which means that it does not need label data for training instead it partitions a set of data into K clusters based on their features or attributes let us understand how a k means algorithm Works let's take an example of few data points now we have to set the value of K and here let us assume that the value of K
[1:13]Is 2 which means in the final result we will have two clusters so for that now we have to initialize and uh for that we have to choose a k initial cluster cental random L for example let's consider this as C1 and this as C2 these are two initial C centroids that we are using and based on this for some radius we have to assign all the data points into these clusters and based on this uh clusters like the data points we have to find the new centroid and update the new centroid let's consider the new centroid here is this point and 3 2 1 and we have to repeat this process
[2:23]Until we no longer see any change uh in the Clusters or the centr significantly or until some specified number of iterations here the algorithm aims to minimize the within cluster variance which means it tries to make the data points within each cluster as similar to each other as possible while also keeping the Clusters as different from each other as possible and K means is a widely used in various application such as the customer segmentation image compression document clustering and also anony deduction Now using this algorithm let us apply this on our amness data set first let us understand what this mnus data set is this amness data set is a
[3:24]Set of numbers that are written by uh po codes and these are the handwritten numbers and using that we have to identify which which digit is what before going there we also have to understand that the crucial part here is setting the value of K we can set the value of K uh using several methods uh few of which are like if you already have the domain knowledge based on that we can set the value of K for example here we know that we are classifying the digits so the digits can be from 0 to 9 and hence the K value here is 10 similarly we can also use a cross
[4:21]Validation method or uh there is one uh famously known method called as elbow method which uh which is used to find the K value uh to be used in the K means clustering now before jumping into the implementation of K means let us understand the elbow method the elbow method is a technique used to determine the optimal number of clusters in a data set for clustering algorithms like K means and it works by plotting the within cluster sum of squares against the number of clusters and identifying the point where the rate of decrease in wcss slows down so uh here uh let's say example that here
[5:28]Is the value of Cl and this wcss and the elbow meod hand so at some point you can find the L at some point you can find the elbow point and this will be the optimal K value that we are looking for that we are looking for so how we can do this is we have to choose a range of key values and start by selecting a range of uh possible values of number of clusters and this should be based on the domain knowledge that we have or it can be our intution about the data set and then run the K means for all the K values and
[6:33]Then for each K value we have to uh calculate the within cluster sum of squares and when we plot this we can find the optimal K value but here we have to uh remember an important thing is that elbow method provides a huris stic for selecting the optimal number of clust and it may not always yield a proper elbow so we have to be careful especially when using large data and complex data sets and in case if the elbow method is not determining a clear k value we can also use like other methods and also few times if we run multiple runs and use different
[7:25]Initializations we may lead to a Rob like we can can ensure the robustness in the choice of K since we already know that the K like the final cluster we want here at 10 let us go with this value and now let's see the implementation uh I've imported all the required packages and here we can see that the data set uh is found in the tensa library and uh we can import from there after importing the data set I also reshaped the training data set then I visualize the images this is how the images look these are the M data set like digits images and
[8:18]Uh based on the each picture we have to classify into what digit the uh does that fall into before doing all these I have performed the dimensionality reduction here we'll see about the dimensionality reduction in the future and here we have initialized the K number of centroids and then assign the Clusters based on the centroids and then updating the centroids and this is basically the K means implementation and here I defined the maximum iterations as 100 and here uh the match cluster label is to check if the uh cluster that we have uh the data point that we have classified is classified correctly or not like does that fall into the cluster
[9:15]That it is indeed mentioned in here I've taken the value of KS 10 and uh I'm like found the like predicted the data like how that's working and for that the accuracy is like around 77.9 there are few ways to increase the accuracy we can try doing that in the future and if I've also mapped the Clusters and this is how the Clusters look this is like all these colors indicate uh the cluster of each digit and the cross mark here is about uh is it centroid thank you
More videos
2:08Bridging the Pixel Gap in Browser Automation.
2:23How One Narrow Safety Rule Can Make an AI Less Safe Everywhere Else.
2:04Why splitting a chunk from its document makes it retrieve for the wrong question
4:20Three You Can Take Back. One You Can't.
2:21Why a 50-turn agent pays for the same screenshot 35 times unless it caches the pixels
1:53