基于Ｗｅｂ結構挖掘算法的網(wǎng)站構建

摘要： Web 結構挖掘是對Web 的鏈接結構進行分析。該文概述Web結構挖掘技術，列舉其常見算法。并對PageRank和HITS這兩種最重要的Web結構挖掘算法分析比較。通過對算法規(guī)律的研究，指出在網(wǎng)站設計規(guī)劃時的策略以提高網(wǎng)站的價值。

關鍵詞： Web結構挖掘；PageRank；HITS；算法

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)34-1619-02

Building the Web Site Based Web Structure Mining Arithmetic

YE Lin-li1， LIN Song-kai2

(1.Computer and Information College， Fujian Agriculture and Forest University， Fuzhou 350002， China; 2.School of Post and Telecommunications of Fujian Province， Fuzhou 350008， China)

Abstract: This paper introduces the conception of Web structure mining， and analyses the authoritative algorithms based on Web hyperlink structure. At the end， correlative application on increasing the rank of the website by Web structure mining algorithms.

key words: web structure mining; pagerank; hyperlink-induced topic search (HITS); agorithm

1 引言

數(shù)據(jù)挖掘是將人工智能技術和數(shù)據(jù)庫技術緊密結合發(fā)展出的一門新的技術，利用計算機從龐大的數(shù)據(jù)中智能地、自動地抽取有價值的知識模式，以滿足人們不同應用的需要。隨著互聯(lián)網(wǎng)的普及和迅猛發(fā)展、Web上信息量的爆炸式增長，網(wǎng)上的資源得到極大豐富，但也充斥著大量的垃圾信息，人們迫切需要能從這些紛繁蕪雜的信息中找到有用知識的工具。鑒于數(shù)據(jù)挖掘工具的日益成熟完善，人們自然而然想到了要把數(shù)據(jù)挖掘技術應用到Web上來。

Web挖掘指在WWW 上挖掘潛在的、有用的模式及隱藏的信息過程。根據(jù)對Web數(shù)據(jù)的感興趣程度不同，Web挖掘一般可以分為三類：Web內容挖掘（Web Content mining）、 Web結構挖掘（Web structure mining）、Web 用法挖掘（Web usage Mining）

其中Web 結構挖掘是對Web 的鏈接結構進行分析，以對超鏈接分析來評估基礎Web 資源，從而發(fā)現(xiàn)有用模式，提高搜索質量。

2 Web結構挖掘綜述

傳統(tǒng)的WEB搜索引擎大多數(shù)是基于關鍵字匹配的，返回的結果是包含查詢項的文檔，也有基于目錄分類的搜索引擎。這些搜索引擎的結果并不令人滿意。有些站點有意提高關鍵字出現(xiàn)的頻率來提高自身在搜索引擎中的重要性，破壞搜索引擎結果的客觀性和準確性。另外，有些重要的網(wǎng)頁并不包含查詢項。搜索引擎的分類目錄也不可能把所有的分類考慮全面，并且目錄大多靠人工維護，主觀性強，費用高，更新速度慢。

Web結構包括不同網(wǎng)頁之間的超鏈接結構和一個網(wǎng)頁內部的可以用HTML，XML表示成的樹開結構，以及文檔URL中的目錄路徑結構等。Web頁之間的超鏈接結構中包含了許多有用的信息，當網(wǎng)頁A到網(wǎng)頁B存在一個超鏈接時，則說明網(wǎng)頁A的作者認為網(wǎng)頁B的內容非常重要，且兩個網(wǎng)頁的內容具有相似的主題。因此，指向一個文檔的超鏈接體現(xiàn)了該文檔的被引用情況。如果大量的鏈接都指向了同一個網(wǎng)頁，我們就認為它是一個權威頁。這就類似于論文對參考文獻的引用，如果某一篇文章經(jīng)常被引用，就說明它非常重要。這種思想有助于對搜索引擎的返回結果進行相關度排序。從WWW的組織結構和鏈接關系中推導知識。通過對Web站點的結構進行分析、變形和歸納，將Web頁面進行分類，分析一個網(wǎng)頁鏈接和被鏈接數(shù)量以及對象來建立Web自身的鏈接結構模式，確定不同頁面間的相似度和關聯(lián)度信息。定位相關主題的權威站點，可以極大的提高檢索結果的質量。

