Source-linked AI summary
Clustering Algorithms: A Comparative Approach
Mayra Z. Rodriguez, Cesar H. Comin, Dalcimar Casanova, Odemir M. Bruno, Diego R. Amancio, Francisco A. Rodrigues, Luciano da F. Costa
TL;DR
The paper addresses the lack of consensus about which clustering methods suit different datasets. It compares seven R implementations on tunable artificial datasets under default and varied parameter settings, finding that spectral clustering usually performs best by default while random parameter selection can improve inaccurate defaults.
Problem
There is no consensus on which clustering methods are most suitable for datasets with varying properties, making comprehensive comparisons important.
Method
The study compares seven clustering methods in R on 270 artificial datasets with tunable properties and evaluates default, single-parameter, and random all-parameter settings.
Results
Spectral clustering usually outperformed the other methods with default configurations, while random parameter selection improved performance when defaults were inaccurate.
Takeaways & Limitations
The comparison provides practical guidance for choosing clustering algorithms and tuning parameters, especially for researchers with limited data-mining experience.
Abstract
from arXiv · showhide
Many real-world systems can be studied in terms of pattern recognition tasks, so that proper use (and understanding) of machine learning methods in practical applications becomes essential. While a myriad of classification methods have been proposed, there is no consensus on which methods are more suitable for a given dataset. As a consequence, it is important to comprehensively compare methods in many possible scenarios. In this context, we performed a systematic comparison of 7 well-known clustering methods available in the R language. In order to account for the many possible variations of data, we considered artificial datasets with several tunable properties (number of classes, separation between classes, etc). In addition, we also evaluated the sensitivity of the clustering methods with regard to their parameters configuration. The results revealed that, when considering the default configurations of the adopted methods, the spectral approach usually outperformed the other clustering algorithms. We also found that the default configuration of the adopted implementations was not accurate. In these cases, a simple approach based on random selection of parameters values proved to be a good alternative to improve the performance. All in all, the reported approach provides subsidies guiding the choice of clustering algorithms.
I. INTRODUCTION
The paper addresses the difficulty of choosing and tuning clustering algorithms by systematically comparing methods across diverse artificial datasets and parameter settings.
- Clustering performance can vary substantially across applications because algorithms involve parameters and must handle high-dimensional, noisy, incomplete, or sampled data.
- The study generates artificial datasets with systematically varied classes, features, object counts, class separation, and feature correlations.Artificial data permits unlimited sampling and controlled changes to dataset properties.
- Performance is measured by comparing known object labels with algorithm-generated labels using four similarity indices.The indices are the Jaccard, Adjusted Rand, Fowlkes-Mallows, and Normalized mutual information indices.
- Parameter optimization can overfit a dataset or become computationally infeasible, which helps explain reliance on software defaults.The paper frames parameter-setting as a longstanding machine-learning problem.
- The comparison evaluates seven clustering methods implemented in popular R packages to support researchers with limited clustering experience.The study focuses on R because of its popularity in data mining and its established clustering packages.
- Algorithms are evaluated with default parameters, one-parameter changes, and simultaneous random variation of all parameters.The random sampling procedure is compared with default settings to investigate possible performance improvements.
III. CLUSTERING METHODS
The paper reviews several clustering families and their R implementations, emphasizing their operating assumptions, strengths, and limitations.
- Common clustering methods rely on related assumptions or mathematical concepts, so their comparative behavior depends on data structure and method design.
- Partitional methods: K-means assigns points to the nearest of k centroids, then repeatedly recalculates centroids and reassigns points.Figure 1 illustrates successive partitions, centroid movement, and the use of four seeds for a two-cluster dataset.
- Partitional methods: K-means requires the number of groups and a distance metric in advance, and is sensitive to seed selection and nonconvex or differently sized clusters.Its main limitation is the a priori setting of the number of clusters.
- Partitional methods: Clara selects medoids from multiple fixed samples, reducing whole-dataset exploration and improving efficiency for large datasets.A medoid is the object with minimal average dissimilarity to other objects in its cluster.
- Hierarchical methods: Hierarchical clustering is either agglomerative, merging individual clusters, or divisive, splitting a single initial cluster.
- Model-based methods: EM models classes as multivariate normal distributions and estimates their parameters by maximum likelihood, but results can depend on initialization and small clusters may be missed.The method is particularly suitable when the dataset is incomplete.
- Spectral methods: Spectral clustering builds an affinity matrix and partitions data using its eigenvalues and eigenvectors without imposing a prefixed cluster shape.Its main disadvantage is the computational cost of calculating eigenvectors.
IV. MATERIALS AND METHODS
The study generates artificial datasets with tunable class, feature, sample-size, covariance, correlation, and separation properties, then evaluates clustering quality against known partitions.
- Artificial dataset generation: The dataset generator creates samples with F features divided into C classes while controlling variance and feature-correlation distributions within each class.Each class receives its own covariance matrix, allowing feature pairs to have distinct correlations across classes.
- Experimental design: The mixing parameter α is tuned for each dataset so that no algorithm achieves either 0% or 100% accuracy.α is associated with the expected distances between classes.
- Artificial dataset generation: The methodology generates diverse configurations, including class-specific feature correlations and varying expected distances between classes.Figure 2 illustrates cases with different numbers of classes, objects per class, and α values.
- Experimental design: The experiments vary C={2, 10, 50}, F={2, 10, 50}, and Ne={5, 50, 100} objects per class across 270 generated datasets.Each dataset realization contains a constant number of instances per class, and 10 realizations are considered for each case.
- Evaluation metrics: Clustering quality is measured with the Jaccard, Adjusted Rand, Fowlkes-Mallows, and Normalized Mutual Information indexes.The measures compare algorithm-produced partitions with known class labels; perfect one-to-one label correspondence yields unity for all measures.
V. RESULTS AND DISCUSSION
The algorithms are evaluated under package defaults, one-at-a-time parameter changes, and simultaneous random parameter sampling to assess performance and parameter sensitivity.
- Evaluation protocol: The study first evaluates each clustering algorithm using the default parameters supplied by its R package.This represents applying a classifier without parameter adjustment.
- Evaluation protocol: A second methodology varies one algorithm parameter while keeping all others at their default values to quantify parameter influence.
- Evaluation protocol: A third methodology varies all algorithm parameters simultaneously through random sampling and compares the results with default-parameter performance.
A. Performance when using default parameters
Under default configurations, spectral clustering generally performs best, while performance depends on feature count, sample count, and the specified number of clusters.
- Effect of feature count: With 2 features, all algorithms display similar performance, whereas larger feature counts produce marked differences and spectral clustering performs best with 50 features.The four performance metrics show similar overall patterns; hierarchical clustering is worst with 50 features.
- Effect of feature count: Performance differences across algorithms are not statistically significant for 2 features, but they are significant for 10 features according to the Kruskal-Wallis analysis.For 2 features, the test reports p=0.07 and χ2=10.26; the supplied passage begins the 10-feature result with p=4.4 × 10^-6.
- Effect of sample count: Increasing the number of objects per class lowers accuracy for hierarchical, k-means, and clara methods, indicating reduced robustness under greater cluster overlap.The effect of Ne depends on the algorithm.
- Effect of expected cluster count: For DB10C10F, setting K below the actual 10 classes performs markedly worse than setting K above 10, so slight overestimation appears less harmful.The study suggests choosing K slightly larger than the expected number of classes.
- Overall default-parameter performance: The spectral algorithm tends to outperform the other algorithms by at least 10% across the evaluated datasets.The study concludes that spectral clustering is preferred when parameter-value optimization is not performed.
B. One-dimensional analysis
The one-dimensional analysis tests how clustering accuracy changes when a single parameter varies, while other parameters remain at defaults. Results show that some parameters substantially improve or reduce performance, but average sensitivity is small in most cases.
- DB2C2F and DB10C2F: 10.75% average improvement occurred for EM's modelName parameter on DB2C2F, while spectral's kpar produced a 7.36% average improvement.For other cases in the two-class, two-feature setting, only minor average performance gains were observed.
- DB2C2F and DB10C2F: −16.15% average accuracy resulted from varying the hierarchical algorithm's method parameter in the 10-class problem.The study identifies this as an inadequate parameter value; most other average performance changes were small.
- DB2C10F and DB10C10F: 18.8% average accuracy gain was obtained by varying EM's modelName parameter for the two-class, 10-feature problem.Hierarchical method variation produced an 8.76% average gain in the same setting.
- DB2C10F and DB10C10F: 13.63% average improvement was observed for EM's modelName parameter in the 10-class, 10-feature problem, while hierarchical method variation yielded 6.72%.The results describe similar behavior when the number of classes was set to 10.
- Parameter effects: Some parameters had minor effects or reduced performance, including spectral kernel and iter, k-means iter.max, subspace min.individuals and models, and clara metric and rngR.Varying subspace min.individuals and models caused average accuracy losses of about −20%, depending on the dataset.
- Multi-dimensional analysis: The multi-parameter procedure randomly samples each parameter within bounds identified from one-dimensional analysis, generating 500 parameter sets per algorithm.The complete parameter space is sampled because simultaneous variation is otherwise difficult due to the number of combinations.
- Multi-dimensional analysis: For DB2C2F, EM and hierarchical clustering achieved average gains of 22.1% and 30.6%, respectively, under random parameter selection.EM was the only algorithm with a p-value larger than 50%; moderate improvements were obtained for hcmodel, k-means, and spectral.
- Multi-dimensional analysis: For DB10C2F, EM and k-means had p-values of 76.5% and 77.7%, respectively, but average improvements were relatively low for all algorithms.The p-value measures the percentage of random configurations outperforming the default configuration.
VI. CONCLUSIONS
The study compares seven clustering methods across heterogeneous artificial datasets and parameter settings. Spectral clustering led with defaults, while parameter variation often improved performance, especially in higher-dimensional settings.
- Study design: Seven popular clustering methods were evaluated on 270 artificial datasets with precisely defined properties, using default, single-parameter, and random-parameter configurations.The datasets varied properties such as class distances and feature correlations.
- Default parameters: With 2 features, default-method performance differences were not significant, whereas 50 features produced a significant difference (p = 1.4 × 10−6; χ2 = 37.48).For 2 features, the Kruskal-Wallis test yielded p = 0.07 and χ2 = 10.26.
- Default parameters: The Spectral method achieved the best default performance with an Adjusted Rand Index (ARI) of 65.80%, while hierarchical clustering achieved 24.81%.The hc routine using parametric Gaussian mixture models achieved 43.53% ARI.
- Parameter variation: For 10-feature datasets, most methods could be improved by changing selected parameters, whereas only hierarchical and EM methods varied significantly for 2-feature datasets.The reported sensitivity therefore depended on dataset dimensionality.
- Parameter variation: For two classes and ten features, EM, hcmodel, subspace, and hierarchical algorithms showed significant performance gains under multidimensional parameter analysis.For ten classes and ten features, improvements were significantly lower for almost all algorithms except hierarchical clustering.
- Overall comparison: For ten-feature datasets, subspace clustering generally provided the best tuned performance, while EM could achieve similar results with parameter tuning.For two-feature datasets, all algorithms showed similar performance.
S1. DESCRIPTION OF THE CLUSTERING ALGORITHMS’ PARAMETERS
The parameter descriptions specify the controls used for clustering methods and their package defaults. These include iteration limits, sampling, distance metrics, cluster counts, and implementation choices.
- k-means: The k-means configuration includes maximum iterations, random starts, implementation algorithm, and the number of cluster centers.The defaults are 10 iterations, 1 random start, Hartigan-Wong, and the dataset’s number of clusters.
- Sampling-based clustering: The sampling-based algorithm uses a dissimilarity metric, sample count, sample size, random-number-generator choice, and cluster count.Its defaults include Euclidean distance, 5 samples, false for rngR, and the dataset’s number of clusters.
Hierarchical clustering
The hierarchical-related configurations specify distance metrics, linkage choices, dissimilarity parameters, and model-based Gaussian-mixture settings.
- Hierarchical method: The hierarchical method exposes a distance metric, clustering method, and parameter for dissimilarity calculation.The defaults are Euclidean distance, average clustering, and par.method = 0.
- Expectation maximization: The EM method uses expectation and maximization routines for parametric Gaussian mixture models.The mstep uses conditional component probabilities and a model name, while the estep uses the model name and mixture parameters.
- Model-based hierarchical clustering: The model-based hierarchical routine hc uses a model name, data or transformation choice, and number of clusters.The defaults are modelName = “VII”, use = “VARS”, and the dataset’s number of clusters.
Spectral algorithm
The spectral routine specc is configured through cluster count, kernel selection, kernel parameters, sampling for sigma estimation, and iteration limits. The supplied parameter descriptions also cover related high-dimensional clustering controls.
- Spectral algorithm: The spectral routine specc includes the number of centers and the kernel used to compute the affinity matrix.The default kernel is rbfdot, described as a Gaussian radial-basis kernel.
- Spectral algorithm: The spectral configuration allows automatic or user-defined kernel parameters, a data proportion for sigma estimation, and a maximum iteration count.The defaults are automatic kpar, Nb/6 for nystrom.sample, and 200 iterations.
- Subspace clustering: The subspace clustering routine hddc selects among model structures and cluster counts using the maximum BIC value.Its model option includes 14 models, and the default selected cluster count lies in the interval (1, 10].
- Subspace clustering: The hddc configuration also specifies the clustering algorithm and initialization procedure.The defaults are EM for algo and kmeans for init; alternatives include CEM, SEM, random, param, and mini-em.
S2. CLUSTERING PERFORMANCE OBTAINED FOR RANDOM SELECTION OF PARAMETERS
This section presents ARI distributions produced by random parameter selection for two datasets across six clustering methods. The figures include default-parameter performance as a reference.
- Random parameter selection is evaluated on datasets DB10C10F and DB2C10F using ARI distributions.Figures S2.1 and S2.2 show histograms for the two datasets.
- The distributions cover hcmodel, clara, hierarchical, spectral, Subspace, and EM methods.
- Red dashed lines mark performance obtained with each implementation’s default parameters.