基于樹編輯距離的聚類算法數(shù)據(jù)記錄抽取

宮麗娜，祝美蓮

（1.棗莊學(xué)院，山東 棗莊 277160；2.中國(guó)石油大學(xué)（華東），山東 青島 266580）

1 引言

網(wǎng)頁(yè)信息抽取為許多網(wǎng)絡(luò)信息處理應(yīng)用領(lǐng)域包括網(wǎng)絡(luò)數(shù)據(jù)挖掘、網(wǎng)絡(luò)信息檢索等提供了有益的基礎(chǔ).

前人已經(jīng)進(jìn)行了很多網(wǎng)頁(yè)信息抽取方法的研究 (如[3][8]；文獻(xiàn)[1]給出了一個(gè)簡(jiǎn)短的總結(jié)).RoadRunner[2]：自動(dòng)生成包裝器的系統(tǒng)，但是它會(huì)產(chǎn)生一些錯(cuò)誤的模式，準(zhǔn)確率較低.MDR[3]方法是第一個(gè)全自動(dòng)的抽取信息的算法，這種方法完全不需要用的參與.DEPTA[4]算法是MDR方法的一種改進(jìn)，它假設(shè)網(wǎng)頁(yè)中每?jī)蓷l數(shù)據(jù)記錄之間的視覺空間都要比數(shù)據(jù)記錄之間的空間大，但是這種情況并不是總是成立的.所有這些方法都具有一些缺點(diǎn).

本文中，提出了一種新的自動(dòng)從網(wǎng)頁(yè)中抽取數(shù)據(jù)記錄的方法.首先，構(gòu)建DOM模型；第二，我們采用了三種啟發(fā)式的規(guī)則來(lái)發(fā)現(xiàn)網(wǎng)頁(yè)的主數(shù)據(jù)區(qū)域；最后提出了一種基于樹編輯距離的聚類算法，來(lái)分離數(shù)據(jù)記錄.通過大量真實(shí)網(wǎng)頁(yè)的實(shí)驗(yàn)驗(yàn)證，本文方法具有較高的準(zhǔn)確率.

2 主數(shù)據(jù)區(qū)域發(fā)現(xiàn)

2.1 DOM樹模型

本文方法首先需要將網(wǎng)頁(yè)的HTML文檔轉(zhuǎn)化為DOM樹的形式，由于HTML語(yǔ)言本身也不夠嚴(yán)謹(jǐn)，因此要對(duì)源文件進(jìn)行預(yù)處理.同時(shí)我們還要對(duì)標(biāo)簽進(jìn)行過濾，去掉一些沒有用的干擾標(biāo)簽.如<select>標(biāo)簽，這個(gè)標(biāo)簽下面通常會(huì)有很多的節(jié)點(diǎn)選擇，會(huì)給我們后面的分析造成干擾，預(yù)處理的時(shí)候?qū)⑵淙サ?

2.2 主數(shù)據(jù)區(qū)域發(fā)現(xiàn)

通常，列表頁(yè)面都滿足下面幾個(gè)特征[8]：DOM樹中的每條數(shù)據(jù)記錄都是有一系列的連續(xù)兄弟子樹組成的.而且，能夠發(fā)現(xiàn)每條數(shù)據(jù)記錄都是由一定數(shù)量的完整子樹構(gòu)成的.

從上述特性得知，定位主數(shù)據(jù)區(qū)域我們所要做的就是找到包含所有記錄項(xiàng)的最小DOM子樹的根節(jié)點(diǎn).本文給出了三種啟發(fā)式方法，分別從DOM樹的不同特征考慮當(dāng)前節(jié)點(diǎn)是否包含所有目標(biāo)記錄項(xiàng).

2.2.1 最大扇出子樹法，思想是：一個(gè)節(jié)點(diǎn)包含的子節(jié)點(diǎn)越多，它就越有可能是包含所有數(shù)據(jù)記錄的最小DOM子樹的根節(jié)點(diǎn).

