網頁分析算法

1 基於網絡拓撲的分析算法

基於網頁之間的鏈接，通過已知的網頁或數據，來對與其有直接或間接鏈接關係的對象（可以是網頁或網站等）作出評價的算法。又分為網頁粒度、網站粒度和網頁塊粒度這三種。

1.1 網頁(Webpage)粒度的分析算法

PageRank和HITS算法是最常見的鏈接分析算法，兩者都是通過對網頁間鏈接度的遞歸和規範化計算，得到每個網頁的重要度評價。PageRank算法雖然考慮了用户訪問行為的隨機性和Sink網頁的存在，但忽略了絕大多數用户訪問時帶有目的性，即網頁和鏈接與查詢主題的相關性。針對這個問題，HITS算法提出了兩個關鍵的概念：權威型網頁（authority）和中心型網頁（hub）。

基於鏈接的抓取的問題是相關頁面主題團之間的隧道現象，即很多在抓取路徑上偏離主題的網頁也指向目標網頁，局部評價策略中斷了在當前路徑上的抓取行為。文獻提出了一種基於反向鏈接（BackLink）的分層式上下文模型（Context Model），用於描述指向目標網頁一定物理跳數半徑內的網頁拓撲圖的中心Layer0為目標網頁，將網頁依據指向目標網頁的物理跳數進行層次劃分，從外層網頁指向內層網頁的鏈接稱為反向鏈接。

1.2 網站粒度的分析算法

網站粒度的資源發現和管理策略也比網頁粒度的更簡單有效。網站粒度的爬蟲抓取的關鍵之處在於站點的劃分和站點等級(SiteRank)的計算。SiteRank的計算方法與PageRank類似，但是需要對網站之間的鏈接作一定程度抽象，並在一定的模型下計算鏈接的權重。

網站劃分情況分為按域名劃分和按IP地址劃分兩種。文獻討論了在分佈式情況下，通過對同一個域名下不同主機、服務器的IP地址進行站點劃分，構造站點圖，利用類似PageRank的方法評價SiteRank。同時，根據不同文件在各個站點上的分佈情況，構造文檔圖，結合SiteRank分佈式計算得到DocRank。文獻證明，利用分佈式的SiteRank計算，不僅大大降低了單機站點的算法代價，而且克服了單獨站點對整個網絡覆蓋率有限的缺點。附帶的一個優點是，常見PageRank 造假難以對SiteRank進行欺騙。

1.3 網頁塊粒度的分析算法

在一個頁面中，往往含有多個指向其他頁面的鏈接，這些鏈接中只有一部分是指向主題相關網頁的，或根據網頁的鏈接錨文本表明其具有較高重要性。但是，在PageRank和HITS算法中，沒有對這些鏈接作區分，因此常常給網頁分析帶來廣告等噪聲鏈接的干擾。在網頁塊級別(Blocklevel)進行鏈接分析的算法的基本思想是通過VIPS網頁分割算法將網頁分為不同的網頁塊(page block)，然後對這些網頁塊建立pagetoblock和blocktopage的鏈接矩陣，分別記為Z和X。於是，在pagetopage圖上的網頁塊級別的PageRank為Wp=X×Z；在blocktoblock圖上的BlockRank為Wb=Z×X。已經有人實現了塊級別的PageRank和HITS算法，並通過實驗證明，效率和準確率都比傳統的對應算法要好。

2 基於網頁內容的網頁分析算法

基於網頁內容的分析算法指的是利用網頁內容（文本、數據等資源）特徵進行的網頁評價。網頁的內容從原來的以超文本為主，發展到後來動態頁面（或稱為hidden web）數據為主，後者的數據量約為直接可見頁面數據（PIW，publiclyIndexable Web）的400~500倍。另一方面，多媒體數據、Web Service等各種網絡資源形式也日益豐富。因此，基於網頁內容的分析算法也從原來的較為單純的文本檢索方法，發展為涵蓋網頁數據抽取、機器學習、數據挖掘、語義理解等多種方法的綜合應用。本節根據網頁數據形式的不同，將基於網頁內容的分析算法，歸納以下三類：第一種針對以文本和超鏈接為主的無結構或結構很簡單的網頁；第二種針對從結構化的數據源（如RDBMS）動態生成的頁面，其數據不能直接批量訪問；第三種針對的數據界於第一和第二類數據之間，具有較好的結構，顯示遵循一定模式或風格，且可以直接訪問。

2.1 基於文本的網頁分析算法

1) 純文本分類與聚類算法

很大程度上借用了文本檢索的技術。文本分析算法可以快速有效的對網頁進行分類和聚類，但是由於忽略了網頁間和網頁內部的結構信息，很少單獨使用。

2) 超文本分類和聚類算法