Ontology alignment based on instance using NSGA-II

Abstract

Nowadays, ontologies are widely used to solve data heterogeneity problems on the Semantic Web. However, simple use of these ontologies may raise the heterogeneity problem to a higher level. Addressing this problem requires identification of correspondences between the entities of various ontologies. Since the real semantics of a concept is often better defined by the actual instances assigned to it, instance, as an important element of ontology, contains a great quantity of knowledge that should be utilized to obtain the ontology alignment. To this end, in this paper, we propose a novel instance-based aligning approach using NSGA-II to determine the optimal instance correspondences and a similarity propagation algorithm that makes use of various semantic relations to propagate the similarity values to other entities of ontologies. The experiment of comparing our approach with the participants of OAEI 2012 has demonstrated that our method is an effective approach that can obtain the alignment with high precision value.

Keywords

Instance-based aligning NSGA-II ontology alignment similarity propagation

1. Introduction

Nowadays, ontologies are widely used to solve the data heterogeneity problems on the Semantic Web. However, because of human subjectivity, different ontologies may define an entity in various ways or with different names, which further raises the so-called heterogeneity problem. Addressing this problem requires identification of correspondences between the entities of various ontologies. This process is commonly known as ontology alignment, which can be described as follows: given two ontologies, each describing a set of discrete entities (which can be classes, properties, predicates, etc.), find the relationships (e.g. equivalence or subsumption) that hold between these entities [1]. However, manually aligning the ontologies is time-consuming, error-prone and clearly not possible on the Web scale since the ontology size is very large. Thus the development of the alignment systems to assist the ontology alignment is crucial to the success of Semantic Web.

Numerous matching systems have arisen over the years and each of them could, in a fully automatic or semi-automatic way, provide a numerical value of similarity between elements from separate ontologies that can be used to decide whether those elements are semantically similar or not. In general, the similarity measures used in these matching systems can be divided into four broad categories: (a) the syntactic measure, which computes a string distance or edit distance between the ontology entities; (b) the linguistic measure, which calculates the similarity between ontology entities by considering linguistic relations such as synonymy and hypernym; (c) the taxonomy-based measure, which utilizes the specialization relation, for example, the subsumption relation, in ontologies to calculate the similarity between ontology entities; and (d) the instance-based measure, which exploits the similarity between classified instances to discover the correspondences between the concepts in ontologies. However, to the best of our knowledge the current matching systems mainly make use of the schema-level similarity measure, that is, the syntactic measure, linguistic measure and taxonomy-based measure to determine the correspondence between entities of different ontologies, and there are few systematic studies of instance-based similarity measure. Since the real semantics of a concept are often better defined by the actual instances assigned to it, instance, as an important element of ontology, contains a great quantity of knowledge that should be utilized to obtain the ontology alignment. In addition, techniques for ontology instance matching are required in several application contexts, for example, semantic integration, identity recognition and ontology population, where the capability of comparing different individuals with the goal of recognizing the same real-world object is demanded and the application of instance matching is crucial [2].

With the intuition that similarity between the instances of two concepts reflects the semantic similarity of these concepts, the goal of the instance-based approach is to determine the similarity between concepts of different ontologies by matching sets of annotated instances of them. To this end, in this paper, we propose a novel instance-based aligning approach by using NSGA-II to determine the optimal instance correspondences and a similarity propagation algorithm that makes use of various semantic relations to propagate the similarity values to other entities of ontologies.

The rest of the paper is organized as follows: Section 2 describes the relation work of this paper; Section 3 illustrates some important basic concepts of ontology and ontology alignment; in Section 4, the similarity measures and similarity propagation algorithm are presented; Section 5 proposes a problem-specific NSGA-II for instance-based ontology alignment; Section 6 shows the experimental results; finally, Section 7 draws the conclusions and proposes some further improvements.

2. Related work

2.1. Instance-based ontology matching

With the increasing popularity of Web 2.0 and Semantic Web technologies, where data are usually provided with a poor schema/metadata specification, the research work on ontology matching is gradually shifting from the level of concepts to the level of instances. During the past few decades, more and more instance-based ontology matching approaches and techniques have been proposed and employed in the ontology matching systems. FCA-Merge [3] and T-Tree [4] make use of the instance-based approach to improve the aligning results obtained by subclass and superclass relationships for each entity as well as the lexical correspondences. GLUE [5] discovers mappings through multiple learners that analyse the taxonomy and the information within concept instances of ontologies, and then use Bayesian decision theory and user input to generate an alignment between ontologies. IF-Map [6] matches two ontologies by first examining their instances to see if they can be assigned to concepts in a reference ontology, and then using formal concept analysis to derive an alignment. In all these matching systems, the instance matching approach is just used to implement other matching approaches or improve the aligning results. However, in our work, the instance matching approach is the kernel technology assisting with other matching approaches.

2.2. Genetic algorithm for ontology alignment

