{"ID":2883732,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.07952","arxiv_id":"2508.07952","title":"Shapley-Inspired Feature Weighting in $k$-means with No Additional Hyperparameters","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.07952","url_pdf":"https://arxiv.org/pdf/2508.07952v1","authors":"[\"Richard J. Fawley\",\"Renato Cordeiro de Amorim\"]","published":"2025-08-11T13:07:21Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false,"code_links":[{"ID":611012,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2883732,"paper_url":"https://arxiv.org/abs/2508.07952","paper_title":"Shapley-Inspired Feature Weighting in $k$-means with No Additional Hyperparameters","repo_url":"https://github.com/rickfawley/shark","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}