Convex hulls and convex separable sets in the multiclass pattern recognition


DOI: 10.34759/trd-2019-109-20

Аuthors

Gainanov D. N.1*, Chernavin N. P.2, Chernavin P. F.2**, Chernavin F. P.3, Rasskazova V. A.1***

1. Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia
2. Ural Federal University, 19, Mira str., Ekaterinburg, 620002, Russia
3. Institute of economics the Ural branch of Russian Academy of Sciences, 29, str. Moskovskaya, Yekaterinburg, 620014, Russia

*e-mail: damir.gainanov@gmail.com
**e-mail: chernavin.p.f@gmail.com
***e-mail: varvara.rasskazova@mail.ru

Abstract

The paper is devoted to the multiclass pattern recognition problem in its geometry statement. Such problems are often occurring in various areas of financial mathematics, diagnosis and forecasting. There is proposed a geometry based approach connected with separatebility properties of convex hulls of sets of finite-dimensional space.

The multiclass pattern recognition problem under consideration is to construct a decision rule to assign an arbitrary input point to some class of the training sample. The main idea is to construct a convex hull for each class of training sample and then to assign an input point to such a class which convex hull will be the most closely to the corresponding point. It is shown that in case when classes of the training sample do not intersect (by points), the proposed approach entails the uniqueness of the decision rule. In general case, it is required that the convex hull of each class does not contain points from other classes. The problems, which training samples satisfy this condition, were called as convex separable set solvable.

The results of computational experiments show that a number of classic pattern recognition problems are convex separable set solvable. In particular, there are presented in the paper the results of computational experiments using test data of the public library. As it turned out, the Iris Fischer problem – fundamental in this particular class – is a convex separable set solvable. Moreover, the constructed decision rule provides the classification of the training sample corresponding to the best known solution. This non trivial fact allows one to expect a high application efficiency of the proposed approach.

It occurred that the hardest stage of the proposed approach is to construct convex hulls for training sample. For these purposes, there were used well known Gale transformation for a sequence of points and after that a convolution S. N. Chernikov’ algorithm to search a minimal infeasible systems of an infeasible system of linear inequalities. These auxiliary algorithm is based on the previously proved dual relationship between hypergranes of a convex polyhedron and multiindices of minimal infeasible systems of an infeasible system of linear inequalities. The corresponding procedure were described in the paper in frame of the small academic example.

It should be also noted that the formalization of the class of convex separable set solvable problems of multiclass pattern recognition, as well as the further development of methods for constructing a convex hull in a finite dimensional space, are objects of further research.

An application meaning of the results obtained, in addition to the above mentioned problems of financial mathematics and forecasting, are also connected with important industry problems such as, for example, metallurgical production. One of the most important problem in such production is to reduce manufacturing errors due to reassignment or complete termination of irrational technological routes. In this regard, the direction of further research could be associated with mathematical modelling, and its continuation in frame of multiclass pattern recognition, to solve problems on the operational technological routes control in the discrete production (in particular, un the metallurgical production).

Keywords:

classification, pattern recognition, algorithm, decision rule, convex hull, convex separable set

