高效计算kNN分类中数据贡献值，解决传统方法太慢问题
Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
- 利用kNN局部性设计动态规划算法，显著降低计算开销
- 加权kNN算法时间复杂度为O(Wkn²)，无权重时达O(nk²)
- 适合需要精准数据价值评估的机器学习研究者
数据估值旨在量化单个数据点对模型性能的贡献，是机器学习中的核心挑战。基于博弈论的巴赞夫值提供公平估值框架，但存在指数级计算复杂度。本文针对k近邻（kNN）分类器，提出高效算法以计算巴赞夫值。首先证明该问题是#P难的；尽管如此，我们利用kNN的局部特性，设计出实用的精确算法。主要贡献包括：针对加权kNN的伪多项式算法，时间复杂度为O(Wkn²)，其中W为前k个权重之和的最大值；针对无权重kNN的专用算法，时间复杂度为O(nk²)，即与数据点数线性相关。此外还提供了高效的蒙特卡洛估计方法。在真实数据集上的大量实验表明，该方法兼具实用性与有效性。
原文摘要 · Abstract (English)
Data valuation, the task of quantifying the contribution of individual data points to model performance, has emerged as a fundamental challenge in machine learning. Game-theoretic approaches, such as the Banzhaf value, offer principled frameworks for fair data valuation; however, they suffer from exponential computational complexity. We address this challenge by developing efficient algorithms specifically tailored for computing Banzhaf values in $k$-nearest neighbor ($k$NN) classifiers. We first establish the theoretical hardness of the problem by proving that it is \#P-hard. Despite this intractability, we exploit the locality properties of $k$NN classifiers to develop practical exact algorithms. Our main contribution is a dynamic programming framework that achieves significant computational improvements: we present a pseudo-polynomial algorithm with $O(Wkn^2)$ time complexity for weighted $k$NN classifiers, where $W$ is the maximum sum of top-$k$ weights, and a specialized algorithm for unweighted $k$NN that achieves $O(nk^2)$ time complexity, that is, linear in the number of data points. We also offer efficient Monte Carlo estimation methods. Extensive experiments on real-world datasets demonstrate the practical efficiency of our approach and its effectiveness in data valuation applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。