應(yīng)用聚類技術(shù)分類提取Web頁面

摘要:針對Web中數(shù)據(jù)密集型的動態(tài)頁面，文本數(shù)據(jù)少，網(wǎng)頁結(jié)構(gòu)化程度高的特點，介紹了一種基于HTML結(jié)構(gòu)的web信息提取方法。該方法先將去噪處理后的Web頁面進(jìn)行解析，然后根據(jù)樹編輯距離計算頁面之間的相似度，對頁面進(jìn)行聚類，再對每一類簇生成相應(yīng)的提取規(guī)則，對Web頁面進(jìn)行數(shù)據(jù)提取。

關(guān)鍵詞:Web信息提取;樹編輯距離;聚類;提取規(guī)則

中圖分類號:TP391文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2010)01-212-02

Application of Clustering Technology Category Extraction Web Pages

CUI Hui-chao， LIU Li

(Southwest Jiaotong University， College of Information Science and Technology， Chengdu 610031， China)

Abstract: According to the characteristic of data-intensive dynamic web pages， insufficient text data and page structure with a high degree in web， this paper outlines a web information extraction method based on HTML structure. This method first parses the de-noised web pages to form DOM trees， then with tree edit distance calculates the similarity between pages， clusters pages， generates the corresponding extraction rules for each category and implements web information extraction.

Key words: Web information extraction; edited tree distance; clustering; extraction rules

互聯(lián)網(wǎng)對我們來說是一個巨大的信息源，信息爆炸而知識匱乏是當(dāng)今人們面臨的一個很重要的問題，因而從Web上提取用戶相關(guān)領(lǐng)域的知識可以極大提高有用信息獲取的效率。Web信息獲取主要有兩種方法:通過搜索引擎查詢或者進(jìn)行Web信息抽取。前者只要是通過關(guān)鍵字匹配查詢，根據(jù)用戶的請求獲取相應(yīng)的文檔，用戶必須從獲得的文檔中自己查找有用的信息。Web信息抽取則自動的從網(wǎng)絡(luò)中分析和發(fā)現(xiàn)有用的信息，廢棄并不需要的數(shù)據(jù)，可充分提取用戶知識領(lǐng)域的知識。

Web信息提取就是指從Web頁面所包含的無結(jié)構(gòu)或半結(jié)構(gòu)的信息中識別用戶感興趣的數(shù)據(jù)，并將其轉(zhuǎn)化為結(jié)構(gòu)和語義更為清晰的格式(XML、關(guān)系數(shù)據(jù)、面向?qū)ο蟮臄?shù)據(jù)等)。

Web信息抽取技術(shù)有多種分類方式，根據(jù)各種工具所采用的原理可以分為:基于自然語言處理方式、基于包裝器歸納方式、基于Ontology方式、基于HTML結(jié)構(gòu)方式和基于Web查詢方式。

基于HTML結(jié)構(gòu)方式的信息抽取技術(shù)的特點是:根據(jù)Web頁面的結(jié)構(gòu)定位信息。在信息抽取之前通過解析器將Web文檔解析成語法樹，通過自動或半自動的方式產(chǎn)生抽取規(guī)則，將信息抽取轉(zhuǎn)化為對語法樹的操作以實現(xiàn)信息抽取。采用該類技術(shù)的典型系統(tǒng)有Lixto、XWARP、RoadRunner和w4F等。本文中介紹的就是基于結(jié)構(gòu)方式與聚類技術(shù)相結(jié)合的一種智能提取方法。

從各種不同的半結(jié)構(gòu)化網(wǎng)頁中自動識別并抽取所需要的信息是互聯(lián)網(wǎng)信息挖掘研究中的一個重要研究課題。近年來人們進(jìn)行了大量的相關(guān)研究工作，并取得了許多重要的研究成果。Reis[1]等在分析網(wǎng)頁DOM結(jié)構(gòu)的基礎(chǔ)上提出了利用改進(jìn)的樹的編輯距離來進(jìn)行自動提取新聞網(wǎng)頁的算法。Liu Bing[2]等提出了使用樹的局部調(diào)整算法來抽取網(wǎng)頁數(shù)據(jù)記錄集。Yeonjung Kim[3]等在此基礎(chǔ)上改進(jìn)了節(jié)點匹配權(quán)重，根據(jù)內(nèi)容在網(wǎng)頁上所占面積設(shè)置其對應(yīng)的匹配權(quán)重，并對某些特定網(wǎng)頁的模板生成上做了改進(jìn)。A honen-Myka[5]和Beif[6]等人設(shè)計了基于HTML標(biāo)簽頻率聚類的算法生成文本提取模板。Gupta S[7]等通過利用網(wǎng)頁標(biāo)簽樹結(jié)構(gòu)提取規(guī)則，這樣產(chǎn)生模板的效率比通過聚類的更直接，但是它對整個網(wǎng)頁進(jìn)行處理，時間復(fù)雜度較高，而且它沒有進(jìn)行噪聲處理和對相同模板的網(wǎng)頁進(jìn)行分類，不能對總結(jié)出的模板進(jìn)行有效利用。

