Source-linked AI summary
Recovering the number of clusters in data sets with noise features using feature rescaling factors
Renato Cordeiro de Amorim, Christian Hennig
TL;DR
The paper addresses estimating the number of spherical Gaussian clusters when irrelevant features impair cluster validation. It introduces feature re-scaling methods based on data structure and feature relevance, and reports improved recovery of the true cluster count across several validity indexes, with index-specific exceptions.
Problem
Estimating the true number of clusters is difficult because noise features substantially affect validation indexes and cluster lacks a generally accepted definition.
Method
The paper introduces three implicit or explicit feature re-scaling methods based on feature weights from intelligent Minkowski Weighted K-Means.
Results
85.5% was the best result with 50% extra noise features, achieved by iMWK-Means with explicit re-scaling followed by K-Means using Dunn’s index and the Minkowski distance.
Takeaways & Limitations
Feature re-scaling increased the chances that cluster validity indexes estimated the true number of clusters, especially for the evaluated noisy data sets.
Takeaways & Limitations
The findings target approximately spherical, compact Gaussian clusters with non-informative features, and Hartigan’s original threshold systematically overestimated K in these experiments.
Abstract
from arXiv · showhide
In this paper we introduce three methods for re-scaling data sets aiming at improving the likelihood of clustering validity indexes to return the true number of spherical Gaussian clusters with additional noise features. Our method obtains feature re-scaling factors taking into account the structure of a given data set and the intuitive idea that different features may have different degrees of relevance at different clusters. We experiment with the Silhouette (using squared Euclidean, Manhattan, and the p$^{th}$ power of the Minkowski distance), Dunn's, Calinski-Harabasz and Hartigan indexes on data sets with spherical Gaussian clusters with and without noise features. We conclude that our methods indeed increase the chances of estimating the true number of clusters in a data set.
1. Introduction
The paper addresses estimating the true number of clusters when cluster definitions are ambiguous and noise features impair validation indexes. It proposes three feature re-scaling methods to improve validity indexes’ likelihood of recovering the true K.
- Motivation: Estimating the true number of clusters lacks unified standards because “cluster” has no generally accepted definition.The paper therefore adopts a working K-Means-oriented definition rather than a general definition of clustering.
- Scope: The study targets approximately spherical, compact Gaussian clusters with similar within-cluster variation and additional non-informative features.The methods may also handle more general shapes when re-scaling makes them approximately spherical.
- Contribution: The paper considers both recovering the true K and finding the best clustering, which need not produce the same solution.A clustering with the best misclassification or adjusted Rand score may use a different K from the true number.
- Motivation: 10% noise features can already considerably impair cluster validation indexes, alongside cluster overlap.The experiments simulate irrelevant features using uniformly random values.
- Contribution: The paper introduces three feature re-scaling methods intended to make cluster validity indexes more likely to return the true number of clusters.The methods are evaluated with K-Means and by comparing indexes before and after re-scaling.
2. Background and related work
The background reviews K-Means, cluster validity indexes, and intelligent initialization. It also describes the distance measures and index-specific assumptions relevant to evaluating unknown cluster counts.
- K-Means: K-Means partitions data around K centroids by iteratively assigning entities to their closest centroid and updating cluster centres until assignments stabilize.Its criterion minimizes within-cluster distance, with lower values indicating better clustering.
- Distance measures: The study applies squared Euclidean, Manhattan, and pth-power Minkowski distances because suitable Minkowski powers can work well with noise features.The Silhouette and Dunn indexes support general distance measures, whereas Calinski-Harabasz and Hartigan use Euclidean within-cluster sums of squares.
- K-Means: K-Means treats features equally, depends strongly on initial centroids, does not guarantee a global optimum, and requires K beforehand.These weaknesses motivate feature weighting and methods for estimating K.
- Cluster validity indexes: The Silhouette compares within-cluster cohesion with separation, while Dunn’s index compares minimum inter-cluster distance with maximum cluster diameter.Silhouette values range from -1 to 1, and Dunn’s index is sensitive to noise-feature information.
- Cluster validity indexes: Calinski-Harabasz uses a between-cluster to within-cluster sum-of-squares ratio, and Hartigan evaluates changes in the Euclidean within-cluster sum of squares as K increases.The experiments use Hartigan’s original threshold rule, with a fallback based on the smallest successive difference.
- Initialization: Intelligent K-Means extracts anomalous patterns sequentially to provide initial centroids, while its estimated K is used here only to narrow the search domain.The original method can drastically overestimate the number of clusters, so it is not treated as the recommended estimator.
3. K-Means with feature weighting and Minkowski distance
This section extends K-Means with feature weighting and Minkowski distances, using data structure to rescale features according to cluster-specific relevance. It also describes iterative optimization, range standardization, and two explicit-rescaling variants for cluster-validity indexes.
- Feature weighting: MWK-Means extends K-Means to handle irrelevant features by weighting features according to their within-cluster dispersion.Lower dispersion receives higher weight, while strongly varying features are weighted down; weights for each cluster sum to one.
- Minkowski distance: The weighted Minkowski distance generalizes Manhattan, Euclidean, and Chebyshev metrics while allowing weights to act as feature-scaling factors.The pth-power form is used, avoiding the root, analogously to squared Euclidean distance in standard K-Means.
- Optimization: MWK-Means alternates assignments, Minkowski-centre updates, and feature-weight updates until the partition stabilizes.Minkowski centres are medians for p = 1, means for p = 2, and are obtained by convex optimization for other p ≥ 1.
- Optimization: MWK-Means converges in a finite number of iterations because each iteration decreases its criterion and only finitely many partitions exist.The algorithm remains nondeterministic because its outcome depends heavily on the initial centroids.
- Feature re-scaling: Range standardization makes feature scales comparable, but the proposed rescaling instead aims to reflect overall and cluster-specific feature relevance.Applying different rescaling at different clusters may affect distances between clusters, creating a methodological concern.
- Explicit rescaling methods: Two explicit-rescaling methods evaluate validity indexes on implicitly rescaled data, either retaining iMWK-Means clustering or following it with fully iterated K-Means.The latter treats iMWK-Means primarily as a rescaling technique and then applies K-Means to the rescaled data.
4. Simulations
Across simulations, feature re-scaling generally improved cluster-number estimation under noise, while effects on clustering quality depended on the index and final K-Means step. The strongest settings varied by metric, with p values commonly near 1.4–2 and sometimes higher.
- No noise features: At p = 2, iMWK-Means achieved the highest adjusted Rand index for five of seven validity indexes and the overall best Silhouette result.At p = 2, Euclidean and Minkowski Silhouette distances are equivalent.
- No noise features: 91% (Silhouette, Euclidean) and 88.5% (Silhouette, Manhattan) were the best overall percentages for estimating the true number of clusters at p = 2.Dunn’s improved by 9% at p = 2, while Calinski-Harabasz improved by 0.5%; its best improvement was 1% at p = 1.4.
- Noise features: More than 10 times higher relative error occurred for baseline Silhouette (Euclidean) after noise features were added compared with experiments without noise features.The comparison concerns the K-Means baseline and demonstrates the impact of irrelevant features on validation performance.
- Noise features: 0.052 was the smallest overall relative error, achieved by explicit re-scaling followed by K-Means with Silhouette and Minkowski distance at p = 1.4.The same p produced relative errors of 0.053 for Silhouette with Euclidean distance and 0.054 for Dunn’s index with Minkowski distance.
- Noise features: 85.5% was the best overall estimate of the true cluster count with 50% noise features, achieved by explicit re-scaling followed by K-Means using Dunn’s index and Minkowski distance at p = 1.4.This configuration was best for all indexes except Hartigan.
5. Conclusion
The paper introduces feature re-scaling methods based on iMWK-Means weights and finds that they improve cluster-number estimation with noise features, while performance depends on the evaluation objective and Minkowski p.
- Three feature re-scaling methods use weights obtained by intelligent Minkowski Weighted K-Means, either implicitly through weighted distances or explicitly before clustering.The explicit approach can be followed by K-Means.
- Across 700 synthetic data sets, noise-feature settings improved most tested validity indexes for suitable Minkowski p values, especially between 1.4 and 1.8.
- With noise, explicit re-scaling followed by K-Means best estimated the true number of clusters, whereas explicit re-scaling without K-Means achieved better adjusted Rand-index results.
- Future work will estimate p across different scenarios and develop K-Means initialization methods to avoid repeated runs used in these experiments.