Our work deals with schema or ontology matching and is driven by the following statements: (1) Most of works only consider intensional description of schemas; (2) They mostly use symmetric similarity measures (and then they match similarity relations betwen concepts); (3) Few prototypes allow an interactive and visual match process. Therefore, we suggest an extensional and asymmetric matching method based on the discovery of significant implication rules between concepts described in textual documents. Our approach relies on the association rules paradigm and use a probabilistic model of deviation from independence, named implication intensity. Our matching method is divided into two consecutive stages: (1) the extraction in documents of relevant terms for each concept; (2) the discovery of significant implications between the concepts. And finally, we enclose this matching approach into an interactive visualization tool in order to facilitate the analyse, the validation and the editing of a mapping set for the knowledge engineer.
The hierarchical categorization of data through ontological forms as taxonomies is widely used with the increase of electronic data and knowledge on the Internet or in companies. Web directories such as Yahoo.com and OpenDirectory, the Electronic Document Management, or the Semantic Web with its OWL ontology are examples of such taxonomies.
In the literature, a lot of works deals with schema/ontology matching. The
schema or ontology matching aims at finding semantic relations (i.e.
equivalence, subsomption, etc) between entities (i.e. concepts, properties) of two
schemas/ontologies. These approaches use various techniques such as machine
learning [
However, the extracted matchings can be enhanced by using asymmetric
measures, which deliver more accurate information in the form of implications
between concepts. For instance, the use of such measures enables the discovery of
equivalence relations between concepts (example : if car → auto and auto → car
then auto ↔ car), and also it can detect if a concept is more specicfi than another
(example : car → vehicle). In knowledge discovery in databases (KDD),
asymmetric measures, called interestingness measures, are widely used for association
rules discovery [
In this paper, we evaluate the use of such asymmetric measures for matching
concepts of schemas or ontologies by using the Implication Intensity [
Our matching method is both extensional and terminological. It is designed to be used on taxonomies of concepts associated with textual documents. The idea underlying our approach considers that one concept is more specific than another, if the vocabulary used in the documents associated to the first concept tends to be included in the vocabulary of the other one.
Our method is divided into two consecutive stages: (1) The extraction of concept-relevant terms; (2) The discovery of association rules rules between concepts.
The results provided by matching algorithms are not the perfect solution to
one matching problem. Thus, the knowledge engineer (i.e. the domain expert)
must be able to analyse and edit the produced results. Nervertheless, most
prototypes/approaches do not offer a user-friendly interface allowing an interactive
match process [
This paper is organized as follows. In a rfist section we give an overview of matching approaches. Then, we introduce the Implication Intensity measure, before describing the concept hierarchy model, and the first stage concerning the extraction of concept-relevant terms. Next, we detail the rule extraction stage. Finally, we present our matching visualization tool and show the results obtained on a benchmark dataset. 2
Many surveys about ontology and schema matching have been proposed in
literature [
The main part of these works propose to process the concept name by using
string-similarities (Anchor-PROMPT [
Most of these approaches are intensional and symmetric. None of them are
both asymmetric and extensional. Among extensional approaches, we can cite
GLUE [
We can also notice that there is only one intensional method distinguishing
asymmetric relations. The method S-MATCH [
The definition of the Implication Intensity Let us now consider a finite set T of n individuals described by a set I of p items. Each transaction t can be considered as an itemset so that t ⊆ I. We denote by A = {t ∈ T ; a ⊆ t} the extension of itemset a and we denote by B = T − { t0 ∈ T ; b ⊆ t0} the complementary of the extension of b (i.e. the extension of b). Then, we introduce the quantities na = card(A), nb = card(B) and na∧b = card(A ∩ B).
An association rule [
More precisely, we compare the observed number of counter-examples na∧b to a probabilistic model noted Na∧b. Let us assume that we randomly draw two subsets X and Y in T which respectively contain na and nb transactions, i.e. Na∧b = card(X ∪ Y ).
The implication intensity of the association rule a → b is denfied by: ϕ(a → b) = 1 − Pr(Na∧b ≤ na∧b) (1)
The distribution of the random variable Na∧b depends on the drawing mode
[
The concept hierarchy model and the extraction of concept-relevant terms Our approach (gfiure 1) is designed for conceptual hierarchies of concepts organized by a partial order relation, connected to a set of textual documents.
We define a conceptual hierarchy H as a quadruplet:
H = (C, ≤ , D, σ 0) where C is a set of concepts, ≤ represents the partial order, D is the set of documents, and σ 0 is the relation which associates a set of documents to each concept (i.e. for a concept c ∈ C, σ 0(c) represents the documents associated to c). From the partial order ≤ , we extend the relation σ 0 to σ , where:
In a first stage, we transform the hierarchy hierarchy H0 defined on terms as follows: σ (c) = [ σ 0(c0) c0≤ c H0 = (C, ≤ , T, γ 0)
H denfied on documents in a where T is the set of relevant terms extracted from D, and γ 0 ⊆ C × T is the relation associating terms to concepts (i.e. γ 0(c) represents the set of relevant terms selected for the concept c). From σ and the relation δ linking terms to documents (i.e. δ (t) is the set of documents in which the term t appears), we can deduce the relation γ 0. Technically, this is done by evaluating association rules t → c (between a term t and a concept c) with the implication intensity measure. A such rule means that the term t tends to appear in documents associated the concept c. The relevant term set of the concept c, noted γ 0(c), is denfied as follows:
γ 0(c) = {t ∈ T0|ϕ(t → c) > ϕt}
where T0 represents the set of the binary terms (terms composed of two
meaningful words) and of the verbs contained in the documents. Binary terms
have the advantage to be more informative and less ambiguous than simple
words: they permits to avoid the problem of polysemy. The acquisition of binary
terms is performed with the software program ACABIT [
ϕ(t → c) = 1 − P r (Nt∧c ≤ nt∧c) where nt∧c = card(δ (t) − σ (c)) is the observed number of counter-examples, that is to say documents which contain the term t and which are not associated with the concept c. And Nt∧c is the expected number of counter-examples under independence hypothesis.
From the partial order ≤ , we extend the relation γ 0 to γ , where: (2) (3) (4) (5) (6) γ (c) =
The common term set of two hierarchies H10 = (C1, ≤ 1, T1, γ 1) and H20 = (C2, ≤ 2, T2, γ 2) is noted T1∩2 = T1 ∩ T2. Next, we denfie the relation γ 1∩2 which associates a subset of T1∩2 for each concept c ∈ C1 ∪ C2:
An implicative match set between two hierarchies H10 and H20 is a set of implicative rules. A rule a → b between the concepts a ∈ C1 and b ∈ C2 represents a quasi-implication (i.e. an implication tendancy) from the set of terms γ 1∩2(a) to the set of terms γ 1∩2(b). (8) H ≤ H '
≤ 5 5.1 binary terms extraction
and relevant terms
selection 0 documents binary terms extraction
and relevant terms selection ≤
0 abstract datum algorithm analysis artificial intelligence computer science database system relevant terms ≤
Significant implication rules discovery
implication rules Discovery of significant rules between concepts
In section 4, we have defined a match result as a set of implication rules between concepts issued from two hierarchies H1 and H2. Nevertheless, a lot of rules can be discovered. In this section, we define the implication intensity of a rule between concepts, and then we give two criteria denfiing the notion of signicfiant rule. relevant terms H ' 1 A1 ≤ A2
A3 A4
A5
A2 B4=0.97 relevant
terms H ' 2
≤ B2
B1
B3 B5
B6
B7
B8
B4 1∩2B4 image processing computer architecture computer programming (9) (10) (11)
The implication intensity of a rule a → b (with a ∈ C1 and b ∈ C2) is defined by:
ϕ(a → b) = 1 − P r Na∧b ≤ na∧b concept a wah∧ibch=arcearndo(tγ r1e∩l2e(vaa)nt− foγr1∩c2o(nbc)e)pits bt.hNe number of relevant terms for where n a∧b is the expected number of relevant terms for concept a which are not relevant for concept b. On figure 2, the rule A2 → B4 has nA2∧B4 = 1 counter-examples. Its implication intensity value is: ϕ(A2 → B4) = nA2∧B4
X k=0 e− λ . λ k = 0, 97 k! where λ = nA2.nB4/n = 6.(30 − 8)/30 (see gfiure 2).
Thus, the two criteria defining a significant rule are, first, its implication intensity value and, second, the specificity of its consequent combined with the generality of its antecedent. A rule a → b (with a ∈ C1 and b ∈ C2) will be significant if:
ϕ(a → b) ≤ ϕr and ∀x ≥ a, ∀y ≤ b, ϕ(x → y) ≤ ϕ(a → b)
The second criterion (equation 11) selects only generative rules and then permits to reduce redundancy in the extracted rules set. Indeed, from the rule a → b, we can deduce all the rules of the form x → y because at the term level: γ 1∩2(b) ⊆ γ 1∩2(y) and γ 1∩2(x) ⊆ γ 1∩2(b). We say that the rule a → b is generative of the rules set x → y. For example (gfiure 2), the rule A2 → B4 is generative of the rules set {A2 → B1, A4 → B4, A5 → B4, A4 → B1, A5 → B1}. 5.2
During the rule extraction step, we can reduce the computation time with the help of the partial order. A top-down search phase enables us to avoid the evaluation of rules having too specific antecedents. This section presents our selection strategy divided into two algorithms.
Inputs :
A : a concept of H1.
Bcurrent : a set of concepts taking from H2.
Procedure specializeAntecedent(A, B) Begin
ForEach Bx ∈ Bcurrent Do
specializeConsequent(A, Bx, Bcurrent, 0.0) End Do ForEach child ∈ children(A) do
Bc0urrent := Bcurrent specializeAntecedent(child, Bc0urrent)
End Do End
Our rfist algorithm (figure 3) takes in a concept a from the hierarchy H1 and a set of concepts Bcurrent ⊂ C2 from H2. For each concept of Bcurrent, the second algorithm (gfiure 4) searches and selects valid consequents. It also updates the set Bcurrent. And then, this rfist procedure is recursively launched over the children of a and with a copy of the set Bcurrent. The set Bcurrent contains the subtrees of H2 with concepts that were selected during the previous recursion steps.
The second algorithm (figure 4) searches a set of valid consequents for the current antecedent a. The search is performed over the set candidate consequents {Bx|Bx ≤ 2 B}. A consequent bs will be selected if the rule a → bs satisefis the two criteria 10 and 11.
This algorithm provides a top-down search of rules in H2, and then explores all branches of the hierarchy. We choose to stop the descent in a branch if ∀b0x ≤ 2 bx, ϕ(a → b0x) < ϕr. For a rule x → y , a property of implication intensity denfies x ∪ y as the best specialization of the consequent. We exploit this property in order to avoid the evaluation of all rules a → b0x.
The describing search method does not consider the roots of hierarchies because all selected terms are associated to root-concepts. The implication intensity value of such rules (i.e. rules which contain root-concepts) is either undenfied or equal to 0.
Experiments and interactive visualization 6.1
We experimented our algorithms and our interactive visualization tool on a
benchmark proposed in [
Our maching algorithms are enclosed into a decision helper system which enables the visualization of a matching. This tool aims to help a domain expert to study, edit and validate a matching set pairs between hierarchies. The tool provides a visual metaphor based on graphs: it represents the two hierarchies by trees where nodes are concepts and edges represent the partial-order relations. The implicative matching pair set is represented by directed edges valued by the implication intensity value. Therefore, the global view of the matching graph is intricate and confused. From this general view, the user can intuit the general structure of the matching and nfid concepts having a lot of implications connected to.
In order to lighten the graph display, the tool proposes a zoom and a ϕr threshold chooser which permits to filter the displayed relations. The user can also choose to keep only the more generative significant rules. Finally, the concepts which do not match other concepts can be hidden.
Fig. 5. Lightened and zoomed representation of an interesting part of a matching graph
The user can select concepts and then visualizes its related information: its number of documents attached, its list of significant terms, and the list of concepts that it matches. In the same way, information about matching relations can be displayed: the source and target concepts, the relevant terms shared by the two concepts (examples), the relevant terms only associated with one concept and the more specific relations that it generates. Therefore, this information helps the user to decide if a matching relation must be kept or removed.
On the gfiure 5, we kept only generative rules having an intensity implication value greater than 0.7. For example, if the expert is interested by the rule ”PLANT BIOLOGY → BOTANY”, he can select this and study the underlying terms (gfiure 6).
This tool can load several kind of hierarchies: OWL ontologies, lfiesystem directory structure with her textual contents. The matching result can be exported into an RDF format for ontology alignment. 6.3
Here, we present results provided by a qualitative test of precision and recall. We
compare the results produced by our approach with a reference matching pair
set provided by [
Then, we varied the two thresholds ϕt and ϕr (from 0.8 to 1) and computed the precision and the recall values according to the ”reference” matching set. These two measures issued from information retrieval are defined as follows: let us considers F the set of matching pairs found using our approache and R the set of ”reference” matching pairs. The precision (precision = card(F ∩ R)/card(F )) measures the ratio of the number of good matching pairs (i.e. matching pairs that are both in our result set and in the reference matching set) over the number of matching pairs found by our method. The recall (recall = card(F ∩ R)/card(R)) measures the ratio of good matching pairs over the number of reference matching pairs.
Results show that the term selection threshold ϕt has a greater inuflence than
the rule selection threshold ϕr. We obtain good precision values (from 0.71 to
1). Nevertheless, the recall values are quite bad: the best value is equal to 0.54.
Our method seems to be too selective. These results can be rfistly explained by
the the lack of textual data associated with the dataset. As [
In this paper, we propose an extensional matching method based on the discovery of significant implication rules between concepts. Our approach takes in two hierarchies of concepts to be matched and the textual corpus indexed to these concepts. The matching task is divided into two stages: (1) the extraction and selection of relevant terms for each concepts; (2) the discovery of signicfiant rules between concepts by using their relevant terms set. The main advantages of this method are the consideration of semantics by using binary terms contained in the corpus and the discovery of rules allowing to enhance the produced matching results only regarding similarity-based matching systems. We implemented our algorithms and an interactive visualization tool. This tool helps a domain expert to edit and validate a matching between conceptual hierarchies populated with textual documents. We illustrated our tool on a real conceptual hierarchy related to university courses descriptions and we compared our results to a manual matching reference.
Currently, we propose an extensional individual matcher. In the near future, we will propose a schema based matcher and combine the two approaches in order to enhance the matching task. We will also enhance the mapping visualization by using more improved graph drawing algorithms and add more editing features for facilitate the validation step.