Clustering

1 · What it is

Clustering is a form of unsupervised learning; nobody tells it which group any example belongs to. If the examples already carried group labels, the same sorting job would be called classification instead. When the algorithm finishes, every group comes back tagged with its own cluster ID. Nothing tells you whether those groups are right, so a person has to judge them, looking both at whole groups and at single examples.

Among methods built around centroids, k-means is the most popular. A centroid is simply the average position of the points in its group. You choose k, the number of groups, before it runs. The starting centroids are dropped at random. Each example then joins whichever centroid is closest. Next, each centroid moves to the average spot of the examples that joined it. Those two moves repeat until no example switches group. Because the start is random, two runs on the same data can end with quite different groups.

How you measure similarity is a decision that depends on knowing your data well. Raw features first need normalizing, scaling and transforming, just as in any other machine learning project. With two features you can eyeball which points belong together; with many, weighing and comparing them stops being obvious.

Other algorithms bake in other assumptions, and each one fits a certain kind of data best. Hierarchical clustering produces a tree, and cutting that tree at a chosen level gives the number of clusters you want. Density-based methods join up crowded regions, so a group can take any shape, and stray outliers stay unassigned. DBSCAN, described in a 1996 paper, is a clustering algorithm built on this density-based view of what a cluster is. Density methods have weak spots too; they struggle when clusters differ in density or when the data has many dimensions.