EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations.

Pablo Barceló, Alexander Kozachinskiy, Miguel Romero, Bernardo Subercaseaux, José Verschae

ACM Transactions on Database Systems · 31.03.2027 · 52 (1) · 1-38

DOI: 10.1145/3834568 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 14.11.2026. Verfasst von Pablo Barceló und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 68 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Despite the wide use of k -Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neighbors classifiers offer interpretability from a “data perspective,” in which the classification of an input vector ̄ is explained by identifying the vectors ν̄ 1 , … , ν̄ k in the training set that determine the classification of ̄, we argue that such explanations can be impractical in high-dimensional applications, where each vector has hundreds or thousands of features and it is not clear what their relative importance is. Hence, we focus on understanding nearest neighbor classifications through a “feature perspective,” in which the goal is to identify how the values of the features in ̄ affect its classification. Concretely, we study abductive explanations such as “minimum sufficient reasons,” which correspond to sets of features in ̄ that are enough to guarantee its classification, and counterfactual explanations based on the minimum distance feature changes one would have to perform in ̄ to change its classification. We present a detailed landscape of positive and negative complexity results for counterfactual and abductive explanations, distinguishing between discrete and continuous feature spaces, and considering the impact of the choice of distance function involved. Finally, we show that despite some negative complexity results, Integer Quadratic Programming and SAT solving allow for computing explanations in practice.

Zitieren

APA

Barceló, P., Kozachinskiy, A., Romero, M., Subercaseaux, B., & Verschae, J. (2027). Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. ACM Transactions on Database Systems, 52(1), 1-38. https://doi.org/10.1145/3834568

Vancouver

Barceló P, Kozachinskiy A, Romero M, Subercaseaux B, Verschae J. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. ACM Transactions on Database Systems. 2027;52(1):1-38. doi:10.1145/3834568

BibTeX
@article{Barcel2027,
  author = {Barceló, Pablo and Kozachinskiy, Alexander and Romero, Miguel and Subercaseaux, Bernardo and Verschae, José},
  title = {Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations},
  journal = {ACM Transactions on Database Systems},
  year = {2027},
  volume = {52},
  number = {1},
  pages = {1--38},
  doi = {10.1145/3834568}
}
Kostenlos starten →