Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors
$k$-nearest neighboralgorithm efficiencyapproximationaxiomatic characterizationcomputational complexitydata duplicationdata valuationempirical validationmemory costsmodel performancenear-linear timequadratic time complexityshapley valuesstructural propertiesweighted $k$nn
Data valuation quantifies the impact of individual data points on model performance, and Shapley values provide a principled approach to this important task due to their desirable axiomatic properties, albeit with high computational complexity. Recent breakthroughs have enabled fast computation of exact Shapley values for unweighted $k$-nearest neighbor ($k$NN) classifiers. However, extending this to weighted $k$NN models has remained a significant open challenge. The state-of-the-art methods either require quadratic time complexity or resort to approximation via sampling. In this paper, we show that a conceptually simple but overlooked approach