# Optimizing Ontology Alignment through Linkage Learning on Entity Correspondences

Authors: Xingsi Xue; Chaofan Yang; Chao Jiang; Pei-Wei Tsai; Guojun Mao; Hai Zhu
Journal: Complexity
 (2021)

---

## Abstract

Data heterogeneity is the obstacle for the resource sharing on Semantic Web (SW), and ontology is regarded as a solution to this problem. However, since different ontologies are constructed and maintained independently, there also exists the heterogeneity problem between ontologies. Ontology matching is able to identify the semantic correspondences of entities in different ontologies, which is an effective method to address the ontology heterogeneity problem. Due to huge memory consumption and long runtime, the performance of the existing ontology matching techniques requires further improvement. In this work, an extended compact genetic algorithm-based ontology entity matching technique (ECGA-OEM) is proposed, which uses both the compact encoding mechanism and linkage learning approach to match the ontologies efficiently. Compact encoding mechanism does not need to store and maintain the whole population in the memory during the evolving process, and the utilization of linkage learning protects the chromosome’s building blocks, which is able to reduce the algorithm’s running time and ensure the alignment’s quality. In the experiment, ECGA-OEM is compared with the participants of ontology alignment evaluation initiative (OAEI) and the state-of-the-art ontology matching techniques, and the experimental results show that ECGA-OEM is both effective and efficient.


---

## Body

## 1. Introduction

Semantic Web (SW) is proposed by Tims Berners-Lee in 1998, which makes the intelligent applications be able to understand a word’s meaning in semantic level. Ontologies are the solution to the issue of data heterogeneity on SW since it is able to make consensus of a certain conception meaning of a field and provide abundant domain knowledge and semantic vocabulary for the interaction between application systems. However, due to SW’s scattering essence, there might be different definitions on a concept in separate ontologies, which leads to the issue of ontology heterogeneity [1]. Ontology matching is regarded as an effective method to address it, and swarm intelligent algorithm- (SIA-) based ontology matching techniques have achieved good performance in past studies [2], such as genetic algorithm (GA) [3], particle swarm optimization algorithm (PSO) [4], firefly algorithm (FA) [2], and artificial bee colony algorithm (ABC) [5]. However, there are two drawbacks in the existing SIA-based approaches: (1) massive time and memory consumption is required, which heavily blocks the efficiency of the ontology matching process; (2) an expert of related field or a reference alignment is required in the process of ontology matching which is usually not available in real application conditions. To overcome these drawbacks, an extended compact genetic algorithm-based ontology entity matching technique (ECGA-OEM) is proposed in this work, which uses both compact encoding mechanism [6, 7] and linkage learning approach to efficiently match the ontologies. In particular, our contributions are as follows:(i)
A new evaluating metrics on the ontology alignment is proposed, which is able to work without the reference alignment and the domain experts.(ii)
An optimal model on ontology entity matching problem is constructed.(iii)
An ECGA-OEM is proposed, which uses the linkage learning and compact encoding mechanism to efficiently address the ontology entity matching problem.The rest of this paper is organized as follows: the related works are narrated in Section2; the statement of ontology, ontology matching, and similarity measures are presented in Section 3; the ontology entity matching through ECGA proposed by this paper is revealed in Section 4; Section 5 presents the experiment results; and finally, Section 6 draws the conclusion and presents the future work.


## 2. Related Works

Ontology matching is a complex, time-consuming, and error-prone work, especially when the scale of ontologies is large. Recently, a number of the machine learning (ML) techniques [8–14] have been proposed to automatically determine the ontology alignment. To improve the matching efficiency, Araújo et al. [15] presented the matching system through parallel computing (PC) technique and Amin et al. [16] matching ontology based on cloud computing (CC). At the same time, SIA-based technique has achieved great performance in the ontology matching [1, 2, 17–20] domain [21–26].Generally, ontology matching techniques are classified into two categories: ontology metamatching techniques and ontology entity matching techniques [27]. The former dedicates to address the problem that how to aggregate different similarity measures with appropriate weights, and the latter tries to directly determine the entity correspondence set between two ontologies. The first SIA-based ontology metamatching system is genetics for ontology alignment (GOAL), which aims at optimizing the aggregating weight set for different matchers [3, 28–30]. Memetic algorithms (MAs), which introduce local search (LS) strategy into evolutionary algorithms (EAs) to improve its local optimization capability, are proposed to solve ontology metamatching problem [31]. To overcome the drawback of overreliance reference alignment, Xue et al. presented a partial reference alignment (PRA), in which only a part of standard reference is used to assess the quality of alignment [32]. Furthermore, Xue and Wang proposed an innovative metric named unanimous improvement ratio (UIR) to assess the alignment’s quality, in which the reference alignment is not required [33]. Besides, artificial bee colony (ABC) algorithm is also adopted to address ontology metamatching problem, which further improves the solution’s quality [5].During the matching process, ontology metamatching techniques need to maintain several similarity matrices, which leads to huge memory consumption. For this reason, ontology entity matching techniques, which aims at directly determining the optimal pair set, attracts the expert’s interests. Genetic algorithm-based ontology matching (GAOM) firstly regards certain matching pairs set as the optimizing objective [34]. MA is also utilized to solve the ontology entity matching problem, whose performance outperforms GA [35]. Bock et al. [4] use PSO to solve the ontology entity matching. In detail, it evaluates the fitness of chromosomes through a certain aggregation strategy for multiple objective functions. Alves et al. [36] argue that instances consisting in the ontology can be used to improve alignment in the condition that knowledge is embedded in them. For this reason, Xue et al. [37] take also instance-level matching into consideration to further improve the quality of alignment.


## 3. Preliminaries

### 3.1. Ontology and Ontology Matching

Definition 1.
(ontology). An ontologyO is a 5-tuple [33]. O=C,P,I,Λ,Γ where C is a set of classes that cannot be empty, P is a set of properties that cannot be empty, I is a set (it could be empty) of individuals that represent the instances of classes in the real world, Λ is a nonempty set of axioms that are used to check the consistency of ontologies or deduce new information, and Γ is a set of annotations that provide information metadata so that the researcher can understand. Particularly, C, P, and I make up the entities in ontologies.Definition 2.
(ontology matching). The ontology matching can be considered as a functionfO1,O2,A′,p,r, where O1 and O2 are two ontologies to be matched; A′ is an existing initial alignment of O1 and O2; p is a set of parameters, e.g., threshold, in the process of ontology matching; and r is a set of external resources, e.g., background knowledge based and dictionaries, which assisted in ontology matching. The process of ontology matching is depicted in Figure 1, where A is the obtained ontology alignment.
An example of matching two ontologies is presented in Figure2, where O1 and O2 are two ontologies to be matched in this figure. The strings in the rounded rectangle are the classes, e.g., “Reference,” “Entry,” and “Book.” The black lines between two classes of the same ontology represent their relation “has a” or “is a” in turn; e.g., “Reference” has a “Book” and “Book” is a “Reference,” which means “Reference” is the supclass of “Book,” and “Book” is the subclass of “Reference.” There are datatype properties that describe the features of a class; e.g., “Data,” “Title,” and “Human Creator” are the properties of “Reference.” The instances of a class are in a rectangle; e.g., “Of Natures Obvious Laws & Processes in Vegetation” is an instance of “Article.” The relation of the entities between the two ontologies are linked by the lines with double arrowhead, and there are symbols: “≡,” “⊆” (or “⊇”), and “⊥,” which, respectively, means equivalence, more specific (or less specific), and disjointness relation; e.g., classes “Entry” and “Book” of O2 are the equivalent and hyponym of class “Reference” of O1, property “Event” of O1, and property “Year” of O2 are irrelevant.Figure 1
The process of ontology matching.Figure 2
An example of matching two ontologies.


### 3.2. Similarity Measures

It is necessary to measure to what extend two ontology entities are similar before finding the reliable entity correspondences. In the ontology domain, we usually use the similarity measure to calculate two entities’ similarity values. Generally, there are three categories of similarity measures, i.e., syntactic, linguistic, and taxonomy-based measures [33].


#### 3.2.1. Syntactic Measures

