楊　焰

摘要：在Web信息檢索中，如何能夠提取出與某個(gè)主題信息相關(guān)的網(wǎng)頁(yè)變得異常重要，web結(jié)構(gòu)挖掘作為web數(shù)據(jù)挖掘的一個(gè)重要方面，主要挖掘web潛在的鏈接結(jié)構(gòu)模式，通過(guò)分析一個(gè)網(wǎng)頁(yè)鏈接和被鏈接數(shù)量以及對(duì)象來(lái)建立web自身的鏈接結(jié)構(gòu)模式，可以用于網(wǎng)頁(yè)歸類，本文探討了Trawling算法在Web結(jié)構(gòu)挖掘中的應(yīng)用。

關(guān)鍵詞：Trawling算法 web 數(shù)據(jù)挖掘 結(jié)構(gòu)挖掘

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們?cè)絹?lái)越多地在互聯(lián)網(wǎng)上發(fā)布和獲取信息。web已經(jīng)成為信息制造、發(fā)布、加工和處理的主要平臺(tái)，其涵蓋的信息面之廣闊、信息量之豐富、都使得它毫無(wú)疑問(wèn)地成為當(dāng)前最大的信息資源庫(kù)。隨著海量信息涌入萬(wàn)維網(wǎng)，互聯(lián)網(wǎng)中特有的許多問(wèn)題，諸如超大規(guī)模的非結(jié)構(gòu)化文檔數(shù)量、良蕎不齊的網(wǎng)頁(yè)質(zhì)量，包含在文檔中的大量多媒體信息，甚至相當(dāng)含糊或不規(guī)范的用戶查詢表示等，必然給檢索數(shù)據(jù)帶來(lái)很大的困難。因此，在Web信息檢索中，如何能夠提取出與某個(gè)主題信息相關(guān)的網(wǎng)頁(yè)變得異常重要。將傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)跟web結(jié)合起來(lái)，進(jìn)行web挖掘活動(dòng)將更有效的從web中抽取感興趣的、潛在的、有用的信息。web挖掘是一項(xiàng)綜合技術(shù)，涉及了統(tǒng)計(jì)學(xué)、人工智能、模式識(shí)別、并行計(jì)算、機(jī)器學(xué)習(xí)、數(shù)據(jù)庫(kù)等多個(gè)領(lǐng)域。web結(jié)構(gòu)挖掘作為web數(shù)據(jù)挖掘的一個(gè)重要方面，主要挖掘web潛在的鏈接結(jié)構(gòu)模式，通過(guò)分析一個(gè)網(wǎng)頁(yè)鏈接和被鏈接數(shù)量以及對(duì)象來(lái)建立web自身的鏈接結(jié)構(gòu)模式，可以用于網(wǎng)頁(yè)歸類，并且可以由此獲得有關(guān)不同網(wǎng)頁(yè)間相似度及關(guān)聯(lián)度的信息，有助于用戶找到相關(guān)主題的權(quán)威站點(diǎn)。

1 Web數(shù)據(jù)結(jié)構(gòu)挖掘

