Ward's method

Ward's method is a criterion used in hierarchical cluster analysis, named for Joe H. Ward, Jr., who proposed a general agglomerative clustering procedure in which the pair of clusters merged at each step is chosen by the optimal value of an objective function. In the common example Ward used, the objective function is the error sum of squares, which gives what is usually called Ward's minimum variance method. At every step the method merges the pair of clusters whose union produces the smallest increase in total within-cluster variance, measured as a weighted squared distance between cluster centers. It starts from singleton clusters and expects initial distances proportional to squared Euclidean distance. It can be written as a Lance-Williams recursive update, and the nearest-neighbor chain algorithm can compute the same clustering in time proportional to the size of the input distance matrix.