Abstract
We propose an algorithm, HPREF (Hierarchical Partitioning by Repeated Features), that produces a hierarchical partition of a set of clusterings of a fixed dataset, such as sets of clusterings produced by running a clustering algorithm with a range of parameters. This gives geometric structure to such sets of clustering, and can be used to visualize the set of results one obtains by running a clustering algorithm with a range of parameters.
Introduction
Clustering is a fundamental unsupervised learning task, yet it remains highly sensitive to hyperparameter selection. Algorithms like DBSCAN require tuning $\epsilon$ and $minPts$, while $k$-means depends on the number of clusters $k$ and initial centroid placement. Consequently, practitioners often generate a large ensemble of potential clusterings rather than a single definitive result. Navigating this "space of clusterings" is difficult; standard metrics like the Rand index compare pairs but fail to provide a global overview of the parameter space's structure. We introduce HPREF (Hierarchical Partitioning by Repeated Features) to address this by providing a scalable, geometric visualization of clustering sets.
The HPREF Algorithm
HPREF organizes a set of clusterings $S$ into a hierarchical partition. The core idea is to treat pairs of data points as "features" that characterize the clusterings.
- Binary Encoding: Each clustering is represented as a high-dimensional binary vector. For every pair of points $(x, y)$ in the dataset, the vector records a
0if the points are clustered together and a1if they are not. - Feature Sampling: Since considering all possible pairs is computationally expensive ($O(N^2)$), the algorithm samples a subset of pairs. These pairs act as "voters" to distinguish between different clustering structures.
- Hierarchical Partitioning: The algorithm identifies the "most repeated" feature—a point pair that behaves consistently across the largest subset of clusterings. This feature is used to split the set $S$ into two. This process continues recursively until a desired number of leaves is reached.
The algorithm uses a scoring function $f(S) = c + m$, where $c$ is the number of unique partitioning features and $m$ is the frequency of the most common one. This heuristic prioritizes splits that are both heterogeneous and supported by a strong consensus feature.
Experimental Evaluation
We evaluated HPREF on classic benchmarks to demonstrate its utility in parameter selection and algorithm comparison.
Parameter Identification
Using Fisher’s Iris dataset with DBSCAN, HPREF successfully isolated a "red class" of solutions in the dendrogram that corresponded to the highest Adjusted Rand Index. This demonstrates that HPREF can automatically identify "stable" regions in parameter space where the clustering accurately reflects the underlying ground truth.
Algorithm Stability and Efficiency
On the large-scale KDD Cup dataset (4.9M points), HPREF was used to compare $k$-means and $k$-means++ initializations. The algorithm clearly separated the two methods, showing that $k$-means++ produces a more stable and lower-error group of clusterings. Despite the dataset's size, HPREF performed the partitioning in minutes, whereas generating the clusterings themselves took hours. This efficiency stems from the algorithm's robustness to sampling; a small subset of point pairs is often sufficient to capture the global structure.
Conclusion
HPREF provides a robust and scalable framework for exploring the space of clusterings. By leveraging repeated features, it identifies the large-scale geometric structures that persist across different parameter settings. This allows researchers to navigate complex parameter spaces and identify high-quality, stable clustering results efficiently.
Summary updated