Clustering for Data Reduction: A Divide and Conquer Approach
Nicholas Andrews, Edward A. Fox · VTechWorks (Virginia Tech) · 2007
We consider the problem of reducing a potentially very large dataset to a subset of representative prototypes. Rather than searching over the entire space of prototypes, we first roughly divide the data into balanced clusters using bisecting k-means and spectral cuts, and then find the prototypes for each cluster by affinity propagation. We apply our algorithm to text data, where we perform an order of magnitude faster than simply looking for prototypes on the entire dataset. Furthermore, our “divide and conquer ” approach actually performs more accurately on datasets which are well bisected, as the greedy decisions of affinity propagation are confined to classes of already similar items. 1 Introduction. We consider the problem of data reduction, whereby we want to reduce our original data to a smaller but representative subset. This is related to feature selection in dimensionality reduction tasks, where we are looking for an m < n, where m << n. A reduced dataset might have a direct interpretation. For instance, the objects in question might be sentences, and resulting prototypes would span only the most essential