Optimal Subset Selection for Classification through SAT Encodings

In this work we propose a method for computing a minimum size training set consistent subset for the Nearest Neighbor rule (also said CNN problem) via SAT encodings. We introduce the SAT-CNN algorithm, which exploits a suitable encoding of the CNN problem in a sequence of SAT problems in order to exactly solve it, provided that enough computational resources are available. Comparison of SAT-CNN with well-known greedy methods shows that SAT-CNN is able to return a better solution. The proposed approach can be extended to several hard subset selection classification problems.