$EVWUDFW In this paper, we present a method for learning ontologies from RDF annotations of Web resources by systematically generating the most specific generalization of all the possible sets of resources. The preliminary step of our method consists in extracting (partial) resource descriptions from the whole RDF graph gathering all the annotations. In order to deal with algorithmic complexity, we incrementally build the ontology by gradually increasing the size of the resource descriptions we consider.
,QWURGXFWLRQ The Semantic Web, expected to be the next step that will lead the Web to its full potential, will be based on semantic metadata describing all kinds of Web resources. Resource Description Framework [RDF, 1999] seems to be the emerging standard allowing to semantically annotate Web resources. These annotations are related to ontologies, for example declared in RDF Schema [RDFS, 2000], as proposed by W3C, or in RDF-compatible languages like OIL [Fensel HWDO ., 2000]. Methods for building hierarchies of classes from RDF annotations will appear to be useful to classify resources, organize knowledge and finally learn ontologies.
The building of hierarchical structures has been extensively studied in machine learning, especially in concept formation. Most approaches of concept formation are dedicated to the prediction of unknown features of new objects [Fischer HW DO , 1987; Gennari HW DO , 1989]. The clusters of VLPLODU objects are then privileged, the learned conceptual hierarchy does not comprise all the possible sets of objects, but only the best ones according to some heuristic criteria.
For learning ontologies, we adopt a particular approach of concept formation. An ontology is viewed as a concept hierarchy, where each concept is defined in extension by a cluster of resources and in intension by the most specific common description of these resources. This approach leads to the systematic generation of all the possible clusters of objects, as in [Mineau, 1990; Carpineto and Romano, 1993; Bournaud HWDO ., 2000].
Since all RDF annotations are gathered inside a common RDF graph, the problem which arises is the extraction of a description for a given resource from the whole RDF graph. After a brief description of the RDF data model (Section 2) and of RDF Schema (Section 3), Section 4 presents several criteria for extracting partial resource descriptions. In order to deal with the intrinsic complexity of the building of a generalization hierarchy, we propose an incremental approach by gradually increasing the size of the descriptions we consider. The principle of the approach is explained in Section 5 and more deeply detailed in Section 6.
RDF is the emerging Web standard for annotating resources with semantic metadata [RDF, 1999] [Decker HWDO , 2000]. An RDF annotation consists of a set of statements, each one specifying a value of a property of a resource. A statement is thus a triple (resource, property, value), a value being either a resource or a literal. The RDF data model is close to semantic nets. A set of statements is viewed as a directed labeled graph: a vertex is either a resource or a literal; an arc between two vertices is labeled by a property. RDF is provided with an XML syntax. Figure 1 presents an example of an RDF graph describing the Web page relative to the cat Njal and its XML serialization.
Cat type
type livesIn ownedBy <rdf:Description about=‘#Njal’> <rdf:type resource=`#Cat’ /> <livesIn> <rdf:Description> <rdf:type resource=`#House’ />
<ownedBy rdf:resource=`#Catherine’ /> </rdf:Description> </livesIn> </rdf:Description> )LJXUH
An RDF annotation and its XML serialization An RDF annotation is a set of RDF triples. It can thus be viewed as a graph, which is a subgraph of the complete RDF graph representing the whole set of annotations on the Semantic Web.
RDF Schema (RDFS) is a schema specification language [RDFS, 2000]. It is dedicated to the specification of schemas representing the ontological knowledge used in RDF statements: a schema consists of a set of declarations of classes and properties. Multi-inheritance is allowed for both classes and properties. A property is declared with a signature allowing several domains and a single range. The RDFS metamodel is presented in Figure 2 and is itself defined as a set of statements by using the core RDFS properties: UGIVVXEFODVV2I and UGIW\SH which denote respectively the subsumption relation between classes and the instantiation relation between an instance and a class. As shown in Figure 2, an ontology embedding domain specific knowledge is represented by a schema defined by refining the core RDFS. Domain specific classes are declared as instances of the “Class” resource, and domain specific properties as instances of the “Property” resource. The “subclassOf” and “subPropertyOf” properties enable to define class hierarchies and property hierarchies. The resources appearing in an RDF annotation are then typed by the classes declared in the RDF schema the annotation is relative to; the properties between the resources are those declared in the RDF schema. Regarding the RDF model, the knowledge base representing the resource annotations consists of a single graph G. There is no difference between stating a resource description in one annotation and stating it in several pieces in separate annotations: “there is no distinction between the statements made in a single sentence and the statements made in separate sentences” [RDF, 1999]. The RDF model does not handle the delimitation of the subgraph of G describing a resource. We thus propose different criteria for extracting a description of a resource R from G. &RPSOHWHGHVFULSWLRQ : We define the complete description of a resource R as follows. A resource is completely described by the subgraph of G containing all the resources reachable from R through properties. Formally, the complete description of R is the largest connected subgraph of G containing R; it is inductively defined as the join of the complete descriptions of the resources adjacent to R in G. Such a complete description may be very large; potentially it may be the graph G representing the whole knowledge base. This is why we define ways of extracting partial descriptions of a resource R from G. 3LHFH RI NQRZOHGJH : We define the piece of knowledge relative to a resource R as the largest connected subgraph of G whose all internal nodes excepted R are anonymous resources. External nodes are either identified resources, or literals or anonymous resources connected to the only resources belonging to the piece. ’HVFULSWLRQ RI OHQJWK Q : We define the description of length n of a resource R as the largest connected subgraph of G containing all possible paths of length smaller or equal to n, starting from or ending to R. The description Dn(R) of length n of a resource R is inductively obtained by joining Dn-1(R) with the descriptions D1 of length 1 of the resources which are external nodes of Dn-1(R). 3DUWLDO GHVFULSWLRQ : We define a partial description of a resource R as either the piece of knowledge relative to R or a description of length n of R. Given the whole RDF graph G, by choosing a description extraction criterion, we can now be provided with a set of partial descriptions for all the resources that are nodes of G. l a j N o t e v i t a l e r e g d e l w o n k f o e c e i P ion la tp jN i rsc fo ed h1 l: g ) t a n j (DN1 lfeo black
color Cat
Cat type
motherOf ownedBy type type
motherOf ownedBy
motherOf ownedBy type
Now, given an RDF graph G and a resource description extraction criterion, let us consider the set of the descriptions of all the resources nodes of G. We can now further describe our approach of ontology learning. It consists in associating to this set of resource descriptions the hierarchy of the concepts whose extensions correspond to all the possible resource clusters.
* type *∈{Sandwich, Njal, Catherine, An. Res.} * type Living Being Our approach of ontology learning consists of systematically considering all the concepts covering a set of resources nodes of G. Each of these concepts may then be defined in extension as a cluster of resources; its definition in intension must generalize the descriptions of the resources belonging to its extension. The definition of criteria to extract resource descriptions from an RDF graph G was thus a preliminary step to concept.
In this hierarchy, each concept ci is labeled by a pair (exti, inti), where exti is the extension of ci and inti is the intension of ci. Inti is the most specific generalization of the descriptions of the resources belonging to exti. We thus call this concept hierarchy a generalization hierarchy. The generalization of a resource description is based on the subsumptions relations between classes and properties declared in the RDF schema representing the ontology which the RDF graph G we consider is relative to. Such a generalization hierarchy is a lattice: its nodes are partially ordered by the subsumption relation on their intensions as well as the inclusion relation on their extensions. Figure 4 presents the generalization hierarchy built from descriptions of length 1 of four resources nodes of the RDF graph depicted in Figure 3: Njal, Sandwich, Catherine and the anonymous resource of type ‘House’.
If several concepts share the same intension, a single concept is added to the generalization hierarchy: the one with the largest extension. Therefore, if the size of the generalization hierarchy may theoretically reach 2N concepts for N resources in the RDF graph G, in practice it is much lower. For instance, the size of the hierarchy of Figure 4 is 8 concepts instead of 16 (24 ).
,QFUHPHQWDOSU LQFLSOH The question which now arises is the choice of a resource description extraction criterion: starting from an RDF graph, we must choose from which partial resource descriptions the concept hierarchy will be built. On the one hand, the larger the extracted resource descriptions will be, the more domain-significant the concepts will be. On the other hand, graph matching and lattice building both have a well-known intrinsic exponential complexity. As a result, we adopt an incremental approach for the construction of the generalization hierarchy.
To be precise, we gradually increase the length of the partial resource descriptions we consider. We first build a generalization hierarchy S1 from resource descriptions of length 1. The concepts of S1 thus have intensions of length 1. Sn is then inductively built from Sn-1 and S1 by incrementally increasing the maximum length of the resource descriptions we consider. The description Dn(R) of length n of a resource R is inductively increased by joining Dn-1(R) with the descriptions of length 1 of the resources which are external nodes of Dn-1(R).
,QFUHPHQWDO EXLOGLQJ RI D JHQHUDOL]DWLRQ
%XLOGLQJRIDJHQHUDO L]DWLRQKLHUDUF K\EDVHGRQ
The principle for building S1 is as follows: 1. Extraction of resource descriptions of length 1 from the whole RDF graph. D1(R) is the set of RDF triples beginning or ending by R. 2. Iterative generalization of all the possible pairs of triples. The generalizations of two triples (R1, P1, V1) and (R2, P2, V2) are the most specific triples (RG, PG, VG) subsuming them. This is based on the ontological knowledge represented in the RDF Schema relative to the RDF annotations we consider. PG is one of the most specific properties generalizing P1 and P2. If V1 and V2 are classes, then VG is one of the most specific classes generalizing V1 and V2; else either VG=V1=V2 or VG is anonymous. We call L1 the set of all generalized triples. 3. Construction of the intensions of length 1 of the S1 nodes. The triples sharing a same extension are grouped together. An intension may include redundant triples, one being more general than another. It is cleaned up by deleting triples subsuming another one. Such an intension is the most specific description of the node. 4. Building of S1 based on the inclusion relations between the node extensions. Several nodes may share the same intension. In this case, the node we preserve corresponds to the largest extension.
Let us apply this principle on the RDF graph depicted on Figure 3. The consecutive steps are illustrated in Figure 5.
In the first step, the descriptions of length 1 of all the resources are extracted from the RDF graph of Figure 4. For each RDF triple (R, P, V), both the triples (*, P,V) and (R, P, *) are generated; the resources R matching * in ( *, P, V) and the resources V matching * in (R, P, *) are indexed to these triples. For instance, the triples (‘Njal’, type, cat) and (‘Sandwich’, type, cat) both match the triple (*, type, cat): the resources ‘Njal’ and ‘Sandwich’ are thus indexed by the triple (*, type, Cat). The result of step 1 is thus an inverted file where resources are indexed by the triples they are the extensions of. ‘Njal’ and ‘Sandwich’ belong to the extension of the intension represented by (*, type, Cat).
In the second step, the triples are matched two by two; for each pair of triples, the most specific generalization of both triples is computed, according to the ontological knowledge expressed in the RDF schema the RDF graph is relative to. The extension of a generalized triple is the union of the extensions of the two initial triples it generalizes. For instance, the triples ( *, color, black) and ( *, color, red) are generalized into the triple ( *, color, ∅), black and red being incomparable; ( *, type, Person) and ( *, type, Cat) are generalized into the triple ( *, type, Living Being), ‘Living Being’ being the most specific class subsuming ‘Cat’ and ‘Person’. Note that RDFS allows for multi-inheritance on class and property hierarchies. Therefore two classes or two properties may have several most specific subsumers; in such cases, the generalization of two triples may lead to several triples.
In the third step, each possible set of resources is considered as the extension of a concept whose intension is to be found: for each extension, the common triples the resources are indexed by are grouped together to build the intension of the concept. For instance, the two resources ‘Njal’ and ‘Sandwich’ viewed as a concept extension lead to the construction of the intension of this concept from the set of triples they are both indexed by: {( *, type, Cat), ( *, color, ∅), ( *, type, Living Being)}. Since the triple ( *, type, Living Being) subsumes the triple ( *, type, Cat), it is discarded from the final intension. Finally, a new concept will be added to the generalization hierarchy, with {'Njal', 'Sandwich'} as extension and {( *, type, Cat), ( *, color, ∅), ( *, type, Living Being)} as intension.
The last step is dedicated to the building of the generalization hierarchy based on the inclusion relations between the concept extensions. The concepts sharing their intensions with concepts whose extensions include their own ones are discarded: for instance, the concept ({Njal, Catherine}, {( *, type, Living Being)}) is discarded since the concept whose extension is the set {Njal, Sandwich, Catherine} shares the same intension. The generalization hierarchy depicted in Figure 4 is the final result S1 obtained from the index file depicted in Figure 5.
%XLOGLQJRIDJHQHUDO L]DWLRQKLHUDUF K\EDVHGRQ
1. Iterative construction of Ln by join of all the possible pairs of one triple of L1 and one triple path of length n-1 of Ln-1. Two triples can be joined if the value in the first triple is equal to the resource described in the second triple. A triple path of length n is thus the result of n-1 joins between n triples. This iterative construction of Ln is equivalent to considering resource descriptions Dn(R) of length n by joining Dn-1(R) and D1(Ri), with i=1..k, Ri being the external nodes of Dn-1(R). 2. Construction of the intensions of length n of the Sn nodes (this step is similar to step 3 of S1 building). 3. Building of Sn based on the inclusion relations between the node extensions (similar to step 4 of S1 building). )LJXUH
… )LJXUH
Building of 6 from 6 depicted in Figure 4.
The principle for building Sn from Sn-1 and S1 is as follows: can be joined with the triple (*, type, Person) since the value of the former triple is equal to a resource belonging to the extension of the second one. The join results in a triple path of length 2 (*, ownedBy, Catherine) (Catherine, type, Person), whose extension is equal to the extension of the former triple.
In the second step, each possible set of resources is considered as the extension of a concept whose intension is to be found: the common triples the resources of a concept extension are indexed by are grouped together to build the intension of the concept. It is thus cleaned up in order to obtain the most specific description. For instance, the triple path (*, ownedBy, Catherine) (Catherine, type, ∅) is discarded from the intension of the extension {Sandwich, Anonymous Resource}, since it subsumes the triple path (*, ownedBy, Catherine) (Catherine, type, Person).
The last step is dedicated to the building of the generalization hierarchy based on the inclusion relations between the node extensions. Figure 7 presents the generalization hierarchy S2 built from the generalization hierarchy S1 depicted in Figure 4. S2 has the same number of concepts than S1 but five of its concepts have more complex intensions: the four concepts whose extensions are reduced to a single resource and whose intensions correspond to the descriptions of length 2 of these resources, and the concept of extension {Sandwich, An. Res.}.
Conceptual clustering aims at building hierarchies to cluster
similar objects and classify object descriptions [Fischer HW
DO , 1987]; a single class hierarchy is built, the best
according to a certain criterion. Our approach of concept
formation for ontology learning is slightly different since it
aims at V\VWHPDWLFDOO\ generating a class for each possible
set of objects. This systematic approach is shared by
researches in formal concept analysis [Wille, 1982], on
knowledge organization [Mineau HW DO , 1990] and in
inductive logic programming [Kietz and Morik, 1994;
Schlobach, 2000]. Another particularity of our method is the
gradual increase of the size of the resource descriptions to
deal with the intrinsic complexity of description matching
and ontology building. A similar approach is adopted in
[Bournaud HWDO , 2000]; it is based on a gradual increase of
the VWUXFWXUH RI PDWFKLQJ. Object descriptions are JLYHQ, and
the concept description language is made more expressive at
each step to gradually take into account the complexity of
the descriptions. Our method differs in that the resource
descriptions are not given in an RDF graph and its
incrementallity is based on the gradual increase of the VL]H
and not of the structure of matching. Finally compared to
the approaches of ontology learning based on the analysis of
textual corpus
We are currently exploring the possible improvements of our algorithms for the construction of the first class hierarchy [Baader HWDO , 1999].