Cluster analysis groups observations using similarities or dissimilarities without supplied class labels. A distance choice specifies which features and scales matter. Agglomerative hierarchical clustering merges groups recursively, producing partitions at different resolutions rather than one intrinsically determined number of groups.
A cluster in cluster analysis is a nonempty group of observations treated as similar under the chosen representation and dissimilarity. A partition assigns each observation to exactly one cluster; agglomerative hierarchical clustering supplies a nested sequence of such partitions. An algorithmic cluster need not correspond to a distinct probabilistic population.
For a prescribed number of groups, minimize within-cluster squared Euclidean distances. At fixed assignments, differentiating the objective gives the mean as the optimal centroid. At fixed centroids, assigning each point to a nearest centroid minimizes its contribution. Alternating these steps cannot increase the objective but can converge to a local optimum, so multiple starts are useful. Empty clusters and ties need an explicit handling rule. The method favors roughly spherical groups and depends on variable scaling.
For distinct observations on the real line and , nearest-centre assignment produces contiguous blocks of the sorted observations because each Voronoi cell is an interval. The arithmetic means of distinct ordered blocks are strictly ordered, preserving this property at subsequent assignments. Initialize at distinct observed values so that the initial assignment has no empty cluster.
The empty-cluster repair in finite termination of K-means clustering also preserves contiguous blocks: an observation farthest from a centre over its assigned block lies at one of that block's endpoints, so transferring it to a new singleton splits the block into two contiguous blocks.
There are possible partitions into nonempty blocks: choose cuts among the gaps. Under the stable tie rule in finite termination of K-means clustering, every round after the first strictly reduces the objective until stopping, so a block partition cannot recur. The number of assignment, repair, and centre-update rounds is therefore at most . Check stability after each update without an additional update round; for , one update suffices.
For a finite dataset, alternate nearest-centre assignment and replacement of each centre by the centroid of its assigned observations. Keep the current assignment whenever an observation is tied between nearest centres. A changed assignment then strictly decreases the within-cluster sum of squared Euclidean distances; updating centres cannot increase it by the centroid sum-of-squares identity.
After each centre update, the centres are determined by the current partition of a set of observation indices. There are only finitely many such partitions, so a strictly improving sequence cannot revisit one and must stop. A convenient exact stopping test is to check after each update whether every observation is still assigned to a nearest centre. This proof is for algorithm termination; it does not guarantee a global minimum.
Empty clusters need an explicit convention. To retain exactly nonempty clusters, transfer an observation from a cluster with at least two members to each empty cluster, making it a singleton centred at that observation. This cannot increase the objective: the transferred observation now has squared distance zero, and no other contribution changes before centre updating. A deterministic choice is an eligible observation farthest from its currently assigned centre, with ties resolved by index. After the first round, an empty cluster can arise only during a strictly improving reassignment, so these repairs preserve the finite-termination argument.
For two distinct centroids in a Euclidean space, equal squared Euclidean distances expand to the displayed affine hyperplane. It is their perpendicular bisector; each closed half-space consists of points at least as close to the centroid on that side. This proves weak linear separability after a two-centroid nearest-assignment step, allowing ties on the boundary. Coincident centroids are an essential exception: every point ties and the distance comparison supplies no nonzero normal vector.
For a nonempty finite collection of Euclidean vectors, its sample mean uniquely minimizes the sum of squared Euclidean distances to a proposed centroid . Expand each squared Euclidean norm around and use to cancel the cross term. The displayed identity leaves a nonnegative term , equal to zero exactly at .
The index measures similarity of finite sets by shared presence relative to total presence. For binary profiles it ignores joint absences, unlike the simple matching coefficient. When both sets are empty, define the similarity to be one. The complementary Jaccard distance measures dissimilarity.
The dissimilarity is the number of mismatched presences divided by the number of coordinates present in at least one profile. It differs from normalized Hamming distance because coordinates absent from both profiles do not enter its denominator. Define the distance of two empty sets to be zero.
A dissimilarity matrix records pairwise separation of observations or profiles. Usually it is symmetric, nonnegative and zero on the diagonal. A metric space additionally requires the triangle inequality and separation of distinct profiles. Agglomerative hierarchical clustering can be applied to many dissimilarity matrices that are not Euclidean distance matrices; the claimed geometry must be checked separately.
For binary vectors, this similarity counts agreements on both presences and absences. Its complement is the normalized Hamming distance. Whether joint absences should count as similarity depends on the application; rare-presence data may call for a different coefficient.
The displayed distance is the normalized Hamming distance. Each coordinate mismatch between implies a mismatch between or , so summing the indicator inequalities proves the triangle inequality. Nonnegativity, symmetry and separation follow immediately. It is a metric on profiles; on separately labelled individuals with identical profiles it is a pseudometric.
Start with singleton clusters and repeatedly merge the two clusters with the smallest chosen intercluster dissimilarity. Single-linkage clustering uses the smallest cross-pair distance; complete-linkage clustering uses the largest. Merge heights and sensitivity to ties help assess a proposed number of groups.
Ward clustering merges the pair causing the smallest increase in within-cluster sum of squares. Expanding each cluster's squared deviations about the merged mean gives the displayed increase. Its Euclidean sum-of-squares interpretation must not be asserted for arbitrary non-Euclidean dissimilarities.
Average linkage merges the pair with the smallest mean cross-pair dissimilarity. This differs from the minimum used by single-linkage clustering and the maximum used by complete-linkage clustering. The convention here weights individual cross-pairs equally; weighting already formed clusters equally is a different algorithm.
The min and max cross-pair definitions of single-linkage clustering and complete-linkage clustering remain meaningful for a symmetric nonnegative dissimilarity matrix that violates the triangle inequality. Such a calculation gives a valid algorithmic dendrogram, but does not turn the original matrix into Euclidean distances. A triangle-inequality counterexample identifies that source defect without requiring invented replacement data.
A dendrogram displays successive cluster merges, with the height of each merge equal to its intercluster dissimilarity. Cutting at a height gives a partition. Single-linkage clustering measures the closest cross-pair and can form chains, while complete-linkage clustering measures the farthest cross-pair and favors smaller within-cluster diameters.
The farthest cross-pair distance determines the next merge. It favors groups with small diameter and reduces the chaining effect of single-linkage clustering, but can be sensitive to isolated extreme observations. Ties can affect intermediate partitions.
Articles by others on the same topic
Cluster analysis is a statistical technique used to group a set of objects or data points into clusters based on their similarities or distances from one another. The main goal of cluster analysis is to identify patterns within a dataset and to categorize data points into groups so that points within the same group (or cluster) are more similar to each other than they are to points in other groups.
