Ward’s method

Topic of Hierarchical clustering and kernel density estimation, part of Statistical learning

Ward’s method

Type	Topic
Taught in	Hierarchical clustering and kernel density estimation
Part	Statistical learning

Agglomerative clustering that at each step merges the two clusters whose union least increases the total within-cluster sum of squares, the criterion k-means minimises. In R it is hclust(..., method = \"ward.D2\").

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.

Ward’s method

In Hierarchical clustering and kernel density estimation

Used in

See also