Learning Without Answers
Most of the machine learning people hear about is supervised: the model sees an input, sees the correct answer, and adjusts. Clustering has no correct answers to look at. It receives a pile of unlabeled data points and has to decide which ones belong together.
That makes it one of the most useful and least well-defined tasks in the field. A retailer with two million customer records does not know in advance how many kinds of customers it has. A biologist sequencing thousands of individual cells does not know which cell types are present. Clustering is how both of them get a first map of the data. The catch is that «which points belong together» depends entirely on how similarity is measured and what shape a group is assumed to have, and different algorithms make very different assumptions.
k-means
k-means is the most widely used clustering algorithm, and it is simple. Pick a number k. Place k centers somewhere in the data. Then repeat two steps: assign every point to its nearest center, and move each center to the mean of the points assigned to it. Stop when the assignments stop changing.
The algorithm goes back to Stuart Lloyd at Bell Labs in 1957 (though it was not published until 1982), and the name «k-means» comes from James MacQueen in 1967. Each iteration can only decrease the total squared distance between points and their centers, so it always converges. What it converges to, though, is a local optimum that depends on where the centers started. A bad initialization can put two centers inside one real group and leave another group with none.
Arthur and Vassilvitskii addressed this in 2007 with k-means++, which picks the initial centers one at a time, each chosen with probability proportional to its squared distance from the centers already placed. That spreads the starting points out and comes with a guarantee that the result is within a logarithmic factor of the optimum in expectation. It is the default initialization in most libraries today.
k-means has two built-in assumptions worth keeping in mind. It uses Euclidean distance to a mean, so it prefers compact, roughly spherical clusters of similar size. And it assigns every single point to some cluster, outliers included. On data shaped like two interlocking crescents, it will cut straight across both.
Choosing k
k-means needs the number of clusters as input, which is often the exact thing the analyst wants to find out. Two common heuristics help. The elbow method plots the total within-cluster distance against k and looks for the point where adding more clusters stops giving much improvement. The silhouette score, introduced by Peter Rousseeuw in 1987, measures for each point how close it is to its own cluster compared to the nearest other cluster, on a scale from -1 to 1. Averaging it across the dataset and picking the k with the highest value is a reasonable rule.
Neither method gives a definitive answer, and on real data the elbow is often not visible at all. In practice, the choice of k is frequently made by looking at whether the resulting groups make sense to someone who knows the domain.
Hierarchical Clustering
Hierarchical clustering avoids choosing k up front by building a whole tree of groupings. The agglomerative version starts with every point as its own cluster and repeatedly merges the two closest clusters until only one is left. The history of merges is drawn as a dendrogram, and cutting the tree at different heights gives different numbers of clusters.
The key decision is how to measure the distance between two clusters. Single linkage uses the closest pair of points, which can follow long, chain-like shapes but tends to string unrelated groups together through a few intermediate points. Complete linkage uses the farthest pair, which produces compact clusters. Ward’s method, from Joe Ward in 1963, merges the pair that causes the smallest increase in total within-cluster variance, and in practice it behaves a lot like k-means.
The main drawback is cost. A straightforward implementation needs all pairwise distances, which is quadratic in memory, so it works well on thousands of points and poorly on millions. It is common in biology, where dendrograms of gene expression profiles or species are standard figures.
DBSCAN and Density-Based Methods
DBSCAN takes a different view: a cluster is a region where points are packed densely, separated from other clusters by regions where they are sparse. Ester, Kriegel, Sander and Xu proposed it in 1996, and the paper received the KDD Test of Time Award in 2014.
The algorithm has two parameters: a radius eps and a minimum number of points. A point with at least that many neighbors within eps is a core point. Clusters grow by connecting core points that are within reach of each other, and points that are not reachable from any core point are labeled as noise.
This gives DBSCAN three things k-means lacks. It does not need the number of clusters. It finds clusters of arbitrary shape, including the two crescents. And it has an explicit notion of outliers, instead of forcing every point into a group. The weak spot is that a single eps assumes all clusters have roughly the same density. HDBSCAN, by Campello, Moulavi and Sander in 2013, fixes this by building a hierarchy across all density levels and extracting the most stable clusters from it, which is why it is now often recommended over plain DBSCAN.
Probabilistic Clustering with Gaussian Mixtures
A Gaussian mixture model assumes the data was generated by several Gaussian distributions, each with its own mean, covariance and weight, and fits them with the expectation-maximization algorithm (Dempster, Laird and Rubin, 1977). Instead of assigning each point to exactly one cluster, it gives a probability of belonging to each.
That soft assignment is useful when groups overlap. Because each component has its own covariance matrix, mixtures can also fit elongated, tilted clusters that k-means would split. k-means is in fact a limiting case of a Gaussian mixture where all covariances are equal and spherical and the assignments are forced to be hard.
Where Clustering Gets Used
Customer segmentation is the textbook example, and it is real: marketing teams use clusters of purchasing behavior to decide who gets which campaign. In single-cell RNA sequencing, clustering is a central step. Tools like Seurat and Scanpy build a nearest-neighbor graph of cells and run community detection algorithms such as Louvain or Leiden on it, and the resulting clusters are then annotated as cell types. In computer vision, k-means on pixel colors is a simple way to reduce an image to a small palette, and clustering of local image descriptors produced the «bag of visual words» used in image retrieval before deep learning. Astronomers cluster stars by position and velocity to find stellar streams, and fraud teams cluster transactions to find groups that behave unlike the rest.
The Question of What a Good Cluster Is
Jon Kleinberg proved in 2002 that no clustering function can satisfy three natural-looking properties at once: scale invariance (multiplying all distances by a constant should not change the result), richness (every possible partition should be reachable with some distance function), and consistency (making points within a cluster closer, and points in different clusters farther, should not change the result). Every algorithm gives up at least one of them.
This matches what practitioners see. The same dataset clustered with k-means, DBSCAN and a Gaussian mixture can give three different, equally defensible answers. Internal metrics like the silhouette score favor certain shapes, so they cannot settle the matter either.
Reflection
Clustering can look like the model is discovering structure on its own, but every method brings its own definition of a group: close to a center, dense in a region, or generated by the same distribution. The algorithm finds what fits that definition. The results are most useful when someone checks the clusters against knowledge from outside the data, because the math alone cannot say which grouping is the real one.
By: Max Johnson B.
Deja una respuesta