Computational Complexity of Prototype and Feature Selection for Isotonic Classification Problems
Zukhba A.V.
Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow Region, Russia
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.