Two syntactic measures, i.e., SMOA (string metric for ontology alignment) [37] and Levenshtein [38], are employed in this paper. Given two strings s1 and s2, the SMOA and Levenshtein similarity are, respectively, defined as follows:(1)SMOAs1,s2=Comms1,s2−Diffs1,s2+WinklerImprs1,s2,where Comms1,s2 stands for the common length of s1 and s2 while Diffs1,s2 for the different lengths and WinklerImprS1,S2 is the improvement to results yielded by the method that proposed by Winkler [39].(2)Levenshteins1,s2=max0,mins1,s2−ds1,s2mins1,s2,where s1 and s2 are the cardinality of the letters contained in s1 and s2, respectively, and ds1,s2 is the number of letters that need to be modified from s1 to s2. The final syntactic similarity is equal to the average of SMOA and Levenshtein.


#### 3.2.2. Linguistic Measures

The linguistic similarity between two strings is worked out by considering the semantic relations (such as synonyms and hypernym) which usually requires using the thesaurus and dictionaries. In this work, WordNet [23, 40], an electronic vocabulary database that has collected every meaning of various words, is used. Given two words w1 and w2, Linguisitc Similarityw1,w2 equals:(i)
1, if wordsw1 and w2 are synonyms in Wordnet.(ii)
0.5, if wordw1 is the hypernym of word w2 or vice versa in Wordnet.(iii)
0, otherwise.


#### 3.2.3. Taxonomy-Based Measures

The core ideal of taxonomy-based measures is to make full use of the hierarchy relationship of ontology to determine two entities’ similarity by considering their neighbor’s similarity. In this work, a mutual reasoning between class and property (MRCP) is proposed as the taxonomy-based measure, which is shown in Figure3.Figure 3
MRCP taxonomy-based measure.
(a)(b)(c)(d)In Figure3, the circle is the class of the ontology, the triangle is the properties of the ontology, and the one-way arrow represents the hierarchical relationship; i.e., class ca1 is the supclass of class ca3, the dividing line arrow between the class and the property indicates that the property belongs to this class, the bidirectional arrow indicates that there is a high similarity between the two entities, and the dashed two-way arrow indicates that the similarity between them is improved after the operation. Subgraph (a) depicts the classes’ similarity gained from their neighbor, i.e., supclass and subclass. There is high similarity between classes ca1 and cb1, so the similarity between their subclasses ca3 and cb2 is supposed to increase. Likewise, similarity of classes ca3 and cb2 would be increased because their subclasses ca6 and cb4 are highly similar. Subgraph (b) is the properties’ similarity gained from their supproperty and subproperty. The similarity of properties pa3 and pb2 will be improved since their supproperties pa1 and pb1 and subproperties pa6 and pb4 are highly similar, respectively. Subgraph (c) is the properties’ similarity gained from the classes which they belong to. ca1 and cb1 are the classes of two ontologies and pa1, pa2, pa3, pb1, pb2, and pb3 are their properties, respectively. The similarities between properties of class ca1 and properties of class cb1 would be improved because of the high similarity of ca1 and cb1; i.e., the similarity of pa3 and pb1 would be promoted and so are the remaining eight combinations. On the contrary, classes’ similarity will be increased due to the same or highly similar properties they shared, as is depicted in subgraph (d). Since pairs pa1 and pb3, pa2 and pb2, and pa3 and pb1, the similarity of ca1 and cb1 is increased too.


#### 3.2.4. Aggregation Strategy

Three similarity matrixes are generated when the three measures have been applied. In this work, three matrices need to be aggregated into one matrix. The final similarity valueSas1,s2 between two entities s1 and s2 is defined as follows:(3)Sas1,s2=1,Ss=1orSl=1,0.8∗Ssl+0.2∗St,Ssl>Threshold,0.2∗Ssl+0.8∗St,Ssl<=Threshold.where Ss, Sl, and St is, respectively, the syntactic, linguistic, and taxonomy-based similarity of s1 and s2; Ssl is the average of Ss and Sl; and Threshold is a given parameter to filter the matching pairs with low similarity.


## 3.1. Ontology and Ontology Matching

Definition 1.
(ontology). An ontologyO is a 5-tuple [33]. O=C,P,I,Λ,Γ where C is a set of classes that cannot be empty, P is a set of properties that cannot be empty, I is a set (it could be empty) of individuals that represent the instances of classes in the real world, Λ is a nonempty set of axioms that are used to check the consistency of ontologies or deduce new information, and Γ is a set of annotations that provide information metadata so that the researcher can understand. Particularly, C, P, and I make up the entities in ontologies.Definition 2.
(ontology matching). The ontology matching can be considered as a functionfO1,O2,A′,p,r, where O1 and O2 are two ontologies to be matched; A′ is an existing initial alignment of O1 and O2; p is a set of parameters, e.g., threshold, in the process of ontology matching; and r is a set of external resources, e.g., background knowledge based and dictionaries, which assisted in ontology matching. The process of ontology matching is depicted in Figure 1, where A is the obtained ontology alignment.
An example of matching two ontologies is presented in Figure2, where O1 and O2 are two ontologies to be matched in this figure. The strings in the rounded rectangle are the classes, e.g., “Reference,” “Entry,” and “Book.” The black lines between two classes of the same ontology represent their relation “has a” or “is a” in turn; e.g., “Reference” has a “Book” and “Book” is a “Reference,” which means “Reference” is the supclass of “Book,” and “Book” is the subclass of “Reference.” There are datatype properties that describe the features of a class; e.g., “Data,” “Title,” and “Human Creator” are the properties of “Reference.” The instances of a class are in a rectangle; e.g., “Of Natures Obvious Laws & Processes in Vegetation” is an instance of “Article.” The relation of the entities between the two ontologies are linked by the lines with double arrowhead, and there are symbols: “≡,” “⊆” (or “⊇”), and “⊥,” which, respectively, means equivalence, more specific (or less specific), and disjointness relation; e.g., classes “Entry” and “Book” of O2 are the equivalent and hyponym of class “Reference” of O1, property “Event” of O1, and property “Year” of O2 are irrelevant.Figure 1
The process of ontology matching.Figure 2
An example of matching two ontologies.


## 3.2. Similarity Measures

It is necessary to measure to what extend two ontology entities are similar before finding the reliable entity correspondences. In the ontology domain, we usually use the similarity measure to calculate two entities’ similarity values. Generally, there are three categories of similarity measures, i.e., syntactic, linguistic, and taxonomy-based measures [33].


### 3.2.1. Syntactic Measures

Two syntactic measures, i.e., SMOA (string metric for ontology alignment) [37] and Levenshtein [38], are employed in this paper. Given two strings s1 and s2, the SMOA and Levenshtein similarity are, respectively, defined as follows:(1)SMOAs1,s2=Comms1,s2−Diffs1,s2+WinklerImprs1,s2,where Comms1,s2 stands for the common length of s1 and s2 while Diffs1,s2 for the different lengths and WinklerImprS1,S2 is the improvement to results yielded by the method that proposed by Winkler [39].(2)Levenshteins1,s2=max0,mins1,s2−ds1,s2mins1,s2,where s1 and s2 are the cardinality of the letters contained in s1 and s2, respectively, and ds1,s2 is the number of letters that need to be modified from s1 to s2. The final syntactic similarity is equal to the average of SMOA and Levenshtein.


### 3.2.2. Linguistic Measures

The linguistic similarity between two strings is worked out by considering the semantic relations (such as synonyms and hypernym) which usually requires using the thesaurus and dictionaries. In this work, WordNet [23, 40], an electronic vocabulary database that has collected every meaning of various words, is used. Given two words w1 and w2, Linguisitc Similarityw1,w2 equals:(i)
1, if wordsw1 and w2 are synonyms in Wordnet.(ii)
0.5, if wordw1 is the hypernym of word w2 or vice versa in Wordnet.(iii)
0, otherwise.


### 3.2.3. Taxonomy-Based Measures

