Efficient Clustering of High-Dimensional Data Sets with ...

1 Efficient Clustering of High-Dimensional Data Sets with Application to Reference Matching Andrew McCallum Kamal Nigam Lyle H. Ungar .. WhizBang! Labs - Research School of Computer Science Computer and Info. Science 4616 Henry Street Carnegie Mellon University University of Pennsylvania Pittsburgh, PA USA Pittsburgh, PA USA Philadelphia, PA USA. ABSTRACT 1. INTRODUCTION. Many important problems involve Clustering large datasets. Unsupervised Clustering techniques have been applied to Although naive implementations of Clustering are computa- many important problems. By Clustering patient records, tionally expensive, there are established efficient techniques health care trends are discovered. By Clustering address for Clustering when the dataset has either (1) a limited num- lists, duplicate entries are eliminated. By Clustering astro- ber of clusters, (2) a low feature dimensionality, or (3) a nomical data, new classes of stars are identified.

2 By cluster- small number of data points. However, there has been much ing documents, hierarchical organizations of information are less work on methods of efficiently Clustering datasets that derived. To address these applications, and many others, a are large in all three ways at once for example, having variety of Clustering algorithms have been developed. millions of data points that exist in many thousands of di- mensions representing many thousands of clusters. However, traditional Clustering algorithms become compu- tationally expensive when the data set to be clustered is We present a new technique for Clustering these large, high- large. There are three different ways in which the data set dimensional datasets. The key idea involves using a cheap, can be large: (1) there can be a large number of elements in approximate distance measure to efficiently divide the data the data set, (2) each element can have many features, and into overlapping subsets we call canopies.

3 Then cluster- (3) there can be many clusters to discover. Recent advances ing is performed by measuring exact distances only between in Clustering algorithms have addressed these efficiency is- points that occur in a common canopy. Using canopies, large sues, but only partially. For example, KD-trees [15] provide Clustering problems that were formerly impossible become for efficient EM-style Clustering of many elements, but re- practical. Under reasonable assumptions about the cheap quire that the dimensionality of each element be small. An- distance metric, this reduction in computational cost comes other algorithm [3] efficiently performs K-means Clustering without any loss in Clustering accuracy. Canopies can be by finding good initial starting points, but is not efficient applied to many domains and used with a variety of cluster- when the number of clusters is large.

4 There has been al- ing approaches, including Greedy Agglomerative Clustering , most no work on algorithms that work efficiently when the K-means and Expectation-Maximization. We present ex- data set is large in all three senses at once when there are perimental results on grouping bibliographic citations from millions of elements, many thousands of features, and many the reference sections of research papers. Here the canopy thousands of clusters. approach reduces computation time over a traditional clus- tering approach by more than an order of magnitude and This paper introduces a technique for Clustering that is effi- decreases error in comparison to a previously used algorithm cient when the problem is large in all of these three ways at by 25%. once. The key idea is to perform Clustering in two stages, first a rough and quick stage that divides the data into over- Categories and Subject Descriptors lapping subsets we call canopies, then a more rigorous [Pattern Recognition]: Clustering ; [Information final stage in which expensive distance measurements are Storage and Retrieval]: Information Search and Retrieval only made among points that occur in a common canopy.

5 Clustering This differs from previous Clustering methods in that it uses two different distance metrics for the two stages, and forms overlapping regions. The first stage can make use of extremely inexpensive meth- ods for finding data elements near the center of a region. Many proximity measurement methods, such as the inverted index commonly used in information retrieval systems, are very efficient in high dimensions and can find elements near the query by examining only a small fraction of a data set. Variants of the inverted index can also work for real-valued We divide the Clustering process into two stages. In the first data. stage we use the cheap distance measure in order to cre- ate some number of overlapping subsets, called canopies.. Once the canopies are built using the approximate distance A canopy is simply a subset of the elements ( data measure, the second stage completes the Clustering by run- points or items) that, according to the approximate simi- ning a standard Clustering algorithm using a rigorous, and larity measure, are within some distance threshold from a thus more expensive distance metric.