1 Web信息提取流程

基于Web的信息提取方法主要包括數(shù)據(jù)獲取、規(guī)則生成和規(guī)則執(zhí)行(見圖1)三個步驟。其中數(shù)據(jù)獲取是下載指定的頁面數(shù)據(jù)，并對其進(jìn)行預(yù)處理，為接下來的數(shù)據(jù)提取做好準(zhǔn)備;提取規(guī)則生成需要根據(jù)用戶需求進(jìn)行制定和調(diào)整，完成目的表模式設(shè)計和數(shù)據(jù)源到目的表結(jié)構(gòu)的模式映射設(shè)計，將頁面文檔解析為HTML DOM(Document Object Model)樹，這樣DOM樹就成為Web網(wǎng)頁在系統(tǒng)內(nèi)部的表示方式，然后通過STM算法對頁面的DOM樹進(jìn)行相似度計算，對頁面進(jìn)行聚類，并對每一個類簇生成相應(yīng)的規(guī)則;數(shù)據(jù)提取是根據(jù)提取規(guī)則，系統(tǒng)可以對用戶所感興趣的信息進(jìn)行的數(shù)據(jù)提取，將符合要求的數(shù)據(jù)寫入結(jié)構(gòu)化的數(shù)據(jù)集中。

2 Web信息提取

2.1 Web頁面預(yù)處理

絕大多數(shù)的Web頁面通過HTML語言描述，但HTML文檔大都由手工生成，時常存在語法等錯誤，另外，在網(wǎng)頁中存在一些關(guān)于圖片信息、超鏈接信息、script腳本信息、style樣式信息等干擾項，不利于信息的提取。因此，在使用之前，需要對文檔進(jìn)行清洗，修復(fù)頁面中的語法錯誤并進(jìn)行去噪處理。

2.2 簡單樹匹配(Simple Tree Matching)[4]算法

由信息提取的流程可以看出，規(guī)則的生成是整個提取過程的重要部分。而實現(xiàn)網(wǎng)頁聚類的一個重要參數(shù)就是兩個頁面對應(yīng)DOM樹的距離，即相似度。要計算兩棵樹之間的距離，通常的做法是找到兩棵樹之間權(quán)值最小的一個映射(mapping)，映射的定義如下:

定義1:設(shè)Tk[i]是樹Tk的第i個子節(jié)點，(節(jié)點排序為從上到下，從左到右)，節(jié)點的個數(shù)為樹的大小。大小為n1的樹T1到大小為n2的樹T2的映射M(i， j)滿足一下條件:

對于所有的(i1，j1)， (i2，j2)∈M，

1) i1=i2?圳j1=j2

2) T1[i1]與T1[i2]是的左鄰節(jié)點?圳 T2[j1]與T2[j2]是的左鄰節(jié)點;

3) T1[i1]是T1[i2]的父節(jié)點?圳 T2[j1]是T2[j2]的父節(jié)點;

該定義要求每個節(jié)點不能在映射中多次出現(xiàn)，同時節(jié)點的層次關(guān)系是確定的。有了映射，就可以計算兩棵樹之間的距離。

設(shè)S表示i和j不相同的數(shù)據(jù)對數(shù)量，即需要替換的標(biāo)簽;D表示T1中沒有出現(xiàn)在M中的節(jié)點，即需要刪除的標(biāo)簽;I表示T2中沒出現(xiàn)在M中的節(jié)點，即需插入的標(biāo)簽。樹編輯距離Dis(T1，T2)的計算公式為:

Dis(T1，T2)=Sp+Dq+Ir，其中p，q，r分別表示替換，刪除和插入的權(quán)值。

定義2:對于M中的所有有序數(shù)對(i，j)，如果T1[i]不等于T2[j]，那么M中不存在T1[i]和T2[j]的任何后代節(jié)點。

