The evaluation of ontology matching algorithms mainly consists of comparing a produced alignment with a reference one. Usually, this evaluation relies on the classical precision and recall measures. This evaluation model is not satisfactory since it does not take into account neither the closeness of correspondances, nor the semantics of alignments. A first solution consists of generalizing the precision and recall measures in order to solve the problem of rigidity of classical model. Another solution aims at taking advantage of the semantic of alignments in the evaluation. In this paper, we show and analyze the limits of these evaluation models. Given that measures values depend on the syntactic form of the alignment, we first propose an normalization of alignment. Then, we propose two new sets of evaluation measures. The first one is a semantic extension of relaxed precision and recall. The second one consists of bounding the alignment space to make ideal semantic precision and recall applicable.
With the semantic Web, many related but heterogenous ontologies are being created. In such an open context, there is no reason why two domain-related applications would share the same ontologies. In order to facilitate the exchange of knowledge between such applications, ontology matching aims at discovering a set of relations between entities from two ontologies. This set of relations is called an alignment.
Many different matching algorithms have been designed [Euzenat and Shvaiko, 2007]. In order to compare the performance of such algorithms, some efforts are devoted to the evaluation of ontology matching tools. Since 2004, the Ontology Alignment Evaluation Initiative1 (OAEI) organizes, every year, an evaluation of ontology matching methods. The evaluation of matching algorithms consists of comparing a produced alignment with a reference one. This evaluation often relies on two classical measures used in information retrieval: precision and recall [van Rijsbergen, 1979]. Precision measures the ratio of correct correspondences in the evaluated alignment. Recall measures the ratio of reference correspondence found by the evaluated alignment.
In the context of alignment evaluation, precision and recall present the drawbacks to be all-or-nothing measures [Ehrig and Euzenat, 2005] and they do not consider neither the semantic of alignment relations, nor those of ontologies. Then, an alignment can be very close to the expected result and have low precision and recall values. Two approaches have been proposed for correcting these drawbacks. [Ehrig and Euzenat, 1 http://oaei.ontologymatching.org 2005] introduced a generalization of precision and recall measures. This approach relies on syntactic measures relaxing the all-or-nothing feature of classical measures in order to take into account close correspondences. [Euzenat, 2007] has introduced semantic precision and recall measures which rely on a semantic of alignments
We will show that semantic precision and recall are still dependent on the alignment syntax and, as a consequence, they can assign different values to semantically equivalent alignments. [David, 2007] proposes to use the ideal semantic precision and recall measures introduced in [Euzenat, 2007] restricted to alignments containing only simple correspondences, i.e. only between named entities.
In this paper, we show and analyze the limits and problems of the semantic precision and recall measures. To overcome their drawbacks, we first investigate an approach allowing to normalize alignments. This normalization relies on algebra of alignment relations and can partially resolves problems encountered by the evaluation measures. In addition, we propose two adaptations of the relaxed and semantic measures. The first adaptation makes use of the generalization framework of [Ehrig and Euzenat, 2005] and allows to locally consider the semantic of alignments. The second one is a restriction of Semantic closures of alignment. This restriction makes the ideal semantic measures proposed in [Euzenat, 2007] useable.
This paper is organized as follows: a first section introduces the definitions related to the syntax and semantics of alignments. In the second section, we first present and introduce five properties that an ideal model should satisfy. Then, we present the classical evaluation measures and the semantic evaluation measures which satisfy three of the five desired properties. In the following section, we explain why these semantic measures do not satisfy the two last properties. The last section proposes three ways for fixing the semantic measures: a normalization of alignments, new relaxed semantic precision and recall measures, and -bounded semantic evaluation measures. 2
2.1
An alignment groups correspondences between entities or formulas from two ontologies o1 and o2. Each element of correspondence can be associated to a quality value by a function q. We use the following syntax for representing an alignment: Definition 1 (Alignment). An alignment between two ontologies o1 and o2 is a set of correspondances holding between o1 and o2. A correspondance, noted c = (x; y; R), is a triple where x, respectively y, are formulas (or entities) from o1, respectively from o2, and R is the relation holding between x and y. A correspondance c = (x; y; R) can be also written xRy
This definition includes both simple alignments considering only matching relations between entities (classes or properties) and complex alignments containing relations between formula inferred from the ontologies. 2.2
Alignments between ontologies can be helpful for reasoning with several ontologies. For enabling reasoning capabilities, a semantic for alignments must be defined. In this paper, we relies on the semantic proposed in [Euzenat, 2007]. This semantic of alignment is function of the semantics of each individual ontology. The semantic of an ontology is given by its set of models.
Definition 2 (Model). a model m = hI ; Di of o is a function I from the terms of o to a domain of interpretation D, which satisfies all the assertions in o: 8
2 o; m j= The set of models of an ontology o is denoted as M(o).
Because the models of various ontologies can have different interpretation domains, we use the notion of an equalising function, which helps make these domains commensurate.
a set of ontologies , an equalising function for hIo; Doio2 is a family of functions = ( o : Do ! U )o2 from the ontology domains of interpretation to a global domain of interpretation U . The set of all equalising functions is called .
The relations used in correspondences do not necessarily belong to the ontology languages. As a consequence, a semantics for them must be provided.
and U a global domain of interpretation, R is interpreted as a binary relation over U , i.e., RU U U .
The definition of correspondence satisfiability relies on and the interpretation of relations. It requires that in the equalised models, the correspondences are satisfied. Definition 5 (Satisfied correspondence). A correspondence c = hx; y; Ri is satisfied for an equalising function by two models m, m0 of o, o0 if and only if o m 2 M(o), o0 m0 2 M(o0) and
h o(m(e)); o0 (m0(e0))i 2 RU This is denoted as m; m0 j=
c.
Given an alignment between two ontologies, the semantics of the aligned ontologies can be defined as follows.
alignment A between these ontologies, a model m00 of these ontologies aligned by A is a triple hm; m0; i 2 M(o) M(o0) , such that m; m0 j= A.
We will consider a specific kind of consequence, -consequences [Euzenat, 2007], which are the correspondences holding for all models of aligned ontologies.
and an alignment A between these ontologies, a correspondence is a -consequence of o, o0 and A (noted A j= ) if and only if for all models hm; m0; i of o, o0 and A, m; m0 j= (the set of -consequences is noted by Cn(A)).
Given this semantic, the semantic closure and semantic reduction of an alignment are given by the following definitions: Definition 8 (Semantic closure). The semantic closure Cn(A) of an alignment A is the set of its -consequences.
Obviously , the semantic closure of an alignment is unique but it has no reason to be finite.
Definition 9 (Semantic reduction). A semantic reduction (or minimal cover) A0 of an alignment A is an alignment satisfying Cn(A0) = Cn(A) and 8c 2 A0; Cn(A0 fcg) 6= Cn(A) There could exist several semantic reductions for a given alignment. An alignment A contains redundant elements if A is not a minimal cover. A correspondence c 2 A is redundant if A fcg j= c. 3
Alignment evaluation is achieved by comparing the produced alignment with the reference one. This comparison usually relies on the precision (P ) and the recall (R) measures [van Rijsbergen, 1979]. Intuitively, the precision aims at measuring the correctness of the evaluated alignment. The recall is used for quantifying the completeness of the evaluated alignment.
In the rest of this paper, we will consider two alignments between ontologies o1 and o2: a reference alignment, noted Ar, and an alignment produced by some matching method Ae. 3.1
If we consider that precision and recall should approximate correctness and completeness, an ideal model taking semantic into account, would respect the constraints given by [Euzenat, 2007]: – Ar j= Ae ) P (Ae; Ar) = 1 (max-correctness) – Ae j= Ar ) R(Ae; Ar) = 1 (max-completeness) – Cn(Ae) = Cn(Ar) iff P (Ae; Ar) = 1 and R(Ae; Ar) = 1 (definiteness)
Furthermore, in the evaluation context, one could be interested to compare several alignments produced by some matching algorithms against one reference alignment. Then, it would be useful that two semantically equivalent alignments have the same precision and recall values. – Cn(Ae1 ) = Cn(Ae2 ) )
R(Ae2 ; Ar) (semantic-equality)
P (Ae2 ; Ar) and R(Ae1 ; Ar) =
Finally, if the evaluated and the reference alignments share some common information then the precision and recall values must not be null: – P (Ae; Ar) = 0 and R(Ae; Ar) = 0 iff Cn(Ae) \ Cn(Ar) = Cn(;) (overlapping positiveness) 3.2
The classical evaluation model is based on the interpretation of alignments as sets and considers the following sets : – E: the set of all correspondences that could be generated between o1 and o2. This set is a subset of the cartesian product of all entities which can be deduced from o1, those deductible for o2 and the set of matching relations considered. – true-positives: the set of correspondences which are found by the matching method and contained in the reference alignment. – false-positives: the set of correspondences which are found by the matching method but not contained in the reference alignment. – false-negatives: the set of reference correspondences which are not found by the matching method. – true-negatives: the set of correspondences that are neither in the evaluated alignment nor in the reference alignment.
found not found relevant jAe \ Arj true-positives
jAr Aej false-negatives jArj not relevant jAe Arj false-positives j(E Ar) Aej jE true-negatives jE Arj jAej
Aej
The cardinalities of these sets are given in the contingency table 1. The sets of truepositives, false negatives, and false-positives are defined only from Ae and Ar. The set of true-negatives is also function of the set E which is not easily identifiable.
From these contingencies, the classical measure of precision and recall can be defined. The precision (P ) represents the proportion of found correspondences that are relevant: 3.3
These two measures applied to this simple model have the advantages to be easily computable and understandable. However, they verify none of the constraints presented Section 3.1. This is because they do not consider the semantic of alignment relations, nor the semantic of ontologies.
Firstly, they do not take into account the semantic of matching relations. For example, if the produced alignment Ae contains the elements x v y and x w y, and the reference alignment Ar contains the element x y, then the classical model will consider x v y and x w y as false-positives and x y as false-negative. In this case the precision and recall values are equals to 0 even if Ae Ar.
Secondly, this classical model does not take the semantic of ontologies into account. For example, Ae contains the element x0 v y, the reference alignment Ar contains the element x y, and the ontology o1 states x0 v x. Even if Ar j= Ae, the classical precision will be equal to 0 since the correspondence x0 v y is considered as a falsepositive by this evaluation model. 3.4
In order to resolve the drawbacks of classical precision and recall, [Euzenat, 2007] proposes to take into account the semantics of matching relations and ontologies. The author provides two extensions of precision and recall.
The ideal extension of the classical model consists of replacing Ae and Ar by their respective sets of -consequences, Cn(Ae) and Cn(Ar). Table 2 show the new contingencies.
relevant found jCn(Ae) \ Cn(Ar)j
true-positives not found jCn(Ar) Cn(Ae)j j(E false-negatives jcn(Ar)j
not relevant jCn(Ae) Cn(Ar)j false-positives Cn(Ar)) Cn(Ae)j jE true-negatives jE Cn(Ar)j jCn(Ae)j
Cn(Ae)j
From this extended model, ideal precision and recall measures, respectively named Pi and Ri, are :
Pi(Ae; Ar) = jCn(Ae) \ Cn(Ar)j
jCn(Ae)j Ri(Ae; Ar) = jCn(Ae) \ Cn(Ar)j
jCn(Ar)j
These measures correct the drawbacks of the classical model and all the properties given Section 3.1 are satisfied. However, they bring a new problem : as the semantic closures of alignments could be infinite, then the measures may be undefined.
In order to overcome this problem, [Euzenat, 2007] introduces two new measures known as semantic precision and semantic recall.
Semantic precision measures the proportion of evaluated correspondances of Ae that can be deduced from Ar.
Ps(Ae; Ar) = jAe \ Cn(Ar)j
jAej Rs(Ae; Ar) = jCn(Ae) \ Arj jArj
Semantic recall measures the proportion of reference correspondances of Ar that can be deduced from Ae.
With these measures, the max-correctness, max-completeness, and definiteness properties are preserved. The values of semantic precision and semantic recall are greater than or equal to those of classical ones because jAe \ Cn(Ar)j > jAe \ Arj and jCn(Ae) \ Arj > jAe \ Arj. 4
Semantic precision and recall correct some drawback of classical precision and recall measure since they satisfy the max-correctness, max-completeness, and definiteness properties. Nevertheless, they do not satisfy the semantic-equality and overlappingpositiveness properties which we have introduced. This is due to the fact that these semantic measures are still dependent on the syntactic form of the alignments. 4.1
Two alignments Ae1 and Ae2 having the same closure and then, semantically equivalent, could have different precision and recall values according to Ar. This due to the fact that the semantic precision and recall are directly function of the cardinalities of the correspondences sets which could be different for two semantically equivalent alignments.
We give two examples demonstrating that semantic evaluation measures do not satisfy the semantic-equality property. In the first example, we reason only with alignment. In the second example, we show that redundancy in alignment can break the satisfaction of semantic-equality property by precision measure.
In the first example, we consider two alignments Ae1 = fx y; u vg and Ae2 = fx v y; x w y; u vg. These two alignments are equivalent since we have only replaced the equivalence x y of Ae1 by x v y and x w y in Ae2 . According to a reference alignment Ar = fx yg, the two alignments do not have the same precision values: Ps(Ae1 ; Ar) = 1=2 and Ps(Ae2 ; Ar) = 2=3. (5) (6)
In the second example, we now have the alignments Ae1 = fx y; u vg and Ae2 = fx0 v y; x y; u vg, and the knowledge o1 j= x0 v x. These two alignments are equivalent since x0 v y is redundant according to x y. Nevertheless, the semantic precision values will be different: Ps(Ae1 ; Ar) = 1=2 and Ps(Ae2 ; Ar) = 2=3 4.2
An alignment could have a null precision or/and recall value even if the intersection of its consequence sets and those of the reference is not the empty set. This due to the fact that the semantic precision and recall partially take the alignment semantic into account. A correspondance can entail several correspondances. Such a correspondance can be partially true-positive in the sense that it entails a true-positive element but also a false-negative or false-positive element. With the semantic precision and recall, such elements are entirely considered as false-positives or/and false-negatives.
For example, let be the two alignments Ae = fag and Ar = fbg, another matching relation c and the properties a j= c, b j= c, a 6j= b and b 6j= a. On this trivial example, the semantic precision and recall values are both equals to 0 even if the intersection of their Semantic closures is not equals to the empty set (i.e. c 2 Cn(Ae) \ Cn(Ar)). 5
In previous section, we highlighted some drawbacks of classical precision and recall and semantic precision and recall. The first kind of problems concerns the inability of classical and generalized precision and recall measures to reason with the alignment relations. The semantic precision and recall try to resolve this problem by using Semantic closures, but these measures are still defined on the alignment cardinality which is dependent on the syntactic form of the alignment. As a consequence, there are some cases where the semantic-equality property is not satisfied.
When this problem is entirely due to the syntactic form the alignments, we may try to resolve it by normalizing the alignment representation. We propose here a normalization strategy which relies on algebras of alignment relations [Euzenat, 2008].
Then, with the help of alignment normalization, we propose two new sets of evaluation measures. The first one concerns relaxed semantic measures based on the generalized precision and recall framework of [Ehrig and Euzenat, 2005]. Contrarily to the original generalized precision and recall measures provided in the aforementioned paper, these new measures are not only based on the syntactic form of alignment, but also on the semantic of alignments.
The second set of measures is an adaptation of ideal semantic measures of [Euzenat, 2007]. 5.1
For allowing measures to respect the semantic-equality property, it is useful to introduce a notion of a normal form for alignments. A normal form for alignments ensures that two semantically equivalent alignments have always the same syntax or form. Naturally, it is a very difficult problem but we can propose a partial solution which only considers the semantic of alignment relations. Our notion of normal form takes benefit of entailment capabilities provided by algebras of alignment relations and does not use any knowledge about the aligned ontologies.
An algebra of alignment relations [Euzenat, 2008] is a particular type of relation algebra [Tarski, 1941] defined by the tuple h2 ; \; [; ; ; ;; f g; 1 i where is the set of all elementary relations; \ and [ are set-operations used to meet and join two sets of relations, for example, if xRy or xR0y then xR [ R0y; is the composition operator, i.e. an associative internal composition law with f g as unity element; 1 the converse operator. For instance, if = f@; A; ; G; ?g, all all elementary relations, except @ and A, are there own converse and, @ 1=A and A 1=@.
Such an algebra allows to write any relation between entities (or formulas) as a disjunction of elementary relations. For example, x v y would be written xf@; gy. With the help of this relation algebra, any pair of entities or formulas will appear at most once in the alignment.
Definition 10. An alignment in normal form is an alignment A = (V; q) where the set of correspondances V satisfies the following properties: 1. V fxRyjx 2 o1 ^ y 2 o2 ^ R g: all relations between two entities (or formulas) are written with a disjunction of elementary relations. 2. 8xRy 2 V; 6 9xR0y 2 V; R = R0: any pair of entities (or formulas) appear at most once in the alignment.
Using such a normalization allows to correct classical and semantic precision and recall when relations between entities or formulas are split into several correspondances. For example, let be Ae = fx v y; x w yg and Ar = fx yg. By rewriting these alignments using disjunction of elementary relations, Ae = fxf@; g \ fA; gyg = fxf gyg and Ar = fxf gyg will be syntactically equivalent.
Of course, when this problem is due to the semantic of ontologies such a normalization is not sufficient. For example, let be Ae = fx v yg and Ar = fx v zg and the axiom y z 2 o2. These alignments are equivalent (given the previous axiom), but their normalization (Ae = fxf@; gyg and Ar = fxf@; gzg) are not equal. 5.2
In generalized precision and recall framework, evaluation measures are function of a measure quantifying the proximity between two correspondences [Ehrig and Euzenat, 2005]. We propose new proximity measures dealing partially with the semantic of alignments. We want such measures to locally respect the max-correctness and maxcompleteness properties contrarily to those provided in [Ehrig and Euzenat, 2005]: – if x0R0y0 j= xRy then prec(xRy; x0R0y0) = 1 (local max-correctness) – if xRy j= x0R0y0 then rec(xRy; x0R0y0) = 1 (local max-completeness)
In order to propose such measures, we suggest to take advantage of an algebra of alignment relations as presented in the previous section (Section 5.1). Following the example of the relaxed precision and recall, which are oriented, we introduce two new measures: prec for precision and rec for the recall. In these two measures, we do not consider the confidence values.
In a first instance, we only consider the case where we have two correspondances aligning the same entities or formulas. Let xRy and xR0y be two such correspondances. From the algebra of alignment relations, we have the following properties: – if xR0y j= xRy, then R0 – if xRy j= xR0y, then R
R,
R0.
Hence, prec and rec are defined by:
0 rec(R; R0) = jR \ R j (8) jRj
Now, for extending these measures to correspondances which do not align the same entities or formulas, we propose to use this relation algebra also with the ontologies. Definition 11 (Relaxed semantic proximity measures). Given an evaluated relation xRy, a reference relation x0R0y0, and relations deduced from ontologies, o1 j= xR1x0 and o2 j= yR2y0, the relaxed semantic proximities prec and rec are defined by: prec(xRy; x0R0y0) = jR \jR1R1R0R0R2R12j 1 j 1 rec(xRy; x0R0y0) = j(R1 jR1
R 1
R2) \ R j
0 R
R2j
The relaxed semantic proximity measures satisfy the local max-correctness and local max-completeness properties. As a consequence, they allow to provide relaxed semantic precision and recall measures which partially deals with alignment semantics. However, such measures do not consider the whole alignment semantic and then, they do not necessarily satisfy any property mentioned Section 3.1.
In our opinion, these semantic proximity measures are a first step for providing new semantic evaluations measures satisfying the desired properties. However, for satisfying these properties, it would be essential to propose new generalized precision and recall measures. 5.3
In order to deals with the semantic of alignments on one hand, and ideal precision and recall on the other hand, we first propose to use a partial closure of alignment instead of its full closure ( -consequence set). This partial closure has the advantage to be finite (7) (9) (10) but in counterpart, it is defined relatively to a set of alignments. As a consequence, the ideal precision and recall can be computed, but their values depend on the set of considered alignments . In a the case of evaluation campaigns, the set = Ae1 [ ::: [ Aen [ Ar will contain all correspondences provided by the participants, and the reference alignment.
ment V given an alignment (V ) is defined as a set of correspondances issued from which can be deduced from V .
V += = Cn(V ) \ (11)
The bounded closure V += of an alignment V is finite when is finite (i.e. each alignment in is finite). From this bounded closure definition, we provide -bounded precision and recall.
dences , the precision of an alignment Ae in comparison to a reference alignment Ar is:
P (Ae; Ar) = jAe+= jAe+= j
\ Ar+= j R (Ae; Ar) = jAe+= jAr+= j \ Ar+= j (12) (13)
dences , the recall of an alignment Ae in comparison to a reference alignment Ar is:
With these measures the max-correctness, max-completeness, definiteness are verified. The semantic-identity property is also satisfied for each semantically equivalent alignments belonging to (but not necessarily for the others). Still the overlappingpositiveness is not satisfied: Ae+= \ Ar+= = ; 6 =) Cn(Ae) \ Cn(Ar) = ;
These measures are defined in the case of expressive alignments but they are dependent of and consequently the precision and recall value are not absolute. Hence, these measures are useful for comparing a finite set of systems, but do not provide an absolute measure of precision and recall with regard to a reference alignment. 6
In this paper, we presented and analyzed several ontology alignment evaluation propositions. Actually, no concrete evaluation measure respects the semantic-equality and the overlapping-positiveness properties that an ideal semantic model should satisfy. More precisely, the semantic precision and recall measures cannot respect the semanticequality due to the facts they still depend on the syntactic representation of alignments. To overcome these limitations, we first introduced alignment normalization principles which partially resolve the problem of semantic-equality. Then, we also proposed two new sets of evaluation measures. The first set of measures is built upon the generalized precision and recall framework and allows to locally consider the semantics of alignments. These measures can be seen as semantic-relaxed precision and recall. The second set of measures is proposed from an adaptation of ideal semantic measures. This adaptation makes the ideal semantic measures useable but in counterpart they do not verify the overlapping-positiveness property any more.