網頁分析算法

網頁分析算法可以歸納為基於網路拓撲、基於網頁內容和基於用戶訪問行為三種類型。

網頁分析算法可以歸納為基於網路拓撲、基於網頁內容和基於用戶訪問行為三種類型。
1 基於網路拓撲的分析算法
基於網頁之間的連結,通過已知的網頁或數據,來對與其有直接或間接連結關係的對象(可以是網頁或網站等)作出評價的算法。又分為網頁粒度、網站粒度和網頁塊粒度這三種。
1.1 網頁(Webpage)粒度的分析算法
PageRank和HITS算法是最常見的連結分析算法,兩者都是通過對網頁間連結度的遞歸和規範化計算,得到每個網頁的重要度評價。PageRank算法雖然考慮了用戶訪問行為的隨機性和Sink網頁的存在,但忽略了絕大多數用戶訪問時帶有目的性,即網頁和連結與查詢主題的相關性。針對這個問題,HITS算法提出了兩個關鍵的概念:權威型網頁(authority)和中心型網頁(hub)。
基於連結的抓取的問題是相關頁面主題團之間的隧道現象,即很多在抓取路徑上偏離主題的網頁也指向目標網頁,局部評價策略中斷了在當前路徑上的抓取行為。文獻[21]提出了一種基於反向連結(BackLink)的分層式上下文模型(Context Model),用於描述指向目標網頁一定物理跳數半徑內的網頁拓撲圖的中心Layer0為目標網頁,將網頁依據指向目標網頁的物理跳數進行層次劃分,從外層網頁指向內層網頁的連結稱為反向連結。
1.2 網站粒度的分析算法
網站粒度的資源發現和管理策略也比網頁粒度的更簡單有效。網站粒度的爬蟲抓取的關鍵之處在於站點的劃分和站點等級(SiteRank)的計算。SiteRank的計算方法與PageRank類似,但是需要對網站之間的連結作一定程度抽象,並在一定的模型下計算連結的權重。
網站劃分情況分為按域名劃分和按IP位址劃分兩種。文獻[18]討論了在分散式情況下,通過對同一個域名下不同主機、伺服器的IP位址進行站點劃分,構造站點圖,利用類似PageRank的方法評價SiteRank。同時,根據不同檔案在各個站點上的分布情況,構造文檔圖,結合SiteRank分散式計算得到DocRank。文獻[18]證明,利用分散式的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,publicly Indexable Web)的400~500倍。另一方面,多媒體數據、Web Service等各種網路資源形式也日益豐富。因此,基於網頁內容的分析算法也從原來的較為單純的文本檢索方法,發展為涵蓋網頁數據抽取、機器學習、數據挖掘、語義理解等多種方法的綜合套用。本節根據網頁數據形式的不同,將基於網頁內容的分析算法,歸納以下三類:第一種針對以文本和超連結為主的無結構或結構很簡單的網頁;第二種針對從結構化的數據源(如RDBMS)動態生成的頁面,其數據不能直接批量訪問;第三種針對的數據界於第一和第二類數據之間,具有較好的結構,顯示遵循一定模式或風格,且可以直接訪問。
2.1 基於文本的網頁分析算法
1) 純文本分類與聚類算法
很大程度上借用了文本檢索的技術。文本分析算法可以快速有效的對網頁進行分類和聚類,但是由於忽略了網頁間和網頁內部的結構信息,很少單獨使用。
2) 超文本分類和聚類算法

相關詞條

熱門詞條

聯絡我們