Using concept lattices to mine functional dependencies

Using Concept Lattices to mine functional dependencies∗ J. Baixeries Departament de LSI Universitat Polit`ecnica de Catalunya [email protected]c.es May 19, 2003 Abstract Concept Lattices have been proved to be a valuable tool to represent the knowlegde in a database. In this paper we show how functional dependencies in databases can be extracted using Concept Lattices, not preprocessing the original database, but providing a new closure operator. We also prove that this method generalizes the previous methods and closure operators that are being used to find association rules in binary databases. 1 Introduction Concept Lattices are a useful tool to represent logical implications in datasets, to find frequent itemsets, and in general, to analyze the underground knowledge that lies behind large amounts of data. Concept lattices are formed by concepts that, broadly speaking, are groups of objects classified together having common attributes. Apart from seeming to be close to the human representation of knowledge, the importance of this model relies on the fact that it is supported by a consistent mathematical theory, which is originally based on Birkhoff’s lattice theory [3], later developed by Ganter and Wille [11], as well as providing a comprehensive graphical interface, that can show structural relations in a given set of data just at a glance. This model has been successfully applied to the ”market basket analysis”, which, in data mining terminology, means the finding of sets that appear together in a large database [2]. The goal is to provide information on when the buying of an item determines that another item is likely to be bought too. Currently the main issues concerning concept lattices have been focused on finding optimal algorithmic solutions in order to compute closures [12]. Some other authors have been dealing with the incremental update of the concept lattice when the set of tuples is dynamically incremented, in order to find an optimal method to create the concept lattice in an incremental way, as well as to provide a conceptual framework [19], [16], [17]. Relating concept lattices to other theoretical frameworks has been proposed in [1], in which an equivalence between rules formed in a concept lattice out of a set of binary tuples, and Horn clauses formed out of a set of models (which is in fact the set of binary tuples seen as a set of models) has been proved. On the other hand, functional dependencies are a key factor in database design. Large amounts of literature have been devoted to this topic, starting with Codd’s pioneer work ([5]), and a complete axiomatization by Fagin, Beeri and Howard [10]. The most well known handbooks on database design also deepen into the underlying theory but from a more practical point of view ([18], [6], [7]). Although being a classical topic, functional dependencies in databases is still an active research topic, mainly in its algorithmic and complexity aspect ([14], [15], [4]), and strongly connected to learning theory [13]. A functional dependency describes the relationship between two sets of attributes with a rule X→Y, that states that the values of the set of attributes X ∗This work is supported in part by EU ESPRIT IST-1999-14186 (ALCOM-FT), MCYT TIC2002-04019-C03-01 (Moises), and matching funds TIC2000-1970-CE, and CIRIT 2001SGR-00252. 1 determine the value of the set of attributes Y. These dependencies are extremely helpful to a database designer in order to know if a database is in third Normal Form. Moreover, the authors of [8] and [9], discovered an equivalence between functional dependencies and a fragment of propositional logic. In fact, the main issue was the equivalence between the inference rules that are to be used in order to derive more functional dependencies out of a given set of functional dependencies, and the axioms that are used to form new implications in propositional calculus. In the first section of this paper, a formal description of a concept lattice will be provided, as well as a formalization of a functional dependency, just in order to standarize the notation that will be used along the paper. In the second section, a new closure operator will be presented, and some of its properties will be reviewed. In the third section, it will be proved that, given a concrete, specific closure operator, concept lattices can determine the functional dependencies in a database. In the fourth section, it will be proved that this operator generalizes the operator that has been used to find association rules in a database. 2 Definitions 2.1 Concept Lattices Let O,I, Rbe a formal context. This means that Ois a set of objects, Iis a set of attributes, and R⊆O×Iis a binary relation between sets Oand I. This formal context can be viewed as a database, as a set of observations, or as a set of models of a logical formula, among many other forms. From now on, we will use the letters X,Y,Z to denote sets of attributes, x, y, z to denote single attributes, A, B, C to denote sets of objects, and a, b, c to denote single objects. Let φ, ψ be two operators such that: •φ:P(I)→P(O). This operator returns the objects that have a relation with all the attributes of the given set of attributes, it is, φ(X)={a∈O|a, x∈R, ∀x∈X}. •ψ:P(O)→P(I). Given a set of objects, this operator returns the largest set of attributes such that all the objects have a relationship with all the attributes, it is, ψ(A)={x∈ I|a, x∈R, ∀a∈A}. Both operators follow a set of properties (for a proof for each property, please refer to [11]): •X⊆Y⇒φ(Y)⊆φ(X) •X⊆ψ(φ(X)) •φ(X)=φ(ψ(φ(X))) •A⊆B⇒ψ(B)⊆ψ(A) •A⊆φ(ψ(A)) •ψ(A)=ψ(φ(ψ(A))) •X⊆ψ(A)⇔A⊆φ(X) The pair (φ, ψ) forms what is called a Galois connection, which is a set of two operators having the following property: •A≤φ(X)⇔X≤ψ(A). (different sets of equivalent properties can be found in [11]). The fact that these two operators form a Galois connection, implies that their composition (ψ.φ and φ.ψ)formsaclosure operator (for a proof, please refer to [11]). A closure operator (ϕ) has the following properties: 2 •X⊆ϕ(X) •X⊆Y→ϕ(X)⊆ϕ(Y) •ϕ(X)=ϕ(ϕ(X)) The operator ϕ=ψ.φ will be used to induce a partition of all the possible sets of attributes in a relation in classes. The closure of a set of attributes Xwill be ϕ(X). A formal concept of (O,I, R)isapairX,Asuch that A∈Oand X∈I,andφ(X)=Aand ψ(A)=X,andletTbe the set of all formal concepts. A precise definition of a concept lattice can now be given: let Obe a set of objects, Ia set of attributes, and R⊆O×Ia binary relation, let ϕ=ψ.φ be a closure operator as previously defined, and let Bthe set of all concepts of (O, I,R), a concept lattice is the the set Bplus an infimum and a supremum given by  t∈T (Xi,A i)= t∈T Xt,φ(ψ( t∈T At)), t∈T (Xi,A i)=ψ(φ( t∈T Xt)), t∈T At where X∈P(I)andA∈P(O). In practice, the graphical concept lattice is represented as follows: the nodes (concepts) are the sets of attributes {X|X=ϕ(X)}, and the infimum is the set of attributes that has a relation with all the objects, it is, the set of attributes that appear in all the tuples (which can be eventualy empty), and the supremum is the set of all the attributes. A node Xwill be connected by a line to another node Yif it immediately includes or it is immediately included by Y. For practical reasons, the sets of objects have been erased from the concepts. The set of generators of a closure Xis Γ(X)={Y|ϕ(Y)=X,Y⊂Y:ϕ(Y)=X},which, together with its closure can form inference rules, of the kind Y→X\Ywhere Y∈Γ(X). These rules have mainly been used to find relations of the kind ”if X appears, then Y also appears”. The concept lattice thus formed explains what attributes depend on other attributes ([17]). The main limitation of this model is the fact that the tuples are binary, and not multivalued, and so, it covers a broad yet limited set of possible cases. In this paper this limitation will be overcome, since we will be dealing with multivalued databases, it is, databases in which the set of values that a relation can take is not limited to a binary domain. 2.2 Functional Dependencies Many literature has been devoted to functional dependencies. The reader can refer to [10] to find a complete and formal explanation. For the purposes of this paper, we will define the following elements: let Ibe a finite set of attributes, let Obe a finite set of objects (tuples), and let Vbe a finite set of possible values an attribute can take, and relation R(informaly, a database) is a subset of I×O×V.Foragivena∈O,a[X] is the ordered set of values that the object atakes for each x∈X(the order in the values will be according to an order induced in the set I). A functional dependency X→y,(whereXis a set of attributes, and yis a single attribute) holds in a relation Rif for all pair of tuples (objects) ai,a j:ai[X]=aj[X]→ai[y]=aj[y], it is, the set of attributes Xdetermines the value of the attribute y. A functional dependency is minimal if no dependency with a proper subset of X as antecedent and the same consequent holds. In [14] the following notation has been presented: a set of attributes can induce a partition of the tuples in classes, according to the values of the attributes, in which each class or subset in this partition will contain those tuples that have the same value for a given set of attributes X.A more formal definition of a partition ΠXis: ΠX={Pi|∀ai,a j∈Pi,a i[X]=aj[X]}, It follows that ∀Pi,P j∈ΠX,P i∩Pj=∅and that Pi=O, it is, all the sets in a given partition are disjoint, and complete. The number of classes in ΠXis |ΠX|. A partition ΠYrefines a partition ΠXiif ∀Pi∈ΠY∃Pj∈ΠXPi⊆Pj. It then follows that if ΠYrefines ΠX,then|ΠX|≤|ΠY|. Following the partition induced by a set of attributes, the following theorem relates functional dependencies and partitions: Theorem 2.1 A functional dependency X→Aholds iif |ΠX|=|ΠX∪A| (See [14] for a proof). 3 3 Concept lattices as a framework to find functional dependencies Our goal will be to provide a framework based on concept lattices that will enable us to find all minimal functional dependencies. To do so, we will provide a new Galois connection, whose composition will form a new closure operator. Using this operator, a concept lattice will be created, and then, it will be proved that the set of rules that will be extracted out of this concept lattice will be equivalent to the set of minimal functional dependencies in that database. The new operator will be able to deal with multivalued databases. It should be noted that Ganter and Wille [11] developed a method to extract the functional dependencies out of a multivalued database. The method transformed the original database DB in a new binary database DB, and then, the current analysis proceeded. The transformation basicaly consisted in intersecting all tuples with each other, and for each pair of records ri,r j∈DB ,a new record si∈DBis created in the new database, and for each single attribute x,si[x]=1if ri[x]=rj[x], zero otherwise. It is then proved that applying the current analysis to this newly created database, the resulting association rules are functional dependencies in DB. Instead of transforming the database, our aim will be to create a new closure operator. 3.1 A new closure operator ΠP(I)is the class of all possible partitions that can be induced by any set of attributes. We define the following operators: •Φ: P(I)→ΠP(I). Given a set of attributes X⊆I, it returns the partition induced by X: ΠX, it is, a set of classes. •Ψ: ΠP(I)→P(I). Given a partition ΠX, it returns a set of attributes Xsuch that ΠX=Π Xand X :X⊂X,ΠX=Π X . It is: it returns the largest set of attributes that can induce the given partition. It is worth mentioning two facts: first, this operator can eventualy be undefined, since there can be no way to partition a given set of tuples according to any set of attributes. For instance, it is not possible to partition a set of tuples into only one class, if there are no attributes that have the same value for all the tuples in the database. It follows that this operator should be carefully used in order to avoid this possibility. Second, if this set exists and is the largest one, it is unique. It can be easily proved that if two different sets X,Y have these properties (induce the partition and are the largest), then X∪Yalso has the same property, and it is larger than any of both of them. We also define an order for attributes and an order for partitions. 1. (P(I),≤), where X, Y ⊆I:X≤Yiif X⊆Y. 2. (ΠP(I),), where ΠX,ΠY⊆ΠP(I):Π XΠYiif ΠXrefines ΠY(|ΠX|≥|ΠY|). In order to prove that these operators form a Galois connection, we need the to show different propositions: Proposition 3.1 Y⊆X→ΠXrefines ΠY Proof: If we suppose that it is not true, then ΠXdoes not refine ΠY. It means that at least there will be two objects a1,a 2that will belong to two different classes in ΠYand to the same class on ΠX. Then, a1[X]=a2[X]. And if they belong to different classes in ΠY,itmeansthat ∃Z⊆Ysuch that a1[Z]=a2[Z]. Therefore, Z⊆Yand ZX, but it contradicts the previous assumption Y⊆X. Proposition 3.2 If X,Y ⊆I, are both the maximum sets of attributes that induce the classes ΠX,ΠYand if ΠXrefines ΠY,then,Y⊆X. 4 Proof: Let PYbe a class in ΠY,andletPXbe a class in ΠXsuch that PX⊆PY. Let us suppose that that X⊂Y. It implies that ∃Z∈Ysuch that Z/∈X.SincePXbelongs to a class, it means that ∀a1,a 2∈PX,a 1[X]=a2[X], and since Xis the maximum class that induces ΠX, it follows that there is no other attribute Zwhich is not included in Xsuch that a1[X∪Z]=a2[X∪Z]. It contradicts our previous assumption X⊂Yand ∀a1,a 2∈PY,a 1[Y]=a2[Y] Proposition 3.3 Given a set of attributes Xand y∈I,if|ΠX|=|ΠX∪{y}|,then,ΠX=Π X∪{y} Proof: Given a partition ΠX, if we add an attribute yto X, the partition ΠX∪{y}will be a refinement of ΠX.Since|ΠX|=|ΠX∪{y}|, it follows that all the classes in ΠXmust be the same as in ΠX∪{y}. Proposition 3.4 |ΠX|≤|ΠX∪{y}|. Proof: Let us suppose that |ΠX|>|ΠX∪{y}|. There will be two elements a1,a 2that are in two different classes in ΠX, but that will be in the same class in ΠX∪{y}, which means that they will have the same value for the attributes X∪{y}. But this contradicts the previous assumption that they were in different classes in ΠX. We are now able to prove that the previously defined operators form a Galois connection. Proposition 3.5 (Φ,≤)and (Ψ,), form a Galois Connection. Given X1,X 2,Y ⊆Iand A1,A 2,B ∈ΠP(I), the following propositions must be proved: 1. x1≤x2→Φ(X1)Φ(X2). Proof: Easily by proposition [3.1]. 2. A1A2→Ψ(A1)≥Ψ(A2). Proof: Easily by proposition [3.2]. 3. Y≤Ψ(Φ(Y)). Proof: Φ(Y)=Π Y,Ψ(ΠY)=Z,beingZthe greatest set such that ΠZ=Π Y. Since Zis the greatest, it follows that Z≥Y. 4. PΦ(Ψ(B)). Proof: Ψ(B)=X,beingXthe greatest set such that ΠX=P,andthen, Φ(X)=Π X=P. The fact that these operators form a Galois connection, enables us to prove that their composition is a closure operator. Proposition 3.6 Since Φand Ψform a Galois Connection, Γ=Ψ.Φ,isaclosureoperator. The proof is given in [11] (proposition 8). 4 Concept lattices and functional dependencies Accordingtothenewlycreated closure operator Γ = Φ.Ψ, we can generate a closure lattice, and then form the rules out of each closed set and its generators. We claim that: Theorem 4.1 The set of rules of a concept lattice formed by the closure operator Γis logically equivalent to the set of minimal functional dependencies (both sets are logically implied by each other). Proof: ⇒) Any minimal functional dependency will be implied by a rule from the concept lattice formed by the closure operator Γ: Let X→ybe a functional dependency. Then, |ΠX|=|ΠX∪{y}|, and, by [3.3], ΠX=Π X∪{y}. Since the partitions induced by both Xand X∪{y}are the same, they belong to the same closure (by construction of Γ). Let Z=Γ(X)=Γ(X∪{y}). Since X→yis minimal, X⊂Xsuch that |Π X|=|ΠX∪{y}|, which means that Xis a generator of 5 Z. By construction of the concept lattice, the following rule will be formed: X→Z\X.Since y∈Z\X, this rule in the concept lattice will imply the functional dependency. ⇐) Any rule in the concept lattice will be implied by a (set of) functional dependency(ies): Let Xbe a minimal generator of a concept Γ(X). Then, the rule X→Γ(X)\Xwill be formed by construction of the Concept Lattice. Let Γ(X)\X=Z.SinceXis a generator, then X⊂X such that Γ(X)=Γ(X). Therefore, if the generated rule is a functional dependency, it will be minimal. Let Z={z1,z 2,...,z n}, then we need to prove that the functional dependencies X→z1,X → z2...,X →znwill hold, since X→z1,X →z2...,X →zn|=X→Z. The proof is for a given X→zi. Let us suppose that X→zidoes not hold: it means that |ΠX|<|ΠX∪{zi}|.Butwe know that |ΠX|=|ΠZ∪X|, and that since zi∈Z, then by [3.1] |ΠX∪{zi}|≤|ΠX∪Z|,whichisa contradiction. Analogous reasoning can be stated for all zi∈Z. AC B B C B A d ependencies of the BataBase S et of minimal functional A B C 1 1 2 1 2 5 3 3 7 9 7 7 1 2 3 4 id Multivalued DataBase B AC AC B Set of rules constructed out of the Concept Lattice Concept Lattice induced by the DataBase B C B A B A C A B C AC Example of how the proposed closure operator works 5 Generalization of the finding of association rules With the next theorem, it will be proved that the closure operator defined in the previous section generalizes the closure operator ϕwhich has been presented in section 2.1, and thus, we will able to affirm that in fact, the analysis of what has been performed with concept lattices is a subcase of the finding of functional dependencies in a database. Since in the classical approach we have been dealing with binary relations (databases), and in the new approach we are dealing with multivalued relations, we need a function to translate this difference, which is the following: Definition 5.1 For partitions of objects over the domain V={0,1},letf:Π P(I)→ΠP(I)be a function such that given ΠXreturns a set Pi∈ΠXsuch that ∀o∈Pi,o[X]={11 ...1},orthe empty set otherwise. We are now ready to see how our method generalizes the former one: Theorem 5.2 The operator Γ=Ψ.f.Φcreates the same set of rules out of a set of models that the operator defined in current concept lattice literature (ϕ). Proof: We only need to prove that ∀X⊆I:ϕ(X)=Γ (X). Let ϕ=ψ.φ.Byconstruction, φ(X) is the collection of objects such that ∀o∈φ(X),o[X]={11 ...1}.Andψ(φ(X)) is the largest set of objects such that complies with the former condition. On the other hand, we have that Φ(X) is the partition induced by X=x1,...x n. The function ffilters all the sets of objects, and retains the one such that ∀o∈xi,x i[X]={111 ...1}.Since all possible values are {0,1}, this possibility holds. Then, Ψ(f(Φ(X))) returns the largest set of attributes that induces a set of objects such that ∀o∈φ(X),o[X]={111 ...1}. 6 References [1] Balc´azar, J.L., Baixeries J. Discrete Deterministic Data Mining as Knowledge Compilation. Workshop on Discrete Mathematics and Data Mining in SIAM International Conference on Data Mining (2003). [2] Bastide Y., Pasquier N., Taouil R., Stumme G., Lakhal L. Mining Minimal Non-Redundant Association Rules using Closed Itemsets. Proc. of the 1st Int’l Conf. on Computational Logic, num. 1861, Lectures Notes in Artificial Intelligence, Springer, july 2000, pages 972-986. [3] Birkhoff G. Lattice Theory, first edition. Amer. Math. Soc. Coll. Publ. 25, Providence, R.I. 1973. [4] Castellanos M. and Saltor F. Extraction of Data Dependencies. Information Modelling and Knowledge Bases V. IOS Press, Amsterdam, 1994, pp. 400-420. [5] Codd, E. F. A relational model for large shared database banks. Communications ACM 16, 6 (June 1970), 377 - 387. [6] Date C.J. Introduction to Database Systems. Addison-Wesley, 7 edition, 2000. [7] Elmasri R., Navathe S. B. Fundamentals of Database Systems. 2nd Edition. Benjamin/Cummings 1994 [8] Fagin R. Functional dependencies in a relational database and propositional logic.IBMJ. Research and Development 21, 6, Nov. 1977, pp. 534-544. [9] Fagin R., Sagiv Y., Delobel D., and Stott Parker D. An equivalence between relational database dependencies and a fragment of propositional logic. Jr. J. ACM 28, 3, July 1981, pp. 435-453. Corrigendum: J. ACM 34, 4, Oct. 1987, pp. 1016-1018. [10] Fagin R., Beeri C., Howard J. H. A complete axiomatization for functional and multivalued dependencies in database relations. Jr. Proc. 1977 ACM SIGMOD Symposium, ed. D. C. P. Smith, Toronto, pp. 47-61. [11] Ganter, B., Wille R. Formal Concept Analysis. Mathematical Foundations. Springer, 1999. [12] Godin, R. and Missaoui, R. An Incremental Concept Formation Approach for Learning from Databases. Theoretical Computer Science, Special Issue on Formal Methods in Databases and Software Engineering, 133, 387-419. [13] Hermo M. and Lav´ın V. Learning Minimal Covers of Functional Dependencies with Queries. Lecture Notes in Artificial Intelligence. Proceedings of ALT’99, Vol. 1720, Springer (1999). [14] Huhtala Y., Karkkainen J., Porkka P., Toivonen H. TANE: An Efficient Algorithm for Discovering Functional and Approximate Dependencies. The Computer Journal 42(2): 100 - 111, 1999. [15] Kivinen J. and Mannila H. Approximate inference of functional dependencies from relations. Theoretical Computer Science 149(1) (1995), 129-149. [16] Pfaltz, J.L. Transformations of Concept Graphs: An Approach to Empirical Induction.2nd International Workshop on Graph Transformation and Visual Modeling Techniques. GTVM 2001, Satellite Workshop of ICALP 2001, Crete, Greece. Pages 320-326. July 2001. [17] Pfaltz, J.L., Taylor, C.M. Scientific Discovery through Iterative Transformations of Concept Lattices. Workshop on Discrete Mathematics and Data Mining at 2nd SIAM Conference on Data Mining, Arlington. Pages 65-74. April 2002. 7 [18] Ullman J.D. Principles of Database and Knowledge-Base Systems. Computer Science Press, Inc. 1988. [19] Valtchev P., Missaoui R. Building Galois (Concept) Lattices from Parts: Generalizing the Incremental Approach. Proceedings of the ICCS 2001, LNCS 2120, Springer Verlag, pp. 290303, Stanford (CA), 2001. 8