Exploiting Structural Information for Text Classication on the WWW Johannes Furnkranz Austrian Research Institute for Articial Intelligence Schottengasse 3, A-1010 Wien, Austria juffi@ai.univie.ac.at Abstract. In this paper, we report on a set of experiments that ex- plore the utility of making use of the structural information of WWW documents. Our working hypothesis is that it is often easier to clas- sify a hypertext page using information provided on pages that point to it instead of using information that is provided on the page itself. We present experimental evidence that conrms this hypothesis on a set of Web-pages that relate to Computer Science Departments. 1 Introduction The advent of the World-Wide Web has rejuvinated the interest in text catego- rization problems. Vast amounts of documents are available on-line, and catego- rizing them into meaningful semantic categories is a rewarding and challenging research problem. However, current approaches to text categorization on the Web mostly con- centrate on simple representation schemes that are based on word occurrence and word frequency. The structural information that is inherent to documents on the Web is often neglected. There are at least two dierent kinds of struc- tural information on the Web that could be used to enhance the performance of current text classication algorithms: { the structure of an HTML representation which allows to easily identify important parts of a document, such as its headings and its title, and { the structure of the Web itself, where pages are linked to each other in various ways. In this paper, we report on a set of experiments that explores the utility of such structural information. Our working hypothesis is that (at least in some domains) it is easier to classify hypertext pages using information provided on pages that point to a page instead of using information that is provided on the page itself. There are several reasons for this: Redundancy: Quite often there is more than one page pointing to a single page on the Web. The ability to combine multiple, independent sources of information can improve classication accuracy. Independent Labeling: Being able to rely on the information provided by multiple authors (the authors of the pages that point to the page to be classied) is less sensitive than having to rely on the vocabulary used by one particular author [11]. Page Sparseness: Web pages are often very sparse or contain mostly images. Using the links to a page increases the chances of encountering informative text about the page to classify. To investigate our hypothesis, we represent a Web page with features derived from information of pages that point to the page. To that end, we encode each hyperlink pointing to a document with its anchor text, the headings structurally preceding it, and the text of the paragraph in which it occurs. Then we learn a set of classication rules with the inductive rule learning algorithm RIPPER [1]. The predictions of links pointing to the same page are then combined to yield a prediction for this page. Our results show that documents can often be classied more reliably with in- formation originating from pages that point to the document than with features that are derived from the document text itself. 2 Motivation Our approach for the use of structural information for classifying Web-pages was motivated by the following observation that we made while working with conventional text classication techniques on the WebKB data set.1 Observation 1: The text on the pages themselves is often insucient or irrelevant for a reliable classication. For example, home pages of computer science departments often only consist of images with pointers to information about oered courses, student and faculty home pages, research projects, etc. Even if this information is contained on a single page, the words on the page itself do not provide many clues for the fact that we are dealing with the home page of a computer science department as opposed to any other page in a computer science department. Observation 2: Information on the pages that contain a pointer to a given page is much more helpful. Very often, at least one of the following three pieces of information contains an obvious clue for the intended classication of the page. 1. the anchor text 2. the context in which the anchor text appears 3. the headings that structurally precede the section of the document in which the link occurs For example, department pages typically have a large number of links point- ing to them that are marked with anchor texts that include phrases like \com- puter science department", \CS department", \dept. of computer science", or 1 A brief description of this domain can be found in section 5 similar. Each of them should be sucient to identify the link as pointing to the page of a computer science department. Student home pages very often contain a pointer to their advisor's home page. Thus, faculty home pages can often be identied by the occurrence of the word \advisor" in the neighborhood of a link that points to the page. Furthermore, many computer science departments have a page that lists all students, faculty, sta, projects, courses, or other informa- tion. Typically such a page (or segment of a page) starts with a heading that identies the type of information that is listed below it. Clearly, this information can also be very useful for classifying the pages that the list items below this heading point to. 3 Document Representation In order to capture its structural information, we represented a document in the followingway. First, the entire text of the document itself was discarded. Instead, we identied a set of pages that contain a pointer to the current page.2 Each of these pages was turned into a separate training example using the following pieces of information: Anchor: All words that occurred in the anchor text of the link (between the opening <A ...> and the closing </A> of the HTML link). Heading: All words that occurred in headings that structurally precede the hyperlink in the HTML document. This means a heading of type <Hi> is included i it appears before the hyperlink and no heading of type <Hj> with j  i appears in the segment between the heading and the hyperlink. Page titles and titles for denition lists (<DT>) were also included as headings (with i = 0 and i = 7 respectively). Paragraph: All words of the paragraph in which the hyperlink occurs. Our method for determining the paragraph is somewhat heuristic and certainly not perfect. Pieces of text separated by <P> or an empty line are paragraphs, as are structural entities such as items in a list <LI>. The three features described above were each encoded as a separate set-valued feature [2] for the separate-and-conquer rule learner Ripper [1], which achieves noise-tolerance through an extension of incremental reduced error pruning [7]. A set-valued feature may be viewed as an ecient encoding of a group of binary features that correspond to the occurrences of words in the document. We will also refer to set-valued features as feature sets and use the terms feature and word interchangeably. Each training example was labelled with the appropriate class information, which is the class of the page the link points to. 2 We did this by scanning a collection of pages of Computer Science departments for all occurrences of an HREF that contains the address of the current page. In principle, this could also be performed on-line using a search engine like AltaVista that allows to query for pages that point to a given address. 4 Voting Schemes As discussed above, the training sets for Ripper consist of one example for each hyperlink. From such a set, Ripper induces a set of unordered rules3 that discriminate the examples of each class from the examples of all other classes. At prediction time, Ripper selects among all rules that re for a given example the one that has the highest condence associated with it and uses it to classify the example. Quite frequently, however, several links point to the same page. As our goal is to the predict the class of a page (and not of each individual link) we can try to exploit the redundancy that is provided by such multiple links. In order to do so, we have to device strategies for combining the predictions of all hyper- links pointing to a page into a single prediction for the class of the page. We implemented the following ve straight-forward techniques: Voting (Vote (all)): The simplest technique is to give each link that points to a page one vote, and predict the class that receives the most votes. Ties are broken in favor of larger classes. Links that are classied using the default rule learned by RIPPER (i.e., the rule specifying that if no other rule applies, predict the majority class among all unexplained examples in the training set) are eligible to vote. Restricted Voting (Vote): It is reasonable to assume that there will always be a few links that are classied by the default rules. Thus we implemented another version of the voting scheme, where votes of such links are ignored and only links that were classied by non-default rules are eligible to vote. If a page only receives votes from default rules, it is classied with the majority class. Weighted Sum (Weight): We also associate a condence score with each of RIPPER's predictions, which simply consists of the Laplace-estimate p+1 p+n+2 of the probability that an example covered by the rule is positive (estimated on the training set). If the prediction originates from a default rule, it is assigned a score of 0. Such a score is computed for each possible class of each link. The Weight voting scheme simply returns the sum of all weights as the condence score of the prediction. Weighted Normalized Sum (Norm): This voting scheme is identical to the previous one, except that the condence scores are rst normalized in a way that distributes a total weight of 1 among the dierent candidate classes for each link. This is necessary because the condence score that is associ- ated with each class only depends on the number of positive and negative examples covered by the best rule that predicts this class and covers the example. Therefore the condence scores associated with each class cannot be interpreted as class probability estimates unless they are normalized. 3 We have also experimented with ordered rule sets, but the results were usually a little worse. Besides, in \ordered" mode, Ripper treats one class as the default class and does not learn rules for that class. Maximum Condence (Max): The last combinationmethod simply chooses the class prediction that receives the highest score over all links that point to the page to classify and predicts that class. This is an attempt to use only the most accurate of all applicable rules to classify a page. From a Machine Learning perspective, the problem can be viewed as com- bining the predictions for dierent training examples, for which it is known that they have the same class label. To the extent to which the predictions of the classier for dierent training examples are independent of each other (which roughly corresponds to the extent to which the feature vector representation of the examples dier), it can be expected that combining the predictions may yield a performance gain [5]. 5 Experimental Setup We performed a series of experiments on 1050 pages of the WebKB domain. These pages are classied into one of the categories Student , Department , Fac- ulty , Research Project , Research Associate, Post Doc, and Course. Within these pages, 5803 hyperlinks point to another page within this set. Each of these is turned into a separate training example using the set-valued features described above. The pages/links were collected from four universities. All reported results are from a 4-fold leave-one-university-out cross-validation, i.e., for each experiment we combined the examples of three universities to learn a classier which was then tested on the data of the fourth university. Because of the dierent test set sizes for each of the four results, we used micro-averaging for evaluating the accuracy of the predictors, i.e., we lumped the predictions from all four runs together and computed an accuracy measure on the entire set of predictions. More details on the experimental setup can be found in [8], while the dataset is described in [4]. 6 Results 6.1 Page Accuracy Table 1 shows the accuracies measured for predicting the page labels. The rows list the dierent representation schemes, starting from the default prediction ac- curacy (using no features), to the classier that uses all features. The columns of the table give the accuracy for each of the 5 implemented prediction combination techniques, starting with the voting scheme including default prediction, voting without default prediction, normalized weighted average, weighted average, and nally the maximummethod (see section 4). In terms of representation, it becomes apparent that using additional feature sets will generally result in higher accuracies. The exception to the rule is the Paragraph feature set. Whenever its features are added to a representation that Combination Method Classier Vote (all) Vote Normal Weight Max Default 51.81 51.81 51.81 51.81 51.81 Anchor 67.52 74.67 74.38 74.19 74.76 Headings 60.48 72.29 72.38 72.95 72.95 Paragraph 63.05 66.86 66.86 66.95 66.29 Anchor+Headings 74.48 85.33 84.95 85.14 86.57 Anchor+Paragraph 68.00 74.29 74.00 73.90 74.67 Headings+Paragraph 70.48 79.90 80.19 81.14 81.33 All 74.19 82.29 81.71 82.67 83.24 Table 1. Accuracies for classifying the 1050 pages using various methods for combining link predictors to page predictors. already includes the Anchor features, the result is a loss of predictive accuracy. A reason for this might be that these two feature sets are much less independent of each other than other pairs of feature sets.4 The best results were achieved when relying only on the anchor text and the information from the headings. Among the ve dierent techniques for combining the link predictions to a page prediction, taking the prediction with the maximum condence is a clear winner. In 7 out of 8 runs, using this method gave the best results (shown in bold face). However, in general, the dierences among the combination methods are not nearly as large as the dierences among the dierent document representa- tions. The only exception is the voting scheme that also allowed the default rule to vote (rst column of table 1). Apparently, the learned rules have a fairly low coverage, so that many of the links have to be classied using the default rule. It happens quite frequently that a few good rules are outnumbered by a number of default predictions. We have also found that the performance deteriorates simi- larly when default predictions are included into the weighted prediction combiner (results not shown). The maximum technique remains mostly unaected by this because it is unlikely that a default prediction receives the maximum condence score among a number of competing link predictions (results also not shown). 6.2 Link Accuracy One question that remains unanswered by table 1 is how much has actually been gained by combining the prediction of dierent links pointing to a single page. To investigate this question, we computed a weighted accuracy estimate by weighting each page with the number of links that point to that page. In 4 Note, however, that even though the set of words occurring on the anchor text is a subset of the set of words occurring in its surrounding paragraph, the result- ing Anchor feature set is not a subset of the resulting Paragraph feature set be- cause the feature x occurs in anchor text is semantically dierent from the feature x occurs in paragraph, the former being more specic than the latter. Combination Method Encoding No Vote(all) Vote Normal Weight Max Default 36.67 36.67 36.67 36.67 36.67 36.67 Anchor 57.92 58.80 75.93 75.56 75.37 76.05 Headings 43.34 40.01 66.62 69.89 70.77 64.33 Paragraph 53.40 55.09 65.91 65.81 66.33 58.59 Anchor+Headings 62.49 61.66 86.18 85.46 86.25 83.22 Anchor+Paragraph 58.40 59.23 73.70 73.67 73.46 71.81 Headings+Paragraph 58.50 56.69 78.67 78.98 80.30 76.63 All 57.99 61.43 79.15 77.74 79.44 79.20 Table 2. Accuracies for classifying the 5803 links with various predictor combination methods. other words, all links that point to the same page perform an internal vote to decide upon a common classication for the page they point to. Each link of such a group is then classied with this common label. The resulting accuracy estimate counts the number of correctly predicted links over all links, and can thus be directly compared to the accuracies of the base classiers that predict the class labels of each link independently. These results are shown in table 2. The rst thing to note is a substantial dierence between the independent classier (rst column) and the classiers that rely on combining the predictions for dierent links for all methods except voting with inclusion of default predictions. Obviously, many mistakes could be corrected by combining the predictions of dierent links and thus being able to rely on good features that appeared in a dierent link pointing to the same page. Secondly, the dierences between the voting scheme that includes default predictions (second column) and the voting schemes that ignore them is more remarkable than in table 1. We explain this with the fact that for pages with many incoming links, there are good chances that many of the links are classied by default rules, and that the combination of these predictions overrides the few \educated" guesses. With the voting schemes that ignore default predictions, the situation is the opposite: A few correct rule-base classications can override many wrong default classications and thus gain substantially in accuracy. It is also interesting to observe that in table 2, the Max prediction method (last column) is not as dominant as in table 1 and, in some cases, it performs substantially worse than its competitors. The reason for this is that the maximum prediction is much less susceptible to variations in the number of link predictions that are combined to a single page prediction. If an erroneous link prediction has the maximumcondence score, it is used for predicting the class of the page. The voting and weighting methods, on the other hand, can make use of a number of unanimous predictions with lower condence scores to override a prediction with a higher condence score. Thus, it can be expected that pages with a higher number of incoming links are classied more reliably by voting or weighting, Recall Precision Classier Vote Normal Weight Max Anchor 40.76 83.64 82.30 82.48 83.88 Headings 74.10 88.05 88.19 88.95 88.95 Paragraph 46.67 75.71 75.91 75.92 74.49 Anchor+Headings 85.90 92.35 91.91 92.13 93.79 Anchor+Paragraph 60.19 83.23 82.81 82.59 83.86 Headings+Paragraph 82.38 88.44 88.79 89.94 90.17 All 78.00 86.94 86.20 87.42 88.16 Table 3. Recall and Precision for the page predictors. Recall is the percentage of pages that are not classied with the default rule and Precision is how many of these classications were correct. while pages with a lower number incoming links are better classied by taking the prediction with the maximum score. As the latter category is more frequent, the page accuracies tend to be higher for the maximumprediction method, while the link accuracies tend to be higher for the voting and weighting schemes. 6.3 Recall and Precision We have discussed above that many of the test examples are classied using the default rule and that it seems to be advisable to ignore these default link predictions for computing the page predictions. But what happens in cases where all links that point to a page are classied by default rules, i.e., no link contains any information that could be used for a justied prediction? In the experiments reported in the previous section, we have simply predicted the majority class Student for each of these pages. What if we ignore these predictions? It can be expected that the classication accuracy goes up at the expense of classifying fewer pages. This trade-o is commonly measured in terms of precision and recall. Table 3 lists recall and precision estimates that shed some light upon this question. Recall is the percentage of pages which were classied using at least one rule dierent from the default rule. Note that this estimate is the same for all combinationmethods because the underlying link classiers are the same and hence the links that are classied with default rules are the same. Precision is the percentage of classied pages that were correctly classied. In general, the precision scores are much higher than the accuracy results of table 1. This is not surprising because accuracy can be viewed as a weighted sum between the precision on the recalled examples and the precision on the examples classied by default rules (which should be about the default accuracy, although the variance can be very high). The recall scores are more dierentiated. Headings features not only have the highest, but also achieve this precision at signicantly higher recall scores. Classier # Features Accuracy Link-Based 8,075 85.05% Full-Text 20,322 70.67% Table 4. Accuracy and number of fea- tures for using feature subset selection on the full-text classier. # Features Accuracy 100% 70.67 50% 73.90 10% 74.19 5% 74.76 1% 71.33 0.1% 54.67 Table 5. Accuracy results for feature subset selection on the full-text classi- er. 6.4 Comparison to full-text classier We also compared the predictive accuracies of the link-based page classiers to those of a classier that uses the words occurring on the page as a feature. Ta- ble 4 shows a comparison between the link-based classier using all four feature sets and a full-text classier in terms of predictive accuracy and the number of features used by both representations.5 The link-based classiers discussed in this paper are considerably more accurate while using less than half of the number of features. An obvious question at this point is, of course, whether the dierences in accuracy are at least partly due to the dierent number of features. Could we produce a similar eect by employing feature subset selection on the full-text classier? We have already seen, that in general, adding additional feature sets improves accuracy. On the other hand, it is also known that too many features can lead to overtting. Table 5 shows the results for using only the top n% of the features of the full-text classier (selected by entropy). Feature subset selection results in some improvement, but the best result is still more than 10% behind the link-based classiers. We have not checked whether feature subset selection would improve the link-classiers as well. 7 Conclusion Our results show that it is possible to classify documents more reliably with in- formation originating from pages that point to the document than with features that are derived from the document text itself. Furthermore, it proved to be benecial to be able to exploit redundant information on the WWW by combin- ing multiple predictions (one for each hyperlink pointing to a page). However, we have shown this for one domain only, so our results can only be considered as preliminary. More experimental work in other domains must be conducted in order to establish a conclusive result. 5 The reported number of features is the total number of features in the entire dataset. Each of the four training sets of the cross-validation contained on average a little more than 80% of the features for both types of classiers. Although the encoding scheme we used is quite straight-forward, it illustrates that the use of information about the HTML structure of pages and about the structure of the WWW itself can be useful for improving text categorization on the WWW. The use of more elaborate representation schemes (e.g., distin- guishing dierent types of headings or even using an entire HTML-tree [6] as background knowledge) suggests itself as a rewarding topic for further research as does the use of relational learning techniques (see, e.g., [3,10]). We have al- ready performed preliminary experiments using linguistic phrases of the kind used in [9] as an additional feature set, but found that they did not make much dierence [8]. Such approaches also need to be investigated in more detail. Acknowledgements This work was performed during the author's stay at Carnegie Mellon University, which was enabled by a Schrodinger-Stipendium (J1443-INF) of the Austrian Fonds zur Forderung der wissenschaftlichen Forschung (FWF). The author has beneted greatly from discussions with Mark Craven, Tom Mitchell, and Ellen Rilo. Thanks to the CMU text learning group for making the WebKB dataset available, in particular to Dayne Freitag and Tom Mitchell for providing a pre-processed version. References 1. William W. Cohen. Fast eective rule induction. In A. Prieditis and S. Russell, editors, Proceedings of the 12th International Conference on Machine Learning (ML-95), pages 115{123, Lake Tahoe, CA, 1995. Morgan Kaufmann. 2. William W. Cohen. Learning trees and rules with set-valued features. In Proceed- ings of the 13th National Conference on Articial Intelligene (AAAI-96), pages 709{716. AAAI Press, 1996. 3. Mark Craven. Using statistical and relational methods to characterize hyperlink paths. In D. Jensen and H. Goldberg, editors, Articial Intelligence and Link Analysis: Papers from the 1998 AAAI Fall Symposium, pages 14{20, Orlando, Florida, 1998. AAAI Press. Technical Report FS-98-01. 4. Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam, and Sean Slattery. Learning to extract symbolic knowledge from the World Wide Web. In Proceedings of the 15th National Conference on Articial Intelligence (AAAI-98). AAAI Press, 1998. 5. Thomas G. Dietterich. Machine learning research: Four current directions. AI Magazine, 18(4):97{136, 1997. 6. Dan DiPasquo. Using HTML structure to aid in automatic information retrieval from the world wide web. Senior Honors Thesis, School of Computer Science, Carnegie Mellon University, May 1998. 7. Johannes Furnkranz. Pruning algorithms for rule learning. Machine Learning, 27(2):139{171, 1997. 8. Johannes Furnkranz. Using links for classifying web-pages. Technical Report OEFAI-TR-98-29, Austrian Research Institute for Articial Intelligence, 1998. 9. Johannes Furnkranz, Tom Mitchell, and Ellen Rilo. A case study in using linguis- tic phrases for text categorization on the WWW. In M. Sahami, editor, Learning for Text Categorization: Proceedings of the 1998 AAAI/ICML Workshop, pages 5{12, Madison, WI, 1998. AAAI Press. Technical Report WS-98-05. 10. Sean Slattery and Mark Craven. Combining statistical and relational methods for learning in hypertext domains. In D. Page, editor, Proceedings of the 8th International Conference on Inductive Logic Programming (ILP-98), pages 38{52, Madison, WI, 1998. Springer-Verlag. 11. Ellen Spertus. ParaSite: Mining structural information on the Web. Computer Networks and ISDN Systems, 29(8-13):1205{1215, September 1997.