# Computational Complexity and ILP Models for Pattern Problems in the Logical Analysis of Data
###### Abstract  
Logical Analysis of Data is a procedure aimed at identifying relevant features in data sets with both positive and negative samples. The goal is to build Boolean formulas, represented by strings over {0,1,-} called _patterns_, which can be used to classify new samples as positive or negative. Since a data set can be explained in alternative ways, many computational problems arise related to the choice of a particular set of patterns. In this paper we study the computational complexity of several of these pattern problems (showing that they are, in general, computationally hard) and we propose some integer programming models that appear to be effective. We describe an ILP model for finding the minimum-size set of patterns explaining a given set of samples and another one for the problem of determining whether two sets of patterns are equivalent, i.e., they explain exactly the same samples. We base our first model on a polynomial procedure that computes all patterns compatible with a given set of samples. Computational experiments substantiate the effectiveness of our models on fairly large instances. Finally, we conjecture that the existence of an effective ILP model for finding a minimum-size set of patterns equivalent to a given set of patterns is unlikely, due to the problem being NP-hard and co-NP-hard at the same time. logical analysis of Data; pattern problems; data mining; computational complexity; integer linear programming models +
Footnote †: journal:  
0000-0001-4010-4010]C. Lancia  
0000-0001-4010-4010-4010]P. Lancia  
0000-0001-4010-4010-4010-4010-4010-4010-4010-4010  
The Logical Analysis of Data has the objective of discovering a set of simple Boolean formulas (or \"rules\") that can be used to classify new binary vectors \((b_{1},\ldots,b_{n})\). Each rule describes what the value of some bits must be for a vector to be classified as positive or negative. For instance, a \"positive rule\" could be  
\[(b_{2}=1)\land(b_{5}=0)\land(b_{9}=0)\]  
meaning that any vector with a 1 in the 2 nd component, and a 0 in the 5 th and 9 th component is classified as positive. Similarly, there can be some \"negative rules\" which specify which vectors should be classified as negative. A rule such as the above can be conveniently represented by a _pattern_, which is a string over the alphabet \(\{0,1,-\}\). The characters 0 and 1 in the pattern specify which positions must be matched exactly by a binary vector to satisfy the rule, while the character - is a wildcard that can be indifferently matched by either 0 or 1. In particular, if \(n=10\) the pattern corresponding to the above rule would be  
-1--0---0-  
If \(r\) is a rule and \(p\) is the pattern corresponding to \(r\), then a binary vector \(b\) satisfies the rule if and only if  
\[\bigwedge_{k:p_{k}\in\{0,1\}}(b_{k}=p_{k})\]  
We say that the pattern \(p\)_covers_ all vectors \(b\) for which the above holds. In view of the equivalence of rules and patterns, we can talk of positive/negative patterns in place of positive/negative rules. The objective of LAD is to infer positive and negative patterns from the data in such a way that (i) each positive row is covered by at least one of the positive patterns, while no negative row is and (ii) each negative row is covered by at least one of the negative patterns, while no positive row is. This approach has been successfully applied to many contexts in both bioinformatics and biomedicine [8]. Since there might be many alternative sets of patterns explaining a given instance of LAD, one has to introduce a suitable criterion for choosing a specific solution. In particular, an _Okkam's razor_ strategy would suggest seeking the simplest possible solutions, i.e., the sets with a minimum number of patterns. Finding a min-size set of patterns which cover a given set of vectors is called the _Pattern Cover Minimality_ problem.