Constraint Programming for Mining Borders of Frequent Itemsets

1 Introduction

Data mining is the art of discovering knowledge from databases. It includes the discovering of frequent itemsets [Agrawal et al., 1994; Han et al., 2000], association rules [Agrawal et al., 1994; Liu et al., 1999], rare itemsets [Szathmary et al., 2007; Adda et al., 2007], sequence patterns [Agrawal and Srikant, 1995], emerging patterns [Dong and Li, 1999], and many other tasks. For many data mining problems, the frequency represents an important metric. Given a frequency threshold s over a transaction dataset, frequent itemsets are those present in at least s transactions. Itemsets present in less than s transactions are called infrequent (or rare). The number of frequent/infrequent itemsets can be huge, making it hard even to print the result. Hence, we often reduce the problem of mining frequent or infrequent itemsets to the problem of mining the borders. The positive border is the set of frequent itemsets with only infrequent supersets, i.e. Maximal Frequent Itemsets (MFIs). The negative border is the set of infrequent itemsets with only frequent subsets, i.e. Minimal Infrequent Itemsets (MIIs). The subsets of the MFIs and the supersets of the MIIs represent the frequent and infrequent itemsets, respectively.

Several techniques have been introduced for mining MFIs [Burdick et al., 2001; Gouda and Zaki, 2001; Uno et al.,

2004], or MIIs [Szathmary et al., 2007; Haglin and Manning, 2007; Szathmary et al., 2012]. Despite an obvious duality between MFIs and MIIs, very few papers propose a single framework for mining both MFIs and MIIs. In [Mannila and Toivonen, 1997; Boros et al., 2003; Nourine and Petit, 2012], inferring MFIs from the set of MIIs and vice versa (or also called the dualization) is reduced to computing the minimal transversals of a hypergraph [Berge, 1984]. In fact, MIIs correspond to the minimal transversals of the hypergraph constructed by the complements of the set of MFIs.

In a recent line of work, researchers have taken advantage of the flexibility of constraint programming to model various data mining problems [De Raedt et al., 2008; Khiari et al., 2010; Lazaar et al., 2016; Schaus et al., 2017; Bessiere et al., 2018]. In terms of CPU time, constraint programming-based methods have not yet competed with ad hoc algorithms. However, their flexibility allows the modeling of complex user queries without revising the solving process.

In this paper we propose a generic parameterized model allowing the user to decide which border to mine (i.e., MFIs or MIIs). For this model we need to define two new global constraints: (1) FREQUENTSUBS for mining itemsets having only frequent subsets, and (2) INFREQUENTSUPERS for mining itemsets having only infrequent supersets. We provide a polynomial domain consistency propagator for each of these two constraints. We then address the issue of mining borders in the presence of other constraints. As noticed in [Bonchi and Lucchese, 2004], mining borders under additional constraints can lead to the loss of solutions. This can happen with maximal/minimal borders, but also with closed itemsets or generator itemsets. We prove that it is coNP-hard to find maximal/minimal itemsets among those satisfying a set of additional constraints. This implies that there does not exist any CSP representing the problem of finding maximal/minimal itemsets under additional constraints, unless coNP ⊆ NP. This is an a posteriori justification of the "multi-shot" approaches, such as the one presented in [Negrevergne et al., 2013].

The paper is organized as follows. Section 2 gives some background material. In Section 3 we give a generic model for mining MFIs or MIIs. We define the new global constraints FREQUENTSUBS and INFREQUENTSUPERS and we present their propagators. Section 4 analyzes the problem of mining constrained MFIs or MIIs. We present some empirical results in Section 5. Finally, we conclude in Section 6.

2 Background

2.1 Itemsets

Let I = {1, . . . , n} be a set of n item indices and T = {1, . . . ,m} a set of m transaction indices. An itemset P is a non-empty subset of I. D = {t1, . . . , tm} is the transactional dataset, where for all i ∈ T , ti is an itemset. The cover of an itemset P, denoted by cover(P), is the set of transactions containing P. The frequency of an itemset P is the cardinality of its cover i.e. freq(P) = |cover(P)|. Let s be some given constant called a support threshold. The itemset P is frequent if freq(P) ≥ s. P is infrequent (or rare) if freq(P) < s. We now define the two main notions used in this paper.

