A thorough scrutiny of the literature dedicated to association rule mining highlights that a determined effort focused so far on mining the co-occurrence relations between items, i.e., conjunctive patterns. In this respect, disjunctive patterns presenting knowledge about complementary occurring items were neglected in the literature. Nevertheless, recently a growing number of works is shedding light on their importance for the sake of providing a richer knowledge for users. For this purpose, we propose in this paper a new tool, called GARM, aiming at building a partially ordered structure amongst some particular disjunctive patterns, namely the disjunctive closed ones. Starting from this structure, deriving generalized association rules, i.e., those offering conjunctive, disjunctive and negative connectors between items, becomes straightforward. Our experimental study put the focus on the mining performances as well as the quantitative aspect and proved the utility of the proposed approach.
Association rule mining is a fundamental topic in Data mining [
In this paper, we propose a new tool, called GARM 1, covering the whole process allowing the extraction of generalized association rules. These latter generalize classical rules – positive rules – to offer disjunctive and negative connectors between items,
in addition to the conjunctive one [
Noteworthily, extracting an exact concise representation of frequent patterns in the
first component of the process makes it possible to exactly derive the different supports
of each frequent pattern. This will make us able to compute the exact values of
quality measures. Indeed, it was shown in [
In general, generalized association rules are useful in many applications. In
particular, disjunctive association rules – having disjunction of items either in premise or in
conclusion – were considered for two main purposes: On the one hand, they were used
as an intermediate step for defining some concise representations for frequent patterns
[
Note that we restrict ourselves in this work to disjunctive closed patterns whose smallest seeds, i.e. essential patterns, are frequent with respect to a minimum conjunctive support threshold. This is argued by the fact that we aim at retaining the spirit of association rule mining where this threshold, as well as the confidence-based one, is used to dramatically limit the number of extracted association rules. In addition, the use of a partially ordered structure will make it possible to select representative subsets of rules to be extracted. This nucleus of rules will be of paramount help for avoiding to overwhelm users by highly-sized rule lists.
The remainder of the paper is organized as follows. The next section discusses the related work. Section 3 recalls the key notions used throughout this paper. The structural properties of the disjunctive search space are explored in Section 4, followed by a detailed description of the GARM tool having for purpose to offer a complete process for the extraction of generalized association rules in Section 5. Experimental results focusing on the mining time as well as the quantitative aspect are reported and discussed in Section 6. Section 7 concludes the paper and points out future works.
Contributions related to association rule mining mainly concentrated on the classical
rule form, namely that presenting conjunction of items in both premise and conclusion
parts. In this respect, many concise representations for such rules were proposed in the
literature [
Some works [
In this section, we briefly sketch the key notions that will be of use throughout the paper. Definition 1. An extraction context is a triplet K = (O, I, R) where O and I are, respectively, a finite set of objects (or transactions) and items (or attributes), and R ⊆ O × I is a binary relation between the objects and items. A couple (o, i) ∈ R denotes that the object o ∈ O contains the item i ∈ I. Example 1. We will consider in the remainder a context that consists of transactions (1, AB ), (2, ACD ), (3, CDE ), (4, DEF ), (5, ABCDE ), and (6, ABC ) 3. Definition 2. (SUPPORTS OF A PATTERN) Let K = (O, I, R) be a context and I be a pattern. We mainly distinguish three kinds of supports related to I:
Supp( ∧ I ) = | {o ∈ O | (∀ i ∈ I, (o, i) ∈ R)} | Supp( ∨ I ) = | {o ∈ O | (∃ i ∈ I, (o, i) ∈ R)} |
Supp(I ) = | {o ∈ O | (∀ i ∈ I, (o, i) ∈/ R)} | Roughly speaking, the semantics of the aforementioned supports is as follows: • Supp(∧ I ) is the number of objects containing all items of I. • Supp(∨ I ) is the number of objects containing at least one item of I. • Supp(I ) is the number of objects that do not contain any item of I.
Note also that Supp(∨ I ) and Supp(I ) are two complementary quantities w.r.t. |O| in the sense that: Supp(∨ I ) + Supp(I ) = |O|.
Example 2. Consider our running context. We have Supp(∧ CDE) = | {3, 5} | = 2, Supp(∨ CDE) = | {2, 3, 4, 5, 6} | = 5 and Supp(CDE) = | {1} | = 1.
Hereafter, Supp(∧ I ) will simply be denoted Supp(I ). In addition, if there is no risk of confusion, the conjunctive support will simply be called support. A pattern I is said to be frequent if Supp(I ) is greater than or equal to a minimum support threshold, denoted minsupp. Since the set of frequent patterns is an order ideal, the set of items I will be considered as only containing frequent items. Lemma 1 states that conjunctive supports can be derived starting from disjunctive ones.
Lemma 1. [
X Supp(I ) =
( − 1)|I0|−1Supp( ∨ I0) ∅⊂I0⊆I 4
In this section, we will characterize disjunctive patterns through the associated
equivalence classes induced by the following closure operator:
Definition 3. Let K = (O, I, R) be an extraction context. The disjunctive closure
operator h is defined as follows [
I 7→ h(I ) = {i ∈ I | (∀ o ∈ O) ((o, i) ∈ R) ⇒ (∃ i1 ∈ I )((o, i1) ∈ R)}.
The disjunctive closure h(I ) of a pattern I is equal to the maximal set of items which
only appear in the transactions that contain at least an item of I. The closure operator h
induces an equivalence relation on the power-set of I, which partitions it into so-called
disjunctive equivalence classes. In each class, all the elements have the same
disjunctive support. The smallest incomparable elements, w.r.t. set inclusion, of a disjunctive
equivalence class are called essential patterns, while the disjunctive closed pattern is the
largest one [
• A pattern I ⊆ I is a disjunctive closed pattern if I = h(I ) or, equivalently, Supp( ∨ I ) < min{Supp(∨I0) | I0 ⊆ I s.t. I ⊂ I0}. • A pattern I ⊆ I is an essential pattern if ∀ I0 ⊂ I, I * h(I0) or, equivalently, Supp(∨ I ) > max{Supp(∨I0) | I0 ⊆ I s.t. I0 ⊂ I}.
Example 3. Consider our running context. The pattern CDEF is disjunctively closed, while BE is not, since Supp(∨ BE ) = Supp(∨ BEF ). On the other hand, the pattern AC is essential, while DE is not, since Supp(∨ DE ) = Supp(∨ D ).
In the remainder, F E PK 4 denotes the set of frequent essential patterns associated to a given context K and a fixedminsupp value. The associated set of disjunctive closure will further be denoted E DCPK 5. This latter set is hence equal to {h(I ) | I ∈ F E P K}.
To establish the link with conjunctive equivalence class – gathering patterns having
the same Galois closure [
As mentioned in the first section, the GARM tool is composed of three complementary components which are as follows: (i) Extracting an exact concise representation of frequent patterns based on disjunctive closed patterns and frequent essential ones. (ii) Building a partially ordered structure w.r.t. set inclusion within disjunctive closed patterns. Each one of these latter will be accompanied by its set of frequent essential patterns. (iii) Deriving generalized association rules from the built structure. 5.1
Our representation is based on the sets F E PK and E DCPK, as stated by Theorem 1.
Theorem 1. The set E DCPK ∪ F E PK is an exact concise representation of the set of
frequent patterns F PK [
Example 4. Figure 1 (Left) lists the set of disjunctive closed patterns associated to the running context. For each closed pattern, its associated disjunctive support and frequent essential patterns, for minsupp = 1, are also given.
This representation will be denoted DSSRK 6. It is extracted thanks to an
adaptation of our DCPR MINER 7 algorithm [
B 3 C 4 F 1 AB 4 EF 3 ABC 5 BEF 5 DEF 4
CDEF 5 ABCDEF 6
FEPK
B C F A
E AC, BC
BE
D
CD, CE AD, AE, BD, BCE
({AD, AE, BD, BCE}: ABCDEF, 6) ({AB, BC}: ABC, 5) ({BE}: BEF, 5) ({CD, CE}: CDEF, 5) ({A}: AB, 4) ({D}: DEF, 4) ({E}: EF, 3) ({B}: B, 3) ({C}: C, 4)
({F}: F, 1)
∅
GARM tool. Starting from DSSRK, the conjunctive and negative supports of frequent
patterns can thus be deduced using disjunctive supports. This representation also allows
the derivation of the support of each literalset whose positive variation is based on a
frequent pattern. This is carried out using the following formula [
( − 1)|S|Supp(x1 ∧ x2 ∧ . . . ∧ xn ∧ S), such
S⊆{y1,...,ym} that its positive variation, namely {x1, x2, . . ., xn, y1, y2, . . ., ym}, belongs to F PK. 5.2
In this section, we will propose a new algorithm, called POSB 8, for partially sorting
disjunctive closed patterns w.r.t. set inclusion. The POSB algorithm hence takes as
input the representation DSSRK s.t. to each disjunctive closed pattern is associated
its set of frequent essential patterns and disjunctive support. A node in the partially
ordered structure will be associated to each disjunctive closed pattern. The
pseudocode of POSB is shown by Algorithm 1. Our algorithm inherits two main optimizations
used in the algorithm proposed by Valtchev et al. [
On the other hand, the border B is an anti-chain w.r.t. set inclusion containing maximal closures among those already treated. In fact, the Valtchev et al. algorithm constructs the Hasse diagram representing the subset-superset relationship among concepts in the Galois lattice. It begins at the top of the lattice and then recursively identifies the lower neighbors of each concept. Nevertheless, it is not directly adapted to our situation. Indeed, although the intersection of two disjunctive closed patterns is obviously
Input: The set EDCPK of disjunctive closed patterns. Output: The disjunctive closed patterns ordered by set inclusion. Begin
B := ∅ ;
P rohibited List = ∅;
inter := b ∩ f ; If (inter = b) then
LOWER COVER INSERTION(f , b);
B := B\ b; Else If (inter 6= ∅) then
LOWER COVER MANAGEMENT(f , b); End
B := B ∪ f ;
a disjunctive closed pattern, this latter does not necessarily belong to E DCPK. This is
due to the fact that it could have all its essential patterns infrequent and, hence, has been
already pruned. On its side, the proposed algorithm in [
In Algorithm 1, disjunctive closed patterns are inserted one at a time to a structure which is only partially finished to obtain at the end the entire one. Letf be the current disjunctive closed pattern to be inserted in the partially ordered structure. f will be compared to the elements of the border B. If an element b ∈ B is included in f , then it is an element of its lower cover. A link between the node representing b and that representing f will be constructed thanks to the LOWER COVER INSERTION procedure (cf. Algorithm 2). The element b will then be deleted from the border. If b is not included in f but their intersection is not empty, then the LOWER COVER MANAGEMENT procedure will identify the common immediate predecessors of b and f (cf. Algorithm 3). Finally, f will be added to the border. It is important to note that in the LOWER COVER MANAGEMENT procedure, a prohibited list is associated to each disjunctive closed pattern to be inserted in the partially ordered structure. Indeed, when updating the precedence link between disjunctive closed patterns, a node can be visited more than once since it can be an immediate predecessor of many other nodes. This list will avoid such useless treatments by only allowing the visit of nodes that do not belong to it.
Example 5. The associated structure to our running context is given by Figure 1 (Right). 5.3
Once the partially ordered structure built, deriving (subsets) generalized association rules can be easily done. An association rule R: X ⇒ Y based on a pattern Z, denoted Z-based rule, is such that X = {x1, x2, . . . , xn} ⊆ I and Y = {y1, y2, . . . , ym} ⊆ I be two patterns, X ∩ Y = ∅, and X ∪ Y = Z. An association rule is usually considered as interesting w.r.t. two statistical measures, namely the support and the confidence. The formulae of these measures for an arbitrary rule are as follows:
Input: A disjunctive closure f , and an element pred to be inserted in its lower cover. Output: The updated lower cover of f .
Begin
Foreach (l ∈ Lower Cover(f )) do inter := l ∩ pred; If (inter = pred) then
return; Else If (inter = l) then
Lower Cover(f ) := Lower Cover(f ) \ l; End
Lower Cover(f ) := Lower Cover(f ) ∪ pred;
Input: A disjunctive closed pattern f , and an element b of the border B.
Output: The updated lower cover of f .
Begin
Foreach (pred b ∈ Lower Cover(b)) do
If (pred b ∈/ P rohibited List) then inter := pred b ∩ f ; If (inter = pred b) then
LOWER COVER INSERTION(f , pred b); Else If (inter 6= ∅) then
LOWER COVER MANAGEMENT(f , pred b);
P rohibited List := P rohibited List ∪ pred b; End
Supp(X ⇒ Y ) = Supp(X ∧ Y ), and, Conf(X ⇒ Y ) = Supp(X ∧ Y ) Supp(X ) A rule is said to be exact if its confidence is equal to 1. Otherwise, it is said to be approximate. In addition, it is said to be interesting or valid if its support and confidence values are greater than or equal to their respective minimum thresholds minsupp and minconf. It is clear that whenever we are able to evaluate Supp(X ⇒ Y ), the derivation of the confidence value will be straightforward.
Let us now adapt the association rule framework to our context. As shown in Subsection 5.1, the DSSRK representation allows deriving the disjunctive, conjunctive and negative supports of each set of positive and negative items whose positive variation is based on a frequent pattern. In the sequel, we present an overview of the process by which we retrieve generalized association rules and evaluate their associated supports through traversing the partially ordered structure. Rules can be classified according to the number of nodes required for their extraction. We then distinguish two cases: 1. An intra-node rule: it requires a unique node and highlight relationships between a frequent essential pattern and its disjunctive closure f (here Z = f ). 2. An inter-nodes rule: it is extracted using two nodes N1 and N2 s.t. the associated disjunctive closure of N1, denoted f1, is one of the immediate predecessors of that of N2, denoted f2. Let e1 be a frequent essential pattern of f1. An inter-nodes rule describes relationships between either f1 and f2 or e1 and f2 (here Z = f2). Both kinds of rules – intra-node and inter-nodes – can be either exact or approximate.
Different forms of generalized association rules can be extracted starting from our
representation (cf. [
Supp(X ∧ Y ) = Supp((( ∨ X ) ∨ ( ∨ Y ))) = Supp(Z ) = |O| - Supp(∨ Z ), 3. Form 3: disjunction of items in premise and negation of items in conclusion ∨ X ⇒ Y : Supp(∨ X ⇒ Y ) = Supp(∨ X ∧ Y ) = Supp((∨ X ) ∨ (∨ Y )) - Supp(∨ Y ) = Supp(∨ Z ) - Supp(∨ Y ), and, 4. Form 4: negation of items in premise and disjunction of items in conclusion X ⇒ ∨ Y : Supp(X ⇒ ∨ Y ) = Supp(X ∧ ∨ Y ) = Supp((∨ X ) ∨ (∨ Y )) - Supp(∨ X ) = Supp(∨ Z ) - Supp(∨ X ), where either X or Y is a frequent essential pattern or a disjunctive closed one, and Z = X ∪ Y is a disjunctive closed pattern (as described above). For each rule, the support of Z is known. It is the same for either X or Y since one of them is assumed to be a frequent essential pattern or a disjunctive closed pattern. For the sake of simplicity, we assume in the remainder that X is a frequent essential pattern or a disjunctive closed pattern. Since Y = Z\X, then Y does not necessarily belong to DSSRK and, may even not be a frequent pattern. Nevertheless, its disjunctive support is required to evaluate that of the associated rule. To this end, we bound the support of Y using a lower bound, denoted lb Supp, and an upper bound, denoted ub Supp, computed as follows: • lb Supp(∨ Y ) = max{Supp(∨ e) | e ∈ F E P K and e ⊆ Y }, • ub Supp(∨ Y ) = min{Supp(∨ f ) | f ∈ E DCP K and Y ⊆ f }.
In this respect, if Y is encompassed between a frequent essential pattern and its disjunctive closure, then lb Supp(∨ Y ) = ub Supp(∨ Y ). Hence, the support and confidence of the associated rule will be exactly computed. Otherwise, these latter measures will be bounded by a minimal and a maximal possible value using the bounds associated to Y . Such rules, further denoted approximated rules, are defined as follows: Definition 5. An association rule is said to be approximated if it has either its support or its confidence not exactly determined.
Then, only valid rules having minimum possible values of support and confidence
greater than or equal to minsupp and minconf, respectively, will be retained. Note that
an approximated rule is different from an approximate rule in the sense that the latter
has its support and confidence exactly computed (with a confidence not equal to1),
what is not the case of the former. In this respect, approximated rules were shown to
convey interesting knowledge in the case of positive rules (see for example [
Noteworthily, the bounds lb Supp(∨ Y ) and ub Supp(∨ Y ) always exist. Indeed, on the one hand, since the set of items I is pruned w.r.t. minsupp, then Y will be composed of frequent items even if it is infrequent. These items obviously belong to F E PK, what ensures the existence of the lower bound. On the other hand, Y is covered by at least a disjunctive closed pattern, namely Z, what ensures the existence of the upper bound. Example 6. Let minsupp = 1 and let minconf = 0.7. Consider the intra-node rule R1 of Form 1 based on the disjunctive closed pattern ABCDEF and its frequent essential pattern BCE: ∨ BCE ⇒ ∨ ADF. Supp(R1) = Supp(∨ BCE) + Supp(∨ ADF) - Supp(∨ ABCDEF) = Supp(∨ ADF) (since h(BCE ) = ABCDEF ). Since ADF ∈/ DSSRK, we need to evaluate its support. Since AD ⊆ ADF ⊆ h(AD ) = ABCDEF (cf. Figure 1 (Left)), then lb Supp(∨ ADF) = ub Supp(∨ ADF) = 6. Hence, Supp(R1) = 6 and Conf (R1) = 1. R1 is hence a valid rule. Now, consider the inter-nodes rule R2 of Form 1 based on ABCDEF and one of its immediate predecessors, namely ABC (cf. Figure 1 (Right)): ∨ ABC ⇒ ∨ DEF. In this case, DEF ∈ E DCPK. Hence, Supp(R2) = Supp(∨ ABC) + Supp(∨ DEF) - Supp(∨ ABCDEF) = 5 + 4 - 6 = 3, and Conf (R2) = 0.6. Here, we took X = ABC. If we set Y = ABC, then the associated rule R3 = ∨ DEF ⇒ ∨ ABC will have the same support than R2. Nevertheless, its confidence is equal to 0.75. Hence, R3 is a valid rule while R2 is not. 6
Our experiments 9 focused on the mining time as well as the number of extracted valid rules w.r.t. their associated type, i.e., exact, approximate or approximated. They were carried out on a PC equipped with a Pentium (R) having 3GHz as clock frequency and 1.75GB of main memory, running the GNU/Linux distribution Fedora Core 7 (with 2GB of swap memory). The compiler gcc 4.1.2 is used to generate the executable code starting from our C++ implementation.
In the proposed experiments, the minconf value is set to the relative minimum support value, i.e., minsupp . Table 1 presents the mining time in seconds of the three |O| components of GARM. This table shows the efficiency of our tool towards extracting generalized associated rules. Indeed, even for low minsupp values, GARM remains very fast. In this respect, the time consumed by each component, w.r.t. the total time, 9 Test contexts are available at: http://fimi.cs.helsinki.fi/data . closely depends on the context characteristics. Nevertheless, the second and third components are in general faster than the first one. On the other hand, Table 2 highlights that the number of extracted rules closely depends on the context density. Indeed, the higher the value of this latter, the larger the associated equivalence classes are, and the greater the number of frequent essential patterns and closed ones is. This fact augments the number of rules even for high minsupp values for dense contexts. Interestingly enough, the number of exact and approximated rules for RETAIL and KOSARAK is equal to 0 for the tested minsupp values. This is due to the fact that for both contexts, each essential pattern is equal to its disjunctive closure what is not the case for the CONNECT and PUMSB contexts. Please note that the mining time and the number of extracted rules when minconf varies is omitted here, due to space limitations. 7
In this paper, we presented a complete tool, called GARM, allowing the extraction of generalized association rules. Our tool is composed of three components. The first consists in extracting a concise representation of frequent patterns based on disjunctive closed ones. The second component aimed at partially ordering these closure w.r.t. set inclusion. Once the structure built, extracting subsets of generalized association rules becomes a straightforward task thanks to the last component. Carried out experiments proved the effectiveness of the proposed tool. It is also important to mention that our GARM tool is easily adaptable to the case where the input is composed by conjunctive (closed) patterns instead of disjunctive ones.
Other avenues for future work mainly address the following points: First, a detailed
comparison of our approach to the general GUHA approach [
Acknowledgments: We would like to thank anonymous reviewers for their helpful comments and suggestions. We are also grateful to Mrs. Nassima Ben Younes for fruitful discussions and help in the implementation of the tool. This work is supported by the French-Tunisian project CMCU-Utique 05G1412.