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
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
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
In the theory of cluster analysis, the nearest-neighbor chain algorithm is an algorithm that can speed up several methods for agglomerative hierarchical clustering. These are methods that take a collection of points as input, and create a hierar ...
can be used to find the same clustering defined by Ward's method, in time proportional to the size of the input
distance matrix
In mathematics, computer science and especially graph theory, a distance matrix is a square matrix (two-dimensional array) containing the distances, taken pairwise, between the elements of a set. Depending upon the application involved, the ''dist ...
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
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
under this
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
, the initial distance between individual objects must be (proportional to) squared
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
.
The initial cluster distances in Ward's minimum variance method are therefore defined to be the squared Euclidean distance between points:
:
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
and
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
and
. Let
*
,
, and
be the pairwise distances between clusters
,
, and
, respectively,
*
be the distance between the new cluster
and
.
An algorithm belongs to the Lance-Williams family if the updated cluster distance
can be computed recursively by
:
where
and
are parameters, which may depend on cluster sizes, that together with the cluster distance function
determine the clustering algorithm. Several standard clustering algorithms such as
single linkage,
complete linkage, and group average method have a recursive formula of the above type. A table of parameters for standard methods is given by several authors.
Ward's minimum variance method can be implemented by the Lance–Williams formula. For disjoint clusters
and
with sizes
and
respectively:
:
Hence Ward's method can be implemented as a Lance–Williams algorithm with
:
Variations
The popularity of the Ward's method has led to variations of it. For instance, Ward
p introduces the use of cluster specific feature weights, following the intuitive idea that features could have different degrees of relevance at different clusters.
References
Further reading
* Everitt, B. S., Landau, S. and Leese, M. (2001), ''Cluster Analysis, 4th Edition'', Oxford University Press, Inc., New York; Arnold, London. {{ISBN, 0340761199
* Hartigan, J. A. (1975), ''Clustering Algorithms'', New York: Wiley.
*
Jain, A. K. and Dubes, R. C. (1988), ''Algorithms for Clustering Data'', New Jersey: Prentice–Hall.
* Kaufman, L. and Rousseeuw, P. J. (1990), ''Finding Groups in Data: An Introduction to Cluster Analysis'', New York: Wiley.
Cluster analysis algorithms