Definition 1 (Maximal Frequent Itemset (MFI)) An itemset is an MFI if it is frequent and all its proper supersets are infrequent.

Definition 2 (Minimal Infrequent Itemset (MII)) An itemset is an MII if it is infrequent and all its proper subsets are frequent.

In [Mannila and Toivonen, 1997] MFIs and MIIs are referred to as positive and negative border respectively. MFIs are closed and MIIs are a generator itemset. We define closed and generator itemsets.

Definition 3 (Closed itemset [Pasquier et al., 1999]) An

itemset P is closed if and only if there does not exist any itemset Q ⊋ P such that freq(Q) = freq(P).

Definition 4 (Generator [Bastide et al., 2000]) A generator is an itemset P such that there does not exist any itemset Q ⊊ P such that freq(Q) = freq(P).

Example 2.1 With s = 3, the dataset in Table 1 has MFIs = {ABE, AC, BCE} and MIIs = {ABC, ACE, D}.

2.2 Constraint Programming (CP)

A CP model specifies a set of variables X = {x1, . . . , xn}, a set of domains dom = {dom(x1), . . . , dom(xn)}, where dom(xi) is the finite set of possible values for xi, and a set of constraints C on X. A constraint cj ∈ C is a relation that specifies the allowed combinations of values for its variables var(cj). An assignment on a set Y ⊆ X of variables is a mapping from variables in Y to values, and a valid assignment is an assignment where all values belong to the domain of their variable. A solution is an assignment on X satisfying all constraints. Constraint programming is the art of writing problems as CP models and solving them by finding solutions. Constraint solvers typically use backtracking search to explore the search space of partial assignments. At each assignment, constraint propagation algorithms (aka, propagators) prune the search space by enforcing local consistency properties such as domain consistency.

A constraint c on var(c) is domain consistent (DC) if and only if, for every xi ∈ var(c) and every dj ∈ dom(xi), there is a valid assignment satisfying c such that xi = dj. Global constraints are constraints defined by a relation on any number of variables. The constraint AllDifferent, specifying that all its variables must take different values is an example of global constraint (see [Rossi et al., 2006]).

Example 2.2 Consider the following instance of a CP model. X = {x1, x2, x3}, dom(x1) = {0, 2}, dom(x2) = {0, 2, 4}, dom(x3) = {1, 2, 3, 4}, and C = {x1 ≥ x2, x1 + x2 = x3}. Value 4 for x2 will be removed by DC because of constraint x1 ≥ x2. Values 1 and 3 for x3 will be removed by DC because of constraint x1 + x2 = x3. This CP model admits the two solutions (x1 = 2, x2 = 0, x3 = 2) and (x1 = 2, x2 = 2, x3 = 4).

3 AGeneric CPModel for Mining Borders

We present a CP model, MODELD,s,b, for mining MFIs or MIIs. MODELD,s,b uses a vector x of n Boolean variables, where xi represents the presence of the item i in the itemset. We will use the following notations:

• x-1 (0) = {i ∈ I | dom(xi) = {0}}

where (1) is a global constraint that holds if and only if the itemset x-1 (1) has only frequent subsets w.r.t s, (2) is a global constraint that holds if and only if the itemset x-1 (1) has only infrequent supersets w.r.t s, and the Boolean parameter b reifies the global constraint FREQUENT (3). FREQUENTD,s holds if and only if x-1 (1) is frequent w.r.t s. We prove that MODELD,s,b is a correct model for mining MFIs or MIIs.

Theorem 1 The set of solutions to MODELD,s,b corresponds to the set of MFIs if b = true, the set of MIIs otherwise.

Proof. We first prove that MFIs and MIIs always satisfy constraints (1) and (2). All supersets of an MFI are infrequent, thus satisfying (2). Because an MFI is frequent, all its proper subsets are frequent, thus satisfying (1). An MII has only frequent subsets, thus satisfying (1). Because an MII is infrequent, it has only infrequent supersets, thus satisfying (2). Hence, all MFIs and all MIIs satisfy constraints (1) and (2).

We now prove that a solution of MODELD,s,b, can only be an MFI or an MII depending on the value of b. A solution of MODELD,s,b can only be frequent (i.e., b = true) or infrequent (i.e., b = false). If it is frequent then it is an MFI (see Definition 1). Otherwise it is an MII (see Definition 2). □

