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.
Optimal Subset Selection for Classification through SAT Encodings
Basta Stefano
2008
Abstract
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.