UDK 519.854.33
THE SELECTION OF LOGICAL PATTERNS FOR CONSTRUCTING A DECISION RULE OF RECOGNITION
A. N. Antamoshkin, I. S. Masich
Siberian State Aerospace University named after academician M. F. Reshetnev 31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660014, Russian Federation E-mail: i-masich@yandex.ru
We investigate an aspect of the construction of logical recognition algorithms – selection of patterns in the set of found patterns in the data. We consider the recognition problem for objects described by binary attributes and divided into two classes. In consequence of performance the procedure of searching patterns on the training set (a set of input data) a number of patterns has been found. The question is to select some patterns from their total number to form a decision rule. That can not only reduce the size of the decision rule, but also improve recognition. One way to make a selection of patterns is to select a subset of patterns that is needed to cover all objects of the training sample. This problem is formulated as an optimization problem. The resulting optimization model represents a problem of conditional pseudo-Boolean optimization, in which the objective function and the constraints functions are unimodal monotone pseudo-Boolean functions. Another way is to make the selection of such patterns, which when used together will increase separating capacity of the decision rule. As a criterion for the formation of the decision rule is considered the width of the separation margin. One more way is to select supporting objects and on their basis to form the rules. The selection of logical patterns, which is made in accordance with the proposed approach, can significantly reduce the number of patterns and simplify the decision rule, almost without compromising the accuracy of recognition. This makes the decision rule clearer, and the results more interpretable. It is necessary to support decision making for recognition.
analysis of data, classification, logical algorithm, recognition
References
- Alexe G., Alexe S., Hammer P. L., Liotta L., Petricoin E., Reiss M. Ovarian CancerDetection by Logical Analysis of Proteomic Data. Proteomics, 2004, no. 4(3), P. 766–783.
- Axelrod D., Bonates T., Hammer P. L., Lozina I. From Diagnosis to Therapy via LAD.Invited Lecture at INFORMS Annual Meeting, Denver, CO, October, 2004.
- Dupuis C., Gamache M., Páge J. F. Logical analysis of data for estimating passenger show rates in the airline industry, Journal of Air Transport Management 18, 2012. P. 78–81.
- Esmaeili S. Development of equipment failure prognostic model based on logical analysis of data, Master of Applied Science Thesis, Dalhousie University, Halifax, Nova Scotia, July 2012.
- Masich I. S. [Combinatorial optimization problem in the classification] Sistemy upravleniya i informatsionnye tekhnologii, 2009, no. 1.2(35), p. 283–288 (In Russ.).
- Hammer P. L., Bonates T. O. Logical analysis of data – An overview: From combinatorial optimization to medical applications. Annals of Operations Research 148, 2006.
- Antamoshkin A. N., Masich I. S. Pseudo-Boolean optimization in case of unconnected feasible sets. Models and Algorithms for Global Optimization. Series: Springer Optimization and Its Applications. Springer. 2007, vol. 4, p. 111–122.
- Antamoshkin A. N., Masich I. S. [Efficient algorithms for constrained optimization pseudo-monotone functions]. Vestnik SibGAU. 2003, no. 4, p. 60–67 (In Russ.).
- Golovenkin S. Е., Masich I. S., Shulman V. А. Et al. [Model of logical analysis for solving problem of prognosis of myocardial infarction complication]. Vestnik SibGAU. 2010, no. 4(30), p. 68–73 (In Russ.).
- Bache K., Lichman M. UCI Machine Learning Repository. Irvine, CA : University of California, School of Information and Computer Science, 2013. Available at: http://archive.ics.uci.edu/ml.
- Masich I. S. [The heuristic algorithms of boundary points search for an constraint pseudo-Boolean optimization problem.] Vestnik SibGAU. 2006, no. 1(8), p. 39–43 (In Russ.).
- Alexe G., Hammer P.L. Spanned patterns for the logical analysis of data, Discrete Appl. Math. 154, 2006. P. 1039–1049.
- Guoa C., Ryoo H. S. Compact MILP models for optimal and Pareto-optimal LAD patterns, Discrete Applied Mathematics 160, 2012. P. 2339–2348.
- Golovenkin S. Е., Gorban A. N., Shulman V. А. et. al. Oslozhneniya infarkta miokarda: baza dannykh dlya aprobatsii sistem raspoznavaniya i prognoza. [Complications of myocardial infarction: a database for testing recognition systems and forecasting]. Vychislitel'nyy tsentr SO RAN: Preprint. 1997, no. 6, 14 p. (In Russ.).
- Waikato Environment for Knowledge Analysis. Weka 3: Data Mining Software in Java. Available at: http://www.cs.waikato.ac.nz/ml/weka.
Antamoshkin Alexander Nikolaevich – Dr. Sc., Professor, Siberian State Aerospace University named after academician M. F. Reshetnev. E-mail: oleslav@mail.ru
Masich Igor Sergeevich – Cand. Sc., Docent, Siberian State Aerospace University named after academician M. F. Reshetnev. E-mail: i-masich@yandex.ru
