The problem of the relevance and the usefulness of extracted association rules is becoming of primary importance, since an overwhelming number of association rules may be derived from even reasonably sized real-life databases. In this paper, we introduce a novel generic base of association rules, based on the Galois connection semantics. The novel generic base is sound and informative. We also present a sound axiomatic system, allowing to derive all association rules that can be drawn from an extraction context.
Data mining has been extensively addressed for the last years, particularly the
problem of discovering association rules. These latter aim at exhibiting
correlations between data items (or attributes), whose interestingness is assessed by
statistical metrics. However, an unexploited huge amount of association rules is
drawn from real-life databases. This drawback encouraged many research issues,
aiming at finding the minimal nucleus of relevant knowledge can be extracted
from several thousands of highly redundant rules. Various techniques are used to
limit the number of reported rules, starting by basic pruning techniques based on
thresholds for both the frequency of the represented pattern (called the support )
and the strength of the dependency between premise and conclusion (called the
confidence). More advanced techniques that produce only a limited number of
the entire set of rules rely on closures and Galois connections [
Once these generic bases are obtained, all the remaining (redundant) rules can be derived ”easily”. In this context, little attention was paid to reasoning from generic bases comparatively to the battery of papers to define them. Essentially, they were interested in defining syntactic mechanisms for deriving rules from generic bases.
In this paper, we introduce a novel generic base of association rule, which is sound and informative. The soundness property assesses the ”syntactic” derivation, since it ensures that all association rules can be derived from the generic base. The informativeness property ensures that the support and confidence of a derivable rule can be exactly determined.
The remainder of the paper is organized as follows. Section 2 introduces the mathematical background of FCA and its connection with the derivation of (non-redundant) association rule bases. Section 3 presents the related work on defining and reasoning from generic bases of association rules. In section 4, we introduce a novel, sound and informative generic base of association rules. We also provide a set of inference axioms, for deriving association rules and we we prove its soundness. Section 5 concludes this paper and points out future research directions. 2
In the following, we recall some key results from the Galois lattice-based paradigm in FCA and its applications to association rules mining. 2.1
In the rest of the paper, we shall use the theoretical framework presented in [
A formal context is a triplet K = (O, A, R), where O represents a finite set of objects (or transactions), A is a finite set of attributes and R is a binary (incidence) relation (i.e., R ⊆ O × A). Each couple (o, a) ∈ R expresses that the transaction o ∈ O contains the attribute a ∈ A. Within a context (c.f., Figure 1 on the left), objects are denoted by numbers and attributes by letters.
We define two functions, summarizing links between subsets of objects and
subsets of attributes induced by R, that map sets of objects to sets of attributes
and vice versa. Thus, for a set O ⊆ O, we define φ(O) = {a | ∀o, o ∈ O ⇒ (o, a) ∈
R}; and for A ⊆ A, ψ(A) = {o | ∀a, a ∈ A ⇒ (o, a) ∈ R}. Both functions φ and
ψ form a Galois connection between the sets P( ) and P(O) [
In what follows, we introduce the frequent closed itemset 3, since we may only look for itemsets that occur in a sufficient number of transactions.
Frequent closed itemset: An itemset A ⊆ A is said to be closed if A = ω(A), and is said to be frequent with respect to minsup threshold if supp(A)= |ψ(A)| ≥ minsup.
|O|
Formal Concept: A formal concept is a pair c = (O, A), where O is called extent, and A is a closed itemset, called intent. Furthermore, both O and A are related through the Galois connection, i.e., φ(O) = A and ψ(A) = O.
Minimal generator: An itemset g ⊆ A is called minimal generator of a
closed itemset A, if and only if ω(g) = A and @g0 ⊆ g such that ω(g0) = A [
Galois lattice: Given a formal context K, the set of formal concepts CK
is a complete lattice Lc = (C, ≤), called the Galois (concept) lattice, when CK
is considered with inclusion between itemsets [
The partial order is used to generate the lattice graph, called Hasse diagram, in the following manner: there is an arc (c1, c2), if c1 ¹ c2 where ¹ is the transitive reduction of ≤, i.e., ∀c3 ∈ CK, c1 ≤ c3 ≤ c2 implies either c1 = c3 or c2 = c3.
Iceberg Galois lattice: When only frequent closed itemsets are considered with set inclusion, the resulting structure (Lˆ, ⊆) only preserves the LUBs, i.e., the joint operator. This is called a join semi-lattice or upper semi-lattice. In the remaining of the paper, such structure is referred to as ”Iceberg Galois Lattice”. Example 1. Let us consider the extraction context given by Figure 1 (Left). The associated Iceberg Galois lattice, for minsup=2, is depicted by Figure 1(Bottom)4. Each node in the Iceberg is represented as couple (closed itemset; support) and is decorated with its associated minimal generators list.
In the following, we present the general framework for the derivation of association rules, then we establish its important connexion with the FCA framework. 2.2
Let I = {i1, i2, . . . , im} be a set of m distinct items. A transaction T , with an identifier further called TID, contains a set of items in I. A subset X of I where k = |X| is referred to as a k−itemset (or simply an itemset), and k is called the length of X. A transaction database, say D, is a set of transactions, which can be easily transformed in an extraction context K. The number of transactions of D containing the itemset X is called the support of X, i.e., 4 We use a separator-free form for sets, e.g., AB stands for {A, B}.
A B C D E 1 × × × 2 × × × 3 × × × × 4 × × 5 × × × ×
AB
AC
AD
AE
BC BD BE CD CE
DE A
B
C
D
E {A} (AC;3) {C} (C;4) {AE}, {AB} (ABCE;2)
{BC},{CE} (BCE;3) {B}, {E} (BE;4) (∅;5) ∅ supp(X)=| {T ∈ D | X ⊆ T } |. An itemset X is said to be frequent when support(X) reaches at least the user-specified minimum threshold minsup.
Association rule derivation is achieved from a set F of frequent itemsets in an extraction context K, for a minimal support minsup. An association rule R is a relation between itemsets of the form R : X ⇒ (Y − X), in which X and Y are frequent itemsets, and X ⊂ Y . Itemsets X and (Y − X) are called, respectively, premise and conclusion of the rule R. The valid association rules are those whose the strength metric conf(R)= |XY | is greater than or equal to |X| the minimal threshold of confidence minconf. If conf(R)=1 then R is called exact association rule (ER), otherwise it is called approximative association rule (AR). 3
The problem of the relevance and usefulness of extracted association rules is
of primary importance. Indeed, in most real life databases, thousands and even
millions of high-confidence rules are generated among which many are
redundant. This problem encouraged the development of tools for rule classification
according to their properties, for rule selection according to user-defined criteria,
and for rule visualization. In this paper, we are specially interested in the lossless
information reduction, which is based on the extraction of a generic subset of
all association rules, called base, from which the remaining (redundant)
association rules may be derived. The concept of rule redundancy can be considered
as follows [
The authors also characterized a generic base of approximate association
rules, based on extending the partial implications base of Luxenburger [
As pointed out in [
In [
Rule # Implication Rule # Implication R8 R9 R10 R11 R12
C.⇒75A C.⇒75BE C ⇒.5 ABE A.⇒66BCE E.⇒75BC
R13 R14 R15 R16 R17
B.⇒75CE
E ⇒.5 ABC
B ⇒.5 ACE
BC.⇒66AE
CE.⇒66AB
In [
In what follows, we present the GBP han algorithm, whose pseudo-code is given by Algorithm 1.1, permitting to derive the GBP han generic base. Example 2. Let us consider the extraction context given by Figure 1 (Left). Then, in what follows the running process of the GBP han algorithm for minsup = 52 and minconf = 21 . The set R is initialized with the set of frequent itemsets in a decreasing order, i.e., R= {ABCE, ABC, ABE, ACE, BCE, AB, AC, AE, BC, BE, CE, A, B, C, E}. For J = ABCE, we have supp(ABCE) = 25 ≤ minconf. Then, we have : LABCE = A, B, C, E, AB, AC, AE, BC, BE, CE, ABC, ABE, ACE, BCE. For I = A, we have |ABCE| = 32 ≥ minconf. In this case, the generic |A| rule A⇒ ABCE is added to the generic base and from LABCE we delete all element including A, i.e., AB, AC, AE, ABC, ABE, ACE, and A. Therefore, the set LABCE equals {B, C, E, BC, CE, BCE}. Next for I= B, we have |ABCE| = 1 , |B| 2 we have to generate the generic rule B⇒ ABCE and to delete BC, C and BCE from LABCE. Therefore, the set LABCE is equal to {C, E, CE}. For I= C, we have supp(ABCE) = 21 , then we generate the generic rule C⇒ ABCE and we delete CE supp(C) and C from LABCE. Finally for I= E, we have |ABCE| = 1 . Hence, we generate |E| 2 the generic rule E⇒ABCE and E is removed from LABCE. Next, we have to remove from the set R, the following itemsets ABC, ABE, ACE, AB and AE. The set R is found to be equal to {BCE, AC, BC, BE, CE, A, B, C, E}. Then, for J= BCE, we have |BCE|= 53 ≥ minconf. In this case, we have to generate the generic rule ∅ ⇒BCE and we delete BCE, BC, BE, CE, B, C and E from R. Therefore, R= {AC, A} and for J= AC we have |AC = 35 ≥ minconf. Then, we | have to generate the generic rule ∅ ⇒ AC. After the removal of AC and A from Algorithm 1.1: GBP han Data: – R= {frequent itemsets in a decreasing order} – minsup – minconf Result: GBP han: generic base begin foreach J ∈ R of size i from m down to 1| m= |largest frequent itemset| do if support(J) ≥ minconf then
GBP han=GBP han∪ {∅ ⇒J }
R=R-{J 0|J 0 ⊆ J } else
LJ = {all nonempty subset of J in an ascendant order } foreach I ∈ LJ of size k from 1 to i-1 do if @ I0 ⇒ J 0 ∈ GBP han | I0 ⊆ I ∧ and J ⊆ J 0 ∧ ||JI|| ≥ minconf then
GBP han=GBP han∪ {I ⇒ J }
LJ =LJ -{ I0| I ⊂ I0 ⊂ J }
LJ =LJ - I
R= R- {J0 ⊆ J | |J0|=|J|} end R, the set R is found to be empty and the algorithm terminates. The resulting generic base is depicted by Table 1.
Implication Support Confidence
ACBE∅∅⇒⇒⇒⇒⇒⇒AAAABBABBBCCCCCCEEEEE 545245525522 323521521312
Table 1. Generic Base GBP han.
For the derivation of association rules, the author presented a sound axiomatic system composed of the following two axioms: A1:Left augmentation If I⇒ JK ∈ GBP han, then IJ⇒JK is a derivable valid rule.
A2:Decomposition If I ⇒ JK∈ GBP han, then I⇒J and I⇒ K are derivable valid rules. For example, from ∅ ⇒AC and using the above mentioned axioms, it is possible to derive A⇒ AC, C⇒ AC and A⇒ C.
However, two drawbacks may be addressed. At first, only frequent itemsets are used to define the generic base, and one can imagine the length and the number of such frequent itemsets that could be derived from correlated extraction contexts. Second, the presented generic base is not informative, i.e., it may exist a derivable rule for which it is impossible to determine exactly both its support and confidence. For example, the association rule BE⇒C is derivable from the generic rule E⇒ABCE. However, it is impossible to derive the exact confidence and support of the derivable rule from the GBP han generic base. 3.3
In [
Cover(X ⇒Y) = {X ∪ Z ⇒ V | Z, V ⊆ Y ∧ Z ∩ V = ∅ ∧ V 6= ∅}.
The number of the derived rules from a rule R: X ⇒ Y is equal to |Cover(R)|=3m2m, where |Y|=m. For a derived rule R’, we have conf(R’)≥ max { conf(Ri)| R’∈ Cover(Ri)} and supp(R’)≥ max { supp(Ri)| R’∈ Cover(Ri)}. In order to determine whether a rule R’:X’⇒Y’ belongs to the cover of a rule R:X⇒Y, we have to check that X ⊆ X0 and Y 0 ⊂ Y .
The author proposed a minimal base of rules called representative association rules (RR) defined as follows: RR={R ∈ AR | @ R’∈ AR, R6=R’and R ∈ C(R’)} where AR is the set of all valid association rules.
As pointed out in [
On the other hand, the author showed that given the following bases: – The DG Duquenne-Guigues basis for exact rules, i.e.,
DG={R:X⇒ω(X)-X |X ∈F P}, where F P the pseudo-closed itemsets. – the PB Proper basis for approximative rules, i.e.,
PB={R:X⇒Y-X |X,Y ∈F CI and X ⊂ Y and conf(R)≤ minconf}
then the couple(PB,DG) forms a lossless, sound and informative base, by
using the conjunction of closure-closure inference rule [
Intuitively, we are looking for defining a new informative generic base providing the ”maximal boundaries” in which stand all the derivable rules. Indeed, a derivable rule cannot present a smaller premise than that of its associated generic rule, i.e., from which it can be derived. On the other hand, a derivable rule cannot present a larger conclusion than that of its associated generic rule. In what follows, we present the definition of the introduced IGB generic base. Definition 4. The generic base IGB of association rules given by : IGB = {R : gs ⇒ A-gs | A ∈ F CI ∧ ω(gs) ≤ A ∧ conf(R) ≥ minconf ∧ @ g0 such that gs ⊂ g0 and conf(g0 ⇒ A-g0)≥minconf }.
Proposition 1. Let I a frequent closet itemset. If |I| ≥ minconf, then the generic rule that can be drawn from I is ∅ ⇒I.
Proof. since conf(∅ ⇒I)=supp(I), then the generic rule ∅ ⇒I is valid. It is also the largest rule that can be drawn from the frequent closed itemset I. Indeed, @ R1: X1 ⇒ Y1 such that X1 ⊂ ∅ and I ⊆Y1. 4.1
The IGB generic base construction In what follows, we present the Igb algorithm, whose pseudo-code is given by Algorithm1.2, permitting to construct the introduced generic base of association rules. The Igb algorithm is based on Proposition 1. So, it considers the set of frequent closed itemsets F CI. For each closed itemset I, it checks whether its support is greater than or equal to minconf. If it is the case, then we generate the generic rule ∅ ⇒I. Otherwise, it has to look for the smallest minimal generator, say gs, associated to a frequent closed itemset subsumed by I, and generates the generic rule gs ⇒I-gs.
Example 3. Let us consider the extraction context given by Figure 1 (Left). Then, in what follows the running process of the Igb algorithm for minsup = 2 5 and minconf = 12 . For I = ABCE, we have |ABCE|= 25 < 12 , LABCE = {C, A, B, E, BC, CE, AE, AB}. Since |ABCE| = 12 , we have to generate the generic rule |C| C⇒ABE and to remove BC, CE and C from LABCE . Next, we have |ABCE| |A| = 23 > 12 . Then, we generate A⇒ BCE and AE, AB and A are removed from LABCE . Then, we have |ABCE| = 1 . So, we generate the generic rule B⇒ACE |B| 2 and we delete B from LABCE . From, the evaluation of |ABCE| = 1 , we have to |E| 2 generate E⇒ ABC, and to remove E from LABCE , which is found to be empty.
For I = BCE we have |BCE| ≥ minconf, then we generate the generic rule ∅ ⇒BCE. Next, we have to apply the same process, respectively, for I = AC, I = BE and I = C. The resulting generic base is depicted by Table 2.
Obviously, the introduced IGB generic base is largely more compact than that proposed by Bastide et al. (8 generic rules vs 17). Comparatively to that proposed by Phan, the IGB generic base is not more compact but it presents the informative property. The Igb algorithm is currently under implementation, and we have to assess its compactness output versus those presented in the literature survey. Algorithm 1.2: Igb Data:
begin foreach frequent closed itemset I ∈ F CI / I6= ∅ do if (|I| ≥ minconf ) then
R= ∅ ⇒ I R.supp=|I| R.conf=|I|
IGB=IGB ∪ R else
2. minconf
LI1 ={non empty minimal generators of frequent closed itemset I1 | I1 ⊆ I} foreach minimal generator g ∈ LI1 do if ( ||gI|| ≥ minconf ∧ I 6= g) then
R= g ⇒I-g R.supp=|I| R.conf= |I|
|g| IGB=IGB ∪ R
LI1 =LI1 -{g0| g ⊂ g0}
LI1 =LI1 -g end 4.2
ARK/ Z ⊂ Y ∧ c0= |X|XZ|| .
c0= | X|YZ| | .
In this subsection, we will try to axiomatize the derivation of association rules from the the IGB generic base. In the following, we provide a set of inference axioms and we prove their soundness. Then, we show that the IGB generic base is informative.
Proposition 2. Let IGBK and ARK be a generic base and the set of valid association rules, respectively, that can be drawn from a context K. Then, the following inference axioms are sound: A0.Conditional Reflexivity: If X ⇒c Y ∈ IGBK ∧ X 6= ∅ then X ⇒cY ∈ ARK A1.Conditional Decomposition: If X ⇒cY ∈ IGBK ∧ X 6= ∅ then X ⇒c0 Z ∈ A2.Augmentation If X ⇒cY ∈ IGBK then X ∪ Z ⇒c0 Y-{Z} ∈ ARK /Z ⊂ Y ∧ Proof. A0.Conditional Reflexivity: follows from the proper definition of the IGB generic base. The condition X 6= ∅ ensures the non emptiness of the derived rule. Implication Support Confidence ∅∅∅∅EBCA⇒⇒⇒⇒⇒⇒⇒⇒AAABBBCABCCBECCCEEEE 5235355225454525 1223512335541254
Table 2. The IGB generic base.
A1.Conditional Decomposition: Since, X ⇒cY ∈ IGBK then conf(X ⇒cY)=c ≥ minconf. Since Z ⊂ XY, we have |XZ|≥ |XY| and then |X|XZ|| ≥ |X|XY|| ≥ minconf. Hence, X ⇒c0 Z is a valid rule with a confidence value c0= |XZ| .The |X| condition X 6= ∅ ensures the non emptiness of the derived rule.
A2.Augmentation Since, X ⇒cY ∈ IGBK then conf(X ⇒cY)=c ⇔ |XY | =c ≥ |X| minconf. From X ⊂ XZ, we have |X| >|XZ| > and minconf < |XY | < |X|XYZZ|| . |X|
Hence, X ∪ Z ⇒c0 Y-{Z} is a valid rule, with a confidence value c0= | X|YZ| | . Proposition 3. The IGB generic base is informative.
Proof. To prove that the IGB generic base is informative, it is sufficient to show that it contains all the necessary information to determine the support of an itemset in a derived rule. Therefore, it means that we have to be able to reconstitute all closed itemset by concatenation of the premise and the conclusion of a generic rule 6. The algorithm considers all the discovered frequent closed itemsets. Hence for a given frequent closed itemset, say c, it tries to find the smallest minimal generator, say gs, associated to frequent closed itemsets subsumed by c and fulfilling the minsup constraint. Therefore, the algorithm generates the following generic rule gs ⇒c. Since gs ⊂ c, then gs ∪ c=c. Then by construction, all frequent closed itemsets can be reconstituted from the IGB generic base.
Conclusion: The IGB generic base is informative.
In what follows, we present the AR-deriv algorithm, whose pseudo-code is given by Algorithm1.3, permitting to derive all valid association rules from the IGB generic base. 5
In this paper, we presented a critical survey of the reported approaches for defining generic bases of association rules. Then, we introduced a novel generic
closed itemset containing it. Algorithm 1.3: A-r-deriv
Result: ARK:set of valid association rules begin foreach R:X⇒c Y ∈ IGBK do /* Applying Reflexivity axiom*/ if X 6= ∅ then ARK=ARK ∪ X⇒c Y if |Y| > 1 then foreach Z | Z⊂ Y do /*Applying Decomposition axiom*/ R’=X⇒Z s=Get-smallest-support(XZ, IGBK) /* the Get-smallest-support function yields the support value of the smallest closed itemset containing XZ*/ c’= |cX×Ys| ARK=ARK ∪ X ⇒c0 Z /*Applying Augmentation axiom*/ R’=XZ⇒Y-{Z} s=Get-smallest-support(XZ,IGBK) c’= |XY |
s
ARK=ARK ∪ XZ ⇒c0 Y − {Z} end base, which is sound and informative. We also provided a set of sound inference axioms for deriving all association rules from the introduced generic base of association rules. The reported algorithms are currently under implementation in order to include them in a Information Retrieval prototype. Specially, we are interested in assessing the well-known IR metrics, namely recall and precision, by using the introduced generic rule base in a query expansion process.