ASP-KNN: a declarative, constraint-aware, and explainable reformulation of k-Nearest Neighbors in answer set programming

The classical k-Nearest Neighbors (KNN) algorithm provides a simple and effective non-parametric approach to classification, but its procedural formulation offers limited transparency and lacks mechanisms for incorporating domain constraints or reasoning control. This paper introduces ASP-KNN, a declarative reformulation of KNN using Answer Set Programming (ASP), where neighbor selection, ranking, and vote aggregation are expressed through logical rules. The baseline ASP-KNN program closely reproduces the predictive behavior of classical KNN while exposing intermediate reasoning structures such as selected neighbors and vote distributions. Building on this formulation, we introduce two declarative extensions. The first extension incorporates label exclusion constraints that prevent the assignment of forbidden labels directly within the classification process. The second extension introduces a soft preference mechanism that refines decisions in ambiguous neighborhoods by favoring assignments supported by closer neighbors. Experiments on five widely used public benchmark datasets (Iris, Wine, Breast Cancer, Pima Diabetes, and Sonar), together with a lightweight comparison to a standard interpretable classifier (Decision Tree), suggest that the baseline ASP formulation closely reproduces the predictive behavior of classical KNN while enabling explicit constraint enforcement and interpretable reasoning traces. The constraint-based extension guarantees zero violations of forbidden labels, while the preference mechanism refines decisions in ambiguous neighborhood configurations without significantly altering overall predictive performance. Runtime analysis further reveals a computational trade-off between reasoning flexibility and efficiency, with most overhead arising from ASP grounding. Overall, ASP-KNN suggests that instance-based classification can be reformulated as a transparent and extensible reasoning process, enabling the integration of constraints, preferences, and symbolic explanations within a unified KNN framework.