Integrating Multiple Internet Directories by Instance-based Learning

1 Introduction

The World-Wide Web (WWW) is now used not only by com­ puter specialists, but by all sorts of people, from children to businessmen and businesswomen, which has resulted in an enormous quantity of web pages available on the Inter­ net. This makes finding pages containing the desired infor­ mation rather difficult. Search engines are requisite for find­ ing the desired information. In general, current search en­ gines perform their functions via one of two methods: a key­ word search and a directory search. A keyword search en­ gine performs searches by means of user-specified keywords. Keyword-based search engines like Google can reliably find pages containing the specified keywords. However, if the user does not have a thorough knowledge of his/her search domain and cannot choose the appropriate keywords, the search engine is useless. In such a situation, directory-based search engines do a good job. In a directory-based search engine, pages are evaluated and organized by humans before being registered in the search engine's archive. Directory­ based search engines provide knowledge of WWW naviga­ tion. Users reach the desired information by going up and down the directories.

Although pages are carefully selected and well-organized, a single Internet directory is not sufficient because the In­ ternet directory tends to have some bias in both collecting and categorizing pages. In order to solve these problems, we herein propose a method that coordinates multiple In­ ternet directories by estimating directory similarities. The proposed method does not simply merge multiple directories into a larger directory, but instead determines the relationship between directories. Many public Internet directories exist. Some are designed to cover wide domains, while others fo­ cus on special domains. Such Internet directories are diffi­ cult to merge. Moreover, these directories should not be inte­ grated, because the existing differences in concept hierarchies among the directories is important when selecting and using directory-based search engines. In this paper, we propose a method to solve this problem by determining the rules for mapping categories in a directory to those in another direc·· tory. Our solution can be applicable not only to the Internet directory problem, but also to the integration of web market­ place catalogs [Agrawal and Srikant, 2001] 1 and ontology in­ tegration in general.

The remainder of this paper is organized as follows. In Section 2, we define the problem of coordinating multiple In­ ternet directories. In Section 3, we discuss related studies. In Section 4, we propose a new machine learning method for the above-mentioned problem. Next, in Section 5, we compare the performance of the proposed method to that of the En­ hanced Naive Bayes approach [Agrawal and Srikant, 2001] for an integration problem using real Internet directories. Fi­ nally, in Section 6, we present our conclusions.

2 Integration of Multiple Internet Directories

In order to state the problem, we introduce a model for the Internet directories we intend to integrate. We assume there are two Internet directories: a source directory and a target directory. The documents in the source Internet directory are expected to be assigned to categories in the target Internet di­ rectory. This produces a virtually integrated Internet directory in which the documents in the source directory are expected to be members of both the source and target directories. This integrated directory inherits the categorization hierarchy from the target Internet directory.

1 For example, the integration of a distributor's catalog and a web marketplace.

The Internet directory model for the source and target is as follows:

• The source Internet directory, S D contains a set of cate­ gories, Csl, Cs2 , ... , Csn , that are organized into an "is­ a" hierarchy. Each category can also contain documents.
• The target Internet directory TD contains a set of cate­ gories, Cn, Ct2 , .. . , Ctm that are organized into an "is­ a" hierarchy. Each category can also contain documents.

The proposed model permits documents to be assigned to intermediate categories. This model is similar to the catalog model in [Agrawal and Srikant, 2001], except that thecate­ gories are organized into a conceptual hierarchy. Since the catalog model ignores hierarchy structure and therefore can­ not assign documents to an intermediate category, our Inter­ net directory model is more general than the catalog model.

The problem addressed in this paper is finding an appro­ priate category Ct in the target directory TD for each docu­ ment D si in the source directory S D . An example is shown as the mapping of a black box D x in Figure 1, where the black circles indicate categories and the hollow boxes indi­ cate documents. What we need to do is determine an appro­ priate category in TD for a document which appears in SD but not in TD, because mapping is not necessary if the doc­ ument is included in both the source and the target directo­ ries. Documents D1 and D2 in Figure 1 are examples of such documents. This mapping can have several possibilities, e.g. , D x can be mapped to an upper left category or to a lower left category, etc.

3 Related Work

