網頁分析算法可以歸納為基於網路拓撲、基於網頁內容和基於用戶訪問行為三種類型
基本介紹
- 中文名：網頁分析算法
- 外文名：Web analysis algorithm
網頁分析算法可以歸納為基於網路拓撲、基於網頁內容和基於用戶訪問行為三種類型。
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算法中，沒有對這些連結作區分，因此常常給網頁分析帶來廣告等噪聲連結的干擾。在網頁塊級別(Blocklevel)進行連結分析的算法的基本思想是通過VIPS網頁分割算法將網頁分為不同的網頁塊(page block)，然後對這些網頁塊建立pagetoblock和blocktopage的連結矩陣，分別記為Z和X。於是，在pagetopage圖上的網頁塊級別的PageRank為Wp=X×Z；在blocktoblock圖上的BlockRank為Wb=Z×X。已經有人實現了塊級別的PageRank和HITS算法，並通過實驗證明，效率和準確率都比傳統的對應算法要好。
2 基於網頁內容的網頁分析算法
基於網頁內容的分析算法指的是利用網頁內容（文本、數據等資源）特徵進行的網頁評價。網頁的內容從原來的以超文本為主，發展到後來動態頁面（或稱為hidden web）數據為主，後者的數據量約為直接可見頁面數據（PIW，publiclyIndexable Web）的400~500倍。另一方面，多媒體數據、Web Service等各種網路資源形式也日益豐富。因此，基於網頁內容的分析算法也從原來的較為單純的文本檢索方法，發展為涵蓋網頁數據抽取、機器學習、數據挖掘、語義理解等多種方法的綜合套用。本節根據網頁數據形式的不同，將基於網頁內容的分析算法，歸納以下三類：第一種針對以文本和超連結為主的無結構或結構很簡單的網頁；第二種針對從結構化的數據源（如RDBMS）動態生成的頁面，其數據不能直接批量訪問；第三種針對的數據界於第一和第二類數據之間，具有較好的結構，顯示遵循一定模式或風格，且可以直接訪問。
2.1 基於文本的網頁分析算法
1) 純文本分類與聚類算法
很大程度上借用了文本檢索的技術。文本分析算法可以快速有效的對網頁進行分類和聚類，但是由於忽略了網頁間和網頁內部的結構信息，很少單獨使用。
2) 超文本分類和聚類算法
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算法中，沒有對這些連結作區分，因此常常給網頁分析帶來廣告等噪聲連結的干擾。在網頁塊級別(Blocklevel)進行連結分析的算法的基本思想是通過VIPS網頁分割算法將網頁分為不同的網頁塊(page block)，然後對這些網頁塊建立pagetoblock和blocktopage的連結矩陣，分別記為Z和X。於是，在pagetopage圖上的網頁塊級別的PageRank為Wp=X×Z；在blocktoblock圖上的BlockRank為Wb=Z×X。已經有人實現了塊級別的PageRank和HITS算法，並通過實驗證明，效率和準確率都比傳統的對應算法要好。
2 基於網頁內容的網頁分析算法
基於網頁內容的分析算法指的是利用網頁內容（文本、數據等資源）特徵進行的網頁評價。網頁的內容從原來的以超文本為主，發展到後來動態頁面（或稱為hidden web）數據為主，後者的數據量約為直接可見頁面數據（PIW，publiclyIndexable Web）的400~500倍。另一方面，多媒體數據、Web Service等各種網路資源形式也日益豐富。因此，基於網頁內容的分析算法也從原來的較為單純的文本檢索方法，發展為涵蓋網頁數據抽取、機器學習、數據挖掘、語義理解等多種方法的綜合套用。本節根據網頁數據形式的不同，將基於網頁內容的分析算法，歸納以下三類：第一種針對以文本和超連結為主的無結構或結構很簡單的網頁；第二種針對從結構化的數據源（如RDBMS）動態生成的頁面，其數據不能直接批量訪問；第三種針對的數據界於第一和第二類數據之間，具有較好的結構，顯示遵循一定模式或風格，且可以直接訪問。
2.1 基於文本的網頁分析算法
1) 純文本分類與聚類算法
很大程度上借用了文本檢索的技術。文本分析算法可以快速有效的對網頁進行分類和聚類，但是由於忽略了網頁間和網頁內部的結構信息，很少單獨使用。
2) 超文本分類和聚類算法
