DOI

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).
Translated title of the contributionConvex hulls and convex separable sets in the multiclass pattern recognition
Original languageRussian
Article number20
JournalТруды МАИ
Issue number109
DOIs
Publication statusPublished - 2019

    GRNTI

  • 06.35.00

    Level of Research Output

  • VAK List

ID: 12032372