一、 引言
資料採擷是將人工智慧技術和資料庫技術緊密結合發展出的一門新的技術，利用電腦從龐大的資料中智慧地、自動地抽取有價值的知識模式，以滿足人們不同應用的需要。隨著互聯網的普及和迅猛發展、Web上信息量的爆炸式增長, 網上的資源得到極大豐富, 但也充斥著大量的垃圾資訊, 人們迫切需要能從這些紛繁蕪雜的資訊中找到有用知識的工具。鑒於資料採擷工具的日益成熟完善, 人們自然而然想到了要把資料採擷技術應用到Web上來。
Web挖掘指在WWW 上挖掘潛在的、有用的模式及隱藏的資訊過程。根據對Web資料的感興趣程度不同，Web挖掘一般可以分為三類：Web內容挖掘（Web Content mining）、 Web結構挖掘（ Web structure mining）、 Web 用法挖掘（Web usage Mining）
其中Web 結構挖掘是對Web 的連結結構進行分析, 以對超連結分析來評估基礎Web 資源, 從而發現有用模式, 提高搜索品質。
二、 Web結構挖掘綜述
傳統的WEB搜尋引擎大多數是基於關鍵字匹配的，返回的結果是包含查詢項的文檔，也有基於目錄分類的搜尋引擎。這些搜尋引擎的結果並不令人滿意。有些網站有意提高關鍵字出現的頻率來提高自身在搜尋引擎中的重要性，破壞搜尋引擎結果的客觀性和準確性。另外，有些重要的網頁並不包含查詢項。搜尋引擎的分類目錄也不可能把所有的分類考慮全面，並且目錄大多靠人工維護，主觀性強，費用高，更新速度慢。
Web結構包括不同網頁之間的超連結結構和一個網頁內部的可以用HTML，XML表示成的樹開結構，以及文檔URL中的目錄路徑結構等。Web頁之間的超連結結構中包含了許多有用的資訊，當網頁A到網頁B存在一個超連結時，則說明網頁A的作者認為網頁B的內容非常重要，且兩個網頁的內容具有相似的主題。因此，指向一個文檔的超連結體現了該文檔的被引用情況。如果大量的連結都指向了同一個網頁，我們就認為它是一個權威頁。這就類似於論文對參考文獻的引用，如果某一篇文章經常被引用，就說明它非常重要。這種思想有助於對搜尋引擎的返回結果進行相關度排序。從WWW的組織結構和連結關係中推導知識。通過對Web網站的結構進行分析、變形和歸納，將Web頁面進行分類，分析一個網頁連結和被連結數量以及物件來建立Web自身的連結結構模式，確定不同頁面間的相似度和關聯度資訊。定位相關主題的權威網站，可以極大的提高檢索結果的品質。
基於這種超鏈分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank演算法，同年J. Kleinberg提出了HITS演算法，其它一些學者也相繼提出了另外的連結分析演算法，如SALSA，PHITS，Bayesian等演算法。這些演算法有的已經在實際的系統中實現和使用，並且取得了良好的效果。
三、 WEB結構挖掘常見演算法
1、 PageRank演算法
PageRank演算法是Web超連結結構分析中最成功的代表之一。該演算法由Stanford大學的Brin和Page提出，是評價網頁權威性的一種重要工具。搜尋引擎Google、Yahoo、Baidu都是利用該演算法和anchor text標記、詞頻統計等因素相結合的方法對檢索出的大量結果進行相關度排序，將最權威的網頁儘量排在前面。
1) PageRank基本原理
傳統情報檢索理論中的引文分析方法是確定學術文獻權威性的重要方法之一,即根據引文的數量來確定文獻的權威性。PageRank 的發明者對網路超連結結構和文獻引文機制的相似性進行了研究,把引文分析思想借鑒到網路文檔重要性的計算中來,利用網路自身的超連結結構給所有的網頁確定一個重要性的等級數,當從網頁A 連結到網頁B 時,就認為”網頁A 投了網頁B 一票”,增加了網頁B 的重要性。最後根據網頁的得票數評定其重要性,以此來?明實現排序演算法的優化,而這個重要性的量化指標就是PageRank 值。
但是網頁和學術上的出版文獻的差別是很大的。首先學術論文的出版發表非常的嚴格,而網頁的出版非常自由、成本很低並缺乏控制,用一個簡單的程式就可以產生大量的網頁和很多連結。另外學術出版物的引文一般和文章的領域有關係,而網頁的連結範圍領域卻很廣。可見簡單的連結數量計算並不能客觀真實地反映網頁的重要性,所以PageRank 除了考慮網頁得票數(即連結) 的純數量之外,還要分析為其投票的網頁的重要性,重要的網頁所投之票有助於增強其他網頁的“重要性”。簡單地說,PageRank 就是要從連結結構中獲取網頁的重要性,而網頁的重要
2) PageRank的實現
PageRank在具體實現時會忽略掉Web頁面上的文本和其它內容，只考慮頁面間的超連結，把Web看成是一個巨大的有向圖G =(V，E)，結點vI V代表一個Web頁面，有向邊(p,
q )I E代表從結點p指向結點q的超連結，結點p的出度是指從頁面p出發的超連結(outlink)的總數，而入度是指所有指向結點p的超連結(inlink)的總數。
PageRank的具體定義如下：將Web對應成有向圖，設W為該有向圖結點的集合，N=|W|， Fi是頁面i指向的所有頁面的集合，Bi是指向頁面i的所有頁面的集合。對每個出度為0的結點S，設FS ={有向圖中全部N個結點}，則所有其他結點的Bi={B E i S}，這樣可以將結點S所具有的PageRank值均勻地傳遞給其他所有頁面。PageRank的具體反覆運算公式為 。
其中，參數 d是 取值0到1之間的衰減因數，因為任何一個網頁的作者都認為其它的網頁不如自己的重要。d通常被置為0.85。
PageRank的實現過程為：將網頁的URL對應成唯一的整數，把每一個超連結用其整數ID存放到索引資料庫中，經過預處理(如去除資料庫中的懸擺指標)之後，設每個網頁的初
始PR值為1，通過以上的遞迴演算法計算每一個網頁的PageRank值，反復進行反覆運算，直至結果收斂。
2、 HITS演算法
1) HITS基本原理
Hill Top 演算法的指導思想和PageRank 是一致的，即都通過反相連結的數量和品質來確定搜索結果的排序權重。但超連結的應用存在著許多的潛在的問題，如大量的連結是為了導航(如“點擊此按鈕返回主頁”)或付費廣告而創建的。而出於商業競爭的原因，儘管內容相關，有些網站又不會把超連結指向他們的競爭對手(如：Cisco公司不會將超連結指向Sun公司的主頁)。
HITS演算法他認為網頁的重要性應該依賴於用戶提出的查詢請求。而且對每一個網頁應該將其authority權重(由網頁的outlink決定)和hub權重(由網頁的inlink決定)分開來考慮，通過分析頁面之間的超連結結構，可以發現以下兩種類型的頁面：
中心網頁（hub）：一個指向權威頁的超連結集合的Web頁
權威網頁（authority）：一個被多個Hub頁指向的權威的Web頁
中心網頁（hub）
權威網頁（authority）
HITS演算法發現，在很多情況下，同一主題下的權威網頁（authority），如上例所述Cisco和SUN，之間並不存在相互的連結。所以，權威網頁（authority）通常都是通過中心網頁（hub）發生關聯的。
HITS演算法描述了權威網頁（authority）和中心網頁（hub）之間的一種依賴關係：一個好的中心網頁（hub）應該指向很多好的權威性網頁（authority），而一個好的權威性網頁（authority）應該被很多好的中心性網頁（hub）所指向。
2) HITS的實現
HITS首先利用一個傳統的文本搜尋引擎(例如AltaVista)獲取一個與主題相關的網頁根集合(root set).然後向根集合中擴充那些指向根集合中網頁的網頁和根集合中網頁所指向的網頁,這樣就獲得了一個更大的基礎集合(base set).假設最終基礎集合中包含N 個網頁,那麼對於HITS 演算法來說,輸入資料就是一個N×N 的相鄰矩陣A,其中如果網頁i 存在一個連結到網頁j,則Aij=1,否則Aij=0。
HITS 演算法為每個網頁i 分配兩個度量值:中心度hi 和權威度ai.設向量a=(a1,a2, … ,aN)代表所有基礎集合中網頁的權威度,而向量h=(h1,h2, …,hN)則代表所有的中心度.最初,將這兩個向量均置為u=(1,1, … ,1).操作In(a)使向量a=ATh,而操作Out(h)使向量h=Aa.反復反覆運算上述兩個操作,每次反覆運算後對向量a 和h 範化,以保證其數值不會使計算溢出.Kleinberg 證明經過足夠的反覆運算次數,向量a 和h 將分別收斂於矩陣ATA 和AAT 的主特徵向量.通過以上過程可以看出,基礎集合中網頁的中心度和權威度從根本上是由基礎集合中的連結關係所決定的,更具體地說,是由矩陣ATA 和AAT 所決定
3、 其它演算法及歸類
連結分析演算法可以用來提高搜尋引擎的查詢效果，可以發現WWW上的重要的社區，可以分析某個網站的拓撲結構，聲望，分類等，可以用來實現文檔的自動分類等。歸根結底，能夠?明使用者在WWW海量的資訊裡面準確找到需要的資訊。這是一個正在迅速發展的研究領域。
PageRank和HITS是演算法中應用最廣的兩種，而其它一些類似的演算法有的處於研究階段，有的已經在具體的系統實現了。這些演算法大體可以分為3類，基於隨機漫遊模型的，比如PageRank，Repution演算法，基於Hub和Authority相互加強模型的，如HITS及其變種，基於概率模型的，如SALSA，PHITS，基於貝葉斯模型的，如貝葉斯演算法及其簡化版本。所有的演算法在實際應用中都結合傳統的內容分析技術進行了優化。一些實際的系統實現了某些演算法，並且獲得了很好的效果，Google實現了PageRank演算法，IBM Almaden Research Center 的Clever Project實現了ARC演算法，多倫多大學電腦系實現了一個原型系統TOPIC，來計算指定網頁有聲望的主題。
四、 PageRank與HITS演算法比較
顯而易見,兩者均是基於連結分析的搜尋引擎排序演算法,並且在演算法中二者均利用了特徵向量作為理論基礎和收斂性依據。但兩種演算法的不同點也非常明顯。
PageRank是對WWW的整體分析，通過模擬在WWW上的隨機遊動對每一個網頁計算其PageRank值。因此該演算法是獨立於使用者查詢的，可以對用戶要求產生快速的回應。HITS演算法是對WWW的局部分析，是根據特定的查詢產生不同的根集，然後計算網頁的Authority值和Hub值。該演算法是依賴於使用者查詢的，即時性差。
HITS演算法存在“主題漂移”的現象，如用戶在查詢“量子物理學”時，由於演算法中需要對初次檢索結果的根集擴充成基集，最終的檢索結果中會包含大量的有關“物理學”的網站。因此，HITS適合與寬主題的查詢，而PageRank則較好地克服了“主題漂移”的現象。
五、 應用WEB結構挖掘演算法提高網站價值
1、 選擇連結策略
在互聯網的海洋中，最重要的就是互聯互通，不被其他網站引用的網站就是“資訊孤島”。WEB結構挖掘引擎所有演算法都將網頁中的連結作為主要挖掘的物件，特別是實際應用中，大多數使用者都是使用基於PageRank演算法的Google, Yahoo，Baidu都搜尋引擎，因此可以採取以下幾種策略，提高網站的排名。
1) 廣泛連結策略
來自其他網站的任何反相連結都是有用的。當前常見的新搜尋引擎已經不再只是網站目錄的索引，而是更全面的網頁索引，所以無論來自其他網站任何地方的反相連結都是非常有價值的。
同時如果一個網頁只有大量的進入連結，而缺乏匯出連結，也會被搜尋引擎認為是沒有價值的網站。保證你的網站能夠幫助搜尋引擎更準確地判斷哪些是對使用者最有價值的資訊，也就是說如果你的網站只有外部反向連結而沒有匯出連結的話，也會對你的網站在搜索結果中的表現帶來負面影響。
2) 高品質連結策略
被PageRank高的網站引用能更快地提高PageRank數量只是關鍵因素之一，來自PageRank高的頁面的連結還能更快的提高被連結目標的PageRank
3) 無空連結策略
應當保持網站自身的健康，經常利用壞鏈檢查工具檢查網站中是否有死鏈。同時保持網頁內容/連結的穩定性和持久性：在搜尋引擎索引中網頁存在的歷史也是一個比較重要的因素，而且歷史比較久的網頁被連結的幾率越高。為了保證自己網頁能夠被比較持久的被其他網站的頁面引用，如果自己網頁中有連結更新時，最好能保留舊的頁面並做好連結轉向，以保持內容的連續性。
2、 構建友好的網站結構
有了合適的連結，就可以在演算法中取得一個比較理想的分值，但由於資料的挖掘過程中由機器Spider自動完成。因此還必須考慮讓引擎能完整的採集到所設計的連結，這就需要構建友好的網站結構。
1) 網站結構扁平化
網站目錄結構要扁平，因為每深一級目錄，PAGERANK降低1－2個檔次。假設首頁是3，其子可能目錄就是1了，更深可能就無法列入評級範圍了。
2) 表現和內容的分離
遵循w3c的規範，使用更規範的XHTML和XML作為顯示格式，JavaScript和CSS盡可能和網頁分離，一方面提高代碼重用度（也方便頁面緩存），另外一方面，由於有效內容占網頁長度的百分比高，也能提高相關關鍵字在頁面中的比重也增加了。因為挖掘引擎會更傾向於<title><h1><h2>……之間的內容，而不是正文。
3) 建立網站地圖
讓所有的頁面都有能夠快速入口：網站地圖，方便網頁爬蟲（spider）快速遍歷網站所有需要發佈的內容。如果首頁就是用Flash或圖片進入的話，無異於將搜尋引擎拒之門外，除了UI設計的用戶友好外，spider 友好也是非常重要的。
六、 結語
網路的結構挖掘技術已經是比較成熟的技術，特別是PageRank演算法已經應用到各大搜索網站中。所有的結構挖掘演算法都是基於網頁結構中超連結的分析。所不同的僅僅只是分析的效率改進和一些附加的分析條件。通過網站結構演算法的研究，可以有效地採取應對措施，提高網站在搜尋引擎中的排名。從而能網站可以有效的被客戶搜索。隨著電子商務的迅猛發展，企業應當儘早地重視這種被挖掘的技術應用，提高自身網站的價值。
參考文獻
〔 1 〕 何曉陽、吳強、吳治蓉，HITS 演算法與PageRank 演算法比較分析，情報雜誌2004 年第2 期
〔 2 〕 王曉宇、周傲，萬維網的連結結構分析及其應用綜述，軟體學報
〔 3 〕 Dan Thies，Google PageRank排名新演算法
〔 4 〕 Sergey Brin，Lawrence Page，Google的技術剖析，http:// www.51web.biz
〔 5 〕 曹軍，Google 的PageRank 技術剖析，情報雜誌2002 年第10 期
〔 6 〕 楊海東、張莉，PageRank 技術分析與搜尋引擎檢索效率研究，淮陰師範學院學報(自然科學版)，第2 卷第3 期，2003 年8 月
〔 7 〕 吳軍、孫從梅，資料採擷技術在Web中的應用，內蒙古科技與經濟，2004年第12期
〔 8 〕 楊沅釗、吳薇、喻曉莉、楊國才，搜尋引擎排名改進演算法分析，《農業網路資訊》2005 年第2 期
〔 9 〕 陳灶芳黃國濤，用於互聯網資訊搜索系統的網路蜘蛛設計與實現，廣東科技
〔 10 〕 楊炳儒、李 岩、陳新中、王 霞，Web結構挖掘，計 算 機 工 程，2003年11月
〔 11 〕 WEB超鏈分析演算法縱覽
〔 12 〕 Web資料採擷的研究現狀及發展
〔 13 〕 陳莉，焦李成.Internet/Web資料採擷研究現狀及最新進展.西安電子科技大學學報（自然科學版）.2001年2月第28卷第1期.
〔 14 〕 車東，如何提高網站在Google中的排名，http://www.zdnet.com.cn/
〔 15 〕 車東，提高網站在Google中的排名——面向搜尋引擎的網站設計
〔 16 〕 如何評價網站的人氣，http://www.zdnet.com.cn/developer/study/story/0,2000081626,39046113,00.htm
〔 17 〕 資料採擷未來研究方向及熱點，http://www.stcsm.gov.cn/fuwuzhinan/fb/bf/know/20010531-1.asp
沒有留言:
張貼留言