The core ideal of taxonomy-based measures is to make full use of the hierarchy relationship of ontology to determine two entities’ similarity by considering their neighbor’s similarity. In this work, a mutual reasoning between class and property (MRCP) is proposed as the taxonomy-based measure, which is shown in Figure3.Figure 3
MRCP taxonomy-based measure.
(a)(b)(c)(d)In Figure3, the circle is the class of the ontology, the triangle is the properties of the ontology, and the one-way arrow represents the hierarchical relationship; i.e., class ca1 is the supclass of class ca3, the dividing line arrow between the class and the property indicates that the property belongs to this class, the bidirectional arrow indicates that there is a high similarity between the two entities, and the dashed two-way arrow indicates that the similarity between them is improved after the operation. Subgraph (a) depicts the classes’ similarity gained from their neighbor, i.e., supclass and subclass. There is high similarity between classes ca1 and cb1, so the similarity between their subclasses ca3 and cb2 is supposed to increase. Likewise, similarity of classes ca3 and cb2 would be increased because their subclasses ca6 and cb4 are highly similar. Subgraph (b) is the properties’ similarity gained from their supproperty and subproperty. The similarity of properties pa3 and pb2 will be improved since their supproperties pa1 and pb1 and subproperties pa6 and pb4 are highly similar, respectively. Subgraph (c) is the properties’ similarity gained from the classes which they belong to. ca1 and cb1 are the classes of two ontologies and pa1, pa2, pa3, pb1, pb2, and pb3 are their properties, respectively. The similarities between properties of class ca1 and properties of class cb1 would be improved because of the high similarity of ca1 and cb1; i.e., the similarity of pa3 and pb1 would be promoted and so are the remaining eight combinations. On the contrary, classes’ similarity will be increased due to the same or highly similar properties they shared, as is depicted in subgraph (d). Since pairs pa1 and pb3, pa2 and pb2, and pa3 and pb1, the similarity of ca1 and cb1 is increased too.


### 3.2.4. Aggregation Strategy

Three similarity matrixes are generated when the three measures have been applied. In this work, three matrices need to be aggregated into one matrix. The final similarity valueSas1,s2 between two entities s1 and s2 is defined as follows:(3)Sas1,s2=1,Ss=1orSl=1,0.8∗Ssl+0.2∗St,Ssl>Threshold,0.2∗Ssl+0.8∗St,Ssl<=Threshold.where Ss, Sl, and St is, respectively, the syntactic, linguistic, and taxonomy-based similarity of s1 and s2; Ssl is the average of Ss and Sl; and Threshold is a given parameter to filter the matching pairs with low similarity.


## 3.2.1. Syntactic Measures

Two syntactic measures, i.e., SMOA (string metric for ontology alignment) [37] and Levenshtein [38], are employed in this paper. Given two strings s1 and s2, the SMOA and Levenshtein similarity are, respectively, defined as follows:(1)SMOAs1,s2=Comms1,s2−Diffs1,s2+WinklerImprs1,s2,where Comms1,s2 stands for the common length of s1 and s2 while Diffs1,s2 for the different lengths and WinklerImprS1,S2 is the improvement to results yielded by the method that proposed by Winkler [39].(2)Levenshteins1,s2=max0,mins1,s2−ds1,s2mins1,s2,where s1 and s2 are the cardinality of the letters contained in s1 and s2, respectively, and ds1,s2 is the number of letters that need to be modified from s1 to s2. The final syntactic similarity is equal to the average of SMOA and Levenshtein.


## 3.2.2. Linguistic Measures

The linguistic similarity between two strings is worked out by considering the semantic relations (such as synonyms and hypernym) which usually requires using the thesaurus and dictionaries. In this work, WordNet [23, 40], an electronic vocabulary database that has collected every meaning of various words, is used. Given two words w1 and w2, Linguisitc Similarityw1,w2 equals:(i)
1, if wordsw1 and w2 are synonyms in Wordnet.(ii)
0.5, if wordw1 is the hypernym of word w2 or vice versa in Wordnet.(iii)
0, otherwise.


## 3.2.3. Taxonomy-Based Measures

The core ideal of taxonomy-based measures is to make full use of the hierarchy relationship of ontology to determine two entities’ similarity by considering their neighbor’s similarity. In this work, a mutual reasoning between class and property (MRCP) is proposed as the taxonomy-based measure, which is shown in Figure3.Figure 3
MRCP taxonomy-based measure.
(a)(b)(c)(d)In Figure3, the circle is the class of the ontology, the triangle is the properties of the ontology, and the one-way arrow represents the hierarchical relationship; i.e., class ca1 is the supclass of class ca3, the dividing line arrow between the class and the property indicates that the property belongs to this class, the bidirectional arrow indicates that there is a high similarity between the two entities, and the dashed two-way arrow indicates that the similarity between them is improved after the operation. Subgraph (a) depicts the classes’ similarity gained from their neighbor, i.e., supclass and subclass. There is high similarity between classes ca1 and cb1, so the similarity between their subclasses ca3 and cb2 is supposed to increase. Likewise, similarity of classes ca3 and cb2 would be increased because their subclasses ca6 and cb4 are highly similar. Subgraph (b) is the properties’ similarity gained from their supproperty and subproperty. The similarity of properties pa3 and pb2 will be improved since their supproperties pa1 and pb1 and subproperties pa6 and pb4 are highly similar, respectively. Subgraph (c) is the properties’ similarity gained from the classes which they belong to. ca1 and cb1 are the classes of two ontologies and pa1, pa2, pa3, pb1, pb2, and pb3 are their properties, respectively. The similarities between properties of class ca1 and properties of class cb1 would be improved because of the high similarity of ca1 and cb1; i.e., the similarity of pa3 and pb1 would be promoted and so are the remaining eight combinations. On the contrary, classes’ similarity will be increased due to the same or highly similar properties they shared, as is depicted in subgraph (d). Since pairs pa1 and pb3, pa2 and pb2, and pa3 and pb1, the similarity of ca1 and cb1 is increased too.


## 3.2.4. Aggregation Strategy

Three similarity matrixes are generated when the three measures have been applied. In this work, three matrices need to be aggregated into one matrix. The final similarity valueSas1,s2 between two entities s1 and s2 is defined as follows:(3)Sas1,s2=1,Ss=1orSl=1,0.8∗Ssl+0.2∗St,Ssl>Threshold,0.2∗Ssl+0.8∗St,Ssl<=Threshold.where Ss, Sl, and St is, respectively, the syntactic, linguistic, and taxonomy-based similarity of s1 and s2; Ssl is the average of Ss and Sl; and Threshold is a given parameter to filter the matching pairs with low similarity.


## 4. Extended Compact Genetic Algorithm-Based Ontology Entity Matching

GA is an excellent methodology to solve the ontology matching problem due to its potential parallel search characteristic and good searchability. In our work, an ECGA to efficiently address the ontology entity matching problem is proposed.


### 4.1. Optimal Model

The optimal model of ontology entity matching problem is given as follows:(4)maxξσ,s.t.σ=x1,x2,…,xO1T,xi∈1,2,…,O2,−1,i=1,2,…,O1,where O1 and O2, respectively, are the cardinalities of two ontologies O1 and O2; xi,i=1,2,…,O1 is the ith matching pairs. Particularly, it means there is no matching of ith entity in O1 when xi=−1. The objective of this work is to maximize ξσ, and for the details of it, refer to Section 4.3.3.


### 4.2. The Framework of ECGA-OEM

Two ontologies are to be matched as input and a reference alignment as output, and the framework of ECGA-OEM is shown in Figure4, whose critical components are narrated in the rest of this section.Two ontologies, generally in XML or RDF format, are extracted into two hierarchy schema in the preprocessing model. The operation of the ECGA optimization model relies on the similarity matrix obtained in the similarity measure model, which has been stated in detail in Section 3.2. Finally, the alignment is generated by the solution generation model. In detail, the ECGA optimization model is described in Section 4.3.Figure 4
The framework of ECGA-OEM.


### 4.3. ECGA Optimization Model

