On Scaling Up Balanced Clustering Algorithms
Arindam Banerjee, Joydeep Ghosh · 2002
1 Introduction The past few years have witnessed a growing interest in clustering algorithms that are suitable for data-mining problems [15, 14, 9]. Clustering algorithms for data-mining problems must be extremely scalable. In addition, several data mining applications demand that the clusters obtained be balanced, i.e., be of approximately the same size or importance. There are several notable approaches that address the scalability issue. Some approaches try to build the clusters dynamically by maintaining sufficient statistics and other summarized information in main memory while minimizing the number of database scans involved. For example, Bradley et al. [4, 5] propose out-of-core methods that scan the database once to form a summarized model (for instance, the size, sum and sum-squared values of potential cluster, and well as a small number of unallocated data-points) in main memory. Subsequent refinement based on this summarized information is then restricted to main memory operations without resorting to further disk scans. Another method with a similar flavor [24] compresses the data objects into many small subclusters using modified index trees and performs clustering with these subclusters. A different approach is to subsample the original data before applying the actual clustering algorithms [6, 12]. Ways of effectively sampling large datasets have also been proposed [20]. A recent work [8] suggests using less number of points in each step of an iterative relocation optimization algorithm like k-means as long as the model produced does not differ significantly from the one that would be obtained with full data.