Description logics are a family of logic-based formalisms used to represent knowledge and reason on it. That knowledge, under the form of concepts and relationships between them called terminological axioms, is usually manually entered and used to describe objects in a given domain. That operation being tiresome, we would like to automatically learn those relationships from the set of instances using datamining techniques. In this paper, we study association rules mining in the description logic EL. First, we characterize the set of all possible concepts in a given EL language. Second, we use those characteristics to develop an algorithm using formal concept analysis to mine the rules more e ciently.
Ontologies are knowledge representation tools used in various domains of application. The semantic web, for example, makes an extensive use of them. They are essentially composed of a list of concepts relevant to a particular domain and relations (mainly inclusion and equivalence, i.e. hierarchical relations) existing between them. Description Logics (DL) are increasingly popular logical frameworks used to represent ontologies and on which is based the OWL1 language for the semantic Web. They have a great representation power and allow powerful reasoning tools. However, the construction of ontologies, usually performed manually by knowledge engineers, is both a tedious and tricky operation.
set of relations between concepts. in order to facilitate this step, we propose to automatize, at least partially, the process of relation generation.
ical framework that also deals with concepts and their hierarchical relationships.
1 OWL is an acronym for Ontology Web Language, which is a W3C standard
formalisms, it would be interesting to combine them both and draw bene ts from their mutual advantages. This combination has already been investigated and two main approaches exist. The rst integrates operators of FCA to the
knowledge base expressed in DL [
We claim that, by using the speci c lattice structure of the set of concepts of description logics, we will be able to modify classical FCA algorithms in order to build complete and consistent sets of terminological axioms from object descriptions given as assertions. This work, which constitutes a rst attempt in this direction, will make use of a simple description logic, which is E L. But, the approach is not restricted to E L; it will certainly be possible to generalize it to other DL, which will be investigated in further work.
four parts. The rst brie y recalls the usual de nitions in both Description Logics and Formal Concept Analysis, the second characterizes the structure of the set of E L-concepts making use of the function that is the set of subsets of incomparable elements of a language, the third describes a simple association rule learning algorithm that works within the set of E L-concepts previously described. It then studies the properties of the set of terminological axioms that it generates. The last part is dedicated to a brief example, which illustrates the di erent notions presented in this paper. 2 2.1
De nitions and Recalls
and reason on knowledge. Syntactically, every description logic language makes use of a set of concept names NC , a set of role names NR and a set of object names
short, concepts. The set of constructors used de nes the language's expression power and the complexity of its reasoning procedures. In this paper, we will consider the logic E L. In it, every concept name is a concept description and, for any concept descriptions A and B and any role r, AuB and 9r:A are also concept descriptions. Having only two constructors, this logic is one of the simplest.
I = ( I ; :I ) where I is a set of objects called the domain and :I a function mapping every concept name C to a subset CI of I and every role name r to a binary relation rI I objects which belong to them.
between concept descriptions. Given two concept descriptions C and D, we say that D subsumes C (C v D) if the set of objects belonging to C is included in the set of objects belonging to D (CI DI ) for all interpretations I. For a given TBox T , we say that D subsumes C with respect to T (C vT D) if CI DI for every model of T . If C v D and D v C, it gives the de nition C D. Constructions such as C v D and C D expressing subsumption relations are called terminological axioms.
2.2
In formal concept analysis (FCA), we call formal context a triplet (O; A; R) where O is a set of objects, A a set of attributes and R a binary relation between objects and attributes. We say here that (o; a) 2 R means that a describes o.
a2A o2O
:0 : 2A 7! 2O A0 = \ fo 2 O j (o; a) 2 Rg :0 : 2O 7! 2A O0 = \ fa 2 A j (o; a) 2 Rg (1) (2)
set of attributes describing every object of O. If A B, then B0 A0 and if
A formal concept is de ned as a pair (E; I) 2 AO 2A where E = I0 and I = E0. We say that E and I are closed. E and I are respectively called the extent and the intent of the concept. In order to prevent confusion, formal concept will not be abbreviated and the term concept will be used exclusively for DL-concepts.
We call F C(O; A; R) the set of formal concepts we can nd in (O; A; R).
as (E; I) < (F; J ) , (F E and I J ) and the pair (F C(O; A; R); <) satis es the properties of a complete lattice. Such a lattice is called a concept (or Galois) lattice. For example, for a formal context in which O = fa; b; c; d; eg, A = f1; 2; 3; 4; 5g and R = f(a; 2), (a; 4), (b; 3), (b; 5), (c; 1), (c; 2), (c; 4), (d; 2), (d; 3), (e; 2), (e; 4)g we obtain the following concept lattice.
({a,b,c,d,e},{}) ({a,c,e},{2,4})
({b,d},{3}) ({c},{1,2,4}) ({b},{3,5})
({d},{2,3}) ({},{1,2,3,4,5})
pairs (B; C), often written B ! C. An implication B ! C holds in a context if every object described by every attribute in B is also described by every attribute in C.
De nition 1. We say that a set X 2 A respects an implication B ! C if B X implies C X.
An implication B ! C follows from a set of implications L if every X 2 A that respects every implication in L respects B ! C. A set L of implications is then called a basis if every implication in L holds in the context and every implication that holds in the context follows from L.
It is a known fact that fX ! X00 j X Ag is an implicational basis which means that, in order to obtain a basis of minimal cardinality, we need only to nd implications whose right-hand side are concept intents. Finding suitable left-hand side has thus been the subject of many works.
De nition 2. A set X 2 A is a pseudo-intent of the context (O; A; R) if X is not a concept intent and, for all pseudo-intent Y X, Y 00 X. De nition 3. The set of implications fX ! X00 j X is a pseudo-intentg is called a Duquenne-Guigues Basis.
3
The Set of Concept Descriptions
of the set of concepts one can build with the description logic E L.
We will use to denote the set of terminological axioms A v B in an acyclic TBox T . NC = AC [ DC will denote the set of concept names used in T with
the left hand side of de nitions. The set of pairs (C1; C2) such as C1 C2 will be called Def (T ). induces a partial order on the set of equivalence classes of concepts, noted NC , used in axioms (if (x u y v z) 2 , we will consider there is some d in DC such as d x u y). We will simply use b a for [a] v [b] . (NC ; ) is then a partially ordered set such as, for all x in NC , [>] [x] .
containing a unique representative of each equivalence class together with the order . Obviously, CN 0 is isomorphic to (NC ; ).
NC , NR and the constructors u and 9. Suppose there are two concepts A and B such as A v B. This means that AI BI so A u B A. Those two concept descriptions being equivalent we consider they are the same and we do not want to include both of them in the set of possible concepts. As such, we want the set of concepts resulting from the conjunction of incomparable elements. De nition 4. We call (CN 0) = fX CN 0 j x 2 X ^ y 2 X ) xjjyg the set of subsets of incomparable elements of CN 0
We call (CN 0) the set of subsets of incomparable elements of CN 0 and uA the concept built from the conjunction of the elements of A. For any two elements C; D 2 (CN 0), we say that C D if and only if uD v uC. That is, C D if and only if for every element c 2 C there is some d 2 D such as c d. Evidently, (CN 0) is isomorphic to the set of ideals of CN 0 ordered by inclusion and its elements are the sets of maximal elements of those ideals.
(CN 0) is then a distributive lattice.
Proposition 1. For any two elements A; B 2 (CN 0), A ^ B = M ax(fx 2 CN 0 j 9a 2 A; 9b 2 B; x a & x bg) and A _ B = M ax(A [ B).
u(A ^ B) corresponds to the least common subsumer of uA and uB and u(A _ B) to the most speci c concept subsumed by uA and uB. They can be easily computed from CN 0.
(CN 0) being nite and distributive, for all A and B in (CN 0), there is a least element X such as A _ X B called di erence and noted B n A. It is equal to M ax(# Bn # A) where # A is the set of elements lower or equal to elements of A in CN 0.
Proposition 2. For a given linear extension of CN 0, the relation A B , B n A = M ax (B) de nes a spanning tree of the covering graph of (CN 0).
The spanning tree gives us, for every element A 2 from f>g to A in which A B ) A B.
(CN 0) is the set of di erent conjunctions of concept names based on the subsumption relation. However, the TBox can also contain equivalences between elements of (CN 0). If (A; B u C) 2 Def (T ) then B A and C A in CN 0. In (CN 0), fAg is thus strictly greater than fB; Cg. Those two concepts being equivalent, every element greater or equal to fB; Cg and lower than fAg is considered redundant.
De nition 5. (CN 0)Def(T ) = (CN 0) n fB j (A; B) 2 Def (T )g is the set of subsets of incomparable elements of CN 0 without the elements corresponding to right-hand sides of de nitions of (C; X )Def(T ) the TBox. (CN 0), a unique path Proposition 3. For any two elements A; B 2 (CN 0)Def(T ) is equal to A ^ B in (CN 0). (CN 0)Def(T ), A ^ B in Proposition 4. For all A and B in (CN 0)Def(T ), the di erence A n B in (CN 0) is an element of (CN 0)Def(T ).
These operations on (CN 0)Def(T ) are thus the same than on (CN 0). The di erences appear when we try to compute the upper cover of an element D, i.e. elements immediately greater than D. We call Cand { for candidate { the set of minimal elements not lower than elements of D in CN 0. In (CN 0), the upper cover of D is then fM ax(D [ c) j c 2 Candg. In (CN 0)Def(T ), if there is some (L; R) 2 Def (T ) such as L M ax(D [ c) R, c must be removed from the list of candidates and L added if it is minimal in Cand n c. In order to nd the elements following D in the spanning tree of (CN 0)Def(T ) induced by some it would then be su cient to remove the candidates c such as c d for some d in D. The algorithm is as follows :
Require: CN n, D 1: Cand = fc 2 CN n j c 2 M in(CN 0n # D) and 8d 2 D; c 2: for each c 2 Cand do 3: if 9(L; R) 2 Def (T ) such as L M ax(D [ c) 4: Cand = M in((Cand n c) [ L) 5: end if 6: end for 7: Return fM ax(D [ c) j c 2 Candg R then dg
Now, (CN 0)Def(T ) is only the lattice of concepts built from a conjunction of concept name without roles. However, it gives us informations on the structure of the set of role-concepts. We know that, for a given role r, A v B ) 9r:A v 9r:B. The partially ordered set of roles of a depth 1 is then isomorphic to (CN 0)Def(T ). We use CNr1 to denote it. If CN 1 = CN 0 SjiN=R1j CNr1i is the set of both concept names and roles of depth 1 together with the partial order induced by , then (CN 1)Def(T ) is the lattice of concepts containing roles up to a depth 1. Recursively, (CN n)Def(T ) where CN n = CN 0 SjiN=R1j CNrni with CNrni isomorphic to (CN n 1)Def(T ) is the set of every possible concept descriptions up to an arbitrary role depth n. 4
Learning Axioms with Formal Concept Analysis
As we said previously, we take the approach of creating a formal context
corresponding to the DL-objects we want to manipulate. More precisely, we use the
formal context (O; A; R) where O is a set of objects, A = (CN n)Def(T ) is the
set of every possible concept descriptions de ned in Section 2.2 and R O A
is the relation associating objects to the most speci c concept to which they
belong. In that respect, it is very similar to contexts from Logical Concept
Analysis [
and
:0 : A 7! 2O X0 = fo 2 O j oRa ) X
ag :0 : 2O 7! A O0 = ^fa 2 A j o 2 O ) oRag (3) (4)
Now, if we want to get implications of the form X ! X00 n X, we cannot use the set-theoretic di erence directly. The di erence B n A in the distributive lattice de ned in the previous section corresponds to the most general concept whose conjunction with A would be more speci c than B. It can also be seen intuitively as the part of B not covered by A. Thus, in the remainder of this work, we will use this de nition of the di erence.
By using the structure of (CN n)Def(T ), we can enumerate concept descriptions and get a set of implications by using the following algorithm :
Require: CN n, 1: Open = ff>gg 2: for every minimal element X of minimal role depth in Open do 3: C = X00 4: if C 6= X then 5: Update CN n with X ! C n X 6: Add elements following X in the spanning tree of (CN n)def(T ) to Open 7: end if 8: end for
Beginning with f>g, the least element of (CN n)def(T ), we classically compute its closure. We then compute the closure of every element of (CN n)def(T ) immediately greater than f>g and so on. Of course, an element of the upper cover of D should not be considered if it contains an element that does not subsume any description of elements of D0. As soon as X00 is di erent from X a new implication is found and CN n is updated, adding a new element to DC if necessary, and X becomes a closed set of the new (CN n)def(T ).
closed sets. As such, for any Y X, Y 00 X. If X 6= X00, X is a pseudo-intent.
we make sure we obtain the Duquenne-Guigues Basis of the original context. As a new implication A ! B changes the structure of the lattice for role concepts we must select the minimal elements in ascending role-depth order.
As an element is added to NC for every A u B v C found and A u B becomes a closed element of the new (CN n)def(T ), the algorithm terminates with CN n isomorphic to the concept lattice of the formal context minus the maximal formal concept.
out. First, our algorithm immediately considers all concepts up to the maximum role depth instead of using a di erent learning phase for each depth. Second, new implications are immediately included in the background knowledge. We believe this is especially important for axioms of the form A v B u 9r:C where A v B would be found a rst time before the step including roles. 5
Example In our example, NC = fMan, Woman, Father, Mother, Parent, GrandFather, GrandMotherg and NR = fhasChildg. Moreover, we know that
Motherv Woman u Parent
Bob : Man u Father u Parent u 9hasChild.Man Bill : Man Benjamin : Man u GrandFather u Father u Parent 9hasChild.(Man u Father u Parent) Bertrand : Man u GrandFather u Father u Parent u 9hasChild.(Mother u Parent) Bernard : Man u Father u Parent u 9hasChild.Woman Clara : Mother u 9hasChild.Woman Coralie : Mother u GrandMother u 9hasChild.(Man u Father u Parent) Claire : Mother u GrandMother u 9hasChild.(Mother u Parent) Chloe : Woman
Initially, Open = f>g and CN n is as follows :
Mother >00 = ; so there is no new implication.
Open = fWoman, Father, GrandMother, Parent, 9hasChild.>, GrandFather, Mang
Woman00 = ; so there is no new implication.
Open = fFather, GrandMother, Parent, 9hasChild.>, GrandFather, Man, Mother, fWoman, Fatherg, fWoman, GrandMotherg, fWoman, Parentg, fWoman, 9hasChild.>g, fWoman, GrandFatherg, fWoman, Mangg
Father00 =fFather, Man, Parent, 9hasChild.>g so The implication Father ! fMan, Parent, 9hasChild.>g is added.
Mother
Father
Open = fGrandMother, Parent, 9hasChild.>, GrandFather, Man, Mother, fWoman, Fatherg, fWoman, GrandMotherg, fWoman, Parentg, fWoman, 9hasChild.>g, fWoman, GrandFatherg, fWoman, Mang, fFather, GrandMotherg, fFather, GrandFatherg, fFather, 9hasChild.Parentg, fFather, 9hasChild.Womang, fFather, 9hasChild.Mangg
Others implications are then found for GrandMother, Parent, 9hasChild.>, fWoman, Parentg, GrandFather, fFather, 9hasChild.Parentg, fMan, Parentg, fMother, 9hasChild.Parentg, fFather, 9hasChild.Parentg. The algorithm terminates with CN n in the following state.
GrandMother
GrandFather Mother 9hasChild.Parent
Father Woman
Parent Man
>
Conclusion
with terminological axioms learned from assertions contained in an ABox. Our approach translates data from DL formalism, that is instances of the ABox, to a form homogeneous to FCA, i.e. to lattices. More precisely, by using the lattice structure of the set of concepts of description logics, we modify classical
In this paper, we have restricted our approach to E L. We have shown that the set of E L-concept descriptions, ordered by the subsumption relation, is isomorphic to a certain subset { that depends on the de nitions of the TBox { of the lattice of ideals of the partially ordered set of equivalence classes built on the union of concept names and role concepts. We then proposed a simple algorithm exploiting this structure to learn terminological axioms from examples. Every implication found in the data is added to the TBox. We can easily make this algorithm interactive. More precisely, it is possible to change it into an attribute exploration-like algorithm in which experts are asked about each axiom and may give counterexamples. In this work, we dealt with description logic E L but the main idea of considering sets of incomparable concepts names is also valid for DLs with the concept ? or the constructor 8. However, it no longer works with constructors such as the negation because it adds new constraints between concept names. More complex DL languages will be the subject of future investigations on our part.