Given the virtual population’s maximum generation,MaxGeneration = 2000 (normally, the number of iterations in the convergence of ECGA is much less than MaxGeneration), Threshold = 0.7, and the hierarchy schema of ontology1 and ontology2 as input and final alignment as output. The pseudocode of ECGA is proposed in Algorithm 1, where PV and BB are probability vector (see also Section 4.3.1) and building blocks (refer to also Section 4.3.7), respectively.Algorithm 1:ECGA optimization model.
Input: the hierarchy schemas of O1 and O2; the aggregated similarity matrix, Mas;Output: the best chromosome, Bestchromosome;(1)
PV=initializationlenofO1,lenofO2(2)
WhileCurrentGeneration<MaxGenerationdo(3)
chromosomes=generationPV,BB;(4)
Elite=competeElite,chromosomes;(5)
Betters=selectElite,chromosomes;(6)
PV=updatePV,Betters;(7)
BB=LinkageLearningBB,PV;(8)
end while


#### 4.3.1. Probability Vector Initialization

Different from binary coding, the probability vector (PV) in this work is two-dimensional. The initialized PV and convergent PV are shown in Tables1 and 2, respectively. The value in the ith row and jth column represents the possibility of matching between the ith entity in O1 and the jth entity in O2; i.e., it means the probability of 0th entity of O1 (reference) and 0th entity of O2 (entry) is 1/1+1+1+1+1, which is shown in Table 1 (peculiarly, the header “−1 (null)” denotes the probability of no matching). The convergence condition is that the probability of taking a unique number on each locus in the PV is 1; i.e., in Table 2, the probability of the 0th entity of O1 (reference) and the 0th entity of O2 (entry) is 23.72/0+23.72+0+0+0 and so do the rest.Table 1
An example of initialized PV.
PV0 (Entry)1 (Book)2 (Proceedings)3 (Article)−1 (Null)0 (Reference)111111 (Book)111112 (Proceedings)111113 (Part)111114 (Article)11111Table 2
An example of convergent PV.
PV0 (Entry)1 (Book)2 (Proceedings)3 (Article)−1 (Null)0 (Reference)23.7200001 (Book)025.330002 (Proceedings)0026.01003 (Part)000022.464 (Article)00024.110


#### 4.3.2. Chromosomes Generation

Certain size chromosomes are produced in each generation through PV. An example of chromosome is given in Figure5. In particular, subgraph (a) shows the locus of the chromosome and corresponding code, and subgraph (b) illustrates decoding chromosome in subgraph (b); i.e., it denotes that the fourth entity of O1 “Article” correspondent to the third entity of O2 “Article” as the code of the fourth locus is “3” (“−1 (Null)” indicates no matching).Figure 5
An example of chromosome.
(a)(b)


#### 4.3.3. Fitness Function

The fitness function is used to determine which chromosomes in the population can better adapt the environment. In the context of ontology matching, the objective of fitness function is to find the best chromosome, whose corresponding alignment’s quality is the highest, with algorithm convergence. The objective function of the optimal model is used as the fitness function of this work, and given a chromosomeσ, its fitness function is defined as follows:(5)ξσ=2⋅β⋅ϕA+1−β⋅fA,where ξσ is the fitness function that is used in this paper; A is the alignment determined by σ; A is the cardinality of A; β, a fraction in the range [0, 1], is the relative weight of ϕA and fA, which is set to 0.25 in this paper; ϕ is a normalization function; and f is a function that calculates the mean of the matched entity pairs’ similarity values in A. In addition, ϕA and fA are defined as follows:(6)ϕA=AminO1,O2,(7)fA=∑i=1AηiA,where O1 and O2 are, respectively, the cardinality of O1 and O2 and ηi is the similarity of the ith matching pair in alignment A. In particular, ϕA is the ratio of the number of matching pair found to the value of the smaller entity number of the two ontologies and fA is the average similarity of the matching pairs found, which, respectively, approximates the recall value and precision value.


#### 4.3.4. Selection Operator

The selection operator selects the best chromosomes in the current population to participate in the next step [41] and updates the PV. Firstly, the chromosomes are sorted in descending order according to their fitness scores. Secondly, the first half of the chromosomes will be retained as a temporary population. Finally, with fitness as the weight through roulette, we can select the chromosome from the temporary population for subsequent operation.


#### 4.3.5. Elite Strategy

The goal of elite strategy is to keep the historical optimal solution and prevent the fitness of the optimal chromosome from “degenerating” in the process of evolution. In this work, the elite strategy has two steps: the historical optimal solutionElite first competes with the current optimal solution Best, and the winner will become the new Elite; the historical optimal solution then participates in the PV update in each generation.


#### 4.3.6. Probability Vector Updating

An example of updating the PV is presented in Figure6, where subgraph (a) is a chromosome generated by the initialized PV. The similarity is derived from the similarity matrix according to the chromosome’s code. It should be noted that the code of the third locus is “0,” which means that the entity “Part” with sequence number “3” in O1 does not match any entity in O2, so its similarity is equal to 1 minus the value of the highest similarity between “Part” and all entities in O2, i.e., 1−0.38=0.62. PV will be updated by the normalized similarity of each locus, which is shown in subgraph (b). The probability of being updated in the PV is bold; i.e., the probability of matching pair “Reference” and “Entry” changed from “1” to “1.2” since the normalized similarity of the corresponding locus of chromosome is “0.20.”Figure 6
An example of update PV.
(a)(b)


#### 4.3.7. Linkage Learning

Building blocks will be saved through linkage learning, thus to improve the efficiency of algorithm and quality of solution [42]. In simple GA, linkage learning is to identify great locus and protect them so that they will not be destroyed in the subsequent crossover and mutation operations; in ECGA, linkage learning keeps good probability distribution so that they are not disturbed in the subsequent update process. A linkage learning approach is proposed in this work, and its detail is shown in Figure 7.Figure 7
An example of linkage learning.For clarity, only column 1 of the original probability vector is selected for narration. In each generation, a low probability clearing operation is performed. The value of each column is divided by the maximum value of the row, and the value of the column will be cleared if the decimal is less than a specific value (0.2 in this work); i.e., 0, 2, 3, and −1 bits in PV are cleared and marked. The row of PV is a “good” probability distribution when all but one bit of this row are zero. Link learning generates building blocks based on the “good” probability distribution, i.e., a building block, the pair of index “0,” and code “0,” which was included in the rounded rectangle produced by linkage learning. After that, all the building blocks are directly put into each chromosome (the bold numbers), which reduces the consumption of runtime and memory consumption.


## 4.1. Optimal Model

The optimal model of ontology entity matching problem is given as follows:(4)maxξσ,s.t.σ=x1,x2,…,xO1T,xi∈1,2,…,O2,−1,i=1,2,…,O1,where O1 and O2, respectively, are the cardinalities of two ontologies O1 and O2; xi,i=1,2,…,O1 is the ith matching pairs. Particularly, it means there is no matching of ith entity in O1 when xi=−1. The objective of this work is to maximize ξσ, and for the details of it, refer to Section 4.3.3.


## 4.2. The Framework of ECGA-OEM

Two ontologies are to be matched as input and a reference alignment as output, and the framework of ECGA-OEM is shown in Figure4, whose critical components are narrated in the rest of this section.Two ontologies, generally in XML or RDF format, are extracted into two hierarchy schema in the preprocessing model. The operation of the ECGA optimization model relies on the similarity matrix obtained in the similarity measure model, which has been stated in detail in Section 3.2. Finally, the alignment is generated by the solution generation model. In detail, the ECGA optimization model is described in Section 4.3.Figure 4
The framework of ECGA-OEM.


## 4.3. ECGA Optimization Model

Given the virtual population’s maximum generation,MaxGeneration = 2000 (normally, the number of iterations in the convergence of ECGA is much less than MaxGeneration), Threshold = 0.7, and the hierarchy schema of ontology1 and ontology2 as input and final alignment as output. The pseudocode of ECGA is proposed in Algorithm 1, where PV and BB are probability vector (see also Section 4.3.1) and building blocks (refer to also Section 4.3.7), respectively.Algorithm 1:ECGA optimization model.
Input: the hierarchy schemas of O1 and O2; the aggregated similarity matrix, Mas;Output: the best chromosome, Bestchromosome;(1)
PV=initializationlenofO1,lenofO2(2)
WhileCurrentGeneration<MaxGenerationdo(3)
chromosomes=generationPV,BB;(4)
Elite=competeElite,chromosomes;(5)
Betters=selectElite,chromosomes;(6)
PV=updatePV,Betters;(7)
BB=LinkageLearningBB,PV;(8)
end while


