基于網(wǎng)頁聚類的Web信息自動抽取*

邱韜奮，楊天奇，曾洪波

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院計(jì)算機(jī)系，廣東 廣州510632)

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

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

1 總體流程

本文根據(jù)數(shù)據(jù)提供網(wǎng)站動態(tài)網(wǎng)頁的特點(diǎn)，在基于DOM的抽取技術(shù)上，根據(jù)樹的相似度比較算法對網(wǎng)頁進(jìn)行聚類分析，從而分類出網(wǎng)頁結(jié)構(gòu)相似度較高的網(wǎng)頁簇，并考慮非模板標(biāo)簽和模板文本改進(jìn)包裝器生成算法，基于這些算法實(shí)現(xiàn)一個高精度的Web信息自動抽取系統(tǒng)，并通過大量的測試網(wǎng)頁集對這些算法進(jìn)行實(shí)驗(yàn)和評估。整個抽取流程如圖1所示。

2 算法實(shí)現(xiàn)

2.1 頁面預(yù)處理

對于抓取的網(wǎng)頁，并不能直接轉(zhuǎn)化成一個DOM樹，因?yàn)镠TML網(wǎng)頁的格式通常不是規(guī)范的XML格式，因此需要將其先轉(zhuǎn)化成XHTML格式。另外，Web中很多的網(wǎng)頁都會存在標(biāo)簽上的錯誤，由于HTML的不規(guī)范性導(dǎo)致代碼中存在的標(biāo)簽不配對也不影響頁面的執(zhí)行，并且很多標(biāo)簽是多余的。對于這些問題，本文采用HTML Tidy[2]來解決。Tidy是一個開源的HTML網(wǎng)頁凈化工具，它可以將HTML轉(zhuǎn)化成XHTML，并能清除網(wǎng)頁中的明顯錯誤。因?yàn)轫撁骖A(yù)處理不是本文的研究重點(diǎn)，所以不對此問題展開闡述。

2.2 樹編輯距離

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

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

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

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

(2)Tl[i1]是Tl[i2]的左鄰節(jié)點(diǎn)的條件是當(dāng)且僅當(dāng)T2[j1]是T2[j2]的左鄰節(jié)點(diǎn)；

(3)Tl[i1]是 Tl[i2]的父節(jié)點(diǎn)當(dāng)且僅當(dāng) T2[j1]是 T2[j2]的父節(jié)點(diǎn)。

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

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

2.3 使用代表點(diǎn)的聚類法

對于網(wǎng)頁集合的聚類，傳統(tǒng)的層次聚類方法能實(shí)現(xiàn)比較好的結(jié)果。層次聚類過程由不同層次的分割聚類組成，層次之間的分割具有嵌套的關(guān)系，整個過程為一個樹狀結(jié)構(gòu)。自底向上的層次算法稱為凝聚層次算法，本文使用的凝聚層次算法是使用代表點(diǎn)的聚類法。

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

2.4 網(wǎng)頁聚類算法

在聚類實(shí)驗(yàn)中網(wǎng)頁的數(shù)目為500～1000，在這個復(fù)雜度上，可以采用類CURE算法。在本文的網(wǎng)頁聚類實(shí)驗(yàn)中，距離定義為兩個網(wǎng)頁的樹編輯距離。

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

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

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

2.5 抽取模板生成

對于網(wǎng)頁聚類后的每一個網(wǎng)頁簇，都會生成一個對應(yīng)的抽取模板，所有抽取模板組成了抽取系統(tǒng)的包裝器。網(wǎng)頁模板生成建立在兩個網(wǎng)頁模板生成的基礎(chǔ)上。

2.5.1 兩個網(wǎng)頁的模板

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

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

2.5.2 多網(wǎng)頁模板生成

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

首先是初始模板的選取。結(jié)合網(wǎng)頁聚類的算法，發(fā)現(xiàn)對于網(wǎng)頁聚類結(jié)果簇集合 C={P0，P1，…，Pk}，滿 足 式（5）的網(wǎng)頁P(yáng)i作為初始模板更為合理。

有了初始模板，接下來就是根據(jù)其他網(wǎng)頁調(diào)整和修正該模板。網(wǎng)頁的順序從節(jié)點(diǎn)數(shù)最多處開始，依次往下，算法的偽代碼如下所示：

2.6 數(shù)據(jù)抽取

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

3 實(shí)驗(yàn)

3.1 評價(jià)標(biāo)準(zhǔn)

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

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

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

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

3.2 抽取結(jié)果分析

本 文 實(shí) 驗(yàn) 分 別 從 car.autohome.com、ebay.com、shopping.yahoo.com三個網(wǎng)站中各選取500個網(wǎng)頁進(jìn)行內(nèi)容抽取，并采用信息抽取工具RoadRunner進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)中不斷地調(diào)整閾值Ωg和Ωe，以達(dá)到最優(yōu)的抽取結(jié)果，如圖 2所示，當(dāng)Ωg和Ωe的取值分別為 0.9和0.8時(shí)，聚類結(jié)果的F-measure值達(dá)到最優(yōu)。

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

表1 抽取網(wǎng)頁內(nèi)容的實(shí)驗(yàn)結(jié)果

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

[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.