Unsupervised Learning and Clustering

Unsupervised clustering asks a different question than supervised classification: rather than predicting a label a human has already assigned, the algorithm must discover groupings directly from the structure of unlabeled feature vectors. K-means is the most widely taught partitional method: given a target number of clusters k, it represents each cluster by a single centroid and assigns every data point to whichever centroid is nearest, then recomputes each centroid as the mean of the points currently assigned to it. This two-step alternation — an assignment step and an update step — repeats until assignments stop changing. The technique traces back to independent discoveries by Hugo Steinhaus in 1956, Stuart Lloyd at Bell Labs in 1957 (though his paper was not published until 1982), and James MacQueen, who coined the term "k-means" in 1967 while formalizing the same alternating-minimization idea.

Formally, k-means minimizes the within-cluster sum of squared distances between points and their assigned centroid — an objective that is NP-hard to optimize exactly, but Lloyd's alternating algorithm reliably finds a local minimum. Geometrically, the fixed centroids at any iteration partition the feature space into a Voronoi diagram: every point is assigned to the region belonging to its nearest centroid, so k-means implicitly assumes clusters are roughly convex, similarly sized, and separated along straight boundaries. This assumption is also the algorithm's chief limitation — it performs poorly on clusters that are elongated, nested, or of very different densities, and it requires k to be chosen in advance, typically using heuristics like the elbow method or silhouette scores.

Because Lloyd's algorithm only guarantees convergence to a local optimum, the choice of initial centroids matters enormously; poor initialization can trap the algorithm in a bad solution, which is why practical implementations typically run k-means from several random restarts, or use smarter seeding strategies (such as k-means++) that spread initial centroids apart before the first assignment step even begins. Despite its simplicity, k-means remains a workhorse of exploratory data analysis precisely because it is fast, scales to large datasets, and gives an interpretable centroid summarizing each cluster — properties that motivate its continued use as a baseline against which more elaborate clustering methods are compared.

Hierarchical clustering avoids committing to a single value of k up front. Agglomerative hierarchical clustering starts with every point as its own cluster and repeatedly merges the two closest clusters, using a linkage rule — single linkage (nearest pair of points), complete linkage (farthest pair), or average/Ward linkage (average distance, or the merge that minimizes increase in within-cluster variance) — to decide how "closeness" between whole clusters is measured. The result is a dendrogram, a tree recording every merge in order, from which an analyst can cut at any height to obtain a clustering with a chosen number of groups, making the method attractive when the natural granularity of the data is not known ahead of time. Divisive hierarchical clustering works in the opposite direction, starting with all points in one cluster and recursively splitting, though it is used less often in practice because exhaustive splitting is more expensive than exhaustive merging.

Density-based clustering takes a fundamentally different view of what a cluster is: rather than a region defined by proximity to a centroid, a cluster is a dense region of points separated from other dense regions by regions of low density. DBSCAN, introduced by Ester, Kriegel, Sander, and Xu, formalizes this with two parameters — a neighborhood radius Eps and a minimum point count MinPts. A point is a core point if at least MinPts other points fall within Eps of it; a border point falls within Eps of some core point but does not itself meet the core-point threshold; and any point that is neither is labeled noise and assigned to no cluster at all. Clusters are then formed by chaining together core points that are density-reachable from one another, along with their border points.

Because DBSCAN defines clusters by connectivity through dense regions rather than distance to a single centroid, it can discover clusters of arbitrary shape — crescents, rings, or elongated filaments — that would defeat k-means, and it naturally identifies outliers as noise rather than forcing every point into some cluster. Its main practical difficulty is sensitivity to the Eps and MinPts parameters: too small an Eps fragments a true cluster into many pieces, while too large an Eps can merge genuinely separate clusters, and a single global density threshold struggles when different regions of the data have very different densities — a limitation that motivated later density-based variants using varying density thresholds.

K-means makes a hard assignment of every point to exactly one cluster, but many real datasets are better described probabilistically, where a point plausibly belongs to more than one cluster with different degrees of confidence. A Gaussian mixture model represents the data as generated by a weighted combination of several Gaussian distributions, each with its own mean and covariance, and fitting it means estimating both which component generated each point and the parameters of every component simultaneously — a chicken-and-egg problem that neither quantity can be computed without the other. The Expectation-Maximization algorithm, formalized by Dempster, Laird, and Rubin, resolves this by iterating between two steps: the E-step computes the "responsibility" each mixture component takes for each data point — essentially a soft, probabilistic cluster assignment — given the current parameter estimates, and the M-step re-estimates each component's mean, covariance, and mixing weight by treating those responsibilities as if they were known. Each E-M cycle is guaranteed to never decrease the data's likelihood under the model, so the algorithm converges monotonically to a local maximum, though — like k-means, which can be seen as a special, hard-assignment case of the same idea — the result depends on initialization.

Spectral clustering approaches the problem from graph theory rather than probability. Ng, Jordan, and Weiss formalized a now-standard version of the algorithm: build an affinity matrix whose entries measure pairwise similarity between points (commonly a Gaussian kernel of Euclidean distance), form the corresponding degree matrix and normalized graph Laplacian, and compute the k eigenvectors associated with its largest eigenvalues. Stacking these eigenvectors as columns and renormalizing each row to unit length produces a new, low-dimensional representation of every original point; ordinary k-means is then run on these rows to obtain the final clustering. The eigenvectors of the graph Laplacian encode information about how the data points are connected through chains of similarity, which lets spectral clustering separate clusters that are not linearly separable or convex in the original feature space — for instance, two intertwined spirals — precisely the kind of structure that defeats k-means applied directly to the raw features.

Taken together, these families illustrate that clustering is not one algorithm but a family of different structural assumptions about what a "group" means: compactness around a centroid (k-means), nested proximity captured by a merge order (hierarchical), local density (DBSCAN), a probabilistic generative process (mixture models), or connectivity through a similarity graph (spectral). A widely cited survey of the field summarizing five decades of clustering research after k-means concludes bluntly that despite thousands of published clustering algorithms, no single method is best for all data — the right choice depends on the geometry, density, and noise characteristics of the specific dataset at hand, which is why practitioners routinely compare several methods before trusting the groupings any one of them proposes.