Validation Semantic Correspondences

A Web Mining Tool to Validate Previously Discovered Semantic Correspondences. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY : 1– KnoE: A Web Mining Tool to Validate Previously Discovered Semantic Correspondences Jorge Martinez-Gil, Member, ACM, and Jos´e F. Aldana-Montes University of M´ alaga, Department of Computer Languages and Computing Sciences Boulevard Louis Pasteur 35. Postal code: 29071. M´ alaga, Spain. E-mail: jorgemar@acm.org; jfam@lcc.uma.es Received — Revised month day, year Abstract The problem of matching schemas or ontologies consists of providing the corresponding entities in two or more models of this kind that belong to a same domain but have been developed separately. Nowadays there are a lot of techniques and tools for addressing this problem, however, the complex nature of the matching problem means existing solutions for real situations are not fully satisfactory. On the other hand, the Google Similarity Distance has appeared recently. Its purpose is to mine knowledge from the Web using the Google Search Engine in order to compare semantically text expressions. Our work consists of developing a software application for validating results discovered by schema and ontology matching tools by using the philosophy behind this distance. Moreover, we are interested in using not only Google, but other popular search engines using this similarity distance. The results have revealed three main facts: firstly, some web search engines can help us to validate semantic correspondences satisfactorily. Secondly there are significant differences among the web search engines, and thirdly the best results are obtained when using combinations of the web search engines that we have studied. Keywords 1 Databases, Database Integration, Data and Knowledge Engineering Tools and Applications Introduction The Semantic Web is a new paradigm for the Web in which the semantics of information is defined, making it possible for the Web to understand and satisfy the requests of people and machines wishing to use the web resources. Therefore, most authors consider it as a vision of the Web from the point of view of an universal medium for data, information, and knowledge exchange [1]. In relation to knowledge, the notion of ontology as a form of representing a particular universe of discourse or some part of it is very important. Schema and ontology matching is a key aspect in order that the knowledge exchange in this extension of the Web may be real [2]; it allows organiza- tions to model their own knowledge without having to stick to a specific standard. In fact, there are two good reasons why most organizations are not interested in working with a standard for modeling their own knowledge: (a) it is very difficult or expensive for many organizations to reach an agreement about a common standard, and (b) these standards do not often fit to the specific needs of the all participants in the standardization process. Although ontology matching is perhaps the most valuable way to solve the problems of heterogeneity between information systems and, there are a lot of techniques for matching ontologies very accurately, experience tells us that the complex nature of the problem to be solved makes it difficult for these techniques to operate satisfactorily for all Terms alignment and matching are often confused. In this work, we will call matching the task of finding correspondences between knowledge models and alignment to the output of the matching task  2 kinds of data, in all domains and as all users expect. Moreover the heterogeneity and ambiguity of data descriptions makes it unlikely that optimal mappings for many pairs of entities will be considered as best mappings by any of the existing matching algorithms. Our opinion is shared by other colleagues who have also experienced this problem. In this way, experience tells us that getting such function is far from being trivial. As we commented earlier, for example, “finding good similarity functions is, data-, context-, and sometimes even userdependent, and needs to be reconsidered every time new data or a new task is inspected” or “dealing with natural language often leads to a significant error rate” [3]. Figure 1 shows an example of matching between two ontologies developed from two different perspectives. Matching is possible because they belong to a common domain that we could name “world of transport”, however there is difficult to find a function in order to discover all possible correspondences. J. Comput. Sci. & Technol., . , , As a result, new mechanisms have been developed from customized similarity measures [4, 5] to hybrid ontology matchers [6, 7], meta-matching systems [8, 9] or even soft computing techniques [10, 11]. However, results are still not entirely satisfactory, but we consider that the web knowledge could be the solution. Our idea is not entirely original; for example, web knowledge has already been used by Ernandes et al. [12] for solving crosswords automatically in the past. We think that this a very promising research line. In fact, we are interested in three characteristics of the World Wide Web (WWW): 1. It is one of the biggest and most heterogeneous databases in the world. And possibly the most valuable source of general knowledge. Therefore, the Web fulfills the properties of Domain Independence, Universality and Maximum Coverage proposed by Gracia and Mena [13]. 2. It is close to human language, and therefore can help to address problems related to natural language processing. 3. It provides mechanisms to separate relevant from non-relevant information or rather the search engines do so. We will use these search engines to our benefit. Fig. 1. Example of matching between two ontologies representing vehicles and landmarks respectively In this way, we believe that the most outstanding contribution of this work is the foundation of a new technique which can help to identify the best web knowledge sources for solving the problem of validating semantic correspondences to match knowledge models satisfactorily. In fact, in [14], the authors state: “We present a new theory of similarity between words and phrases based on information distance and Kolmogorov complexity. To fix thoughts, we used the World Wide Web (WWW) as the database, and Google as the search engine. The method is also applicable to other search engines and databases”. Our work is about those search engines. Therefore in this work, we are going to mine the Web, using search engines to decide if a pair of semantic correspondences previously discovered by a schema or ontology matching tool could be  A Web Mining Tool to Validate Previously Discovered Semantic Correspondences true. It should be taken into account that under no circumstances this work can be considered as a demonstration that one particular web search engine is better than another or that the information it provides is, in general, more accurate. The rest of this article is organized as follows. Section 2 describes the problem statement related to the schema and ontology alignment problem and reviews some of the most outstanding matching approaches. Section 3 describes the preliminary definitions that are necessary for understanding our proposal. Section 4 deals with the details of KnoE, the tool we have built in order to test our hypothesis. Section 5 shows the empirical data that we have obtained from several experiments using the tool. Section 6 discusses the related works presented in the past, and finally, Section 7 describes the conclusions and future lines of research. 2 Problem Statement The process of matching schemas and ontologies can be expressed as a function where given a couple of models of this kind, an optional input alignment, a set of configuration settings and a set of resources, a result is returned. The result returned by the function is called alignment. An alignment is a set of semantic correspondences (also called mappings) which are tuples consisting of a unique identifier of the correspondence, entities belonging to each of the respective ontologies, the type of correspondence (equality, generalization, specialization, etc..) between the entities and a real number between 0 and 1 representing the mathematical probability that the relationship described by R may be true. The entities that can be related are concepts, object properties, data properties, and even instances belonging to the models which are going to be matched. According to the literature, we can group the subproblems related to schema and ontology matching in seven different categories. 1. How to obtain high quality alignments automatically. 2. How to obtain alignments in the shortest possible time. 3 3. How to identify the differences between matching strategies and determine how good each is according to the problem to be solved. 4. How to align very large models. 5. How to interact with the user during the process. 6. How to configure the parameters of the tools in an automatic and intelligent way. 7. How to explain to the user why this alignment was generated. Most researchers work on some of these subproblems. Our work does not fit perfectly with any of them but it identifies a new one: How to validate previously discovered semantic correspondences. Therefore, we work with the output from existing matching tools (preferably with cutting-edge tools). There are a lot of outstanding approaches for implementing this kind of tools: [15, 16, 17, 18, 19, 20, 21]. They often use one or more of the following matching strategies: 1. String normalization. This consists of methods such as removing unnecessary words or symbols. Moreover, strings can be used for detecting plural nouns or to take into account common prefixes or suffixes as well as other natural language features. 2. String similarity. Text similarity is a string based method for identifying similar elements. For example, it may be used to identify identical concepts of two ontologies based on having a similar name [22]. 3. Data Type Comparison. These methods compare the data type of the ontology elements. Similar concept attributes have to be of the same data type. 4. Linguistic methods. This consists of the inclusion of linguistic resources such as lexicons and thesauri to identify possible similarities. The most popular linguistic method is to use WordNet [23] to identify some kinds of relationships between entities.  4 J. Comput. Sci. & Technol., . , , 5. Inheritance analysis. These kinds of methods take into account the inheritance between concepts to identify relationships. The most popular method is the analysis that tries to identify subsumptions between concepts. 6. Data analysis. These kinds of methods are based on the rule: If two concepts have the same instances, they will probably be similar. Sometimes, it is possible to identify the meaning of an upper level entity by looking at one of a lower level. 7. Graph-Mapping. This consists of identifying similar graph structures in two ontologies. These methods use known graph algorithms. Mostly this involves computing and comparing paths, children and taxonomy leaves [4]. 8. Statistical analysis. This consists of extracting keywords and textual descriptions to detect the meaning of one entity in relation to others [24]. 9. Taxonomic analysis. It tries to identify similar concepts or properties by looking at their related entities. The main idea behind this analysis is that two concepts belonging to different ontologies have a certain degree of probability of being identical if they have the same neighborhood [25]. 10. Semantic analysis. According to [2], semantic algorithms handle the input based on its semantic interpretation. One supposes that if two entities are the same, then they share the same interpretations. Thus, they are deductive methods. Most outstanding approaches are propositional satisfiability and description logics reasoning techniques. Most of these strategies have proved their effectiveness when they are used with some kind of synthetic benchmarks like the one offered by the Ontology Alignment Evaluation Initiative (OAEI) [26]. However, when they process real ontologies, their results are worse [27]. For this reason, we propose to use a kind of linguistic resources which have not been studied in depth in this field. Our approach consists of mining knowledge from the Web with the help of web search engines, in this way, we propose to get benefit from the fact that this kind of knowledge is able to support the process of validating the set of correspondences belonging to an schema or ontology alignment. On the other hand, several authors have used web knowledge in their respective work, or have used a generalization: background knowledge [28, 29, 30, 31]. This uses all kinds of knowledge sources to extract information: dictionaries, thesauri, document collections, search engines and so on. For this reason web knowledge is often considered a more specific subtype. The classical approach to this problem has been addressed in literature with the use of a tool called WordNet [23]. Related to this approach, the proposals presented in [15] is the most remarkable. The advantage that our proposal presents in relation to the use of WordNet [23] is that it reflects more closely the language used by people to create their content on the Internet, therefore, it is much closer to everyday terms, thus, if two words appear very often on the same website, we believe that there is some probability that a semantic relationship exists between them. There are other works about Web Measures. For instance, Gracia and Mena [13] try to formalize a measure for comparing the relatedness of two terms using several search engines. Our work differs from that in several key points. Firstly, they use Yahoo! as a search engine in their experiment arguing its balance between good correlation with human judgment and fast response time. Instead we prefer to determine the best source by means of an empirical study. Secondly, authors say they can perform ontology matching tasks with their measure. Based in our experiences, this is not a great idea; i.e. they need to launch many thousands queries in a search engine in order to align two small ontologies and to lower the tolerance threshold [27]. Therefore, they obtain a lot of false positives. Instead, we propose to use the cutting-edge tool [21] to match schemas or ontologies and use  A Web Mining Tool to Validate Previously Discovered Semantic Correspondences web knowledge to validate these previously discovered correspondences. For the same ontologies, we need a thousand times fewer queries number and we do not incur any additional false positive. 3 Technical Preliminaries In this section, we are going to explain some technical details which are necessary to understand our proposal. Definition 1 (Similarity measure). A similarity measure sm is a function sm : µ1 × µ2 7→ R that associates the similarity between two entities µ1 and µ2 to a similarity score sc ∈ < in the range [0, 1]. A similarity score of 0 stands for complete inequality and 1 for equality of the entities µ1 and µ2 . 5 Recall is the fraction of the relevant mappings that are obtained successfully in a matching task. In this way, precision is a measure of exactness and recall a measure of completeness. The problem here is that techniques can be optimized either to obtain high precision at the cost of the recall or, alternatively, recall can be optimized at the cost of the precision. For this reason a measure, called f-measure, is defined as a weighting factor between precision and recall. For the rest of this work, we use the most common configuration which consists of weighting precision and recall equally. Definition 5 (Relatedness Distance). Relatedness Distance is a metric function that states how related two or more entities belonging to different models are and meets the following axioms 1. relatedness(a, b) ≤ 1 2. relatedness(a, b) = 1 if and only if a = b Definition 2 (Alignment). An alignment a is a set of tuples {(id, e, e0 , n, R)}. Where id is an identifier of the mapping, e and e0 are entities belonging to two different models, R is the relation of correspondence between these entities, and n is a real number between 0 and 1 that represents the probability that R may be true. Definition 3 (Matching function). A matching sm function mf is a function mf : O1 × O2 → A that associates two input knowledge models km1 and km2 to an alignment a using a similarity measure. There are many matching techniques for implementing this kind of function as we shown in Section II. Definition 4 (Alignment Evaluation). An alignment evaluation ae is a function ae : a×aR 7→ precision ∈ < ∈ [0, 1] × recall ∈ < ∈ [0, 1] that associates an alignment a and a reference alignment aR to two real numbers stating the precision, recall of a in relation to aR . Precision states the faction of retrieved correspondences that are relevant for a matching task. 3. relatedness(a, b) = relatedness(b, a) 4. relatedness(a, c) ≤ relatedness(a, b) + relatedness(b, c) Notions of similarity and relatedness seems to be very similar, but they are not. Similarity expresses equivalence, while relatedness expresses membership in a common domain of discourse. For example, similarity between car and wheel is low while they are not equivalent at all, while relatedness between car and wheel is high. We can express the differences more formally: Theorem 1 (Similarity involves relatedness). Let µ1 and µ2 be two entities belonging to different knowledge models. If µ1 and µ2 are similar then µ1 and µ2 are related. Theorem 2 (Relatedness does not involve similarity). Let µ1 and µ2 be two related entities belonging to different knowledge models. If µ1 and µ2 are related then we cannot guarantee that they are similar.  6 J. Comput. Sci. & Technol., . , , Lemma 1 (About the validation of semantic correspondences). Let S be the set of semantic correspondences generated using a specific technique. If any of these correspondences are not related, then they are false positives. Example 1 (About Lemma 1). Let (bucks, bank, =, 0.8) be a mapping automatically detected by a matching tool. If we use a relatedness distance which, for example, tell us that bucks and bank do not co-occur in the same websites frequently, then we have that the matching tool generated a false positive. Otherwise, if bucks and bank co-occur very often in the Web, then we cannot refute the correctness of this mapping. Definition 6 (Hit). Hit is an item found by a search engine to match specified search conditions. More formally, we can define a hit as the function hit : ϑ 7→ N which associates a natural number to a set of words to ascertain its popularity in the WWW. A value of 0 stands for no popularity and the bigger the value, the bigger its associated popularity. Moreover, we want to remark that the function hit has many possible implementations. In fact, every web search engine implements it a different way. For this reason, we can not take into account only one search engine to perform our work. Example 2. (Normalized Google Distance). It is a measure of relatedness derived from the number of hits returned by the Google search engine for a given (set of ) keyword(s). Keywords with the same or similar meanings in a natural language sense tend to be close in units of Google distance, while words with dissimilar meanings tend to be farther apart. The normalized Google distance (NGD) between two search terms a and a is mx{log hit(a), log hit(b)} − log hit(a, b) log M − mn{log hit(a), log hit(b)} (1) where M is the total number of web pages D(a, b) = searched by Google; hit(a) and hit(b) are the number of hits for search terms a and b, respectively; and hit(a, b) is the number of web pages on which a and b co-occur. Finally, we define a correspondence validator as an software artifact that uses a relatedness distance to detect false positives in schema or ontology alignments according to the Lemma 1. We have built a correspondence validator called Knowledge Extractor (KnoE). 4 KnoE Semantic similarity between text expressions changes over time and across domains. The traditional approach to solve this problem has consisted of using manually compiled taxonomies. The problem is that a lot of terms are not covered by dictionaries; therefore, similarity measures that are based on dictionaries cannot be used directly in these tasks. However, we think that the great advances in web research have provided new opportunities for developing new solutions. In fact, with the increase of larger and larger collections of data resources on the WWW, the study of web measures has become one of the most active areas for researchers. We consider that techniques of this kind are very useful for solving problems related to semantic similarity because new expressions are constantly being created and also new senses are assigned to existing expressions. The philosophy behind KnoE (Knowledge Extractor) is to use a web measure based on the Google Similarity Distance [14]. This similarity measure gives us an idea of the number of times that two concepts appear together in comparison with the number of times that the two concepts appear separately in the subset from the Web indexed by a given search engine. For the implementation of the function hit, we have chosen the following search engines from among the most popular in the ranking Alexa [32]: Google, Yahoo!, Lycos, Altavista, MSN and Ask. The comparison is made between previously discovered correspondences. In this way we can decide if compared correspondences are considered reliable, or if they are not.  A Web Mining Tool to Validate Previously Discovered Semantic Correspondences We could launch a task to make a comparison between all the entities of source and target knowledge model respectively. Then, only pairs of entities likely to be true (those whose parameter n exceeds a certain threshold) would be included in the final output alignment. There are several reasons why we do not propose this: Attempting to match models using directly such web knowledge function as Google Distance would involve considerable cost in terms of time and broadband consumption because each comparison needs 3 queries for the search engine and repeating this m · n times, where m and n are the number of entities belonging to the source and target knowledge models respectively. But the most important reason is that the amount of generated false positives means that this process may be unworkable. We have tried to solve the benchmark from OAEI [26] using only web knowledge and have obtained an average f-measure of about 19 percent. This represents a very low figure if we consider that the most outstanding tools obtains a f-measure of above 90 percent for the same benchmark [27]. 7 validation. In Figure 3, we have launched a task to validate the correspondence (f ootball, goal) using Google, Yahoo! and MSN. As it can be seen, Google considers that is not possible to refute the correctness of the correspondence, while Yahoo! and MSN consider that the equivalence is wrong. Fig. 3. Graphical User Interface for KnoE. In this figure we show the validation of the pair (football, goal) according to several search engines 5 Fig. 2. Screenshot from the main window of KnoE. Users can select individual terms or lists. Moreover, they can choose some search engines for mining the web Finally, KnoE has been coded using Java so it can be used in console mode on several operating systems, but to make the tool more friendly to the user, we have programmed a graphical user interface, as Figure 2 shows. The operation mode is simple: once users select correspondences to compare, they should choose one or more search engines to perform the Empirical Evaluation Now we evaluate KnoE using three widely accepted benchmark datasets. These benchmarks are Miller-Charles [33], Gracia-Mena [13], and Rubenstein-Goodenough [34] which are pairs of terms that vary from low to high semantic relatedness. Several notes that are important in order to perform these experiments are: Some of the companies which own the web search engines do not allow many queries to be launched daily, because it is considered as mining service. So the service is limited and several days were necessary to perform the experiments. Results from Lycos Search Engine have not been included because, after several executions, they do not seem to be appropriate. In addition, it is important to note that this experiment was performed in February 2010, because the information indexed by the web search engines is  8 J. Comput. Sci. & Technol., . , , not static. Table 1 shows the results that we have obtained for the Miller-Charles benchmark dataset. Table 2 shows the results we have obtained for the Gracia-Mena benchmark dataset. Finally, Table 3 shows the results we have obtained for the Rubenstein-Goodenough benchmark dataset. On the other hand, Figures 4, 5, and 6 show the behavior of the average means from the web search engines in relation to the benchmark datasets. We have chosen to represent the average mean because it gives us the best result among the statistical functions studied. We have studied the mode and median additionally, but it does not outperform the average mean. The comparison between the benchmark datasets and our results is made using the Pearson’s Correlation Coefficient, which is an statistical measure which allows to compare two matrices of numeric values. Therefore the results can be in the interval [-1, 1], where -1 represents the worst case (totally different values) and 1 represents the best case (totally equivalent values). dataset. We interpret this in the following form: although a correct pair of concepts cannot be validated by a specific search engine, it is very difficult that all search engines can be wrong at the same time. Therefore, for the rest of this work, we are going to use the average mean in our semantic correspondence validation processes. score Mil.-Cha. KnoE case Fig. 4. Graphic representation of the behavior for the Miller-Charles benchmark score Gra.-Mena KnoE • Experimental results on Miller-Charles benchmark dataset show that the proposed measure outperforms all the existing webbased semantic similarity measures by a wide margin, achieving a correlation coefficient of 0.61. case • Experimental results on Gracia-Mena benchmark dataset show that the proposed measure outperforms all the existing web-based semantic similarity measures (except Ask), achieving a correlation coefficient of 0.70. Fig. 5. Graphic representation of the behavior for the Gracia-Mena benchmark score Rub.-Go. • Experimental results on RubensteinGoodenough benchmark dataset show that the proposed measure outperforms all the existing web-based semantic similarity measures (except Yahoo!) achieving a correlation coefficient of 0.51. The average mean presents a better behavior than the rest of studied mining processes: It is the best for the first benchmark dataset and the second one for the second and third benchmark KnoE case Fig. 6. Graphic representation of the behavior for the Rubenstein-Goodenough benchmark  9 A Web Mining Tool to Validate Previously Discovered Semantic Correspondences Mil.-Cha. Google Ask Altavista MSN Yahoo KnoE cord-smile 0.13 0.05 0.25 1.00 0.00 0.00 0.26 rooster-voyage 0.08 0.24 1.00 0.00 0.00 0.00 0.25 noon-string 0.08 0.50 1.00 0.00 0.00 0.00 0.30 glass-magician 0.11 1.00 1.00 1.00 0.00 0.01 0.60 monk-slave 0.55 1.00 1.00 1.00 0.00 0.00 0.60 coast-forest 0.42 1.00 1.00 1.00 0.02 0.01 0.61 monk-oracle 1.10 1.00 1.00 1.00 0.00 0.00 0.60 lad-wizard 0.42 0.04 1.00 1.00 0.00 0.00 0.41 forest-graveyard 0.84 1.00 1.00 1.00 0.00 0.01 0.60 food-rooster 0.89 1.00 1.00 1.00 0.00 0.00 0.60 coast-hill 0.87 1.00 1.00 1.00 0.06 0.02 0.62 car-journey 1.16 0.17 1.00 1.00 0.01 0.00 0.44 crane-implement 1.68 0.14 1.00 0.00 0.00 0.00 0.23 brother-lad 1.66 0.18 1.00 1.00 0.00 0.00 0.44 bird-crane 2.97 1.00 1.00 1.00 0.13 0.09 0.64 bird-cock 3.05 1.00 1.00 1.00 0.07 0.07 0.63 food-fruit 3.08 1.00 1.00 1.00 0.03 0.01 0.61 brother-monk 2.82 1.00 1.00 1.00 0.11 0.04 0.63 asylum-madhouse 3.61 1.00 1.00 1.00 0.00 0.00 0.60 furnace-stove 3.11 0.46 1.00 1.00 0.00 1.00 0.69 magician-wizard 3.50 1.00 1.00 1.00 0.04 0.98 0.80 journey-voyage 3.84 1.00 1.00 1.00 0.00 0.00 0.60 coast-shore 3.70 1.00 1.00 1.00 0.02 0.08 0.62 implement-tool 2.95 1.00 1.00 1.00 0.00 0.02 0.60 boy-lad 3.76 1.00 1.00 1.00 0.18 0.02 0.64 automobile-car 3.92 1.00 1.00 1.00 0.01 0.34 0.67 midday-noon 3.42 1.00 1.00 1.00 0.07 0.00 0.61 gem-jewel 3.84 1.00 1.00 1.00 0.39 0.05 0.69 Correlation 1.00 0.47 0.26 0.35 0.43 0.34 0.61 Table 1. Experimental results obtained on Miller-Charles benchmark dataset