Ontology matching approaches have mostly worked on the schema level so far. With the advent of Linked Open Data and the availability of a massive amount of instance information, instance-based approaches become possible. This position paper discusses approaches and challenges for using those instances as input for machine learning algorithms, with a focus on rule learning algorithms, as a means for ontology matching.
Today, data integration results produced by various developed automated algorithms and systems are still error-prone. Therefore, the eld of data integration is a major challenge of modern information technology and of signi cance to various research areas. Ontologies can play a key role in resolving semantic heterogeneity 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 di erent ontologies. While Linked Open Data is much concerned about the linking of instances, mappings on the schema level, e.g. for federating queries across di erent 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 nding 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.
In the last years, a major research focus has been set on schema based
solutions. 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 [
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 rst 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 re ne 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 di erent data sets { either identi ed 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 classi cation, it provides an instance set using di erent ontologies, which can be used as a benchmark for instance-based ontology 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 [
The portions of the two ontologies under consideration are essentially di erent. For example, the YAGO ontology relies mainly on a rich classi cation 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 9DBpedia-owl:genre: fDBpedia:IndustrialRockg 4 http://www.netestate.de/De/Loesungen/DBpedia-YAGO-Ontology-Matching 5 See http://DBpedia.org/resource/Nine_Inch_Nails for this example. 0 >=95 >=90 >=85 Minimum confidence threshold
In a rst experiment, we tried to infer the simple 1:1 mappings. Using the
feature generation toolkit FeGeLOD [
DBpedia-owl:ProtectedArea
yago:Park
DBpedia-owl:ProtectedArea
yago:Park
DBpedia-owl:ProtectedArea
yago:Park
As discussed in [
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 rst case, but also boolean properties indicating whether there is an incoming or outgoing relation of a certain type. The resulting 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 mappings, 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 di erent 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 evaluation of complex mappings.
dataset from ontology O1 @data high,low,high,medium,low high,low,low,high,medium low,low,high,high,low low,low,low,low,medium medium,high,high,low,low medium,high,low,high,medium low,high,high,medium,high ...
dataset from ontology O2 @relation cars @attribute acceleration {low,medium,high} @attribute cargoCapacity {low,high} @attribute passengerSpace {low,high} @attribute convenience {low,medium,high} @attribute numberOfExtras {low,medium,high} @attribute mpg {low,medium,high} @data high,low,high,medium,medium,low high,low,low,low,high,high low,low,high,high,high,low low,low,low,high,medium,low low,high,high,high,low,medium medium,high,high,high,high,medium low,high,high,medium,low,high ... In the second case study, our goal is to use classi cation rule learning to nd non-trivial alignments between ontologies, which cannot be found through conventional schema-based matching techniques. We focus on nding additional property alignments, assuming that some alignments between properties de ned 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 classi cation problems would be created: using 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 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 di erent 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 prede ned mappings, it can be concluded that both rules use the same properties with the same values and hence are similar (with con dence 1:0). Note that all numerical values of all properties are discretized in a preprocessing step for simpli cation 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 di erent 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 de ne the similarity of two rule sets could look as follows: simR(R; R0) =
Psimr(r1;i;r2;j) (jD1j+jD2j)=2 (tp(r1;i)+tp(r2;j))=2 where jDij 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 de ned by simr(r; r0) = (1 if r matches r0 exactly 0 otherwise (1) (2) Clearly, in real world situations these de nitions are too restrictive. Nevertheless, despite their simplicity, rst experiments show that they are su cient. 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 di erent, since these are di erent properties. Thus, the overall similarity value for numberOfExtras and milesPerGallon is signi cantly lower than for mpg and milesPerGallon. Therefore, in the end, the mapping milesPerGallon mpg was found while numberOfExtras 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 de nition of
metrics for rule comparison, the use of suitable rule learning heuristics [
Janssen et al.
Conclusion and Challenges In this paper, we have discussed approaches of learning and re ning non-trivial ontology alignments from instances through utilization of inductive rule learning algorithms. We have shown two case studies which examine how nding and re ning 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 rst case study has shown an approach which is especially suitable for discovering complex mappings. Suitable benchmark datasets for complex mappings 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 re ning mappings. Necessary preprocessing 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 di erent and maybe better means for comparison.
Although those challenges are non-trivial and require further deep investigations, we are con dent that rule learning is suitable means to instance-based ontology matching. Thus, we are con dent that the approaches sketched in this paper will lead to the development of high-performance matching algorithms.