Geodesic
Computational complexity of prototype and feature selection for isotonic classification problems
Matematičeskaâ biologiâ i bioinformatika, Tome 10 (2015) no. 2, pp. 356-371.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MBB_2015_10_2_a18,
     author = {A. V. Zukhba},
     title = {Computational complexity of prototype and feature selection for isotonic classification problems},
     journal = {Matemati\v{c}eska\^a biologi\^a i bioinformatika},
     pages = {356--371},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MBB_2015_10_2_a18/}
}
TY  - JOUR
AU  - A. V. Zukhba
TI  - Computational complexity of prototype and feature selection for isotonic classification problems
JO  - Matematičeskaâ biologiâ i bioinformatika
PY  - 2015
SP  - 356
EP  - 371
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MBB_2015_10_2_a18/
LA  - ru
ID  - MBB_2015_10_2_a18
ER  - 
%0 Journal Article
%A A. V. Zukhba
%T Computational complexity of prototype and feature selection for isotonic classification problems
%J Matematičeskaâ biologiâ i bioinformatika
%D 2015
%P 356-371
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MBB_2015_10_2_a18/
%G ru
%F MBB_2015_10_2_a18
A. V. Zukhba. Computational complexity of prototype and feature selection for isotonic classification problems. Matematičeskaâ biologiâ i bioinformatika, Tome 10 (2015) no. 2, pp. 356-371. http://geodesic.mathdoc.fr/item/MBB_2015_10_2_a18/

[1] Vorontsov K. V., “O problemno-orientirovannoi optimizatsii bazisov zadach raspoznavaniya”, ZhVM i MF, 38:5 (1998), 870–880 | MR | Zbl

[2] Vorontsov K. V., “Optimizatsionnye metody lineinoi i monotonnoi korrektsii v algebraicheskom podkhode k probleme raspoznavaniya”, ZhVM i MF, 40:1 (2000), 166–176 | MR | Zbl

[3] Vorontsov K. V., “Kombinatornyi podkhod k otsenke kachestva obuchaemykh algoritmov”, Matematicheskie voprosy kibernetiki, 13, ed. Lupanov O. B., Fizmatlit, M., 2004, 5–36

[4] Vorontsov K. V., Makhina G. A., “Printsip maksimizatsii zazora dlya monotonnogo klassifikatora blizhaishego soseda”, Matematicheskie metody raspoznavaniya obrazov, 15-ya vserossiiskaya konferentsiya, MAKS Press, M., 2011, 64–67

[5] Gromova O. A., Torshin I. Yu., Rudakov K. V., Grustlivaya U. E., Kalacheva A. G., Yudina N. V., Egorova E. Yu., Limanova O. A., Fedotova L. E., Gracheva O. N. i dr., “Nedostatochnost magniya — dostovernyi faktor riska komorbidnykh sostoyanii: rezultaty krupnomasshtabnogo skrininga magnievogo statusa v regionakh Rossii”, Farmateka, 2013, no. 6, 116–129

[6] Guz I. S., “Nelineinye monotonnye kompozitsii klassifikatorov”, Matematicheskie metody raspoznavaniya obrazov, 13-ya vserossiiskaya konferentsiya, MAKS Press, M., 2007, 111–114

[7] Guz I. S., “Minimizatsiya empiricheskogo riska pri postroenii monotonnykh kompozitsii klassifikatorov”, Trudy MFTI, 3:3(11) (2011), 115–121 | MR

[8] Zagoruiko N. G., Prikladnye metody analiza dannykh i znanii, IM SO RAN, Novosibirsk, 1999

[9] Ivanov M. N., Vorontsov K. V., “Primenenie monotonnogo klassifikatora blizhaishego soseda v zadache kategorizatsii tekstov”, Intellektualizatsiya obrabotki informatsii (IOI-9), Dokl., Torus Press, M., 2012, 621–624

[10] Kormen T., Leizerson Ch., Rivest R., Shtain K., Algoritmy: postroenie i analiz, 2-e izdanie, Izdatelskii dom “Vilyams”, M., 2005

