Using MOEA/D for optimizing ontology alignments

This paper proposes a novel approach which uses a multi-objective evolutionary algorithm based on decomposition to address the ontology alignment optimization problem. Comparing with the approach based on Genetic Algorithm (GA), our method can simultaneously optimize three goals (maximizing the alignment recall, the alignment precision and the f-measure). The experimental results shows that our approach is able to provide various alignments in one execution which are less biased to one of the evaluations of the alignment quality than GA approach, thus the quality of alignments are obviously better than or equal to those given by the approach based on GA which considers precision, recall and f-measure only, and other multi-objective evolutionary approach such as NSGA-II approach. In addition, the performance of our approach outperforms NSGA-II approach with the average improvement equal to 32.79  \(\%\) . Through the comparison of the quality of the alignments obtained by our approach with those by the state of the art ontology matching systems, we draw the conclusion that our approach is more effective and efficient.     

Evaluation of two heuristic approaches to solve the ontology meta-matching problem

Nowadays many techniques and tools are available for addressing the ontology matching problem, however, the complex nature of this problem causes existing solutions to be unsatisfactory. This work aims to shed some light on a more flexible way of matching ontologies. Ontology meta-matching, which is a set of techniques to configure optimum ontology matching functions. In this sense, we propose two approaches to automatically solve the ontology meta-matching problem. The first one is called maximum similarity measure, which is based on a greedy strategy to compute efficiently the parameters which configure a composite matching algorithm. The second approach is called genetics for ontology alignments and is based on a genetic algorithm which scales better for a large number of atomic matching algorithms in the composite algorithm and is able to optimize the results of the matching process.     

A Compact Co-Evolutionary Algorithm for sensor ontology meta-matching

With the proliferation of sensors, semantic web technologies are becoming closely related to sensor network. The linking of elements from semantic web technologies with sensor networks is called semantic sensor web whose main feature is the use of sensor ontologies. However, due to the subjectivity of different sensor ontology designer, different sensor ontologies may define the same entities with different names or in different ways, raising so-called sensor ontology heterogeneity problem. There are many application scenarios where solving the problem of semantic heterogeneity may have a big impact, and it is urgent to provide techniques to enable the processing, interpretation and sharing of data from sensor web whose information is organized into different ontological schemes. Although sensor ontology heterogeneity problem can be effectively solved by Evolutionary Algorithm (EA)-based ontology meta-matching technologies, the drawbacks of traditional EA, such as premature convergence and long runtime, seriously hamper them from being applied in the practical dynamic applications. To solve this problem, we propose a novel Compact Co-Evolutionary Algorithm (CCEA) to improve the ontology alignment’s quality and reduce the runtime consumption. In particular, CCEA works with one better probability vector (PV) \(PV_{better}\) and one worse PV \(PV_{worse}\), where \(PV_{better}\) mainly focuses on the exploitation which dedicates to increase the speed of the convergence and \(PV_{worse}\) pays more attention to the exploration which aims at preventing the premature convergence. In the experiment, we use Ontology Alignment Evaluation Initiative (OAEI) test cases and two pairs of real sensor ontologies to test the performance of our approach. The experimental results show that CCEA-based ontology matching approach is both effective and efficient when matching ontologies with various scales and under different heterogeneous situations, and compared with the state-of-the-art sensor ontology matching systems, CCEA-based ontology matching approach can significantly improve the ontology alignment’s quality.     

基于局部标准匹配结果的本体匹配技术

针对已有的基于进化算法的本体匹配技术要求事先提供完整的标准匹配结果的缺陷,提出一种基于局部标准匹配结果的本体匹配技术．首先提出通过本体概念聚类算法以构建局部标准匹配结果,并在此基础上建立基于局部标准匹配结果的本体匹配问题的多目标优化模型;然后设计一种基于局部标准匹配结果的MOEA/D算法;最后,采用2012年的本体匹配评价竞赛的测试数据集进行实验,实验结果表明所提出的方法是有效的．     

Detecting duplicate objects in ontologies using FCA

