In this work we present GOAL (Genetics for Ontology Alignments) a new approach to compute the optimal ontology alignment function for a given ontology input set. Although this problem could be solved by an exhaustive search when the number of similarity measures is low, our method is expected to scale better for a high number of measures. Our approach is a genetic algorithm which is able to work with several goals: maximizing the alignment precision, maximizing the alignment recall, maximizing the f-measure or reducing the number of false positives. Moreover, we test it here by combining some cutting-edge similarity measures over a standard benchmark, and the results obtained show several advantages in relation to other techniques.
The Semantic Web is a new paradigm for the Web in which the semantics of
information is de ned, making it possible for the web to understand and satisfy
the requests of people and machines to use the web resources. Therefore, most
authors consider it as a vision of the Web from the point of view of an universal
medium for data, information, and knowledge exchange [
In relation to knowledge, it is very important the notion of ontology as a form of representation about a particular universe of discourse or some part of it. Ontology alignment is a key aspect in order to the knowledge exchange in this extension of the Web may be real; it allows organizations to model their own knowledge without having to stick to a speci c standard. In fact, there are two good reasons why most organizations are not interested in working with a standard for modelling their own knowledge: (a) it is very di cult or expensive for many organizations to reach a agreement about a common standard, and (b) these standards do not often t to the speci c needs of the all participants in the standarization process.
Altought ontology alignment is perhaps the most valuable way to solve the
problems of heterogeneity and, even there are a lot of techniques for aligning
ontologies in a very accurate manner, experiences tells us that the complex
nature of the problem to be solved makes di cult that these techniques operate
in a satisfactory way for all kinds of data, in all domains, and as all users expect.
This problem has been studied in [
As a result, techniques that combine existing methods have appeared. The goal of these techniques is to obtain more complex and accurate matching algorithms. The way to combine these matching algorithms is under an exhaustive research now. The most promising mechanisms are reviewed in the Section 6, but we can advance that the use of Genetic Algorithms (GAs) has been studied in little depth by researchers. Therefore, the main contributions of this work are: { The proposal of an e cient mechanism, other than those that already exist, to compute the optimal function for aligning arbitrary sets of ontologies. { The additional possibility to obtain goal-driven results, thus optimize some of the characteristics of an output alignment. { We provide results following a standard benchmark to enable the comparison with other approaches.
The rest of this work is structured in the following way: Section 2 describes
the problem statement. Section 3 presents the technical preliminaries which are
neccesary to our approach. Section 4 discusses our aproach. Section 5 ndings
extracted from several experiments, including the use of a benchmark provided
by the Ontology Alignment Evaluation Initiative [
The process of aligning ontologies can be expressed as a function f where given a pair of ontologies o and o0, an partial (and optional) input alignment A, a set of parameters p and a set of resources r, returns a new alignment A0:
A0 = f (o; o0; A; p; r)
A0 is a set of mappings. A mapping is an expression that represents a semantic correspondence between two entities. A mapping is the atomic component of an alignment and is a formalism that allows to share knowledge models created separately.
However, experience tells us that getting f is far from trivial. As we commented earlier, the heterogeneity and ambiguity of data descriptions makes unrealistic the scenario in which that optimal mappings for many pairs of entities will be considered as "best mappings" by any of the existing matching algorithms. For instance, the Fig. 1 shows an alignment that is valid for users from some countries, but not for some others. The current trend is to diversify (and possibly weight) the matching algorithms. To do it, it is neccesary to use composite ontology matchers.
Composite matchers are aggregation of simple matchers which exploit a wide
range of information, in fact, we can classify the matching algorithms in the
following types:
1. String normalization. This consists of methods such as removing
unnecessary words or symbols from the entity names. Moreover, they can be used
for detecting plural nouns or to take into account common pre xes or su xes
as well as other natural language features.
2. String similarity. Text similarity is a string based method for identifying
similar entity names. For example, it may be used to identify identical
concepts of two ontologies if they have a similar name. The reader can see [
The main idea of composite matchers is to combine similarity values predicted
by multiple simple algorithms to determine correspondences between entities
belonging to di erent ontologies. The most popular proposals in this eld are
COMA [
De nition 1 (Similarity measure). A similarity measure sm is a function
sm : 1 2 7! < that associates the similarity of two input ontology entities
1 and 2 to a similarity score sc 2 < in the range [
similarity measures and w a numeric weight vector, and let O1, O2 be two input ontologies, then we can de ne wsm as a weighted similarity measure in the following form: wsm(O1; O2) = x 2 [0; 1] 2 < ! 9 hA; wi ; x = max(Pii==1n Ai wi) subject to Pii==1n wi 1
From an engineering point of view, this function leads to an optimization problem for calculating the numeric weight vector, because the number of candidates from the solution space (in this case an arbitrary continous interval) is in nite. Hence, exact techniques are of low help here, and we are interested in methods such metaheuristics (e.g.g genetic algorithms) that nd quasi optimum results in such solution spaces.
tuples f(id; e; e0; n; R)g. Where id is an unique identi er of the mapping, e and e0 are entities belonging to two di erent ontologies, R is the relation of correspondence between these entities and n is a real number between 0 and 1 that represents the mathematical probability that R is true. The entities that are related are the concepts, roles, rules, and even axioms of the two ontologies.
a function om : O1 O2 s!m A that associates two input ontologies O1 and O2 to an alignment A using a similarity measure (or a weighted similarity measure).
tion ae : A AR 7! precision recall that associates an alignment A and an reference alignment AR to two real numbers in the interval [0; 1] stating the precision and recall of A in relation to AR.
Code 1 shows an example of an output from an alignment evaluation process
where two ontologies from a standard benchmark provided by the OAEI [
We are beginning our research. First, we are going to consider GAs. Later, we may consider other approaches. GAs are often used to search along very high dimensional problems spaces. For example, if we want to nd the maximum value of the function wsf with three independent variables w0, w1 and w2: w0 datatype(O1; O2) + w1
wsf (O1; O2) =
normalization(O1; O2) + w2 synonyms(O1; O2)
where w0, w1 and w2 are weights to determine the importance of the three
respective similarity measures, which belong, for instance, to the continuous
interval [
While this problem can be solved trivially by a brute force search over the range of the independent variables w0, w1 and w2, the GA method scales very well to similar problems of a higher dimensionality; for example, we might have functions using a large number of independent variables w0, w1, w2,..., wn. In this case, an exhaustive search would be prohibitively expensive. { Characterize the problem by encoding in a string of values the contents of a tentative solution. { Provide a numeric tness function that will allow to rate the relative quailty of each individual tentative solution in a population.
That is what we are going to do with GOAL. Our rst task is to characterize
the search space as some parameters. We need to encode several parameters
in a single chromosome, so we have designed a method for converting a bit
representation to a set of oating-point numbers in the real range [
Later, we haved designed a tness function to determine which chromosomes in the population are most likely to survive and reproduce using genetic crossover and mutation operations.
Related to the tness function, we can choose any parameter provided for the alignment evalution process. In this way, we are providing the possibility to select one of these goals.
{ Optimizing the precision (f itness := precision) { Optimizing the recall (f itness := recall) { Optimizing the f-measure (f itness := f measure) { Reducing the number of false positives (f itness := f all out)
The tness function consist of selecting one of the parameters retrieved by
an Alignment Evaluation (see De nition 5). All of these parameters are concepts
used in Information Retrieval [
Our algorithm works under the paradigm of a single goal programming strategy, but optimizing the F-Measure (a weighted sum of precision and recall) has an e ect similar to a multi-objetive strategy. However, a brief discussion about using a multi-objetive algorithm will be presented as future work. 5
In this section, we provide an empirical evaluation of our approach. To do that,
we have worked with the well-known benchmark provided by the OAEI [
We are going to do a preeliminary study of the parameters for the algorithm. { For the number of genes per chromosome we have selected such values as 5, 10 and 20. A study using a t-Test distribution has shown us that that the di erences between samples are not statistically signi cant. Therefore, we have selected 20 genes per chromosome. { For the number of individuals in the population, we have selected such values as 20, 50 and 100. Again, a t-Test statistical distribution has shown that the di erences between these samples are not statistically signi cant. So we have selected a population of 100 individuals. { Related to crossover and mutation fraction, we have choosen a high value for the crossover between genes and, a little percentage for mutations, because we wish a classical con guration for the algorithm. { After ten independent executions, we noticed that the genetic algorithm does not improve the results beyond the fth generation, so we have set a limit of ve generations. 5.2
Related to the conditions of the experiment, we have used: { As similarity measure vector:
fLevhenstein[
We allow 5 generations { The platform characteristics: Intel Core 2 Duo, 2.33GHz and 4GB RAM.
The way that we have choosen for providing the dynamic evaluation of the alignment uses the following formulas:
P recision = frelevant mappingsg \ fretrieved mappingsg
frelevant mappingsg Recall = frelevant mappingsg \ fretrieved mappingsg
fretrieved mappingsg F M easure = 2 precision recall precision + recall F allout = fnon relevant mappingsg \ fretrieved mappingsg
fnon relevant mappingsg
Now, let us discuss the results we have obtained. Table 1 shows a brief description about the purpose of each test of the benchmark.
Table 2 shows the results from a Precision-Driven test, the Table 3 shows the results from a Recall-Driven test, the Table 4 shows results from a F-MeasureDriven test and, nally Table 5 shows the empirical data from a Fall-out-driven test. 1 Fitness and search space have been explained in the previous section
Brief explanation
Strictly identical ontologies
A regular ontology and a null ontology A regular ontology and other with a language generalization
A regular ontology and other with a language restriction
Ontologies without entity names
Ontologies without entity comments Ontologies without entity names and comments
Ontologies with di erent naming conventions
Ontologies whose labels are synonymous Ontologies whose labels are in di erent languages
A regular ontology and other with no specialisation A regular ontology and other with a atenned hierarchy A regular ontology and other with a expanded hierarchy
Identical ontologies without instances
Identical ontologies without restrictions
A real ontology about bibliography made by MIT
Table 1. Explanation of the performed tests Ontology 101 102 103 104 201 202 203 204 205 206 221 222 223 224 225 301
As it can be seen, we have found the optimal alignment function for the majority of tests. In this way, we could cover matching cases, and therefore increase the chances of success. Some of test cases are solved in the rst generation, this is because our application is not very di cult, maybe the problem is, but these speci c instances are not. 6
If we look at literature, we can distinguish between individual algorithms (i.e.
FCA-MERGE [
The problem is that those kinds of proposals use weights de ned by an expert for con guring the composite matchers, while using our approach involves to compute the weigths in an automatic way, so the process can be more exible, at least, in real scenarios.
To avoid the expert intervention, there are two research lines; one line for
evaluating the results of an alignment tool and maybe feedback the process
[
However, exhaustive searches are very expensive, and unworkable when
combining a great number of measures, from a computational point of view.
Unfortunately, the paper from eTuner [
Based on Machine Learning meta-matching techniques can be divided into two
subtypes: Relevance feedback [
However, these kind of solutions implies spending much time on training the
systems in relation to our proposal.
In relation to other based-on-Genetic-Algorithm solutions, the most oustandig
tool is GAOM [
Table 7 shows a comparison of the results we have obtained for both GAOM and GOAL.
Although we also follow a GA based paradigm, our GOAL is slightly better in terms of numbers to GAOM as our results shows. We think that the main diference in relation to the other tool is the tness function. Therefore, as far as we know, our results constitute the new state of the art (S.O.T.A.) in this domain. 7
We have here presented a mechanism for obtaining optimum ontology alignment functions using genetic algorithms which is part of a novel computational discipline, called meta-matching, which allows exible and accurate automatic ontology matching and generalizes and extends previous proposals for exploiting an ensemble of ontology matchers.
We have shown that our proposal is able to nd the optimal solutions for ontology alignment in most cases. According to the results, our approach seems to be an accurate and e cient tool for this task. And most importantly, it can be used in a single goal-driven way versus others using composite matching algorithms.
However, this mechanism is heavily dependent of the similarity measures to be weighted. By this reason, we highly recommend to use not only cutting-edge measures, but a big enough and representative set of them. We recommend to use, at least, one similarity measure for each kind of the matchers discussed in Section 2.
As future work, we want to study a multiobjetive strategy, thus, we plan to
avoid unwanted deviations from precision and recall values. Moreover, we want
to learn more about [
This work has been funded by Spanish Ministry of Education & Science through the research projects: A basic infrastructure for development in the Semantic Web and its application to conceptual mediation in Bioinformatics. (TIN200509098-C05-01) and Net Centric Optimization. (TIN2005-08818-C04-01).