基于網頁聚類的Web信息自動抽取*

邱韜奮，楊天奇，曾洪波

(暨南大學 信息科學技術學院計算機系，廣東 廣州510632)

隨著Internet技術的迅速發展，Web已經成為當今最龐大的信息庫。然而Web頁面中通常含有很多用戶并不關心的信息(如廣告鏈接、導航欄和版權信息等)，如何從Web頁面中抽取出有用的信息已經成為當前信息領域的研究熱點之一。

Web信息抽取是一種從Web文檔中抽取出有用信息的技術，通常用于Web信息抽取的軟件又稱作包裝器（Wrapper）。自 1994年起，包裝器生成技術經歷了從手工編寫包裝器腳本，到利用機器學習的半自動化生成，再到自動化生成的三個階段。目前，自動化已經成為Web信息抽取技術的一個重要特征,比較有代表性的抽取工具有 RoadRunner、IEPAD、Dela 和 MDR-2 等[1]。

1 總體流程

本文根據數據提供網站動態網頁的特點，在基于DOM的抽取技術上，根據樹的相似度比較算法對網頁進行聚類分析，從而分類出網頁結構相似度較高的網頁簇，并考慮非模板標簽和模板文本改進包裝器生成算法，基于這些算法實現一個高精度的Web信息自動抽取系統，并通過大量的測試網頁集對這些算法進行實驗和評估。整個抽取流程如圖1所示。

2 算法實現

2.1 頁面預處理

對于抓取的網頁，并不能直接轉化成一個DOM樹，因為HTML網頁的格式通常不是規范的XML格式，因此需要將其先轉化成XHTML格式。另外，Web中很多的網頁都會存在標簽上的錯誤，由于HTML的不規范性導致代碼中存在的標簽不配對也不影響頁面的執行，并且很多標簽是多余的。對于這些問題，本文采用HTML Tidy[2]來解決。Tidy是一個開源的HTML網頁凈化工具，它可以將HTML轉化成XHTML，并能清除網頁中的明顯錯誤。因為頁面預處理不是本文的研究重點，所以不對此問題展開闡述。

2.2 樹編輯距離

基于DOM模型的Web信息抽取技術的基礎算法就是比較兩棵HTML標簽樹的相似性。比較兩棵樹相似性的方法之一就是計算它們的編輯距離，要計算兩棵樹之間的樹編輯距離[3]，通常的做法是找到兩棵樹之間權值最小的一個映射(mapping)，映射的定義如下：

定義 1：假設 X是一棵樹，X[i]是樹 X中第 i個字節點，則樹Tl和T2之間的映射M滿足以下條件的有序數對(i，j)的集合。

對于任何 M 中的所有有序數對(i1，j1)、(i2，j2):

(1)i1=i2的條件是當且僅當j1=j2；

(2)Tl[i1]是Tl[i2]的左鄰節點的條件是當且僅當T2[j1]是T2[j2]的左鄰節點；

(3)Tl[i1]是 Tl[i2]的父節點當且僅當 T2[j1]是 T2[j2]的父節點。

有了映射，就可以計算兩棵樹之間的樹編輯距離。設兩棵樹Tl和T2之間的映射為M。在M包含的數據對(i，j)中 i、j分別表示 Tl和 T2的標簽。令 S表示 i和 j不相同的數據對數量，即需要替換的標簽；D表示Tl中沒出現在M中的節點，即需要刪除的標簽；I表示T2中沒出現在M中的節點，即需要插入的標簽。則樹編輯距離ed(Tl，T2)可 以 由 式(1)得 出 ：

其中，p、q、r分別表示替換、刪除和插入的權值。為了使得出的值介于 0與1之間，利用式（2）規范化計算結果便于計算相似矩陣，式中的 len(Tl)和 len(T2)分別表示Tl和T2的節點數：

2.3 使用代表點的聚類法

對于網頁集合的聚類，傳統的層次聚類方法能實現比較好的結果。層次聚類過程由不同層次的分割聚類組成，層次之間的分割具有嵌套的關系，整個過程為一個樹狀結構。自底向上的層次算法稱為凝聚層次算法，本文使用的凝聚層次算法是使用代表點的聚類法。

