Nearest-neighbor chain algorithm

Many problems in data analysis concern clustering, grouping data items into clusters of closely related items. Hierarchical clustering is a version of cluster analysis in which the clusters form a hierarchy or tree-like structure rather than a strict partition of the data items. In some cases, this type of clustering may be performed as a way of performing cluster analysis at multiple different scales simultaneously. In others, the data to be analyzed naturally has an unknown tree structure and the goal is to recover that structure by performing the analysis. Both of these kinds of analysis can be seen, for instance, in the application of hierarchical clustering to biological taxonomy. In this application, different living things are grouped into clusters at different scales or levels of similarity (species, genus, family, etc). This analysis simultaneously gives a multi-scale grouping of the organisms of the present age, and aims to accurately reconstruct the branching process or evolutionary tree that in past ages produced these organisms. The input to a clustering problem consists of a set of points. In agglomerative clustering methods, the input also includes a distance function defined on the points, or a numerical measure of their dissimilarity. The distance or dissimilarity should be symmetric: the distance between two points does not depend on which of them is considered first. However, unlike the distances in a metric space, it is not required to satisfy the triangle inequality. The nearest-neighbor chain algorithm uses a smaller amount of time and space than the greedy algorithm by merging pairs of clusters in a different order. In this way, it avoids the problem of repeatedly finding closest pairs. Nevertheless, for many types of clustering problem, it can be guaranteed to come up with the same hierarchical clustering as the greedy algorithm despite the different merge order. ==The algorithm==

Intuitively, the nearest neighbor chain algorithm repeatedly follows a chain of clusters where each cluster is the nearest neighbor of the previous one, until reaching a pair of clusters that are mutual nearest neighbors. In more detail, the algorithm performs the following steps: • Initialize the set of active clusters to consist of one-point clusters, one for each input point. • Let be a stack data structure, initially empty, the elements of which will be active clusters. • While there is more than one cluster in the set of clusters: • If is empty, choose an active cluster arbitrarily and push it onto . • Let be the active cluster on the top of . Compute the distances from to all other clusters, and let be the nearest other cluster. • If is already in , it must be the immediate predecessor of . Pop both clusters from and merge them. • Otherwise, if is not already in , push it onto . When it is possible for one cluster to have multiple equal nearest neighbors, then the algorithm requires a consistent tie-breaking rule. For instance, one may assign arbitrary index numbers to all of the clusters, and then select (among the equal nearest neighbors) the one with the smallest index number. This rule prevents certain kinds of inconsistent behavior in the algorithm; for instance, without such a rule, the neighboring cluster might occur earlier in the stack than as the predecessor of . ==Time and space analysis==

Each iteration of the loop performs a single search for the nearest neighbor of a cluster, and either adds one cluster to the stack or removes two clusters from it. Every cluster is only ever added once to the stack, because when it is removed again it is immediately made inactive and merged. There are a total of clusters that ever get added to the stack: single-point clusters in the initial set, and internal nodes other than the root in the binary tree representing the clustering. Therefore, the algorithm performs pushing iterations and popping iterations. Each of these iterations may spend time scanning as many as inter-cluster distances to find the nearest neighbor. The total number of distance calculations it makes is therefore less than . For the same reason, the total time used by the algorithm outside of these distance calculations is . Since the only data structure is the set of active clusters and the stack containing a subset of the active clusters, the space required is linear in the number of input points. ==Correctness==

For the algorithm to be correct, it must be the case that popping and merging the top two clusters from the algorithm's stack preserves the property that the remaining clusters on the stack form a chain of nearest neighbors. Additionally, it should be the case that all of the clusters produced during the algorithm are the same as the clusters produced by a greedy algorithm that always merges the closest two clusters, even though the greedy algorithm will in general perform its merges in a different order than the nearest-neighbor chain algorithm. Both of these properties depend on the specific choice of how to measure the distance between clusters. A distance function on clusters is defined to be reducible if, for every three clusters , and in the greedy hierarchical clustering such that and are mutual nearest neighbors, the following inequality holds: :. If a distance function has the reducibility property, then merging two clusters and can only cause the nearest neighbor of to change if that nearest neighbor was one of and . This has two important consequences for the nearest neighbor chain algorithm. First, it can be shown using this property that, at each step of the algorithm, the clusters on the stack form a valid chain of nearest neighbors, because whenever a nearest neighbor becomes invalidated it is immediately removed from the stack. Second, and even more importantly, it follows from this property that, if two clusters and both belong to the greedy hierarchical clustering, and are mutual nearest neighbors at any point in time, then they will be merged by the greedy clustering, for they must remain mutual nearest neighbors until they are merged. It follows that each mutual nearest neighbor pair found by the nearest neighbor chain algorithm is also a pair of clusters found by the greedy algorithm, and therefore that the nearest neighbor chain algorithm computes exactly the same clustering (although in a different order) as the greedy algorithm. ==Application to specific clustering distances==

Ward's method Ward's method is an agglomerative clustering method in which the dissimilarity between two clusters and is measured by the amount by which merging the two clusters into a single larger cluster would increase the average squared distance of a point to its cluster centroid. That is, :d(A,B)=\sum_{x\in A, y\in B} \frac{d^2(x,y)} - \sum_{x,y\in A} \frac{d^2(x,y)} - \sum_{x,y\in B} \frac{d^2(x,y)}. Expressed in terms of the centroid c_A and cardinality n_A of the two clusters, it has the simpler formula :d(A,B)=\frac{d^2(c_a,c_b)}{1/n_A + 1/n_B}, allowing it to be computed in constant time per distance calculation. Although highly sensitive to outliers, Ward's method is the most popular variation of agglomerative clustering both because of the round shape of the clusters it typically forms and because of its principled definition as the clustering that at each step has the smallest variance within its clusters. Alternatively, this distance can be seen as the difference in k-means cost between the new cluster and the two old clusters. Ward's distance is also reducible, as can be seen more easily from a different formula for calculating the distance of a merged cluster from the distances of the clusters it was merged from: :d(A\cup B,C) = \frac{n_A+n_C}{n_A+n_B+n_C} d(A,C) + \frac{n_B+n_C}{n_A+n_B+n_C} d(B,C) - \frac{n_C}{n_A+n_B+n_C} d(A,B). Distance update formulas such as this one are called formulas "of Lance–Williams type" after the work of . If d(A,B) is the smallest of the three distances on the right hand side (as would necessarily be true if A and B are mutual nearest-neighbors) then the negative contribution from its term is cancelled by the n_C coefficient of one of the two other terms, leaving a positive value added to the weighted average of the other two distances. Therefore, the combined distance is always at least as large as the minimum of d(A,C) and d(B,C), meeting the definition of reducibility. Because Ward's distance is reducible, the nearest-neighbor chain algorithm using Ward's distance calculates exactly the same clustering as the standard greedy algorithm. For points in a Euclidean space of constant dimension, it takes time and space . Single linkage In single-linkage or nearest-neighbor clustering, the oldest form of agglomerative hierarchical clustering, Centroid distance Another distance measure commonly used in agglomerative clustering is the distance between the centroids of pairs of clusters, also known as the weighted group method. ==History==

The nearest-neighbor chain algorithm was developed and implemented in 1982 by Jean-Paul Benzécri and J. Juan. They based this algorithm on earlier methods that constructed hierarchical clusterings using mutual nearest neighbor pairs without taking advantage of nearest neighbor chains. ==References==