k-Means Clustering Algorithm

Most introductions present k-means as a method for sorting data into groups. That description is accurate, but it hides a second reading of the same algorithm. Instead of asking which group a point belongs to, you can ask how a point is described once the algorithm has finished. Seen this way, k-means is not only grouping data. It is also rewriting every data point in terms of something simpler. The name given to this rewriting is vector quantization.

Earlier methods in this course describe data by building it up from parts. Principal component analysis, usually called PCA, looks for directions in which the data varies the most, chosen so that as much of the spread in the data as possible is captured. Non-negative matrix factorization, usually called NMF, looks for components that add together to make the data, and these components often correspond to extremes or recognizable parts of the data set rather than to averages.

Both approaches share a common pattern. Each data point is expressed as a combination of several components, and the point's identity comes from how those components are mixed together. k-means seems to have no components at all, so the natural question is whether it fits this same pattern. It does, once you look at what it hands back for each point.

k-means takes a different route. It tries to represent each data point using a cluster center. Where PCA and NMF build each point from several pieces, k-means assigns each point exactly one stand-in: the center of the cluster it belongs to. In other words, every point is described by a single component, and that component is the cluster center. The comparison below makes the contrast explicit.

This is the central idea of vector quantization. Viewing k-means as a decomposition method means treating the set of cluster centers as a small vocabulary of components, with each data point being represented by one entry from that vocabulary. The point is not stored in full detail after clustering. It is replaced by the center that stands for its cluster.

The diagram below shows the codebook view. Each cluster center is a key in a small table, and the points it stands for are the values stored under that key. Because the table is small, the whole data set is described through a handful of entries rather than through every original value.

Consider four one-dimensional values, 1.0, 1.2, 4.8, and 5.1, that k-means has grouped into two clusters with centers at 1.1 and 5.0. The example below is an illustration constructed for this article. It shows exactly what changes when each point is replaced by its center.

The outcome is the trade described earlier. The whole data set is now expressed through two centers instead of four distinct values. Each point still has a clear representative, but the small offsets from that representative, such as 1.0 being 0.1 below 1.1, are no longer stored.

The process for a single point has two stages. First, the point is compared against the cluster centers and matched to the one it belongs to. Second, the point's description is replaced by that center. The original point is not needed for the representation, because the center alone now carries its identity.

Read the map from left to right. Each position holds one original point, and the value stored there after quantization is the single center that point is assigned to. Every point has exactly one entry, which is what makes the representation a single-component description.