Constructive evaluation of the complete cross-validation for threshold classification
Guz I.S.
Department of management and applied mathematics, Moscow institute of physics and technology, 141700, Russia, Moscow Region, town Dolgoprudny, Institutsky lane, 9
ivan.guzz@gmail.com
Abstract. Significant part of classification problems, in particular problems in medical diagnostics and bioinformatics, can be naturally reduced to the problem of selection of the optimal thresholds for features that take real values, which is studied in this article. Combinatorial upper and lower bounds of the complete cross-validation (CCV) for one-dimensional binary classification problem are introduced. Solution for this problem is sought in the family of monotone threshold classifiers. Iterative procedure for CCV bounds evaluation is introduced that has polynomial complexity of the number of objects in the problem. This procedure is also used for the detection of anomalous objects that can be filtered out to reduce upper CCV bound.
Key words: binary classification, tight complete cross-validation bounds, anomalous objects filtering.