基于這種超鏈分析的思想，Sergey Brin和Lawrence Page在1998年提出了PageRank算法，同年J. Kleinberg提出了HITS算法，其它一些學者也相繼提出了另外的鏈接分析算法，如SALSA，PHITS，Bayesian等算法。這些算法有的已經(jīng)在實際的系統(tǒng)中實現(xiàn)和使用，并且取得了良好的效果[1-3]。

3 WEB結構挖掘常見算法

3.1 PageRank算法

PageRank的具體算法是，將某個頁面的PageRank除以存在于這個頁面的正向鏈接，由此得到的值分別和正向鏈接所指向的頁面的PageRank相加，即得到了被鏈接的頁面的PageRank。

算法基于“從許多優(yōu)質的網(wǎng)頁鏈接過來的網(wǎng)頁，必定還是優(yōu)質網(wǎng)頁”的回歸關系，來判定所有網(wǎng)頁的重要性。Google認為當某個網(wǎng)頁有鏈接到另一個網(wǎng)頁時，它就對該網(wǎng)“投了一票”。一個網(wǎng)頁的得票越多，則認為它的重要性也就越高。進一步說，投票網(wǎng)頁的重要性也決定著票本身的重要程度. Google通過計算網(wǎng)頁得票來得到頁面重要性。計算PageRank值時每票的重要性都要考慮在內。

簡單將 PageRank算法描述如下：將網(wǎng)絡看作一個有向圖：G=( V，E )，其中V是節(jié)點〔網(wǎng)頁)集，E是邊(當且僅當存在從頁面i到頁面j的鏈接時存在從節(jié)點i到節(jié)點j的邊)集。

PageRank的基本思想在于一個頁面重要或者有鏈接指向它的頁面多，或者有鏈接指向它的頁面重要或者二者兼而有之。其初始定義如下:

■

其中：PR(q)：頁面q的網(wǎng)頁級別，PR(p)：頁面p的網(wǎng)頁級別，頁面p鏈向頁面q， N(p)：頁面p鏈出的鏈接數(shù)量。

PageRank在具體實現(xiàn)時會忽略掉Web頁面上的文本和其它內容，只考慮頁面間的超鏈接，將網(wǎng)頁的URL對應成唯一的整數(shù)，把每一個超鏈接用其整數(shù)ID存放到索引數(shù)據(jù)庫中，經(jīng)過預處理(如去除數(shù)據(jù)庫中的懸擺指針)之后，設每個網(wǎng)頁的初始PR值為1，通過以上的遞歸算法計算每一個網(wǎng)頁的PageRank值，反復進行迭代，直至結果收斂。

3.2 HITS算法

Hill Top 算法的指導思想和PageRank 是一致的，即都通過反相鏈接的數(shù)量和質量來確定搜索結果的排序權重。但超鏈接的應用存在著許多的潛在的問題，如大量的鏈接是為了導航(如“點擊此按鈕返回主頁”)或付費廣告而創(chuàng)建的。而出于商業(yè)競爭的原因，盡管內容相關，有些網(wǎng)站又不會把超鏈接指向他們的競爭對手。

HITS首先利用一個傳統(tǒng)的文本搜索引擎獲取一個與主題相關的網(wǎng)頁根集合，然后向根集合中擴充那些指向根集合中網(wǎng)頁的網(wǎng)頁和根集合中網(wǎng)頁所指向的網(wǎng)頁，這樣就獲得了一個更大的基礎集合。假設最終基礎集合中包含N 個網(wǎng)頁，那么對于HITS 算法來說，輸入數(shù)據(jù)就是一個N×N 的相鄰矩陣A，其中如果網(wǎng)頁i 存在一個鏈接到網(wǎng)頁j，則Aij=1，否則Aij=0。

