As a well developed mathematical model for analyzing individuals and structuring concepts, Formal Concept Analysis (FCA) has been applied to ontology matching (OM) tasks since the beginning of OM research, whereas ontological knowledge exploited in FCA-based methods is limited. The study in this paper aims to empowering FCA with as much as ontological knowledge as possible for identifying and validating mappings across ontologies. Our method, called FCA-Map, constructs three types of formal contexts and extracts mappings from the lattices derived. Firstly, the token-based formal context describes how class names, labels and synonyms share lexical tokens, leading to lexical mappings (anchors) across ontologies. Secondly, the relation-based formal context describes how classes are in taxonomic, partonomic and disjoint relationships with the anchors, leading to positive and negative structural evidence for validating the lexical matching. Lastly, after incoherence repair, the positive relationbased context can be used to discover additional structural mappings. Evaluation on anatomy track and large biomedical ontologies track of the 2015 Ontology Alignment Evaluation Initiative (OAEI) campaign demonstrates the effectiveness of FCA-Map and its competitiveness with 2015 OAEI top-ranked OM systems.
In the Semantic Web, ontologies model domain conceptualizations so that applications
built upon them can interoperate with each other by sharing the same meanings. Such
knowledge sharing and reuse can be severely hindered by the fact that ontologies for
the same domain are often developed for various purposes, differing in coverage,
granularity, naming, structure and many other aspects. Ontology matching (OM) techniques
aim to alleviate the heterogeneity by identifying correspondences across ontologies.
Ontology matching can be performed at the element level and the structure level [
Among the first batch of OM algorithms and tools proposed in the early 2000s,
FCA-Merge [
Following the steps of FCA-Merge, several OM systems continued to use FCA as
well as its alternative formalisms, exploiting different entities as the sets of objects
and attributes for constructing formal contexts [
This motivated the study in this paper, i.e., empowering FCA with as much as ontological information as possible for identifying and validating mappings across ontologies. Our method, called FCA-Map, generates three types of formal contexts and extracts mappings from the lattices derived. Firstly, the token-based formal context describes how class names, labels and synonyms share lexical tokens, leading to lexical mappings (anchors) across ontologies. Secondly, the relation-based formal context describes how classes are in taxonomic, partonomic and disjoint relationships with the anchors, leading to positive and negative structural evidence for validating the lexical matching. Lastly, after incoherence repair, the positive relation-based context can be used to discover additional structural mappings. Evaluation on anatomy track and large biomedical ontologies track of the 2015 Ontology Alignment Evaluation Initiative (OAEI) campaign demonstrates the effectiveness of FCA-Map and its competitiveness with 2015 OAEI top-ranked OM systems. 2
Formal Concept Analysis (FCA) is a mathematical theory of data analysis using formal
contexts and concept lattices. Formal context is defined as a triple K := (G; M; I ),
where G is a set of objects, M a set of attributes, and I a binary relation between G
and M in which gI m holds, i.e., (g; m) 2 I , reads: object g has attribute m [
Definition 1. [
A0 = fm 2 M j gIm f or all g 2 Ag
B0 = fg 2 G j gIm f or all m 2 Bg
A0 denotes the set of attributes common to the objects in A; B0 denotes the set of objects which have all the attributes in B.
A formal concept of context K is a pair (A; B) consisting of extent A 2 G and intent B 2 M such that A = B0 and B = A0. B(K) denotes the set of all formal concepts of context K. The partial order relation, namely subconcept-superconcept-relation, is defined as: (A1; B1) (A2; B2) :, A1
A2(, B1
B2)
Relation is called a hierarchical order of formal concepts. B(K) ordered in this way is exactly a complete lattice, called the concept lattice and denoted by B(K). elephant dolphin porpoise hawk octopus
For an object g 2 G, its object concept g := (fgg00; fgg0) is the smallest concept in B(K) whose extent contains g. In other words, object g can generate formal concept g. Symmetrically, for an attribute m 2 M , its attribute concept m := (fmg0; fmg00) is the greatest concept in B(K) whose intent contains m. In other words, object m can generate formal concept m. For a formal concept (A; B), its simplified extent (simplified intent), denoted by Kex (Kin), is a minimal description of the concept. Each object (attribute) in Kex ( Kin ) can generate the formal concept (A; B). As a matter of fact, Kex dose not appear in any descendant of (A; B) and Kin dose not appear in any ancestor of (A; B). Figure 1 shows the concept lattice of context Ke in Table 1, where each formal concept is labeled by its simplified extent and intent.
Galois Sub-hierarchy (GSH) introduced by [
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.
We take two anatomical ontologies, Adult Mouse Anatomy1 (MA) and the anatomy subset of National Cancer Institute Thesaurus2 (NCI), to demonstrate our method. MA is a structured controlled vocabulary describing the anatomical structure of the adult mouse, whereas NCI describes the human anatomy for the purpose of cancer research. The versions used are the OWL files of these two ontologies provided by the 2015 OAEI. For MA and NCI, the token-based and relation-based formal contexts are of large-size, resulting in complex structures of the concept lattices derived. In order to avoid generating redundant information, GSH, a polynomial-sized representation of concept lattice that preserves the most pertinent information, is utilized in FCA-Map. 3.1
Most OM systems rely on lexical matching as initiation due to the fact that classes sharing names across ontologies quite likely represent the same entity in the domain of interest. FCA-Map, rather than using lexical and linguistic analysis, generates a formal context at the lexical level and obtains mappings from the lattice derived from the context.
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 elimination3, 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, 1 http://www.informatics.jax.org/glossary/adult ma dictionary 2 https://ncit.nci.nih.gov/ncitbrowser/ 3 Although eliminating the stop words carrying logical meanings may affect the precision, its benefit in recall is more advantageous according to our experiments. or a synonym4 or lexical variation5 of m. Table 2 shows Klex of a small part of MA and NCI, and its derived concept lattice in GSH form is displayed in Figure 3. For each formal concept derived, in addition to strings in its extent, we are also interested in the classes that these strings come from, called class-origin extent. For example, in Figure 3, the class-origin extent of formal concept by node 7 is fMA:mammary gland fluid/secretion, NCI:Breast Fluid or Secretiong since in NCI, “Mammary Gland Fluids and Secretions” is a synonym of class NCI:Breast Fluid or Secretion. MA:palatine gland MA:adrenal gland zona fasciculata MA:adrenal gland zona reticularis MA:mammary gland fluid/secretion NCI:Palatine Salivary Gland NCI:Fasciculata Zone NCI:Reticularis Zone
NCI:Mammary Gland Fluids and Secretions
An essential property of FCA is the duality between a set of objects and their attributes. The more attributes demanded, the fewer objects can meet the requirements. In the case of the token-based formal concept, the more common tokens appearing in its intent, the fewer strings the extent contains, and the more possibly for the classes in class-origin extent to be matched. This is to say that cardinality of the extent can reflect how similar the strings are, thus classes from different source ontologies in a smaller-sized class-origin extent can be considered as a mapping with higher confidence. Practically, 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. Of note, on the other hand, cardinality of the intent cannot be used to measure the similarity of strings. For example, MA:nerve and NCI:Nerve, which is a match, only share one token, whereas MA:left lung respiratory bronchiole and NCI:Right Lung Respiratory Bronchiole, not a match, share three tokens.
Type I anchor. Simplified extent Kex of the formal concept contains exactly two strings from classes across ontologies. This indicates that the two strings are composed of the same or synonymous tokens, thus the corresponding classes are extracted to be a match, as exemplified by (M A : mammary gland fluid/secretion; N CI : Breast Fluid or Secretion) through formal concept of node 7 in Figure 3 whose Kex has two strings, one from MA and the other NCI.
Type II anchor. The class-origin extent of the formal concept contains exactly two classes across ontologies and simplified extent Kex contains strings from at most 4 Sub-Term Mapping Tools (https://lsg2.nlm.nih.gov/LexSysGroup/Projects/stmt/2013+/web/ index.html) are used to access synonyms. 5 SPECIALIST Lexicon (https://lexsrv3.nlm.nih.gov/LexSysGroup/Projects/lexicon/current/web/ index.html) of UMLS is used to access lexical variations. fasciculata reticularis 2 3 adrenal zona 5 gland
4 palatine
6 MA:palatine gland
fluid mammary secretion 7
Type I Type II one source ontology. Here the strings share tokens in the intent rather than composed of the same or synonymous tokens. For example, (MA:adrenal gland zona fasciculata, NCI:Fasciculata Zone) is extracted from node 2 in Figure 3, due to the common token “fasciculata” which exists solely in these two classes. And (MA:palatine gland, NCI:Palatine Salivary Gland) is identified as an anchor from node 6, due to the common tokens “palatine” and “gland” which co-exist solely in these two classes.
Structural relationships of ontologies are exploited to validate the matches obtained at
the lexical level. One of our previous studies [
tenam, tengam) tssreyangm, tsreySangm) tiissseeuodp, iissseeuodpT) ) tillrexygananm,: itlreeyagnaagnLLm) rrxyyxnanL,:)ICN )(ISA lig:(AM iL:ICN (I-)D o:(AM O:ICN ()ISB a:(AM A:ICN (ISB (AM :ICN ()PTA la:(AM
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. In the case of MA and NCI, four kinds of relationships are considered, ISA, SIBLING-WITH, PART-OF, and DISJOINT-WITH, 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. The relation-based formal context Krel of a small part of MA and NCI is displayed in Table 3. For instance, MA:periodontal ligament and NCI:Periodontium are subclasses of MA:ligament and NCI:Ligament, respectively, thus (MA:periodontal ligament, (ISA)(MA:ligament, NCI:Ligament)) 2 Irel and (NCI:Periodontium, (ISA)(MA: ligament, NCI:Ligament)) 2 Irel hold. Moreover, MA:adipose tissue is a subclass of MA:organ system whereas NCI:Adipose Tissue is disjoint with NCI:Organ System, thus (MA:adipose tissue, (I-D)(MA:organ system, NCI:Organ system)) 2 Irel and (NCI:Adipose Tissue, (I-D)(MA:organ system, NCI:Organ system)) 2 Irel hold. (I-D)(MA:organ system, NCI:Organ System)
MA:adipose tissue
NCI:Adipose Tissue
(SIB)(MA:adipose tissue, NCI:Adipose Tissue)
3 (ISA)(MA:ligament, NCI:Ligament ) MA:periodontal ligament
MA:auricular ligament 4
NCI:Periodontium
NCI:Broad Ligament (SIB)(MA:larynx ligament, NCI:Laryngeal Ligament )
MA:larynx ligament 5 NCI:Laryngeal Ligament (PAT)(MA:larynx, NCI:Larynx )
The derived concept lattice in GSH form of Krel of a small part of MA and NCI is illustrated in Figure 4. 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. Conversely, 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. For example, in the extent of node 3 in Figure 4, (MA:periodontal ligament, NCI:Periodontium) and (MA:larynx ligament, NCI:Laryngeal Ligament), two anchors acquired lexically, are positive evidences to anchor (MA:ligament, NCI:Ligament) with label “(ISA)” in the intent, and negative evidences to anchor (MA:organ system, NCI:Organ System) with label “(I-D)”. The support degree and incoherence degree of each anchor are the cardinality of its positive and negative evidence set, respectively.
Now we can utilize all the positive evidence sets P and negative evidence sets N to eliminate incorrect lexical anchors and retain the correct ones. There are two steps conducted one-by-one as follows.
Incoherence repairing. The negative evidence leads to incoherency among anchors, for which FCA-Map repairs in a greedy way, i.e., eliminating the incoherence-causing anchors iteratively until N becomes empty. At each iteration, anchor a having the least negative evidence set, i.e., the smallest incoherence degree, is selected. For every anchor a0 in N (a), if incoherence degree of a0 is greater than a, eliminate a0; otherwise, compare the support degree of a and a0, and eliminate the one with smaller support degree.
Anchor screening. Anchors having no positive structural evidence according to the updated P are either caused by the structural isolatedness of classes, or simply incorrect mismatches. FCA-Map screens anchors based on both lexical and structural evidence, where Type II anchors without positive evidence are eliminated. 3.3
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. In the case of MA and NCI, five kinds of relationships are considered, ISA, SUPERCLASS-OF, SIBLING-WITH, PART-OF, and HAS-PART, 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. Although most of the mappings extracted this way have already been identified at the lexical level, new additional matches emerge, as exemplified by (MA: hindlimb bone, NCI: Bone of the Lower Extremity). 4
To demonstrate the effectiveness of FCA-Map, evaluation is performed on two pairs of real-world ontologies, Adult Mouse Anatomy (2,744 classes) and the anatomy subset of NCI Thesaurus (3,304 classes); and the Foundational Model of Anatomy (3,696 classes) and NCI (6,488 classes), respectively, from anatomy track and large biomedical ontologies track of OAEI 2015. FCAlib6 is used to derive concept lattices (GSH) from formal contexts. It is an open-source, extensible library for FCA tool developers. FCAMap is implemented in Java and the experiments were conducted in a PC with Intel i7 (3.60GHz) and 8GB RAM. It took 166 seconds and 425 seconds, respectively, for FCA-Map to finish the MA-NCIAnat: and the FMA-NCI matching. 4.1
The results of lexical matching by FCA-Map are summarized in Table 4, and structural matching is presented in Table 5 where the upper part is about structural validation and the lower part about extra discovered structural mappings. Columns “Corr.”, “Incor.”, and “Unkn.” indicate the number of correct, incorrect, and unknown mappings, respectively, as categorized by OAEI where “unknown” mappings will neither be considered as correct nor incorrect when evaluating the alignment, but will simply be ignored.
Types of anchors Total
Type I Type II
MA-NCIAnat: Corr. Incor. P
FMA-NCI
Corr. Unkn. Incor.
One can see that most of the lexical anchors are of Type I, i.e., the name, synonym or label of one class is the same as another class. For example, MA:cortical layer II and NCI:External Granular Layer are extracted as an anchor because in MA, “external granular layer” is a synonym of MA:cortical layer II. Incorrect Type I anchors mainly come from three cases. (1) Although having the same name, classes in anchor do not represent equivalent entity. For example, MA:organ system and NCI:Organ System, although sharing matched subclasses, have respective additional different subclasses. (2) Mismatched classes may be considered to be a mapping based on their synonyms or labels. For example, anchor (MA:cerebellum lobule I, NCI:Lingula ) (through synonym “lingula” in MA) is a mismatch because the former is a part of cerebellar vermis and the latter a part of left lung. (3) Using external lexicon may introduce incorrect anchors. For example, MA:back matches NCI:Dorsum because “back” and “dorsum” are synonymous according to the lexicon used in FCA-Map. This is a mismatch because in MA back is a part of trunk, while in NCI dorsum refers to outer surface of scapula.
Type II lexical anchors have lower precisions, reflecting the unstable performance of relying on names sharing tokens to derive commonalities of classes. Nevertheless, many incorrect anchors can be eliminated in the validation process, causing the precision to increase, for instance from 47.2% to 75.4% for Type II anchors in FMA-NCI. Take Type II anchor (MA:retina ganglion cell layer, NCI: Retinal Ganglion Cell) for example. It is eliminated in incoherence repair because of its conflict with (MA:retina layer, NCI: Retina Layer), of which the support degree is 0 and 8, respectively. The structural validation based on the relation-based concept lattice in FCA-Map can ensure to improve the precision of lexical mappings. 4.2
Among many lexical matching methods such as string equality, substring test, and edit
distance, TFIDF-based methods [
1 TFIDF measures simultaneously how often the tokens appear in one class name and how much information the tokens bring across names of classes from different ontologies. We compare the performance of lexical matching of FCA-Map with TFIDF solely using the class names of MA and NCI without any external resources. The result is shown in Figure 5, where F-measure of FCA-Map is higher than TFIDF for any threshold. FMA-NCI
Compared with the TFIDF-based methods, FCA-Map emphasizes on the particular commonality of two strings, and there is no need for setting thresholds which is required in TFIDF for selecting matches. This can be illustrated by MA: tectum and NCI: tectum mesencephali. They are not matched according to TFIDF because token “mesencephali” has a high inverse-document-frequency (it solely appears in this string) and token “tectum” is ignored (it solely appears in the two strings). On the other hand, this correspondence can be derived in our method since there is a formal concept with intent f“tectum”g and extent exactly containing these two strings. Moreover, our method can avoid the mistake of locally measuring frequency of tokens. For instance, MA: common iliac artery and NCI: Right Common Iliac Artery have a relatively high similarity (0.86) according to TFIDF, while this pair is not extracted by FCA-Map. There are many other class names share tokens “common”, “iliac”, and “artery”, such as MA: Left Common Iliac Artery and NCI: Right Common Iliac Artery Branch, therefore what the two strings in comparison share are not unique enough for them to be chosen as a match. Indeed, our method features in detecting the particular commonality solely belongs to the names compared while ignoring the commonality shared by many other names. 4.3
A comparison between FCA-Map and OAEI 2015 top-ranked systems is shown in Table 6. For MA-NCIAnat:, the precision, recall and F-measure of FCA-Map ranks second, fifth, and forth, respectively. Results of FMA-NCI are encouraging, with both recall and F-measure tie for first. Moreover, FCA-Map is capable of extracting mappings that cannot be identified by other systems, as exemplified by Type II anchors (MA:adrenal gland zona reticularis, NCI:Reticularis Zone), (MA:ileocaecal junction, NCI:Ileocecal Valve). These mappings are identified in the token-based concept lattice and validated in the relation-based concept lattice. 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, whereas its performance can be relatively poor for general-purpose ontologies whose terminologies are more varied and ambiguous, like those in the conference track of OAEI where FCA-Map ranked at the average level. Additionally, for negative evidence to be identified, our method requires that at least one source ontology declares disjointedness relationships between classes.
Systems
P MA-NCIAnat:
R
F
P
FMA-NCI
R
F Discovering complex mappings structurally. As shown in Table 5, structural mappings identified by the positive relation-based concept lattice are limited. Nevertheless, in the lattice we noticed that the simplified extents of some formal concepts contain more than two classes from different source ontologies, meaning these classes share the same structural relationships to anchors in the intent. Such classes may compose a complex mapping, as elaborated in the following. 1. One-to-group mappings. The simplified extent contains only one class from one source ontology and multiple classes from the other source ontology. For example, MA:inferior suprarenal vein can be mapped to the group of concepts fNCI:Left Suprarenal Vein, NCI:Right Suprarenal Veing as the three concepts are contained within one simplified extent that has no more classes. This one-to-group mapping comes from the difference in granularity between MA and NCI. 2. Group-to-group mappings. The simplified extent contains multiple classes from different source ontologies, respectively. For example, two groups of concepts fMA: sacral vertebra 1, MA:sacral vertebra 2, MA:sacral vertebra 3, MA:sacral vertebra 4g and fNCI:S1 Vertebra, NCI:S2 Vertebra, NCI:S3 Vertebra, NCI:S4 Vertebra, NCI:S5 Vertebrag can be mapped as these classes are contained in one simplified extent that has no more classes. This group-to-group mapping represents the difference between mouse and human anatomy.
Compared with other FCA-based OM systems, the study in this paper is more comprehensive as an attempt to push the envelope of the Formal Concept Analysis formalism in ontology matching tasks. Three types of formal contexts are constructed oneby-one, and their derived concept lattices are used to cluster the commonalities among classes at lexical and structural level, respectively. Experiments on large, real-world domain ontologies show promising results and reveal the power of FCA. Our 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.