fdokumen.id

KAO ET AL.: MINING WEB INFORMATIVE STRUCTURES AND CONTENTS BASED ON ENTROPY ANALYSIS43Fig. 3. The linked graph of CDN (www.cdn.com.tw). Page numbers N 270 and total links L 1,515.Fig. 4. The reduced subgraph contains TOC and article pages: N 252 and L 350.Crawlers and Information Agents can focus on theinformative structure to precisely and efficientlyextract information for further analysis. Search Engines may index only the informative partsof an article page rather than indexing every page inthe whole Web site. As a consequence, we are able toreduce the index size and increase the retrievalprecision when the query terms match terms innonindexed redundant blocks. Previous researches on Web miners (informationextraction systems, e.g., WIEN [26], Stalker [31],IEPAD [16], and [35] expect the input Web pages topossess a high degree of regularity so that structuredinformation, e.g., metadata, encoded in these pagescan be retrieved. Informative structure is a key toautomatically locate target informative contentblocks containing useful repeated patterns in thewhole site.To illustrate the difficulty of the problem, we consider areal Web site in Fig. 3, which shows a small graph of a Website that contains only 270 pages and 1,515 links. The graphlooks like a messy “Web.” The graph shown in Fig. 4 is asubgraph (informative structure) extracted from the original graph in Fig. 3 based on manually labeling TOC andarticle pages of the Web site. That is the answer set of theinformative structure. This concise graph in Fig. 4 onlycontains TOC pages and the corresponding article pages,which excludes 76.8 percent of the links and 6.7 percent ofthe pages from the original graph. Fig. 4 consists of severaltrees whose root nodes are TOC pages. In this paper, wepropose methods to reduce complicated Web site structuressuch as the one in Fig. 3 into concise informative structuresas in Fig. 4.Explicitly, we propose in the paper mechanisms toautomatically discover informative structure of a Web siteand contents of pages to reduce intrasite redundancy. Wealso present an entropy-based analysis to estimate theinformation quality of links and content blocks. This newentropy measure is used in the approaches for discoveringinformative structure. In the rest of the paper, we firstpresent a literature survey on related studies of the paper inSection 2. In Section 3, we present a formal model on theproblem and develop our entropy-based analysis. Following the system design and implementation in Section 4, weperform several experiments on real data sets to evaluateour methods in Section 5. Finally, we conclude the paperand describe the direction of future research in Section 6.2RELATED WORKThe Hyperlink Induced Topics Search (HITS) algorithm [25]and Google’s PageRank [7] are widely applied to analyzethe structure of the Web. HITS estimates the authority andhub values of hyperlinked pages in the Web and Googlemerely ranks pages. Both methods are applied to rankingthe search result. Based on a mutual reinforcement relationship, HITS provides an innovative methodology for Websearching and topics distillation. According to the definitionin [25], a Web page is an authority on a topic if it provides

44IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,good information and is a hub if it provides links to goodauthorities. HITS uses the mutual reinforcement operationto propagate hub and authority values to represent thelinking characteristic. In recent research work on linkanalysis of hyperlinked documents, HITS is applied to theresearch area of topic distillation and several kinds of linkweights are proposed to enhance the significance of links inhyperlinked documents. In the Clever system [14], weightstuned empirically are added to distinguish same-site linksand others. In [3], the similarity between the document andthe linked document is taken as the link weight for analysis.Another study that uses the similarity between thesurrounding text of a link and the linked document todetermine the link weight is conducted in [13]. Consideringthe distribution of terms in documents, Chakrabarti et al.[11] combines the TFIDF-weighted model and microhub torepresent the significance of links in regions with information needed.Intuitively, HITS and its related methods applied to thetopic distillation are useful in the analysis of Webinformative structures. However, the topic distillation isdifferent from the informative structure mining in severalaspects:.The former distills hubs and authorities from a set ofpages retrieved from search engines with a givenquery. These pages are not restricted to be publishedfrom the same Web site. However, the latter minesthe informative structure from all pages of a givenWeb site. With different targets of data sets, studies of topicdistillation usually omit intralinks and nepotisticlinks to perform the mutual reinforcement betweensites. However, these links are important while thelink analysis is focused on a Web site. Most adaptive topic distillation algorithms based onHITS take the relationship between queries anddocuments into consideration. However, these algorithms do not work well on mining informativestructures because of the absent of a target query.Furthermore, as described in [12], [27], the linkanalysis algorithms, e.g., HITS, are vulnerable to theeffect of nepotistic clique attack and Tightly-KnitCommunity (TKC). This is caused by the reason thatthe values of hub and authority of nodes will be selfprompted by the mutual reinforcement propagations in a highly connecting community. The effectswill be more significant for mining informativestructures of Web sites since we observed thatnepotistic links and cliques appear more frequentlyin a Web site [24].Based on mining the informative structure of a Web site,the complex structure is reduced to a concise one. However,if we look into pages of the structure, many redundantcontent blocks are not meaningful for the pages content. In[20] and [23], studies provide learning mechanisms torecognize advertisements and redundant/irrelevant links ofWeb pages. However, these methods need to build thetraining data first and related domain knowledge must beincluded to extract features for generation of classificationrules. Therefore, both methods are difficult to be applied toVOL. 16,NO. 1,JANUARY 2004automatically extract the informative structures of systematic Web sites.Studies of Information Extraction (IE) [21], [22], [26], [35]aim to mine structure values (metadata) of pages from Websites. Although being able to extract valuable metadata frompages, most of these IE systems need labor-intensive work.Cardie [10] defines five pipelined processes for an IE system:tokenization and tagging, sentence analysis, extraction,merging, and template generation. Machine learning isusually applied to learn, generalize, and generate rules inthe last three processes based on manually generateddomain-specific knowledge such as concept dictionariesand templates. Training instances applied to learningprocesses are also artificially selected and labeled. Forexample, in Wrapper induction [26], the author manuallydefines six wrapper classes, which consist of knowledge toextract data by recognizing delimiters to match one or moreof the classes. The richer a wrapper class, the more likely itwill work with any new site [15]. SoftMealy [22] provides aGUI that allows a user to open a Web site, define theattributes and label the tuples in the Web page. Thecommon disadvantages of IE systems are the cost oftemplates, domain-dependent knowledge, or annotationsof corpora generated by hand. This is the very reason thatthese systems are merely applied to specific Web applications, which extract the structural information from pagesof specific Web sites or pages generated by CGI. Consequently, the general IE systems are not scalable and,therefore, cannot be applied to resolve the problem ofredundant content blocks in pages.3THE ENTROPY-BASED ANALYSISIn this section, we propose an entropy-based analysis toremedy the deficit of HITS-related algorithms. In light ofthis analysis, we devise two mechanisms to mine theinformative structure of a Web site. We first develop amechanism of analyzing the entropy of anchor texts andlinks, namely, Link Analysis of Mining Informative Structure (LAMIS), to reduce a complex Web site to a distilledconcise Web structure. Then, we devise another mechanismon analyzing the entropy of content blocks, namely,InfoDiscoverer, to identify informative (significant) contentblocks from pages in the concise structure.3.1LAMIS—Analyzing Entropy of Anchor Textsand LinksGiven an entrance of a Web site, HITS is applied to measurehub and authority values of all pages. Intuitively, a TOCpage is expected to have a high hub value, and an articlepage is to have a high authority value. That is, HITS isdesigned to provide a reasonable solution to mining theinformative structures of news Web sites. However, theexistence of redundant and irrelevant links usually causesthe phenomenon of topic drift in pages published insystematic Web sites. Therefore, the analysis of authorityand hub cannot solely depend on the linked structures withthe page granularity. We apply the entropy to measure thesignificance of anchor texts and page content while usingHITS on the link analysis. For example, when the linkentropy is applied to shrink the CDN graph shown in Fig. 3,

KAO ET AL.: MINING WEB INFORMATIVE STRUCTURES AND CONTENTS BASED ON ENTROPY ANALYSIS45Fig. 5. The graph of CDN: links with entropy values smaller than 0:8½N ¼ 241; L ¼ 569 .Fig. 6. The graph of CDN: links with entropy values smaller than 0:4½N ¼ 236; L ¼ 353 .the thresholds of entropy values, 0.8 and 0.4, reduce thatgraph to those shown in Fig. 5 and Fig. 6, respectively. Incomparison with the answer set shown in Fig. 4, Fig. 6reduced by the threshold 0.4 indeed approaches to theoptimal solution. Explicitly, the objective of our firstmechanism, LAMIS, is to reduce a complex graph to anoptimal subgraph that represents the informative TOC andarticle structure. The detail is described in the followingsections.3.2InfoDiscoverer—Analyzing Entropyof Content BlocksThe entropy-based analysis can further be applied toanalyze page content blocks and discover informativecontents from article pages clustered by LAMIS. Oursecond mechanism, InfoDiscoverer, standing for “discovering informative content blocks,” is designed to analyze theinformation measure of content blocks (in a page set) anddynamically select the entropy-threshold to classify a page’sblocks into either informative or redundant. By partitioninga page into blocks based on HTML tags, InfoDiscoverercalculates entropy values of features (i.e., terms, keywords,or phrases) according to the probability distribution offeatures in the page set. Entropy values of content blocksare derived from their features. Based on the answer setgenerated from 13 manually tagged news Web sites with atotal of 26,518 Web pages, experiments show that both recalland precision rates are greater than 0.956.Consequently, LAMIS applies the link entropy to discover the informative structure and InfoDiscoverer employsthe content entropy to determine the content property,informative or redundant. In the following, we describe thederivation of content and link entropy values. Then, wedevelop mechanisms to apply link entropy values toenhance the link analysis and mine the informativestructure.3.3The Entropy of Content and Link and EnhancedLink AnalysisThe text is an important clue for users to determine themeaning of a page. Therefore, we extract features (terms)from the page text to represent its corresponding significance. For the same reason, the anchor text is an importantclue for users to click the link. Therefore, we also extractfeatures (terms) from an anchor text to represent thesignificance of the link. In this paper, a term correspondsto a meaningful keyword. The idea is that featuresfrequently appearing in most pages are redundant andcarry less information to users. In contrast, features appearing in fewer pages are more informative. That is, we can

46IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,VOL. 16,NO. 1,JANUARY 2004apply the probability distribution of terms in pages toestimate the information measures of features. First, wecalculate the feature entropy and deduce the entropy valuesof content blocks and links.Given a set of HTML pages or a Web site, we canparse all pages into content blocks and links based onHTML tags. Also, texts appearing in contents and linkscan be parsed into a set of terms with correspondingblocks and links. In the page set, those features form afeature-document matrix with weights in matrix entries.The feature weight is calculated based on the calculationof feature frequency in the page set [29]. Then, Shannon’sinformation entropy [34] is applied to calculate thefeature entropy based on the feature-document matrix.By definition, the entropy E can be expressed asP ni¼1 pi log pi , where pi is the probability of eventi andn is number of events. By normalizing the weight of afeature to be [0, 1], the entropy of feature (term) Ti is:EðTi Þ ¼ nXwij log2 wij ;j¼1in which wij is the value of normalized feature frequency inthe page set. To normalize the entropy to the range [0, 1],the base of the logarithm is chosen to be the number ofpages, and the previous equation becomes:EðTi Þ ¼ nXwij logn wij ;where n ¼ jDj; D is the set of pages:Entropy values of content blocks and links are derived fromthe average of their features entropies. For the example ofcalculating the entropy of a content block, intuitively,feature entropies contribute to the semantic measure of acontent block that owns these features, i.e., the entropyvalue of a content block is the summation of its featuresentropies:kXAðvÞ ¼XHðuÞ uv and HðvÞ ¼ðu;vÞ2Ej¼1HðCBi Þ ¼Fig. 7. A simple Web site, jDj ¼ 5.EðTj Þ;j¼1where Tj is a feature ofCBi with k features:Since content blocks contain different numbers of features,the equation is normalized as:Pkj¼1 EðTj Þ:HðCBi Þ ¼kThat is, the entropy of a content block, HðCBÞ, is the averageof all feature entropies in the block. The link entropy ismeasured analogously.In the link graph of a Web site G ¼ ðV ; EÞ, HITSalgorithm computes two scores for each node v in V , i.e.,the hub score HðvÞ and the authority score AðvÞ by themutual reinforcement propagation between connectingnodes. In our approach, we incorporate entropy values oflinks as link weights to present the significance of links in aWeb site structure. Therefore, the original HITS algorithm ismodified as follows:XAðuÞ uv ;ðv;uÞ2Ewhere uv is the weight of the link from u to v, denotedANuv . According to the definition of entropy of a link, uv isdefined as follows: uv ¼ 1 EðANuv Þ:It can be seen that the more information a link carries, thelarger the link weight is, i.e., the lower the link entropy is.The weight uv can also be expressed as the average ofthe weights of features contained, i.e.,Pkj¼1 W ðTj Þ: uv ¼kAccording to the characteristic of the entropy, the weight offeature Tj , i.e., W ðTj Þ, is defined as W ðTj Þ ¼ 1 EðTj Þ. Theweight of a feature is similar to its inverse documentfrequency, IDF, which is defined as logn dfnj , where dfj is thedocument frequency of Tj . IDF is usually applied torepresent the discriminability of a term in a set ofdocuments. According to the definition, there are thefollowing relationships between W ðTj Þ and IDFj : 1) if Tjis uniformly distributed among some pages, W ðTj Þ ¼ IDFj ,and 2) if Tj is not uniformly distributed, then W ðTj Þ IDFjand the more skewed the distribution of Tj is, the largerW ðTj Þ is. The relationship 1) can be proven as follows:Relationship 1. If Tj is uniformly distributed among some ofpages, W ðTj Þ ¼ IDFj .Proof. Assume n ¼ jDj, tfj ¼ the total frequency of Tj , because Tj is uniformly distributed, tfij , i.e., the termtffrequency of Tj in pagei , is equal to dfjj . According to thedefinition of the entropy-based weighting,