In our work we consider a new approach to detecting duplicates in an ontology built on real redundant data. This approach is based on the transformation of an initial ontology into a formal context and processing of this context using Formal Concept Analysis (FCA) methods. A new index for measuring the similarity between objects in formal concept analysis is introduced to detect duplicate objects. We study the new approach on a real ontology based on the collection of political news and documents. The proposed index is compared with the existing indices and methods for detecting object similarity.     

基于NSGA-Ⅱ的大规模本体映射方法

现有的基于进化算法的本体映射技术在面对大规模本体映射问题时,由于搜索空间太大导致算法效率低下,从而使其无法有效地在实际中得到应用。针对这一问题,提出了基于快速非支配排序的多目标遗传算法(NSGA-Ⅱ)的大规模本体映射方法。该方法通过三个步骤来映射本体:1)通过基于邻居相似度的划分算法来将源本体划分为不相交的概念块;2)通过相关概念过滤方法来确定目标本体中同源本体概念块相关的概念块;3)使用NSGA-Ⅱ方法来完成概念块之间的映射并通过贪心算法集成最终的结果。使用OAEI 2012的小规模的书目本体测试数据集和大规模的生物医学本体测试数据集对所提出的方法进行测试。同OAEI 2012的参与者的比较结果表明,所基于NSGA-Ⅱ的大规模本体映射方法能够在较短的时间内获取较好的本体映射结果,因此该方法是有效的。     

传播式启发式图搜索算法PRA及PRA

本文基于传播值的概念,提出了一个新的传播式启发式图搜索算法PRA及PRA,算法PRA是可采纳的,且在运行时间上优于算法RA,本文还基于约束消解的概念,研究了算法RA与PRA之间在运行结果上的关系定理。     

A segment-based approach for large-scale ontology matching

The most ground approach to solve the ontology heterogeneous problem is to determine the semantically identical entities between them, so-called ontology matching. However, the correct and complete identification of semantic correspondences is difficult to achieve with the scale of the ontologies that are huge; thus, achieving good efficiency is the major challenge for large- scale ontology matching tasks. On the basis of our former work, in this paper, we further propose a scalable segment-based ontology matching framework to improve the efficiency of matching large-scale ontologies. In particular, our proposal first divides the source ontology into several disjoint segments through an ontology partition algorithm; each obtained source segment is then used to divide the target ontology by a concept relevance measure; finally, these similar ontology segments are matched in a time and aggregated into the final ontology alignment through a hybrid Evolutionary Algorithm. In the experiment, testing cases with different scales are used to test the performance of our proposal, and the comparison with the participants in OAEI 2014 shows the effectiveness of our approach.     

RiMOM: A Dynamic Multistrategy Ontology Alignment Framework

Ontology alignment identifies semantically matching entities in different ontologies. Various ontology alignment strategies have been proposed; however, few systems have explored how to automatically combine multiple strategies to improve the matching effectiveness. This paper presents a dynamic multistrategy ontology alignment framework, named RiMOM. The key insight in this framework is that similarity characteristics between ontologies may vary widely. We propose a systematic approach to quantitatively estimate the similarity characteristics for each alignment task and propose a strategy selection method to automatically combine the matching strategies based on two estimated factors. In the approach, we consider both textual and structural characteristics of ontologies. With RiMOM, we participated in the 2006 and 2007 campaigns of the Ontology Alignment Evaluation Initiative (OAEI). Our system is among the top three performers in benchmark data sets.     

改进的本体概念相似度计算模型

本体映射能很好地解决语义网中的本体异构性问题,其核心在于计算本体概念的相似度。针对现有的概念相似度计算的精度和查准率不高,提出一种改进的概念相似度计算模型。首先利用本体特征之间的偏序关系建立形式背景和概念格,然后在结构层次求出概念间的交不可约元集,并通过对集合里各元素的语义关系进行量化计算出概念间的相似度。实例和分析结果表明,改进的概念相似度计算模型在F-Score上有明显提高。     

一种基于语义词典的本体对齐框架

提出一种基于语义词典的本体对齐框架.首先抽取出代表本体元素的字符串,这些字符串包括本体中的概念、实例、关系等,并利用现有的词典和语义资源将字符串变为词的集合;然后将本体对齐转换为单词集合间的映射,通过多相似度的匹配算法来进行相似度计算,从而实现本体对齐.实验结果表明,所提出的方法是有效的且较之以前的对齐方法有一定的提高.     

