Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
Preprint
Abstract
This work aims to address an open problem in data valuation literature concerning the efficient computation of Data Shapley for weighted $K$ nearest neighbor algorithm (WKNN-Shapley). By considering the accuracy of hard-label KNN with discretized weights as the utility function, we reframe the computation of WKNN-Shapley into a counting problem and introduce a quadratic-time algorithm, presenting a notable improvement from $O(N^K)$, the best result from existing literature. We develop a deterministic approximation algorithm that further improves computational efficiency while maintaining the key fairness properties of the Shapley value. Through extensive experiments, we demonstrate WKNN-Shapley's computational efficiency and its superior performance in discerning data quality compared to its unweighted counterpart.
Keywords
All Related Versions
This publication has 2 references indexed in Scilit:
- The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clientsExpert Systems with Applications, 2009
- A Value for N-Person Games1952