*119108*

Masich I.S.

Siberian State Aerospace University

named after academician M. F. Reshetnev, Russia

Selection of informative patterns in logical

algorithms of recognition

A method of selection of logical rules that describe patterns in a studied phenomenon or system and are designed for solving the problem of recognition is considered in this paper. The method of rules selection is based on the criterion of maximizing the separating margin between the images of the classes and is reduced to the pseudo-Boolean optimization problem.

By now quite efficient classification algorithms for solving diagnosis and prognosis problems are developed, that solves problems with high accuracy under skillful setting. But in the practical application of such algorithms often raises the question of the interpretability and proof of results. Decision making requires an explicitly model, such a model, in which calculated solutions are justified and based on the available data.

The process of formation of decision rules is accompanied by solving problems of choosing the best alternatives according to some criterion. The formalization of this process as a series of combinatorial optimization problems creates a flexible and efficient algorithm of logical analysis for the data classification [1].

Consider the recognition problem for objects described by binary attributes and divided into two classes . The object is describe by a binary vector and can be presented as a point in the subcube of binary attribute space .

Consider a pattern P (or a rule) as a term which covers at least one object of a class and does not cover any object of another class. That is, the pattern corresponds to the subcube, which has a non empty intersection with one of the sets ( or ), and an empty intersection with another set ( or , respectively). A pattern P, which does not intersect with , we call positive and a pattern P ', which does not which does not intersect with - negative.

Suppose that in result of searching for patterns in learning sample we found a number of positive patterns of P_i, i = 1, ..., p, and negative patterns of N_j, j = 1, ..., n.

The decision function can be defined by the expression

for some object a, where P_i(a)=1, if the pattern P_i covers the object a, and P_i(a)=0 otherwise. The same for N_j(a).

During solving many problems rises the question of selection patterns from the total number of patterns for the formation of a decision rule. That can not only reduce its size, but also to improve recognition. Let introduce the variables that determine whether a pattern is presented in the decision function.

As the criterion for formation a decision rule, consider width of margin

Take into account emissions that may be presented in real problems. To do this, we introduce the variable

Then the problem of selection patterns can bу written in the following form.

,

where ,

,

,

Algorithms for solving these optimization problems are presented in [2, 3].

Literature

1. Antamoshkin A.N., Masich I.S. Combinatorial optimization and rule search in logical algorithms of machine learning. Engineering & automation problems, V.7, N.1, 2010, p.52-57.

2. A.N. Antamoshkin, I.S. Masich. Unimprovable algorithm for monotone pseudo-Boolean function conditional optimization. Engineering & automation problems. V. 6, N. 1, 2008, 71-75.

3. A.N. Antamoshkin, I.S. Masich. Heuristic search algorithms for monotone pseudo-boolean function conditional optimization. Engineering & automation problems. N. 3, 2007, 41-45.