Multiple sequence alignment with affine gap by using multi-objective genetic algorithm

Multiple sequence alignment is of central importance to bioinformatics and computational biology. Although a large number of algorithms for computing a multiple sequence alignment have been designed, the efficient computation of highly accurate and statistically significant multiple alignments is still a challenge. In this paper, we propose an efficient method by using multi-objective genetic algorithm (MSAGMOGA) to discover optimal alignments with affine gap in multiple sequence data. The main advantage of our approach is that a large number of tradeoff (i.e., non-dominated) alignments can be obtained by a single run with respect to conflicting objectives: affine gap penalty minimization and similarity and support maximization. To the best of our knowledge, this is the first effort with three objectives in this direction. The proposed method can be applied to any data set with a sequential character. Furthermore, it allows any choice of similarity measures for finding alignments. By analyzing the obtained optimal alignments, the decision maker can understand the tradeoff between the objectives. We compared our method with the three well-known multiple sequence alignment methods, MUSCLE, SAGA and MSA-GA. As the first of them is a progressive method, and the other two are based on evolutionary algorithms. Experiments on the BAliBASE 2.0 database were conducted and the results confirm that MSAGMOGA obtains the results with better accuracy statistical significance compared with the three well-known methods in aligning multiple sequence alignment with affine gap. The proposed method also finds solutions faster than the other evolutionary approaches mentioned above.     

Semantic similarity estimation from multiple ontologies

The estimation of semantic similarity between words is an important task in many language related applications. In the past, several approaches to assess similarity by evaluating the knowledge modelled in an ontology have been proposed. However, in many domains, knowledge is dispersed through several partial and/or overlapping ontologies. Because most previous works on semantic similarity only support a unique input ontology, we propose a method to enable similarity estimation across multiple ontologies. Our method identifies different cases according to which ontology/ies input terms belong. We propose several heuristics to deal with each case, aiming to solve missing values, when partial knowledge is available, and to capture the strongest semantic evidence that results in the most accurate similarity assessment, when dealing with overlapping knowledge. We evaluate and compare our method using several general purpose and biomedical benchmarks of word pairs whose similarity has been assessed by human experts, and several general purpose (WordNet) and biomedical ontologies (SNOMED CT and MeSH). Results show that our method is able to improve the accuracy of similarity estimation in comparison to single ontology approaches and against state of the art related works in multi-ontology similarity assessment.     

Language Structure Using Fuzzy Similarity

Learning of (context-free) grammar rules that are based on alignment between texts of a given collection of sentences has attracted the attention of many researchers. We define and study the alignment profile and formulate fuzzy similarity of alignment profiles for a given collection of sentences. Using the fuzzy-similarity-based profile alignment, we give a methodology to formulate stochastic context-free grammar (CFG) rules. We introduce profile-alignment-based dynamic sentence similarity threshold to formulate the rules of stochastic CFG. The proposed methodology is tested using Child Language Data Exchange System (CHILDES) dataset of sentences. The benefits of our approach are experimentally demonstrated. Since our approach does not make use of any domain knowledge, it is expected to be useful in wide variety of applications requiring model construction.     

一种综合事件本体相似度计算方法

事件本体相比于传统本体具有更加丰富的语义信息,在面向事件的大数据集成中更具优势,然而用传统的本体相似计算方法计算事件本体相似度存在很多不足,提出了一种综合的事件本体相似度计算方法。该方法以词语相似度、集合相似度、层次结构相似计算为基础,然后从事件类名称、事件类要素、事件类层次结构和非层次结构讨论事件本体的相似度,最终获得事件本体的综合相似度。实验表明该方法相比传统本体相似度计算方法准确率更高,语义信息更加丰富。     

Using Fuzzy Ontology to Improve Similarity Assessment: Method and Evaluation

