In statistics, Ward's method is a criterion applied in hierarchical cluster analysis. Ward's minimum variance method is a special case of the objective function approach originally presented by Joe H. Ward, Jr. Ward suggested a general agglomerative hierarchical clustering procedure, where the criterion for choosing the pair of clusters to merge at each step is based on the optimal value of an objective function. This objective function could be "any function that reflects the investigator's purpose." Many of the standard clustering procedures are contained in this very general class. To illustrate the procedure, Ward used the example where the objective function is the error sum of squares, and this example is known as Ward's method or more precisely Ward's minimum variance method. The nearest-neighbor chain algorithm can be used to find the same clustering defined by Ward's method, in time proportional to the size of the input distance matrix and space linear in the number of points being clustered.
The minimum variance criterion Ward's minimum variance criterion minimizes the total within-cluster variance. To implement this method, at each step find the pair of clusters that leads to minimum increase in total within-cluster variance after merging. This increase is a weighted squared distance between cluster centers. At the initial step, all clusters are singletons (clusters containing a single point). To apply a recursive algorithm under this objective function, the initial distance between individual objects must be (proportional to) squared Euclidean distance. The initial cluster distances in Ward's minimum variance method are therefore defined to be the squared Euclidean distance between points:
d i j = d ( { X i } , { X j } ) = ‖ X i − X j ‖ 2 . {\displaystyle d_{ij}=d(\{X_{i}\},\{X_{j}\})={\|X_{i}-X_{j}\|^{2}}.}
Note: In software that implements Ward's method, it is important to check whether the function arguments should specify Euclidean distances or squared Euclidean distances.
Lance–Williams algorithms Ward's minimum variance method can be defined and implemented recursively by a Lance–Williams algorithm. The Lance–Williams algorithms are an infinite family of agglomerative hierarchical clustering algorithms which are represented by a recursive formula for updating cluster distances at each step (each time a pair of clusters is merged). At each step, it is necessary to optimize the objective function (find the optimal pair of clusters to merge). The recursive formula simplifies finding the optimal pair. Suppose that clusters C i {\displaystyle C_{i}} and C j {\displaystyle C_{j}} were next to be merged. At this point all of the current pairwise cluster distances are known. The recursive formula gives the updated cluster distances following the pending merge of clusters C i {\displaystyle C_{i}} and C j {\displaystyle C_{j}} . Let
d i j {\displaystyle d_{ij}} , d i k {\displaystyle d_{ik}} , and d j k {\displaystyle d_{jk}} be the pairwise distances between clusters C i {\displaystyle C_{i}} , C j {\displaystyle C_{j}} , and C k {\displaystyle C_{k}} , respectively,
d ( i j ) k {\displaystyle d_{(ij)k}} be the distance between the new cluster C i ∪ C j {\displaystyle C_{i}\cup C_{j}} and C k {\displaystyle C_{k}} . An algorithm belongs to the Lance-Williams family if the updated cluster distance d ( i j ) k {\displaystyle d_{(ij)k}} can be computed recursively by
… excerpt ends here. Continue reading the full article.
