Abstract. Decision rules with monotonicity constraints are often used in biomedical diagnostics. Simultaneous feature selection and prototype selection can significantly affect the degree of monotonicity of the data set and, as a consequence, the classification quality. In this paper we propose a systematization of discrete optimization problems of simultaneous feature selection and prototype selection and estimate their computational complexity.

 

Key words: machine learning, feature selection, prototype selection, isotonic classifier, discrete optimization, computational complexity.