The Anchors Hierachy: Using the triangle inequality to survive high dimensional data

This paper is about metric data structures in high-dimensional or non-Euclidean space that permit cached sufficient statistics accelerations of learning algorithms. It has recently been shown that for less than about 10 dimensions, decorating kd-trees with additional"cached sufficient statistics"such as first and second moments and contingency tables can provide satisfying acceleration for a very wide range of statistical learning tasks such as kernel regression, locally weighted regression, k-means clustering, mixture modeling and Bayes Net learning. In this paper, we begin by defining the anchors hierarchy - a fast data structure and algorithm for localizing data based only on a triangle-inequality-obeying distance metric. We show how this, in its own right, gives a fast and effective clustering of data. But more importantly we show how it can produce a well-balanced structure similar to a Ball-Tree (Omohundro, 1991) or a kind of metric tree (Uhlmann, 1991; Ciaccia, Patella,&Zezula, 1997) in a way that is neither"top-down"nor"bottom-up"but instead"middle-out". We then show how this structure, decorated with cached sufficient statistics, allows a wide variety of statistical learning algorithms to be accelerated even in thousands of dimensions.

It has recently been shown that for less than about 10 dimensions, decorating kd trees with additional "cached sufficient statis tics" such as fi rst and second moments and contingency tables can provide satisfying ac celeration for a very wide range of statistical learning tasks such as kernel regression, lo cally weighted regression, k-means clustering, mixture modeling and Bayes Net learning.
In this paper, we begin by defining the an chors hierarchy-a fast data structure and algorithm for localizing data based only on a triangle-inequality-obeying distance metric. We show how this, in its own right, gives a fast and effective clustering of data. But more importantly we show how it can pro duce a well-balanced structure similar to a Ball-Tree (Omohundro, 1991) or a kind of metric tree (Uhlmann, 1991;Ciaccia, Patella, & Zezula, 1997) in a way that is neither "top down" nor "bottom-up" but instead "middle out" . We then show how this structure, dec orated with cached sufficient statistics, al lows a wide variety of statistical learning al gorithms to be accelerated even in thousands of dimensions. 1

