=Paper=
{{Paper
|id=None
|storemode=property
|title=An Inference System for Exhaustive Generation of Mixed and Purely
Negative Implications from Purely Positive Ones
|pdfUrl=https://ceur-ws.org/Vol-672/paper24.pdf
|volume=Vol-672
|dblpUrl=https://dblp.org/rec/conf/cla/MissaouiNR10
}}
==An Inference System for Exhaustive Generation of Mixed and Purely
Negative Implications from Purely Positive Ones==
https://ceur-ws.org/Vol-672/paper24.pdf
An Inference System for Exhaustive Generation
of Mixed and Purely Negative Implications from
Purely Positive Ones
Rokia Missaoui1 , Lhouari Nourine2 ,Yoan Renaud2
1
Université du Québec en Outaouais, Gatineau
rokia.missaoui@uqo.ca
2
Université Blaise Pascal, Clermont-Ferrand
{nourine,renaud}@isima.fr
Abstract. The objective of this article is to study the problem of gen-
erating implications with negation when only a set of purely positive
implications related to a formal context K = (G, M, I) is provided. To
that end, we define a sound and complete inference system which in-
cludes a characterization of implications whose left-hand side is a key in
the context K|K̃ representing the apposition of the context K and its
complementary K̃.
1 Introduction
In the classical problem of association rule mining, only attributes (items) present
in data are recorded and positive rules are extracted. This class of rules is a sub-
class of the larger and more general set of boolean association rules (i.e., rules
with negation, conjunction and disjunction) [11] and can help identify unex-
pected (surprising) patterns in many real-life applications (e.g., ostrich is a bird
that exceptionally does not fly or customers who buy smoked salmon buy also
caviar but not orange juice) [17]. In market basket analysis [1], rules with nega-
tion can help identify items that conflict with each other (e.g., if we buy caviar,
then we do not buy canned tuna) or suggest a classification of customers ac-
cording to their ability to buy or not a group of products [4]. A negative rule
of the form Y → Z̃ can also be useful to mine itemset substitutes because the
presence of the antecedent Y implies the absence of the positive counterpart of
the consequent Z̃, which means that Y may be a substitute for Z [18].
In the formal concept analysis (FCA) framework, a straightforward but not
efficient solution to the general problem of extracting association rules with
negation from a formal context K consists to conduct the apposition of the
initial context K with its complementary context K̃ to get the concept lattice
B(K|K̃) and then extract the rules out of that lattice. However, data collections
in many real-life applications tend to be very sparse and hence the corresponding
complementary contexts are dense and will generate a very likely huge set of
candidate itemsets and a tremendous set of uninteresting rules.
272 Rokia Missaoui, Lhouari Nourine,Yoan Renaud
In an initial work [12], we showed that in general cases, it is impossible to
compute all mixed implications from the sets of positive and negative implica-
tions without the context in hand. We also proposed a set of properties and
inference rules to infer a non exhaustive set of mixed implications (i.e., impli-
cations in which at least a negative attribute and a positive attribute coexist),
using either positive, negative or mixed implications, provided the original con-
text K is reduced. Later on, an additional inference rule [15] has been defined to
complete the inference system (see the last axiom in Table 4 of the appendix).
In this paper we present an inference system for the exhaustive generation
of purely negative and mixed implications when only a generic basis [13] of
positive implications is initially provided. Obviously, the whole set of implications
(denoted by ΣK|K̃ ) is a superset of purely positive implications (i.e., implications
with positive attributes only) and purely negative ones (denoted by ΣK̃ ) since
it generally contains mixed implications.
The paper is organized as follows. Section 2 provides a background on formal
concept analysis and association rule mining. Section 3 gives a brief overview of
related work. Section 4 provides a solution to the problem of generating impli-
cations with negation when only a set of purely positive implications is given
while the proposed inference system is presented in Section 5. A special case
is considered in Section 6 where the set ΣK of purely positive implications is
empty. Finally, a conclusion and further work are given in Section 7.
2 Background
2.1 Formal concept analysis
Formal Concept Analysis [7] has been successfully used for conceptual clustering
and rule mining. A formal context is a triple K := (G, M, I) where G, M and I
stand for a set of objects, a set of attributes, and a binary relation between G
and M respectively. For A ⊆ G and B ⊆ M we define
A0 := {a ∈ M | oIa ∀o ∈ A} and B 0 := {o ∈ G | oIa ∀a ∈ B},
the set of attributes common to objects in A and the set of objects sharing all the
attributes in B. The mapping (denoted by 0 ) between the powerset of G and the
powerset of M defines a Galois connection, and the induced closure operators
(on G and M ) are denoted by 00 . A formal concept c is a pair (A, B) with A ⊆ G,
B ⊆ M , A = B 0 and B = A0 , where A is called the extent of c and B its intent.
In the closed itemset mining framework [13, 23], G, M , A and B correspond to
the transaction database, the set of items (products), the closed tidset and the
closed itemset respectively.
The set B(K) of all concepts of the context K, partially ordered by:
(X1 , Y1 ) ≤ (X2 , Y2 ) ⇔ X1 ⊆ X2 , Y2 ⊆ Y1 .
An Exhaustive Generation of Mixed and Purely Negative Implications ... 273
forms a complete lattice, called a concept lattice and denoted by B(K). Concept
(X2 , Y2 ) is called the successor of (X1 , Y1 ) and, inversely, (X1 , Y1 ) is the prede-
cessor of (X2 , Y2 ). Concepts with a single immediate predecessor (successor) are
called join-irreducible (meet-irreducible).
Object (resp. attribute) set reduction of a context K = (G, M, I) consists of
discarding from the set G (resp. M ) all objects (resp. attributes) that may be
obtained through the intersection of some other objects (resp. attributes). The
concept lattice of a reduced context is isomorphic to the concept lattice of the
initial one.
The apposition K = K1 |K2 of two contexts K1 = (G, M1 , I1 ) and K2 =
(G, M2 , I2 ) is the horizontal concatenation of contexts sharing the same set G of
objects [7, 19]. It represents the context K = (G, M1 ∪M ˙ 2 , I1 ∪I
˙ 2 ) whose lattice
is a substructure of the direct product of B(K1 ) and B(K2 ).
In the rest of the paper and unless otherwise indicated, we will use upper-
case letters (e.g., B, Y ), lower-case letters and letters with tilde to mean sets of
attributes (itemsets), atomic attributes and elements with negation respectively.
For example, ã stands for the negation of attribute a and means that Object
o belongs to the extent of ã iff it does not belong to the extent of a, and Ã
represents the set {ã | a 6∈ A}.
2.2 Association Rule Mining
Association rule mining [2] is an extensively studied problem in data mining and
consists to extract a set of association rules from data (e.g., a set of transactions
describing a collection of items bought together). An association rule r is an
implication of the form Y → Z [sup, conf ], where Y and Z are subsets of
attributes (called itemsets), Y ∩ Z = ∅, and sup and conf represent the support
and the confidence of the rule, respectively. The support of a rule is defined as
P rob(Y ∪ Z) while the confidence is computed as the conditional probability
P rob(Z/Y ).
A set of studies in FCA were conducted on the generation of concise repre-
sentations of rules [9] such as informative rules (i.e., with minimized premise and
maximized consequence), Guigues-Duquenne basis [7, 8], generic basis [13], and
Luxenburger basis [10]. The notion of generator of a closed itemset [13, 14] and
pseudo-intent [7, 8] play a key role in such studies. A generic basis [13] associated
with a context K is a concise representation of exact rules (implications) of the
form r: Y → Y 00 \Y [sup, 1] such that Y is a generator for Y 00 . The generator
Y [14] of a closed itemset Z is a minimal subset of Z such that Y 00 = Z. The
support of the rule r is sup = |Y 0 |/|G|.
In this work the rule sets ΣK , ΣK̃ and ΣK|K̃ are generic bases and any
rule in such collections is an implication which will be further represented by
Y → Z [sup] because the confidence is always equal to 1.
274 Rokia Missaoui, Lhouari Nourine,Yoan Renaud
Fig. 1. The concept lattice B(K) corresponding to Table 1.
2.3 Illustrative Example
To further illustrate notions and properties, let us take the following exam-
ple in which a context K = (G, M, I) is given, with G = {1, 2, 3, 4, 5, 6} and
M = {b, c, d, e, f, g}. The corresponding concept lattice3 is represented with a
reduced labelling as shown by Figure 1. For example, nodes labeled with values
1 and 5 represent the object concepts ({1}, {c, d, e, f }) and ({1, 2, 5, 6}, {e, c})
respectively.
Kb c d e f g K|K̃ b c d e f g b̃ c̃ d˜ ẽ f˜ g̃
1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1
2 1 1 1 1 0 0 2 1 1 1 1 0 0 0 0 0 0 1 1
3 0 0 1 1 0 0 3 0 0 1 1 0 0 1 1 0 0 1 1
4 0 1 0 0 1 0 4 0 1 0 0 1 0 1 0 1 1 0 1
5 0 1 0 1 0 0 5 0 1 0 1 0 0 1 0 1 0 1 1
6 0 1 1 1 0 1 6 0 1 1 1 0 1 1 0 0 0 1 0
Table 1. A context K, and the apposition of K and its complementary context K̃.
A first glance at Table 2 which provides the complete set of implications
generated from K|K̃ shown in Table 1 indicates that the positive implications
3
The lattice is constructed using the SourceForge project called Concept Explorer
[22].
An Exhaustive Generation of Mixed and Purely Negative Implications ... 275
Positive implications Negative implications A subset of implications in
ΣK ΣK̃ ΣK|K̃
d → e[0.66] d˜ → b̃g̃[0.33] f˜ → e[0.66] bb̃ → M M̃ [0]
f → c[0.66] c̃ → b̃f˜g̃[0.16] dg̃ → e[0.50] cc̃ → M M̃ [0]
cd → e[0.50] d˜f˜ → b̃g̃[0.16] b̃f˜ → e[0.50] dd˜ → M M̃ [0]
df → ce[0.16] ˜
ẽ → b̃dg̃[0.16] cdg̃ → e[0.33] eẽ → M M̃ [0]
ef → cd[0.16] c̃d˜ → b̃ẽf˜g̃[0] db̃f˜ → e[0.33] f f˜ → M M̃ [0]
b → cde[0.16] c̃ẽ → b̃d˜f˜g̃[0] df → ceb̃g̃[0.16] gg̃ → M M̃ [0]
g → cde[0.16] ẽf˜ → b̃c̃dg̃[0]
˜ cdb̃f˜ → eg[0.16] bf → M M̃ [0]
bf → cdeg[0] cdb̃g̃ → ef [0.16] bc̃ → M M̃ [0]
bg → cdef [0] cdf˜g̃ → be[0.16] ˜ → M M̃ [0]
def
f g → bcde[0] db̃f˜g̃ → ec̃[0.16] cdb̃f˜g̃ → M M̃ [0]
.. ..
. .
Table 2. Positive, negative and mixed implications of Table 1.
in ΣK do not convey interesting information about the absence of some items,
and implications with a null support seem useless. However, the set ΣK|K̃ brings
additional associations about the absence of items (e.g., f˜ → e [0.66]), and we
will see later that implications with a null support can be exploited to generate
mixed implications (see Property 3 and Table 4 in the appendix).
3 Related work
In the area of data mining, the notion of negative associations (relationships)
between itemsets was initially discussed by Brin and Motwani [6] who proposed
a procedure that exploits the Chi-square test to search for a border between
correlated and uncorrelated elements in the itemset lattice. Many studies rec-
ognize that mining rules with negation (i.e., rules that contain negative items)
is a very challenging problem [5] and there is an urgent need to define prun-
ing strategies, procedures and interestingness measures (other than confidence)
to generate negative association rules in an efficient and correct way [6, 20, 21].
For example, Wu et al. [21] define a new algorithm for negative association rule
generation as well as a new quality measure for an efficient pruning of gener-
ated frequent itemsets. In [16], positive frequent itemsets are combined with
background knowledge to mine negative association rules, while in [3] a new
technique based on Kullback-Leibler divergence is defined. Teng et al. [18] ex-
ploit negative rules for item substitution (i.e., replacing the purchase of an item
with another one) in market basket analysis [1] and propose an approach to
identify substitution rules in two steps: the first one identifies concrete itemsets
(i.e., frequent itemsets whose elements are statistically dependent among a large
number of frequent itemsets) while the second step generates substitution rules.
276 Rokia Missaoui, Lhouari Nourine,Yoan Renaud
Two concrete itemsets Y and Z constitute a substitution rule, denoted by Y . Z
to mean that Y is a substitute for Z if and only if Y and Z are negatively
correlated and the negative association rule Y → Z̃ holds.
The notion of negative rules has different meanings. In [16], it represents rules
of the form Y 9 Z whose actual support deviates at least M inRI × M inSup
from its expected support (based on the support of items in closed itemsets and
the taxonomy on attributes). M inRI and M inSup correspond to the minimal
value of an interest measure RI and the support, respectively. In [5], the rule
Y → Z̃ has the standard meaning, i.e., the presence of items in Y implies the
absence of all items in Z.
In [12] the problem of computing the generic basis of positive, negative and
mixed implications from a given input is analyzed and a set of situations are
identified based on the type of available input (e.g., the formal context K =
(G, M, I), the set ΣK of positive implications, the concept lattice B(K)) and the
sort of output to produce (e.g., B(K), the set of negative implications ΣK̃ , the
whole set of implications ΣK|K̃ ). Inference rules to produce a non exhaustive set
of mixed association rules, using either positive, negative or mixed implications
are also defined. A more elaborated inference system is described in [15] and
summarized in the appendix.
4 Problem Statement
We have noticed that the implications of the form AC̃ → x [sup] such that
|A| > 1 and |C̃| > 1 and sup 6= 0 can never be deduced from the inference
axioms initially presented in [12] since the attributes are moved (and negated)
only one at a time from one side to another side of a given implication (see the
first five rows of Table 4 in the appendix). This leads us to propose an additional
inference rule (see the last axiom in Table 4) and later on generalize the idea
to characterize implications of the form AB̃ → M M̃ [0] such that the former
implications could be retrieved. This means that we need to find all keys in K|K̃,
including those that contain at least two positive items and two negative ones.
To handle the problem of generating purely negative and mixed implications
out of purely positive ones in an exhaustive way, we proceed in two steps: (i)
we first find a characterization of keys in K|K̃, and then (ii) show that such a
characterization can be combined with Property 3 (previously presented in [12])
to infer the set of negative and mixed implications in a sound and complete
manner.
The first step can be stated by Problem 1 while the second one can by
expressed by Problem 2.
Problem 1. : Key Computation (KC)
Instance: A set ΣK of positive implications of a reduced context.
Question: Compute the set K of keys in K|K̃.
The reason for imposing a reduced context comes from the fact that an
implication base ΣK may correspond to many contexts, and hence the apposition
An Exhaustive Generation of Mixed and Purely Negative Implications ... 277
of each context with its complementary one may generate more than one set
ΣK|K̃ .
Problem 2. : Exhaustive Implication Computation (EIC)
Instance: An implication set ΣK of a reduced context and the set K of keys.
Question: Compute a cover of ΣK|K̃ .
First, we need to characterize join-irreducible concepts to further identify
keys.
Property 1. Let F ⊆ M . F is the intent of a join-irreducible concept in K iff F
is closed and ∃ b ∈ M \F such that ∀ x ∈ M \F F x → b ∈ ΣK .
Proof. Suppose that F is the intent of a join-irreducible concept. Then, there
exists a unique closed set B that covers F . Let b ∈ B\A. Then, any closed
set containing both F and an element of M \F , contains also b. Therefore, ∀
x ∈ M \F F x → b ∈ ΣK .
Now suppose that there exists an element b ∈ M \F such that ∀ x ∈ M \F
F x → b ∈ ΣK . Then F is covered by a unique closed set. So if F is closed, then
it is the intent of a join-irreducible concept.
In our illustrative example, there are six join-irreducible concepts. One of
them is the concept ({1, 2, 5, 6}, {c, e}) since ∀ x ∈ {b, d, f, g} the implication
cex → d holds in ΣK .
5 Inference System
In the following we establish a corollary which helps generate all the implications
whose left-hand side is a key in M M̃ . To that end, we first state the property
below which is based on the fact that a key cannot be larger than the intent of
a join-irreducible concept since its closure is the intent of the lattice infimum.
Property 2. Let AB̃ ⊆ M M̃ . Then, AB̃ → M M̃ [0] iff 6 ∃ F an intent of a join-
irreducible concept in K such that A ⊆ F and B ∩ F = ∅.
Proof. A set AB̃ is a key of K|K̃ iff there is no intent of a join-irreducible
concept containing AB̃. We only need to note that F is the intent of a join-
irreducible concept of K such that A ⊆ F and B ∩ F = ∅ iff F B̃ is the intent of
a join-irreducible concept in K|K̃.
For example, the set AB̃ = {c, d, b̃, f˜} is not a key in K|K̃ since among the
join-irreducible concepts that have an intent that includes A = {c, d}, there is
a concept, namely ({6}, {c, d, e, g}, whose intent has an empty intersection with
B = {b, f }. However, the set AB̃ = {c, d, b̃, f˜, g̃} is a key in K|K̃.
The corollary below follows directly from the two preceding properties.
Corollary 1. Let AB̃ ⊆ M M̃ . Then, AB̃ → M M̃ [0] iff 6 ∃ a closed set F ⊆ M
such that A ⊆ F , B ∩ F = ∅ and ∀ x ∈ M \F Ax → b with b ∈ M \F .
278 Rokia Missaoui, Lhouari Nourine,Yoan Renaud
Implications of the form: {ai a˜i } → M M̃ [0] ∀i ∈ {1 . . . k} are a special case
of implications involving a key, and hence the contradiction axiom (see the third
axiom in the appendix) which states that one cannot have both item ai and its
negation a˜i becomes redundant in our new inference system.
We recall a property from [12, 15] which allows us to generate new implica-
tions (see the fifth axiom in the appendix).
Property 3. Let Ax ⊆ M M̃ . Then, Ax → M M̃ [0] ⇔ A → x̃ [sup].
Theorem 1. Let ΣK be a non empty set of positive implications in K. Then,
Corollary 1 and Property 3 allow the inference of a sound and complete set of
implications in K|K̃.
Proof. Corollary 1 generates all the keys in K|K̃, including {ai a˜i } → M M̃ [0]
∀i ∈ {1 . . . k}. Each purely negative implication and each mixed implication can
be generated from keys using Property 3.
As an illustration, the purely negative implication d˜ → b̃g̃ can be inferred from
bd˜ → M M̃ [0] and g d˜ → M M̃ [0] using Property 3. Moreover, the mixed impli-
cation cdb̃f˜g̃ → M M̃ [0] holds in ΣK|K̃ since there does not exist F , an intent
of a join-irreducible concept such that {cd} ⊆ F and {cd} ∩ {bf g} = ∅. Using
Property 3, the mixed implication involving a key cdb̃f˜g̃ → M M̃ [0] leads to
five other mixed implications by moving one attribute at a time (and taking its
negation) from the left-hand side to the right-hand side of the implication (e.g.,
cdb̃f˜ → g[0.16]). It is easy to see that the last axiom presented in Table 4 of the
appendix allows the inference of cdb̃f˜ → g[0.16] which leads to cdb̃f˜g̃ → M M̃ [0]
by applying Property 3.
6 Empty Implication Set
There are formal contexts such that their corresponding positive (respectively
negative) implication set is empty. A special case of such contexts is the one
with the following features: it has the same number of objects and attributes,
and each object differs from each one of the other objects by only one attribute
(see Table 3). The corresponding concept lattice is a Boolean one. In such a
context K = (G, M, I) where M = {a1 , ..., ak } and ΣK is empty, the set of purely
negative implications is ΣK̃ = {a˜i a˜j } → M M̃ [0], ∀i ∈ {1..k}, ∀j ∈ {1..k}, i 6= j.
K and K̃ a b c d ã b̃ c̃ d˜
1 0 1 1 1 1 0 0 0
2 1 0 1 1 0 1 0 0
3 1 1 0 1 0 0 1 0
4 1 1 1 0 0 0 0 1
Table 3. A context K with an empty ΣK and its complementary context K̃.
An Exhaustive Generation of Mixed and Purely Negative Implications ... 279
By applying Property 3 to implications in ΣK̃ , one can infer the following
implications: a˜i → aj , ∀i ∈ {1..k}, ∀j ∈ {1..k}, i 6= j.
Even though ΣK is empty, we can observe that the trivial implication {a1 ...ak } →
M M̃ [0] holds and will generate through Property 3 the implications: M \ai → a˜i ,
∀i ∈ {1..k}.
The whole set of implications that can be generated when ΣK = ∅ is then as
follows:
ΣK|K̃ = {a˜i a˜j → M M̃ [0], ∀i ∈ {1..k}, ∀j ∈ {1..k}, i 6= j}
∪ {a˜i → aj , ∀i ∈ {1..k}, ∀j ∈ {1..k}, i 6= j}
∪ {a1 ...ak → M M̃ [0]}
∪ {M \ai → a˜i , ∀i ∈ {1..k}}
∪ {ai a˜i } → M M̃ [0], ∀i ∈ {1..k}}
The second and fourth sets of implications are inferred from the first and third
ones respectively by moving (and negating) one attribute from the left side to
the right side of the implications (see Property 3). The fifth group of implica-
tions reflects contradiction (see the third axiom in the appendix) and holds for
any context.
7 Conclusion
This paper is an extension to our first investigation [12] on generating implica-
tions with negation. It aims to generate the exhaustive set of rules ΣK|K̃ when
only the set of positive implications ΣK is given, provided that the formal con-
text K is reduced.
Our contribution lies in the proposal of a property that identifies all the keys
AB̃ in K|K̃ where A ∈ M and B̃ ∈ M̃ and the presentation of a new inference
rule (see Corollary 1), which together with Property 3, provides a sound and
complete inference system for the generation of mixed rules. A special case when
ΣK is empty has been analyzed.
We are currently designing procedures that efficiently compute the set of
implications ΣK|K̃ and the closure of a set AB̃ when ΣK is given.
Acknowledgment
The first author acknowledges the financial support of the Natural Sciences and
Engineering Research Council of Canada (NSERC). All the authors would like
to thank the anonymous referees for their helpful suggestions and are grateful
to Sebastian Rudolph and Léonard Kwuida for fruitful discussions about empty
implication sets.
References
1. R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of
items in large databases. pages 207–216, May 1993.
280 Rokia Missaoui, Lhouari Nourine,Yoan Renaud
2. Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association
rules. pages 487–499, September 1994.
3. Leila Nemmiche Alachaher and Sylvie Guillaume. Mining negative and positive
influence rules using kullback-leibler divergence. In ICCGI ’07: Proceedings of the
International Multi-Conference on Computing in the Global Information Technol-
ogy, pages 1–25, Washington, DC, USA, 2007. IEEE Computer Society.
4. Maria-Luiza Antonie and Osmar R. Zaı̈ane. Mining positive and negative associ-
ation rules: An approach for confined rules. In PKDD, pages 27–38, 2004.
5. Jean-François Boulicaut, Artur Bykowski, and Baptiste Jeudy. Towards the
tractable discovery of association rules with negations. In FQAS, pages 425–434,
2000.
6. Sergey Brin, Rajeev Motwani, and Craig Silverstein. Beyond market baskets: gen-
eralizing association rules to correlations. In SIGMOD ’97: Proceedings of the 1997
ACM SIGMOD international conference on Management of data, pages 265–276,
New York, NY, USA, 1997. ACM Press.
7. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foun-
dations. Springer-Verlag New York, Inc., 1999. Translator-C. Franzke.
8. Jean-Louis Guigues and Vincent Duquenne. Familles minimales d’implications
informatives résultant d’un tableau de données binaires. Mathématiques et Sciences
Humaines, 95(1):5–18, 1986.
9. Marzena Kryszkiewicz and Marcin Gajek. Concise representation of frequent pat-
terns based on generalized disjunction-free generators. In PAKDD ’02: Proceedings
of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data
Mining, pages 159–171, London, UK, 2002. Springer-Verlag.
10. Michael Luxenburger. Implications partielles dans un contexte. Mathématiques,
informatique et sciences humaines, 29(113):35–55, 1991.
11. Heikki Mannila and Hannu Toivonen. Multiple uses of frequent sets and condensed
representations (extended abstract). In KDD, pages 189–194, 1996.
12. Rokia Missaoui, Lhouari Nourine, and Yoan Renaud. Generating positive and
negative exact rules using formal concept analysis: Problems and solutions. In
ICFCA, pages 169–181, 2008.
13. Nicolas Pasquier, Yves Bastide, Rafik Taouil, and Lotfi Lakhal. Efficient Mining of
Association Rules Using Closed Itemset Lattices. Information Systems, 24(1):25–
46, 1999.
14. J. Pfaltz and C. Taylor. Scientific discovery through iterative transformations of
concept lattices. In Proceedings of the 1st International Workshop on Discrete
Mathematics and Data Mining, pages 65–74, April 2002.
15. Yoan Renaud. Quelques aspects algorithmiques sur les systèmes de fermeture. PhD
thesis, Université Blaise Pascal, décembre 2008.
16. Ashok Savasere, Edward Omiecinski, and Shamkant B. Navathe. Mining for strong
negative associations in a large database of customer transactions. In ICDE, pages
494–502, 1998.
17. Einoshin Suzuki. Data mining methods for discovering interesting exceptions from
an unsupervised table. J. UCS, 12(6):627–653, 2006.
18. Wei-Guang Teng, Ming-Jyh Hsieh, and Ming-Syan Chen. A statistical framework
for mining substitution rules. Knowl. Inf. Syst., 7(2):158–178, 2005.
19. Petko Valtchev, Rokia Missaoui, and Pierre Lebrun. A partition-based approach
towards constructing galois (concept) lattices. Discrete Math., 256(3):801–829,
2002.
An Exhaustive Generation of Mixed and Purely Negative Implications ... 281
20. Hao Wang, Xing Zhang, and Guoqing Chen. Mining a complete set of both positive
and negative association rules from large databases. In PAKDD, pages 777–784,
2008.
21. Xindong Wu, Chengqi Zhang, and Shichao Zhang. Efficient mining of both positive
and negative association rules. ACM Trans. Inf. Syst., 22(3):381–405, 2004.
22. Serhiy A. Yevtushenko. System of data analysis ”concept explorer”. In Proceedings
of the 7th national conference on Artificial Intelligence KII 2000, pages 127–134,
2000.
23. Mohammed Javeed Zaki and Ching-Jiu Hsiao. Charm: An efficient algorithm for
closed itemset mining. In Proceedings of the Second SIAM International Conference
on Data Mining, Arlington, VA, USA, April 11-13, 2002.
282 Rokia Missaoui, Lhouari Nourine,Yoan Renaud
Appendix: Inference Axioms
The following table summarizes the (complete and sound) inference system presented
in [15] where A ⊆ M , Ã ⊆ M̃ , x ∈ M , x̃ ⊆ M̃ and the initial context K is reduced.
The last axiom completes the set of properties and inference rules initially defined in
[12].
ID Properties and inference rules
1 ΣK ` A → x ⇔ ΣK|K̃ ` A → x; ΣK̃ ` Ã → x̃ ⇔ ΣK|K̃ ` Ã → x̃
2 ΣK ` A → M [0] ⇔ ΣK|K̃ ` A → M M̃ [0]; ΣK̃ ` Ã → M̃ [0] ⇔ ΣK|K̃ ` Ã → M M̃ [0]
3 ΣK|K̃ ` aã → M M̃ [0], ∀a ∈ M
4 ΣK ` Ax → y ⇒ ΣK|K̃ ` Aỹ → x̃; ΣK̃ ` Ãx̃ ⇒ ỹ ⇒ Ãy → x
5 ΣK ` Ax → M [0] ⇔ ΣK|K̃ ` A → x̃; ΣK̃ ` Ãx̃ ⇔ M̃ [0] ⇒ ΣK|K̃ ` Ã → x
6 ΣK|K̃ ` B → x, B ⊆ M M̃ with B = B + ∪ B − , B + ⊆ M , B − ⊆ M̃ and x ∈ M
⇔
∀y ∈ M \B + , ΣK|K̃ ` By → x and B + is not the intent of a join-irreducible concept.
Table 4. Summary of properties and inference axioms to generate ΣK|K̃ from ΣK and
ΣK̃ .