Adjusted Rand index

Topic of K-means clustering, part of Statistical learning · Also in Hierarchical clustering and kernel density estimation

Adjusted Rand index

Type	Topic
Taught in	K-means clustering · Hierarchical clustering and kernel density estimation
Part	Statistical learning

A measure of agreement between two partitions of the same items, built from the pairs placed together or apart in both and corrected for chance, so that identical partitions score 1 and random labelling scores about 0. It does not need cluster 1 to mean class 1.

In K-means clustering

From K-means clustering

Setosa is recovered as its own cluster: all 50 setosa flowers sit in cluster 2, and nothing else does. Versicolor and virginica are mixed, 39 against 14 in one cluster and 11 against 36 in the other. The adjusted Rand index compares the clustering with the species partition without requiring cluster 1 to mean species 1. On its chance-corrected scale, identical partitions score 1, and the index can be negative. The value 0.6201 is the agreement on this run. The direct sum of squared distances to the assigned centres reproduces tot.withinss to the tolerance in the check, which is the unweighted criterion \widetilde W.

In Hierarchical clustering and kernel density estimation

From Hierarchical clustering and kernel density estimation

The same scaled observations are clustered by four linkages, so the only change from one result to the next is the merge rule. Each tree is then cut into three groups and compared with the species labels by the adjusted Rand index. Those labels are not an input to the linkage. The index equals 1 when the two partitions agree up to the names of the groups, and its expectation is 0 when the labels are attached at random. Two univariate bandwidth selectors are also applied to petal length. They are different approximations to a bandwidth that balances bias and variance. Let iris_x be the matrix of iris measurements and iris_y the species labels, and let iris$Petal.Length be the petal-length column.

z <- scale(iris_x)
ari <- sapply(c("single", "complete", "average", "ward.D2"),
  function(method) {
    groups <- cutree(hclust(dist(z), method = method), k = 3)
    mclust::adjustedRandIndex(groups, iris_y)
  })
round(ari, 3)
#>    single complete average ward.D2
#>     0.558    0.573   0.562   0.615
c(rule_of_thumb = bw.nrd0(iris$Petal.Length),
  Sheather_Jones = bw.SJ(iris$Petal.Length))
#> rule_of_thumb Sheather_Jones
#>        0.5832         0.1920

The adjusted Rand indices are 0.558 for single linkage, 0.573 for complete linkage, 0.562 for average linkage, and 0.615 for Ward’s method (ward.D2). They tell how each three-group partition agrees with the iris species labels on this sample. Choosing a linkage because this agreement is high would make the labels part of model selection. In the same way, a bandwidth comparison needs its units: the rule-of-thumb bandwidth is 0.5832 and the Sheather–Jones bandwidth is 0.1920, and a width of 0.3 means something only relative to the variable being smoothed. Ward’s linkage is included as a fourth merge rule in the comparison. The three linkages derived above are single, complete, and average.

Key idea

Single linkage merges on the nearest cross-pair, complete linkage on the farthest, and average linkage on the mean of the cross-pairs, so the same points can grow a chain or a sequence of compact groups. A Gaussian kernel density estimate is a mixture of bumps centred at the data, with common covariance equal to the bandwidth matrix. Small bandwidths retain fine detail and sampling noise; large bandwidths erase both. The training likelihood drives the bandwidth to zero, for the same reason an unconstrained mixture covariance can collapse, so the scale is chosen by a held-out score or by mean integrated squared error.

Used in

Taught in K-means clustering · Hierarchical clustering and kernel density estimation
Also used in Hierarchical clustering and kernel density estimation
All 8 questions on K-means clustering

In K-means clustering

In Hierarchical clustering and kernel density estimation

Used in

See also