Cluster analysis · aiwiki.page

Cluster analysis is a family of methods for grouping observations so that members of a group, called a cluster, share similarities or statistical structure. It is used in statistics, machine learning, and data mining to investigate patterns in data. Usually classified as unsupervised learning, it differs from supervised learning because the groups are not supplied as labeled examples. Clustering is not a single algorithm: different methods define groups through proximity, connectivity, density, or probabilistic models. (introml.mit.edu)

Representation and similarity

Observations are often represented as feature vectors, arranged in a matrix whose rows correspond to objects and columns to measured attributes. Some methods instead accept pairwise distances or similarities. The representation determines which aspects of the objects can influence the grouping. (scikit-learn.org)

For numerical attributes, Euclidean distance measures straight-line separation. Other choices include Manhattan distance and cosine similarity; the latter emphasizes vector direction rather than magnitude. A distance or similarity measure encodes a substantive definition of resemblance, so different choices can produce different groupings. (scikit-learn.org)

Feature scaling is particularly important for distance-based methods. An attribute measured in thousands can dominate another measured in fractions, even when neither is inherently more relevant. Standardization commonly subtracts each feature’s mean and divides by its standard deviation. This changes the geometry of the data rather than merely changing its presentation. Dimensionality reduction, including principal component analysis, can simplify representations, but the resulting structure depends on which information is retained. (scikit-learn.org)

Principal approaches

Partitioning methods. K-means clustering divides observations into a specified number $k$ of groups. Its objective is

\min_{C_1,\ldots,C_k} \sum_{j=1}^{k}\sum_{x_i\in C_j} \lVert x_i-\mu_j\rVert^2,

where $\mu_j$ is the mean of cluster $C_j$ . This is a mathematical optimization problem with a within-cluster squared-distance loss function. The usual iterative algorithm alternates between assigning observations to their nearest center and recomputing centers. It can reach different local optima from different initializations; repeated runs help identify better solutions. Its objective favors compact groups and may poorly represent elongated or irregular structures. (introml.mit.edu)

Hierarchical methods. Hierarchical clustering constructs nested groups. Agglomerative procedures begin with individual observations and repeatedly merge groups; divisive procedures begin with a larger group and split it. A dendrogram displays the hierarchy, and cutting the tree at a selected level produces a partition. Linkage rules determine how separation between groups is calculated: single linkage uses the closest pair, complete linkage the farthest pair, and average linkage the average pairwise distance. Ward’s method selects mergers according to increases in within-cluster squared variation. (online.stat.psu.edu)

Density-based methods. DBSCAN identifies dense neighborhoods using a distance threshold and a minimum neighborhood size. It builds clusters around connected core observations, attaches eligible border observations, and labels remaining observations as noise. It can discover irregularly shaped groups without specifying their number in advance. However, its results depend on the neighborhood parameters, and a single density scale can be unsuitable when clusters have markedly different densities. (scikit-learn.org)

Model-based methods. A Gaussian mixture model represents data as a weighted combination of Gaussian distributions. Each observation receives component-membership probabilities, allowing soft rather than exclusively hard assignments. Parameters are commonly fitted using the expectation–maximization algorithm for maximum likelihood estimation. Different covariance structures permit different component shapes. The number of mixture components need not equal the number of substantively meaningful groups. (scikit-learn.org)

Spectral methods. Spectral clustering represents similarities through a graph and uses eigenvectors of a graph Laplacian to construct a representation for partitioning. It can identify nonconvex groups that are poorly described by centers and spreads. Results depend strongly on the construction of the similarity graph. (scikit-learn.org)

Choosing and evaluating clusters

There is generally no uniquely correct number of clusters independent of the analytical purpose. Some methods require a number explicitly; others determine it indirectly through thresholds or model-selection criteria. The elbow heuristic examines where additional clusters yield diminishing improvements in an objective, but a clear elbow need not exist. Mixture models can instead be compared using penalized likelihood criteria. (introml.mit.edu)

Internal evaluation uses the observations and cluster assignments themselves. The silhouette coefficient compares an observation’s average distance within its cluster with its average distance to the nearest other cluster. Values approach 1 for well-separated assignments, lie near 0 around overlapping boundaries, and can be negative for poorly matched assignments. Such measures embody particular geometric assumptions; silhouette scores tend to favor compact, separated clusters over some density-based structures. (scikit-learn.org)

External evaluation compares a clustering with an independent reference grouping. The adjusted Rand index measures agreement in pairwise grouping while adjusting for chance. It is unaffected by arbitrary permutations of cluster labels. Agreement with reference labels answers a different question from whether the clustering is internally coherent. (scikit-learn.org)

Applications and interpretation

Applications include customer segmentation, document grouping, image segmentation, and biological data exploration. In ecology, for example, sample sites can be grouped by species composition. Clustering can also support anomaly detection by identifying observations that fall outside dense or well-supported groups. (online.stat.psu.edu)

Interpretation remains conditional on the variables, similarity measure, algorithm, and parameter settings. An algorithm can partition data even when the resulting groups have little substantive meaning. Cluster descriptions therefore concern patterns in the chosen representation; a favorable numerical score alone does not establish that the groups correspond to distinct real-world populations. (introml.mit.edu)