Shapley-Inspired Feature Weighting in $k$-means with No Additional Hyperparameters
This addresses the challenge of feature relevance in clustering for high-dimensional or noisy data, though it is incremental as it builds on existing feature weighting and Shapley value concepts.
The paper tackles the problem of feature weighting in clustering by proposing SHARK, a Shapley-inspired algorithm that requires no additional hyperparameters, and shows it matches or outperforms existing methods with improved robustness and accuracy in noisy settings.
Clustering algorithms often assume all features contribute equally to the data structure, an assumption that usually fails in high-dimensional or noisy settings. Feature weighting methods can address this, but most require additional parameter tuning. We propose SHARK (Shapley Reweighted $k$-means), a feature-weighted clustering algorithm motivated by the use of Shapley values from cooperative game theory to quantify feature relevance, which requires no additional parameters beyond those in $k$-means. We prove that the $k$-means objective can be decomposed into a sum of per-feature Shapley values, providing an axiomatic foundation for unsupervised feature relevance and reducing Shapley computation from exponential to polynomial time. SHARK iteratively re-weights features by the inverse of their Shapley contribution, emphasising informative dimensions and down-weighting irrelevant ones. Experiments on synthetic and real-world data sets show that SHARK consistently matches or outperforms existing methods, achieving superior robustness and accuracy, particularly in scenarios where noise may be present. Software: https://github.com/rickfawley/shark.