This article is cited in 3 papers

Intellectual Analisys of Data

Constructive evaluation of the complete cross-validation for threshold classification

I. S. Guz

Department of management and applied mathematics, Moscow institute of physics and technology, 141700, Russia, Moscow Region, town Dolgoprudny, Institutsky lane, 9

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: classification, tight complete cross-validation bounds, anomalous objects filtering.

UDC: 519.7:004.852

Received 19.05.2011, Published 25.07.2011