The paper presents an overview of a novel procedure for mapping hierarchical ontologies, populated with properly classified text documents. It combines structural and instance-based approaches to reduce the terminological and conceptual ontology heterogeneity. It yields important granularity and instantiation judgments about the inputs and is to be applied to mapping web-directories.
document is represented as a TF/IDF vector [
An entity which plays a key role in our approach is the intersection of DO1 and
DO2 . However, when the sets elements are vectors of text documents, it is very
likely that the sets contain documents which are similar, but not identical, and
therefore not part of the intersection. In order to make use of such documents, we
introduce the notion of relaxed intersection (RI) which integrates both identical
and similar documents from both sets as opposed to the standard strict set
intersection (Figure 1(b)): RI(DO1 , DO2) = {diO1 , djO2 |dist(diO1 , djO2 ) ≤ cd, diO1 ∈
DO1 , djO2 ∈ DO2 }, where dist is a properly chosen distance measure on the set of
TF/IDF documents [
Structural and Instance-based Mapping Strategies
In the following, we will describe the structural approach which forms the first
part of our mapping strategy. A hierarchical ontology as described in definition
1 is directly translated to a directed rooted tree G(V, E). Since only hyponimic
relations are allowed at this stage, we will assume that the ontology graphs are
unlabeled. Bunke et al. [
The abbreviation mcs stands for maximal common subgraph of G1 and G2
defined as a maximal graph isomorphic to sub-graphs of both G1 and G2 and |G|
denotes the number of vertices in a graph G. The problem of finding a mcs is
solved in polynomial time for trees. Various algorithms are discussed in [
In addition to the structural approach, we employ two extensional
methods for deriving concepts similarity assertions. Even though independent from
one another, they can be combined yielding an improved similarity learner. In
both approaches, we make use of Support Vector Machines (SVMs) [
One convenient way of making use of extensional information is to model
concepts as ”bags” of instances and measure their similarity on set theoretic
accounts considering A and B very similar when A∩B ≈ A. A standard
instancebased similarity measure is the Jaccard coefficient [
The second extensional indicator for semantic closeness we propose is based
on a variable selection procedure for SVMs. Variable selection in
descriptive statistics is about pointing out the input variables, which most strongly
affect the response. For a given data set of the type SO1 it indicates which of
the TF/IDF vector dimensions are most important for the separation of the
documents into such that belong to a given concept and such that do not. Our
variable selection criterion is the sensitivity of the VC dimension [
A Procedure for Ontology Mapping
The structural and extensional approaches described so far are our instruments
used to build a combined procedure for ontology mapping. Another important
criterion for concept similarity is the presence of similar concept names in both
ontologies. Linguistic analysis approaches to this problem, relying on names and
textual description of ontology elements, are used in [
Let us take as input again the ontologies O1 and O2 together with their corresponding document sets DO1 and DO2. In the following, we describe our method for combining the mapping approaches earlier.
Case 1: |DO1 | ≈ |DO2 |
The first big case considers ontologies which contain similar number of documents. The ratio rΔ = ||DDOO11 ∩∪DDOO22 || is an indicator of the size of the intersection of both sets relative to the sets size. There are two further possibilities: - Case 1.1. rΔ > crΔ , where crΔ ∈ (0, 1) is a parameter to be fixed. In this case we have two different ontologies on (almost) the same documents sets. It is very likely that they share a conceptual similarity. We proceed to checking the graph distance between them.
- Case 1.1.a. d(GO1 , GO2 ) ≈ 0. The taxonomies have similar structures, describe the same domain and have the same extensions. It is left to establish the precise concept-to-concept mappings, done by the help of the instance based similarity check.
- Case 1.1.b. d(GO1 , GO2 ) ≈ 1. The maximal common subgraph of both ontologies is quite small, i.e. one of the taxonomies contains significantly lower number of nodes compared to the other (Figure 2(a)). Let us assume that |CO1 | < |CO2 |. Since both ontologies are ”built” on approximately the same sets of documents, this means that O2 is more specific than O1, and contains more concept nodes. O1 can be directly injected into O2. The concept-to-concept correspondences indicating the exact injection pattern are provided by instancebased concept similarity applied on the set of the nodes of the mcs of both taxonomies.
- Case 1.2. rΔ ≤ crΔ. The ontologies are little likely to be similar since their extensions share very little (or no) overlap. Case 2: |DO1 | < |DO2 |
In the second big case, the set DO1 contains less documents than the set DO2 (conventional choice). One can distinguish between three further sub-cases: Case 2.1. - the two sets do not intersect (rΔ = 0); Case 2.2. - the two sets intersect, but do not fully overlap; and Case 2.3. - the smaller set is a subset of the bigger one. Case 2.1. is in conflict with a major assumption introduced in the beginning and therefore does not provide mapping candidates. Case 2.2. conforms with either Case 2.1. or Case 2.3., depending on the size of the intersection DO1 ∩ DO2 relative to |DO1 |. We will study in details Case 2.3. and proceed to measure the structural similarity between the inputs.
- Case 2.3.a. d(GO1 , GO2 ) ≈ 0. O1 is structurally very similar to O2. Hence, it is just as specific as O2, but less populated with documents. This indicates that O1 can be replaced entirely by O2.
- Case 2.3.b. d(GO1 , GO2 ) ≈ 1. There are two different scenarios, depending on which of the two input ontologies contains more nodes.
1) |CO1 | < |CO2 |, i.e. there are less concepts in O1 than in O2. This is the case when O1 is a sub-taxonomy of O2 and can be entirely injected into it, as described in Case 1.1.
2) |CO2 | < |CO1 |. O1 is more granular a hierarchy, but less populated than O2 (Figure 2(b)). We will take instances from O2 and assign them to O1 by first aligning the nodes of both ontologies by the help of the instance-based mapping procedure. to another in terms of both conceptualization and instantiation.