One popular approach to this kind of problem is to apply standard machine learning methods [Langley, 1996]. This requires a flattened class space having one class for ev­ ery leaf node. The problem can then be considered to be a normal classification problem for documents. Naive Bayes(NB) [Mitchell, 1997] is an established method used for this type of document classification framework. A classifier is constructed using the words in the documents. However, this classification scheme ignores the hierarchical structure of classes and, moreover, cannot use the categorization informa­ tion in the source directory. Enhanced Naive Bayes [Agrawal and Srikant, 2001 ], hereafter referred to as E-NB, is a method which does use this information. E-NB will be discussed in the next section. GLUE [Doan et a/., 2002] is another type of system employing NB. To improve accuracy, GLUE combines NB and a constraint optimization technique called relaxation labeling. However, the general performance of the system depends on that of NB. Unlike NB, the systems in [Koller and Sahami, 1997], [Wang eta/., 1999] classify documents into hierarchical categories, and these systems use the words in the documents for classification rules. However, these systems cannot use the categorization information in the source directory.

Another type of approach is ontology merging/alignment systems. These systems combine two ontologies, which are represented in a hierarchal categorization. Chi­ maera [McGuinness eta/., 2000] and PROMPT [Noy and Musen, 2000] are examples of such systems and assist in the combination of different ontologies. However, such systems require human interaction for merging or alignment. In ad­ dition to this requirement, these systems are based on the similarity between words, which introduces instability. The dictionaries used for such systems often have word similarity bias. FCA-MERGE [Stumme and Madche, 2001] is another type of ontology merging method. It uses the attributes of concepts to merge different ontologies. As a result, it cre­ ates a new concept without regarding the original concepts in both ontologies. Calvanese eta!. [ Calvanese eta/., 2001] also discussed an ontology integration framework with respect to global ontology and local ontology.

As mentioned before, we also tackled the similar problem of catalog integration. An approach, besides E-NB, is to con­ struct the abstract-level structure of two hierarchies [Ome­ layenko and Fensel, 2001]. This approach does not direct the transformation of source and target information, but trans­ forms via the abstract-level structure. It is relatively easy to transfer information through many hierarchical structures, but it is hard to create a common structure for those hierarchies.

The bookmark-sharing systems of Siteseer [Rucker and Polanco, 1997] and Blink [Blink, 2000] also deal with a similar problem. These systems attempt to share URL in­ formation which appears in the source bookmark but not in the target bookmark. These systems flatten the categoriza­ tion of bookmarks in the same manner as NB and deter­ mine the mapping of categories in each bookmark, based on the shared URL information. Such systems are problematic when a given URL does not fit into an exact category. kMe­ dia [Takeda eta/., 2000] is another bookmark-sharing system that uses hierarchical structures explicitly, but is dependent on the similarity of the words within pages.

In the context of information retrieval, Stucken­ schmidt [Stuckenschmidt, 2002] has coordinated the formal model of hierarchies with multiple classification hierarchies. In our paper, since the upper and lower boundaries of concept mapping can be determined by subsumption relationships, we can infer the boundary of valid mapping and also check whether or not the given mapping is consistent. In our problem, since we have only partial evidence of classes and do not know the definitions of classes, we can not apply this method directly.

4 Learning the Relationship between Categories of Two Internet Directories

In this section, we explain our method to determine the rela­ tionship between categories in two Internet directories. One characteristic of the proposed method is to use the hierarchi­ cal structure "as is." We use all categories including inter­ mediate categories and leaf categories, because information for categorization can also be obtained from these categories. Another characteristic of the proposed method is the exclu­ sive reliance on the categorization structure of both directo­ ries, i.e., with no reliance on the semantic information of the documents. We can determine the relationship between cat­ egories of the two directories by statistically comparing the membership of the documents to the categories.

4.1 Basic Concept

Although E-NB was developed for a very similar problem, it is missing an important feature: categorization hierarchy. According to [Agrawal and Srikant, 2001], the initial defini­ tion of the problem is identical to that of this paper. However, the previous paper assumes that "any documents assigned to an interior node really belong to a conceptual leaf node that is a child of that node," and concludes from this assumption that "we can flatten the hierarchy to a single level and treat it as a set of categories." However, the conclusion overlooks the categorization hierarchies. The categorizations are not in­ dependent of each other. The categorization hierarchies are usually structured using an "is-a" or another relationship. If a document is categorized in a lower category in the categoriza­ tion hierarchy, then the document should also be categorized in the upper categories 2 · If we flatten the categories, such in­ formation regarding the relationships between categories will be lost.