Example 3.1 The lattice in Figure 1 displays the set of itemsets satisfying the constraints FREQUENTSUBS and INFREQUENTSUPERS on the dataset of Table 1 with s = 3. The intersection between both sets is the set MFIs ∪MIIs.

We can then use MODELD,s,b to mine either MFIs or MIIs by simply setting b to true or false. We now define the global constraints FREQUENTSUBS and INFREQUENTSUPERS and we propose propagators.

3.1 The Global Constraint FREQUENTSUBS

We present the new global constraint FREQUENTSUBS used to mine itemsets that have only frequent subsets.

Definition 5 (FREQUENTSUBS) Let x be a vector of Boolean variables, s a support threshold and D a dataset. The global constraint FREQUENTSUBSD,s(x) holds if and only if ∀p ⊂ x-1 (1), freq(p) ≥ s.

Algorithm. The propagator for the global constraint FREQUENTSUBS is presented in Algorithm 1. Algorithm 1 takes as input the variables x and the support threshold s. Algorithm 1 starts by computing the cover of the itemset x-1 (1) and stores it in cover (line 4). Then, for each item j ∈ x-1 (1), Algorithm 1 computes the cover of the subset x-1 (1) \ {j}, and stores it in cov[j] (line 6). If x-1 (1) \ {j} is infrequent then x-1 (1) is not a solution and we return a failure (line 7). Algorithm 1 must then remove items i that cannot belong to a solution containing x-1 (1). To do that, we first test if the itemset x-1 (1) is infrequent (line 8). If so, we remove 1 from dom(xi) for all i ∈ x-1 (∗) (lines 9-10) because the itemset x-1 (1) ∪ {i} has an infrequent subset (x-1 (1)) for every i in x-1 (∗). Otherwise, for every item i in x-1 (∗) we test if the itemset x-1 (1) ∪ {i} is infrequent (line 12). If so, it could have infrequent subsets. Thus, for every item j in x-1 (1), we test if the size of the cover of x-1 (1)∪{i}\{j} (i.e., cov[j]∩cover(i)) is less than s (line 14). If so, we remove i from the possible items, that is, we remove 1 from dom(xi) and break the loop (line 15).

Theorem 2 The propagator in Algorithm 1 enforces domain consistency on the constraint FREQUENTSUBS.

Algorithm 1: Propagator for FREQUENTSUBS

Proof. We first prove that if FREQUENTSUBS admits a solution, x-1 (1) is necessarily one of them. Suppose there is a solution and x-1 (1) is not one of them. This means that there exists a superset of x-1 (1) which has all its subsets frequent. x-1 (1) is one of these subsets. Thus, all subsets of x-1 (1) are frequent and x-1 (1) is solution too, which contradicts the assumption. We now prove that Algorithm 1 returns failure if and only if FREQUENTSUBS does not admit any solution. We know that FREQUENTSUBS has no solution if and only if x-1 (1) is not solution. x-1 (1) is not solution if and only if it has an infrequent subset x-1 (1) \ {j} for some j in x-1 (1). In such a case the test in line 7 is true and failure is returned. If FREQUENTSUBS admits solutions, x-1 (1) is a support for xi = 0, for all i ∈ x-1 (∗). As a result, Algorithm 1 does not need to check consistency of value 0 for any variable.

We now prove that Algorithm 1 prunes value 1 from dom(xi) exactly when i cannot belong to a solution containing x-1 (1). Suppose value 1 of xi is pruned by Algorithm 1. This means that the test in line 8 (or line 14) was true, that is, there exists a subset of x-1 (1) ∪ {i} which is infrequent. Thus, by definition, x-1 (1) ∪ {i} does not belong to any solution. Suppose now that value 1 of xi is not pruned. From lines 8 and 14, we deduce that there does not exist any infrequent subset of x-1 (1)∪{i}. Thus x-1 (1)∪{i} is a solution and value 1 of xi is domain consistent. □

Theorem 3 Given a transaction dataset D of n items and m transactions, Algorithm 1 has an O(n2 ×m) time complexity.