Cached Sufficient Statistics
This paper is not about new ways of learning from data, but instead how to allow a wide variety of cur rent learning methods, case-based tools, and statistics methods to scale up to large datasets in a computa-tionally tractable fashion. A cached sufficient statis tics representation is a data structure that summarizes statistical information from a large dataset. For exam ple, human users, or statistical programs, often need to query some quantity (such as a mean or variance) about some subset of the attributes (such as size, posi tion and shape) over some subset of the records. When this happens, we want the cached sufficient statistic representation to intercept the request and, instead of answering it slowly by database accesses over huge numbers of records, answer it immediately.
For all-discrete (categorical) datasets, cached sufficient statistics structures include frequent sets (Agrawal, Mannila, Srikant, Toivonen, & Verkamo, 1996) (which accelerate certain counting queries given very sparse high dimensional data), datacubes (Harinarayan, Ra jaraman, & Ullman, 1996) (which accelerate count ing given dense data up to about 7 dimensions), and all-dimensions-trees (Moore & Lee, 1998;Anderson & Moore, 1998) (which accelerate dense data up to about 100 dimensions). The acceleration of counting means that entropies, mutual information and corre lation coefficients of subsets of attributes can be com puted quickly, and (Moore & Lee, 1998) show how this can mean 1000-fold speed-ups for Bayes net learning and dense association rule learning.
But what about real-valued data? By means of mrkd trees (multiresolution k-dimensional trees) (Deng & Moore, 1995;Moore, Schneider, & Deng, 1997;Pelleg & Moore, 1999, 2000 (an extension of kd-trees (Fried man, Bentley, & Finkel, 1977)) we can perform clus tering, and a very wide class of non-parametric statis tical techniques on enormous data sources hundreds of times faster than previous algorithms (Moore, 1999), but only up to about 8-10 dimensions.
This paper replaces the kd-trees with a certain kind of Metric tree (Uhlmann, 1991) and investigates the ex tent to which this replacement allows acceleration on real-valued queries in higher dimensions. To achieve this, in Section 3 we introduce a new tree-free ag-glomerative method for very quickly computing a spa tial hierarchy (called the anchors hierarchy) -this is needed to help generate an efficient structure for the metric tree. And while investigating the effectiveness of metric trees we introduce three new cached suffi cient statistics algorithms as examples of a much wider range of possibilities for exploiting these structures while implementing statistical and learning operations on large data.

Metric Trees
Metric Trees, closely related to Ball trees (Omohundro, 1991), are a hierarchical structure for representing a set of points. They only make the assumption that the distance function between points is a metric: Metric trees do not need to assume, for example, that the points are in a Euclidean space in which vector components of the datapoints can be addressed di rectly. Each node n of the tree represents a set of datapoints, and contains two fields: npivot and nradi u s· The tree is constructed to ensure that node n has n radius = maxxEn D(npivot , x) meaning that if x is owned by node n, then If a node contains no more than some threshold Rmin number of points, it is a leaf node, and contains a list of pointers to all the points that it owns.
If a node contains more than Rmin points, it has two child nodes, called Child1 ( n) and Child2 ( n). The points owned by the two children partition the points owned by n: How are the child pivots chosen? There are numer ous schemes in the Metric tree literature. One simple method is as follows: Let fi be the datapoint inn with greatest distance from npivot. Let h be the datapoint in n with greatest distance from fi. Give the set of points closest to fi to Child1 ( n), the set of points clos est of /2 to Child2(n), and then set Childt(n) p i vo t equal to the centroid of the points owned by Child1 ( n) and set Child2 ( n) pivo t equal to the centroid of the points owned by Child2 ( n). This method has the merit that the cost of splitting n is only linear in the number of points owned by n. Entries 0 with prob 2/3, 1 with prob 1/3 Attributes 201 .. 1000 All entries 0 with probability 0.5 1 with probability 0.5 All entries 0 with probability 0.5 1 with probability 0.5 Figure 1: A spreadsheet with 100,000 rows and 1000 columns. In the rightmost 80 percent of the dataset all values are completely random. In the leftmost 20 percent there are more 1 's than 0 's in the top half and more O's than 1's in the bottom half. kd-trees structure this poorly. Metric trees structure it well.
kd-trees, upon which earlier accelerations were based, are similar in spirit to decision trees. Each kd-tree node has two children, specified by a splitting dimen sion, nsplitdim, and a splitting value, nspli t val. A point is owned by child 1 if its nsplitdim 'th component is less than nsplitval, and by child 2 otherwise. Notice kd trees thus need to access vector components directly. kd-trees grow top-down. Each node's children are cre ated by splitting on the widest (or highest entropy) dimension.
kd-trees are very effective in low dimensions at quickly localizing datapoints: after travelling down a few lev els in the tree, all the datapoints in one leaf tend to be much closer to each other than to datapoints not in the same leaf (this loose description can be formal ized). That in turn leads to great accelerations when kd-trees are used for their traditional purposes (nearest neighbor retrieval and range searching) and also when they are used with cached sufficient statistics. But in high dimensions this property disappears. Consider the dataset in Figure 1. The datapoints come from two classes. In class A, attributes 1 through 200 are independently set to 1 with probability 1/3. In class B, attributes 1 through 200 are independently set to 1 with probability 2/3. In both classes attributes 201 through 1000 are independently set to 1 with proba bility 1/2. The marginal distribution of each attribute is half 1's and half O's, so the kd-tree does not know which attributes are best to split on. And even if it split on one of the first 200 attributes, its left child would only contain 2/3 of class A and 1/3 of class B (with converse proportions for the right child). The kd tree would thus need to split at least 10 times (mean ing thousands of nodes) until at least 99 percent of the datapoints were in a node in which 99 percent of the datapoints were from the same class.
For a metric tree, it is easy to show that the very first split will, with very high probability, put 99 percent of class A into one child and 99 percent of class B into the other. The consequence of this difference is that for a nearest neighbor algorithm, a search will only need to visit half the datapoints in a metric tree, but many more in a kd-tree. We similarly expect cached sufficient statistics to benefit from metric trees. 3

The Anchors Hierarchy
Before describing the fi rst of our metric-tree-based cached sufficient statistics algorithms, we introduce the Anchors Hierarchy, a method of structuring the metric tree that is intended to quickly produce nodes that are more suited to our task than the simple top down procedure described earlier. As we will see, cre ating this hierarchy is similar to performing the statis tical operation of clustering-one example of the kind of operation we wish to accelerate. This creates a chicken and egg problem: we'd like to use the met ric tree to find a good clustering and we'd like to fi nd a good clustering in order to build the metric tree. The solution we give here is a simple algorithm that creates an effective clustering cheaply even in the absence of the tree.
The algorithm maintains a set of anchors A {a 1 , .. a k }. The i'th anchor, a i , has a pivot a ; pivot, and an explicit list of the set of points that are closer to a i than any other anchor: (3) where Vi, j, p, This list is sorted in decreasing order of distance to a i , and so we can define the radius of a i to be the furthest distance of any of the points owned by a i to its pivot simply as At each iteration, a new anchor is added to A, and the points it must own (according to the above con straints) are computed efficiently. The new anchor, a new , attempts to steal points from each of the exist ing anchors. To steal from a i , we iterate through the sorted list of points owned by a i . Each point is tested to decide whether it is closer to a i or a new . However, if we reach a point in the list at which we inspect x� and we discover that (6) we can deduce that the remainder of the points in a i 's list cannot possibly be stolen because for k 2: 0: so D (x�+k,a i pivot ) :::; D (a new pivot,X�+k ). This saving gets very significant when there are many anchors be cause most of the old anchors discover immediately that none of their points can be stolen by a new .
How is the new anchor a new chosen? We simply find the current anchor am a x rad with the largest radius, and choose the pivot of a new to be the point owned by     To create k anchors in this fashion reqmres no pre existing cached statistics or tree. Its cost can be as high as Rk for R datapoints, but in low dimensions, or for non-uniformly-distributed data, it requires an expected O(R log k) distance comparisons for k << R.

3.1
Middle-out building of a Cached statistic metric tree We now describe how we build the metric trees used in this paper. Instead of "top-down" or "bottom up" (which, for R datapoints is an O(R2) operation, though can be reduced in cost by approximations) we build it "middle-out" . We create an anchors hierarchy containing VR anchors. These anchors are all assigned to be nodes in the tree. Then the most compatible pair of nodes are merged to form a parent node. The compatibility of two nodes is defined to be the radius of the smallest parent node that contains them both completely-the smaller the better.
This proceeds bottom up from the VR anchors until all nodes have been agglomerated into one tree. When this is completed we must deal with the fact that each of the leaf nodes (there are VR of them) contains VR points on average. We will subdivide them further. This is achieved by, for each of the leaves, recursively calling this whole tree building procedure (including this bit), on the set of datapoints in that leaf. The base case of the recursion are nodes containing fewer than R min points. Figures 7-10 give an example.    We use the following cached statistics: each node con tains a count of the number of points it owns, and the centroid of all the points it owns1.
We first describe the naive K-means algorithm for pro ducing a clustering of the points in the input into [{ clusters. It partitions the data-points into [{ subsets such that all points in a given subset "belong" to some center. The algorithm keeps track of the centroids of the subsets, and proceeds in iterations. Before the first iteration the centroids are initialized to random values. The algorithm terminates when the centroid locations stay fixed during an iteration. In each iteration, the following is performed: 1. For each point x, find the centroid which is closest to x. Associate x with this centroid.
2. Re-estimate centroid locations by taking, for each centroid, the center of mass of points associated with it.
The K-means algorithm is known to converge to a local minimum of the distortion measure (that is, average squared distance from points to their class centroids). It is also known to be too slow for very large databases. Much of the related work does not attempt to con front the algorithmic issues directly. Instead, different methods of subsampling and approximation are pro posed.
1 In order for the concept of centroids to be meaningful we do require the ability to sum and scale datapoints, m addition to the triangle inequality Instead, we will use the metric trees, along with their statistics, to accelerate K-means with no approxima tion. This uses a similar approach to (Pelleg & Moore, 1999)'s kd-tree-based acceleration. Each pass of this new efficient K-means recurses over the nodes in the metric tree. The pass begins by a call to the following procedure with n set to be the root node, C set to be the set of centroids, and Cands set to also be the full set of centroids.
I<meansStep(node n, CentroidSet C, CentroidSet Cands) Invariant: we assume on entry that Cands are those members of C who are provably the only possible owners of the points in node n. Formally, we assume that Cands � C, and Vx En, (argminc E cD(x, c)) E Cands.
1. Reduce Cands: We attempt to prune the set of centroids that could possibly own datapoints from n. First, we identify c * E Cands, the candidate centroid closest to n p ivot. Then all other candi dates are judged relative to c * . For c E Cands, if D(c * , n pivo t) + R::; D(c, n p ivot) -R then delete c from the set of candidates, where R = nradius is the radius of node n. This cutoff rule will be discussed shortly.

Update statistics about new centroids:
The purpose of the K-means pass is to generate the centers of mass of the points owned by each cen troid. Later, these will be used to update all the centroid locations. In this step of the algorithm we accumulate the contribution to these centers of mass that are due to the datapoints inn. Depend ing on circumstances we do one of three things: • If there is only one candidate in Cands, we need not look at n's children. Simply use the information cached in the node n to award all the mass to this one candidate. • Else, if n is a leaf, iterate through all its dat apoints, awarding each to its closest centroid in Cands. Note that even if the top-level call had ]{ = 1000 centroids, we can hope that at the levels of leaves there might be far fewer centroids remaining in Cands, and so will see accelerations over conventional K means even if the search reaches the leaves. and soc cannot own any x inn.

Anomaly Detection
As an example of a non-parametric statistics operation that can be accelerated, consider a test for anomalous datapoints that proceeds by identifying points in low density regions. One such test consists of labeling a point as anomalous if the number of neighboring points within some radius is less than some threshold.
This operation requires counts within the nodes as the only cached statistic. Given a query point x, we again recurse over the tree in a depth first manner, trying the child closer to x before the further child. We main tain a count of the number of points discovered so far within the range, and another count-an upper bound on the number of points that could possibly be within range. At each point in the search we have an impres sive number of possibilities for pruning the search: 1. If the current node is entirely contained within the query radius, we simply add ncount to the count.
2. If the current node is entirely outside the query radius, we simply ignore this node, decrement ing the upper bound on the number of points by ncount · 3. If the count of the number of points found ever exceeds the threshold, we simply return FALSE the query is not an anomaly.
4. If the upper bound on the count ever drops be low threshold then return TRUE-the query is an anomaly.

Example 3: Grouping Attributes
The third example is designed to illustrate an impor tant use of high dimensional methods. Consider a dataset represented as a matrix in which rows corre spond to datapoints and columns correspond to at tributes. Occasionally, we may be more interested in groupings among attributes than among datapoints. If so, we can transpose the dataset and build the metric tree on attributes instead of datapoints.
For example, suppose we are interested in finding pairs of attributes that are highly positively correlated. Re member that the correlation coefficient between two attributes x and y is p(x, y) = :L)x;x)(y;y)/((J'x(J'y) where x; is the value of attribute x in the ith record. If we subtract the attribute means and divide by their standard deviations we may defi ne normalized values x i= (x;x ) /(J'x and Yi = (y;y)/(J'y· Then p(x,y) = l: xfyf = 1-D2(x*,y*)/2 (8) using Euclidean distance. Thus, for example, finding all pairs of attributes correlated above a certain level p corresponds to finding pairs with distances below �· There is no space to describe the details of the al gorithm using metric trees to collect all these close pairs. It is a special case of a general set of "all-pairs" algorithms described (albeit on conventional kd-trees) by (Gray & Moore, 2000) and related to the celebrated Barnes-Hut method (Barnes & Hut, 1986) for efficient R-hody simulation.

Empirical Results
The following results used the datasets in Table 1.
Each dataset had K-means applied to it, the non parametric anomaly detector, and all-pairs. For the latter two operations suitable threshold parameters were chosen so that the results were "interesting" (e.g. in the case of anomalies, so that about 10 percent of all datapoints were regarded as anomalous). This is im portant: all the algorithms do very well (far greater ac celerations) in extreme cases because of greater prun ing possibilities, and so our picking of "interesting" cases was meant to tax the acceleration algorithms as much as possible. For K-means, we ran three exper iments for each dataset in which J{ (the number of centroids) was varied between 3, 20 and 100.
The results in Table 2 show three numbers for each experiment. First, the number of distance compar isons needed by a regular (i.e. treeless) implemen tation of the algorithm. Second, the number of dis tance comparisons needed by the accelerated method using the cached-statistics-supplemented metric tree. And third, in bold, the speedup (the first number di vided by the second). For the artificial datasets, we restricted K-means experiments to those in which J{, the number of clusters being searched for, matched the actual number of clusters in the generated dataset.
The speedups in the two dimensional datasets are all excellent, but of course in two dimensions regu lar statistics-caching kd-trees would have given equal or better results. The higher dimensional cell and covtype datasets are more interesting-the statis tics caching metric trees give a substantial speedup whereas in other results we have established that kd trees do not. Notice that in several results, K=20 gave a worse speedup than K=3 or K= 100. Whether this is significant remains to be investigated.
The Reuters dataset gave poor results. This only has 10,000 records and appears to have little intrin sic structure. Would more records have produced bet ter results? Extra data was not immediately avail able at the time of writing and so, to test this the ory, we resorted to reduci ng the amount of data. The Reuters50 dataset has only half the documents, and its speedups are indeed worse. This gives some cre dence to the argument that if the amount of data was increased the anti-speedup of the metric trees would be reduced, and eventually might become profitable.
On anomaly detection and all-pairs, all methods per formed well, even on Reuters. There is wild variation in the speedup. This is an artifact of the choice of thresholds for each algorithm. If too large or too small pruning becomes trivial and the speedup is enormous. Table 3 investigates whether the "anchors" approach to building the tree has any advantage over the sim pler top-down approach. For the four datasets we tested, using K-means as the test, the speedups of us ing the anchors-constructed tree over the top-down constructed tree were modest (ranging from 20 per cent to 180 percent) but consistently positive. Similar results comparing the two tree growth methods for all pairs and anomalies give speedups of 2-fold to 6-fold.
As an aside, Table 4 examines the quality of the clustering created by the anchors algorithm. In all experiments so far, K-means was seeded with ran dom centroids. What if the anchors algorithm was used to generate the starting centroids? Table 4 shows, in the middle four columns, the distortion (sum squared distance from datapoints to their near est centroids) respectively for randomly-chosen cen troids, centroids chosen by anchors, centroids started randomly followed by 50 iterations of K-means and centroids started with anchors followed by 50 itera tions of K-means. Both before and after K-means, anchors show a substantial advantage except for the Reuters dataset.  Ta ble 2: Results on various datasets. Non-bold numbers show the number of distance computations needed in each experiment. Bold-face numbers show the speedup-how many times were the statistics-caching metric trees faster than conventional implementations in terms of numbers of distance computations? The columns labeled k = 3, k = 20 and k = 100 are for K-means.  "Random Start" are the distortion measures for randomly chosen centroids. "Anchors Start" are the distortion measures obtained when using the anchors hierarchy to generate initial centroids. The next two columns show the resulting distortion of random-start and anchors-start respectively after 50 iterations of K-means. The final two columns summarize the relative merits of anchors versus random: by what factor is anchor's distortion better than random's? "Start Benefit" shows the factor for the initial centroids. "End benefit" shows the factor for the final centroids.
Dataset k=3 k=20 k=100 cell 1.3 1.2 1.2 covtype 1.3 1.3 1.3 squiggles 1.6 1.5 1.6 gen10000-k20 2.8 2.7 2.7 Table 3: The factor by which using anchors to build the metric tree improves over using top-down building in terms of number of distance calculations needed.

6
Accelerating other learning algorithms The three cached-statistic metric tree algorithms in troduced in this paper were primarily intended as ex amples. A very wide range of both parametric and non-parametric methods are amenable to acceleration in a similar way. As further examples, and on our short-list for future work are: • Dependency trees (Meila, 1999), by modifying the all-pairs method above to the case of Kruskal's al gorithm for minimum spanning tree in Euclidean space (equivalently maximum spanning tree in correlation space). Additionally, although Mutual Information does not obey the triangle inequality, it can be bounded above (Meila, 2000) and below by Euclidean distance and so it should also be possible to apply this method to entropy based tree building for high-dimensional discrete data.
• Mixtures of spherical, axis aligned or general Gaussians. These are all modifications of the K means algorithm above and the mrkd-tree-based 7 acceleration of mixtures of Gaussians described in (Moore, 1999).
• Mixtures of multinomials for high dimensional discrete data.
• There are numerous other non-parametric statis tics, including n-point correlation functions used in astrophysics that we will apply these techniques to. In addition, Gaussian processes, certain neu ral net architectures, and case-based reasoning systems may be accelerated.

Discussion
The purpose of this paper has been to describe, discuss and empirically evaluate the use of metric trees to help statistical and learning algorithms scale up to datasets with large numbers of records and dimensions. In so doing, we have introduced the anchors hierarchy for building a promising first cut at a set of tree nodes effi ciently before the tree has been created. We have given three examples of cached-sufficient-statistics-based al gorithms built on top of these structures.
If there is no underlying structure in the data (e.g. if it is uniformly distributed) there will be little or no acceleration in high dimensions no matter what we do. This gloomy view, supported by recent theoret ical work in computational geometry (Indyk, Amir, Efrat, & Samet, 1999), means that we can only accel erate datasets that have interesting internal structure.
Resorting to empirical results with real datasets, how ever, there is room for some cautious optimism for real-world use.