Among ontology matching systems that make use of the Genetic Algorithm (GA), the most notable one is GOAL (Genetics for Ontology ALignments) [7]. GOAL does not directly compute the alignment between two ontologies, but it determines, through a GA, the optimal weight configuration for a weighted average aggregation of several similarity measures by considering a reference alignment. The same idea of implementing a matching system to combine multiple similarity measures into a single aggregated metric is also developed in two more recent papers [8, 9]. In this paper, our proposal is different from these approaches in two aspects: (a) we use Multi-Objective Evolutionary Algorithm (MOEA) rather than GA with a single objective to determine the ontology alignment; and (b) our approach is based on instance level instead of schema level. To be specific, all the matching systems mentioned above work with one objective, that is, to maximize the F-measure (which is introduced in Section 3.2), to evaluate the quality of an alignment. However, simple use of the F-measure may lead to bias improvement, which derives from an improvement in one of the metrics at the expense of a decrement in the other. To overcome this defect, we propose to utilize the NSGA-II (fast Non-dominated Sorting Genetic Algorithm) [10], whose objectives are to maximize both the recall and precision (which are presented in Section 3.2), to determine the ontology entity correspondences. In addition, to the best of our knowledge this is the first time that MOEA has been applied to align the ontologies based on their instances to improve the quality of ontology alignment.

2.3. MOEA

Multi-objective Evolutionary Algorithm is an integral part of optimization activities and has tremendous practical importance, since almost all real-world optimization problems are ideally suited to being modelled using multiple conﬂicting objectives. A variety of Pareto-based MOEA have been proposed in the last decade, including the non-dominated sorting genetic algorithm (NSGA) [11] and NSGA-II [10], the strength Pareto evolutionary algorithm (SPEA) [12] and SPEA2 [13], the Pareto archived evolution strategy (PAES) [14], the Pareto differential evolution algorithm (PDE) [15], the non-dominated sorting particle swarm optimizer (NSPSO) [16], the constrained nonlinear multi-objective optimization immune algorithm (CNMOIA) [17], the co-evolutionary particle swarm optimization algorithm (CCPSO) [18], the dominating-tree based multi-objective evolutionary algorithm (DTEA) [19], the adaptive multi-objective particle swarm optimization algorithm (MO-TRIBES) [20], the hybrid MOEA with two crossover operators [21] and the multi-objective endocrine particle swarm optimization algorithm (MOEPSO) [22]. Moreover, in [23], a new MOEA with Min–Max Strategy and Sphere Coordinate Transformation is proposed to overcome the drawbacks of the algorithms using the weighted sum of the objectives, and explore the objective space to find approximate uniformly distributed solutions on the Pareto front gradually.

Since the early development of MOEAs in 1993, they have been applied to many real-world and interesting optimization problems. In Niknam et al. [24], MOEA was applied for volt/varcontrol in distribution networks, which simultaneously and effectively minimizes electrical energy losses, voltage deviations, total electrical energy costs and total emissions of renewable energy sources and grid. In Ahmadi et al. [25], MOEA is used for the optimal design of a polygeneration energy system, which considers minimizing the total cost rate of the system while maximizing the system energy efficiency. References [26 –28] present the studies on the application of MOEA in the field of sustainable and renewable energy. In Liu et al. [29], MOEA are also utilized to solve the WCDMA Network Planning. However, there are very few studies of MOEA in solving the ontology aligning problem. The only ontology alignment system that exploits a multi-objective evaluation is MapPSO [30]. However, this work uses an evaluation method based on multiple objectives following an a priori approach, that is, it aggregates all objectives in a weighted function. In order to overcome the well-known drawbacks of a priori methods, in this work, we propose to apply NSGA-II to the ontology alignment problem.

3. Basic concepts

3.1. Ontology and ontology alignment

There have been many definitions of ontology over years. However, the most frequently referenced one was given by Gruber in 1993, which defined the ontology as an explicit specification of a conceptualization. For convenience of the work in this paper, an ontology can be defined in Definition 1.

Definition 1 [31]: an ontology is a triple, $O = (C, P, I)$ , where

$C$ is the set of classes, that is, the set of concepts that populate the domain of interest;

$P$ is the set of properties, that is, the set of relations existing between the concepts of domain; and

$I$ is the set of individuals, that is, the set of objects of the real world, representing the instances of a concept.

In general, classes, properties and individuals are referred as entities.

Ontologies are seen as the solution to data heterogeneity on the web. However, the existing ontologies could themselves introduce heterogeneity: given two ontologies, the same entity can be given different names or simply be defined in different ways, whereas both ontologies may express the same knowledge but in different languages [32]. To solve this problem, a so-called ontology alignment process is necessary. Formally, an alignment between two ontologies can be defined as presented by Definition 2.

Definition 2 [31]: an alignment between two ontologies is a set of mapping elements. A mapping element is a 4-tuple $(e, e', n, r)$ , where

$e$ and $e'$ are the entities of the first and the second ontology, respectively;

$n$ is a confidence measure in some mathematical structure (typically in the [0,1] range) holding for the correspondence between the entities $e$ and $e'$ ; and

$r$ is a relation (typically the equivalence) holding between the entities $e$ and $e'$ .

In principle, all relations between entities in the given ontology language can be used as the correspondence relation, and in this thesis, there is no distinction between different correspondence relations. Indeed the interpretation of correspondences and alignments is strongly use-case-dependent. However, in many cases, a correspondence between ontological entities is thought of as expressing that those entities are ‘equivalent’ or at least somewhat ‘similar’. Depending on the interpretation of correspondences, they can have an impact on the semantics of entities defined in the ontologies to the point of introducing incoherency or inconsistency. Irrespective of the correspondence interpretation in the use case, a common assumption is to regard a correspondence as an equivalence axiom for the two corresponding entities.

Definition 3 [31]: the alignment process can be seen as a function $φ$ that, from a pair of ontologies $O$ and $O'$ to align, an input alignment $A_{I}$ , a set of parameters $p$ and a set of resources $r$ , returns a new alignment $A_{N}$ between these ontologies – $A_{N} = φ (O, O', A_{I}, p, r)$ .

