Efficient clustering of high-dimensional data sets with application to reference matching

TLDR

Clustering large datasets is computationally expensive, and while efficient techniques exist for limited clusters, low dimensionality, or few points, little work addresses datasets that are large in all three dimensions. The authors introduce a new technique for clustering large, high‑dimensional datasets. Their method partitions data into overlapping canopy subsets using a cheap approximate distance, then performs exact‑distance clustering only within shared canopies, allowing integration with algorithms such as K‑means, agglomerative clustering, and EM. Canopies render previously infeasible large‑scale clustering practical, achieving identical accuracy while reducing computation time by more than tenfold and decreasing error by 25% compared to a prior algorithm.

Abstract

important problems involve clustering large datasets. Although naive implementations of clustering are computa- tionally expensive, there are established ecient techniques for clustering when the dataset has either (1) a limited num- ber of clusters, (2) a low feature dimensionality, or (3) a small number of data points. However, there has been much less work on methods of eciently clustering datasets that are large in all three ways at once|for example, having millions of data points that exist in many thousands of di- mensions representing many thousands of clusters. We present a new technique for clustering these large, high- dimensional datasets. The key idea involves using a cheap, approximate distance measure to eciently divide the data into overlapping subsets we call canopies .T hen cluster- ing is performed by measuring exact distances only between points that occur in a common canopy. Using canopies, large clustering problems that were formerly impossible become practical. Under reasonable assumptions about the cheap distance metric, this reduction in computational cost comes without any loss in clustering accuracy. Canopies can be applied to many domains and used with a variety of cluster- ing approaches, including Greedy Agglomerative Clustering, K-means and Expectation-Maximization. We present ex- perimental results on grouping bibliographic citations from the reference sections of research papers. Here the canopy approach reduces computation time over a traditional clus- tering approach by more than an order of magnitude and decreases error in comparison to a previously used algorithm by 25%.