2.2.2 最大內(nèi)容增大法.計(jì)算節(jié)點(diǎn)的總的內(nèi)容量，并減去節(jié)點(diǎn)的平均內(nèi)容量（節(jié)點(diǎn)大小除以節(jié)點(diǎn)扇出值），作為節(jié)點(diǎn)的內(nèi)容增大量，一個(gè)節(jié)點(diǎn)的內(nèi)容增大量越大，它越有可能是包含所有數(shù)據(jù)記錄的DOM子樹的根節(jié)點(diǎn).

2.2.3 最大標(biāo)記量法，考慮子樹中包含的HTML標(biāo)記量，對(duì)于沒有祖先關(guān)系的兩個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)包含的HTML標(biāo)記越多，它排位越靠前.

將上述三種方法分別加一個(gè)權(quán)重，根據(jù)權(quán)重計(jì)算得到一個(gè)加權(quán)平均的排序節(jié)點(diǎn)列表.列表的第一個(gè)節(jié)點(diǎn)就是我們所要找的節(jié)點(diǎn).

3 數(shù)據(jù)記錄分割

接下來(lái)要研究的是如何將主數(shù)據(jù)區(qū)域中的多條數(shù)據(jù)記錄進(jìn)行分離.我們采用樹編輯距離來(lái)表示兩棵相鄰子樹的相似度.

3.1 樹編輯距離

計(jì)算兩棵樹的樹編輯距離，主要就是要找出兩棵樹之間的一個(gè)權(quán)值最小的映射，這個(gè)映射可以有如下的定義：

假定X是一棵樹，X[i]是樹X中第i個(gè)子節(jié)點(diǎn).那么T1和T2之間的映射M是滿足以下條件的有序數(shù)對(duì)(i,j)的集合對(duì)于任何(a1,b1)，(a2,b2)

（1）a1=a2 當(dāng)且僅當(dāng) b1=b2

（2）T1[a1]是 T1[a2]的左鄰節(jié)點(diǎn)當(dāng)且僅當(dāng) T2[b1]是 T2[b2]的左鄰節(jié)點(diǎn)

（3）T1[a1]是T1[a2]的父節(jié)點(diǎn)當(dāng)且僅當(dāng)T2[b1]是T2[b2]的父節(jié)點(diǎn)

本文采用簡(jiǎn)單樹匹配算法來(lái)求解樹編輯距離.令A(yù)=(RA,A1,…,Am)和 B=（RB,B1,…,Bn）是兩棵樹，其中 RA和 RB是 A和B的根節(jié)點(diǎn)，Ai和Bj分別是A和B的第i個(gè)和第j個(gè)第1層子樹.當(dāng)RA和RB的標(biāo)記相同時(shí)，A和B的最大匹配為MA,B+1，其中MA,B是<A1,A2,…,Am>和<B1,B2,…,Bn>的最大匹配.偽代碼如算法1所示：

算法 1：STM(A,B)

1 開始

2 如果RA和RB不同

3 返回0;

4 否則

5 設(shè)m為節(jié)點(diǎn)RA的子樹的個(gè)數(shù)

6 設(shè)n為節(jié)點(diǎn)RB的子樹的個(gè)數(shù)

7 M[i,0]←0所有的 i=0,…,m

8 M[0,j]←0所有的 j=0,…,n

9 從i=1到m

10 從j=1到n

11 W[i,j]←STM(Ai,Bj)

12 M[I,j]=max(M[i,j-1],M[i-1,j],M[i-1,j-1]+W[i,j])

13 結(jié)束

14 結(jié)束

15 返回M[i,j]+1

16 結(jié)束

給定兩個(gè)HTML文檔，它們對(duì)應(yīng)的DOMTree為T1,T2，T1,和T2中每一個(gè)節(jié)點(diǎn)標(biāo)記對(duì)應(yīng)HTML中的一個(gè)標(biāo)簽，其中文本節(jié)點(diǎn)用<text>節(jié)點(diǎn)代替.記樹T的節(jié)點(diǎn)數(shù)目為|T|，定義T1與T2的相似度為：

上式中，|T1|，|T2|分別表示兩棵樹的最大匹配節(jié)點(diǎn)數(shù).兩棵樹的最大匹配節(jié)點(diǎn)數(shù)越大，則兩棵樹越相似，即它們所代表的HTML文檔也就越相似.

