BETULA: Fast clustering of large data with improved BIRCH CF-Trees
Andreas Lang, Erich Schubert
Abstract
BIRCH clustering is a widely known approach for clustering that has influenced much subsequent research and commercial products. The key contribution of BIRCH is the Clustering Feature tree (CF-Tree), which is a compressed representation of the input data. As new data arrives, the tree is eventually rebuilt to increase the compression. Afterward, the leaves of the tree are used for clustering. Because of the data compression, this method is very scalable. The idea has been adopted, for example, for k-means, data stream, and density-based clustering. Clustering features used by BIRCH are simple summary statistics that can easily be updated with new data: the number of points, the linear sums, and the sum of squared values. Unfortunately, how the sum of squares is then used in BIRCH is prone to catastrophic cancellation. We introduce a replacement cluster feature that does not have this numeric problem, that is not much more expensive to maintain, and which makes many computations simpler and, hence, more efficient. These cluster features can also easily be used in other work derived from BIRCH such as algorithms for streaming data. In the experiments, we demonstrate the numerical problem and compare the performance of the original algorithm compared to the improved cluster features. We furthermore explain how to improve clustering with different algorithms such as hierarchical clustering, k-means, k-means++ and Gaussian mixture modeling by using the variance information stored in the cluster features to obtain high-quality result approximations in a substantially reduced runtime (up to 500× faster in our experiments).