HITS 算法為每個網(wǎng)頁i 分配兩個度量值：中心度hi 和權威度ai。設向量a=(a1，a2， … ，aN)代表所有基礎集合中網(wǎng)頁的權威度，而向量h=(h1，h2， …，hN)則代表所有的中心度.最初，將這兩個向量均置為u=(1，1， … ，1)。操作In(a)使向量a=ATh，而操作Out(h)使向量h=Aa.反復迭代上述兩個操作，每次迭代后對向量a 和h 范化，以保證其數(shù)值不會使計算溢出.Kleinberg 證明經(jīng)過足夠的迭代次數(shù)，向量a 和h 將分別收斂于矩陣ATA 和AAT 的主特征向量。通過以上過程可以看出，基礎集合中網(wǎng)頁的中心度和權威度從根本上是由基礎集合中的鏈接關系所決定的，更具體地說，是由矩陣ATA 和AAT 所決定

3.3 其它算法及歸類

鏈接分析算法可以用來提高搜索引擎的查詢效果，可以發(fā)現(xiàn)WWW上的重要的社區(qū)，可以分析某個網(wǎng)站的拓撲結構，聲望，分類等，可以用來實現(xiàn)文檔的自動分類等。歸根結底，能夠幫助用戶在WWW海量的信息里面準確找到需要的信息。這是一個正在迅速發(fā)展的研究領域。

PageRank和HITS是算法中應用最廣的兩種，而其它一些類似的算法有的處于研究階段，有的已經(jīng)在具體的系統(tǒng)實現(xiàn)了。這些算法大體可以分為3類：基于隨機漫游模型的，比如PageRank，Repution算法；基于Hub和Authority相互加強模型的，如HITS及其變種；基于概率模型的，如SALSA，PHITS，基于貝葉斯模型的，如貝葉斯算法及其簡化版本。所有的算法在實際應用中都結合傳統(tǒng)的內容分析技術進行了優(yōu)化。一些實際的系統(tǒng)實現(xiàn)了某些算法，并且獲得了很好的效果，Google實現(xiàn)了PageRank算法，IBM Almaden Research Center 的Clever Project實現(xiàn)了ARC算法，多倫多大學計算機系實現(xiàn)了一個原型系統(tǒng)TOPIC，來計算指定網(wǎng)頁有聲望的主題。

4 PageRank與HITS算法比較

顯而易見，兩者均是基于鏈接分析的搜索引擎排序算法，并且在算法中二者均利用了特征向量作為理論基礎和收斂性依據(jù)，但兩種算法的不同點也非常明顯[4]。

PageRank是對WWW的整體分析，通過模擬在WWW上的隨機游動對每一個網(wǎng)頁計算其PageRank值。因此該算法是獨立于用戶查詢的，可以對用戶要求產(chǎn)生快速的響應。HITS算法是對WWW的局部分析，是根據(jù)特定的查詢產(chǎn)生不同的根集，然后計算網(wǎng)頁的Authority值和Hub值。該算法是依賴于用戶查詢的，實時性差。

HITS算法存在“主題漂移”的現(xiàn)象，如用戶在查詢“量子物理學”時，由于算法中需要對初次檢索結果的根集擴充成基集，最終的檢索結果中會包含大量的有關“物理學”的站點。因此，HITS適合與寬主題的查詢，而PageRank則較好地克服了“主題漂移”的現(xiàn)象。

5 應用WEB結構挖掘算法提高網(wǎng)站價值

5.1 選擇鏈接策略

在互聯(lián)網(wǎng)的海洋中，最重要的就是互聯(lián)互通，不被其他網(wǎng)站引用的網(wǎng)站就是“信息孤島”。WEB結構挖掘引擎所有算法都將網(wǎng)頁中的鏈接作為主要挖掘的對象，特別是實際應用中，大多數(shù)用戶都是使用基于PageRank算法的Google，Yahoo，Baidu都搜索引擎，因此可以采取以下幾種策略，提高網(wǎng)站的排名。

1) 廣泛鏈接策略。來自其他網(wǎng)站的任何反相鏈接都是有用的。當前常見的新搜索引擎已經(jīng)不再只是網(wǎng)站目錄的索引，而是更全面的網(wǎng)頁索引，所以無論來自其他網(wǎng)站任何地方的反相鏈接都是非常有價值的。

