Using the K-associated Optimal Graph to Provide Counterfactual Explanations

Only recently have data mining results been thought to aid human interpretability. Explanations are useful to understand the reasons why (or why not) the model has (or hasn't) achieved a given decision. Counterfactual explanations aim to explain why not the model yield an expected decision. A counterfactual explanation is usually done by a post -hoc algorithm which often requires access to training data or model details. Also, the majority of such algorithms do not generate robust explanations, once they assume the model is noise -free and will not be updated over time. This paper proposes a model agnostic, training data -independent algorithm to provide robust counterfactual explanations. The proposed method generates data samples around the instance to be explained and builds a K-Associated Optimal Graph (KAOG) with those data. KAOG allows measuring how intertwined the data examples are regarding their classes. This way, the explanation method can search for an example that relies on a noise -free area in the attribute space, granting trust to the explanation. Experiment results on counterfactual feasibility and distance from query data show the effectiveness of the proposed algorithm when compared to ten state-of-the-art methods on three data sets.