The paper reviews the issues of detection of hidden rules (or patterns) in data sets and their use to support decision making in recognition. The problem of nding patterns is considered as the problem of conditional optimization of monotone pseudo-Boolean functions. For comparison of patterns, three criteria are used: simplicity, selectivity and evidence, as well as their possible overlap. We consider the types of patterns obtained in accordance with these criteria, which are of the greatest interest for supporting decision making in recognition. The problem of searching for informative patterns by means of formalizing this search in the form of a conditional pseudo-Boolean optimization problem is investigated. The analysis of properties of the optimization model is carried out, and a new alternative optimization model is proposed to search for strong spanned patterns.
At present, when solving classi cation problems, in addition to the requirement of high accuracy, the necessity often arises for interpretability and validity of the obtained solutions. Especially interpretability and validity are key factors in solving those practical problems in which losses from making the wrong decision can be great. Therefore, the decision support system used for such problems should justify possible solutions and interpret the result.
To create such system, data classi cation algorithms are required that, in addition to the solution itself, provide an explicit rule, that is, they reveal knowledge from the available data. This is true for logical classi cation algorithms, the working principle of which is to identify patterns in data and formalize them in the form of rules set, i.e. a set of patterns described by a simple logical formula. ? Results were obtained in the framework of the state task 2.5527.2017/8.9 of the Ministry of Education and Science of the Russian Federation Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
The process of forming logical rules is accompanied by solving the problems of choosing the best alternatives in accordance with some criteria. In the studied method the formalization of the formation process of logical rules is implemented in the form of a number of problems of combinatorial optimization, which forms a exible and e cient algorithm for nding patterns in the primary data. By combining a number of patterns in the composition, the obtained classi er will solve the problem.
However, at present time, there are a number of problems associated with the application of the method of logical data analysis in solving practical classi cation problems. One of them is the construction of optimization models for the informative patterns formation. While considering this problem, rst of all, it is necessary to determine the criteria and constraints that are the foundation of these optimization models.
The main objective is increase of the interpretability of the classi er and the quality of recognition of new observations, that is, to improve the classi er's generalizing abilities.
The main object of the research conducted by the authors is the method of logical analysis of data derived from the theory of combinatorial optimization [3]. This method belongs to rule based classi cation algorithms and is based on identi cation of logical patterns from the data sample. This paper analyses the existing optimization model for searching patterns and o ers an alternative optimization model for constructing strong spanned patterns. 2
The creation and use of logical classi cation algorithms is based on the identication in the primary data of the patterns from which a decision function is formed. The search for patterns can be considered as a task of combinatorial optimization. To obtain a more e cient solution, the choice of the optimization algorithm should be made proceeding from the characteristic properties inherent in the optimization considered problem. In this paper some properties of optimization problems are considered that can be solved in the course of searching of logical patterns in the data.
Let us consider the problem of recognizing objects described by binary variables and divided into two classes
K = K+ [ K
B2n; where B2n = B2 B2 B2, B2 = f0; 1g.
In this case, the classes do not intersect:
K+ \ K = ;:
An observation X 2 K is described by a binary vector X = (x1; x2; :::; xn) and can be represented as a point in the hypercube of the space of binary variables B2n. Observations of the class K+ will be called positive points of the sample K, and observations of the class K will be called negative points of the sample.
Let us consider a subset of points from B2n, for which some variables are xed and identical, and the rest take an arbitrary value: for some subsets A; B f1; 2; : : : ; ng, A T B = ;. This set can also be de ned as a Boolean function that takes a true value for the elements of the set: T = fx 2 B2njxi = 1 for 8i 2 A and xj = 0 for 8j 2 Bg t(x) = ^ xi i2A !
0
1 ^ xj A : j2B
The set of points x, for which t(x) = 1, is de ned as S(t). S(t) is a subcube in the Boolean hypercube B2n , the number of points of the subcube is 2(n jAj jBj).
The binary variable xi or its negation xi in a term is called a literal. Record xi indicates xi if = 1 and xi if = 0. Thus, a term is a conjunction of various literals that does not simultaneously contain a certain variable and its negation. The multiplicity of literals in the term t is de ned as Lit(t).
Let us consider that the term t covers the point a 2 B2n, if t(a) = 1, that is, this point belongs to the corresponding subcube.
In this case under a pattern P (or rule) is meant a term that covers at least one observation of a certain class and does not cover any observations of another class [1]. That is, the pattern corresponds to a subcube having a non-empty intersection with one of the sets (K+ or K ) and an empty intersection with another set (K or K+ relatively). A consistent pattern P , which does not intersect with K , will be called positive and a consistent pattern P 0, which does not intersect with K+ will be called negative. Below for de niteness only positive patterns will be considered. A set of observations that are covered by the pattern P is de ned as Cov(P ).
Patterns are elementary blocks for constructing logical recognition algorithms. The most useful for this purpose are patterns with the largest coverage (maximum patterns), that is, those for which jCov(P )j is maximum.
One of the ways in constructing a set of patterns for the recognition algorithm is to search for patterns that are based on the values of the attributes of speci c objects. 3
There are no single unambiguous criteria for comparing logical patterns with each other. While analyzing various data, di erent requirements can be imposed on the quality and features of the formed patterns. In accordance with [5], to evaluate the quality of pure patterns (homogeneous, non-covering observations of other classes), three criteria are used { simplicity, selectivity and evidence, as well as their possible overlap.
The criterion of simplicity (or compactness) is often used to compare patterns among themselves, including those obtained by di erent learning algorithms.
A pattern P1 is more preferable to P2 by the criterion of simplicity (de ne P1 P2), if Lit(P1) Lit(P2).
In [2] a pattern P is prime if after removing any literal from Lit(P ) a term is formed and is not a (pure) pattern (that is, it covers the observations of another class).
It is obvious that the optimality of a pattern by the criterion of simplicity is identical with the assertion that this pattern is the prime.
The search for simpler patterns has well-founded premises. First, such patterns are better interpreted and understandable for humans when used in decision making. Secondly, it is often believed that simpler patterns have a better generalizing ability, and their use leads to better recognition accuracy. However, this assertion is debatable; moreover, it has been shown in [6] that a decrease in simplicity can lead to greater accuracy.
The usage of simple and, therefore, short patterns leads to the fact that the number of incorrectly recognized positive observations (false negative) decreases, but at the same time this can lead to an increase in the number of incorrectly recognized negative observations (false positive observations). The natural way to reduce the number of erroneous positive observations is the formation of more selective observations, which is achieved by reducing the size of the subcube that determines the pattern.
A pattern P1 is more preferable to P2 by criterion of selectivity (de ne P1 P2) if S(P1) S(P2).
It should be noted that the two criteria considered above are opposite to each other, that is, Lit(P1) Lit(P2) , S(P1) S(P2).
A pattern that optimal by the selectivity criterion is a minterm, that is, a pattern covering the only positive observation. The use of this criterion by itself is, of course, not e ective, since the resulting patterns (minterms) do not possess any generalizing ability. But the selectivity criterion is extremely useful when used in conjunction with other criteria, which will be discussed later.
Another useful criterion is a criterion based on coverage, that is, the number of positive observations of the training sample that satisfy the conditions of the pattern. Undoubtedly, the patterns with greater coverage have a greater generalizing ability. And the observations of the training sample, covered by the pattern, are a kind of proof of the applicability of this pattern to the decision.
A pattern P1 is more preferable to P2 by criterion of evidence (de ne P1 " P2), if Cov(P1) Cov(P2).
The patterns that are optimal by the criterion of evidence are called strong. That is, a pattern P is strong in such case that there is no such pattern P', that Cov(P 0) Cov(P ).
It is important to note that the considered criteria are not completely independent. So, the criteria of simplicity and selectivity are opposite to each other. Moreover, the following dependencies can be noted:
P1
P2 ) P1
P1
P2 ) P2 " P1: To combine the considered criteria with each other two methods are used.
For given criteria and a pattern P1 is more preferable with respect to P2 by intersection of ^ (de ne P1 ^ P2), if and only if P1 P2 and P1 P2.
For given criteria and a pattern P1 is more preferable with respect to P2 on lexicographical re nement j (de ne P1 j P2), if and only if P1 P2 or (P1 P2 and P1 P2).
In [2] it is shown that only three of all possible combinations of criteria deserve attention. Patterns that are optimal by criterion ^" are called spanned. Patterns that are optimal by criterion "j are called strong prime. And patterns that are optimal by criterion "j are called strong spanned.
Among all the types of patterns obtained in accordance with the above criteria and their combinations, patterns of prime, strong prime and strong spanned are most useful for identifying informative patterns and their use to support decision making in recognition. 4
Let us emphasize some a 2 K+ observation and de ne pattern P a, covering the observation a. Those variables that are xed in P a , are equal to the corresponding values of the attributes of the object a.
To de ne the pattern P a, the binary variables Y = (y1; y2; : : : ; yn) are introduced: yi = 1; if ith attribute is xed in P a; 0; otherwise.
Some point b 2 K+ will be covered by the pattern P a only if yi = 0 for all i for which bi 6= ai. On the other hand, some point c 2 K will not be covered by the pattern P a in case if yi = 1 at least for one variable i, for which ci 6= ai.
A condition that says that a positive pattern must not contain any point K requires that for each observation c 2 K variable yi take the value 1 for at least one i, for which ci 6= ai [2]:
On the other hand, a positive observation b 2 K+ will be a part of considerate subcube when the variable yi takes the value 0 for all indices i for which bi 6= ai. Thus, the number of positive observations covered by a-pattern can be calculated as:
X
Thus, the problem of nding the maximum pattern can be written in the form
of a problem of nding such values Y = (y1; y2; : : : ; yn), in which the obtained
pattern P a covers as many possible points b 2 K+ and does not cover any points
c 2 K [4]:
(
Y
Let us consider optimization problem properties (
{ Points X1; X2 2 B2n are called k-nearly, if they di er in value k coordinate, k = 1; : : : ; n. { Set Ok(X), k = 0; : : : ; n, of all points B2n, k-nearly to the point X, is called k-th level of point X. { Point X 2 B2n is called k-nearly to the set A B2n, if A T Ok(X) 6= ; and 8l = 0; : : : ; k 1 : A S Ol(X) = ;. { Point X 2 B2n, for which f (X ) < f (X); 8X 2 O1(X ), is called local minimum of a pseudo-Boolean function f . { A pseudo-Boolean function having only one local minimum is called unimodal function on B2n. { Unimodal function f is called monotone on B2n, if 8Xk 2 Ok(X ); k = 1; : : : ; n: f (Xk 1) f (Xk), 8Xk 1 2 Ok 1(X ) T O1(Xk), and strictly monotone, if this condition is satis ed with the strict inequality sign. { A set of points W (X0; Xl) = fX0; X1; : : : ; Xlg B2n is called path between points X0 and Xl, if 8i = 1; : : : ; l point Xi is nearly to Xi 1. { Path W (X0; Xl) B2n between k-nearly points X0 and Xl is called shortest, if l = k. { 8X; Y 2 B2n combination of all shortest paths W (X; Y ) is called subcube B2n and de ne as K(X; Y ).
Let us consider the basic properties of the set of feasible solutions of the conditional pseudo-Boolean optimization problem. There is a problem of the following form:
{ Point Y 2 S is a boundary point of the set S, if there are X 2 O1(Y ), for which X 2= S. { Point Y 2 Oi(X0) T S is called limiting point of the set S with base point
X0 2 S, if 8X 2 O1(Y ) T Oi+1(X0) condition X 2= S is ful lled.
{ The constraint de ning the subarea of the space of Boolean variables are
called active if the optimal solution of the conditional optimization
problem (
One of the properties of the set of feasible solutions is as follows:
Property 1. If the objective function is a strictly monotonic unimodal function
and the constraint is active, then the optimal solution of problem (
X2B2n where Aj (Y ) =
yi:
Let us consider a separate restriction in the optimization problem (
1; for some cj 2 K ; j = f1; 2; :::; jK jg;
Function Aj (Y ) is monotone decreasing from the point Y 1 = (1; 1; : : : ; 1).
The limiting points of the feasible domain are points Yk 2 On 1(Y 1) (either, which is the same thing, Yk 2 O1(Y 0)), and such that Yk di er from Y 0 = (0; 0; : : : ; 0) by the value of the k-th component, for which kj = 1.
The set of feasible solutions is the combination of the subcubes formed by the limiting points of the feasible space and the point Y 1:
Now let us move on to the entire system of constraints
Aj (Y )
1; for all j = 1; 2; : : : ; jK j: This system will be satis ed by points belonging to the set jK j \
[ j=1 k: kj=1
K(Ykj ; Y 1); which, in the nal analysis, is the union of a nite number of subcubes. The limiting points of the feasible space can be at completely di erent levels of the point Y 1. And their number, in the worst case, can reach the value Cn[n=2] that is the average power level.
Next, let us consider the objective function
C(Y ) = X (1
yi) for some \basic" observation a 2 K+. Or it can be written as
jK+j n C(Y ) = X Y(1
The function C(X) increases monotonically from the point Y 1 = (1; 1; :::; 1), taking the value 1 in it, which corresponds to the covering of the \basic" observation a. The largest value, equal to jK+j, the function C(X) takes the value Y 0 = (0; 0; :::; 0) at a point.
Let us suppose that the observation b 2 K+ closest to observation a di ers in the value of the s component.
At all points Y 2 Ok(Y 1), k = 0; 1; :::; s 1, the value of the objective function are the same and equal to 1. The presence of such a set of constancy complicates the work of optimization algorithms starting to search from a feasible point Y 1 and leading it along nearly points, since the calculation of the objective function in a nearly system consisting of nearly points does not give an information on the best direction of the search.
In solving practical problems of large dimensions this set of constancy can be such that most of the points of the feasible space belong to it. This complicates or makes the operation of such algorithms as a genetic algorithm, a local search with a multistart impossible.
Another consequence of the sets of constancy presence of the objective function is that the optimal solution is not only a point belonging to a subset of limiting points of an feasible space, but it can be an integer set of points representing a set of constancy of the objective function. The following statement is true.
Proposition 1. The limiting points of the feasible space of problem (
The proof follows from the concepts of the limiting point and the prime pattern.
It should be noted that the found prime pattern will not necessarily be a strong pattern. This property is garanteed only for the optimal solution of the problem.
Proposition 2. The optimal solution of problem (
Thus, applying approximate optimization algorithms, it can be con rmed that the found pattern will be prime, but it will not necessarily be strong. If the exact optimization algorithm will be used, then found pattern will be a strong prime pattern. 6
The optimization model is determined, rst of all, by the way in which the variables that de ne the alternatives of the optimization problem are introduced. In the optimization model discussed above, the alternatives, that is, the patterns, are determined by including or not including in the pattern the conditions that are satis ed in some basic observation. Let us consider an alternative way of specifying the pattern.
Let us introduce the binary variable
To ensure that the resulting pattern is encompassing, let us introduce into it all the literals available for all positive observations that this pattern covers, that is, those literals for which the condition is true: zb = 8 1; if observation b 2 K+ < is covered by P a; : 0; otherwise.
Y jbi aij) = 1:
Now let us formulate the problem of nding the maximum pattern as the maximization of the coverage of positive observations under the condition that the coverage of negative observations is in admissible: jbi aij)
Having solved this optimization problem, we will de ne a set of positive observations covered by the desired pattern. The pattern itself can be determined using the characteristic variables Y = (y1; y2; :::; yn): yi =
Y jbi aij) ; i = 1; :::; n:
In this formulation of the optimization problem, the objective function is
strictly monotonic, and there are no sets of constancy of the objective function.
Proposition 3. In the problem (
Proof. Let us take a point Zk 2 Ok(Z0), where Z0 = (z1; :::; zm+ ). For any point Zk+1 2 O1(Zk) T Ok+1(Z0), Cov(Tk) Cov(Tk+1) is ful lled, where Tk and Tk+1 are terms, corresponding to the points Zk and Zk+1 respectively. If Zk is an limiting point of an feasible set, then any point of Zk+1 2 O1(Zk) T Ok+1(Z0) is not permissible, and the term Tk+1 is not a pattern, consequently, the term Tk is a strong pattern (according to the concept of a strong regularity).
In turn, if the point Zk is not an limiting point then there is an admissible point of Zk+1 2 O1(Zk) T Ok+1(Z0) and the corresponding term Tk+1, which is a pattern with a large covering Cov(Tk+1) Cov(Tk), so the term Tk is not strong pattern. 7
The results of experimental studies conducted on the problem of predicting complications of myocardial infarction are presented in [4]. The sample consists of 1700 observations (patients), each of which is described by 112 di erent types of symptoms. According to the input criteria, it is required to make a prediction about the onset of four complications of the disease: ventricular brillation (VF), auricular brillation (AF), pulmonary edema (PE), cardiac rupture (CR). 85% of sample observations were used for training, the rest { for control. The search for patterns was implemented with the help of two optimization models: the search for the maximum prime patterns (model 1) and the search for strong spanned patterns (model 2).
The optimization problems were solved using the algorithms of conditional pseudo-Boolean optimization described in [1].
Table 1 presents comparative results for the average degree of obtained patterns (the number of literals in the term) and the accuracy of recognition of control observations. As can be seen from the results, the use of strong spanned patterns makes it possible to obtain classi ers with a better generalizing ability.
Degree Precision Degree Precision The paper examines the problem of searching for informative patterns by means of formalizing of this search in the form of a conditional pseudo-Boolean optimization problem. The analysis of the properties of the constructed optimization model is implemented and a new alternative model is proposed for optimization, designed to search for strong spanned patterns.