The ontology alignment process computes a mapping element by using a similarity measure, which determines the closeness value $n$ (related to a given relation $R$ ) between the entities $e$ and $e'$ in the range [0,1], where 0 stands for complete inequality and 1 for complete equality.

Since the quality of resulting alignment and the correctness and completeness of the correspondences found already, need to be assessed, we will introduce some conformance measures that derive from the information retrieval field in the next section.

3.2. Alignment evaluation

The alignment is normally assessed on the basis of two measures commonly known as recall and precision [33]. Recall (or completeness) measures the fraction of correct alignments found in comparison to the total number of correct existing alignments. A recall of 1 means that all of the alignments have actually been found, but it does not provide the information about the number of additionally falsely identified alignments. Typically, recall is balanced against precision (or correctness), which measures the fraction of found alignments that are actually correct. A precision of 1 means that all found alignments are correct, but it does not imply that all alignments have been found. Therefore, recall and precision are often balanced against each other with the so-called F-measure, which is the uniformly weighted harmonic mean of recall and precision. However, when two alignments’F-measures are equal, it is difficult to say which one is better or has less bias to recall or precision.

Given a reference alignment $R$ and an alignment $A$ , $recall$ , $precision$ and $F - measure$ are given by the following formulas:

recall = \frac{| R \cap A |}{| R |}

(1)

precision = \frac{| R \cap A |}{| A |}

(2)

F - measure = 2 \times \frac{precision \times recall}{precision + recall}

(3)

4. Instances similarity measure and similarity propagation algorithm

In this section, two basic technologies of our instance-based matching approach, that is, the instance similarity measure and the similarity propagation algorithm, are presented. The second technology can be further divided into two steps: (a) propagate the similarity from instances to their direct related concepts; and (b) propagate the similarity between concepts.

4.1. Instance similarity measure

The instance similarity measure determines the similarity of two instances by executing a pair-wise comparison of property values using a similarity function. The result is a similarity matrix with each dimension representing the properties of one instance. Then the matrix is aggregated into one value that defines the similarity of these two instances. This aggregation is done by applying the following formula:

similarity (instanc e_{1}, instanc e_{2}) = \frac{\sum_{i = 1}^{m} {max}_{j = 1 \dots n} (sim (pro p_{ins t_{1} i}, pro p_{ins t_{2} j})) + \sum_{j = 1}^{n} max_{i = 1 \dots m} (sim (pro p_{ins t_{1} i}, pro p_{ins t_{2} j}))}{m + n}

(4)

where

$m$ is the number of properties of $instanc e_{1}$ and $n$ is the number of properties of $instanc e_{2}$ ;

$pro p_{ins t_{1} i}$ is the $i$ th property of $instanc e_{1}$ and $pro p_{ins t_{2} j}$ is the $j$ th property of $instanc e_{2}$ ;

$sim ()$ is the similarity function that returns the similarity value of $pro p_{ins t_{1} i}$ and $pro p_{ins t_{2} j}$ .

This formula uses for every property of $instanc e_{1}$ the highest similarity to a property of $instanc e_{2}$ and vice versa. These maxima are added and the resulting sum is divided by the number of all instances.

In our work, the similarity value of two properties is determined by considering four aspects, that is, the instance’s Uniform Resource Identifier (URI), the property’s name, data type and data value. First, we compare two instances’ URI to judge whether they refer to the same real-world entity, which could simplify the process of similarity measuring. Two instances with the same URI will be regarded as equal instances, otherwise we first calculate the similarity value of two properties’ names and data types by applying both the syntactic measure, specifically the Levenstein distance and Jaro distance, and linguistic measure. Then, with respect to the similarity measure of the property’s data value, for each specific attribute data type, for example, date, time and real number, appropriate matching techniques are provided to calculate the similarity of attribute values. As an example, approaches for matching numerical values use conversion functions to determine how to transform values of a source data type (e.g. real values) into corresponding values of a target data type (e.g. integer values). However, most of the work on the similarity measure of data values has been focused on computing the similarity of strings owing to the fact that string data are the most frequently used data types for real-world instance descriptions. Specifically, in our work, the Q-Gram distance, which is based on string tokens, is applied to obtain the similarity between two data values of different conventions for describing data (e.g. ‘Jack Smith’ and ‘Smith, Jack’). Finally, the similarity value of two instances is determined by the average of those of their properties’ name, data type and data value.

A measure is a kind of index that is used to judge some characteristic of the objective in particular scenario, for example, in Jia et al. [34], Rand Index is used to measure the clustering accuracy for reference. However, different from [34], in our work, we mainly focus on how to measure the similarity value of two words in syntactic and linguistic terms. Therefore, in the following, we present two similarity measures, that is, the syntactic measure and linguistic measure, which are used in our work.

4.1.1. Syntactic measures

Syntactic measures compute a string distance or edit distance between the ontology entities. In our work, we utilize two widely used syntactic measures: the Levenstein distance [9] and the Jaro distance [39].

