Simulated annealing-based ontology matching [1], or SANOM, is an ontology alignment system which exploits the well-known simulated annealing to find the correspondences. The system considers three different similarity measures, namely string-based, linguistic-based and structural-based measures. A rudimentary version of the proposed method is participated in Ontology Alignment Evaluation Initiative (OAEI) 2017, and the results are report accordingly. SANOM is an energy-based ontology alignment system which tries to find the most possible alignment through the minimization of a predefined energy function by the well-known simulated annealing method. To define the energy function for a given alignment, we need to process each existing correspondence. To do so, three different similarity measures is taken into account. For each correspondence in the alignment, the minus sum of all the similarity measures is considered as the energy; therefore, the alignment with minimum energy entails more similar concepts. In the following, the potential similarity measures are reviewed along with the simulated annealing.
Simulated annealing is a probabilistic approach to estimate the global optimum of problems which cannot be solved by the standard optimization techniques. As the name suggests, this technique simulates the annealing in metallurgy which slowly cool the materials to decrease their defects.
The controlled cooling in the simulated annealing method is implemented as the decrease in the probability of accepting the worse solution. It is fundamental in this algorithm to accept the worse solutions with some probability in order to escape the local optimum.
Let S be the current state and S ′ be the successor (or the neighbor) created based on the current state. Simulated annealing needs a fitness function to estimate the fineness of each state. The transition form the current state to the next is probabilistic: If the successor has a better fitness than the current state, then the transition to the successor will definitely happen (or with the probability of 1.) In other words, the transition to the successor is made if ∆Eng = f itness(successor) f itness(current) > 0 where ∆Eng is the difference between the fitness of two states and fitness(a) indicates the fineness of the state a. Otherwise, if the successor is not as good as the current state, e.g. ∆Eng < 0, the transition happens with the probability of P = e ∆TE where T is the temperature. It is plain to see that transition to the worse solution is less likely when the temperature is lower. The simulated annealing algorithm starts with higher temperature and gradually decreases the temperature. This means that the probability of transition to the worse solution is way higher at the beginning, and little by little it is less feasible to get the worse solution as the temperature augments.
The ontology alignment is the relation between the concepts of two given ontologies. The relation (or map) could be seen as a bipartite graph, in which each part represents the concepts of one ontology and the edges indicate the similarity among concepts.
Let G be the bipartite graph depicting the relation between the concepts of two given ontologies. Assume that C1 and C2 are the concepts of two given ontologies, the nodes of the graph are the concepts of two ontologies, i.e. V = C1 + C2, and the edges connect each concept from one side of the graph to the other. The weights w of edges are the similarity among the concepts, which can be shown by w : E ! R, where E C1 C2.
The cardinality is assumed to be 1 : 1, meaning that each concept from the first ontology is mapped only with (maximum) one concept from the target. Let S (e); e 2 E be the similarity between two arbitrary concepts, the goal could be summarized in the following problem To gauge the similarity of two given concepts, various measures are considered. The similarity measures are classified into string, linguistic and structural measures. Thus, S (e) can be defined as where S s(:), S l(:) and S st are the string, linguistic and structural similarity measures, respectively. 1.3. SANOM Let the energy function Eng(:) be max ∑ S (e)
e2E S (e) = S s(e) + S l(e) + S st(e)
Eng(E) = ∑ S (e) e2E then the output alignment of the above energy function from the simulated annealing method is the final result of the system.
In this section, the results of various tracks in which SANOM has participated are reported.
The Anatomy track is the challenge of matching two different anatomy ontologies from human and mouse.
The result of SANOM is compared with other systems via McNemars test. There are two ways to apply
McNemars test in which the difference is if we consider the false correspondences or not [
According to these figures, SANOM has outperformed ONTOEMMA, WikiV3 and Alin in both cases while AML, POMap, YAM-Bio and Xmap has a better performance than SANOM. Further, SANOM and KEPLER is quite competitive: If the false correspondences are taken into account KEPLER is better while SANOM is superior if only correct correspondences are taken into account. It means that SANOM has more true and false correspondences than KEPLER.
AML
This track includes the alignment between ontologies coming from different languages. SANOM, in the
current version, does not use any translator so that it is not able to find good correspondences in this track.
However, it has produced some results due to the structural similarity between two ontologies. SANOM
is compared with other participants via the Friedman test [
According to this diagram, AML is the best system in comparison with others. As expected, SANOM does have not a good performance because of lack of a translator, but its performance is slightly better than XMap and LogMapLite.
The conference track consists of 21 different matching tasks coming from coupling of 6 different ontologies. There are three different mapping tasks, namely mapping only classes (M1), only properties (M2),
AML
and mapping both (M3). For the reference alignment, three different reference alignments, e.g. ra1, ra2 and rar2, are considered. Therefore, there are overally 9 different types of matching, each of which has 21 mapping tasks. Table 1 tabulates the average F-measure of SANOM in each type of matching. For the tasks which the properties is desired, SANOM has a degraded performance as its current version does not consider the matching of properties. SANOM participated in OAEI 2017 for the first time. The system is in its rudimentary state, but we plan to more advance it to be able to compete with top systems. Nonetheless, the performance of SANOM is quite fair in the tracks it participated this year.