arXiv:2508.07952cs.LG2025-08被引 1

用博弈论方法自动加权特征,无需调参提升聚类效果。

Shapley-Inspired Feature Weighting in $k$-means with No Additional Hyperparameters

  • 基于谢林值思想,自动计算特征重要性并迭代调整权重。
  • 在含噪声数据上聚类准确率显著提升,优于现有方法。
  • 无需额外超参数,适合高维或噪声数据的聚类任务。

聚类算法常假设所有特征对数据结构贡献相同,这一假设在高维或噪声环境下往往失效。特征加权方法可缓解此问题,但多数需额外调参。本文提出SHARK(Shapley Reweighted k-means),受合作博弈论中谢林值启发,量化特征相关性,且不引入额外参数。证明k-means目标函数可分解为每特征谢林值之和,为无监督特征重要性提供公理基础,并将谢林值计算从指数时间降至多项式时间。SHARK通过取谢林贡献的倒数迭代重加权特征,突出有用维度,抑制无关特征,等价于将特征方差的算术平均替换为调和平均。在合成与真实数据集上的实验表明,SHARK始终匹配或超越现有方法,尤其在存在噪声时表现出更强鲁棒性与更高精度。代码开源:https://github.com/rickfawley/SHARK。

原文摘要 · Abstract (English)

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, and is equivalent to replacing the arithmetic mean of feature dispersions with their harmonic mean. 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.

聚类特征加权谢林值无超参

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。