k-Means Algorithm

Read this in other languages: Português

The k-Means algorithm is an unsupervised Machine Learning algorithm. It's a clustering algorithm, which groups the sample data on the basis of similarity between dimensions of vectors.

In k-Means classification, the output is a set of classes assigned to each vector. Each cluster location is continuously optimized in order to get the accurate locations of each cluster such that they represent each group clearly.

The idea is to calculate the similarity between cluster location and data vectors, and reassign clusters based on it. Euclidean distance is used mostly for this task.

Image source: Wikipedia

The algorithm is as follows:

Check for errors like invalid/inconsistent data
Initialize the k cluster locations with initial/random k points
Calculate the distance of each data point from each cluster
Assign the cluster label of each data point equal to that of the cluster at its minimum distance
Calculate the centroid of each cluster based on the data points it contains
Repeat each of the above steps until the centroid locations are varying

Here is a visualization of k-Means clustering for better understanding:

Image source: Wikipedia

The centroids are moving continuously in order to create better distinction between the different set of data points. As we can see, after a few iterations, the difference in centroids is quite low between iterations. For example between iterations 13 and 14 the difference is quite small because there the optimizer is tuning boundary cases.

Code Examples

kMeans.js
kMeans.test.js (test cases)

References

k-Means neighbors algorithm on Wikipedia