1.1 web數(shù)據(jù)挖掘 web數(shù)據(jù)挖掘起源于數(shù)據(jù)挖掘，數(shù)據(jù)挖掘(Data Mining)是指從大型數(shù)據(jù)庫(kù)的數(shù)據(jù)中提取人們感興趣的知識(shí)，而這些知識(shí)是隱含的、事先未知的、潛在的有用信息。數(shù)據(jù)挖掘的提出最初是針對(duì)大型數(shù)據(jù)庫(kù)的，但是從更廣泛的角度來(lái)講，數(shù)據(jù)挖掘意味著在一些事實(shí)或觀察數(shù)據(jù)的集合中尋找模式的決策支持過(guò)程。因而，數(shù)據(jù)挖掘的對(duì)象不僅僅可以是數(shù)據(jù)庫(kù)，還可以是任何組織在一起的數(shù)據(jù)集合，如www信息資源等。WWW以超文本的形式給用戶提供了包含從技術(shù)資料、商業(yè)信息到新聞報(bào)道、娛樂(lè)信息等多種類別和形式的信息，可以說(shuō)是web當(dāng)今世界上最大的電子信息倉(cāng)庫(kù)，蘊(yùn)含著巨大潛在價(jià)值的知識(shí)。然而，Internet是一個(gè)具有開(kāi)放性、動(dòng)態(tài)性、異構(gòu)性的全球分布式網(wǎng)絡(luò)，資源分布分散，沒(méi)有統(tǒng)一的管理和結(jié)構(gòu)，這就導(dǎo)致了信息、知識(shí)獲取的困難，即所謂的Rich Data poor Information的問(wèn)題。因此，運(yùn)用現(xiàn)有數(shù)據(jù)挖掘技術(shù)對(duì)分布的、異構(gòu)的web信息資源進(jìn)行挖掘，就成為了數(shù)據(jù)挖掘技術(shù)的挑戰(zhàn)和未來(lái)的發(fā)展方向，由此產(chǎn)生了基于web的數(shù)據(jù)挖掘。web數(shù)據(jù)挖掘(web Data Mining)，簡(jiǎn)稱Web挖掘，是一項(xiàng)綜合技術(shù)，涉及web、數(shù)據(jù)挖掘、計(jì)算機(jī)語(yǔ)言學(xué)、信息學(xué)、數(shù)據(jù)庫(kù)技術(shù)等多個(gè)領(lǐng)域。web數(shù)據(jù)挖掘是針對(duì)包括web頁(yè)面內(nèi)容、頁(yè)面之間的結(jié)構(gòu)、用戶訪問(wèn)信息、電子商務(wù)信息等在內(nèi)的各種web數(shù)據(jù)源，在一定基礎(chǔ)上應(yīng)用數(shù)據(jù)挖掘的方法以發(fā)現(xiàn)有用的隱含的知識(shí)的過(guò)程。

1.2 Web數(shù)據(jù)結(jié)構(gòu)挖掘 在邏輯上可以把Web看作是位于物理網(wǎng)絡(luò)之上的一個(gè)有向圖G=(V，E)，其中節(jié)點(diǎn)集V對(duì)應(yīng)于Web上的所有文檔，而有向邊集E則對(duì)應(yīng)于節(jié)點(diǎn)之間的超鏈接(Hyperlink)。對(duì)節(jié)點(diǎn)集作進(jìn)一步的劃分，V={Vi，Vj}所有的非葉節(jié)點(diǎn)Vij是HTML文檔，其中除了包括文本以外，還包含了標(biāo)記以指定文檔的屬性和內(nèi)部結(jié)構(gòu)，或者嵌入了超鏈接以表示文檔間的結(jié)構(gòu)關(guān)系。葉節(jié)點(diǎn)Vi可以是HTML文檔，也可以是其他格式的文檔。Web上信息的多樣性決定了Web知識(shí)發(fā)現(xiàn)的多樣性，當(dāng)前Web上的信息主要分為三類:①Web頁(yè)面中的內(nèi)容，包括文本信息和各種多媒體信息；②Web頁(yè)面中超鏈接之間相互引用的數(shù)據(jù)；③Web服務(wù)器上的用戶登錄網(wǎng)站的訪問(wèn)日志數(shù)據(jù)。

由此Web數(shù)據(jù)挖掘可以分為Web內(nèi)容挖掘(web Content Mining)、web結(jié)構(gòu)挖掘(Web Strueture Mining)、Web使用挖掘(Web usage Mining)三大類（圖1）。

