Web Page Cleaning for Web Mining through Feature Weighting

1 Introduction

The rapid expansion of the Internet has made Web a popular place for disseminating and collecting information. However, useful information on the Web is often ac­ companied by a large amount of noise such as banner ads, navigation bars, copyright notices, etc. Although such information items are functionally useful for human viewers and necessary for Web site owners, they can se­ riously harm automated information collection and mining on the Web, e.g., Web page clustering, Web page classification, and information retrieval. Web noise can be grouped into two categories based on their granularities:

Global noise: It refers to redundant objects with large granularities, which are no smaller than individual pages. Global noise includes mirror sites, duplicated Web pages and old versioned Web pages to be deleted, etc.

Local (intra-page) noise: It refers to irrelevant items within a Web page. Local noise is usually incoherent

Bing Liu

Department of Computer Science University of Illinois at Chicago 851 S. Morgan Street Chicago, IL 60607 liub@cs.uic.edu

with the main content of the page. Such noise includes banner ads, navigational guides, decoration pictures, etc. This work focuses on dealing with local noise in Web pages. We call it Web page cleaning. The work is chal­ lenging because it is a non-trivial task to decide which part of a Web page is meaningful and which is noisy. Despite its importance, relatively little research has been done on Web page cleaning so far (see Section 2). In this paper, we propose an effective feature weighting technique to clean Web pages with the purpose of improving Web mining. Our method does not decide and physically remove those noisy blocks of a page. Instead, it assigns low weights to the features in those possibly noisy blocks. The advantage of our method is that there is no need to use a threshold to determine whether a block is noisy or not. Setting a suit­ able threshold is very hard in practice.

Our cleaning technique is based on the following ob­ servation. In a typical commercial Web site, Web pages tend to follow some fixed layouts and presentation styles as most pages are automatically generated. Those parts of a page that also appear in many other pages in the site are more likely to be the noise, and those parts of the page that are quite different from other pages are usually the main content of the page. To capture the common structure and comparable blocks among Web pages, we introduce the compressed structure tree to compress or to merge a set of Web pages from a Web site. We then propose a measure that is based on information theory [Shannon, 1948] to evaluate each element node in the compressed structure tree to determine the importance of the node. Based on the tree and node importance values, our method assigns a weight to each word feature in its content block. These feature weights are then directly used in Web mining.

Our experimental results based on two popular Web mining tasks, i.e., Web page clustering and classification, demonstrate that the proposed cleaning technique is able to boost the mining accuracy significantly. For example, in classification, the average classification accuracy over all our datasets increases from 0.785 before cleaning to 0.951 after cleaning.

2 Related Work

Although Web page cleaning IS an important problem, relatively little work has been done to deal with it. In [Lin and Ho, 2002], a method is proposed to detect informative blocks in Web pages. Their concept of informative blocks is similar to our concept of main contents of a page. However, the work in [Lin and Ho, 2002] is limited by the following two assumptions: (I) the system knows a priori how a Web page can be partitioned into coherent content blocks; and (2) the system knows a priori which blocks are the same blocks in different Web pages. As we will see, partitioning a Web page and identifying corresponding blocks in different pages are actually two critical problems in Web page cleaning. Our system is able to perform these tasks automatically. Besides, their work views a Web page as a flat collection of blocks, and each block is viewed as a collection of words. These assumptions are often true in news Web pages, which is the domain of their applications. In general, these assumptions are too strong.

In [Bar-Yossef and Rajagopalan, 2002], Web page cleaning is defined as a frequent template detection problem. They propose a frequency based algorithm to detect templates or patterns. Their work is not concerned with the context of a Web site, which can give useful clues for page cleaning. Moreover, in their work, the partition­ ing of a Web page is pre-fixed, which is not suitable for a Web site because a Web site typically has common layouts and presentation patterns. We can exploit these common patterns to partition Web pages and to clean them.

Other related work includes data cleaning for data mining and data warehousing (e.g., [Lee, et a!., 2000]). However, they are only concerned with structured data. Web page data are semi-structured, and thus require dif­ ferent cleaning techniques.

Web page cleaning is also related to feature selection in traditional text learning (see [Yang and Pedersen, 1997] for a survey of feature selection techniques). In feature selection, features are individual words or attributes. However, items in Web pages have some structures, which are reflected by their nested HTML tags. Hence, different methods are needed in the context of the Web.

[Kushmerick, 1999] proposes some learning mecha­ nisms to recognize banner ads, redundant and irrelevant links of Web pages. However, these techniques are not automatic. They require a large set of manually labeled training data and also domain knowledge to generate classification rules.