Proof. Computing the size of the cover of an itemset is in O(n×m). Line 5 is called at most n times, leading to a time complexity in O(n2 ×m). The time complexity of lines 8-10 is bounded above by n. The test at line 13 is done at most n2 times. The cover x-1 (1) ∪ {i} \ {j} at line 13 is computed in O(m) thanks to the cov data structure. Thus, the time complexity of lines 9-14 is bounded above by n2 ×m. As a result, Algorithm 1 has an O(n2 ×m) time complexity. □

Algorithm 2: Propagator for INFREQUENTSUPERS

1 In: s: support threshold; 2 InOut: x = {x1 . . . xn}: Boolean item variables; 3 begin 4 cover ← cover(x-1 (1) ∪ x-1 (∗)); 5 if |cover| ≥ s then 6 foreach j ∈ x-1 (0) do 7 if |cover ∩ cover(j)| ≥ s then 8 return failure; 9 foreach i ∈ x-1 (∗) do 10 cover2 ← cover(x-1 (1) ∪ x-1 (∗) \ {i}); 11 if |cover2| ≥ s then 12 foreach j ∈ (x-1 (0) ∪ {i}) do 13 if |cover2 ∩ cover(j)| ≥ s then 14 dom(xi) ← dom(xi) \ {0}; break;

3.2 The Global Constraint INFREQUENTSUPERS

We present the new global constraint INFREQUENTSUPERS used to mine itemsets that have only infrequent supersets.

Definition 6 (INFREQUENTSUPERS) Let x be a vector of Boolean variables, s a support threshold and D a dataset. The global constraint INFREQUENTSUPERSD,s(x) holds if and only if ∀p ⊃ x-1 (1), freq(p) < s.

Algorithm. The propagator for the global constraint INFREQUENTSUPERS is presented in Algorithm 2. Algorithm 2 takes as input the variables x and the support threshold s. Algorithm 2 starts by computing cover, the cover of the largest possible itemset, x-1 (1) ∪ x-1 (∗) (line 4). If such an itemset has a frequent superset (line 7) then no itemset containing x-1 (1) can be a solution and we return failure (line 8). Algorithm 2 must then remove value 0 from dom(xi) if the absence of the item i can lead to an itemset that has a frequent superset. To do that, for every free item i (line 9), Algorithm 2 computes cover2, the cover of the largest itemset not containing the item i, i.e. x-1 (1)∪x-1 (∗)\{i} (line 10). If x-1 (1) ∪ x-1 (∗) \ {i} is frequent (line 11), it could have a frequent superset. Thus, for every item j in x-1 (0) ∪ {i} we test whether the itemset x-1 (1) ∪ x-1 (∗) \ {i} ∪ {j} is frequent (line 13). If so, we remove 0 from dom(xi) and break the loop (line 14).

Theorem 4 The propagator in Algorithm 2 enforces domain consistency on the constraint INFREQUENTSUPERS.

Proof. We first prove that if INFREQUENTSUPERS admits a solution, x-1 (1) ∪ x-1 (∗) is necessarily one of them. Suppose there is a solution and x-1 (1) ∪ x-1 (∗) is not one of them. This means that there exists a subset of x-1 (1) ∪ x-1 (∗) which has all its supersets infrequent. x-1 (1) ∪ x-1 (∗) is one of these supersets. Thus, all supersets of x-1 (1) ∪ x-1 (∗) are infrequent and x-1 (1) ∪ x-1 (∗) is solution too, which contradicts the assumption. We now prove that Algorithm 2 returns failure if and only if INFREQUENTSUPERS does not admit any solution. We know that if INFREQUENTSUPERS has solutions, x-1 (1) ∪ x-1 (∗) is one of them. x-1 (1) ∪ x-1 (∗) is not solution if and only if it has a frequent superset. In such a case the test in line 7 is true for some j in x-1 (0) and failure is returned. If INFREQUENTSUPERS has solutions, x-1 (1) ∪ x-1 (∗) is a support for xi = 1, for all i ∈ x-1 (∗). As a result, Algorithm 2 does not need to check consistency of value 1 for any variable.

We now prove that Algorithm 2 prunes 0 from dom(xi) exactly when i belongs to all solutions containing x-1 (1). If the test in line 13 is true this means that with xi = 0 we get itemsets having at least a frequent superset. Hence, 0 must be pruned from dom(xi). Suppose now that the test in line 13 is false for all j. x-1 (1) ∪ x-1 (∗) \ {i} has only infrequent supersets and xi = 0 is domain consistent. □