Web結(jié)構(gòu)挖掘即挖掘Web潛在的超鏈接結(jié)構(gòu)模式，通過(guò)分析一個(gè)網(wǎng)頁(yè)鏈接和被鏈接數(shù)量以及對(duì)象來(lái)建立Web自身的鏈接結(jié)構(gòu)模式。這種模式可以用于網(wǎng)頁(yè)歸類，并且由此可以獲得有關(guān)不同網(wǎng)頁(yè)間相似度及關(guān)聯(lián)度的信息，幫助用戶找到相關(guān)主題的權(quán)威站點(diǎn)。Web結(jié)構(gòu)挖掘的主要內(nèi)容在于超鏈接分析，即通過(guò)分析頁(yè)面的鏈接關(guān)系來(lái)研究網(wǎng)頁(yè)的引用關(guān)系。超鏈接分析最早被用于搜索引擎，它的基本原理就是通過(guò)統(tǒng)計(jì)分析互聯(lián)網(wǎng)上哪些頁(yè)面被鏈接的次數(shù)多，那么該網(wǎng)頁(yè)就被認(rèn)為是比較重要的頁(yè)面或者權(quán)威頁(yè)面(Authority Pages)。與傳統(tǒng)的搜索引擎使用的基于詞頻統(tǒng)計(jì)的查詢結(jié)果排序算法相比，基于超鏈接分析的算法的優(yōu)勢(shì)在于它提供了一種客觀的、不容易作弊(一些Web文檔通過(guò)增加不可見(jiàn)的字符串用來(lái)欺騙傳統(tǒng)搜索引擎)的Web資源評(píng)價(jià)方法。Web結(jié)構(gòu)挖掘還應(yīng)用于網(wǎng)站架構(gòu)上，一個(gè)架構(gòu)完善的網(wǎng)站可以提高使用者瀏覽的興趣、吸引更多的使用者上線瀏覽。此外，Web結(jié)構(gòu)挖掘還可以用于對(duì)Web頁(yè)進(jìn)行分類，預(yù)測(cè)用戶的鏈接使用以及鏈接屬性的可視化，對(duì)各個(gè)商業(yè)搜索引擎的Web頁(yè)數(shù)量進(jìn)行統(tǒng)計(jì)分析等。

2 基于有向二分圖的Trawling算法在Web結(jié)構(gòu)挖掘的應(yīng)用

拖網(wǎng)(trawling)算法是建立在web頁(yè)面上集心頁(yè)面與權(quán)威頁(yè)面的二分圖關(guān)系上的。它從二分有向圖的角度對(duì)互聯(lián)網(wǎng)上的社給出了一種明確的定義描述。根據(jù)隨機(jī)二分圖的理論，一個(gè)足夠大而稠密的隨二分圖將以很高的概率包含一個(gè)完全二分有向圖，那么如果將某個(gè)社區(qū)的鏈接構(gòu)看作一個(gè)大而稠密的二分有向圖，則社區(qū)的核就可以用一個(gè)完全二分有向圖complete bipartite graph)來(lái)表示。具體到互聯(lián)網(wǎng)環(huán)境中，可以對(duì)上述概念有如下觀的理解:如果在互聯(lián)網(wǎng)上存在一個(gè)某種主題的社區(qū)，那么這種二分的核必將含在其中。一個(gè)二分有向圖是這樣一個(gè)圖:圖Kij的節(jié)點(diǎn)集合可以被分為兩個(gè)集合，用(ran)和c(center)來(lái)表示。集合F中有i個(gè)節(jié)點(diǎn)，集合C中有j個(gè)節(jié)點(diǎn)，并且合F中的每個(gè)節(jié)點(diǎn)到集合C中的每個(gè)節(jié)點(diǎn)都存在一條有向邊。拖網(wǎng)算法數(shù)據(jù)來(lái)源不是依據(jù)某個(gè)主題，而采用的是一般的爬取結(jié)果，通過(guò)掃描數(shù)據(jù)集合發(fā)現(xiàn)所有潛在的Fan集合，同時(shí)也確定了Center集合。然后通過(guò)重復(fù)的包含/排除剪枝得到所有的核，最后采用關(guān)聯(lián)規(guī)則挖掘算法(Priorial gorithm)聚類為較小規(guī)模的核的集合。最后，每個(gè)核就是一個(gè)社區(qū)。

