=Paper=
{{Paper
|id=None
|storemode=property
|title=Towards
Rule Learning Approaches to Instance-based Ontology Matching
|pdfUrl=https://ceur-ws.org/Vol-868/paper2.pdf
|volume=Vol-868
|dblpUrl=https://dblp.org/rec/conf/esws/JanssenFNP12
}}
==Towards
Rule Learning Approaches to Instance-based Ontology Matching==
https://ceur-ws.org/Vol-868/paper2.pdf
Towards Rule Learning Approaches
to Instance-based Ontology Matching
Frederik Janssen1 , Faraz Fallahi2
Jan Noessner3 , and Heiko Paulheim1
1
Knowledge Engineering Group,
TU Darmstadt, Hochschulstrasse 10, 64289 Darmstadt, Germany
{janssen,paulheim}@ke.tu-darmstadt.de
2
ontoprise GmbH,
An der Raumfabrik 29, 76227 Karlsruhe, Germany
fallahi@ontoprise.de
3
KR & KM Research Group
University of Mannheim, B6 26, 68159 Mannheim, Germany
jan@informatik.uni-mannheim.de
Abstract. Ontology matching approaches have mostly worked on the
schema level so far. With the advent of Linked Open Data and the avail-
ability of a massive amount of instance information, instance-based ap-
proaches become possible. This position paper discusses approaches and
challenges for using those instances as input for machine learning algo-
rithms, with a focus on rule learning algorithms, as a means for ontology
matching.
1 Introduction
Today, data integration results produced by various developed automated algo-
rithms and systems are still error-prone. Therefore, the field of data integration
is a major challenge of modern information technology and of significance to
various research areas. Ontologies can play a key role in resolving semantic het-
erogeneity by providing a formal description of a domain.
Not only since the advent of Linked Open Data, ontology mappings have
become an essential ingredient to ensure the interoperability of data sets using
different ontologies. While Linked Open Data is much concerned about the link-
ing of instances, mappings on the schema level, e.g. for federating queries across
different data sets, are currently under-represented. At the same time, the vast
amount of instance data in Linked Open Data allows for developing powerful
instance-based approaches to ontology matching to complement the currently
predominant schema-level approaches.
Utilizing matching algorithms with lexical distance measure and pattern
recognition techniques for automatically finding mappings between ontologies do
not always yield the expected results. Where lexical distance measure algorithms
fail, machine learning algorithms which are based on symbolic representations
can serve as a remedy, at least to some extent.
2 Janssen et al.
In the last years, a major research focus has been set on schema based so-
lutions. Hence, a variety of state-of-the-art algorithms for alignment have been
developed, which work mostly on traversing schemas and their structure, and
only a few approaches explicitly use data about instances [1, 2]. In the scope of
the MappingAssistant project [4], instance data has been utilized to repair and
refine existing ontology alignments.
In this paper, we discuss two possible approaches for employing machine
learning for instance-based ontology matching. The basic idea of both of them is
to use rule learning to solve this problem. The main advantage of rule learning
is its symbolic character, i.e., rules can be interpreted and compared to each
other. In a first case study, we use association rule learners on the instance level
to discover mappings. A second case study shows how separate-and-conquer rule
learners can be employed to further refine mappings. Both case studies aim at
demonstrating the ideas and exploring possible challenges.
2 Case Study 1 – Creating Mappings by Rule Learning
In this case study, we focus on cases where a set of instances is contained
in different data sets – either identified by identical URIs or connected via
owl:sameAs statements. While this is rather frequent in Linked Open Data,
the OAEI datasets typically do not contain shared instances. Therefore, we have
created our own dataset, using an excerpt from DBpedia. As DBpedia uses its
own ontology as well as YAGO for classification, it provides an instance set using
different ontologies, which can be used as a benchmark for instance-based ontol-
ogy matching. To construct our dataset, we used an existing, publicly available
partial 1:1 mapping4 between the DBpedia and the YAGO ontology as a starting
point. The dataset contains 169 simple mappings between DBpedia and YAGO.
For that dataset, we retrieved all instances that contain at least one of the types
in the mapping. That data set has a total of 231,635 instances.
We use association rule mining to discover ontologies, as suggested by [6].
Association rules are used, e.g., to discover sets of items that are likely to be
bought together, in order to build recommender algorithms. Likewise, we use
them to find out which classes (and other ontology constructs) frequently co-
occur, and derive mappings from those co-occurences.
The portions of the two ontologies under consideration are essentially differ-
ent. For example, the YAGO ontology relies mainly on a rich classification and
contains very special classes such as yago:IndustrialRockMusicGroups, while
the DBpedia relies on relations to describe such classes, e.g., as a DBpedia-owl:
Band with a value of DBpedia:IndustrialRock for DBpedia-owl:genre5 . Thus,
the mapping between the two ontologies can only be expressed by a complex one:
yago:IndustrialRockMusicGroups
≡ DBpedia-owl:Band u ∃DBpedia-owl:genre. {DBpedia:IndustrialRock}
4
http://www.netestate.de/De/Loesungen/DBpedia-YAGO-Ontology-Matching
5
See http://DBpedia.org/resource/Nine_Inch_Nails for this example.
Towards Rule Learning Approaches to Instance-based Ontology Matching 3
100 1
90 0.9
80 0.8
number of mapping rules
70 0.7
60 0.6
precision
50 0.5 precision
40 0.4 # of rules
30 0.3
20 0.2
10 0.1
0 0
>=95 >=90 >=85 >=80
Minimum confidence threshold
Fig. 1. Matching results for complex mappings
In a first experiment, we tried to infer the simple 1:1 mappings. Using the
feature generation toolkit FeGeLOD [5], we added a boolean feature for each
rdf:type property for all the instances in our data set, ending up with a total of
98,414 features. On this data set, we used an association rule mining algorithm
to find rules expressing frequent co-occurring rdf:type statements, i.e., two
classes in different ontologies that share many instances. For example, from two
symmetrically occurring rules, we conclude a mapping as follows:
DBpedia-owl:ProtectedArea ← yago:Park
yago:Park ← DBpedia-owl:ProtectedArea
⇒ DBpedia-owl:ProtectedArea ≡ yago:Park
As discussed in [5], an F-Measure of up to 25% can be achieved with this naive
approach. While this is not as much as state-of-the-art approaches, the mappings
found are often hard to find with conventional approaches, as the above example
shows.
In a second experiment, we tried to infer complex mappings between two
classes. To that end, we have created a second dataset which comprises not only
the type information as in the first case, but also boolean properties indicating
whether there is an incoming or outgoing relation of a certain type. The result-
ing data set has 117,029 features. From that dataset, we were able to discover
complex mappings, such as
≥ 1DBpedia-owl:name v yago:Person
Since there is, to the best of our knowledge, no gold standard for complex map-
pings, we have evaluated our approach by counting the number of rules found,
and manually determining the rules that are correct. The results are depicted in
Fig. 1 for different thresholds. The experiments show that it is possible to employ
association rule learning for discovering ontology mappings. Typical challenges
include scalability to larger datasets, learning more expressive rules, and evalu-
ation of complex mappings.
4 Janssen et al.
dataset from ontology O1 dataset from ontology O2
@relation car @relation cars
@attribute acceleration {low,medium,high} @attribute acceleration {low,medium,high}
@attribute cargoCapacityRating {low,high} @attribute cargoCapacity {low,high}
@attribute passengerSpaceRating {low,high} @attribute passengerSpace {low,high}
@attribute convenienceRating {low,medium,high} @attribute convenience {low,medium,high}
@attribute milesPerGallon {low,medium,high} @attribute numberOfExtras {low,medium,high}
@attribute mpg {low,medium,high}
@data @data
high,low,high,medium,low high,low,high,medium,medium,low
high,low,low,high,medium high,low,low,low,high,high
low,low,high,high,low low,low,high,high,high,low
low,low,low,low,medium low,low,low,high,medium,low
medium,high,high,low,low low,high,high,high,low,medium
medium,high,low,high,medium medium,high,high,high,high,medium
low,high,high,medium,high low,high,high,medium,low,high
... ...
Figure 1: A 4 class classification problem
Fig. 2. Excerpt of the input for the separate-and-conquer approach
3 Case Study 2 – Extending Mappings by Rule Learning
In the second case study, our goal is to use classification rule learning to find
non-trivial alignments between ontologies, which cannot be found through con-
ventional schema-based matching techniques. We focus on finding additional
property alignments, assuming that some alignments between properties defined
in two ontologies O1 and O2 are given as an initial mapping, as indicated by the
arrows in Fig. 2. Note that in that example, the property numberOfExtras that
is present in O2 is missing in O1 .
The goal is to detect additional property alignments between O1 and O2 . In
the example, the alignment still left to detect is milesPerGallon ≡ mpg.
For each unmapped property, we construct a dataset as input for a rule
learner. The datasets are created by including all the instances available from
the A-boxes of the two ontologies, and using the unmapped property as a
class attribute. In Fig. 2, three classification problems would be created: us-
ing milesPerGallon as the target class in the data set for O1 , and using
numberOfExtras and mpg as the target class in the data set for O2 .
In our example, we learn rule sets for each non-aligned property q1 and
q2 , using a CN2-like rule learner. While for the illustration of the approach
the actual learning algorithm is not that important (given that the output are
rules), certainly the performance of the approach is strongly related to the used
algorithm (cf. the discussion in Section 4). In the end, the rule learner outputs
three rule sets, one for each non-aligned property, e.g., one ruleset R1 for the
property milesPerGalllon of O1 , and two rulesets (R2 and R3 ) for the two
properties that reside unmapped in O2 (numberOfExtras and mpg). The key
idea of the approach is to compare the rules found on the instances of the two
ontologies: if two rules comprise attribute-value tests for properties that are
previously mapped, the consequence is that the target properties (the prediction
Towards Rule Learning Approaches to Instance-based Ontology Matching 5
of the rules) then can be also mapped, because their characteristics are similar
to a certain extent.
To illustrate such a mapping, in the following examples for similar and
different rules are shown. The best case is that the rules are identical: r1,1 :
milesPerGallon=medium←convenienceRating=high ∧ acceleration=high.
r2,1 : mpg=medium← convenience=high ∧ acceleration=high. where ri,j stands for
the j-th rule of rule set i. Rule r1,1 tests whether the convenienceRating is high
and the acceleration is high. Due to the predefined mappings, it can be con-
cluded that both rules use the same properties with the same values and hence
are similar (with confidence 1.0). Note that all numerical values of all properties
are discretized in a preprocessing step for simplification issues. Therefore, rules
that are exactly similar may not be so rare. Nevertheless, rules that are found
on real world data may not be identical. An example for such different rules is
given below.
r1,3 : milesPerGallon=high← acceleration=medium ∧ cargoCapacityRating=low.
r3,3 : numberOfExtras=high← convenience=high ∧ passengerSpace=high.
In that case, the rules are completely dissimilar. Thus, a similarity measure
simr (r, r0 ) for a pair of rules r and r0 is needed. This similarity of individual
rules is used then to compute the similarity of the whole rule sets simR (R, R0 ).
A naive choice to define the similarity of two rule sets could look as follows:
P
(tp(r1,i )+tp(r2,j ))/2
0 simr (r1,i ,r2,j )≥θ
simR (R, R ) = (|D1 |+|D2 |)/2
(1)
where |Di | is the total number of examples in dataset Di , tp(r) yields the number
of true positive examples covered by rule r (i.e., the examples that are correctly
covered by the rule r), and θ is a threshold that decides whether the rules are
equal or not. The similarity of single rules can naively be defined by
(
1 if r matches r0 exactly
simr (r, r0 ) = (2)
0 otherwise
Clearly, in real world situations these definitions are too restrictive. Nevertheless,
despite their simplicity, first experiments show that they are sufficient. These
preliminary experiments with two ontologies containing a few instances show
that the approach works. The two rule sets R1 (rules for milesPerGalllon)
and R3 (rules for mpg) were identical. In contrast, the rule sets learned for
numberOfExtras and milesPerGallon are completely different, since these are
different properties. Thus, the overall similarity value for numberOfExtras and
milesPerGallon is significantly lower than for mpg and milesPerGallon. There-
fore, in the end, the mapping milesPerGallon ≡ mpg was found while number-
OfExtras is left unmapped.
The case study shows that rule learning can be used to derive additional
mappings from those already found. Open challenges include the definition of
metrics for rule comparison, the use of suitable rule learning heuristics [3], and
the decomposition of the ontology matching problem into a binary classification
problem.
6 Janssen et al.
4 Conclusion and Challenges
In this paper, we have discussed approaches of learning and refining non-trivial
ontology alignments from instances through utilization of inductive rule learn-
ing algorithms. We have shown two case studies which examine how finding
and refining ontology mappings can be reformulated as problems of association
rule mining and separate-and-conquer rule learning, respectively. While the case
studies show the feasibility of employing rule learning algorithms for ontology
matching, there are quite a few open research issues and challenges.
The first case study has shown an approach which is especially suitable for
discovering complex mappings. Suitable benchmark datasets for complex map-
pings do not exist at the moment. Generating those benchmark sets from Linked
Open Data is a suitable option, which at the same time produces new scalability
challenges. When dealing with instance-based matching, using a reasoner in the
loop is also an interesting opportunity for refining mappings. Necessary prepro-
cessing steps, e.g., for dealing with numerical data properties, are also a subject
of future research.
The second case study has used the similarity of rule sets as a means of
assessing validity of ontology mappings. Finding suitable similarity measures of
rule sets is a challenge for future work. It may also be a valid direction to use other
learning models (e.g. subgroup discovery, or even decision trees) and suitable
heuristics, which may allow different and maybe better means for comparison.
Although those challenges are non-trivial and require further deep investi-
gations, we are confident that rule learning is suitable means to instance-based
ontology matching. Thus, we are confident that the approaches sketched in this
paper will lead to the development of high-performance matching algorithms.
References
1. M. Ehrig and Y. Sure. Ontology Mapping - An Integrated Approach. In C. Bussler,
J. Davis, D. Fensel, and R. Studer, editors, Proceedings of the 1st European Seman-
tic Web Symposium, volume 3053, pages 76–91, Heraklion, Greece, 2004. Springer
Verlag.
2. J. Huber, T. Sztyler, J. Nößner, and C. Meilicke. CODI: Combinatorial Optimization
for Data Integration: Results for OAEI 2011. In Proceedings of the 6th International
Workshop on Ontology Matching, Bonn, Germany, October 2011.
3. F. Janssen and J. Fürnkranz. On the Quest for Optimal Rule Learning Heuristics.
Machine Learning, 78(3):343–379, March 2010. DOI 10.1007/s10994-009-5162-2.
4. J. Noessner, F. Fallahi, , E. Kiss, and H. Stuckenschmidt. Interactive data integra-
tion with mappingassistant. In Demo Proceedings of the 10th International Semantic
Web Conference (ISWC), Bonn, Germany, October 2011.
5. H. Paulheim and J. Fürnkranz. Unsupervised Feature Generation from Linked Open
Data. In 2nd International Conference on Web Intelligence, Mining, and Semantics,
2012. to appear.
6. J. Völker and M. Niepert. Statistical Schema Induction. In Proceedings of the
8th Extended Semantic Web Conference: Linked Open Data Track, pages 124–138,
Berlin, Heidelberg, 2011. Springer-Verlag.