Cluster analysis

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.

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 $x,z$ implies a mismatch between $x,y$ or $y,z$, 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.

The nearest cross-pair distance determines the next merge. At a threshold, clusters are connected components of the graph joining pairs below that threshold. This handles nonconvex shapes but can join otherwise separate groups through a chain of intermediate observations.