Assessing semantic similarity is a fundamental requirement for many AI applications. Crisp ontology (CO) is one of the knowledge representation tools that can be used for this purpose. Thanks to the development of semantic web, CO‐based similarity assessment has become a popular approach in recent years. However, in the presence of vague information, CO cannot consider uncertainty of relations between concepts. On the other hand, fuzzy ontology (FO) can effectively process uncertainty of concepts and their relations. This paper aims at proposing an approach for assessing concept similarity based on FO. The proposed approach incorporates fuzzy relation composition in combination with an edge counting approach to assess the similarity. Accordingly, proposed measure relies on taxonomical features of an ontology in combination with statistical features of concepts. Furthermore, an evaluation approach for the FO‐based similarity measure named as FOSE is proposed. Considering social network data, proposed similarity measure is evaluated using FOSE. The evaluation results prove the dominance of proposed approach over its respective CO‐based measure.     

基于概念集群的本体映射方法研究

本体异构是目前本体应用的一大瓶颈,而本体映射则是解决本体异构性的基础。基于概念集群的本体映射方法(CCOM)将概念间的语义结构关系引入映射过程中,用概念集群相似度代替概念相似度进行映射规则推导。实验证明本方法具有较好的查全率与查准率。     

Hybrid multiobjective artificial bee colony for multiple sequence alignment

In the bioinformatics community, it is really important to find an accurate and simultaneous alignment among diverse biological sequences which are assumed to have an evolutionary relationship. From the alignment, the sequences homology is inferred and the shared evolutionary origins among the sequences are extracted by using phylogenetic analysis. This problem is known as the multiple sequence alignment (MSA) problem. In the literature, several approaches have been proposed to solve the MSA problem, such as progressive alignments methods, consistency-based algorithms, or genetic algorithms (GAs). In this work, we propose a Hybrid Multiobjective Evolutionary Algorithm based on the behaviour of honey bees for solving the MSA problem, the hybrid multiobjective artificial bee colony (HMOABC) algorithm. HMOABC considers two objective functions with the aim of preserving the quality and consistency of the alignment: the weighted sum-of-pairs function with affine gap penalties (WSP) and the number of totally conserved (TC) columns score. In order to assess the accuracy of HMOABC, we have used the BAliBASE benchmark (version 3.0), which according to the developers presents more challenging test cases representing the real problems encountered when aligning large sets of complex sequences. Our multiobjective approach has been compared with 13 well-known methods in bioinformatics field and with other 6 evolutionary algorithms published in the literature.     

Variable weight semantic graph‐based ontology mapping method

The mapping method that is based on the name and structure of the ontology elements is the strategy used in most mapping methods. Methods using the name often only use the similarity between the individual elements in the ontology to predict the semantic relations between two ontologies, while the latter measure the mapping between two ontologies by means of the structural relations between the elements. The effects of these two kinds of mapping strategies are not ideal. Addressing this issue, the work presented in this paper proposes an ontology mapping approach, in which the ontology element name and structure are combined. It uses the approaches based on linguistics and distance to generate a variable weight semantic graph. On this graph, the similarity of element names and structure are calculated through iterative computation. In the process of iteration, similarity result values are constantly adjusted. The approach avoids the problem of single methods that cannot use the entire amount of ontology information; therefore, it provides a more ideal mapping result. For making full use of the message of ontology, our implementation and experimental results are provided to demonstrate the effectiveness of the mapping approach.     

MRMOGA: a new parallel multi‐objective evolutionary algorithm based on the use of multiple resolutions

In this paper, we introduce MRMOGA (Multiple Resolution Multi‐Objective Genetic Algorithm), a new parallel multi‐objective evolutionary algorithm which is based on an injection island approach. This approach is characterized by adopting an encoding of solutions which uses a different resolution for each island. This approach allows us to divide the decision variable space into well‐defined overlapped regions to achieve an efficient use of multiple processors. Also, this approach guarantees that the processors only generate solutions within their assigned region. In order to assess the performance of our proposed approach, we compare it to a parallel version of an algorithm that is representative of the state‐of‐the‐art in the area, using standard test functions and performance measures reported in the specialized literature. Our results indicate that our proposed approach is a viable alternative to solve multi‐objective optimization problems in parallel, particularly when dealing with large search spaces. Copyright © 2006 John Wiley & Sons, Ltd.