The Levenstein distance calculates the number of operations, such as modifications, deletions and insertions of a character, which are necessary to transform one string into another. Formally, the Levenstein distance between two strings $s_{1}$ and $s_{2}$ is defined by the following equation:

Levenstein (s_{1}, s_{2}) = max (0, \frac{min (| s_{1} |, | s_{2} |) - d (s_{1}, s_{2})}{min (| s_{1} |, | s_{2} |)})

(5)

where

$| s_{1} |$ and $| s_{2} |$ are the lengths of strings $s_{1}$ and $s_{2}$ , respectively; and

$d (s_{1}, s_{2})$ is the number of operation necessary to transform $s_{1}$ into $s_{2}$ .

Another measure is the Jaro distance, an edit distance that uses the number of common characters in the two strings and the positions at which they appear. Given strings $s_{1}$ and $s_{2}$ , the Jaro distance is defined as follows:

JaroDistance (s_{1}, s_{2}) = \frac{1}{3} \times (\frac{com (s_{1}, s_{2})}{| s_{1} |} + \frac{com (s_{1}, s_{2})}{| s_{2} |} + \frac{com (s_{1}, s_{2}) - trans (s_{1}, s_{2})}{com (s_{1}, s_{2})})

(6)

where

$| s_{1} |$ and $| s_{2} |$ are the lengths of strings $s_{1}$ and $s_{2}$ , respectively;

$com (s_{1}, s_{2})$ is the number of common characters of $s_{1}$ and $s_{2}$ ; and

$trans (s_{1}, s_{2})$ is the number of pairs consisting of common characters that appear in different positions.

Q-gram distance is a token-based technique that measures the similarity of two strings by the common string tokens they have. Specifically, given two token sets of strings $s_{1}$ and $s_{2}$ , which are obtained by separating the strings using the characters ‘#’, ‘−’, ’,’ blank space and strings $s_{1}$ , $s_{2}$ , respectively, the Q-gram distance can be calculated by the following formula:

QGramDistance (s_{1}, s_{2}) = \frac{(m + n) - \sum_{i = 1}^{t} | tokens (toke n_{i}, s_{1}) - tokens (toke n_{i}, s_{2}) |}{m + n}

(7)

where

$m$ and $n$ are the cardinalities of token sets $s_{1}$ and $s_{2},$ respectively, and $t$ is the cardinality of the union of two token sets; and

$tokens (toke n_{i}, s_{1})$ gets the number of the $toke n_{i}$ , which is the $i$ th token in the union of two token sets, appearing in the string $s_{1}$ , and $tokens (toke n_{i}, s_{2})$ is similar.

4.1.2. Linguistic measures

The linguistic measure calculates the similarity between ontology entities by considering linguistic relations such as synonymy and hypernym. To compute the linguistic similarity or inversely the linguistic distance, a lexicon and thesaurus is needed, the most popular one used to identify the relationships between entities being WordNet [35]. WordNet is an electronic lexical database where various senses of words are put together into sets of synonyms, and it can be used to calculate a synonymy-based distance by considering the names of entities. In detail, given two words $w_{1}$ and $w_{2}$ , $LinguisitcDistance (w_{1}, w_{2})$ equals:

1, if the words $w_{1}$ and $w_{2}$ are synonymous;

0.5, if the word $w_{1}$ is the hypernym of $w_{2}$ or vice versa;

0, otherwise.

Next, we present an additional function that refers to the concept of upPropagation [36], in which the similarities between instances are propagated to their concepts.

4.2. Similarity propagation algorithm

Similarity propagation is necessary because we have to deal with incomplete instance situation, that is, not every concept has instances and normally only leaves of a schema have instances. Specifically, in this paper, the proposed similarity propagation algorithm based on the instance mappings first propagates the similarity from instances to their directly related concepts, based on the idea that concepts that have similar instances are similar too. In our work, the algorithm propagates the instance similarity to their direct concepts because they have the strongest relationship. Specifically, given two concepts $c_{1}$ and $c_{2}$ and their direct instance set $s_{1}$ and $s_{2}$ , the similarity value of $c_{1}$ and $c_{2}$ can be calculated by the following formula:

similarity (c_{1}, c_{2}) = \frac{\sum_{i = 1}^{m} {max}_{j = 1 \dots n} (sim (ins t_{c_{1} i}, ins t_{c_{2} j})) + \sum_{j = 1}^{n} \max_{i = 1 \dots m} (sim (ins t_{c_{1} i}, ins t_{c_{2} j}))}{m + n}

(8)

where

$m$ and $n$ are the cardinalities of $s_{1}$ and $s_{2}$ , respectively;

$ins t_{c_{1} i}$ is the $i$ th instance of $c_{1}$ and $ins t_{c_{2} j}$ is similar;

$sim ()$ is the similarity function that returns the similarity value of $ins t_{c_{1} i}$ and $ins t_{c_{2} j}$ by using the instance similarity measure.

This formula uses for every instance of $c_{1}$ the highest similarity to an instance of $c_{2}$ and vice versa. These maxima are added and the resulting sum is divided by the number of all instances.

Then the algorithm propagates the similarity between the concepts through two kinds of semantic relations, that is, subsumption and object property. Specifically, we first initialize the object property mappings by considering the name and comment values using Q-gram measure. Then an iterative process of updating the concept mappings and object property mappings is carried out until no new concept mapping could be found. During the updating process, the maximum similarity value of concept mapping or object property mapping will be saved. The outline of the similarity propagation algorithm is presented in Figure 1.

