FCA-Map is an automatic ontology matching system based on Formal Concept Analysis (FCA), which is a well developed mathematical model for analyzing individuals and structuring concepts. More precisely, we construct three types of formal contexts and extracts mappings from the lattices derived. Firstly, token-based formal context describes how class names, labels and synonyms share lexical tokens, leading to lexical mappings (anchors) across ontologies. Secondly, relation-based formal context describes how classes are in taxonomic or disjoint relationships with the anchors, leading to positive and negative structural evidence for validating the lexical matching. Lastly, after incoherence repair, positive relation-based context can be used to discover additional structural mappings. In this paper, we briefly introduce FCA-Map and its results of three tracks (i.e., Anatomy, Large Biomedical Ontologies, Disease and Phenotype) on OAEI 2016.
FCA with as much as ontological information as possible, we proposed FCA-Map, which generates three types of formal contexts and extracts mappings from the lattices derived. The next sub-sections provide more details about FCA-Map and then discuss our results of OAEI. 1.1
Given two ontologies, FCA-Map builds formal contexts and uses the derived concept lattices to cluster the commonalities among ontology classes, at lexical level and structural level, respectively. Concretely, FCA-Map performs step-by-step as follows. 1. Acquiring anchors lexically. The token-based formal context is constructed, and from its derived concept lattice, a group of lexical anchors A across ontologies can be extracted. 2. Validating anchors structurally. Based on A , the relation-based formal context is constructed, and from its derived concept lattice, positive and negative structural evidence of anchors can be extracted. Moreover, an enhanced alignment A0 without incoherences among anchors is obtained. 3. Discovering additional matches. Based on A0, the positive relation-based formal context is constructed, and from its derived concept lattice, additional matches across ontologies can be identified. 1.2
The process of our system consists of the following successive steps.
The token-based formal context Klex := (Glex; Mlex; Ilex) is described as follows. Names of ontology classes as well as their labels and synonyms, when available, are exploited after normalization that includes inflection, tokenization, stop word elimination, and punctuation elimination. In Klex, Glex is the set of strings each corresponding to a name, label, or synonym of classes in two ontologies, Mlex is the set of tokens in these strings, and binary relation (g; m) 2 Ilex holds when string g contains token m, or a synonym or lexical variation of m. For the derived formal concepts, we restrict our attention to formal concepts whose simplified extent or class-origin extent contains exactly two strings or classes across ontologies, and extract two types of lexical anchors, namely Type I anchor for the exact match, and Type II anchor for the partial match, respectively.
Sept 2: Constructing the relation-based formal context to validate lexical anchors. Structural relationships of ontologies are exploited to validate the matches obtained at the lexical level. [7] proposed using positive and negative structural evidence among anchors for the purpose of validation. In this step, we build the relation-based formal context to obtain both positive and negative structural evidence for lexical anchors. The relation-based formal context Krel := (Grel; Mrel; Irel) is described as follows. Classes in two source ontologies are taken as object set Grel, and lexical anchors prefixed with different relational labels are taken as attribute set Mrel. For example, relationships ISA, SIBLING-WITH, PART-OF, and DISJOINT-WITH are labeled by “(ISA)”, “(SIB)”, “(PAT)”, and “(I-D)” (or “(D-I)”), respectively. Binary relation (g; m) 2 Irel holds if g has the corresponding relationship (as in the prefix of m) with the class from the same source ontology as g in the anchor of m. Formal concepts whose extents include both classes in some anchors indicate structural evidence. Such anchors are positive evidence to anchors with label“(ISA)”, “(SIB)” or “(PAT)” in the intent, and vice versa. On the other hand, they are negative evidence to anchors with label “(I-D)” or “(D-I)” in the intent, and vice versa. In this way, positive and negative structural evidence set of each anchor a can be obtained, denoted by P (a) and N (a), respectively. Then we utilize all the positive evidence sets P and negative evidence sets N to eliminate incorrect lexical anchors and retain the correct ones.
Setp 3: Constructing the positive relation-based formal context to discover additional matches. After incoherence repair and screening, anchors retained are those supported both lexically and structurally. Based on the enhanced alignment, FCA-Map goes further to build the positive relation-based formal context aiming to identify new, structural mappings. The way positive relation-based formal context K0rel constructed is similar to Krel, i,e., using classes in two source ontologies as object set and anchors prefixed with relationship labels as attribute set, where disjointedness relationship is no longer necessary. For the derived formal concepts, we restrict our attention to those with exactly two classes across ontologies in the simplified extent. 1.3
SEALS wrapped version of FCA-Map for OAEI 2016 is available at https://drive.google. com/open?id=0B810qAwN1CIoM0NMV3ZJMzVsTlk. 1.4
The results obtained by FCA-Map during OAEI 2016 are available at https://drive.google. com/open?id=0B810qAwN1CIodGdPUjVWY0M3U0U. 2
In this section, we present the results of FCA-Map achieved on OAEI 2016. Our system mainly focuses on Anatomy, Large Biomedical Ontologies, Disease and Phenotype. 2.1
The Anatomy track consists of finding an alignment between the Adult Mouse Anatomyand a part of the NCI Thesaurus describing the human anatomy. The results are shown in Table 1. The evaluation was run on a server with 3.46 GHz (6 cores) and 8GB RAM allocated. FCA-Map ranked fifth in Anatomy track.
Matcher
AML CroMatcher
XMAP LogMapBio FCA-Map The Large BioMed track consists of finding alignments between the Foundational Model of Anatomy (FMA), SNOMED CT, and the National Cancer Institute Thesaurus (NCI). The results obtained by FCA-Map for the small fragments of the FMA, NCI and SNOMED CT ontologies are summarize in Table 2. The evaluation of first two tasks was run on a Ubuntu Laptop with an Intel Core i7-4600U CPU @ 2.10GHz x 4 and 15Gb RAM allocated with 2 hours timeout. And the last task was run on a PC with Intel i7-4790 CPU @ 3.60GHz and 8GB RAM allocated. FCA-Map ranks second in the first two tasks.
Task
FMA-NCI (small) FMA-SNOMED (small) SNOMED-NCI (small)
Precision Recall F-Measure Runtime (s) 0.954 0.917 0.935 236 0.936 0.803 0.865 1,865 0.914 0.666 0.771 13,542 This is the first time FCA-Map system participates in the OAEI campaign. It is competitive with other systems in some tracks such as Anatomy, Large Biomedical Ontologies, Disease and Phenotype. Three types of formal contexts are constructed one-by-one, and their derived concept lattices are used to cluster the commonalities among classes at lexical and structural level, respectively. The tokens shared by two classes in these mappings are unique to their names. The lexical matching method of FCA-Map is suitable for domain ontologies having class names, labels, or synonyms from domain-specific vocabulary. 4
In this paper, we have presented FCA-Map and its results of three tracks (i.e.,Anatomy, Large Biomedical Ontologies, Disease and Phenotype) on OAEI 2016. The evaluation results show the good performance of FCA-Map. Future work would introduce more elements of ontology into FCA-Map including properties, individuals, and logical constructors and axioms. Optimization techniques for handling large-scale FCA contexts will also be worth exploring.
Acknowledgements. This work has been supported by the National Key Research and Development Program of China under grant 2016YFB1000902, the Natural Science Foundation of China under No. 61232015, the Knowledge Innovation Program of the Chinese Academy of Sciences (CAS), Key Lab of Management, Decision and Information Systems of CAS, and Institute of Computing Technology of CAS. 6. Xu, X., Wu, Y., Chen, J.: Fuzzy fca based ontology mapping. In: 2010 First International
Conference on Networking and Distributed Computing, IEEE (2010) 181–185
7. Zhang, S., Bodenreider, O.: Experience in aligning anatomical ontologies. International
journal on Semantic Web and information systems 3(