[Kao et a!., 2002] enhances the HITS algorithm of [Kleinberg, 1998] by using the entropy of anchor text to evaluate the importance of links. It focuses on improving HITS in order to find informative structures in Web sites. Although it segments Web pages into content blocks to avoid unnecessary authority and hub propagations, it does not detect or eliminate noisy contents in Web pages.

Our work is also related to segmentation of text docu­ ments, which has been studied extensively in information retrieval. Existing techniques roughly fall into two cate­ gories: lexical cohesion methods [Beeferman eta!., 1997; Eichman eta!., 1999; Kaufmann, 1999; Reynar, 1999] and multi-source methods [Allan eta!., 1998; Beeferman eta!.,

1999]. The former identifies coherent blocks of text with similar vocabulary. The latter combines lexical cohesion with other indicators of topic shift, such as relative per­ formance of two statistical language models and cue words . In [Hearst and Plaunt, 1993], Hearst and Plaunt discussed the merits of imposing structure on full-length text documents and reported good results of using local structures for information retrieval. Instead of using pure text, which is unstructured, we process semi-structured data. We can make use of the semi-structures present in Web pages to help our cleaning task.

Finally, our feature weighting method is different from feature weighting methods used in information retrieval. One of the popular methods used in text information re­ trieval for feature weighting is the TFIDF scheme [Salton and McGill, 1983; Baeza-Yates and Bibeiro-Neto, 1999]. This scheme is based on individual word (feature) counts within a page and among all the pages. It is, however, not suitable for Web pages because it does not consider Web page structures in determining the importance of each content block and consequently the importance of each word feature in the block. For example, a word in a navigation bar is usually noisy, while the same word oc­ curring in the main part of the page can be very important.

3 The Proposed Technique

The proposed cleaning technique is based on analysis of both layouts (structures) and contents of the Web pages in a given Web site. Thus, our first task is to find a suitable data structure to capture and to represent common layouts or presentation styles in a set of pages of the Web site. We propose the compressed structure tree (CSI) for this pur­ pose. Below, we start by giving an overview of the DOM (Document Object Model) 1 tree and showing that it is insufficient for our task. We then present the compressed structure tree, which is followed by our entropy measures for evaluating the nodes in the compressed structure tree for noise detection.

3.1 DOM tree

Each HTML page corresponds to a DOM tree where tags are internal nodes and the actual text, images or hyperlinks are the leaf nodes. Figure 1 shows a segment of HTML codes and its corresponding DOM tree. In the DOM tree, each solid rectangle is a tag node. The shaded box is the actual content of the node, e.g., for the tag IMG, the actual content is "src=image.gif'. The order of child tag nodes is from left to right. Notice that our study of HTML Web pages begins from the BODY tag nodes since all the viewable parts are within the scope of BODY. Each tag node is also attached with the display properties of the tag. Display properties defined by CSS (Cascading Style Sheet) 2 are treated as normal display properties if CSS is avail­ able in the page source (i.e., if CSS is not external). For convenience of analysis, we add a virtual root node without any attribute as the parent tag node of BODY tag node in each DOM tree.

1 http: //www.w3.org/DOM/

2 http://www.w3 .org/Stvle/CSS/

Although a DOM tree is sufficient for representing the structure of one HTML page and it has been used in many applications (e.g., [Chakrabarti et a/., 2001 ]), it cannot represent the common structure of a set of Web pages . We aim to compress individual DOM trees of Web pages into a single tree (compressed structure tree) which captures the commonalities of the pages in a Web site. Based on this tree, we can easily study some statistical properties of the structures and the contents of the Web pages.

3.2 Compressed structure tree (CST)

Before defining the compressed structure tree, we first define the presentation style of a tag node in a DOM tree.

Definition (presentation style): The presentation style of a tag node Tin a DOM tree, denoted by Sr, is a sequence <r1, r2, ... , rn>, where ri is a pair (Tag, Attr) specifying the ith child tag node ofT.

• Tag is the tag name, e.g., "TABLE" and "IMG";
• Attr is the set of display attributes of Tag, e.g., bgcolor =RED, width= 100, etc.

n is the length of the style. For example, in Figure 1, the presentation style of tag node BODY is <(TABLE, {width=800, height=200} ), (IMG, {width=800} ), (TABLE, {bgcolor=red} )>.

We say two presentation styles Sa:< raJ, ra2, ... , ram> and Sb:< rb~o rb2· ... , rbn> are equal, i.e., Sa= Sb, iffm =nand rai·Tag= rbi·Tag and rai·Attr = rbi·Attr, i = 1, 2, ... , m.

An element node (the basic information unit) of a compressed structure tree (CST) is defined as follows:

Definition (element node): An element node E represents a set of merged tag nodes in the DOM tree. It has 5 components, denoted by (Tag, Attr, TAGs, STYLEs, CHILDs), where