該定義為樹的編輯距離增加了一個限制條件，我們稱之為自頂向下限制。有了這個限制，STM算法的時間復(fù)雜度就大大降低了。

在該動態(tài)簡單樹匹配算法中，函數(shù)首先判斷傳入的兩個參數(shù)節(jié)點是否相同，如果不同，則這兩棵樹的相似度為0。如果相同，則按節(jié)點順序枚舉所有節(jié)點匹配關(guān)系，找到所有子節(jié)點的最大匹配，然后加上當(dāng)前節(jié)點的匹配權(quán)重。該算法可以根據(jù)M數(shù)組回溯得到兩棵樹的最大節(jié)點匹配映射關(guān)系。

2.3 網(wǎng)頁聚類

在本文中，采用基于帶標(biāo)點的聚類方法對Web頁面進(jìn)行聚類。CURE[8]算法是凝聚層次聚類算法的一種常用算法，它首先把每個單獨的數(shù)據(jù)對象作為一個簇，距離最近的簇對首先被合并，直到簇之間的距離大于給定的閾值，算法結(jié)束。其顯著的特點是:可以識別任意形狀的簇;對異常數(shù)據(jù)的處理有效。

在網(wǎng)頁聚類中，距離定義為兩個網(wǎng)頁的不相似度。計算公式如下:

其中n1，n2分別為Tree1，Tree2的節(jié)點數(shù)目，|M(Tree1，Tree2)|是映射的節(jié)點數(shù)目。

2.4 模板生成

首先選取對所有頁面相似度最高的網(wǎng)頁為初始模板，即代表點，然后再根據(jù)其他網(wǎng)頁進(jìn)行調(diào)整，把相似度大于某個閾值的頁面聚為同一類，對相同類別的網(wǎng)頁泛化得出抽取結(jié)構(gòu)模板。在網(wǎng)頁簇集合C={P0，P1，…，Pk}中，網(wǎng)頁P(yáng)i需滿足如下表達(dá)式，即對于所有網(wǎng)頁的相似度最高，作為初始模板。

2.5 數(shù)據(jù)提取

將待抽取網(wǎng)頁與模板進(jìn)行距離計算，如果模板中的所有必需節(jié)點都在最后的映射中，說明該網(wǎng)頁滿足此模板，則把抽取規(guī)則制定的內(nèi)容節(jié)點對應(yīng)的網(wǎng)頁內(nèi)容部分抽取出來。

用一個dataset來表示抽取的數(shù)據(jù)，其中每一個網(wǎng)頁是一個元組，模板中每一個是為一個列屬性，對于非主鍵屬性，如果網(wǎng)頁中不含該節(jié)點，即為空值。

3 結(jié)論

這種方法可以不用人工干擾，自動對有多個數(shù)據(jù)記錄的數(shù)據(jù)密集型網(wǎng)頁進(jìn)行批量信息提取，在電子商務(wù)、文獻(xiàn)分析等方面有廣泛的應(yīng)用前景。但是對于新聞、博客、論壇等以自由文本為主要內(nèi)容形式的網(wǎng)頁，在網(wǎng)頁聚類、信息定位和抽取的準(zhǔn)確率等方面還有待于進(jìn)一步研究。

參考文獻(xiàn):

[1] Reis. Automatic Web news extraction using tree edit distance[C].Proceedings of the 13th international conference on World Wide Web，2004:502-511.

[2] Yanghong Z， Bing L. Web Data Extraction Based on Partial Tree Alignment[c].Proceedings of the ACM， 2005:76-85.

[3]. Yeonjung Kim， Jeahyum Park， et al. Web Information Extraction by HTML Tree Edit Distance Matching[C].International Conference on Convergence Information Technology， 2007:2455-2460.

[4] Yang W. Identifying syntactic differences between two programs[J].Software-Practice and Experience，1991，21(7):739-755.

[5] AHONEN-MYKAH. Discovery of frequent word sequences in text， template detection via data mining and its applications[R].Helsinki:Universityof Helsinki，2002

[6] Belf. Frequent term-based text clustering[C].ACM，2002:436-442.

[7] Gupta S. DOM-based content extraction of HTML documents[C].Proceedings of the 12th World Wide Web Conference，2003:512-515.

[8] Sudipto Guha， Rajeev Rastogi，Kyuseok Shim. CURE: an efficient clustering algorithm for large databases[J].Information Systems，2001，26(1):35-58.