Data Aggregation for Hierarchical Clustering
This addresses the challenge of enabling exploratory data analysis on very large datasets for users in embedded or resource-constrained environments, though it is incremental as it builds on existing BIRCH aggregation methods.
The paper tackles the problem of Hierarchical Agglomerative Clustering (HAC) requiring quadratic memory and cubic runtime, which is problematic for resource-constrained systems, by using data aggregation with BETULA to make HAC viable with only small losses in clustering quality.
Hierarchical Agglomerative Clustering (HAC) is likely the earliest and most flexible clustering method, because it can be used with many distances, similarities, and various linkage strategies. It is often used when the number of clusters the data set forms is unknown and some sort of hierarchy in the data is plausible. Most algorithms for HAC operate on a full distance matrix, and therefore require quadratic memory. The standard algorithm also has cubic runtime to produce a full hierarchy. Both memory and runtime are especially problematic in the context of embedded or otherwise very resource-constrained systems. In this section, we present how data aggregation with BETULA, a numerically stable version of the well known BIRCH data aggregation algorithm, can be used to make HAC viable on systems with constrained resources with only small losses on clustering quality, and hence allow exploratory data analysis of very large data sets.