• Tag is the tag name;
• Attr is the set of display attributes of Tag.
• TAGs is the set of actual tag nodes in the original DOM trees that are compressed (or merged) in E.
• STYLEs is the set of presentation styles merged into E.
• CHILDs is the set of pointers pointing to the child element nodes of E in CST.

An example of compressed structure tree is given in Figure 2, which compresses the DOM trees d1 and d2. We observe that, except for the tag node SPAN, all the tag nodes in d1 are merged with corresponding tag nodes in d2· So, an element node in CST actually denotes a set of merged tag nodes, which represents a set of logically comparable blocks in different DOM trees.

Tag nodes in different DOM trees cannot be merged randomly. We need to ensure that the merged tag nodes are the same logical blocks in different Web pages. We build a CST of a set of Web pages from a Web site by merging their DOM trees from top to bottom in following steps:

1. All root tag nodes of the DOM trees are merged to form the first (the top most) element node of the CST. We have Tag= root, Attr = {}, and TAGs being the set of all the root tag nodes in the DOM trees of the Web pages.
2. We compute STYLEs of the element node E passed from the previous step. E. STYLEs is the set of presen­ tation styles of all the tag nodes in the DOM trees covered by E. Note that common presentation styles are combined.
3. All the corresponding child tag nodes of those (tag nodes) in E. TAGs with the same presentation style are merged, which form the initial child element nodes of E. However, we want to further merge these initial child element nodes. For any pair of initial child element nodes E1 and E2, if their respective Tags and Attrs are the same, we compare their textual contents to see whether they are similar and can be merged. Let the characteristic feature (or word) set of Ej.TAGs be Jj = {featurek I freq(jeaturek) ;:::; y, featurek occurs in textual contents of Ej.TAGs}, where)= 1, 2.freq(jeaturek) is the document frequency ofjeaturek within Ej.TAGs and yis a predefined constant between 0 and 1. If lljl > 0 (j = 1, 2) and II,nhl/111 U 1212: A., then E1 and E2 are merged to form a new element node (E1 and E2 are deleted). The new element node is inserted into the set of initial

child element nodes. The merging step ends when no pair of child element nodes can be merged. In our ex­ periments, we set y = 0.85 and A.= 0.85, which perform very well.

1. If no child element node is created in step 3, stop; else for each child element node from step 3, goto step 2.

After the CST is built, it is used to compute a weight for each word feature in each block of a Web page.

3.3 Weighting policy

Intuitively, if an element node contains many different presentation styles, it is more likely to be important and hence should be assigned a high weight. Otherwise, it will be assigned a low weight, i.e., it is more likely to be noisy.

We use the entropy of presentation styles to encode the importance of an element node E in the CST.

Definition: For an internal element node E in CST, let I= IE.STYLEsl and m = IE.TAGsl. The importance of E, denoted by Nodefmp(E), is

where p; is the probability that a tag node in E. TAGs uses the ith presentation style.

For example, in CST of Figure 2, by equation 1, we obtain Nodefmp(root) = -llog21 = 0 since the root element node has only one presentation style. For the BODY element node, Nodefmp(BODY) = -(0.5/og20.5 + 0.5/og20.5) = 1.

A leaf node is treated differently from an internal node since it contains the actual words or features without any tag. We define its importance to be the averaged impor­ tance of the actual word features in it.

Definition: For a leaf element node E in CST, let N be the number of features present in E, the importance of E is:

where a; is a feature of the content in E and He(aJ is the information entropy of a; within E, which is

where m = IE.TAGsl, and pij is the probability that a; appears in thejth tag node of E. TAGs.

Nodefmp(E) only evaluates local importance of E. In order to weigh a feature contained in a leaf node of a CST, we use the cumulative importance of the path from root to the node containing the feature. We call this cumulative im­ portance of E the path importance, denoted by Pathfmp(E). Pathfmp(E) measures the importance of the structure from root to E in CST.

Since the path importance is a cumulative importance value, it should meet the following requirement:

• For any two element nodes E1 and E2 in CST, if E1 is an

ancestor of E2, then 1'2:Pathlmp(E2) C.Pathfmp(E1) ?.0. We define the path importance of an element node E in a CST as follows.

Definition: For an element node E in a CST, the path importance of E, denoted by Pathfmp(E), is:

where E; is an ancestor of E orE itself in the CST.

Our weighting policy considers both the structure and content context of the features. The weight of each feature in a particular block (or under a particular tag) of the Web page is computed as follow.

Definition: For a feature a; in a leaf element node E of a CST, the weight of a; under the tag node T; of the DOM tree of a Web page (i .e., T; E E. TAGs), denoted by WE(a;, T;), is defined by

where fij is the frequency of a; under tag T; of the page.

In our implementation, we do not use the actual leaf tag nodes in a page as they overly fragment the page. Instead, we use the grandparent tag nodes of the actual leaf tag nodes in the DOM tree as the (virtual) leaf tag nodes in building CST, and in computing feature weights.

After a weight to each feature in every block of a Web page is assigned, we add the weights of the same feature in the page. All the feature weights of the page together form a feature vector of the page, which is used as input to Web mining, e.g., clustering and classification.

4 Empirical Evaluation

This section evaluates the proposed cleaning technique. Since the purpose of our data cleaning is to improve Web mining, we performed two mining tasks, i.e., clustering and classification, to test our system. By comparing the mining results before cleaning and after cleaning, we show that our Web cleaning technique is able to boost mining accuracy dramatically.

Below, we first describe the datasets used in our ex­ periments and the evaluation measures. We then present our experimental results of clustering and classification.

4.1 Datasets and evaluation measures

Our empirical evaluation is done using Web pages from 5 commercial Web sites, Amazon 3 , CNet 4 , PCMag 5 , J&R 6 and ZDnet 7 · These sites contain many introduction or overview pages of different kinds of products. In order to guide users and/or to show advertisements, these Web pages all contain a large amount of noise. We will see that the noise mislead mining algorithms to produce poor resuits (in both clustering and classification).

3 http://www.amazon.com/

4 htto://www.cnet.com/

5 http://www.pcmag.com/

6 http://www.jandr.com/

7 http://www.zdnet.com/

All the five Web sites contain Web pages of many categories or classes of products. We choose the Web pages that focus on the following categories of products: Digital Camera, Notebook, TV, Printer and Mobile Phone. Table 1 lists the number of documents that we downloaded

from each Web site, and their corresponding classes.

Since we test our system using clustering and classifi­ cation, we use the popular F score measure in information retrieval to evaluate the results before and after cleaning. F score is defined as follows :

where p is the precision and r is the recall. F score meas­ ures the performance of a system on a particular class, and it reflects the average effect of both precision and recall . We will also include the accuracy results for classification.

4.2 Experimental results

We now report our experimental results before and after cleaning. Cleaning is done on all the Web pages from each Web site separately using the proposed technique.

Clustering

For clustering, we use the popular k-means algorithm

[Anderberg, 1973]. We put all the 5 categories of Web pages into a big set, and use the k-means clustering algo­ rithm to cluster them into 5 clusters. Since the k-means algorithm selects the initial seeds randomly, we performed a large number of experiments (800) to show the behaviors of k-means before and after page cleaning. The F score for each of the 800 runs is drawn in Figure 3, where X-axis shows the experiment number and Y -axis shows the F score. F score for each run is the average value of the 5 classes, which is computed as follow: By comparing the pages' original classes and the clustering results, we find the optimal assignment of class to each cluster that gives the best average F score for the 5 classes.

From Figure 3, we can clearly observe that after clean­ ing the results are drastically better. Over the 800 runs, the average F score for the noise case is 0.506, while the av­ erage F score for the clean case is 0.756, which is a remarkable improvement.

After cleaning, 84.38% of the 800 results have F scores higher than 0.7, and only 4.63% lower than 0.5. Before cleaning, only 0.5% of the 800 results ( 4 out of 800) have F scores higher than 0.7, and 47.63% lower than 0.5. Thus, we can safely conclude that our feature weighting tech­ nique is highly effective for clustering.

Classification

For classification, we use Support Vector Machine (SVM), which has been shown to perform very well for text classification by many researchers (e.g., [Joachims 1997]). We used the SVMiight package [Joachims, 1999] for all our experiments.

In each experiment, we build classifiers based on two classes of pages from different Web sites. For example, the two classes can be camera pages from Amazon and notebook pages from CNet. Then we use the classifier to classify the combined set of camera and notebook pages from the other Web sites. We have experimented with all possible two class combinations of the 5 sites. Table 2 gives the averaged F scores and accuracies before and after cleaning. In the table, F(N) and A(N) stand for F score and accuracy before cleaning respectively, while F(C) and A(C) stand for F score and accuracy after cleaning. From the results, we can see that after cleaning, the classifiers perform much better. On average over all the experiments, both the F score and accuracy improve by a large margin.

5 Conclusions

In this paper, we proposed an effective technique to clean Web pages for Web mining. Observing that Web pages in a Web site usually share some common layouts and pres­ entation styles, we propose a new tree structure, called compressed structure tree to concisely capture the com­ monalities of a Web site. This tree provides us with rich information for analyzing both the structure and the con­ tents of the Web pages. An information based measure is also proposed to evaluate each tree node to determine its importance, which is then used to assign weights to fea­ tures in their corresponding Web pages. Using the re­ sulting feature weights, we can perform Web mining tasks. Experimental results with two popular Web mining tasks show that the proposed technique is highly effective.