Matching algorithms automatically discover semantic relations between two autonomously developed conceptual representations of two overlapping domains. Typical examples of such conceptualizations are electronic market catalogues (e.g., UNSPSC and ECL@SS) and web directories (e.g., GOOGLE and YAHOO!). The objective of this paper is the description of a use case in which matching algorithm has been used to re-classify into UNSPSC the catalogue of the of ce equipment and accessories used by a worldwide telecommunication company to classify their suppliers. On the basis of this experience we are envisaging new application of the algorithm in the area of demand aggregation, and we will conclude the paper by brie y describing a future application in this area.
In the e-Business hype, marketplaces have been proposed as the optimal solution to foster ef ciency and dynamic business integration, however, reality have shown something different. The assumption that standard catalogues can substitute local ones has been neglected by the simple evidence that, on similar business domains, there are different competing standards [Agrawal and Srikant, 2001]. Moreover, company buyers have dif culties in adopting classi cation standards that are way complex and generic from their simple and task speci c ones. This is more true when considering that local conceptualizations are not just the mere result of cultural/historical differences, but rather the consequence of different, substantial, valuable ways of doing things. Furthermore, the idea of standardizing semantics seems to be conceptually wrong, more than practically unfeasible, if semantic heterogeneity is read in terms of richness to be exploited rather than in terms of noise to be reduced [Bonifacio and Molani, 2003]. In very simple words, if people call things in different ways is because they do different things, have different goals, adopt different perspectives.
In this scenario the only feasible solution to heterogeneity in e-Business is the one that admits the existence of a set of heterogeneous and overlapping products catalogues, and supports semantic interoperability between then. Semantic interoperability is reached by matching algorithms, i.e., procedures capable to nd semantic relations between the categories of different products catalogues. Two examples of matching algorithms, representing two different approaches, are the CTXMATCH algorithm described in [Bouquet et al., 2003], and the GoldenBullet system described in [Ding et al., 2002]. The former is based on NLP techniques applied to the labels occurring in the classi cation and the transformation of the matching problem in a satis ability problem, while the latter uses techniques for information retrieval and machine learning applied to the content of the classi cation. While GoldenBullet demands for a training set, i.e., it needs a set of examples of mappings between concepts which have been checked manually, CTXMATCH is completely automatic and needs as input just two classi cations.
The objective of this paper is the description of an experiment of applying the CTXMATCH algorithm in a case where no training set was available. In particular we apply CTXMATCH to nd mapping between the catalogue of of ce equipment and accessories used to classify company suppliers of a worldwide telecommunication company and the standard catalogue UNSPSC. In this sense we simulated a situation in which a network actor of a marketplace becomes able to share information about products and services with other actors without adopting a prede ned ontology. This paper can be consider also as a partial answer of the call for proposal described in [Schulten et al., 2001], where the author suggest the following challenge in the e-business [. . . ] to come up with a generic model and working solution that can semiautomatically map a given product description between two different e-commerce product classi cation standards.
The paper is structured as follows. In Section 2 we describe the CTXMATCH algorithm; Section 3 describes the problem and the solution we have proposed in use case. Section 4 draw some conclusions and describe a future application. 2
CTXMATCH enables semantic interoperability between overlapping concept hierarchies through mapping discovery. The algorithm [Magnini et al., 2002] takes as input two conceptual hierarchies (i.e. a source hierarchy and a target hierarchy) and returns a set of directed mappings between source and target concepts. The main features of the algorithm are the following: it does not consider concept instances (e.g., documents), so that it can be used in situations where such information is partially available or is not available at all; it returns a semantic evaluation of the mapping between two concepts (i.e. equivalence, more general than, less general than); it is context-based, in the sense that it builds a semantic representation of the meaning of a concept which depends ,"$ both on the position in which it appears in a concept hierarchy and on world knowledge available in an external resource.
The algorithm performs three main steps: (i) a linguistic analysis of the concepts without considering the hierarchical structure of the context; (ii) a logical interpretation of the concept based on the structural relations of the context; (iii) the identi cation of mapping relations between the logical interpretations of the concepts using SAT.
The rst step of the procedure consists of text chunking, i.e. dividing each label into syntactically correlated parts of words. We run the standard Alembic chunker [Day and Vilain, 2000], developed by MITRE Corporation as part of the Alembic extraction system [Aberdeen et al., 1995].
For example, with the label Globalization and Free Trade, the chunker rst selects a part of speech for each word (`Globalization' and `Trade' are nouns, `Free' is an adjective, `and' is a conjunction); then, it identi es two noun groups (NGs), i.e. `GLOBALIZATION' and `Free TRADE' (notice that the syntactic head is marked in small capitals), and a coordinating conjunction between them: [(GLOBALIZATION) ] (and) [(Free) (TRADE) ]
The output of the chunker is used to transform each label into a basic logical form. A noun group consisting of more than one word is interpreted as the conjunction of the head and all its modi ers; for instance, Iron Trade is interpreted as [Iron & Trade]. The relations between different noun groups are interpreted on the basis of the linguistic material connecting them: coordinating conjunctions and commas are interpreted as a disjunction (e.g. Globalization and Free Trade is interpreted as [[Globalization] [Free & Trade]]), prepositions, like `in' or `of', are interpreted as a conjunction (e.g. Iron Trade of Great Britain is transformed into [[Iron & Trade] & [Great & Britain]]), expressions denoting exclusion, like `except' or `but not', are interpreted as a negation (e.g. Garments except Skirts becomes [[Garments] & [Skirts]]).1
In order to perform the semantic interpretation of the labels CTXMATCH accesses WORDNET [Fellbaum, 1998]. When a word is found, all the senses of that word are selected and attached to the basic logical form.
When two or more words in a label are contained in WORDNET as a single expression (i.e. a multiword), the corresponding senses are selected and, in the basic logical form, the intersection between the two words is substituted by the multiword. In the case of [[iron* & trade*] & [great* & Britain*]], for instance, `Great Britain' is provided in WORDNET as a single expression, so the logical interpretation is substituted by the senses of the multiword, thus obtaining [[iron* & trade*] & [Great Britain*]]. root is Soccer, with a descendant Leagues and a further descendant Clubs. The full logical form of the root is simply [soccer*], the full logical form of Leagues is [[soccer*] & [league*]] and the full logical form of Clubs is [[soccer*] & [league*] & [club*]].
As explained before, the disjunction between noun groups can be made explicit by the presence of a coordinating conjunction, but we can also have implicit disjunction between elements placed at different levels of the hierarchy. In the example above, at a deeper level of analysis there are two conicting interpretations: from the point of view of the hierarchical structure clubs denotes a subset of leagues; on the other hand, from the point of view of the world knowledge provided in WORDNET, [club#2] and [league#1] are disjoint because they have the same hypernym, i.e. association#1 . In order to combine the two information sources, leagues has to be reinterpreted as if it were leagues and clubs, i.e. [[league#1] [club#2]].
Similarly, also the negation is not always marked by expressions like `but not' or `except'. For instance, we can have Sociology and Science as sibling nodes classi ed under Academic Study of Soccer. From the point of view of world knowledge, sociology is a science (and in fact in WORDNET sociology#1 is a second level hyponym of science#2). As a consequence, the node labeled with Science has to be interpreted as if it were Science except Sociology.
The recognition of multiwords can also be performed on different contiguous levels. For instance, in WORDNET there is a multiword `billiard player', so in a hierarchy where Sport has Billiards as a child and Player as a further descendant, the conjunction of [billiard*] and [player*] can be substituted with the multiword, giving as a result the logical form [[sport*] & [billiard player*]].
CTXMATCH performs word sense disambiguation by taking into consideration both structural relations between labels and conceptual relations between words belonging to different labels.
Let L be a generic label and L either an ancestor label or a descendant label of L and let s* and s * be respectively the sets of WORDNET senses of a word in L and a word in L . If one of the senses belonging to s* is either a synonym, a hypernym, a holonym, a hyponym or a meronym of one of the senses belonging to s *, these two senses are retained and all other senses are discarded.
As an example, imagine Apple (which can denote either a tree or a fruit) and Food as its ancestor; since there exists a hyponymy relation between apple#1 (denoting a fruit) and food#1, we retain apple#1 and discard apple#2. 2.2
The full logical form of a label is the conjunction of the basic logical forms of the label and all its ancestors. To make an example, let's take the concept hierarchy whose
1We use the following notation: `Trade' indicates a simple word; Trade indicates a label of a concept; Trade indicates a predicate in a logical form; trade* indicates the disjunction of all the senses of `trade' in WORDNET; trade#3 indicates sense 3 of `trade', while trade#[2,4] indicates the disjunction of senses 2 and sense 4.
Item list ’( that ! logic.
The equivalence between *" the relation between and is obtained by translating !"$ and into a set of subsumptions in description %’.-/0"1 The background theory relevant for computing
the WORDNET hierarchical relations on senses appearing in %*-/,"1 . Similarly, the fact that is more speci c [general] ! %&’*-;(") ] is implied by ; the fact that is compatible 2" and is checked by verifying 435!") !"$ 637’! and are both implied by %’*-;,") ." in ; nally the fact that is disjoint from is checked ," ’! =<>&’2"? with is checked by verifying that is satis able !" ! 8392") :3 than is checked by verifying that [&’!") ’! @<4&’*"$ %*-/!"1 by verifying that is not satis able in .
To each relation it is possible to associate also a quantitative measure that considers the relation on the cardinality of models satisfying w(k) and w(k').
In order to centrally manage all the company acquisition processes, the headquarter of a well known world wide telecommunication company had realized an eProcurement system 2, which all the company branch-quarters have been required to join. In order to join it, each single of ce was also required to migrate from the product catalogue they used to manage with, to the new one managed within the platform. This catalogue is extracted from the Universal Standard Products and Services Classi cation (UNSPSC), which is an open global coding system that classi es products and services. The UNSPSC is used extensively around the world in the electronic catalogues, search engines, procurement application systems and accounting systems. UNSPSC is a four level hierarchical classi cation; an extract is reported in the following table: A of re-classi cation: if the algorithm returns that the item A B UNSPSC, then can be classi ed under UNSPSC of UNSPSC. B is equivalent to, or more speci c than, the node UNSPSC of 3.1 Methodology We started with the linguistic analysis (normalization phase) of the company item catalogue and of the UNSPSC segments we took into account. The linguistic analysis inovolves rst a morphological cleaning process, then a disambiguation and enrichment process. This is performed by accessing WordNet and, for each given term, nding out all the instances of its semantic meanings (corresponding to WordNet numeric IDs) and associate to them all the available synonyms. The output was two les with the semantic explicitations of the catalogue items on one hand, and of the UNSPSC nodes on the other, both in terms of IDs of WordNet. Then we went on with the matching phase by running the alghoritm on the two les.
The result of the matching can be cleary interpreted in terms
Notice that the company item catalogue we had to deal
with, was a plain list of items, each identi ed with a
numerical code made up of two couple of numbers the rst
referring to a set of more general categories
rst numerical codes with their textual description, provided us by the company. The validation phase of our results has been made by comparing them with the results of a simple keyword based alghoritm. Obviously, in order to set the correctness, in terms of precision and recall, of such results we needed a correct matching list to be used as point of reference for the validation. Then we ask a domain expert, Alessandro Cederle, Managing Director of Kompass Italia3 to validate a possible correct matching list we provided him with.
The Italian of ce asked us to apply the matching alghoritm to re-classify into UNSPSC (version 5.0.2) the catalogue of the of ce equipment and accessories used to classify company suppliers.
The items to be re-classi ed are mainly labeled with Italian phrases, but labels contain also abbreviations, acronyms, proper names, some English phrases and some typing errors.
The English translation of an extract of this list is reported in the following table (the italic parts were contained in the original labels).
Level 4 Sofas Level 4 Coat racks 3
Description cartridge hp desk jet 2000c magnetic tape cassette exatape 160m xl 7,0gb hybrid roller pentel red safety scissors, length 25 cm The item list was matched with two UNSPSC's-segments, namely: Of ce Equipment and Accessories and Supplies (segment 44) and Paper Materials and Products (segment 14).
2An eProcurement system is a technological platform which supports a company in managing its procurement processes and, more in general, the ri-organization of the value chain on the supply side.
This sections presents the results of the re-classi cation. Consider rst the baseline macthing process. The baseline has been performed by a simple keyword based matching which worked according to the following rule: for each item description (made up of one or more words) gives back the set of nodes, and their paths, which maximize the occurrences of the item words.
The following tables summarizes the results for baseline matching:
3Kompass (www.kompass.com) is a company which provides product information, contacts and other information about 1.8 million companies worldwide. All companies are classi ed under the Kompass Product Classi cation with more than 52,000 products and services.
Given the 194 items to be re-classi ed, the baseline process found 1945 possible nodes, that means that for each item it found a set of 6 possible maximazing nodes by average. What is crucial is that only 75 out of the 1945 proposed nodes are correct. The baseline, being a mere simple string matching, is able to capture a certain number of re-classi cations, but the percentage of error is quite high (50%), with respect to the one of correctness (39%). Such parameter shows different values for the matching algorithm, that is able not only to compare strings but also to interpret their meaning. The results of the matching algorithm are reported in the following table: In this case the percentage of success is sensibly higher (70%) and, even most relevant, the percentage of error is minimal (8%). 4 This is con rmed also by the values of precision and recall, computed with respect to the validated list: C in some cases the item to be re-classi ed has a incorrect position within the company catalogue, so the matching alghoritm couldn't compute in the right way the relations with the node and its father node. Examples are the ashtray which has been classi ed under tape dispenser, the wrapping paper which has been classi ed under adhesive labels.
C in some cases in order to understand the meaning of the item to be re-classi ed, more domain knowledge should be requested and then embedded within the system. An example is the case of paper for hp: in order to understand that it is printer paper, it's necessary to know that hp stands for Helwett Packard and that this is a company which produces printers. algorithm is able to suggest the matching with the UNSPSC node evidenziatori, which is the plural form .
¿From the structural point of view, the possibility to reason on some topologichal properties allows the alghoritm to point out a semantic relation such as More General than between the company catalogue item nastro per stampante, toner, cartuccia, testina di stampa and the UNSPSC node Cartucce d'inchiostro. In this case, the properties taken into account are two: the fact that the catalogue item has just one level higher, while the UNSPSC one has two, and the fact that the catalogue item is made up of several single items, while the UNSPSC one just of one. These two consideration are enough to set that the meaning of the rst should be more general then the second's. If there are not enough structural data to suggest a semantic relation, the alghoritm gives back at least a compatibility between the two elements, computed on some linguistic occurrences measures (see the last four lines of the table). For the Non Classi ed items, it should be noticed the following:
1945 641 Precision 4% 21%
39% 70% Baseline
Matching
The baseline precision level is quite small, while the matching one is not excellent but de nitely better. The same observations can be done also for the recall values.
Table 1 reports some examples where the algorithm found out a correct item for re-classi cation, while the baseline did not5.
The ability of the alghoritm to reason both on linguistical data and on structural ones, accounts for its good performance with respect to the baseline one. ¿From the linguistical point of view, two considerations are to be done. First the possibility for our algorithm to manage with synonimous allows it, for example, to recognize that the item perforatrice 6, and all its variants (perforatrice 2/4 fori, perforatrice universale, etc) have the same meaning of the UNSPSC node punzonatrice so it suggested to re-classify it under that node. Second, the fact that during the normalization phase a stemming cleaning is performed on words allows the matching phase to deal with lemmas in their basic form, without any morphological modi cation. (e.g. the singular or plural word). This means that in the example of the item evidenziatore7 (singular form) the
4Notice that the algorithm did not take into account only the UNSPSC 4th level category, since in some cases catalogues items can be matched with UNSPSC (3rd level) category nodes.
5Since the whole matching work strongly depends on languages, we will present results in Italian but provided with a very literally English translation. We apologise if in some cases such translation will not completely support the reader in the comprehension of the example.
6In English: drilling machine. 7In English: highlight.
A nal step of the use case was having a second matching between the company catalogue's IDs and the output of the normalization of the English version of UNSPSC with the English version of WordNet. This procedure, viable because the matching computation performing on the matrix takes into account just the concepts' IDs, allows us to nd many more matching than using just one language.
More in general, this way allows us to approach and manage multilanguage environments and to exploit the richness which typically charaterizes the English version of any linguistic resources. 8
Two lessons have been learned from this experiment. First, our algorithm is good for re-classi cation rather than for simple classi cation of a plain list of items. As previuosly explained, the alghoritm exploits two kinds of data, linguistical and structural ones: in the case of a plain list, the second set of data are missed and this impacts on the results' goodness.
This is the reason why results de nitely improve when we run the alghoritm on the company items catalogue enriched by the category structure extracted from the numerical codes.
The second lesson concerns the quality of the labels. The better the labels are written, the better is the matching obtained. In presence of meaningless labels such as shortcuts (num for number, cart. for cartridge, etc.), proper names (Duracell, Hewlett Packard, etc.), this version of the
8We do not report here the results of this last step, since we cannot compare them with the results of the baseline that, being a mere keyword based algorithm, could run only on homogeneus linguistical situation.
perforatrice/perforatrice a 2-4 fori nastro per stampante, toner, cartuccia, testina di stampa penna lampostil, pennarello, evidenziatore/evidenziatore nastro per stampante, toner, cartuccia, testina di stampa E Table 1: Reclassi cations found by CTXMATCH and not found by the baseline ( stands for compatible) algorithm is not capable of assigning a proper semantic to the labels, decreasing the performances. Possible improvements in this direction could be reached through two ways.
First, the linguistic analysis of labels can be improved by using domain-oriented linguistical resources. Several domains are developing thesaura, ontologies, standard classi cations which speci cally deal with their lexicons. 9 These kind of resources involve also relevant proper names, company names, abbreviations and acronyms, which right now are still problematic data for the algorithm. 10 The second way to be investigated is the possibility of supporting funcionalities of spell checking, able to detect spelling errors and to suggest the right alternatives. 4
An alternative approach to CTXMATCH, for product classi cation in UNSPSC, called GoldenBullet, is described in [Ding et al., 2002]. GoldenBullet is an environment that support product classi cation according to content standards. It applies techniques of information retrieval and machine learning. The classi cation is based on a training set. The classi cation algorithm implemented in GoldenBullet performs indeed very well when it is used in a supervised way. This approach can therefore be useful (and maybe it could perform better than CTXMATCH) in presence of a representative set of pre-classi ed examples. CTXMATCH, instead provides good results also without such a training set.
A relevant approach to ontology matching has been proposed in [Doan et al., 2002] and [Madhavan et al., 2002]. Althought the aim of the work (i.e. establishing mappings among concepts of overlapping ontologies) is in many respects similar to our goals, the methodologies differ significantly. A major difference is that the GLUE system builds mappings taking advantage of information contained in instances, while our current version of the CTXMATCH algo9for example in the Healthcare domain a good linguistical resources is MESH (http://www.nlm.nih.gov/mesh/), the National Library of Medicine's controlled vocabulary thesaurus. It consists of sets of terms naming descriptors in a hierarchical structure that permits searching at various levels of speci city.
10see http://www.acronym nder.com/ for an example of acronym database. rithm completely ignores them. This makes CTXMATCH more appealing, since most of the ontologies currently available on the Semantic Web still do not contain signi cant amount of instances. A second difference concerns the use of domain-dependent constraints, which, in case of the GLUE system, need to be provided manually by domain experts, while in CTXMATCH they are automatically extracted from an already existing resource (i.e. WordNet). Finally, CTXMATCH attempts to provide a qualitative caracterization of the mapping in terms of the relation involved among two concepts, a feature which is not considered in GLUE. Although a strict comparison with the performances reported in [Doan et al., 2002] is rather dif cult, the accuracy achieved by CTXMATCH could be roughly compared with the accuracy of the GLUE module which uses less information (i.e. the name learner).
A mapping procedure based on lexical information has been proposed in [Bergamaschi et al., 2002]. No quantitative evaluation is reported. Only a qualitative exempli cation, based on the task proposed in [Schulten et al., 2001], is described to show the algorithm capabilities.
Finally, the evaluation of the Anchor-PROMPT System [Noy and Musen, 2001] has been conducted on two ontologies and the mappings identi ed by the algorithm have been manually checked. Results are presented in term of the achieved precision. 5
We focused on the evaluation of a context matching algorithm, which automatically generates mappings among the concepts of two overlapping hierarchies. The main features of the algorithm are the following: it does not consider concept instances, so that it can be used in situations where such information is partially available or not available at all; it returns a qualitative estimation of the mapping between two concepts (i.e. equivalence, more general than, less general than); it is content-based, in the sense that it builds a semantic representation of the meaning of a concept given both the context of its neighborhood and the world knowledge available in an external resource (i.e. WordNet).
We have presented three empirical experiments with a twofold aim: rst, we wanted to evaluate the CTXMATCH algorithm in real, large scale scenarios; second, we wanted to test different evaluation methodologies. In particular, we have experimented CTXMATCH on Web directories and market place catalogues.
A number of data have been collected, which are to be considered as a rst contribution toward common evaluation practices and the possibility to share resources for context matching algorithms.
Another application we are now working on is a system to manage the automatical aggegation of buyers' demands. This is aimed to be embedded in those technological platforms (such as eProcurements system, or also marketplaces) where the possibility for buyers to aggregate their product demands could give them some advantages in terms of forniture conditions or buying power. In order to support the aggregation process, the system should be able, rst to point out groups of buyers interested in a similar category of product, then to suggest if and how each buyer should modify some requested features in order to get to more advantages. As an example consider the following case: the acquisition of ces of two public universities are interested in buying 200 mobile phones, but one of ce preferes mobiles with the features A and B, the other of ce is more interested in mobile with the features C and D. Let's suppose that a mobile seller proposes a strong discount for 400 mobiles with features A, D and E. If the two of ces converged on this last kind of mobile, they would get to the discount. In order to support this process, the system should be able not only to match item at the product description level, but also at the attribute level. Attributes are used to specify product features such as color, lenght, size, etc, and typically they are the elements on which a negotiation process could be done. The rst idea we are investigating on is to develop different attribute contexts (one for colors, one for lenght, one for size,...), and a speci c version of the alghoritm aimed to match this kind of structures. This way would allow us to split the matching between product structures, and the one between attribute structures and to combine afterwards the two sets of results.
A step further will be to develop the capability for the system to support buyers in the negotiation on attributes, for example by providing users with simulations of different combinations of attributes and displaying the related advantages.