In pattern mining, one of the most important problems is ghting exponential explosion of the set of patterns. A typical solution is generating only a part of all patterns satisfying some criteria. The most well-known criterion is support of a pattern, which has the monotonicity property allowing one to generate only frequent (highly supported) patterns. Many other useful criteria are not monotonic, which makes it di cult to generate best patterns e ciently. In this paper we introduce the notion of \generalized monotonicity" and Sofia algorithm that allow to generate top patterns in polynomial time modulo basic operations, e.g., measure computation, for criteria that are not monotonic. This approach is applicable not only to itemsets, but to complex descriptions such as sequences, graphs, numbers or interval tuples, etc. In this paper we consider stability and D-measures which are not monotonic. In the experiments, we compute top best patterns w.r.t. these measures and obtain very promising results.
To solve the problem of exponential explosion of patterns valid in a dataset
many kinds of interestingness measures were proposed [
Due to the increasing importance of pattern mining, e cient approaches of
nding best patterns are appearing. In [
In this paper we introduce a new algorithm Sofia (So a, for Searching for
Optimal Formal Intents Algorithm) for extracting top best patterns of di erent
kinds, i.e., itemsets, string, graph patterns, etc. Sofia algorithm is applicable to a
class of measures, including classical monotonic measures, stability, d-freeness [
FCA is a formalism convenient for describing models of itemset mining and
knowledge discovery [
Let us denote the derivative operators of the Galois connection between 2G
and D by ( ) (see [
For real datasets, the number of patterns can be large. In order to reduce
the most interesting concepts di erent measures can be used. In this paper we
rely on stability [
The approach proposed in this paper is based on projections introduced for
reducing complexity of computing pattern lattices [
An o-projected pattern structure (projected pattern structure for simplicity)
((G; (D; u); )) is a pattern structure (P) = (G; (D ; u ); ), where D =
(D) = fd 2 D j 9d~ 2 D : (d~) = dg and 8x; y 2 D; x u y := (x u y) [
Our algorithm is based on this order on projections. The simpler a projection is, the less patterns we can nd in (P), and the less computational e orts one should take. Thus, we compute a set of patterns for a simpler projection, then we remove unpromising patterns and extend our pattern structure and the found patterns to a more detailed projection. This allows to reduce the size of patterns within a simpler projection in order to reduce the computational complexity of more detailed projection. 3 3.1
Our algorithm is based on the projection monotonicity, a new idea introduced
in this paper. Many interestingness measures for patterns, e.g., stability, are not
monotonic w.r.t. subsumption order on patterns, i.e., given patterns X and Y
such that X v Y , and a nonmonotonic measure M, one does not necessarily have
M(X) M(Y ). For instance, support is a monotonic measure w.r.t. pattern
order and it allows for e cient generation of patterns with support higher than
a threshold [
De nition 1. Given a pattern structure P and a projection , a measure M is called monotonic w.r.t. the projection , if (8p 2 (P))(8q 2 P; (q) = p)M (p)
M(q); (1) where M (p) is the measure M of pattern p computed in (P).
Here, for any pattern p of a projected pattern structure we check that a preimage q of p for , e.g. p = (q), has a measure smaller than the measure of p. It should be noticed that a measure M for a pattern p can yield di erent values if M is computed in P or in (P). Thus we use the notation M for the measure M computed in (P).
An important example is given by binary data or formal contexts (G; M; I). In this case, a projection m corresponds to the removal of an attribute m 2 M , i.e., m(B) = B \ (M n fmg) for any B M . So De nition 1 means that the interestingness of an itemset p w.r.t. a measure M computed in (G; M n fmg; I n G fmg) should be higher than the interestingness of the itemsets p and p [ fmg (the preimages of p for m) w.r.t. the measure M computed in (G; M; I). If the value of a measure for a pattern does not depend on a projection this de nition is related to a classical monotonic measure. Indeed, because of contractivity of ( (p) v p), for any monotonic measure one has M( (p)) M(p).
Thus, given a measure M monotonic w.r.t. a projection , if p is a pattern such that M (p) < , then M(q) < for any preimage q of p for . Hence, if, given a pattern p of (P), one can nd all patterns q of P such that (q) = p, it is possible to nd the patterns of (P) and then to lter them w.r.t. M and a threshold, and nally to compute the preimages of ltered patterns. 3.2
However, given just one projection, it can be hard to e ciently discover the patterns, because the projection is either hard to compute or the number of unpromising patterns that can be pruned is not high. Hence we introduce a chain of projections 0 < 1 < < k = 1, where the whole pattern lattice for 0(P) can be easily computed and 1 is the identity projection, i.e., (8x)1(x) = x. For example, to nd frequent itemsets, we typically search for small itemsets and, then, extend them to larger ones. It corresponds to extension to a more detailed projection.
Let us discuss what is a chain of projections in the case of a binary context K = (G; M; I) with M = fm1; ; mN g. It can be seen that any subcontext Ks = (G; N; I \ G N ), where N M , corresponds to a projection such that (B M ) = B \ N . If we put Mi = fm1; ; mig, then we can consider a chain of projections corresponding to the subset of attributes M1; M2; ; M . The corresponding projections are properly ordered. Now we de ne the projection monotonicity of M w.r.t. a chain of projections.
De nition 2. Given a pattern structure P and a chain of projections 0 < 1 < < k = 1, a measure M is called monotonic w.r.t. the chain of projections if M is monotonic w.r.t. all i for 0 i k. 3.3
Given a measure monotonic w.r.t. a chain of projections, if we are able to nd all preimages of any element in the xed set of i that belong to a xed set of i+1, then we can nd all patterns of P with a value of M higher than a given threshold . We call this algorithm j-Sofia and its pseudocode is given in Fig. 1. In lines 11-12 we nd all patterns for 0(P) satisfying the constraint that a value of M is higher than a threshold. Then in lines 13-15 we iteratively extend projections from smaller to bigger ones. The extension is done by constructing the set Pi of preimages of the set Pi 1 (lines 2-5) and then by removing the patterns that do not satisfy the constraint from the set Pi (lines 6-9).
The algorithm is sound and complete, because rst, when we compute the set of preimages of a pattern p, the pattern p is a preimage of itself ( (p) = p) and second, if we remove a pattern p from the set P, then the value M(p) < and, hence, the measure value of any preimage of p is less than by the projection chain monotonicity of M.
The worst-case time complexity of j-Sofia algorithm is
T(j-Sofia) = T(F indP atterns( 0))+ + k 0m<iaxkjPij (T(P reimages) + T(M)); (2) where T(X) is time for computing operation X. Since projection 0 can be chosen to be very simple, in a typical case the complexity of F indP atterns( ; 0) can be low or even constant. The complexities of P reimages and M depend on the Data: A pattern structure P, a chain of projections = f 0; 1; ; kg, a measure M monotonic for the chain , and a threshold for M. 1 Function ExtendProjection(i, , Pi 1)
Data: i is the projection number to which we should extend (0 < i k), is a threshold value for M, and Pi 1 is the set of patterns for the projection i 1.
Result: The set Pi of all patterns with the value of measure M higher than the threshold for i. 2 Pi ;; 3 /* Put all preimages in i(P) for any pattern p 4 foreach p 2 Pi 1 do 5 Pi Pi [ Preimages(i,p) 6 /* Filter patterns in Pi to have a value of M higher than 7 foreach p 2 Pi do 8 if M i (p) then 9 Pi Pi n fpg 10 Function Algorithm j-Sofia
Result: The set P of all patterns with a value of M higher than the threshold for P. 11 /* Find all patterns in 0(P) with a value of M higher than 12 P FindPatterns( ; 0); 13 /* Run through out the chain and find the result patterns 14 foreach 0 < i k do 15 P ExtendProjection(i; ; P); */ */ */ */ Algorithm 1: The j-Sofia algorithm for nding patterns in P with a value of a measure M higher than a threshold . measure in use and on the instantiation of the algorithm. In many cases 0m<iaxkjPij can be exponential in the size of the input, because the number of patterns can be exponential. It can be a di cult task to de ne the threshold a priori such that the maximal cardinality of Pi is not higher than a given number. Thus, we introduce Sofia algorithm, which automatically adjusts threshold ensuring that 0m<iaxkjPij < L. Here L can be considered as a constraint on the memory used by the algorithm. It can be seen from Eq. (2) that Sofia algorithm has polynomial time complexity if M and P reimages are polynomial. In the next subsection we consider an important partial case where Sofia has polynomial complexity. 3.4
In this subsection we have a formal context K = (G; M; I) with M = fm1; ; mN g and we want to nd itemsets X M interesting w.r.t. a measure M. First, we instantiate a chain of projections. In the case of binary data it corresponds to the chain of contexts Ki = (G; Mi; I \ G Mi), where Mi = fm1; ; mig, i.e., Mi contains the rst i attributes from M . It means that i(X) = X \ Mi.
Then we de ne how the function P reimages works for this kind of chains of projections. A set X Mi 1 has two preimages in the powerset of Mi, i.e. X and X [ fmig. Hence, the computation complexity of nding preimages for any itemset X is constant. For the projection 0 corresponding to the context (G; ;; ;) there is only one itemset ;. Thus, the worst case complexity for j-Sofia algorithm is
T(j-Sofiabinary) = jM j 0m<iaxNjPij T(M): (3) In particular, the complexity of Sofia for binary data is jM j L T(M), i.e., it is polynomial modulo complexity of the measure. 3.5
Closed frequent itemsets are widely used as a condensed representation of all
frequent itemsets since [
A projection of P induces a projection C of PC , given by C (X G) = (X ) , where diamond is computed in P. The function C is a projection because of the properties of ( ) operators and mappings. We use this approach for representing closed patterns in our computer experiments. 4
Datasets L = 103DecreLasi=ng10o4rder L = 105 L = 103IncreLas=ing10o4rder L = 105 L = 103 RanLdo=m1o0r4der L = 105 t # t # t # t # t # t # t # t # t # Mushrooms < 1 0.99 181 2 0.87 49 39 0.89 7 1 0.99 181 6 0.87 49 38 0.89 7 < 1 0.99 181 3 0.87 49 117 0.89 7 Chess < 1 0.997 97 2 0.92 69 17 0.94 46 1 0.88 144 4 0.24 84 38 0.68 49 < 1 0.65 103 2 0.92 69 19 0.94 46 Plants 1 1 147 14 0.96 70 146 0.94 37 3 1 147 29 0.96 70 263 0.94 37 1 1 147 14 0.96 70 143 0.94 37 Cars < 1 0.94 19 < 1 0.61 0 < 1 0.06 0 < 1 0.86 22 < 1 0.61 0 < 1 0.06 0 < 1 0.94 19 < 1 0.6 0 < 1 0.06 0
In the experiment we show how our algorithm in conjunction with stability
estimate behaves on di erent datasets from UCI repository [
There are two obvious orders for adding an attribute in Sofia algorithm: the decreasing and increasing orders of attribute support. We consider also a random order of attributes allowing one to discard any bias in the order of attributes. Another point about our algorithm is that it does not ensure nding L-top best patterns. It nds no more than L patterns allowing to compute the result in polynomial time by adjusting the threshold of stable patterns.
Thus, in our experiment we have checked which order is better for the attributes and how many patterns we can nd for a given L. Table 1 shows the results and is divided into three parts corresponding to the order in which attributes were added to the context. Then all parts are divided into three subparts corresponding to a value of L 2 f103; 104; 105g. Hence, we have 9 experiments and for every experiment we measure the computation time in seconds (t), the ratio of found patterns to L (#) and the nal corresponding to the found patterns. For example, in the Mushrooms dataset, adding the attributes in the decreasing order of their support for L = 10000, the total computational time is equal to 2 seconds; the algorithm found around 0:87 L = 8700 patterns representing all patterns with stability higher than 49.
In Table 1 we can see that our algorithm is e cient in the big and small datasets however the computational time and the number of found patterns depend on the order of attribute addition, i.e., on a projection chain. We can see that the computational time and the number of patterns for increasing order are never better than those of decreasing order and random order. Decreasing order and random order have nearly the same behavior, but in some cases the random order gives slightly worse results than the decreasing order. In fact, in the case of decreasing order we generate more patterns on earlier iterations of our algorithm, i.e., we have more chances to nd an unstable pattern and lter it as earlier as possible. Since concepts are ltered earlier, we have more space for the computation, thus having smaller threshold and larger number of found patterns, and we should process less patterns, thus saving the computation time. We see that for the decreasing order of attributes the number of found patterns is always around or higher than 0:9 L, i.e., we nd nearly as many patterns as the requested limit L. 1 https://archive.ics.uci.edu/ml/datasets/Mushroom 2 https://archive.ics.uci.edu/ml/datasets/Car+Evaluation 3 https://archive.ics.uci.edu/ml/datasets/Chess+(King-Rook+vs.
+King-Knight) 4 https://archive.ics.uci.edu/ml/datasets/Mushroom
In this paper we have introduced a new kind of interestingness measures of patterns monotonic w.r.t. a chain of projections. Based on this monotonicity we introduce a new algorithm called Sofia that nds the top best patterns for such kind of measures in polynomial time. Our experiments justi ed the e ciency of our algorithms. Many directions for future work are promising. First, we should work on adaptation of Sofia for nding di erent kinds of patterns, e.g., itemset generators, sequences, graphs. Second, we should study the best chains of projections and the best order of attributes for Sofia algorithm. Finally, the study of new measures that can be used with Sofia is also very important.