拖網(wǎng)算法為:①獲取數(shù)據(jù)源，如web搜索結(jié)果的備分；②刪除所有重復(fù)或鏡像頁(yè)面，以防產(chǎn)生虛假網(wǎng)站核；③由于只考慮那些潛在的網(wǎng)站，所以刪去入度超過(guò)某一值(比如50)的所有）center；④考慮每一條邊，對(duì)于指定的有向完全二分圖的要求，或者產(chǎn)生一個(gè)相應(yīng)的網(wǎng)站核，或者刪除這條邊，無(wú)論如何，都將移去這條邊；⑤對(duì)于掃描到的較小規(guī)模的網(wǎng)站核，即有向完全二分圖，濾去那些fans中包含來(lái)自同一個(gè)域的多個(gè)fans的結(jié)果；⑥一個(gè)有向完全二分圖的任何真子集都是有向完全二分圖，通過(guò)aPriori算法發(fā)現(xiàn)所有更大規(guī)模的網(wǎng)站核；⑦對(duì)于找到的網(wǎng)站核，使用HITS算法將他們擴(kuò)展為真正的網(wǎng)站。HITS(Hypertext Indueed Topic Seareh)算法是關(guān)于超鏈接的檢索算法。該算法通過(guò)對(duì)網(wǎng)絡(luò)中超鏈接的分析，利用頁(yè)面的被引用次數(shù)及其鏈接數(shù)目來(lái)決定不同網(wǎng)頁(yè)的權(quán)威性。Hub和Anthority的關(guān)系可以用圖2來(lái)表示:

因此，一個(gè)Hub頁(yè)應(yīng)該指向許多好的權(quán)威頁(yè)，而被許多Hub頁(yè)指向的一定是權(quán)威頁(yè)。HITs算法中網(wǎng)頁(yè)的Anthority權(quán)重和Hub權(quán)重有相互增強(qiáng)的關(guān)系。HITS算法的實(shí)現(xiàn)過(guò)程:根據(jù)用戶查詢請(qǐng)求，首先用一個(gè)現(xiàn)有的商業(yè)搜索引擎進(jìn)行查詢，取其部分查詢結(jié)果(約200個(gè)左右)作為算法的根集(RootSet)，記為RQ。由于這些頁(yè)面中的許多頁(yè)面是假定與搜索內(nèi)容相關(guān)的，因此它們中應(yīng)包含指向最權(quán)威頁(yè)面的指針。所以，對(duì)RQ中每一個(gè)節(jié)點(diǎn)，將所有指向該節(jié)點(diǎn)或該節(jié)點(diǎn)所指向的網(wǎng)頁(yè)補(bǔ)充進(jìn)來(lái)形成基集(BaseSet)，記為BQ。計(jì)算BQ中每一個(gè)網(wǎng)頁(yè)的Anthority權(quán)重和Hub權(quán)重，這是一個(gè)遞歸的過(guò)程。

拖網(wǎng)算法中使用的共同引用過(guò)于嚴(yán)格而排除了一些可能的潛在網(wǎng)站，造成有用網(wǎng)站的遺漏。通過(guò)寬松引用(relaxed-cocited)重新定義了稠密二分有向圖和完全二分有向圖，使得一些原來(lái)被排斥在外的頁(yè)面包括進(jìn)來(lái)。拖網(wǎng)算法是針對(duì)整個(gè)Web爬取結(jié)果進(jìn)行的，因此，發(fā)現(xiàn)的網(wǎng)站較為完整。而且，拖網(wǎng)的結(jié)果是客觀的，與主題無(wú)關(guān)。

參考文獻(xiàn)：

[1]Gordons.Linoff Michael J.A.Berry等著.沈鈞毅，燕彩蓉等譯.Web數(shù)據(jù)結(jié)構(gòu)挖掘:將客戶數(shù)據(jù)轉(zhuǎn)化為客戶價(jià)值.北京.電子工業(yè)出版社.2004.

[2]秦拯，張玲，李娜.改進(jìn)的PagcRank在Web信息搜集中的應(yīng)用.計(jì)算機(jī)研究與發(fā)展.2006(6).

[3]高瑣，谷士文，唐璉.基于鏈接分析web社區(qū)發(fā)現(xiàn)技術(shù)的研究.計(jì)算機(jī)應(yīng)用研究.2006(07).