### 4.3.1. Probability Vector Initialization

Different from binary coding, the probability vector (PV) in this work is two-dimensional. The initialized PV and convergent PV are shown in Tables1 and 2, respectively. The value in the ith row and jth column represents the possibility of matching between the ith entity in O1 and the jth entity in O2; i.e., it means the probability of 0th entity of O1 (reference) and 0th entity of O2 (entry) is 1/1+1+1+1+1, which is shown in Table 1 (peculiarly, the header “−1 (null)” denotes the probability of no matching). The convergence condition is that the probability of taking a unique number on each locus in the PV is 1; i.e., in Table 2, the probability of the 0th entity of O1 (reference) and the 0th entity of O2 (entry) is 23.72/0+23.72+0+0+0 and so do the rest.Table 1
An example of initialized PV.
PV0 (Entry)1 (Book)2 (Proceedings)3 (Article)−1 (Null)0 (Reference)111111 (Book)111112 (Proceedings)111113 (Part)111114 (Article)11111Table 2
An example of convergent PV.
PV0 (Entry)1 (Book)2 (Proceedings)3 (Article)−1 (Null)0 (Reference)23.7200001 (Book)025.330002 (Proceedings)0026.01003 (Part)000022.464 (Article)00024.110


### 4.3.2. Chromosomes Generation

Certain size chromosomes are produced in each generation through PV. An example of chromosome is given in Figure5. In particular, subgraph (a) shows the locus of the chromosome and corresponding code, and subgraph (b) illustrates decoding chromosome in subgraph (b); i.e., it denotes that the fourth entity of O1 “Article” correspondent to the third entity of O2 “Article” as the code of the fourth locus is “3” (“−1 (Null)” indicates no matching).Figure 5
An example of chromosome.
(a)(b)


### 4.3.3. Fitness Function

The fitness function is used to determine which chromosomes in the population can better adapt the environment. In the context of ontology matching, the objective of fitness function is to find the best chromosome, whose corresponding alignment’s quality is the highest, with algorithm convergence. The objective function of the optimal model is used as the fitness function of this work, and given a chromosomeσ, its fitness function is defined as follows:(5)ξσ=2⋅β⋅ϕA+1−β⋅fA,where ξσ is the fitness function that is used in this paper; A is the alignment determined by σ; A is the cardinality of A; β, a fraction in the range [0, 1], is the relative weight of ϕA and fA, which is set to 0.25 in this paper; ϕ is a normalization function; and f is a function that calculates the mean of the matched entity pairs’ similarity values in A. In addition, ϕA and fA are defined as follows:(6)ϕA=AminO1,O2,(7)fA=∑i=1AηiA,where O1 and O2 are, respectively, the cardinality of O1 and O2 and ηi is the similarity of the ith matching pair in alignment A. In particular, ϕA is the ratio of the number of matching pair found to the value of the smaller entity number of the two ontologies and fA is the average similarity of the matching pairs found, which, respectively, approximates the recall value and precision value.


### 4.3.4. Selection Operator

The selection operator selects the best chromosomes in the current population to participate in the next step [41] and updates the PV. Firstly, the chromosomes are sorted in descending order according to their fitness scores. Secondly, the first half of the chromosomes will be retained as a temporary population. Finally, with fitness as the weight through roulette, we can select the chromosome from the temporary population for subsequent operation.


### 4.3.5. Elite Strategy

The goal of elite strategy is to keep the historical optimal solution and prevent the fitness of the optimal chromosome from “degenerating” in the process of evolution. In this work, the elite strategy has two steps: the historical optimal solutionElite first competes with the current optimal solution Best, and the winner will become the new Elite; the historical optimal solution then participates in the PV update in each generation.


### 4.3.6. Probability Vector Updating

An example of updating the PV is presented in Figure6, where subgraph (a) is a chromosome generated by the initialized PV. The similarity is derived from the similarity matrix according to the chromosome’s code. It should be noted that the code of the third locus is “0,” which means that the entity “Part” with sequence number “3” in O1 does not match any entity in O2, so its similarity is equal to 1 minus the value of the highest similarity between “Part” and all entities in O2, i.e., 1−0.38=0.62. PV will be updated by the normalized similarity of each locus, which is shown in subgraph (b). The probability of being updated in the PV is bold; i.e., the probability of matching pair “Reference” and “Entry” changed from “1” to “1.2” since the normalized similarity of the corresponding locus of chromosome is “0.20.”Figure 6
An example of update PV.
(a)(b)


### 4.3.7. Linkage Learning

Building blocks will be saved through linkage learning, thus to improve the efficiency of algorithm and quality of solution [42]. In simple GA, linkage learning is to identify great locus and protect them so that they will not be destroyed in the subsequent crossover and mutation operations; in ECGA, linkage learning keeps good probability distribution so that they are not disturbed in the subsequent update process. A linkage learning approach is proposed in this work, and its detail is shown in Figure 7.Figure 7
An example of linkage learning.For clarity, only column 1 of the original probability vector is selected for narration. In each generation, a low probability clearing operation is performed. The value of each column is divided by the maximum value of the row, and the value of the column will be cleared if the decimal is less than a specific value (0.2 in this work); i.e., 0, 2, 3, and −1 bits in PV are cleared and marked. The row of PV is a “good” probability distribution when all but one bit of this row are zero. Link learning generates building blocks based on the “good” probability distribution, i.e., a building block, the pair of index “0,” and code “0,” which was included in the rounded rectangle produced by linkage learning. After that, all the building blocks are directly put into each chromosome (the bold numbers), which reduces the consumption of runtime and memory consumption.


## 4.3.1. Probability Vector Initialization

Different from binary coding, the probability vector (PV) in this work is two-dimensional. The initialized PV and convergent PV are shown in Tables1 and 2, respectively. The value in the ith row and jth column represents the possibility of matching between the ith entity in O1 and the jth entity in O2; i.e., it means the probability of 0th entity of O1 (reference) and 0th entity of O2 (entry) is 1/1+1+1+1+1, which is shown in Table 1 (peculiarly, the header “−1 (null)” denotes the probability of no matching). The convergence condition is that the probability of taking a unique number on each locus in the PV is 1; i.e., in Table 2, the probability of the 0th entity of O1 (reference) and the 0th entity of O2 (entry) is 23.72/0+23.72+0+0+0 and so do the rest.Table 1
An example of initialized PV.
PV0 (Entry)1 (Book)2 (Proceedings)3 (Article)−1 (Null)0 (Reference)111111 (Book)111112 (Proceedings)111113 (Part)111114 (Article)11111Table 2
An example of convergent PV.
PV0 (Entry)1 (Book)2 (Proceedings)3 (Article)−1 (Null)0 (Reference)23.7200001 (Book)025.330002 (Proceedings)0026.01003 (Part)000022.464 (Article)00024.110


## 4.3.2. Chromosomes Generation

Certain size chromosomes are produced in each generation through PV. An example of chromosome is given in Figure5. In particular, subgraph (a) shows the locus of the chromosome and corresponding code, and subgraph (b) illustrates decoding chromosome in subgraph (b); i.e., it denotes that the fourth entity of O1 “Article” correspondent to the third entity of O2 “Article” as the code of the fourth locus is “3” (“−1 (Null)” indicates no matching).Figure 5
An example of chromosome.
(a)(b)


## 4.3.3. Fitness Function

The fitness function is used to determine which chromosomes in the population can better adapt the environment. In the context of ontology matching, the objective of fitness function is to find the best chromosome, whose corresponding alignment’s quality is the highest, with algorithm convergence. The objective function of the optimal model is used as the fitness function of this work, and given a chromosomeσ, its fitness function is defined as follows:(5)ξσ=2⋅β⋅ϕA+1−β⋅fA,where ξσ is the fitness function that is used in this paper; A is the alignment determined by σ; A is the cardinality of A; β, a fraction in the range [0, 1], is the relative weight of ϕA and fA, which is set to 0.25 in this paper; ϕ is a normalization function; and f is a function that calculates the mean of the matched entity pairs’ similarity values in A. In addition, ϕA and fA are defined as follows:(6)ϕA=AminO1,O2,(7)fA=∑i=1AηiA,where O1 and O2 are, respectively, the cardinality of O1 and O2 and ηi is the similarity of the ith matching pair in alignment A. In particular, ϕA is the ratio of the number of matching pair found to the value of the smaller entity number of the two ontologies and fA is the average similarity of the matching pairs found, which, respectively, approximates the recall value and precision value.