使用代表點的聚類法(Clustering Using Representatives)，首先把每個單獨的數據對象作為一個簇，每一步距離最近的簇對首先被合并，直到簇的個數為K，算法結束。CURE的顯著特點是：(1)可以識別任意形狀的簇；(2)有效處理異常數據[4]。

2.4 網頁聚類算法

在聚類實驗中網頁的數目為500～1000，在這個復雜度上，可以采用類CURE算法。在本文的網頁聚類實驗中，距離定義為兩個網頁的樹編輯距離。

定義網頁集合P={P0,P1,…,Pn}，根據網頁間的HTML標簽樹的樹編輯距離計算相似矩陣。將Pi和Pj利用es(pi，pj)計算出樹編輯距離，在矩陣中表示為 mij，計算結果為一個 N×N 矩陣。定義 Pi和 Pj的列相似度為 cs(pi，pj)，通過實驗可以發現引入平均絕對誤差概念的列相似度比用單純的樹編輯距離es(pi，pj)在聚類過程的計算中具有更好的健壯性。列相似度cs(pi，pj)由式（3）得出：

緊接著利用代表點的聚類算法對網頁進行聚類計算。網頁的聚類分析中，首先認為每個網頁就是單獨的一個簇，然后根據簇間的相似性不斷地合并簇對，直到合并為理想的簇的個數時算法結束。這里引用了自相似度的概念以獲得更好的聚類結果[5]，其中集合Φ的自相似性 s(Φ)由式（4）得出：

網頁聚類中產生的代表簇必須滿足兩個閾值。首先簇的全局自相似性必須滿足閾值Ωg，其次簇中兩兩網頁間的列相似度必須滿足閾值Ωe，這個閾值的設定是為了避免出現新簇，雖有較高的全局自相似性，但簇內仍然包含了一些不相似對象的情況。在本實驗中，將Ωg和Ωe值分別設置為 0.9和0.8，整個過程算法的偽代碼如下：

2.5 抽取模板生成

對于網頁聚類后的每一個網頁簇，都會生成一個對應的抽取模板，所有抽取模板組成了抽取系統的包裝器。網頁模板生成建立在兩個網頁模板生成的基礎上。

2.5.1 兩個網頁的模板

兩個網頁模板的生成算法的基礎也是DOM樹的相似性算法，在計算距離的同時，生成一個節點映射集合，獲得樹節點T1和T2之間距離最小的子樹匹配情況，把這些匹配情況作為一個列表返回。當T1和T2不匹配時，返回的列表為空；當T1和T2至少有一個沒有子節點時，返回的列表只包含T1和T2的匹配。

返回的兩個網頁的節點映射集合中的節點就是模板中的必需節點，而兩個網頁不在映射集合中的點可以認為是可選節點，也可以認為是內容節點。如果是可選節點，就要把這些節點插入到模板中，可以把T1認為是最終模板，然后把T2的可選節點插入到T1中。插入的算法是：對于任一T2在映射中的節點P，獲得它在 T1中的對應節點Q，遍歷P的所有子節點C，如果節點 C在 T1中存在映射節點D，則記錄D節點在Q節點的子節點列表中的位置；如果節點C在T1中不存在映射，則把節點C插入列表中最近一次記錄的位置后面。

2.5.2 多網頁模板生成

多網頁模板生成算法建立在兩個網頁的模板生成算法之上。主要過程是選取一個網頁作為初始模板，然后根據其他網頁逐步調整模板，最后通過統計的方法得到模板，利用此模板生成抽取網頁信息的包裝器。

首先是初始模板的選取。結合網頁聚類的算法，發現對于網頁聚類結果簇集合 C={P0，P1，…，Pk}，滿 足 式（5）的網頁Pi作為初始模板更為合理。

有了初始模板，接下來就是根據其他網頁調整和修正該模板。網頁的順序從節點數最多處開始，依次往下，算法的偽代碼如下所示：

2.6 數據抽取