3.2 聚類算法

由第三節(jié)中描述的列表頁(yè)面的特點(diǎn)知，數(shù)據(jù)記錄可以是一棵或者多棵連續(xù)子樹的集合，這樣可以產(chǎn)生候選的分割方案，設(shè)主數(shù)據(jù)區(qū)域的根節(jié)點(diǎn)有n棵子樹，則可以產(chǎn)生2n-1候選分割方法，算法的效率很低.本文采用聚類算法將子樹分類，來(lái)減少候選分割方案的數(shù)量，來(lái)提高算法的效率.

對(duì)樣本空間進(jìn)行聚類，需規(guī)定樣本的相異度值，其由相異度矩陣表達(dá)，定義如下.

相異度矩陣(dissim ilarity matrix)用來(lái)存儲(chǔ)n個(gè)樣本兩兩之間的相似性，形式為n×n維矩陣：

我們用d(X2,X1)來(lái)表示樣本Xi和Xj相異性，取值非負(fù)數(shù).對(duì)象i和j越相似，其值越接近0；否則其值越大.

用上一節(jié)介紹的STM算法計(jì)算兩棵子樹的距離，首先將每棵子樹都作為一個(gè)單獨(dú)的簇，定義一個(gè)閾值d0，當(dāng)兩棵子樹之間的距離小于d0時(shí)，把兩棵子樹聚類，作為一個(gè)大類.閾值d0的大小會(huì)影響到簇的數(shù)量和規(guī)模：如果d0比較大，簇的規(guī)模也會(huì)比較大大，反之類似.所以選擇一個(gè)適當(dāng)?shù)拈撝稻垲惓晒Φ年P(guān)鍵，通過多次試驗(yàn)本文選取的d0值為0.15.

設(shè)Ci和Cj分別代表兩個(gè)不同的類，Xi和Xj分別表示Ci和Cj的類中心，則類Ci和Cj之間距離我們采用平均距離進(jìn)行度量：

其中，ni和nj表示類Ci和Cj的樣本數(shù)目.

算法2：聚類

(1)假設(shè)每個(gè)子樹Xi都是一個(gè)簇{Xi}.

(2)設(shè)d0為相似度閾值.

(3)計(jì)算相似度矩陣值D=(Dij)m×m，m是簇的個(gè)數(shù).

(4)找到最小的矩陣值D,

如果D值小于d0,

將Xi和Xj合并為一個(gè)新的簇,并設(shè)m=m-1.

否則結(jié)束

(5)如果m>2繼續(xù)執(zhí)行(3)

(6)否則結(jié)束.

如圖1給出了一個(gè)簡(jiǎn)單的聚類結(jié)果的例子，10棵子樹，聚成了三個(gè)類.

圖1 聚類結(jié)果示例

前面的預(yù)處理步驟完成后，我們下面生成候選數(shù)據(jù)記錄分割方案.我們利用文獻(xiàn)[8]中的方法產(chǎn)生候選分割方案：

圖2 候選分割方案

3.4 最佳分割方案

為了獲得正確的數(shù)據(jù)記錄分割方案，我們依賴列表頁(yè)面所具有的特征，即每條記錄的樹結(jié)構(gòu)相似.這樣我就可以選擇具有最高相似度的候選分割方案作為最終結(jié)果，我們?yōu)槊恳粭l記錄添加一個(gè)根節(jié)點(diǎn)，構(gòu)造成樹結(jié)構(gòu).然后根據(jù)STM算法來(lái)計(jì)算每條記錄之間的相似性.計(jì)算公式如下面的公式(3)：

根據(jù)公式3對(duì)圖2獲得的候選分割方案分別計(jì)算其相似性，可以看出，以C0開始的分割方案的相似性最高，這樣就選擇列表當(dāng)中的第一種方案作為最佳分割方案.

4 實(shí)驗(yàn)分析

4.1 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用標(biāo)準(zhǔn)指標(biāo)查全率(Recall)和準(zhǔn)確率(Precision)來(lái)評(píng)價(jià)我們的系統(tǒng)的好壞.

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