Another problem associated with NB is its sensitivity to the words in documents. For example, if a document con­ tains the word bank, the category for the document could be a financial category; however, the category could also be a construction category. The quality of categorization with NB is thus not stable according to the contents of documents, due to the natural language techniques of processing words. It is critical to integrate Internet directories because mixing re­ liable Internet directories maintained by human editors with less reliable and less stable machine-generated classifiers will confuse users and decrease their confidence. In addition to the problem of sensitivity, analysis of a document to extract words is expensive.

Our method focuses on the similarity of the way of catego­ rization, not the similarity of documents. Then, how do we measure the similarity of categorization? We utilize shared documents in both the source and target Internet directories as our measurement standard. If many documents in category Csi also appear in category Ctj at the same time, we consider these two categories to be similar, because the ways of cate­ gorization in Csi and Ctj are supposed to be similar, i.e., if another document D comes in Csi, it is likely that D will be also included in Ctj. This method avoids both the keyword extraction process and the handling of word meaning. The example shown in Figure 2 illustrates that documents in the bottom category in the source Internet directory can be trans­ ferred to a similar category in the target Internet directory.

2 Note that the reverse is not always true, because documents can be categorized into intermediate categories.

4.2 ~~:-Statistic

The remaining problem is how to determine the pairs of simi­ lar categories. We adopt a statistical method to determine the degree of similarity between two categorization criteria. The ~~:-statistic method [Fleiss, 1973] is an established method for evaluating the similarity between two criteria. Suppose there are two categorization criteria, Csi in Sv and Ctj in Tv. We can determine whether or not a particular document belongs to a particular category 3 . Consequently, documents are di­ vided into four classes, as shown in Table 1. The symbols Nu, N12, N21 and N22 denote the numbers of documents for these classes. For example, N11 denotes the number of doc­ uments which belong to both Csi and Ctj· We may logically assume that if categories Csi and Ctj have the same criterion of categorization, then N12 and N21 are nearly zero, and if the two categories have a different criterion of categorization, then Nu and N22 are nearly zero. The ~~:-statistic method uses this principle to determine the similarity of categoriza­ tion criteria.

In the ~~:-statistic method, we calculate the probability P, which denotes the percentage of coincidence of the concep­ tual criteria, and the probability P', which denotes the per­ centage of coincidence of the conceptual criteria by chance.

3 Remember that categorization in a directory is determined using the nodal structure of the categorization hierarchy.

As such, the value of the ~~:-statistic is represented as the following equation:

Next, we examine whether we can assume the 11: = 0, which indicates that the percentage of coincidence for the two conceptual criteria is zero. We therefore calculate the test statistic Z according to the following equation.

The value Z follows a normal distribution. A null hypothe­ sis is considered to occur when the percentage of coincidence of the concept criteria is zero. When we assume a signifi­ cance level of 5% and the following equation is satisfied, we can dismiss the null hypothesis.

When the null hypothesis can be dismissed, the criteria are determined to be the same.

4.3 Determination of Pairs of Similar Categories

The relationship between the two categorization criteria is ex­ amined from top to bottom. This algorithm is shown in Fig­ ure 3. First, the most general categories in the two catego­ rization hierarchies are compared using the ~~:-statistic. If the comparison confirms that the two categories are similar, then the algorithm outputs this pair of categories. At the same time, the algorithm generates all possible pairs of their chil­ dren categories. It generates two lists of categories each of which is a list of the confirmed category and its children cat­ egories. Then, the algorithm picks one category from each list and makes a pair, except for the original pair. This new pair is then evaluated recursively using the ~~:-statistic method. When a similar pair is not generated, the algorithm outputs the pairs of similar concepts between the two categorization hierarchies. They are used as mapping rules from the source directory to the target directory 4 .

This top-down comparison approach attempts to reduce the exploration space, using the structure of both directories as a guide. Assuming that similar categories include similar sub­ categories, we can skip the combination of categories which is likely unnecessary 5 . This is another benefit of using the "as is" hierarchy, in contrast to the flattening approach.