數據字段的抽取是一個相對簡單的過程。只要對要抽取的網頁和包裝器的相應模板做距離計算，如果模板中的所有必需節點都在最后的映射中，說明該網頁滿足此包裝器，則把與包裝器指定的內容節點對應的網頁內容部分抽取出來。如果模板中不是所有必需節點都在映射中，則通過距離計算選取最相似的模板抽取網頁信息。

3 實驗

3.1 評價標準

對于聚類結果精確度的評估標準，采用聚類算法通用的F-Measure評估，它結合了信息抽取中的準確率(Precision)和查全率(Recall)的思想：

定義 C={C1，C2，…，Ck}為網頁集合 D的一個聚類結果簇集合，C*={，C2*，…，}為網頁集合 D的正確聚類簇結果集合，則簇j相對于簇i的查全率Rec(i，j)可以表示為|Cj∩Ci*|/||，簇 j相對于簇 i的準確率 Prec(i，j)可以表示為|Cj∩|/|Cj|， 簇 j相對于簇 i的 F-Measure結合這兩個值:

基于這個公式，聚類結果簇集合C的F-Measure定義為:

F-Measure的值在0～1之間，為1時表示完全正確。

3.2 抽取結果分析

本 文 實 驗 分 別 從 car.autohome.com、ebay.com、shopping.yahoo.com三個網站中各選取500個網頁進行內容抽取，并采用信息抽取工具RoadRunner進行對比實驗。實驗中不斷地調整閾值Ωg和Ωe，以達到最優的抽取結果，如圖 2所示，當Ωg和Ωe的取值分別為 0.9和0.8時，聚類結果的F-measure值達到最優。

從三個網站的信息抽取結果可知，本文基于網頁聚類的方法能取得較好的準確率和查全率，平均值分別達到80.3%和81.5%。比較RoadRunner的抽取結果，平均67.3%和66.6%的準確率和查全率，本文提出的方法明顯能達到較好的抽取結果，因為RoadRunner沒有考慮網頁文本節點模板，而且對一個頁面出現多個數據集的情況不能提取網頁的主要內容。分析本文方法對個別網站抽取結果不太理想，是因為網站產品信息列表分布不均勻，主要信息塊比較分散，造成準確率和查全率比較低。對于其他大部分主要信息塊比較集中的數據提供網站，該方法抽取準確率和查全率在75%～85%，個別高度模板化的網站甚至可以達到90%，網頁內容抽取實驗結果如表1所示。

表1 抽取網頁內容的實驗結果

本文介紹了一種用于Web動態網站的網頁聚類方法，利用生成高相似度的網頁簇生成高效的包裝器，并且成功地用于信息提取，取得了較好的效果，而且與同類技術相比具有算法構造簡單、準確率高等優勢。該方法適用于信息項內容的結構變化不是很大的Web頁面，但另一方面，對于信息項的結構變化較大、數據塊較多的情況準確率還有待提高。下一步主要工作就是改進抽取模板生成算法，準確識別網頁中的主要數據塊，提高算法的通用性，以適用于各種類型的網頁。

[1]CHANG H,KAYED M,GIRGIS R，et al.A survey of web information extraction systems[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(10):1411-1428.

[2]RAGGETT D.Clean up your web pages with HP's HTML tidy[J].Computer Networks and ISDN Systems，1998(30):730-732.

[3]LEVENSHTEIN V I.Binary codes capable of correcting deletions,insertions,and reversals[J].Soviet Physics Doklady，1996(10)：707-710.

[4]CRESCENZI V,MERIALDO P,MIDDIER P.Clustering web pages based on their structure[J].Data and Knowledge Engineering Journal,2005,54(3)：279-299.

[5]ALVAREZ M,PAN A,RAPOSO J，et al.Extracting lists of data records from semi-structured web pages[J].Data Knowledge Engineering,2008,24(2):491-509.

[6]CRESEENZI V,MEEEA G,MERIALDO P.RoadRu-nner:Towards automatic data extraction from large websites[C].In Proceedings of the 27th International Conferenee on Very Large DataBases,Rome,Italy,2001:109-118.