KAO ET AL.: MINING WEB INFORMATIVE STRUCTURES AND CONTENTS BASED ON ENTROPY ANALYSIS47TABLE 1Entropy Values of Links Shown in Fig. 70W ðTj Þ ¼ 1 EðTj Þ ¼ 1 @ 1tfij AlogntfjtfjX tfijdfjand tfj ¼ tfij dfj . We then getW ðTj Þ ¼ 1 þ logn1n¼ logn¼ IDFj :dfjdfjWhen the distribution of Tj is more skewed, EðTj Þ willdecrease and W ðTj Þ will increase. The relationship 2) istherefore conformed.utBenefiting from these two relationships, the weight of aterm attained from the entropy value is more representativefor the importance of a term than from IDF. We will give thestatistical result on the real Web site in Section 4.1 to showthese relationships.Moreover, the SALSA proposed in [27] is designed toresist effects of TKC and cliques and we also apply entropyweights on SALSA to remedy the effects similarly. Theimprovement will be empirically evaluated by our experimental studies later.3.4 An Illustrated ExampleConsidering the example of a simple news Web site shownin Fig. 7, page P0 is the homepage of the Web site. Page P1 isthe TOC page with two anchors linking to news articlepages, P3 and P4 . Page P2 is an advertisement page linkedby the other four pages. Most pages contain anchor texts,i.e., “home,” “hot news,” and “sales,” linking to P0 , P1 , andP2 , respectively. P3 and P4 have anchors linking to eachother. It is regarded as a cross-reference to present therelated news. The Web site structure is also widely used incommercial Web sites. Based on the terms in each page, thefeature entropy of the Web site is calculatedas below:EðT0 Þ ¼ EðTi Þ ¼ 3X11log5 ¼ 0:682;33j¼12X25j¼12 1log5 ¼ 0:655;5 5EðT2 Þ ¼ EðT5 Þ ¼ 4X14j¼11log5 ¼ 0:861; and42X11log5 ¼ 0:430:EðT3 Þ ¼ EðT4 Þ ¼ 22j¼1The entropy values of links derived from featureentropies are listed in Table 1. According to the definitionof entropy, the most informative links are AN10 and AN11 ,which link to article pages P3 and P4 from TOC page P1 .Based on the link entropy, we use our entropy-basedHITS algorithm to calculate values of hub and authority. Incomparison with HITS shown in Table 2, hub and authorityvalues are obtained after 10 iterations. P1 is ranked as thetop 1 hub page by the entropy-based HITS, and P3 and P4are ranked with the highest authority. However, HITS ranksthe advertisement page (P2 ) as the best authoritative page,and news article pages (P3 and P4 ) as good hub ones. It canbe seen that the link entropy is effective to enhance the linksignificance in link analysis algorithms.4THE SYSTEM DESIGNIn this section, we will describe the design of LAMIS andInfoDiscoverer. The LAMIS system is designed to explorehyperlink information to extract and identify the hub (TOC)and authority (article) pages. InfoDiscoverer then measuresthe entropy values of content blocks among clustered pages(a set of article or TOC pages) and dynamically selects theentropy-threshold to extract informative content blocks.Given an entrance URL of a Web site, without manualinventions and prior knowledge about the Web site, LAMISand InfoDiscoverer are capable of crawling all pages,analyzing the structure, and extracting the informativestructures and content blocks of the site. In this section, wedescribe the system architecture and processes of LAMISand InfoDiscoverer.4.1 The System ArchitectureOur Web mining system, shown in Fig. 8, consists of threeparts:1.Web Crawler which crawls pages, parses them intoblocks, and builds the link graph of the Web site.2. Feature Extractor which extracts features (terms), indegrees, out-degrees, text lengths, and links asmetadata of pages. Feature Extractor also calculatesentropy values of features to derive entropies oflinks and content blocks.3. Informative structure mining module which iscomposed of LAMIS and InfoDiscoverer.First, a starting URL of a site is given to Crawler. Inour system, we can assign crawl depths to different pathsTABLE 2Results of Link Analysis of HITS and Entropy-Based HITS

48IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,VOL. 16,NO. 1,JANUARY 2004Fig. 9. 1-EN versus IDF for www.cnn.com.Fig. 8. The system architecture.(subtrees) of the site. Once a site has been crawled, apage is represented by

one month of online news articles are reachable through their Web links. Based on these rules, it suffices to index only 5 percent of their pages and the index size of their informative parts is about 12.14 percent of the original page size. This implies that a typical search en