Figure 1.

Outline of similarity propagation algorithm.

Given two concepts $c_{1}$ and $c_{2}$ and their direct subclass sets $s c_{1}$ and $s c_{2}$ , in our work, the $Cmappings$ updating process through the subsumption relation is based on the following formula:

s i m i l a r i t y (c_{1}, c_{2}) = \frac{\sum_{i = 1}^{m} \max_{j = 1 \dots n} (s i m (s u b C o n c e p t_{c_{1} i}, s u b C o n c e p t_{c_{2} j})) + \sum_{j = 1}^{n} \max_{i = 1 \dots m} (s i m (s u b C o n c e p t_{c_{1} i}, i n s t s u b C o n c e p t_{c_{2} j}))}{m + n}

(9)

where

$m$ and $n$ are the cardinalities of $s c_{1}$ and $s c_{2}$ , respectively;

$subConcep t_{c_{1} i}$ is the $i$ th subconcept of concept $c_{1}$ and $subConcep t_{c_{2} j}$ is the $j$ th subconcept of concept $c_{2}$ ; and

$s i m ()$ is the similarity function that returns the similarity value of $subConcep t_{c_{1} i}$ and $subConcep t_{c_{2} j}$ .

In addition, given the similarity value of two object properties $o p_{1}$ and $o p_{2}$ , if the similarity value of their domain classes $d c_{1}$ and $d c_{2}$ is determined, the similarity value of their range classes $r c_{1}$ and $r c_{2}$ can be obtained by the average of the similarity value of $o p_{1}$ , $o p_{2}$ and that of $d c_{1}$ , $d c_{2}$ , and vice versa. Moreover, the similarity value of two object properties $o p_{1}$ and $o p_{2}$ is determined by the average of the similarity value of their domain classes and that of their range class.

Finally, the data property mapping $DPmappings$ is generated by considering the similarity of their related concepts, the data property’s name, comment, data type, constraints and the constraints’ cardinality. All the similarities mentioned above are obtained by the syntactic measure and linguistic measure, and the average of them taken as the similarity value of two data properties. The alignment to be evaluated is obtained by combining $Cmappings$ , $OPmappings$ and $DPmappings$ .

5. NSGA-II for instance-based ontology alignment

The process of determining the optimal instance mapping set in order to yield the alignment with the best quality can be regarded as an optimizing process. In the following, given two ontologies $O_{1}$ and $O_{2}$ to align, the Multi-Objective Optimal Model for the instance-based ontology alignment is first presented, and then the details of a problem-specific NSGA-II are given.

5.1. Multi-Objective Optimal Model for instance-based ontology alignment

In this section, the Multi-Objective Optimization Model for the instance-based ontology alignment optimizing problem is presented as follows:

{Max f (X) = \max (R e c a l l (X), P r e c i s i o n (X)) s . t . X = {(x_{1}, x_{2}, \dots, x_{n})}^{T} x_{i} \in [1, | i n s t S e t_{O_{2}} |], i = 1 \dots n

(10)

where $n = | instSe t_{O_{1}} |$ and $| instSe t_{O_{2}} |$ represent the cardinalities of the instance set of $O_{1}$ and $O_{2}$ , respectively. In this model, $x_{i}, i = 1, \dots, n$ , represents the $i$ th pair of the instance mapping, and the objective of this model is to maximize both recall and precision of the alignment. Since the two objectives are contradictory, the problem of optimizing the ontology alignment could be regarded as a multi-objective optimizing problem that could be solved utilizing NSGA-II.

NSGA-II aims to obtain a well-distributed approximation set of points that are close to the Pareto front. Both closeness and diversity are addressed in the selection operator, where the population is sorted using non-domination ranks as the primary sorting criterion, and crowding distances as the secondary sorting criterion. Basically, the NSGA-II is an elitist EA with $μ + γ$ selection. The $μ + γ$ -EA starts by generating the initial population with $μ$ individuals, and then the EA generates a set of $γ$ new solutions through recombination and mutation. The new candidate solutions are evaluated and ranked in terms of their quality. The outline of NSGA-II is presented in Figure 2. In the following, four basic steps of NSGA-II for optimizing the ontology alignment are presented.

Figure 2.

Outline of NSGA-II.

5.2. Chromosome encoding

Let $n_{1}$ be the number of instances in $O_{1}$ , and $n_{2}$ be the number of instances in $O_{2}$ . Each chromosome in the population would be a one-dimensional array with $n_{1}$ +1 integer elements. The first $n_{1}$ elements take values between 1 and $n_{2}$ , denoted as $N_{1} N_{2}, \dots, N_{n_{1}}$ , where $N_{i} = M (i) \in {1, \dots, n_{2}}$ , and this means that the $i$ th instance in $O_{1}$ is mapped to the $N_{i}$ th instance in $O_{2}$ . In addition, the last element in the chromosome, which takes values between 0 and 1, represents the threshold for filtering the mappings in the alignment.

5.3. Fitness function

Fitness functions are objective functions that evaluate the quality of the alignment obtained using the instance similarity measure and similarity propagation algorithm. In our work, there are two fitness functions calculating the recall and precision value of the generated result, respectively.

5.4. Genetic operators

5.4.1. Selection

Like in nature, the most suitable chromosomes must have more opportunities of reproducing themselves. The best chromosomes in a population are the chromosomes that have the best fitness value and the genetic information of these chromosomes can potentially provide the best solutions to the problem. Anyway, reproduction opportunities of the less suitable chromosomes should not be completely removed, because it is important to keep diversity in the population. In this article, in order to ensure the diversity of the population and accelerate the convergence of the algorithm, the selection operator first queues the chromosomes of population in descending order according to their crowding distances, which estimate the density of the solutions. Then we select half of the chromosomes in the front of the population and randomly copy one each time until a new population is formed.

5.4.2. Crossover

The crossover operator takes two chromosomes called parents and generates two children chromosomes, which are obtained by mixing the genes of the parents. Crossover is applied with a certain probability, a parameter of the genetic algorithm. In this work, we use the common one-cut-point method to carry out the crossover operation on the population. First, a cut position in two parents is randomly determined and this position is a cut point that cuts each parent into two parts: the left part and the right part. Then, the right parts of them are switched to form two children.

5.4.3. Mutation

The mutation operator ensures diversity in the population and prevents premature convergence. In our work, for each number in the chromosome, we check if the mutation could be applied according to the mutation probability and, if it is, when the number is not the last one in the chromosome, the value of that number is then modified as a random value in $[1, | instSe t_{O_{2}} |]$ , where $instSe t_{O_{2}}$ represents the cardinality of the instance set of $O_{2}$ . Regarding the last number, which represents the threshold, the modified random value is between 0 and 1.

5.5. Generation of the new population

First, we put the current population and the new population together and remove the redundancy of the chromosomes. Then, the new population is selected by non-dominated sorting and the crowd distance [10].

When the algorithm terminates, we propose a selection strategy to select the representative solutions. Among the solutions with the highest F-measure in the first front, we adopt the max–min approach to obtain a better solution, that is, suppose that solutions $x_{1} x_{2}, \dots, x_{k}$ have the highest F-measure, and their recall and precision values are denoted by $f_{r} (x_{i})$ and $f_{p} (x_{i})$ , respectively, for $i = 1, \dots, k$ . Then we select the solution by the max–min approach as follows: $x_{j} = \arg \max {\min {f_{r} (x_{i}), f_{p} (x_{i})}}$ .

In the following, we take an example to illustrate the procedure of the max–min approach. For instance, there are two solutions with the same F-measure of 0.97 while the recall and the precision of the first solution are 0.95 and 1.0, respectively, and the recall and the precision of the second solution are 0.98 and 0.97 respectively. First, we select the smaller value of recall and precision in the first solution, which is 0.95, and then the smaller one in the second solution, which is 0.97. Since 0.97 is larger than 0.95, the second solution is better than the first one, which means that the solution has less bias to recall and precision than the first one.

6. Experimental results and analysis

In the experiments, the well-known benchmarks provided by the OAEI 2012 [37] were used. In particular, we applied our approach to three datasets: the Bibliographic benchmarks, the Anatomy track and the Library track. In the following, we present the experiment configuration and compare our approach with those of the participants in OAEI 2012. The results of the participants in OAEI 2012 refer to Aguirre et al. [38] and the results obtained by our approach are the averages of 30 independent runs.

6.1. Experiments configuration

The similarity measures used are as follows:

Levenstein distance (syntactic measure);

Jaro distance (syntactic measure);

Q-Gram distance (syntactic measure);

linguistic distance (linguistic measure).

The NSGA-II uses the following parameters:

search space for each parameter is the continuous interval [0,1];

numerical accuracy = 0.01;

the fitnesses are recall and precision;

population size = 20 individuals;

crossover probability = 0.8;

mutation probability = 0.09;

maximum generation = 30 – after 30 independent executions, we noticed that the NSGA-II does not improve the results beyond the thirtieth generation, so we set a limit of 30 generations.

The results of the experiments are given in the next section.

6.2. Results and analysis

The bibliographic benchmark consists of a set of small-scale ontologies that are built around a seed ontology, which contains 33 named classes, 24 object properties, 40 data properties, 56 named individuals and 20 anonymous individuals, and many variations. Variations are artificially generated, and focus on the characterization of the behaviour of the tools rather than having them compete on real-life problems. They are organized into three groups: simple tests (1xx) compare the reference ontology with itself; systematic tests (2xx) are obtained by discarding/modifying features, which include names of entities, comments, the specialization hierarchy, instances, properties and classes, from the reference ontology; and real-life ontologies (3xx) are found on the Web.

The mean values of the results in 1xx, 2xx and 3xx are presented in Table 1, and were obtained by our approach and the participants in OAEI 2012. As can be seen from Table 1, except for MapSSS whose F-measure value is equal to ours, our approach outperformed all of the participants in OAEI 2012 in terms of F-measure, and the precision value of our approach ranks in second place.

Table 1.

Comparison of our approach with the participants in OAEI 2012 on the bibliographic benchmark.

Systems	Recall	Precision	F-Measure
MapSSS	0.77	0.99	0.87
YAM++	0.72	0.98	0.83
AROMA	0.64	0.98	0.77
AUTOMSv2	0.54	0.97	0.69
WeSeE	0.53	0.99	0.69
Hertuda	0.54	0.90	0.68
HotMatch	0.50	0.96	0.66
Optima	0.49	0.89	0.63
WikiMatch	0.54	0.74	0.62
ServOMap	0.43	0.88	0.58
LogMap	0.45	0.73	0.56
MaasMatch	0.57	0.54	0.56
MEDLEY	0.50	0.60	0.54
ServOMapLt	0.20	1.00	0.33
ASE	0.54	0.49	0.51
Our approach	0.86	0.98	0.92

The anatomy real world track is a large ontology matching task that concerns matching the Adult Mouse Anatomy (2744 classes) and part of the NCI Thesaurus (3304 classes) describing the human anatomy. As can be seen from Table 2, our approach’s F-measure value ranks in second place while the precison of our approach outperforms that of all of the others.

Table 2.

Comparison of our approach with that of the participants in OAEI 2012 on Anatomy benchmark.

Systems	Recall	Precision	F-Measure
GOMMA-bk	0.93	0.92	0.92
YAM++	0.85	0.94	0.89
CODI	0.82	0.96	0.89
LogMap	0.84	0.92	0.88
GOMMA	0.79	0.95	0.87
MapSSS	0.74	0.93	0.83
WeSeE	0.76	0.91	0.83
LogMapLt	0.72	0.96	0.82
TOAST	0.75	0.85	0.80
ServOMap	0.63	0.99	0.77
ServOMapLt	0.63	0.99	0.77
HotMatch	0.63	0.97	0.77
AROMA	0.68	0.86	0.76
WikiMatch	0.67	0.86	0.75
Optima	0.58	0.85	0.69
Hertuda	0.67	0.69	0.68
MaasMatch++	0.78	0.43	0.55
Our approach	0.88	0.97	0.92

The library track is also a large ontology matching task that concerns matching two real-world thesauri: STW (economics) and TheSoz (social sciences). Despite being from two different domains, these two thesauri have huge overlapping areas, and moreover, they are roughly the same size, and both were originally developed in German, are multilingual and have English translations. To be specific, the STW Thesaurus for economics provides more than 6000 standardized subject headings and 19,000 additional keywords in both languages, and TheSoz contains overall about 12,000 keywords, of which 8000 are standardized subject headings (in English and German), and 4000 additional keywords. The goal of this track is to find whether the matchers can handle such lightweight ontologies including a huge number of concepts and additional descriptions. As can be seen from Table 3, our approach’s results are much better than those of the participants in OAEI 2012.

Table 3.

Comparison of our approach with that of the participants in OAEI 2012 on the library benchmark.

Systems	Recall	Precision	F-Measure
GOMMA	0.90	0.53	0.67
ServOMapLt	0.68	0.65	0.67
LogMap	0.64	0.68	0.66
ServOMap	0.61	0.71	0.66
YAM++	0.75	0.59	0.66
LogMapLt	0.77	0.57	0.66
Hertuda	0.92	0.46	0.61
WeSeE	0.60	0.61	0.60
HotMatch	0.57	0.64	0.60
CODI	0.48	0.43	0.44
MAPSSS	0.18	0.52	0.27
AROMA	0.65	0.10	0.18
Optima	0.07	0.32	0.11
Our approach	0.95	0.74	0.83

7. Conclusions

In this paper, we propose a novel ontology aligning approach based on instances. We first describe the instance similarity measure and similarity propagation algorithm. Then we present the Multi-Objective Optimal Model for the ontology alignment and give the details of a problem-specific NSGA-II. Finally, the experiment of comparing our approach with the participants of OAEI 2012 has demonstrated that our method is an effective approach and is able to determine the alignment with high precision value.

Future work on this topic will include the extension of the similarity propagation algorithm to handle the situation where ontologies have few instances and a poor concept hierarchy structure in order to improve the recall values. Moreover, we are also interested in improving our approach to deal with the large-scale aligning problem, which is another challenging problem in ontology matching domain.

Footnotes

Funding

This work is supported by the National Natural Science Foundation of China (No. 61272119 and No. 61472297).

References

Euzenat

Valtchev

. Similarity-based ontology alignment in OWL-Lite. In: Proceedings of the 16th European conference on artificial intelligence, 2004, p. 333.

Castano

Ferrara

Montanelli

Lorusso

. Instance matching for ontology population. In: SEBD2008, pp. 121–132.

Stumme

Madche

. FCA-Merge: Bottom-up merging of ontologies. In: The 7th international conference on artificial intelligence (IJCAI), 2001, pp. 225–230.

Euzenat

. Brief overview of T-tree: The TROPES taxonomy building tool. In: The 4th ASIS SIG/CR workshop on classification research, 1994, pp. 69–87.

Doan

A H

Madhavan

Dhamankar

. Learning to match ontologies on the semantic web. The International Journal on Very Large Data Bases2003; 12(4): 303–319.

Kalfoglou

Schorlemmer

. IF-Map: An ontology mapping method based on information flow theory. Journal of Data Semantics2003; 98–127.

Martinez-Gil

Alba

Aldana-Montes

. Optimizing ontology alignments by using genetic algorithms. In: Nature-inspired reasoning for the Semantic Web (NatuReS2008), 2008, pp. 31–45.

Naya

JMV

Romero

Loureiro

. Improving ontology alignment through genetic algorithms. Soft computing methods for practical environment solutions: Techniques and studies. Hershey, PA: ISI Global, 2010, pp. 240–259.

Ginsca

A-L

Iftene

. Using a genetic algorithm for optimizing the similarity aggregation step in the process of ontology alignment. In: The 9th Roedunet international conference (RoEduNet), 2010, pp. 118–122.

10.

Deb

Agrawal

Pratap

. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In: Proceedings of the parallel problem solving from nature VI conference, 2000; Vol. 1917, pp. 849–858.

11.

Srinivas

Deb

. Multiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation1994; 2: 221–248.

12.

Zitzler

Thiele

. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation1999; 3: 257–271.

13.

Zitzler

Laumanns

Thiele

. SPEA2: Improving the strength Pareto evolutionary algorithm. In: Evolutionary methods for design, optimization and control with applications to industrial problems: Proceedings of the EUROGEN2001 conference, Athens, 2001.

14.

Knowles

Corne

. M-PAES: A memetic algorithm for multiobjective optimization. In: Proceedings of 2000 congress on evolutionary computation, 2000, Vol. 1, pp. 325–332.

15.

Abbass

Sarker

Newton

. PDE: A Pareto-frontier differential evolution approach for multi-objective optimization problems. In: Proceedings of the congress on evolutionary computation, 2001, Vol. 2, pp. 971–978.

16.

. A non-dominated sorting particle swarm optimizer for multiobjective optimization. Lecture Notes in Computer Science, Vol. 2723. Berlin: Springer, 2003, pp. 37–48.

17.

Zhang

. Immune optimization algorithm for constrained nonlinear multiobjective optimization problems. Applied Soft Computing2007; 7: 840–857.

18.

Goh

Tan

Liu

Chiam

. A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design. European Journal of Operational Research2010; 202: 42–54.

19.

Shi

Yan

Shi

Zhang

. A fast multi-objective evolutionary algorithm based on a tree structure. Applied Soft Computing2010; 10: 468–480.

20.

Cooren

Clerc

Siarry

. MO-TRIBES: An adaptive multiobjective particle swarm optimization algorithm. Computational Optimization and Applications2011; 49: 379–400.

21.

Mashwani

Salhi

. A decomposition-based hybrid multiobjective evolutionary algorithm with dynamic resource allocation. Computational Optimization and Applications2012; 12: 2765–2780.

22.

Chen

Zou

Wang

. A multi-objective endocrine PSO algorithm and application. Computational Optimization and Applications2012; 12: 4508–4520.

23.

Liu

Wang

Cheung

. A multiobjective evolutionary algorithm using min–max strategy and sphere coordinate transformation. Intelligent Automation and Soft Computing2009; 15(3): 361–384.

24.

Niknam

Zare

Aghaei

. Scenario-based multiobjective volt/var control in distribution networks including renewable energy sources. IEEE Transactions on Power Delivery2012; 27: 2004–2019.

25.

Ahmadi

Rosen

Dincer

. Multi-objective exergy-based optimization of a polygeneration energy system using an evolutionary algorithm. Energy2012; 46: 21–31.

26.

Niknam

Meymand

Mojarrad

. An efficient algorithm for multi-objective optimal operation management of distribution network considering fuel cell power plants. Energy2011; 36: 119–132.

27.

Niknam

Kavousifard

Tabatabaei

Aghaei

. Optimal operation management of fuel cell/wind/photovoltaic power sources connected to distribution networks. Journal of Power Sources2011; 196: 8881–8896.

28.

Ahmadi

Dincer

. Thermodynamic and exergoenvironmental analyses, and multi-objective optimization of a gas turbine power plant. Applied Thermal Engineering2011; 31: 2529–2540.

29.

Liu

Cheung

Xie

Zhang

. On solving WCDMA network planning using iterative power control scheme and evolutionary multiobjective algorithm. IEEE Computational Intelligence Magazine2014; 44–52.

30.

Bock

Hettenhausen

. Discrete particle swarm optimisation for ontology alignment. Information Sciences2012; 192: 152–173.

31.

Acampora

Loia

Salerno

. A hybrid evolutionary approach for solving the ontology alignment problem. International Journal of Intelligent Systems2012; 27(3): 189–216.

32.

Maedche

Staab

. Measuring Similarity between Ontologies. In: Proceedings of the international conference on knowledge engineering and knowledge management (EKAW), 2002, pp. 251–263.

33.

Van Rijsbergen

. Information retrieval. London: Butterworth, 1975.

34.

Jia

Cheung

Liu

. Cooperative and penalized competitive learning with application to kernel-based clustering. Pattern Recognition2014; 47: 3060–3069.

35.

Miller

. WordNet: A lexical database for English. Communications of the ACM1995; 38(11): 39–41.

36.

Aumueller

Massmann

. Schema and ontology matching with COMA++. In: Proceedings of the 2005 ACM SIGMOD international conference on management of data, 2005, pp. 906–908.

37.

Ontology Alignment Evaluation Initiative (OAEI), http://oaei.ontologymatching.org/2012 (accessed March 2014).

38.

Aguirre

Eckert

Euzenat

. Results of ontology alignment evaluation initiative 2012. In: Proceedings of 7th ISWC workshop on ontology matching, 2012, pp. 73–115.

39.

Jaro

. Probabilistic linkage of large public health data files. Statistics in Medicine 1995, 14: 491–498.