4 The rules do not guarantee the consistency of the mappings, because category hierarchies have the possibility of inconsistency with regard to similar relationships.

4.4 Application Policy of Rules

Since the proposed method uses categorization similarity, if a category in the source Internet directory does not have a similar category in the target directory, then those documents cannot be categorized in the target Internet directory. In order to avoid this problem, we once again use the categorization hierarchy. If the system cannot find a similar category pair for the category containing the document, it applies the rule generated for the parent category instead.

5 This assumption may sometimes be too strong, e.g., a child cat­ egory of a category is not so relevant, whereas its child category (a grandchild category of the original category) is relevant. In such cases, we should relax this constraint when exploring future candi­ dates.

4.5 Computational Complexity

In this section, we discuss the computational complexity of the proposed algorithm shown in Figure 3. Suppose that two concept hierarchies SD and TD are trees of width b (the num­ ber of subcategories for each category) and height d (the num­ ber of categories from top to bottom) for the sake of simplic­ ity. In this case, we calculate the total number of categories N using the following equation:

Comparison of the similarity among all categories requires N x N comparisons. As a result, the order of computational complexity is O(b 2 d).

Next, we consider the cost of our algorithm. Assuming that after the similarity tests using K-statistic have been con­ ducted, n% of the tests are confirmed to be similar to other categories. The number of pairs produced by make_comb is (b + 1? - 1 because it makes pairs from the two lists, each pair of which consists of the category itself and its child categories, except for the original pair. The number of ex­ pected combination pairs after processing of the K-statistic is n(b 2 + 2b) + (1- n) · 0. The second halfofthe formula (1- n) · 0 is applied because no similar pair is produced when the K-statistic does not confirm the similarity. We finally ob­ tain the total number of nodes M to be compared as the prod­ uct of the number of examined nodes and the expected num­ ber of nodes. M is given by the following equation:

The order of complexity is then obtained as O(ndb 2 d) = O((nb 2 )d). Since n denotes the percentage of category pairs confirmed to be similar, 0 :::; n :::; 1 is satisfied. As a result, we obtain less computational complexity using the algorithm in Figure 3. In other words, although the depth remains the same, the search algorithm can reduce computation by con­ straining the breadth size.

5 Experiments Using Internet Directories

5.1 Experimental Settings

In order to evaluate the proposed algorithm, we conducted experiments using data collected from the Yahoo! [Yahoo!, 2001] and Google [ Google, 2001 ] 6 Internet directories. The data was collected in the fall of 2001. In order to compare the proposed method to that in [Agrawal and Srikant, 2001 ], we selected the same locations in Yahoo! and Google for the experimental data. The locations are as follows:

• Yahoo! : Recreation I Automotive Google : Recreation I Autos
• Yahoo! : Entertainment I Movies_and_Film Google : Arts I Movies
• Yahoo! : Recreation I Outdoors Google : Recreation I Outdoors

6 Since the data in Google is constructed by the data in dmoz [dmoz, 2001], we collected data through dmoz.

• Yahoo! : Arts I VisuaLArts I Photography Google : Arts /Photography
• Yahoo! : Computers_andJ:nternet I Software Google : Computers I Software

Table 2 shows the numbers of categories, the links in each Internet directory and the links included in both Internet di­ rectories. Links are considered to be the same when the URLs in both directories are identical.

We conducted ten-fold cross validations for the shared links. The shared links were divided into ten data sets; nine of these sets were used to construct rules, and the remaining set was used for testing. Ten experiments were conducted for each data set, and the average accuracy is shown in the re­ sults. In order to compare our proposed method to the E-NB approach, the classifiers are assumed to correctly assign doc­ uments when the document is categorized either in the same category as the test data or in the parent categories of the test data. E-NB constructs classifiers for only the first-level cat­ egories in the experimental domain, whereas the proposed method uses all of the categories from top to bottom. The significance level for the K-statistic was set at 5%.

5.2 Experimental Results

The experimental results are shown in Tables 3 and 4. Ta­ ble 3 shows the results obtained using Yahoo! as the source Internet directory and Google as the target Internet directory, and Table 4 shows the results obtained using Google as the source Internet directory and Yahoo! as the target Internet directory. For comparison, these tables also include the re­ sults of [Agrawal and Srikant, 2001]. E-NB denotes the method of [Agrawal and Srikant, 2001] and SBI denotes the similarity-based integration method that is proposed in this paper. The data obtained for the proposed method and that presented in [Agrawal and Srikant, 2001] are not truly com­ parable because the collection date is different?.

The proposed algorithm did well compared to E-NB, per­ forming more than 10% better in accuracy on the averages. In the Movies domain, the proposed algorithm performs much better in accuracy than E-NB. One reason for this is that the pages related to movies contain various words that indicate numerous movie settings, making classification using word­ based systems difficult. On the other hand, in the Outdoors domain, performance is similar for both methods because the Outdoors domain treats pages using special outdoors-related words, and no classification method for the Outdoors domain has been established for human readers.

7 In addition, differences may have occurred due to data selec­ tion. For example, Yahoo! has links that use @(the at mark). The treatment of such links was not discussed in [Agrawal and Sri kant, 2001] . In the present study, we did not use such links.

As mentioned earlier, in the experiments described in [Agrawal and Srikant, 2001 ], the classifiers induced by the system have the ability to classify the documents into only the first-level categories of the test domain in the target Internet directory. The proposed classifiers can classify the documents into sub-categories as well. For example, we used 4,623 cat­ egories for document assignment in the Movies domain of Yahoo! as the source Internet directory and Google as the tar­ get Internet directory, whereas their system used only 40 cat­ egories. Therefore, the classifiers obtained by the proposed method are more reliable and useful than those obtained by other methods.

Next, we compare our method with GLUE [Doan eta!., 2002]. The basic steps of GLUE are as follows. First, the user trains learners for each concept for target taxonomies. Learn­ ers can be a combination of different strategies like name- or contents-based learning. Then, they determine that the source concept and target concept are similar, if the application of learners for the source concept yields good enough. Finally, the system applies the relaxation labeling method for simi­ lar concept pairs. The method does not use the hierarchical structures in learning very well, and relies mainly on the per­ formance of the learning method, namely NB. On the other hand, our method does use hierarchical structures in learning very well. So, we do not need a semantical analysis in learn­ ing. They report an accuracy of 65-95% which is equivalent to our results, but they use only a few categories, i.e., 40-363, while we use 170-4623 categories. We can say from both theoretical and practical viewpoints that our method is more appropriate in learning for large hierarchical structures.

6 Conclusions

In this paper, a statistical-based technique was proposed for integrating multiple Internet directories by determining the relationship between these directories. The proposed method uses the ~~:-statistics to find similar category pairs, and trans­ fers the document categorization from a category in the source Internet directory to a similar category in the target Internet directory. The proposed method has an advantage in document treatment in that it relies on the category struc­ ture only, and not on words or word similarity in a docu­ ment. The performance of the proposed method was tested using actual Internet directories, and the results of these tests show that the performance of the proposed method was more than 10% better in accuracy than that of previous methods, although the number of categories were by far larger for our proposed method. In addition, our problem modeling is more general than the other models in terms of assignment docu­ ments on intermediate categories. From this, we can conclude our approach shows great promise in comparison to systems employing NB, such as E-NB [Agrawal and Srikant, 2001], GLUE [Doan eta!., 2002], and so on.

Although the present results are encouraging, much has yet to be done. The limitation of the proposed method is that this method is based on the existence of shared links. In other words, the proposed method is less reliable if there are fewer shared links. To improve our proposed method, various methods might be used to obtain semantic informa­ tion in order to increase the number of shared links, e.g., to regard similar pages as the same links. Another option for this problem might be to combine semantic information or other information about the documents. If we could a es­ tablish good combination of our proposed method and such information, it is possible that we could greatly improve our method. Moreover, the present method can find only one-to­ one mapping rules. If the system is able to find one-to-many or many-to-many mappings, it would work more correctly in categorization. For the development of these mappings, we might invent probabilistic mapping representations and also introduce a subsumption technique [Stuckenschmidt, 2002]. Finally, the proposed method should be expanded so that it can apply to more than three concept hierarchies. In such a case, despite the conflict between several concept hierar­ chies, we would expect more information to be obtained. The aforementioned tasks for improvement will be investigated in future studies.