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

關鍵詞：Trawling算法 web 數(shù)據(jù)挖掘 結構挖掘

0 引言

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

1 Web數(shù)據(jù)結構挖掘

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

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

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

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

2 基于有向二分圖的Trawling算法在Web結構挖掘的應用

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

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

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

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

參考文獻：

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

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

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