## 4.3.4. Selection Operator

The selection operator selects the best chromosomes in the current population to participate in the next step [41] and updates the PV. Firstly, the chromosomes are sorted in descending order according to their fitness scores. Secondly, the first half of the chromosomes will be retained as a temporary population. Finally, with fitness as the weight through roulette, we can select the chromosome from the temporary population for subsequent operation.


## 4.3.5. Elite Strategy

The goal of elite strategy is to keep the historical optimal solution and prevent the fitness of the optimal chromosome from “degenerating” in the process of evolution. In this work, the elite strategy has two steps: the historical optimal solutionElite first competes with the current optimal solution Best, and the winner will become the new Elite; the historical optimal solution then participates in the PV update in each generation.


## 4.3.6. Probability Vector Updating

An example of updating the PV is presented in Figure6, where subgraph (a) is a chromosome generated by the initialized PV. The similarity is derived from the similarity matrix according to the chromosome’s code. It should be noted that the code of the third locus is “0,” which means that the entity “Part” with sequence number “3” in O1 does not match any entity in O2, so its similarity is equal to 1 minus the value of the highest similarity between “Part” and all entities in O2, i.e., 1−0.38=0.62. PV will be updated by the normalized similarity of each locus, which is shown in subgraph (b). The probability of being updated in the PV is bold; i.e., the probability of matching pair “Reference” and “Entry” changed from “1” to “1.2” since the normalized similarity of the corresponding locus of chromosome is “0.20.”Figure 6
An example of update PV.
(a)(b)


## 4.3.7. Linkage Learning

Building blocks will be saved through linkage learning, thus to improve the efficiency of algorithm and quality of solution [42]. In simple GA, linkage learning is to identify great locus and protect them so that they will not be destroyed in the subsequent crossover and mutation operations; in ECGA, linkage learning keeps good probability distribution so that they are not disturbed in the subsequent update process. A linkage learning approach is proposed in this work, and its detail is shown in Figure 7.Figure 7
An example of linkage learning.For clarity, only column 1 of the original probability vector is selected for narration. In each generation, a low probability clearing operation is performed. The value of each column is divided by the maximum value of the row, and the value of the column will be cleared if the decimal is less than a specific value (0.2 in this work); i.e., 0, 2, 3, and −1 bits in PV are cleared and marked. The row of PV is a “good” probability distribution when all but one bit of this row are zero. Link learning generates building blocks based on the “good” probability distribution, i.e., a building block, the pair of index “0,” and code “0,” which was included in the rounded rectangle produced by linkage learning. After that, all the building blocks are directly put into each chromosome (the bold numbers), which reduces the consumption of runtime and memory consumption.


## 5. Experiments and Discussion

### 5.1. Experiment Setup

In the experiment, the Biblio benchmark provided by the Ontology Alignment Evaluation Initiative (OAEI) is used to verify the effectiveness of our approach. Normally, two ontologies to be matched and a reference alignment are included in each testing case as a standard to evaluate the quality of matching results. The testing cases can be classified into five categories, which are briefly described in Table3.Table 3
A brief description of OAEI Biblio benchmark.
CasesBrief description101–104The ontologies to be matched are the same or there is only a slight difference in OWL restriction between them201–210The ontologies to be matched have the same structural, but different lexical and linguistic features221–247The ontologies to be matched have the same lexical and linguistic, but different structural features248–266The ontologies to be matched have different lexical, linguistic, and structure features301–304The ontologies in the real world often have strong heterogeneityIn this work, the method is compared with the participants of OAEI-, GA-, and CGA-based ontology matching techniques. The experimental results are the H-mean values of 30 independent runs.


### 5.2. Alignment Evaluation Metrics according to Reference Alignment

A criterion is needed when evaluating the quality of matching systems. Given an alignment resultA, two measures, recall and precision, are employed in this work and their formula is as follows [22, 23]:(8)recallA=R∩AR,(9)precisionA=R∩AA,where R and A are the cardinality of matching pairs in the reference alignment provided in case set and the matching pairs in alignment are produced by the matching system and R∩A is the cardinality of matching pairs, which exist in both reference alignment and alignment found. It means that all the matching pairs in reference alignment have been found when recall is 1, while all the matching pairs found is correct when precision is 1.Both recall and precision are important parameters of the evaluation results and they should be considered at the same time. A weighted harmonic mean of recall and precision, F-measure, is used in this work, which is presented in the following equation[43]:(10)f−measureA=recallA⋅precisonAα⋅recallA+1−α⋅precisonA,where α0,1 is the relative weight of recall and precision and it is set as 0.5 in this work, which is named f1-measure.


### 5.3. Comparison with OAEI’s Participants

The participants from OAEI 2016, 2015, and 2014 are selected to compare with our approach. In particular, if a matching system has participated for more than one year, only the latest results are used. The harmonic mean comparison of participants and ECGA-OEM is shown in Figure8. The vertical axis represents different matching systems, and the horizontal axis represents the score of their corresponding parameters. In terms of f-measure, ECGA-OEM ranks third, which it is slightly lower than Lily and CroMatch. Wiki has been used as the linguistic measure in Lily and CroMatch, which is able to improve the performance of the algorithm at the expense of efficiency. In addition, ECGA-OEM has an unparalleled performance in maintaining the balance between precision and recall, while one of them is much higher than the other in the participants, which is very important in evaluating results quality.Figure 8
The harmonic mean of OAEI’s participants and ECGA-OEM.Furtherf-measure comparison of OAEI participants and ECGA-OEM in a total of 32 test cases is given. Figure 9 shows the numbers of participants with ECGA-OEM superior, equal, and inferior, respectively. The horizontal axis is the set of different test cases, and the vertical axis is the number of matching systems. In the vast majority of test cases, the number of matching systems with ECGA-OEM superior to is much higher than those ones with ECGA-OEM inferior to. Only in No. 246, No. 247, and No. 254 cases, the ranking of ECGA-OEM is relatively low (refer to also Table 4 for the specific f-measure values in each testing case).Figure 9
The number of participants with ECGA-OEM superior, equal, and inferior.Table 4
Comparison onF-measure harmonic mean on each testing case among OAEI participants and ECGA-OEM.
Case123456789101112131415161718ECGA-OEM+/=/-1010.970.961110.9300.980.730.870.780110.950.710.970.52113/5/02010.950.940.930.610.890.820.680.950.620.770.620.44110.840.620.770.47116/2/02020.810.840.920.810.860.820.640.870.620.760.620.420.980.990.850.620.760.480.9616/0/22210.970.95110.980.930.990.980.730.870.780.51110.940.720.970.53114/4/02220.970.9510.80.980.940.770.9900.850.770.51100.720.7800.9914/1/32230.970.961110.930.990.980.730.860.780.51110.940.720.970.53113/5/02240.960.951110.930.970.980.920.8710.51110.940.90.970.53112/6/02250.970.961110.930.990.980.730.870.780.51110.950.720.970.52113/5/0228110.93110.840.970.960.50.880.551110.920.4810.8110/8/02320.970.96110.980.930.970.980.930.8710.51110.940.90.970.53113/5/0233110.93110.840.970.960.50.880.551110.920.4810.8110/8/0236110.93110.840.970.960.860.8811110.920.810.819/9/02370.960.9510.810.940.770.9900.850.990.51100.910.7800.9912/2/42380.970.951110.930.990.980.930.8710.51110.950.90.970.52112/6/0239110.93110.840.970.960.50.880.551110.920.4810.80.979/1/8240110.93110.840.970.960.50.880.551110.920.4810.80.9910/0/8241110.93110.840.970.960.860.8811110.920.810.819/9/0246110.93110.840.970.960.860.8811110.920.810.80.989/0/9247110.93110.840.970.960.860.8811110.920.810.80.999/0/92480.830.840.930.810.860.820.840.870.630.760.620.450.980.970.80.620.770.430.915/0/32490.810.80.870.650.890.820.810.870.810.760.790.420.950.950.820.80.820.480.9618/0/02500.810.830.850.880.880.720.870.840.420.760.430.90.940.980.810.40.880.69118/0/02510.830.820.940.60.870.830.590.8700.750.610.430.930.9700.610.5900.9115/0/32520.820.8300.860.890.820.780.870.610.750.620.450.970.950.830.620.760.490.9216/0/22530.830.8300.790.870.820.790.870.810.760.790.420.970.940.860.790.810.470.916/0/22540.830.8500.880.880.720.890.840.420.760.430.920.940.980.810.40.8800.838/1/92570.840.8500.880.880.720.870.840.740.760.790.920.90.950.880.720.880.74118/0/02580.810.8300.60.880.830.580.870.680.730.790.450.930.9500.80.6600.9116/0/22590.830.8500.80.890.820.830.870.80.750.790.460.960.940.830.80.8100.9216/0/22600.810.8200.880.880.740.870.8500.790.430.90.930.9500.410.900.8812/2/42610.80.8500.880.880.720.870.840.420.760.430.90.890.890.830.40.8800.8915/2/12620.810.8300.880.880.720.850.840.740.760.790.920.940.940.810.70.880.690.839/1/8In Table4, the numbers from 1 to 18 in the first row are edna, AML, CroMatch, Lily, LogMap, LogMapLt, Xmap, LogMapBio, AML-2014, Gmap, LogMap-C, Mamba, AOT-2014, AOTL, MassMatch, OMReasoner, RSDLWB, and Xmap2, respectively. ECGA-OEM is the matching system proposed by us. The value of each column represents the f-measure score of the matching system in the corresponding case. The f-measure of participants higher than that of ECGA-OEM is bold, and the equal ones are underlined. The “+,” “=,” and “−” in the last column, respectively, indicate the number of matching systems, with ECGA-OEM superior, equal, and inferior.