References

  1. Bel’skii A.B., Choban V.M. Trudy MAI, 2013, no. 66, available at: http://trudymai.ru/eng/published.php?ID=40856

  2. Gainanov D.N. Kombinatornaya geometriya i grafy v analize nesovmestnykh sistem i raspoznavanii obrazov (Combinatorial Geometry and Graphs in the Infeasible Systems Theory and Pattern Recognition), Moscow, Nauka, 2014, 173 p.

  3. Geil D. Teoriya lineinykh ekonomicheskikh modelei (Linear Economics Models), Moscow, Izd-vo inostrannoi literatury, 1963, 418 p.

  4. Goldovskii A.A. Trudy MAI, 2019, no. 107, available at: http://trudymai.ru/eng/published.php?ID=107919

  5. Danilenko A.N. Trudy MAI, 2011, no. 46, available at: http://trudymai.ru/eng/published.php?ID=25997

  6. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya (Introduction to the Linear and Convex Programming), Moscow, Nauka, 1970, 191 p.

  7. Eremin I.I. Teoriya lineinoi optimizatsii (Linear Optimization Theory), Ekaterinburg, Izd-vo Ekaterinburg, 1999, 312 p.

  8. Zhuravel’ A.A., Troshko N.V., Edzhubov L.G. Ispol’zovanie algoritma obobshchennogo portreta dlya opoznavaniya obrazov v sudebnom pocherkovedenii. Pravovaya kibernetika (Generalized Portrait Algorithm in Solving Pattern Recognition and Forensic Handwriting Problems), Moscow, Nauka, 1970, pp. 212 – 227.

  9. Zakirov R.G. Trudy MAI, 2015, no. 85, available at: http://trudymai.ru/eng/published.php?ID=67515

  10. Mazurov V.D. Metod komitetov v zadachakh optimizatsii i klassifikatsii (The Committees Method in Optimization and Classification Problems), Moscow, Nauka, 1990, 248 p.

  11. Mazurov V.D. Lineinaya optimizatsiya i modelirovanie (Linear Optimization and Modelling), Sverdlovsk, UrGU, 1986, 68 p.

  12. Nikonov O.I., Chernavin F.P. Den’gi i Kredit, 2014, no. 11, pp. 52 – 55.

  13. Syrin S.A., Tereshchenko T.S., Shemyakov A.O. Trudy MAI, 2015, no. 82, available at: http://trudymai.ru/eng/published.php?ID=58745

  14. Flakh P. Mashinnoe obuchenie. Nauka i iskusstvo postroeniya algoritmov, kotorye izvlekayut znaniya iz dannykh (Machine Learning. The Science and Art on Algorithms Construction, which Derive Knowledges from Data), Moscow, DMK Press, 2015, 400 p.

  15. Chernavin N.P., Chernavin F.P. Mezhdunarodnaya nauchnaya konferentsiya “Nauka molodykh”: sbornik materialov, Moscow, Izd-vo Rusal’yans “Sova”, 2015, pp. 307 – 320.

  16. Chernavin N.P., Chernavin F.P. Sovremennye nauchnye issledovaniya v sfere ekonomiki: sbornik rezul’tatov nauchnykh issledovanii, Kirov, Mezhregional’nyi tsentr innovatsionnykh tekhnologii v obrazovanii, 2018, pp. 1052 – 1062.

  17. Chernikov S.I. Lineinye neravenstva (Linear Inequalities Theory), Moscow, Nauka, 1970, 191 p.

  18. Diego Fernandes-Francos, Jscar Fontela-Romero, Amparo Alonso-Betanzos. One-class classification algorithm based on convex hull, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 2016, available at: https://www.elen.ucl.ac.be/Proceedings/esann/esannpdf/es2016-136.pdf

  19. Gainanov D. N., Mladenovic N., Berenov. D. Dichotomy algorithms in the multi-class problem of pattern recognition, Advances in Operational Research in the Balkans, 2019, pp. 3 – 14. doi: https://doi.org/10.1007/978-3-030-21990-1_1

  20. Pardalos P.M., Li Y., Hager. W.W. Linear Programming Approaches to the Convex Hull Problem in Rm , Computers Mathematics Applications, 1995, vol. 29, no. 7, pp. 23 – 29.

  21. Zhenbing Liu, JG Liu, Chao Pan, Guoyou Wang. A novel geometric approach to binary classification based on scaled convex hulls, Neural Networks, IEEE Transactions on, 2009, no. 20 (7), pp. 1215 – 1220.

  22. Uci machine learning repository, available at: http://archive.ics.uci.edu/ml/machine-learning-databases/iris

  23. Koel’o L.P., Richard V. Postroenie sistem mashinnogo obucheniya na yazyke Python (Building Machine Learning Systems with Python), Moscow, DMK Press, 2016, 302 p.


Download

mai.ru — informational site MAI

Copyright © 2000-2024 by MAI

 Вход