同時如果一個網(wǎng)頁只有大量的進入鏈接，而缺乏導出鏈接，也會被搜索引擎認為是沒有價值的站點。保證你的網(wǎng)站能夠幫助搜索引擎更準確地判斷哪些是對用戶最有價值的信息，也就是說如果你的網(wǎng)站只有外部反向鏈接而沒有導出鏈接的話，也會對你的網(wǎng)站在搜索結果中的表現(xiàn)帶來負面影響。

2) 高質量鏈接策略。被PageRank高的網(wǎng)站引用能更快地提高PageRank數(shù)量只是關鍵因素之一，來自PageRank高的頁面的鏈接還能更快的提高被鏈接目標的PageRank

3) 無空鏈接策略。應當保持網(wǎng)站自身的健康，經(jīng)常利用壞鏈檢查工具檢查網(wǎng)站中是否有死鏈。同時保持網(wǎng)頁內容/鏈接的穩(wěn)定性和持久性：在搜索引擎索引中網(wǎng)頁存在的歷史也是一個比較重要的因素，而且歷史比較久的網(wǎng)頁被鏈接的幾率越高。為了保證自己網(wǎng)頁能夠被比較持久的被其他網(wǎng)站的頁面引用，如果自己網(wǎng)頁中有鏈接更新時，最好能保留舊的頁面并做好鏈接轉向，以保持內容的連續(xù)性。

5.2 構建友好的網(wǎng)站結構

有了合適的鏈接，就可以在算法中取得一個比較理想的分值，但由于數(shù)據(jù)的挖掘過程中由機器Spider自動完成。因此還必須考慮讓引擎能完整的采集到所設計的鏈接，這就需要按照下面方式構建友好的網(wǎng)站結構：（下轉第1629頁）

（上接第1620頁）

1) 網(wǎng)站結構扁平化。網(wǎng)站目錄結構要扁平，因為每深一級目錄，PAGERANK降低1－2個檔次。假設首頁是3，其子可能目錄就是1了，更深可能就無法列入評級范圍了。

2) 表現(xiàn)和內容的分離。遵循w3c的規(guī)范，使用更規(guī)范的XHTML和XML作為顯示格式，JavaScript和CSS盡可能和網(wǎng)頁分離，一方面提高代碼重用度（也方便頁面緩存），另外一方面，由于有效內容占網(wǎng)頁長度的百分比高，也能提高相關關鍵詞在頁面中的比重也增加了。因為挖掘引擎會更傾向于

3) 建立站點地圖。讓所有的頁面都有能夠快速入口：站點地圖，方便網(wǎng)頁爬蟲（spider）快速遍歷網(wǎng)站所有需要發(fā)布的內容。如果首頁就是用Flash或圖片進入的話，無異于將搜索引擎拒之門外，除了UI設計的用戶友好外，spider 友好也是非常重要的。

5 結束語

網(wǎng)絡的結構挖掘技術已經(jīng)是比較成熟的技術，特別是PageRank算法已經(jīng)應用到各大搜索網(wǎng)站中。所有的結構挖掘算法都是基于網(wǎng)頁結構中超鏈接的分析。所不同的僅僅只是分析的效率改進和一些附加的分析條件。通過網(wǎng)站結構算法的研究，可以有效地采取應對措施，提高網(wǎng)站在搜索引擎中的排名。從而能網(wǎng)站可以有效的被客戶搜索。隨著電子商務的迅猛發(fā)展，企業(yè)應當盡早地重視這種被挖掘的技術應用，提高自身網(wǎng)站的價值。

參考文獻：

[1] 何曉陽，吳強，吳治蓉.HITS 算法與PageRank 算法比較分析[J].情報雜志，2004(2).

[2] 王曉宇，周傲.萬維網(wǎng)的鏈接結構分析及其應用綜述[J].軟件學報，2003(10).

[3] 楊炳儒，李巖，陳新中，等.Web結構挖掘[J].計算機工程，2003(11).

[4] 楊沅釗，吳薇，喻曉莉，等.搜索引擎排名改進算法分析[J].農業(yè)網(wǎng)絡信息，2005(2).