Theorem 5 Given a transaction dataset D of n items and m transactions, Algorithm 2 has an O(n2 ×m) time complexity.

Proof. Computing the cover of x-1 (1) ∪ x-1 (∗) in line 4 is in O(n × m). The loop in line 6 computes the cover of x-1 (1) ∪ x-1 (∗) ∪ {j} in O(m) using the already computed cover of x-1 (1) ∪ x-1 (∗) (i.e., cover). As a result the worst case time complexity of lines 4-8 is in O(n×m). Similarly, the time complexity of lines 10-14 is bounded above by n ×m. Lines 10-14 are called at most n times, leading to a time complexity in O(n2 × m). □

It is worth noticing the duality between Algorithm 1 and Algorithm 2. Algorithm 1 removes value 1 from dom(xi) if including the item i leads to an itemset having an infrequent subset. Algorithm 2 removes value 0 from dom(xi) if excluding the item i necessarily leads to itemsets having a frequent superset. This duality is not totally obvious at a first glance because Algorithm 1 requires the cov data structure to have its good time complexity whereas Algorithm 2 does not need it. The reason is that Algorithm 1 computes the covers of subsets that we cannot derive from the cover of their supersets whereas Algorithm 2 computes covers of supersets that can be obtained by simple bitwise operation on their subsets.

4 On Constrained Borders

As pointed out in [Bonchi and Lucchese, 2004], constraints can interfere with closedness (or maximality) when they are not monotone. Likewise, constraints can interfere with minimality when they are not anti-monotone. Hence, existing "one-shot" CP approaches can miss solutions because they look for maximal/minimal itemsets that in addition satisfy constraints (see [Lazaar et al., 2016]), whereas we are usually interested in itemsets that are maximal (or minimal) among those satisfying the constraints. In this section we prove that deciding whether a frequent itemset is maximal or closed or minimal among those satisfying the constraints is coNPcomplete. This means that finding maximal/closed/minimal itemsets among those satisfying a set of constraints is coNPhard. It is a proof that it is not possible to solve this problem using a single CSP (unless coNP ⊆ NP). This validates "multi-shot" approaches [Negrevergne et al., 2013].

Theorem 6 Given a dataset D on a set of items I and a set C of user's constraints, deciding whether an itemset is maximal/closed among those satisfying C is coNP-complete.

Proof. Membership. Given an itemset P, a witness to its non maximality/closedness is an itemset P ′ ⊃ P that is frequent, satisfies C, and in the case of closedness has the same frequency as P. Checking that P ′ is frequent and checking that it has the same frequency as P is linear in |D|. Checking that P ′ satisfies C requires the polynomial check of the C constraints. Hence, the "no" answer admits a polynomial certificate, and so deciding maximality or closedness is in coNP.

Completeness. We reduce co3COL, which is coNPcomplete, to the problem of deciding whether an itemset is maximal/closed. We want to decide whether a connected graph G = (V,E) is non colorable with three colors. We build the dataset D on the set I = (a1, . . . , an, b1, . . . , bn, c) of items, where n = |V |. The pair (ai, bi) of items will represent the vertex i in V . D contains the single transaction (1, . . . , 1) and the frequency threshold s is set to |T |/2.

As in all CP models for itemset mining, there is a Boolean variable for each item. The standard semantics is that xp = 1 if and only if the item p is in the itemset returned as solution.

For each edge (i, j) ∈ E, a quaternary constraint c(xai , xbi , xaj , xbj ) is put in the set C of user's constraints. The tuples allowed by c(xai , xbi , xaj , xbj ) are (0000), (0110), (0111), (1001), (1011), (1101), (1110). The assignments (01), (10), and (11) for the pair of variables (xai , xbi ) represent the three colors for vertex i. c(xai , xbi , xaj , xbj ) accepts the tuple (0000) plus the six tuples representing the six combinations of different colors for the pair of vertices (i, j). Hence, by construction, the tuple (0, . . . , 0) is solution, and, as soon as a variable xai or xbi is set to 1, it forces all neighbors in E of vertex i to take another color than the color represented by the assignment of (xai , xbi ). As a result, deciding whether the itemset {c} is maximal/closed among the itemsets satisfying C is equivalent to deciding whether there does not exist any superset of {c} satisfying C, which is equivalent to deciding whether G is non 3-colorable. □