為了檢驗(yàn)本為提出的方法的效果，選用了不同類型的200個(gè)網(wǎng)頁(yè)作為實(shí)驗(yàn)對(duì)象，挖掘網(wǎng)頁(yè)中的相似記錄項(xiàng).同時(shí)將我們的實(shí)驗(yàn)結(jié)果與MDR算法進(jìn)行比較，實(shí)驗(yàn)的數(shù)據(jù)如表1所示.

從表1可以看出，對(duì)于淘寶和亞馬遜等站點(diǎn)，基于本文方法抽取相似記錄項(xiàng)，都取得了100%的召回率和100%準(zhǔn)確率.經(jīng)查看網(wǎng)頁(yè)結(jié)構(gòu)發(fā)現(xiàn)網(wǎng)頁(yè)結(jié)構(gòu)化程度非常高.易趣和CNKI等站點(diǎn)的召回率和準(zhǔn)確率相對(duì)較低，經(jīng)查看網(wǎng)頁(yè)結(jié)構(gòu)，發(fā)現(xiàn)這些站點(diǎn)的結(jié)構(gòu)化程度相對(duì)較低.從總體上看，實(shí)驗(yàn)取得了98.82%的召回率和99.52%的準(zhǔn)確率，說(shuō)明本文方法，對(duì)于各種類型的列表網(wǎng)頁(yè)的信息抽取，取得了很好的效果.本文方法同MDR方法結(jié)果進(jìn)行比較，在準(zhǔn)確率和召回率方面都有提高，證明本文方法的有效性.

表1 實(shí)驗(yàn)結(jié)果

5 總結(jié)

本文提出了將最大扇出子樹法、最大內(nèi)容增大法和最大標(biāo)記量法三種啟發(fā)式方法結(jié)合的思路查找網(wǎng)頁(yè)的主數(shù)據(jù)區(qū)域.在數(shù)據(jù)記錄分割階段，采用基于樹編輯距離的聚類算法來(lái)減少候選分割方案，最后通過給出的公式挑選出最佳分割方案，完成數(shù)據(jù)記錄的抽取.實(shí)驗(yàn)證明對(duì)各種類型列表頁(yè)面進(jìn)行數(shù)據(jù)記錄抽取的效果都很不錯(cuò).但是本文方法只適用于一個(gè)主數(shù)據(jù)區(qū)域的頁(yè)面，以后將進(jìn)一步研究多信息塊的數(shù)據(jù)記錄抽取.

〔1〕A.H.F.Laender,B.A.Ribeiro-Neto,A.Soares da Silva,J.S.Teixeira,A brief survey of web data extraction tools,ACM SIGMOD Record 31(2)(2002)84–93.

〔2〕V.Crescenzi,G.Mecca,P.Merialdo,ROADRUNNER:towards automatic data extraction from large web sites,in:Proceedings of the 2001 International VLDB Conference,(2001):109–118.

〔3〕B.Liu,Grossman,R.and Y.Zhai,Mining data records in Web pages.KDD,(2003):601-606.

〔4〕Y.Zhai,B.Liu,Structured data extraction from the web based on partial tree alignment,IEEE Transactions on Knowledge and Data Engineering 18 (12)(2006)1614–1628.

〔5〕A.Arasu,H.Garcia-Molina,Extracting structured data from web pages,in:Proceedings of the ACM SIGMOD International Conference on Management of Data,(2003).

〔6〕C.Chang,S.Lui,IEPAD:information extraction based on pattern discovery,in:Proceedings of 2001 InternationalWorldWide Web Conference,(2001):681–688.

〔7〕B.Liu,Y.Zhai,NET:System for extracting Web data from flat and nested data records.In Proceedings of the Conference on Web Information Systems Engineering,(2005):487-495.

〔8〕Manuel A′lvarez,Alberto Pan,Juan Raposo,Fernando Bellas,Fidel Cacheda,Extracting lists of data records from semi-structured web pages,Data&Knowledge Engineering(64),(2008):491-509.