An Inference System for Exhaustive Generation of Mixed and Purely Negative Implications from Purely Positive Ones

Abstract

The objective of this article is to study the problem of generating 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 de ne a sound and complete inference system which includes a characterization of implications whose left-hand side is a key in the context KjK~ representing the apposition of the context K and its complementary K~ .

-

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 subclass of the larger and more general set of boolean association rules (i.e., rules with negation, conjunction and disjunction) [ 11 ] and can help identify unexpected (surprising) patterns in many real-life applications (e.g., ostrich is a bird that exceptionally does not y or customers who buy smoked salmon buy also caviar but not orange juice) [ 17 ]. In market basket analysis [ 1 ], rules with negation can help identify items that con ict with each other (e.g., if we buy caviar, then we do not buy canned tuna) or suggest a classi cation of customers according 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 e cient 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(KjK~ ) 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.

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 implications 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., implications in which at least a negative attribute and a positive attribute coexist), using either positive, negative or mixed implications, provided the original context K is reduced. Later on, an additional inference rule [ 15 ] has been de ned 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 KjK~ ) 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 implications 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 de ne

A0 := fa 2 M j oIa 8o 2 Ag and

B0 := fo 2 G j oIa 8a 2 Bg; 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 de nes 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 = B0 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: 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 predecessor 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 = K1jK2 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 [_M2; I1 [_I2) 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 uppercase 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, a~ stands for the negation of attribute a and means that Object o belongs to the extent of a~ i it does not belong to the extent of a, and A~ represents the set fa~ j a 62 Ag. 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 con dence of the rule, respectively. The support of a rule is de ned as P rob(Y [ Z) while the con dence is computed as the conditional probability P rob(Z=Y ).

A set of studies in FCA were conducted on the generation of concise representations 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 00nY [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 = jY 0j=jGj.

In this work the rule sets K , K~ and KjK~ are generic bases and any rule in such collections is an implication which will be further represented by Y ! Z [sup] because the con dence is always equal to 1. To further illustrate notions and properties, let us take the following example in which a context K = (G; M; I) is given, with G = f1; 2; 3; 4; 5; 6g and M = fb; c; d; e; f; gg. 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 (f1g; fc; d; e; f g) and (f1; 2; 5; 6g; fe; cg) respectively.

K b c d e f g KjK~ b c d e f g ~b c~ d~ e~ 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 rst glance at Table 2 which provides the complete set of implications generated from KjK~ shown in Table 1 indicates that the positive implications 3 The lattice is constructed using the SourceForge project called Concept Explorer [ 22 ]. Positive implications Negative implications

K K~ A subset of implications in

KjK~ d ! e[0:66] f ! c[0:66] cd ! e[0:50] df ! ce[0:16] ef ! cd[0:16] b ! cde[0:16] g ! cde[0:16] bf ! cdeg[0] bg ! cdef [0] f g ! bcde[0] in K do not convey interesting information about the absence of some items, and implications with a null support seem useless. However, the set 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). KjK~ brings 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 recognize 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 de ne pruning strategies, procedures and interestingness measures (other than con dence) to generate negative association rules in an e cient and correct way [ 6, 20, 21 ]. For example, Wu et al. [ 21 ] de ne a new algorithm for negative association rule generation as well as a new quality measure for an e cient pruning of generated 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 de ned. Teng et al. [ 18 ] exploit 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 rst one identi es 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. 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 di erent 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 identi ed 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 KjK~ ). Inference rules to produce a non exhaustive set of mixed association rules, using either positive, negative or mixed implications are also de ned. 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 ~ j j > 1 and jCj > 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 rst ve 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 nd all keys in KjK~ , 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 rst nd a characterization of keys in KjK~ , 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 rst 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 KjK~ .

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 of each context with its complementary one may generate more than one set

KjK~ .

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

KjK~ .

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 i F is closed and 9 b 2 M nF such that 8 x 2 M nF F x ! b 2 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 2 BnA. Then, any closed set containing both F and an element of M nF , contains also b. Therefore, 8 x 2 M nF F x ! b 2 K .

Now suppose that there exists an element b 2 M nF such that 8 x 2 M nF F x ! b 2 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 (f1; 2; 5; 6g; fc; eg) since 8 x 2 fb; d; f; gg 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 rst 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 in mum. Property 2. Let AB~ M M~ . Then, AB~ ! M M~ [0] i 6 9 F an intent of a joinirreducible concept in K such that A F and B \ F = ;.

Proof. A set AB~ is a key of KjK~ i there is no intent of a join-irreducible concept containing AB~. We only need to note that F is the intent of a joinirreducible concept of K such that A F and B \ F = ; i F B~ is the intent of a join-irreducible concept in KjK~ .

For example, the set AB~ = fc; d; ~b; f~g is not a key in KjK~ since among the join-irreducible concepts that have an intent that includes A = fc; dg, there is a concept, namely (f6g; fc; d; e; gg, whose intent has an empty intersection with B = fb; f g. However, the set AB~ = fc; d; ~b; f~; g~g is a key in KjK~ .

The corollary below follows directly from the two preceding properties. Corollary 1. Let AB~ M M~ . Then, AB~ ! M M~ [0] i 6 9 a closed set F such that A F , B \ F = ; and 8 x 2 M nF Ax ! b with b 2 M nF . M

Implications of the form: faia~ig ! M M~ [0] 8i 2 f1 : : : kg 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 implications (see the fth 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 KjK~ .

Proof. Corollary 1 generates all the keys in KjK~ , including faia~ig ! M M~ [0] 8i 2 f1 : : : kg. Each purely negative implication and each mixed implication can be generated from keys using Property 3.

As an illustration, the purely negative implication d~ ! ~bg~ can be inferred from bd~ ! M M~ [0] and gd~ ! M M~ [0] using Property 3. Moreover, the mixed implication cd~bf~g~ ! M M~ [0] holds in KjK~ since there does not exist F , an intent of a join-irreducible concept such that fcdg F and fcdg \ fbf gg = ;. Using Property 3, the mixed implication involving a key cd~bf~g~ ! M M~ [0] leads to ve 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., cd~bf~ ! g[0:16]). It is easy to see that the last axiom presented in Table 4 of the appendix allows the inference of cd~bf~ ! g[0:16] which leads to cd~bf~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 di ers 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 = fa1; :::; akg and K is empty, the set of purely negative implications is K~ = fa~ia~j g ! M M~ [0]; 8i 2 f1::kg; 8j 2 f1::kg; i 6= j.

By applying Property 3 to implications in K~ , one can infer the following implications: a~i ! aj ; 8i 2 f1::kg; 8j 2 f1::kg; i 6= j.

Even though K is empty, we can observe that the trivial implication fa1:::akg ! M M~ [0] holds and will generate through Property 3 the implications: M nai ! a~i, 8i 2 f1::kg.

The whole set of implications that can be generated when K = ; is then as follows:

KjK~ = fa~ia~j ! M M~ [0]; 8i 2 f1::kg; 8j 2 f1::kg; i 6= jg [ fa~i ! aj ; 8i 2 f1::kg; 8j 2 f1::kg; i 6= jg [ fa1:::ak ! M M~ [0]g [ fM nai ! a~i; 8i 2 f1::kgg [ faia~ig ! M M~ [0]; 8i 2 f1::kgg The second and fourth sets of implications are inferred from the rst 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 fth group of implications re ects contradiction (see the third axiom in the appendix) and holds for any context. 7

Conclusion This paper is an extension to our rst investigation [ 12 ] on generating implications with negation. It aims to generate the exhaustive set of rules KjK~ when only the set of positive implications K is given, provided that the formal context K is reduced.

Our contribution lies in the proposal of a property that identi es all the keys AB~ in KjK~ where A 2 M and B~ 2 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 e ciently compute the set of implications KjK~ and the closure of a set AB~ when K is given. Acknowledgment The rst author acknowledges the nancial 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 Leonard Kwuida for fruitful discussions about empty implication sets. Appendix: Inference Axioms The following table summarizes the (complete and sound) inference system presented in [ 15 ] where A M , A~ M~ , x 2 M , x~ M~ and the initial context K is reduced. The last axiom completes the set of properties and inference rules initially de ned in [ 12 ].

ID Properties and inference rules 1 2 3 4 5 6

K ` A ! x ,

KjK~ ` A ! x;

K~ ` A~ ! x~ ,

KjK~ ` A~ ! x~

KjK~ ` By ! x and B+ is not the intent of a join-irreducible concept. KjK~ from

K and

References

1. R. Agrawal , T. Imielinski , and A. Swami . Mining association rules between sets of items in large databases . pages 207 { 216 , May 1993 .

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 in uence rules using kullback-leibler divergence . In ICCGI '07: Proceedings of the International Multi-Conference on Computing in the Global Information Technology , pages 1 { 25, Washington, DC, USA, 2007 . IEEE Computer Society.

4. Maria-Luiza Antonie and Osmar R. Za ane. Mining positive and negative association rules: An approach for con ned rules . In PKDD , pages 27 { 38 , 2004 .

5. Jean-Francois 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: generalizing 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 Foundations . Springer-Verlag New York, Inc., 1999 . Translator-C. Franzke .

8. Jean-Louis Guigues and Vincent Duquenne . Familles minimales d'implications informatives resultant d'un tableau de donnees binaires . Mathematiques et Sciences Humaines , 95 ( 1 ):5{ 18 , 1986 .

9. Marzena Kryszkiewicz and Marcin Gajek . Concise representation of frequent patterns based on generalized disjunction-free generators . In PAKDD '02: Proceedings of the 6th Paci c-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 . Mathematiques, 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, Ra k Taouil, and Lot Lakhal . E cient Mining of Association Rules Using Closed Itemset Lattices . Information Systems , 24 ( 1 ): 25 { 46 , 1999 .

14. J. Pfaltz and C. Taylor . Scienti c 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 systemes de fermeture . PhD thesis , Universite Blaise Pascal, decembre 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 .

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 . E cient 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 Arti cial Intelligence KII 2000 , pages 127 { 134 , 2000 .

23. Mohammed Javeed Zaki and Ching-Jiu Hsiao . Charm: An e cient algorithm for closed itemset mining . In Proceedings of the Second SIAM International Conference on Data Mining , Arlington, VA , USA, April 11 - 13 , 2002 .

Table 4. Summary of properties and inference axioms to generate ~ . K