Theorem 7 Given a dataset D on a set of items I and a set C of user's constraints, deciding whether an itemset is minimal/generator among those satisfying C is coNP-complete.

Proof. (Sketch.) Membership is direct adaptation of the proof of membership in Theorem 6: A witness of nonminimality/non-generator of an itemset P is a subset that is infrequent (or has the same frequency in case of generator) and satisfies C, which is polynomial to check. Completeness is the dual of the reduction in Theorem 6. We reduce co3COL to the problem of deciding whether an itemset is minimal/generator. We build the dataset D on the set I = (a1, . . . , an, b1, . . . , bn) of items with the three transactions (1, 0, . . . , 0), (0, . . . , 0, 1) and (1, . . . , 1). The frequency threshold s is set to |T |/2. For each edge in the graph, we use again a quaternary constraint but the tuple (0000) is replaced by the tuple (1111) and the three colors are represented by the assignments (00), (01), and (10) instead of (01), (10), and (11). By construction, the tuple (1, . . . , 1) is solution and deciding whether the itemset (a1, . . . , an, b1, . . . , bn) is minimal/generator among the itemsets satisfying C is equivalent to deciding whether there does not exist any subset of (a1, . . . , an, b1, . . . , bn) satisfying C, which is equivalent to deciding whether G is non 3-colorable. □

Corollary 1 Given a dataset D on a set of items I and a set C of user's constraints, finding an itemset that is maximal/closed/minimal/generator among those satisfying C is coNP-hard.

5 Experiments

We made several experiments to compare our CP model MODELD,s,b to the state of the art approaches.

5.1 Experimental Protocol

The implementation of MODELD,s,b and its constraint propagators were carried out in the Oscar solver using Scala (bitbucket.org/oscarlib/oscar). The code is publicly available at gite.lirmm.fr/belaid/cp4borders. All experiments were conducted on an Intel core i7, 2.2Ghz with a RAM of 8Gb and a timeout of one hour. MODELD,s,b is denoted by CP4MFI (resp. CP4MII) when b = 1, i.e. mining MFIs, (resp. b = 0, mining MIIs). We used the global constraint COVERSIZE to encode the constraint (3) in MODELD,s,b. COVERSIZED(x, p) holds if and only if p = |cover(x-1 (1))| [Schaus et al., 2017]. We enforce frequency by simply adding the constraint p ≥ s and infrequency by adding p < s. The propagator of COVERSIZE enforces DC on the frequency, but it does not on the infrequency. We have assessed the quality of the COVERSIZE encoding of infrequency by comparing to a propagator that enforces DC on the infrequency. We observed that the number of additional nodes explored with the COVERSIZE encoding was marginal and the CPU time was better. We thus use the propagator of COVERSIZE in all our experiments. As an MFI is a closed itemset and an MII is a generator, we enhance propagation by adding, respectively, the global constraints COVERCLOSURE [Schaus et al., 2017] and GENERATOR [Belaid et al., 2019]. After a few preliminary tests, we decided to use smallest item frequency first as variable ordering heuristic and largest value first as value ordering heuristic. We compared CP4MFI to the FPGROWTH [Grahne and Zhu, 2003] specialized algorithm for extracting MFIs (Borgelt's platform: borgelt.net/fpgrowth.html) and CP4MII to WALKY-G [Szathmary et al., 2012] for mining MIIs (CORON platform: coron.loria.fr). We selected several real-sized datasets from the FIMI repository (fimi.ua.ac.be/data). A dataset is characterized by its name, the number of items |I|, the number of transactions |T | and its density ρ.

5.2 Mining Borders

Our first experiment compares CP4MFI to FPGROWTH and CP4MII to WALKY-G for mining MFIs and MIIs. For each approach and each selected instance, Table 2 reports the CPU time and the number of MFIs/MIIs. 1 An instance of a given dataset is characterized by its minimum support s (e.g., Zoo 50 denotes the instance of Zoo with s = 50).

A first observation is that the specialized algorithms FPGROWTH and WALKY-G follow a completely different approach to extract MFIs and MIIs whereas our CP model can T10 = T10I4D100K TO= timeout OOM= out of memory mine a border or the other just by flipping a parameter. When mining MFIs, the main observation that we can draw from Table 2 is that, as expected, the specialized algorithm FPGROWTH performs very well. However, CP4MFI is very competitive too, and even faster on one instance (Chess 160). As for MIIs, CP4MII outperforms WALKY-G in 14 instances out of 26. CP4MII reaches once the timeout of one hour. WALKYG reaches the time out on two instances and an out of memory state on three instances. WALKY-G uses a hash structure for storing frequent generators. Maintaining this data structure can be very expensive, especially on dense datasets. For instance, on the very dense Chess 500, WALKY-G exhausts the 8Gb of memory to store the 50M frequent generators. On the moderately dense Connect 7000, WALKY-G needs to store more than 7.4M frequent generators to find the 165K MIIs in 163.25 seconds. On these two instances, CP4MII returns the whole set of MIIs in only 97.42 and 99.42 seconds, respectively. On sparse datasets, where we have few frequent generators, WALKY-G is very efficient. On the very sparse dataset T10, WALKY-G stores less than 50K frequent generators to extract the 698K MIIs of T10 50 in less than 5 seconds whereas CP4MII needs more than 7 minutes.

1 This number is computed by releasing the timeout.

Table 2: FPGROWTH vs CP4MFI for mining MFI and WALKY-G vs CP4MII for mining MIIs (time in seconds)

5.3 Mining Constrained Borders

In many practical applications, the user asks for itemsets satisfying some additional constraints. We performed experiments that show the strength of our CP approach in taking into account user's constraints. We look for MFIs of minimim size lb and MIIs of maximum size ub. These two queries can easily be expressed in our CP model by adding the cardinality constraints ∑i∈I xi ≥ lb to CP4MFI, and ∑i∈I xi ≤ ub to CP4MII. FPGROWTH includes a filtering step allowing us to specify the minimum size of extracted MFIs. However, WALKY-G does not provide such feature, and extracting MIIs under cardinality constraints is only possible via a post-processing step. Table 3 reports the results. We selected the instances having more than one million MFIs and/or MIIs in Table 2. For each selected instance, we increased lb (resp.

TO= timeout OOM= out of memory

Table 3: FPGROWTH vs CP4MFI for mining constrained MFI and WALKY-G vs CP4MII for mining constrained MIIs (time in seconds)

decreased ub) and we report the CPU time, in seconds, according to the number of solutions.

