Counterfactual explanations with the k-Nearest Neighborhood classifier and uncertain data

counterfactual Analysis is a powerful tool in Explainable Machine Learning. Given a classifier and a record, one seeks the smallest perturbation necessary to have the perturbed record, called the counterfactual explanation, classified in the desired class. When applied to real-world scenarios, Counterfactual Analysis may be affected by different sources of uncertainty, which should be taken into account to provide robust counterfactual explanations. In this paper, we address the problem of finding counterfactual explanations in which uncertainty involves features and the recourse. Feature uncertainty reflects the inherent variability and noise present in data, and the way they are measured. Uncertainty may also be present in the recourse implementation, as the actions prescribed by the counterfactual explanation may not be executed exactly by the user. More precisely, we assume a tabular data set in which each record, instead of being identified with a point, is given by a (convex) set modeling uncertainty around a nominal value or the result of an aggregation procedure. Moreover, the counterfactual solution is modeled as a convex set centered at a reference point, with a prescribed shape. The baseline classifier used is the 𝑘-Nearest Neighbor (𝑘-NN), which allows output explainability and has deep theoretical foundations. Finding counterfactual explanations with a 𝑘-NN classifier where both the records and the counterfactual are given by sets is expressed as a mixed integer nonlinear optimization problem, solved with a Variable Neighborhood Search heuristic.