Several metrics have been proposed for recognition of relationships between elements of two Ontologies. Many of these methods select a number of such metrics and combine them to extract existing mappings. In this article, we present a method for selection of more effective metrics based on data mining techniques. Furthermore, by having a set of metrics, we suggest a data-mining-like means for combining them into a better ontology alignment.
Ontology Alignment is an essential tool in semantic web to
overcome heterogeneity of data, which is an integral attribute
of web. In [
In this paper, given several similarity metrics we are trying to determine which of them is best for a particular data set, using data mining techniques. In order to do that, we train our techniques on some mappings for which we have a gold standard alignment, determining which metric is the best predictor of the correct alignment. We consider such metrics to be the best, and calculate Compound Similarity using them.
The rest of this article is organized as follows. In section 2, a review of related works in evaluation of existing methods and calculation of compound similarity are given. Section 3 reports our proposed method. In section 4 an example of applying this method is shown. Finally in section 5, discusses on its advantages and disadvantages are explained. 2
Works on metric evaluation as well as a method for aggregating results of different metrics is introduced in this section. 2.1
Many of the algorithms and articles in Ontology Alignment
context uses Precision and Recall or their harmonic mean,
referred to as F-Measure, to evaluate the performance of a
method [
In [
The work closest to ours is probably that of Marc Ehrig et
al. [
We first proposed a method to select appropriate metrics
among existing set, and then introduce a method to
combine them as a compound similarity. To use Precision, Recall,
F-measure and Accuracy for metrics evaluation, it is needed
to do mapping extraction. It depends on the definition of
a Threshold value and the approach for extracting as well
as on some defined constraints. Such dependencies results in
in-appropriateness of current evaluation methods, although
methods like what defines in [
In our algorithm, selection of appropriate metrics and aggregation of them are done based on Data Mining Techniques. 3.1.1
For a pair of Ontologies a table is created with rows showing comparison of an entity from first ontology to an entity from the second one. For each metric under consideration a column is created in such a table with values showing normalized metric value for the pair of entities. An additional column with true or false values shows the existence of actual mapping between the two entities is also considered.
One table is created for each pair of Ontologies in the training set. Then all of such tables are aggregated in a single table. In this table, the column representing actual mapping value between a pair of entities is considered as target variable and the rest of columns are predictors. The problem now is a typical data mining problem and so we can apply classic data mining techniques to solve it. Fig. 1 shows the process. In this figure Real Results part shows the real mappings among entities of ontologies which are required during learning phase, and the Sensitivity Analysis Rectangle shows the results which are gain after sensitivity analysis, showing the appropriateness of metrics on the given train set. 3.1.2
In what following, we analysis the problem using Neural
Networks as well as CART 2 and C5.0 decision tress[
Neural Networks: Sensitivity Analysis for any problem is applied after a model has been constructed. With varying the values of input variables in the acceptable interval, the output variation is measured. With the interpretation of the output variation it is possible to recognize most influential input variable. After giving average value for each input variable to the model and measuring the output of the model, Sensitivity Analysis for each variable is done separately. To do this, the values of all variables except one in consideration are kept constant (their average value) and the model’s response for minimum and maximum values of the variable in consideration are calculated. This process is repeated for all variables and then the variables with higher influence on variance of output are selected as most influential variables. For our problem it means that the metric having most variation on output during analysis is the most important metric.
Decision Trees: After creating the root node, in each iteration of the algorithm, a node is added to the decision tree. This process is repeated until the expansion of the tree is not possible anymore considering some predefined constraints. Selection of a variable as next node in the tree is done based on information theory concepts – in each repetition a variable with higher influence is selected among candidates. Therefore as a node is more near to the root, its corresponding variable has higher influence on the value of target variable. Hence from the constructed decision tree, it is possible to say that the metric in the root node has the highest influence. 3.1.3
According to the results, and considering step 3-1, the
problem is reduced to a Data Mining problem with the goal of
finding an algorithm to compute target variable based on the
predictor variables. In the Data Mining area several solutions
have been proposed for these kind of problems. Among
existing Data Mining solutions, we can refer to CART and C5.0
[
Similar to the evaluation method, a table is constructed. As before, columns are the values selected metrics and an additional column records the target variable (0 or 1) showing the existence of a mapping between two entities. Now having such training samples a Neural Network Model is built. It is like a combined metric from the selected metrics which can be used as a new metric for the extraction phase. 2 Classification And Regression Trees
To simplify the problem only String Based similarity metrics
are considered. For the initial set of metrics we consider
following metrics: the Levenshtein distance [
Each comparison of two strings is assigned a similarity degree. After collecting output for each metric, we evaluate them for each data set as it is described in Sect. 2. Fig 2 shows the results of applying Sensitivity Analysis on each test set after normalization. Levenshtein similarity is the most important one. Besides Sensitivity Analysis, Decision Tree models are also used to confirm the results. In Table 1 we compare results of these techniques. All of three tests agree about importance of Levenshtein similarity on the test set. Neural Network chooses Levenshtein while C5.0 and CART select it as second suitable metric. According to the presented algorithm and considering the fact that only one category is introduced as input, only Levenshtein is selected. In a more real situation the above steps are done for each category and one metric from each category is selected. Levenshtein and Jaro-Winkler are selected (from two imaginary categories). After creating a neural network with 4 layers and evaluation of the model on 3xx test set, we got the convincing results.
Most 2 important metrics 5
One advantage of the evaluation method is the uniform treatment of Similarity and Distance metrics so that we don’t need to differentiate and process them separately. This is because in Data Mining evaluation, methods, there is no difference between a variable and a linear form of it. The alignment method can be improved when new metrics are introduced. In such cases it is only needed to add some new columns and do learning to adjust weights. Some of the researchers have emphasized on clustering and application of metrics for clusters as their future works. Another advantage of this method is that we can add cluster value as a new column to influence its importance for combination of metrics.