### 5.4. Comparison among GA, CGA, and ECGA

To verify the performance of linkage learning, we compare ECGA with GA and CGA. The detailed f-measure and runtime of the three competitors are, respectively, shown in Tables5 and 6. All the GA, CGA, and ECGA’s results are the mean value of 30 independent runs. It can be seen that the replacement of crossover and mutation operators (GA) with probability vector (CGA) improves the f-measure and significantly reduces the runtime. The average f-measure is slightly improved, while the average runtime is reduced from 31.975 seconds to 3.540 seconds; i.e., it largely improves the algorithm’s efficiency with only takes about 1/10 of runtime. Except testing cases No. 301 and No. 304, CGA is more stable than GA in terms of both f-measure and runtime since their standard deviation is smaller. Testing cases No. 301 and No. 304 are the representatives of real-world cases with unique heterogeneity, which make the f-measure produced by CGA decreased slightly. Linkage learning, the technique applied in ECGA, further increased the score of f-measure and made decrement in runtime with average 1.749 seconds based CGA. A smaller standard deviation than CGA was obtained by ECGA, which certified the strong stability of ECGA. It is worth to be noticed that the f-measure score of ECGA in testing case No. 301 and No. 304 is almost the same as that of GA (only 0.003 score lower in testing case No. 301 and this minor difference could be ignored), which embodied the ability of linkage learning to overcome the CGA’s shortcoming.Table 5
Comparison ofF-measure and its standard deviation.
Testing caseGACGAECGAf-MeasureSt. devf-MeasureSt. devf-MeasureSt. dev1010.9960.0041.0000.0001.0000.0002010.9990.0031.0000.0001.0000.0002210.9960.0061.0000.0001.0000.0002230.9940.0070.9980.0041.0000.0022240.9970.0051.0000.0001.0000.0002330.9960.0071.0000.0001.0000.0002360.9970.0071.0000.0001.0000.0002400.9780.0200.9940.0121.0000.0002410.9940.0101.0000.0001.0000.0002500.9950.0091.0000.0001.0000.0002570.9930.0101.0000.0001.0000.0003010.6060.0030.5860.0250.6030.0073040.6650.0040.6500.0330.6720.007Average0.9390.0070.9410.0060.9440.001Table 6
Comparison of runtime and its standard deviation.
Testing caseGACGAECGARuntime (s)St. devRuntime (s)St. devRuntime (s)St. dev10144.2964.4474.1460.2552.0160.04720143.4636.1954.1440.2791.9760.04222143.2045.3654.1150.2232.0380.04122351.1466.6406.9470.2083.2260.25522444.6246.1064.1430.2772.0530.05823312.6863.0801.2760.0780.7340.02223613.4632.7971.2440.0540.7200.03024022.7404.9503.2940.0281.7710.14524113.4743.8041.2360.0760.7280.02425014.2562.5761.2350.0930.6240.02625714.5072.7651.2640.0820.6110.02830145.0564.2536.3060.8803.3530.08630452.7596.4006.6730.7052.8850.067Average31.9754.5683.5400.2491.7490.067


## 5.1. Experiment Setup

In the experiment, the Biblio benchmark provided by the Ontology Alignment Evaluation Initiative (OAEI) is used to verify the effectiveness of our approach. Normally, two ontologies to be matched and a reference alignment are included in each testing case as a standard to evaluate the quality of matching results. The testing cases can be classified into five categories, which are briefly described in Table3.Table 3
A brief description of OAEI Biblio benchmark.
CasesBrief description101–104The ontologies to be matched are the same or there is only a slight difference in OWL restriction between them201–210The ontologies to be matched have the same structural, but different lexical and linguistic features221–247The ontologies to be matched have the same lexical and linguistic, but different structural features248–266The ontologies to be matched have different lexical, linguistic, and structure features301–304The ontologies in the real world often have strong heterogeneityIn this work, the method is compared with the participants of OAEI-, GA-, and CGA-based ontology matching techniques. The experimental results are the H-mean values of 30 independent runs.


## 5.2. Alignment Evaluation Metrics according to Reference Alignment

A criterion is needed when evaluating the quality of matching systems. Given an alignment resultA, two measures, recall and precision, are employed in this work and their formula is as follows [22, 23]:(8)recallA=R∩AR,(9)precisionA=R∩AA,where R and A are the cardinality of matching pairs in the reference alignment provided in case set and the matching pairs in alignment are produced by the matching system and R∩A is the cardinality of matching pairs, which exist in both reference alignment and alignment found. It means that all the matching pairs in reference alignment have been found when recall is 1, while all the matching pairs found is correct when precision is 1.Both recall and precision are important parameters of the evaluation results and they should be considered at the same time. A weighted harmonic mean of recall and precision, F-measure, is used in this work, which is presented in the following equation[43]:(10)f−measureA=recallA⋅precisonAα⋅recallA+1−α⋅precisonA,where α0,1 is the relative weight of recall and precision and it is set as 0.5 in this work, which is named f1-measure.


## 5.3. Comparison with OAEI’s Participants