6 However, significant central point. Significantly, an element may appear under computation is saved by eliminating all of the distance com- more than one canopy, and every element must appear in at parisons among points that do not fall within a common least one canopy. Canopies are created with the intention canopy. Unlike hard-partitioning schemes such as block- that points not appearing in any common canopy are far ing [13] and KD-trees, the overall algorithm is tolerant to enough apart that they could not possibly be in the same inaccuracies in the approximate distance measure used to cluster. Since the distance measure used to create canopies create the canopies because the canopies may overlap with is approximate, there may not be a guarantee of this prop- each other. erty, but by allowing canopies to overlap with each other, by choosing a large enough distance threshold, and by under- From a theoretical standpoint, if we can guarantee certain standing the properties of the approximate distance mea- properties of the inexpensive distance metric, we can show sure, we can have a guarantee in some cases.

7 That the original, accurate Clustering solution can still be recovered with the canopies approach. In other words, if The circles with solid outlines in Figure 1 show an example the inexpensive Clustering does not exclude the solution for of overlapping canopies that cover a data set. The method the expensive Clustering , then we will not lose any Clustering by which canopies such as these may be created is described accuracy. In practice, we have actually found small accuracy in the next subsection. increases due to the combined usage of two distance metrics. In the second stage, we execute some traditional cluster- Clustering based on canopies can be applied to many differ- ing algorithm, such as Greedy Agglomerative Clustering or ent underlying Clustering algorithms, including Greedy Ag- K-means using the accurate distance measure, but with the glomerative Clustering , K-means, and Expectation-Maxim- restriction that we do not calculate the distance between two ization.

8 Points that never appear in the same canopy, we assume their distance to be infinite. For example, if all items are This paper presents experimental results in which we apply trivially placed into a single canopy, then the second round the canopies method with Greedy Agglomerative Clustering of Clustering degenerates to traditional, unconstrained clus- to the problem of Clustering bibliographic citations from the tering with an expensive distance metric. If, however, the reference sections of computer science research papers. The canopies are not too large and do not overlap too much, Cora research paper search engine [11] has gathered over a then a large number of expensive distance measurements million such references referring to about a hundred thou- will be avoided, and the amount of computation required sand unique papers; each reference is a text segment exist- for Clustering will be greatly reduced.

9 Furthermore, if the ing in a vocabulary of about hundred thousand dimensions. constraints on the Clustering imposed by the canopies still in- Multiple citations to the same paper differ in many ways, clude the traditional Clustering solution among the possibil- particularly in the way author, editor and journal names are ities, then the canopies procedure may not lose any cluster- abbreviated, formatted and ordered. Our goal is to cluster ing accuracy, while still increasing computational efficiency these citations into sets that each refer to the same article. significantly. Measuring accuracy on a hand-clustered subset consisting of about 2000 references, we find that the canopies approach We can state more formally the conditions under which the speeds the Clustering by an order of magnitude while also canopies procedure will perfectly preserve the results of tra- providing a modest improvement in Clustering accuracy.

10 On ditional Clustering . If the underlying traditional clusterer is the full data set we expect the speedup to be five orders of K-means, Expectation-Maximization or Greedy Agglomer- magnitude. ative Clustering in which distance to a cluster is measured to the centroid of the cluster, then Clustering accuracy will 2. EFFICIENT Clustering be preserved exactly when: WITH CANOPIES. The key idea of the canopy algorithm is that one can greatly For every traditional cluster, there exists a canopy reduce the number of distance computations required for such that all elements of the cluster are in the Clustering by first cheaply partitioning the data into over- canopy. lapping subsets, and then only measuring distances among pairs of data points that belong to a common subset. If instead we perform Greedy Agglomerative Clustering clus- tering in which distance to a cluster is measure to the closest The canopies technique thus uses two different sources of point in the cluster, then Clustering accuracy will be pre- information to cluster items: a cheap and approximate sim- served exactly when: ilarity measure ( , for household address, the proportion of words in common between two address) and a more ex- pensive and accurate similarity measure ( , detailed field- For every cluster, there exists a set of canopies by-field string edit distance measured with tuned transfor- such that the elements of the cluster connect.)