Visualization tools for parameter selection in cluster analysis

Alexander Rolle, Luis Scoccola

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.

The Problem of Parameter Selection

Clustering is a fundamental tool in data science, yet it is plagued by the "parameter selection" problem. Popular algorithms like DBSCAN or k-means require users to specify sensitive inputs, such as the distance scale $\epsilon$ or the number of clusters $k$. As shown in Figure 1, even minor adjustments to these parameters can yield drastically different results, making it difficult for researchers to determine which output represents the true underlying structure of the data rather than mere noise.

Clustering sensitivity to parameters (eps, k)

Typically, researchers handle this by running an algorithm multiple times across a parameter grid. However, this produces a massive collection of clusterings that is difficult to interpret globally. While metrics like the Rand index allow for pairwise comparisons, they do not provide a visual map of the entire parameter space.

The HPREF Algorithm

To address this, we introduce HPREF (Hierarchical Partitioning by Repeated Features). The core innovation is treating pairs of data points as "voters" to identify stable features across the set of clusterings.

  1. Binary Encoding: Each clustering in a set $S$ is represented as a binary vector based on whether pairs of points $(x, y)$ are grouped together (0) or separated (1).
  2. Repeated Features: If many distinct pairs of points suggest the same split across the set of clusterings, that split is identified as a "large-scale feature."
  3. Top-Down Partitioning: HPREF starts with the full set of clusterings and iteratively splits them using the most supported features. This process is guided by a scoring function $f(S) = c + m$, where $m$ is the multiplicity of the most repeated split and $c$ is the number of unique ways the data points partition the clusterings.
The iterative partitioning of the parameter space by HPREF

As illustrated in Figure 2, this iterative approach progressively maps out stable regions in the parameter space, allowing users to see which ranges of $\epsilon$ and $k$ produce consistent results.

Empirical Validation

We evaluated HPREF on two distinct datasets to test its accuracy and scalability:

  • Fisher’s Iris Dataset: Using DBSCAN, HPREF successfully isolated a "red class" branch in the resulting dendrogram. This branch corresponded to the highest Adjusted Rand Index (mean ~0.7), effectively identifying the parameters that best recovered the known ground truth of the three iris species.
  • KDD Cup 1999 Dataset: To test scalability, we applied HPREF to nearly 4.9 million points. The algorithm processed 40 clusterings in just 12 minutes by sampling 20,000 point pairs. Notably, HPREF perfectly separated standard k-means results from k-means++ results, visually demonstrating that k-means++ produces more tightly grouped, stable clusters.

Key Insights and Stability

A central finding is that stability serves as a proxy for quality. High-quality clustering results tend to cluster into distinct, persistent branches in the HPREF dendrogram. Furthermore, the success of pairwise sampling proves that the global structure of a clustering space can be captured efficiently without comparing every possible pair of points ($N^2$), making the tool viable for massive datasets.

Conclusion and Future Work

HPREF provides a much-needed geometric structure to the space of clustering results. While it significantly simplifies parameter selection, the final interpretation still requires a human-in-the-loop to evaluate the resulting dendrogram. Future research will explore alternative scoring heuristics and the algorithm's sensitivity to extremely high-noise environments where stable clusters may not exist.

Summary updated

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.
BibTeX
@misc{rolle2019visualization,
  author = {Alexander Rolle and Luis Scoccola},
  title = {{Visualization tools for parameter selection in cluster analysis}},
  year = {2019},
  eprint = {1902.01436},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.01436},
}

Loading related content...

Figure