The participants from OAEI 2016, 2015, and 2014 are selected to compare with our approach. In particular, if a matching system has participated for more than one year, only the latest results are used. The harmonic mean comparison of participants and ECGA-OEM is shown in Figure8. The vertical axis represents different matching systems, and the horizontal axis represents the score of their corresponding parameters. In terms of f-measure, ECGA-OEM ranks third, which it is slightly lower than Lily and CroMatch. Wiki has been used as the linguistic measure in Lily and CroMatch, which is able to improve the performance of the algorithm at the expense of efficiency. In addition, ECGA-OEM has an unparalleled performance in maintaining the balance between precision and recall, while one of them is much higher than the other in the participants, which is very important in evaluating results quality.Figure 8
The harmonic mean of OAEI’s participants and ECGA-OEM.Furtherf-measure comparison of OAEI participants and ECGA-OEM in a total of 32 test cases is given. Figure 9 shows the numbers of participants with ECGA-OEM superior, equal, and inferior, respectively. The horizontal axis is the set of different test cases, and the vertical axis is the number of matching systems. In the vast majority of test cases, the number of matching systems with ECGA-OEM superior to is much higher than those ones with ECGA-OEM inferior to. Only in No. 246, No. 247, and No. 254 cases, the ranking of ECGA-OEM is relatively low (refer to also Table 4 for the specific f-measure values in each testing case).Figure 9
The number of participants with ECGA-OEM superior, equal, and inferior.Table 4
Comparison onF-measure harmonic mean on each testing case among OAEI participants and ECGA-OEM.
Case123456789101112131415161718ECGA-OEM+/=/-1010.970.961110.9300.980.730.870.780110.950.710.970.52113/5/02010.950.940.930.610.890.820.680.950.620.770.620.44110.840.620.770.47116/2/02020.810.840.920.810.860.820.640.870.620.760.620.420.980.990.850.620.760.480.9616/0/22210.970.95110.980.930.990.980.730.870.780.51110.940.720.970.53114/4/02220.970.9510.80.980.940.770.9900.850.770.51100.720.7800.9914/1/32230.970.961110.930.990.980.730.860.780.51110.940.720.970.53113/5/02240.960.951110.930.970.980.920.8710.51110.940.90.970.53112/6/02250.970.961110.930.990.980.730.870.780.51110.950.720.970.52113/5/0228110.93110.840.970.960.50.880.551110.920.4810.8110/8/02320.970.96110.980.930.970.980.930.8710.51110.940.90.970.53113/5/0233110.93110.840.970.960.50.880.551110.920.4810.8110/8/0236110.93110.840.970.960.860.8811110.920.810.819/9/02370.960.9510.810.940.770.9900.850.990.51100.910.7800.9912/2/42380.970.951110.930.990.980.930.8710.51110.950.90.970.52112/6/0239110.93110.840.970.960.50.880.551110.920.4810.80.979/1/8240110.93110.840.970.960.50.880.551110.920.4810.80.9910/0/8241110.93110.840.970.960.860.8811110.920.810.819/9/0246110.93110.840.970.960.860.8811110.920.810.80.989/0/9247110.93110.840.970.960.860.8811110.920.810.80.999/0/92480.830.840.930.810.860.820.840.870.630.760.620.450.980.970.80.620.770.430.915/0/32490.810.80.870.650.890.820.810.870.810.760.790.420.950.950.820.80.820.480.9618/0/02500.810.830.850.880.880.720.870.840.420.760.430.90.940.980.810.40.880.69118/0/02510.830.820.940.60.870.830.590.8700.750.610.430.930.9700.610.5900.9115/0/32520.820.8300.860.890.820.780.870.610.750.620.450.970.950.830.620.760.490.9216/0/22530.830.8300.790.870.820.790.870.810.760.790.420.970.940.860.790.810.470.916/0/22540.830.8500.880.880.720.890.840.420.760.430.920.940.980.810.40.8800.838/1/92570.840.8500.880.880.720.870.840.740.760.790.920.90.950.880.720.880.74118/0/02580.810.8300.60.880.830.580.870.680.730.790.450.930.9500.80.6600.9116/0/22590.830.8500.80.890.820.830.870.80.750.790.460.960.940.830.80.8100.9216/0/22600.810.8200.880.880.740.870.8500.790.430.90.930.9500.410.900.8812/2/42610.80.8500.880.880.720.870.840.420.760.430.90.890.890.830.40.8800.8915/2/12620.810.8300.880.880.720.850.840.740.760.790.920.940.940.810.70.880.690.839/1/8In Table4, the numbers from 1 to 18 in the first row are edna, AML, CroMatch, Lily, LogMap, LogMapLt, Xmap, LogMapBio, AML-2014, Gmap, LogMap-C, Mamba, AOT-2014, AOTL, MassMatch, OMReasoner, RSDLWB, and Xmap2, respectively. ECGA-OEM is the matching system proposed by us. The value of each column represents the f-measure score of the matching system in the corresponding case. The f-measure of participants higher than that of ECGA-OEM is bold, and the equal ones are underlined. The “+,” “=,” and “−” in the last column, respectively, indicate the number of matching systems, with ECGA-OEM superior, equal, and inferior.


## 5.4. Comparison among GA, CGA, and ECGA

To verify the performance of linkage learning, we compare ECGA with GA and CGA. The detailed f-measure and runtime of the three competitors are, respectively, shown in Tables5 and 6. All the GA, CGA, and ECGA’s results are the mean value of 30 independent runs. It can be seen that the replacement of crossover and mutation operators (GA) with probability vector (CGA) improves the f-measure and significantly reduces the runtime. The average f-measure is slightly improved, while the average runtime is reduced from 31.975 seconds to 3.540 seconds; i.e., it largely improves the algorithm’s efficiency with only takes about 1/10 of runtime. Except testing cases No. 301 and No. 304, CGA is more stable than GA in terms of both f-measure and runtime since their standard deviation is smaller. Testing cases No. 301 and No. 304 are the representatives of real-world cases with unique heterogeneity, which make the f-measure produced by CGA decreased slightly. Linkage learning, the technique applied in ECGA, further increased the score of f-measure and made decrement in runtime with average 1.749 seconds based CGA. A smaller standard deviation than CGA was obtained by ECGA, which certified the strong stability of ECGA. It is worth to be noticed that the f-measure score of ECGA in testing case No. 301 and No. 304 is almost the same as that of GA (only 0.003 score lower in testing case No. 301 and this minor difference could be ignored), which embodied the ability of linkage learning to overcome the CGA’s shortcoming.Table 5
Comparison ofF-measure and its standard deviation.
Testing caseGACGAECGAf-MeasureSt. devf-MeasureSt. devf-MeasureSt. dev1010.9960.0041.0000.0001.0000.0002010.9990.0031.0000.0001.0000.0002210.9960.0061.0000.0001.0000.0002230.9940.0070.9980.0041.0000.0022240.9970.0051.0000.0001.0000.0002330.9960.0071.0000.0001.0000.0002360.9970.0071.0000.0001.0000.0002400.9780.0200.9940.0121.0000.0002410.9940.0101.0000.0001.0000.0002500.9950.0091.0000.0001.0000.0002570.9930.0101.0000.0001.0000.0003010.6060.0030.5860.0250.6030.0073040.6650.0040.6500.0330.6720.007Average0.9390.0070.9410.0060.9440.001Table 6
Comparison of runtime and its standard deviation.
Testing caseGACGAECGARuntime (s)St. devRuntime (s)St. devRuntime (s)St. dev10144.2964.4474.1460.2552.0160.04720143.4636.1954.1440.2791.9760.04222143.2045.3654.1150.2232.0380.04122351.1466.6406.9470.2083.2260.25522444.6246.1064.1430.2772.0530.05823312.6863.0801.2760.0780.7340.02223613.4632.7971.2440.0540.7200.03024022.7404.9503.2940.0281.7710.14524113.4743.8041.2360.0760.7280.02425014.2562.5761.2350.0930.6240.02625714.5072.7651.2640.0820.6110.02830145.0564.2536.3060.8803.3530.08630452.7596.4006.6730.7052.8850.067Average31.9754.5683.5400.2491.7490.067


## 6. Conclusions

Ontology matching can effectively solve the problem of data heterogeneity by discovering correspondence between two ontologies’ entities. Compact encoding mechanism shows high efficiency in ontology matching, especially in ontology entity matching. Linkage learning, which is employed in ECGA-OEM proposed in this paper, can produce qualified alignment of ontology matching. The experiment results have shown that our approach outperforms the participants of OAEI in terms of f-measure, recall, and precision. The comparison on terms of f-measure and runtime with GA, CGA, and ECGA shows that ECGA-OEM is able to greatly reduce the runtime consumption while maintaining the alignment’s quality.In the future, we would like to apply the linkage learning in other compact SIAs for better results. In addition, matching large-scale ontologies, such as anatomy and large biomedical track in OAEI, are an open challenge in the domain of ontology matching. We are interested in using the improved ECGA to match these large-scale ontologies.



---

*Source: 5574732-2021-02-05.xml*