Constructive evaluation of the complete cross-validation for threshold classification

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.