Source-linked AI summary
To Cluster, or Not to Cluster: An Analysis of Clusterability Methods
A. Adolfsson, M. Ackerman, N. C. Brownstein
TL;DR
Clustering is appropriate for uncovering inherent structure only when that structure is present, but clusterability measures vary and may disagree. This paper formalizes requirements, compares measures extensively on simulated and real data, and derives application-oriented selection guidelines. Its results show that method performance depends on dimension, outliers, and cluster shape, motivating different choices for different scenarios.
Problem
Clusterability lacks a settled formal definition, and existing measures can disagree, making it difficult to choose a suitable measure for a given application.
Method
The paper formalizes clusterability requirements and empirically compares measures across extensive simulations and real data, organizing guidance by application needs.
Results
Method performance differs with dimension, outlier treatment, and cluster shape or separability; distance-based methods generally perform well, while PCA is useful for two or three clusters but weak for nonlinear data.
Takeaways & Limitations
Users should select among effective measures according to whether small clusters, chaining structure, or high dimensionality matter in the target clustering.
Takeaways & Limitations
The study focuses on Euclidean distance and cautions that PCA may be unsuitable for highly nonlinear data; other metrics and reductions remain future work.
Abstract
from arXiv · showhide
Clustering is an essential data mining tool that aims to discover inherent cluster structure in data. For most applications, applying clustering is only appropriate when cluster structure is present. As such, the study of clusterability, which evaluates whether data possesses such structure, is an integral part of cluster analysis. However, methods for evaluating clusterability vary radically, making it challenging to select a suitable measure. In this paper, we perform an extensive comparison of measures of clusterability and provide guidelines that clustering users can reference to select suitable measures for their applications.
1. Introduction
Clusterability determines whether clustering should be applied when the goal is to uncover inherent groups. Because legitimate judgments depend on application needs and measures disagree, users need guidance for choosing among them.
- Motivation: Clustering with realistic aims is appropriate only when inherent cluster structure is present; otherwise, partitions can be arbitrary and misleading.A single Gaussian may be artificially subdivided by algorithms such as k-means with k ≥2.
- Clustering pipeline: Clusterability analysis is inserted after preprocessing to decide whether data should be clustered or reprocessed before selecting an algorithm.The pipeline uses clusterability as a decision point before algorithm selection or development.
- Measure selection: Clusterability notions vary substantially and can produce different conclusions, creating a dilemma over which measure suits the data.The paper frames this as a second user’s dilemma alongside clustering-algorithm selection.
- Application dependence: Application needs determine whether ambiguous patterns, such as outliers, count as meaningful clusters.Small clusters may be accepted in one application but treated as irrelevant in another.
- Paper contribution: The paper addresses this dilemma through extensive empirical statistical analysis intended to identify effective notions and differences among them.Simulations and real-data applications support decisions about suitable clusterability techniques.
2. Measures of Clusterability
The paper formalizes clusterability measures and uses practical requirements to focus its empirical comparison. It then evaluates candidate methods across simulated and real data to derive selection guidelines.
- Formalization: A clusterability measure maps a data set to a value quantifying its degree of inherent cluster structure.Outputs may be real values, binary indicators, or probability measures.
- Requirements: The framework uses efficiency, algorithm independence, and effectiveness as requirements for selecting measures.These requirements distinguish practical, algorithm-agnostic, and accurate notions of clusterability.
- Requirements: Algorithm independence avoids restricting clusterability evaluation to structure recoverable by one particular clustering algorithm.Different algorithms identify different types of cluster structure.
- Empirical analysis: The study compares selected measures on many real and simulated data sets, using unambiguous cases and ambiguous cases to assess effectiveness and suitability.Differences in behavior across scenarios support practitioner guidelines.
2.2. Effective Approaches to Clusterability Evaluation
Effective clusterability approaches commonly reduce data to one dimension and test the resulting distribution for multimodality. Pairwise distances and principal components provide complementary summaries, but their reliability depends on dimensionality and data shape.
- PCA: PCA projects data onto dimensions explaining original variance, and its first component explains the most variation.PCA is less prone than some reductions to high-dimensionality problems but is poorly suited to nonlinear structures.
- Distance summaries: Distance histograms can reveal within-cluster and between-cluster separation through groups of small and large pairwise distances.Homogeneous data should not show the same separation.
- Multimodality tests: Multimodality tests assess whether reduced data has more than one mode, using rejection of unimodality as evidence of multiple clusters.Large p-values support unimodality, whereas small p-values question that assumption.
- Dimension reduction: Pairwise-distance and first-principal-component distributions are unimodal for single-cluster data and multimodal for data generated from multiple clusters.Figure 3 illustrates this pattern across one, two, and three Gaussian clusters.
- Limitations: Applying multimodality tests directly to multidimensional data is unpredictable because their asymptotic behavior is unknown in higher dimensions.The paper therefore motivates reducing data to one dimension before testing.
2.3. Clusterability via Multimodality
The paper evaluates multimodality-based clusterability methods on reduced representations and distances. These methods infer cluster structure when the reduced data provides evidence against unimodality.
- Operational interpretation: Failure to reject unimodality in reduced data is treated as insufficient evidence of cluster structure for clustering.The paper’s operational rule is not to cluster when reduced data lacks clear multimodal evidence.
- Distance-based methods: Dip-dist applies the Dip test to sorted pairwise Euclidean distances, using multiple modes in their distribution to suggest multiple clusters.The method relies on distance lengths rather than their arrangement in the original data.
- PCA-based methods: PCA-based methods extract the first principal component and apply a multimodality test to that one-dimensional reduction.The first principal component is obtained through PCA, while Silverman’s test evaluates its modality.
- Classical methods: Classic Silverman and Classic Dip apply multimodality tests directly to the original multidimensional data for comparison.The paper includes these classical variants despite known problems with multimodality testing in higher dimensions.
2.4. Clusterability via Spatial Randomness
Spatial-randomness clusterability methods compare nearest-neighbor distances for sampled data points and pseudo points to assess whether the data are clustered.
- Hopkins compares nearest-neighbor distances from sampled data points with distances from pseudo points whose features are randomly selected from the data.
- Under the unclusterable-data null hypothesis, the Hopkins statistic follows a beta distribution with both parameters equal to the sample size n.
- The statistic is compared with the Beta quantile qα(n, n), where P(H < qα(n, n)) is 100α% under the no-cluster hypothesis.
- Sampling too few points may produce unrepresentative distances, whereas sampling too many can invalidate the Beta-distribution assumptions.
2.5. New Clusterability Methods
The paper proposes new clusterability approaches that apply valid multimodality tests to reduced data representations, including corrected Silverman and dip-test variants.
- Both the dip and Silverman tests are applied to each reduced version of the data as proposed clusterability methods.
- A proposed distance-based method uses Silverman’s test, with the necessary correction, on pairwise Euclidean distances instead of the dip test.
- A proposed principal-component method uses the dip test to assess whether the first principal component is multimodal instead of Silverman’s test.
- The dip test classifies the modality of the principal curve.
2.6. Other Clusterability Methods
The study omits clusterability notions that are ineffective, computationally impractical, overly sensitive to noise or outliers, algorithm-specific, or subjective.
- Worst pair ratio is excluded because it labels some clearly clusterable datasets as unclusterable, including closely positioned Gaussian clusters.
- Some theoretical measures are omitted because they are NP-hard to compute or too strict for practical use due to sensitivity to noise and outliers.
- Measures based on specific algorithms or objective functions are excluded because the analysis seeks any cluster structure, not only structure found by one technique.
- Approaches relying on subjective judgment rather than a quantifiable measure are also omitted.
3. Simulations
The simulations evaluate whether clusterability measures behave correctly on clear cases and identify which methods are appropriate under noise, outliers, high dimensions, and chaining structure.
- Simulation design: 31,000 simulations across 31 data-set types tested clusterability measures on Gaussian, t-distributed, noisy, outlier-containing, and structurally varied data.Each type used the same parameters for 1,000 repetitions.
- Evaluation criteria: Type I error measures false positives on unclusterable data, whereas statistical power measures correct detection of cluster structure on clusterable data.Type I error substantially above 5% indicates excessive false positives.
- Unclusterable data: Principal curve methods were invalid on single-Gaussian data, while other methods generally had low false-positive rates; some methods were overly conservative with type I error below 1%.The principal-curve methods classified single-cluster data as clusterable much more often than 5%.
- Outliers and small clusters: Outlier results depended on the intended interpretation: Hopkins and Silverman methods often treated outliers as separate clusters, while dip-based methods were more robust.Dip-based methods classified some outlier-containing t-distribution data as clusterable less than 10% of the time, whereas Hopkins and Silverman-based methods ranged from 44% to 85%.
- Clusterable data: Well-separated clusters yielded nearly 100% power, but overlapping high-dimensional clusters exposed weaknesses in classical methods and favored PCA- or distance-based Dip and Silverman tests.For partially overlapping 50-dimensional clusters, Hopkins power dropped to 32% and classic methods fell below 5%, while PCA- or distance-based tests retained near-perfect power.
- Chaining structure: Dip-dist was the most effective method for chaining data, maintaining high power while controlling false positives; PCA methods struggled with nonlinear circles and parallel lines.Distance-based methods reached 100% power for distinct circles, whereas PCA-based methods had less than 6% power for parallel lines.
4. Results on Non-Simulated Data
On non-simulated data, methods agreed on clearly structured datasets but differed on ambiguous datasets, outliers, and dimension-reduction behavior. Distance- and PCA-based methods generally gave the most reasonable results, while principal-curve and some classic methods produced problematic conclusions.
- Principal-curve methods showed excessive false positives and failed to converge on a famous highly linear dataset.
- All tests identified the known cluster structure in the iris and faithful datasets.
- Hopkins and Silverman-based methods detected small clusters, whereas Dip-based methods were more robust to outliers.For rivers, Hopkins and Silverman methods indicated clusterability while Dip-based methods did not.
- Most methods judged datasets without known structure unclusterable, but questionable methods produced frequent positive classifications.Classic Silverman and principal-curve methods declared USArrests and USJudgeRatings clusterable nearly 70% of the time; trees and cars were classified as clusterable 18% and 19% of the time, respectively.
- Distance dip, distance Silverman, PCA dip, and PCA Silverman produced the most reasonable overall results, highlighting the value of dimensionality reduction.
5. Runtime
Runtime varied substantially across clusterability methods, with computational complexity depending on sample size and dimension. Dip-based methods were generally fastest, while Silverman-based distance methods were especially expensive.
- The runtime evaluation reported average execution times for simulations and non-simulated datasets, including separate chaining-structure simulations.
- PCA dip has asymptotic running time O(nd^2 + d^3), while PCA Silverman has complexity O(n^2 + d^2n + d^3).
- Silverman-based methods were slower than corresponding Dip-based methods, with Dip-dist much faster than Silv-dist and PCA Dip much faster than PCA Silv.Dip-based methods completed in less than one hundredth of a second in the reported comparisons.
- Distance Silverman was the slowest method in simulations, requiring nearly 1 to over 8.5 seconds and running one to three orders of magnitude slower than other methods.Its cost reflects processing the quadratic number of pairwise distances before applying Silverman’s test.
- On non-simulated data, PCA dip and distance dip each ran in one to three thousandths of a second, while PCA Silverman took about seven-tenths to eight-tenths of a second.
6. Discussion
The discussion shows that clusterability methods differ by dimension, outlier treatment, and cluster geometry, so method selection must reflect application needs. Distance-based and selected PCA methods were generally effective, whereas principal-curve methods were problematic.
- Distance-based methods performed well in most scenarios, while PCA methods handled two or three clusters and avoided spurious clusters for single-cluster data.PCA had lower power than distance-based methods in low dimensions and performed poorly on non-linear data.
- Principal-curve methods had excessive false positives, and principal-curve reduction consistently inflated Type I error rates.
- Silverman and Hopkins methods treated outliers as clusters, whereas Dip-based methods were robust to outliers.
- Dip-dist was the only method that consistently performed well on chaining data, identifying both clusterable and unclusterable structures.
- PCA dip, PCA Silverman, and Dip-dist performed well and were reasonably efficient through 50 dimensions, suggesting suitability for high-dimensional data.
- For very high-dimensional data, especially when dimensions greatly exceed elements, additional investigation is needed.The paper leaves alternative reductions such as Sparse PCA for future work.
- The paper’s recommendations assume Euclidean distance and caution that highly non-linear data may require a different dimension-reduction choice.
7. Conclusions
The conclusions advocate integrating clusterability analysis before clustering because clustering algorithms can produce partitions even when no meaningful structure exists. The paper provides practical selection guidance based on outliers, chaining structure, and dimensionality.
- Clusterability analysis should precede clustering to identify whether partitioning is appropriate and avoid invalid conclusions from unclusterable data.
- The practical selection table distinguishes methods by whether small clusters or outliers matter, whether chaining structure is present, and whether data is high dimensional.
- PCA dip and PCA Silverman support small-cluster and high-dimensional settings, while Dip-dist supports outlier-robust and chaining-data settings.
- The authors describe ongoing implementation work intended to facilitate user-friendly applications of the methods.