The main observation on the performance of FPGROWTH for extracting constrained MFIs is that its CPU time is almost constant. For instance, extracting more than 5M or just 10 MFIs on Chess 160 requires almost the same CPU time. This is explained by the fact that the cardinality constraint in FPGROWTH has no pruning power. It is just used as a checker. On the contrary, when lb increases, CP4MFI removes more values thanks to constraint propagation, thus drastically reducing the search space. Take for instance Pumsb 17000. When lb = 22, CP4MFI extracts the 55K MFIs in more than 50 minutes whereas when lb increases to 30, CP4MFI returns the 21 remaining solutions in only 15 seconds. On instances with no solutions, such as Pumsb 17000 with lb = 35, CP4MFI proves the absence of solutions in one second whereas FPGROWTH spends 157.28 seconds.

For WALKY-G, no results are reported because it already has an OOM or TO state before reaching post-processing step. The main observation that we can draw on the behavior of CP4MII is again the strong correlation between the increase of tightness of the cardinality constraint (that is, the decrease of ub) and the drop in CPU time needed to extract the constrained MIIs. The explanation for this good behavior of CP4MII is again the strength of constraint propagation to discard inconsistent values, thus reducing the search space. On Pumsb 17000, when ub decreases from 8 down to 1, CP4MII goes from 45 minutes down to 4.59 seconds to return the set of MIIs (1.3M MIIs for ub = 8 and 2K MIIs for ub = 1).

6 Conclusion

We have presented a CP model for mining MFIs and MIIs. We defined two new global constraints, namely FREQUENTSUBS and INFREQUENTSUPERS, with polynomial complete propagators. We have proved that the problem of MFIs or MIIs with constraints is co-NPhard, ruling out the hope for a single CSP solving this problem. Nevertheless, our CP model is sound when the additional constraints are monotone on MFIs or anti-monotone on MIIs. Experiments showed that the CP approach is competitive with state of the art techniques for mining MFIs or MIIs and even better for mining MFIs or MIIs with additional constraints.