In ontology alignment, there is no single best performing matching algorithm for every matching problem. Thus, most modern matching systems combine several base matchers and aggregate their results into a nal alignment. This combination is often based on simple voting or averaging, or uses existing matching problems for learning a combination policy in a supervised setting. In this paper, we present the COMMAND matching system, an unsupervised method for combining base matchers, which uses anomaly detection to produce an alignment from the results delivered by several base matchers. The basic idea of our approach is that in a large set of potential mapping candidates, the scarce actual mappings should be visible as anomalies against the majority of non-mappings. The approach is evaluated on di erent OAEI datasets and shows a competitive performance with state-of-the-art systems.
In ontology matching, there is only rarely a one size ts all solution. Ontology
matching problems di er along many dimensions, so that a matching system
that performs well on one dataset does not necessarily deliver good results on
another one. To overcome this problem, many ontology matching tools combine
the results of various base matchers, i.e., individual matching strategies.
However, this approach gives way to a new problem, i.e., how to combine the results
of the base matchers in a way that the combination suits the problem at hand [
In this paper, we propose to use anomaly or outlier detection for the
problem of matcher combination. Anomaly detection is the task of nding those data
points in a data set that deviate from the majority of the data [
First, all base matchers that are based on local information of each ontology entity are executed. The entities of the target and source ontology are matched in a pair-wise fashion. This step matches Classes, DataProperties and ObjectProperties pairwise and independently.
After this the rst feature vector is analyzed and an uncorrelated feature subset is extracted. The results of those uncorrelated matchers are used as the input similarities for the structural matchers.
The result of the structural matchers is joined with the element level matcher result to create a feature vector. Since some of the features might be redundant or not vary in their values and thus do not contribute to the nal matching, we remove results with little variation, correlated results, and also support PCA for computing meaningful linear combinations of base matcher results.
The current version of COMMAND implements a large variety of element and structure level techniques. Those encompass 16 string similarity metrics, ve external metrics based on WordNet and corpus linguistics, and ve structural matching techniques, such as similarity ooding. 2.2
The next step is the aggregation of the base matcher results into a nal matching score for all correspondences. We perform this step by detecting outlying datapoints in the feature vector space, and using this score as a measure of similarity. The anomaly analysis and score normalization are performed separately for classes, data properties, and object properties.
To compute outlier scores, we apply anomaly analysis techniques on the
feature vector representations. In this paper, we use three di erent techniques: A
k-nearest-neighbor based method (KNN) that computes the anomaly score of a
data point based on the average euclidean distances2 to its nearest neighbors, a
cluster-based method that calculates the unweighted cluster-based local anomaly
factor (CBLOF) based on a given clustering scheme produced by an arbitrary
clustering algorithm [
To evaluate the COMMAND approach, we use the benchmark, conference, and
anatomy of the Ontology Alignment Evaluation Initiative (OAEI) 2014 [
We compare the results of COMMAND to three baselines. Single best global refers to the single base matcher that performs best on the given test case (i.e., conference, benchmark, and anatomy), using the optimal global threshold. Majority vote performs a voting across all base matchers, again using the best global threshold. Single best local selects the best base matcher for each problem.3
Furthermore, we compare COMMAND to the contestants of the OAEI 2014 initiative. To make that comparison fair, we use one global parameter set for each variant across all three OAEI datasets, instead of per dataset settings.
Tables 1, 2, and 3 depict the results of COMMAND on the OEAI datasets, once with and once without the use of ALCOMO. For anatomy, we restrict ourselves to the CBLOF variant and a subset of eight element-level matchers due to reasons of runtime. Except for the Single best local baseline (which is informative and not a baseline that can actually be implemented), COMMAND outperforms all baselines. When comparing COMMAND to the results of OAEI 3 Note that in practice, it would not be possible to implement a matcher like Single best local. We only report it for informative purposes. 2014, we can nd that the system, using CBLOF and PCA, and alignment repair with ALCOMO, would score on rank on a shared fth rank (with XMap2) for the benchmark track, on rank four for the conference track (between LogMapC and XMap), and on rank six (between LogMap-C and MaasMatch) for the anatomy track.
The runtime of COMMAND is assessed by measuring the time of a complete end-to-end pipeline execution. The general time complexity of COMMAND is quadratic to the size of the input ontologies. Additionally, the time consumption of the individual steps is measured. The results are depicted in table 4. 4
In this paper, we have introduced a novel approach using anomaly detection for combining the results of di erent ontology matchers into a nal aggregated matching score.
Overall, COMMAND performs an e cient matcher selection that only considers matchers that contribute to the nal result, and uses anomaly detection as an unsupervised method for aggregating base matcher results. It is superior total t vector creation t aggregation t extraction to a simple majority vote baseline and performs in the range of state of the art matching tools. Furthermore, the possibility to use principal component analysis for feature space transformation also allows for implicitly computing relevant linear combinations of matcher scores.
The evaluation has been carried out on three OAEI datasets. For conference and benchmarks, the system achieved competitive performances in comparison to other OAEI participants. The results on the anatomy track showed that, since only a reduced con guration could be used with sub-optimal results, that more memory-e cient implementations are still required for fully exploiting the capabilities of COMMAND.
Furthermore future work will include the inclusion of other anomaly detection approaches, like angle-based methods, as well as other score normalization methods.