[11] Makhina G. A., “O vosstanovlenii monotonnykh bulevykh funktsii metodom blizhaishego soseda”, Intellektualizatsiya obrabotki informatsii (IOI-2012), Dokl., Torus Press, M., 2012, 78–81

[12] Uspenskii V. M., Informatsionnaya funktsiya serdtsa. Teoriya i praktika diagnostiki zabolevanii vnutrennikh organov metodom informatsionnogo analiza elektrokardiosignalov, Ekonomika i informatika, M., 2008, 116 pp.

[13] Uspenskii V. M., “Informatsionnaya funktsiya serdtsa”, Klinicheskaya meditsina, 86:5 (2008), 4–13

[14] Barlow R., Bartholomew D., Bremner J., Brunk H., Statistical inference under order restrictions; the theory and application of isotonic regression, Wiley, New York, 1972 | MR | Zbl

[15] Chandrasekaran R., Ryu Y. U., Jacob V. S., Hong S., “Isotonic separation”, INFORMS J. on Computing, 17:4 (2005), 462–474 | DOI | MR | Zbl

[16] Cortes C., Vapnik V., “Support-vector networks”, Machine Learning, 20:3 (1995), 273–297 | Zbl

[17] Ivanov M. N., “Prototype sample selection based on minimization of the complete cross validation functional”, Pattern Recognition and Image Analysis, 20:4 (2010), 427–437 | DOI

[18] Kamp R., Feelders A., Barile N., “Isotonic classification trees”, Advances in Intelligent Data Analysis VIII, Proceedings of the 8th International Symposium on Intelligent Data Analysis, Springer-Verlag, Berlin–Heidelberg, 2009, 405–416 | DOI

[19] Malar B., Nadarajan R., Saisundarakrishnan G., “Isotonic separation with an instance selection algorithm using softset: Theory and experiments”, WSEAS Transactions On Information Science And Applications, 9:11 (2012), 350–367

[20] Natarajan B. K., “Sparse approximate solutions to linear systems”, Society for Industrial and Applied Mathematics, 24 (1995), 227–234 | MR | Zbl

[21] Royston P., “A useful monotonic non-linear model with applications in medicine and epidemiology”, Statistics in Medicine, 19:15 (2000), 2053–2066 | 3.0.CO;2-6 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[22] Ryu Y. U., Chandrasekaran R., Jacob V. S., “Breast cancer prediction using the isotonic separation technique”, European Journal of Operational Research, 181:2 (2007), 842–854 | DOI | Zbl

[23] Sill J., “Monotonic networks”, Advances in Neural Information Processing Systems, eds. Jordan M. I., Kearns M. J., Solla S. A., MIT Press, Cambridge, 1998, 661–667

[24] Sill J., Abu-Mostafa Y. S., “Monotonicity hints”, Advances in Neural Information Processing Systems, eds. Mozer M. C., Jordan M. I., Petsche T., MIT Press, Cambridge, 1997, 634–640

[25] Spirin N. V., Vorontsov K. V., “Learning to rank with nonlinear monotonic ensemble”, 10th International Workshop on Multiple Classifier Systems (Naples, Italy, June 15–17, 2011), Lecture Notes in Computer Science, eds. Sansone C., Kittler J., Roli F., Springer-Verlag, Berlin, 2011, 16–25 | DOI

[26] Torshin I. Yu., “The study of the solvability of the genome annotation problem on sets of elementary motifs”, Pattern Recognition and Image Analysis, 21 (2011), 652–662 | DOI

[27] Uspenskiy V. M., Vorontsov K. V., Tselykh V. R., Bunakov V. A., “Information function of the heart: Discrete and fuzzy encoding of the ECG-signal for multidisease diagnostic system”, Advances in Mathematical and Computational Tools in Metrology and Testing X, Series on Advances in Mathematics for Applied Sciences, 86, World Scientific, Singapore, 2015, 377–384 | DOI

[28] Zhang J., “Advancements of Outlier Detection: A Survey”, ICST Transactions on Scalable Information Systems, 13 (2013) | DOI

[29] Zukhba A. V., “NP-completeness of the problem of prototype selection in the nearest neighbor method”, Pattern Recognition and Image Analysis, 20 (2010), 484–494 | DOI