基于等價(jià)壓縮快速聚類的Web表格知識抽取

吳小龍， 曹存根

(1. 中國科學(xué)院 計(jì)算技術(shù)研究所 智能信息處理重點(diǎn)實(shí)驗(yàn)室，北京 100190；2. 中國科學(xué)院大學(xué)，北京 100049)

0 引言

Web表格知識抽取是一種重要的獲取高質(zhì)量知識的途徑，在知識獲取、知識圖譜、網(wǎng)頁挖掘、信息檢索、問答系統(tǒng)等方面都有廣泛的研究意義與應(yīng)用價(jià)值。

Web表格作為一種簡潔有效的知識表現(xiàn)形式，富含結(jié)構(gòu)化和半結(jié)構(gòu)化的知識，并且大量存在于網(wǎng)頁之中。Google的一項(xiàng)研究表明，大概有1.5億高質(zhì)量的關(guān)系表存在于萬維網(wǎng)之中[1]。Web表格資源豐富，具有結(jié)構(gòu)化和半結(jié)構(gòu)的特點(diǎn)，使得Web表格成為重要的知識抽取來源，并被廣泛應(yīng)用于大規(guī)模知識庫的構(gòu)建之中[2]。大型知識庫DBpedia和YAGO以維基百科的Infobox表、維基表格 Wikitable 作為主要知識來源之一，Google的知識圖譜也將Web表格作為知識融合的主要對象[3]。

傳統(tǒng)的Web表格知識抽取方法主要依賴于良好的表格結(jié)構(gòu)和足夠的先驗(yàn)知識，但在復(fù)雜的表格結(jié)構(gòu)及先驗(yàn)知識不足等情形下難以奏效。針對這類方法的問題，充分利用表格自身的結(jié)構(gòu)特點(diǎn)，以無監(jiān)督的聚類方法挖掘表格結(jié)構(gòu)共性，從而推測語義結(jié)構(gòu)共性來獲取知識，是一條解決問題的新思路。

然而，據(jù)作者所知，在目前的文獻(xiàn)中尚未發(fā)現(xiàn)專門用于Web表格聚類的相關(guān)算法，傳統(tǒng)的經(jīng)典聚類方法如密度峰值聚類方法[4](clustering by fast search and find of density peaks，DPC)直接用于表格聚類又將面臨相似性度量困難、時(shí)間復(fù)雜度較高、聚類中心較難選取等問題。

因此，本文提出了一套可面向大規(guī)模數(shù)據(jù)的基于等價(jià)壓縮快速聚類的Web表格知識抽取方法，通過發(fā)掘表格的形式結(jié)構(gòu)類型與特點(diǎn)，并從相似形式結(jié)構(gòu)的表格中推測表格的語義結(jié)構(gòu)，以“同類結(jié)構(gòu)相同抽取方法”的辦法從中抽取知識。具體地，本文的主要工作和貢獻(xiàn)如下：

(1) 針對重復(fù)的DOM(document object model)子樹結(jié)構(gòu)造成的表格相似性度量困難問題，本文基于表格形式上的伸縮與語義結(jié)構(gòu)無關(guān)的假設(shè)，提出了基于DTW(dynamic time warping)的方法來構(gòu)造兩棵DOM樹的相似性度量，使得表格相似性度量更符合表格的形式特點(diǎn)。

(2) 通過構(gòu)造等價(jià)距離，將絕大部分的復(fù)雜的兩個(gè)Web表格之間的距離計(jì)算等價(jià)為構(gòu)造的基準(zhǔn)坐標(biāo)空間下的歐氏距離計(jì)算，縮短單個(gè)點(diǎn)對的距離計(jì)算時(shí)間，并提出了一種自壓縮Canopy算法進(jìn)行預(yù)聚類，剔除等價(jià)表格，并減少大量不必要的距離計(jì)算，以降低聚類時(shí)間復(fù)雜度。

(3) 為避免半自動(dòng)選擇聚類中心帶來的主觀性和不確定性，提出了一種確定聚類中心點(diǎn)的啟發(fā)式算法，解決了聚類中心難以選取的問題。

(4) 結(jié)合上述工作提出了一種可面向大規(guī)模數(shù)據(jù)的基于等價(jià)壓縮的Web表格快速聚類算法，并針對聚類結(jié)果構(gòu)造模板化的抽取算法來抽取知識，所抽取的知識三元組的準(zhǔn)確率也達(dá)到了令人滿意的結(jié)果。

1 相關(guān)工作

本節(jié)將介紹傳統(tǒng)的Web表格知識抽取方法以及候選的可用于Web表格聚類的相關(guān)算法。

1.1 Web表格知識抽取方法

傳統(tǒng)的Web表格知識抽取研究主要通過先驗(yàn)知識庫的本體映射、實(shí)體對齊，或以大量的人工標(biāo)記數(shù)據(jù)作為有監(jiān)督學(xué)習(xí)手段，在默認(rèn)的良好的表格結(jié)構(gòu)下，發(fā)掘表格內(nèi)的實(shí)體、概念及其關(guān)系，從而抽取知識。

用已存在于知識庫中的實(shí)體、概念去識別表格的元素，該過程可稱之為表格注釋[5-6]?；谌酥阅芾斫獗砀袷且?yàn)槿四X中擁有對知識的認(rèn)識，Wang等[7]通過使用知識庫Probase的通用概率分類體系(本體)，構(gòu)造了一種基于表頭識別和實(shí)體識別的框架，以用于從網(wǎng)頁表格中獲取新知識。類似地，Ritze等[8]也運(yùn)用了大型知識庫DBpedia，將表格的行和列的內(nèi)容映射到DBpedia知識庫中，以尋找相對應(yīng)的實(shí)體和關(guān)系模式，從而推測剩余表格的新實(shí)體和關(guān)系。另外，Hogan等[9]運(yùn)用已有的開放鏈路數(shù)據(jù)去識別維基百科表格中已有的實(shí)體關(guān)系，并推測表中其他未被鏈接的實(shí)體和已被鏈接的實(shí)體具有相同的關(guān)系，從而獲取新的實(shí)體關(guān)系。Nagy等[10]通過挑選空白、單元格字符數(shù)等7個(gè)單元格特征，提供了一個(gè)可訓(xùn)練的關(guān)鍵單元格定位算法來學(xué)習(xí)表格的關(guān)鍵單元格的特征。Pinto等[11]將文本文檔中ASCII表的每一行標(biāo)記為非知識行、表頭行、數(shù)據(jù)行、注腳行等，結(jié)合空白特征、文本特征、分隔符特征等，構(gòu)建并訓(xùn)練條件隨機(jī)場模型，用于表格定位、單元格類型判斷等，進(jìn)而推測表格的知識分布，用以表格抽取。

此外，在良好的表格結(jié)構(gòu)下，可以根據(jù)表格內(nèi)各單元格內(nèi)容自身的特點(diǎn)及其與附近單元格內(nèi)容的關(guān)系來分析表格內(nèi)的語義關(guān)系。Chen等[12]利用表格的單元格、行和列元素之間的字符串、命名實(shí)體以及數(shù)字類型的相似性來識別表格的內(nèi)容模式。Dalvi等[13]通過聚類同類項(xiàng)并結(jié)合Hearst模式獲得的概念來給這些同類項(xiàng)分配相對應(yīng)的概念從而獲取新的概念實(shí)例對。Pivk等[14]將Web表格轉(zhuǎn)化為一個(gè)邏輯表格，描述表格元素之間的關(guān)系，達(dá)到區(qū)分表格中的屬性單元格和實(shí)例單元格的目的。

綜上所述，傳統(tǒng)的Web表格知識抽取方法主要依賴于良好的表格結(jié)構(gòu)和足夠的先驗(yàn)知識，也未能充分利用表格自身的形式結(jié)構(gòu)特點(diǎn)，難以應(yīng)對復(fù)雜的表格結(jié)構(gòu)以及先驗(yàn)知識不足等問題。

1.2 Web表格聚類方法

Web表格由Lautert等[15]根據(jù)經(jīng)驗(yàn)分為如圖1所示的類型。一般而言，相似形式結(jié)構(gòu)的表格擁有相似的語義結(jié)構(gòu)。Web表格聚類避免了大量數(shù)據(jù)標(biāo)注的資源依賴性問題以及復(fù)雜的特征工程問題，通過無監(jiān)督聚類，發(fā)掘表格形式結(jié)構(gòu)的共性，從而發(fā)現(xiàn)表格的語義結(jié)構(gòu)，便于將表格分類處理。

圖1 Web表格分類圖

對于海量的、形式多樣的Web表格，具備解決大規(guī)模數(shù)據(jù)問題、發(fā)現(xiàn)任意形狀簇等關(guān)鍵能力的聚類算法尤為必要。在目前的文獻(xiàn)中我們尚未發(fā)現(xiàn)專門用于Web表格聚類的相關(guān)算法，然而在候選的可用的相關(guān)算法中，密度峰值聚類DPC是常見的、較為有效的大規(guī)模數(shù)據(jù)聚類方法。在該方法中，聚類中心是那些相對于它們的鄰居有著高密度且它們之間的相對距離較大的點(diǎn)[16]，由兩個(gè)變量來刻畫： 每一個(gè)樣本點(diǎn)的局部密度ρi，以及它與最近鄰高密度點(diǎn)之間的相對距離δi。

局部密度的定義如式(1)所示。

相對距離δi定義如式(2)所示。

總體說來，DPC算法思想簡單直觀，能夠快速有效地發(fā)現(xiàn)任意形狀的簇，但是其時(shí)間復(fù)雜度為Ο(N2)，且聚類中心需要人工判斷選擇。因此，有效降低時(shí)間復(fù)雜度，實(shí)現(xiàn)DPC算法全自動(dòng)化，對于解決大規(guī)模數(shù)據(jù)聚類、發(fā)揮DPC簡潔有效的優(yōu)勢有著重要的現(xiàn)實(shí)意義。

2 基于等價(jià)壓縮快速聚類的Web表格知識抽取

本節(jié)中，我們從改善Web表格相似性度量、降低時(shí)間復(fù)雜度以及自動(dòng)聚類中心選取三個(gè)方面提出了基于等價(jià)壓縮的Web表格聚類算法，以進(jìn)行表格聚類，然后對聚在同一類的具有相似結(jié)構(gòu)的表格分別使用相同的模板化的抽取方法抽取知識。

2.1 基于等價(jià)壓縮的Web表格聚類

針對多數(shù)聚類算法如密度峰值聚類方法DPC的相似性度量困難、時(shí)間復(fù)雜度較高、聚類中心較難選取等問題，我們提出了以下三個(gè)方法予以解決。

(1) 通過DTW算法，改善表格相似性度量；

(2) 通過自壓縮Canopy聚類，降低時(shí)間復(fù)雜度；

(3) 通過啟發(fā)式聚類中心選取，提高算法自動(dòng)性。

2.1.1 基于DTW的Web表格相似性度量

對于常見的經(jīng)典聚類算法而言，相似性度量/距離度量是必不可少的，是決定聚類算法效果的關(guān)鍵。Web表格以行和列的形式組織而成，其中若干行和列在形式上是重復(fù)的，這種重復(fù)結(jié)構(gòu)不影響表格形式特點(diǎn)，但極為影響表格的相似性度量，如傳統(tǒng)的樹編輯距離[17]、最長公共子串[18]、簡單樹匹配算法[19]都較難解決該問題。因此，解決重復(fù)子結(jié)構(gòu)帶來的問題是Web表格相似性度量的關(guān)鍵。

為解決問題，我們首先給出以下定義：

定義1Web表格。對于具有表格形式的顯式結(jié)構(gòu)，并以DOM(HTML標(biāo)簽樹)為隱式結(jié)構(gòu)的網(wǎng)頁內(nèi)容組織形式，我們稱之為Web表格(Web table)。

定義2Web表格相似度。任意兩個(gè)表格的DOM樹的相似度Sim(Treei,Treej)，等于該兩個(gè)Web表格的相似度 Sim(Tablei,Tablej)。

定義3葉子路徑。DOM樹的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的HTML標(biāo)簽序列稱為DOM樹葉子路徑pathi。

定義4葉子路徑相似度。任意兩個(gè)葉子路徑的相似度ψ(pathi,pathj)的計(jì)算如式(3)所示。

(3)

其中，Max(γ)=a×min{|pathi|,|pathj|}，Min(γ)=-a×min{|pathi|,|pathj|}-b×ΔL，其中ΔL=||pathi|-|pathj||。a表示字符串編輯距離的匹配操作的權(quán)重，b表示替換、插入或刪除操作的權(quán)重。

接著，結(jié)合表格結(jié)構(gòu)特點(diǎn)，我們引入一個(gè)假設(shè)：

假設(shè)1表格形式上的伸縮(重復(fù)子結(jié)構(gòu)的多少)與語義結(jié)構(gòu)無關(guān)[20]。

然后，我們通過對DOM樹以先序遍歷的方式獲得葉子路徑，計(jì)算任意兩兩葉子路徑相似度?；诩僭O(shè)1，使用DTW[21]的方法計(jì)算兩棵樹的累積距離，如式(4)所示。

其中，Φ[i,j]表示一個(gè)(m+1)×(n+1)的矩陣，m和n分別表示兩個(gè)表格的路徑數(shù)，將Φ[i,0] 和Φ[0,j] 初始化為，Φ[0,0]=0，以及進(jìn)行等價(jià)轉(zhuǎn)換φ(pathi,pathj)=1-ψ(pathi,pathj)，另外，Min=min {Φ[i,j-1],Φ[i-1,j],Φ[i-1,j-1]}，因此Φ[m,n]可表示兩棵DOM樹的累積距離。設(shè)N為動(dòng)態(tài)規(guī)整路徑的節(jié)點(diǎn)數(shù)。

最終，可得兩棵樹的相似度，如式(5)所示。

2.1.2 自壓縮Canopy預(yù)聚類

對于樣本集，通過“相似去重”可以縮小數(shù)據(jù)集規(guī)模，消除同質(zhì)化樣本的集體效應(yīng)，以更好地發(fā)現(xiàn)樣本間的相互關(guān)系與存在模式，這種思想我們稱之為等價(jià)壓縮。

為降低聚類算法的時(shí)間復(fù)雜度，我們基于等價(jià)壓縮的思想提出了自壓縮Canopy預(yù)聚類方法，具體如下：

(1) 通過構(gòu)造等價(jià)距離，將復(fù)雜的兩個(gè)Web表格之間的DTW距離計(jì)算等價(jià)為構(gòu)造的基準(zhǔn)坐標(biāo)空間下的歐氏距離計(jì)算，從而縮短單個(gè)點(diǎn)對的距離計(jì)算時(shí)間。

(2) 通過提出一種自壓縮Canopy聚類算法進(jìn)行預(yù)聚類，在聚類的過程中剔除等價(jià)表格，以降低聚類規(guī)模。在預(yù)聚類的結(jié)果下，縮小點(diǎn)對距離計(jì)算范圍，即只計(jì)算在同一個(gè)類內(nèi)的點(diǎn)對距離，從而減少不必要的點(diǎn)對距離計(jì)算。

為了“相似去重”，刻畫表格等價(jià)性，我們給出了以下兩個(gè)定義。

定義5等價(jià)表格。設(shè)定一個(gè)極小的數(shù)ε，ε>0，如果兩個(gè)表格Tablei和Tablej的距離小于ε，那么我們認(rèn)為這兩個(gè)表為等價(jià)表格。因此，對于第三個(gè)表格Tablek，如果已知Tablei和Tablek的距離為dik，那么Tablej和Tablek的距離djk等于dik。

由2.1.1節(jié)內(nèi)容可知，設(shè)有S個(gè)表，則所有表格DTW距離所產(chǎn)生的時(shí)間復(fù)雜度為ΟD((SMNmn)2)(M和N分別表示兩棵DOM樹的葉子路徑總數(shù)，m和n分別表示兩條葉子路徑的長度)。通過使用等價(jià)距離，時(shí)間復(fù)雜度變?yōu)棣疍(KSMNmn)+ΟE((KS)2)(即Ο(KS)的DTW距離計(jì)算加上Ο(S2)的K維向量之間的Euclidean歐氏距離計(jì)算)，其中K遠(yuǎn)小于S，且ΟE(S2)的歐氏距離計(jì)算時(shí)間遠(yuǎn)小于ΟD(S2)的DTW距離計(jì)算時(shí)間。由以上時(shí)間復(fù)雜度分析可知，等價(jià)距離極大地縮短了單個(gè)點(diǎn)對的距離計(jì)算時(shí)間。

在構(gòu)造等價(jià)距離之后，基于等價(jià)壓縮的思想我們提出了自壓縮Canopy聚類算法，如算法1所示。

算法1 自壓縮Canopy聚類算法輸入: 樣本集S=Xi{}Ni=1,兩個(gè)距離閾值T1,T2,并且T1>T2輸出: Canopyi{}Ki=1,每個(gè)Canopy包含的樣本點(diǎn)(1) 從樣本集S中隨機(jī)選出一個(gè)小樣本集S′=Yi{}Mi=1;(2) 調(diào)用Canopy原始聚類算法[22]求得小樣本集S′的L個(gè)Canopy中心Ci{}Li=1;(3) 結(jié)合中心Ci{}Li=1在S對應(yīng)的樣本點(diǎn),對S進(jìn)行排序,將包含樣本集數(shù)量多的Canopy的中心點(diǎn)優(yōu)先處理,從而形成一個(gè)有優(yōu)先處理順序的新樣本集S″,并都標(biāo)記為1;(4) 從新樣本集S″中依次選擇一個(gè)標(biāo)記為1的樣本點(diǎn)Xj作為一個(gè)Canopyi的中心,并將其標(biāo)記改為0;(5) 計(jì)算樣本集S″中除Xj之外的所有標(biāo)記為1的樣本Xi{}Ni=1Xj到Xj的等價(jià)距離d′ij;(6) 如果d′ij<ε, 該樣本Xi為Xj的等價(jià)樣本(等價(jià)表格),保存該等價(jià)關(guān)系,并將該樣本Xi標(biāo)記改為0;如果d′ij

其中，步驟(2)、步驟(3)的目的在于通過隨機(jī)構(gòu)造小樣本集得到一些初始預(yù)聚類中心，使得這些中心對應(yīng)的樣本點(diǎn)能在循環(huán)步驟(7)的前若干次能找到大量的等價(jià)表格，從而減少步驟(5)中距離的計(jì)算次數(shù)，即當(dāng)越多的樣本被標(biāo)記為0時(shí)，樣本規(guī)模就不斷縮小，算法的執(zhí)行速度加快。

通過自壓縮Canopy聚類，可以得到若干個(gè)Canopy，由于Canopy預(yù)聚類旨在說明出現(xiàn)在同一個(gè)Canopy里的樣本點(diǎn)才有可能被聚在同一個(gè)類[23]。因此我們只需要計(jì)算同一個(gè)Canopy里的任意樣本點(diǎn)之間的點(diǎn)對距離，在滿足一般的聚類過程和結(jié)果前提下，減少不必要的點(diǎn)對距離計(jì)算。

2.1.3 啟發(fā)式聚類中心選取

在DPC算法中，聚類中心通常是那些局部密度ρi和相對距離δi都比較大的點(diǎn)。因此通過構(gòu)造γi=ρi×δi，找出γi值比較突出的點(diǎn)，對于自動(dòng)識別聚類中心有重要的啟發(fā)式作用。由于局部密度ρi和相對距離δi可能不在一個(gè)數(shù)量級，所以為使γi值更合理，需要對ρi和δi進(jìn)行歸一化，如式(7)所示。

由圖2可知，UCI的Aggregation和Flame數(shù)據(jù)集的γi，γi值比較突出的點(diǎn)分別有7個(gè)和兩個(gè)(如圖2中虛線上方的稀疏的圓圈所示，因?yàn)閭€(gè)別γi值較為接近，兩圖中都有兩個(gè)幾乎重疊的圓圈)，與這兩個(gè)數(shù)據(jù)集的實(shí)際類別數(shù)保持一致。由此可見，γi值比較突出的點(diǎn)正是候選的聚類中心點(diǎn)，找出γi值比較突出的點(diǎn)是解決問題的關(guān)鍵。

圖2 UCI的Aggregation和Flame數(shù)據(jù)集的γi散點(diǎn)圖

如圖2所示，γi值比較突出的點(diǎn)在圖中較為稀疏，而不突出的點(diǎn)則較為密集且平滑，在某一點(diǎn)處發(fā)生階躍(如圖2中虛線所示)。因此確定產(chǎn)生“階躍”的位置，在“階躍”點(diǎn)前的所有較大的γi值所對應(yīng)的點(diǎn)即為聚類中心點(diǎn)。

由上分析，我們根據(jù)聚類中心的特點(diǎn)，提出了啟發(fā)式聚類中心選取算法，具體流程如算法2所示。

算法2 啟發(fā)式聚類中心點(diǎn)選取算法輸入: 樣本集S=Xi{}Ni=1中所有樣本點(diǎn)的局部密度ρi和相對距離δi,截?cái)嗑嚯xd′c輸出: 聚類中心點(diǎn)Ci{}Mi=1(1) 計(jì)算每一個(gè)樣本點(diǎn)Xi的γi值;(2) 對γi值進(jìn)行降序排序,使得γq1≥…≥γqN;(3) 計(jì)算每個(gè)γqi的密度ργqi;(參考公式(1))ργqi=∑jχdγqiγqj-d′c(), dγqiγqj=γqi-γqj(4) 計(jì)算相鄰兩ργqi值之差Spaceqi=ργqi-ργqi-1;(5) 找出“階躍點(diǎn)”位置qj～j:argmaxSpaceqj{};(6) 從前qj-1個(gè)γi找出相應(yīng)樣本點(diǎn)作為聚類中心Ci{}Mi=1;

基于自壓縮Canopy聚類和啟發(fā)式聚類中心選取算法，我們提出了基于等價(jià)壓縮的Web表格快速聚類算法(fast clustering with equivalent compression，F(xiàn)CEC)，如算法3所示。

算法3 基于等價(jià)壓縮的Web表格快速聚類輸入: 表格樣本集S=Xi{}Ni=1,截?cái)嗑嚯xdc輸出: 每一個(gè)表格樣本點(diǎn)Xi的類別標(biāo)簽Lj{}Kj=1(1) 對樣本集S執(zhí)行算法1(自壓縮Canopy聚類),得到K個(gè)Canopy即Canopyi{}Ki=1;(2) 計(jì)算每個(gè)Canopy所包含的樣本點(diǎn)的點(diǎn)對等價(jià)距離d′ij;(3) 計(jì)算每個(gè)樣本點(diǎn)Xi的局部密度ρi;(4) 計(jì)算每個(gè)樣本點(diǎn)Xi的相對距離δi;(5) 分析γi=ρi×δi,執(zhí)行算法2,即通過啟發(fā)式算法自動(dòng)選擇聚類中心點(diǎn);(6) 給每個(gè)樣本點(diǎn)Xi選擇最近的聚類中心,賦予類標(biāo)簽Lj;(7) 計(jì)算每個(gè)類的平均密度上界ρUpK,判斷每一個(gè)樣本點(diǎn)Xi是否為離群點(diǎn)。

2.2 基于FCEC的表格知識抽取

通過基于FCEC的Web表格快速聚類，我們把具有相似形式結(jié)構(gòu)的表格聚在一類，針對每一類，采用相應(yīng)的抽取算法(模板化)進(jìn)行知識抽取。

例如，對于水平表格這一類表格，我們可以依據(jù)算法4從表1中抽取出知識三元組<伊夫林卡西爾，職位，出納員>。如表1所示，“姓名”和“職位”為屬性行，由HTML的“th”標(biāo)簽標(biāo)識，而其他行用“tr”標(biāo)識，具體到每個(gè)單元格用“td”標(biāo)識。對于第一列中的實(shí)體，我們可以在第二列的“職位”屬性中找到對應(yīng)屬性值，構(gòu)成“姓名→職位”的語義結(jié)構(gòu)。

表1 水平表格示例

在算法4中，對于水平表格這一類型的表格來說，屬性或?qū)嶓w關(guān)系(Predicate(k))一般出現(xiàn)在首行，主實(shí)體(Subject(k))出現(xiàn)在首列，其他列為客體或?qū)傩灾?Object(k))。根據(jù)大量實(shí)驗(yàn)觀察，過濾規(guī)則可為： 第一列為主實(shí)體列，如果第一列為字母或者數(shù)字序列，則依次向右找到第一個(gè)實(shí)體列作為主實(shí)體列。

算法4 面向水平表格的模板化知識抽取算法輸入: 通過算法3聚類得到的水平表格(M行N列)輸出: 三元組< Subject(k), Predicate(k), Object(k)>(1) For i=0 to M do(2) For j=0 to N do(3) if th[i=0, j] 且td[i,j=0]滿足過濾規(guī)則 do P(k)‰ th[i=0, j]; O(k)‰ td[i, j]; S(k)‰ td[i, j=0];(4) End for(5) End for

3 實(shí)驗(yàn)與分析

為了驗(yàn)證所提算法的可行性和性能效果，我們采用不同類型的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

(1) UCI公開數(shù)據(jù)集： Aggregation、Iris、Flame數(shù)據(jù)集；

(2) 人造Wiki數(shù)據(jù)集： 爬取50萬個(gè)維基百科網(wǎng)頁，通過Jsoup網(wǎng)頁解析和清洗，隨機(jī)選擇5 000和50 000個(gè)維基表格分別作為Wiki數(shù)據(jù)集S1和S2。

實(shí)驗(yàn)條件和實(shí)驗(yàn)過程：

(1) 實(shí)驗(yàn)采用的硬件條件： Intel E5-2640 2.40 GHz×2，64 GB RAM；軟件環(huán)境： Windows 7 64 bit，Java 1.7.0，Matlab 2014b。

(2) 實(shí)驗(yàn)過程： 首先在UCI數(shù)據(jù)集上驗(yàn)證等價(jià)距離的有效性，然后驗(yàn)證自壓縮Canopy算法的預(yù)聚類性能，最后驗(yàn)證基于FCEC的表格知識抽取的效果。

3.1 等價(jià)距離的有效性

為驗(yàn)證等價(jià)距離在一般數(shù)據(jù)集上的有效性，我們分別對UCI的Aggregation、Iris、Flame數(shù)據(jù)集進(jìn)行不同K基準(zhǔn)點(diǎn)下(K=0/5/10/20)的聚類測試。其中，K=0時(shí)表示不使用等價(jià)距離，即用常見的距離計(jì)算方式進(jìn)行計(jì)算，并使用DPC聚類。聚類結(jié)果如圖3所示。

圖3 不同K下Aggregation、Iris、Flame數(shù)據(jù)集的聚類

由圖3可知，在不同的K基準(zhǔn)下都能呈現(xiàn)較好的聚類形式，由于基準(zhǔn)的不同，導(dǎo)致聚類的形狀有所區(qū)別，存在伸縮、翻轉(zhuǎn)等現(xiàn)象，但基本都能將各類有效區(qū)分。再者，選取哪K個(gè)基準(zhǔn)點(diǎn)具有隨機(jī)性，我們在K=5/10/20下分別做了20次試驗(yàn)，求得平均聚類準(zhǔn)確率如表2所示。在此，我們使用準(zhǔn)確率(正確聚類樣本數(shù)/樣本總數(shù))來衡量在3個(gè)數(shù)據(jù)集上的聚類效果。

表2 不同K下的不同數(shù)據(jù)集的聚類準(zhǔn)確率

由表2可知，對于不同的K，P值在原來的基礎(chǔ)上上下浮動(dòng)。因此，等價(jià)距離在某種程度上為了提高聚類速度對聚類準(zhǔn)確率有所改變，但基本能達(dá)到原有的、不使用等價(jià)距離的聚類效果，還可能超越，這取決于K的基準(zhǔn)數(shù)的選擇以及基準(zhǔn)表的選擇。事實(shí)上，在實(shí)驗(yàn)中我們發(fā)現(xiàn)，如果K選擇的那K個(gè)基準(zhǔn)點(diǎn)正好是聚類中心時(shí)能達(dá)到比較穩(wěn)定的、近似等價(jià)的聚類結(jié)果。

3.2 自壓縮Canopy算法的預(yù)聚類性能

自壓縮Canopy算法主要通過預(yù)聚類，在聚類的過程中剔除等價(jià)表格，以降低聚類規(guī)模，然后在構(gòu)造好的Canopy集中，只計(jì)算在同一個(gè)Canopy內(nèi)的點(diǎn)對距離，從而減少不必要的點(diǎn)對距離計(jì)算，并將計(jì)算好的點(diǎn)對距離保存，為后續(xù)的表格聚類算法提供輸入。以K=20基準(zhǔn)表進(jìn)行等價(jià)距離轉(zhuǎn)換，對 5 000 和50 000個(gè)Wiki表格進(jìn)行自壓縮后，剔除掉的等價(jià)表格占將近90%，分別剩余590和4 357個(gè)表格。這種現(xiàn)象可能是因?yàn)閃iki表格本身相對模板化、風(fēng)格較為統(tǒng)一，從而導(dǎo)致存在大量的等價(jià)表格出現(xiàn)。

由于自壓縮Canopy算法還需要首先設(shè)定兩個(gè)超參數(shù)： 距離閾值T1，T2，在此，我們使用交叉檢驗(yàn)的方式求得5 000個(gè)表格下的距離閾值T1，T2，如表3所示。因?yàn)門1的大小決定了樣本點(diǎn)的重復(fù)迭代次數(shù)，影響自壓縮Canopy算法時(shí)間；T2的大小決定了每個(gè)Canopy內(nèi)樣本點(diǎn)的數(shù)量，從而影響了需要計(jì)算的樣本點(diǎn)的點(diǎn)對距離計(jì)算的時(shí)間。因此，對于5 000個(gè)表格，當(dāng)我們選擇T1=0.4，T2=0.3時(shí)，可以得到79個(gè)Canopy，且最終FCEC聚類算法所用時(shí)間為20min，且達(dá)到了最好的聚類準(zhǔn)確率0.823。而使用DPC聚類實(shí)際所用時(shí)間為72h(主要為計(jì)算5 000個(gè)樣本點(diǎn)任意點(diǎn)對之間的DTW距離所用時(shí)間)。

表3 對超參數(shù)T1,T2(T1>T2)的交叉驗(yàn)證

其中，79個(gè)Canopy意味著平均每個(gè)Canopy有5 000/79個(gè)點(diǎn)，因此，每個(gè)Canopy內(nèi)的點(diǎn)對計(jì)算量為5 000/79×(5 000/79-1)×1/2≈1 971次，所有Canopy內(nèi)的點(diǎn)對計(jì)算量為1 971×79≈155 728次，考慮等價(jià)距離、自壓縮效果和重疊部分的不重復(fù)計(jì)算等因素，總計(jì)算量將遠(yuǎn)小于原始計(jì)算量的5 000×(5 000-1)×1/2=12 497 500次。同樣地，對于50 000個(gè)表格，F(xiàn)CEC聚類算法所用時(shí)間為80min，而使用DPC聚類實(shí)際所用時(shí)間預(yù)計(jì)為7 200h左右，如表4所示。

表4 不同數(shù)據(jù)量下兩算法的聚類準(zhǔn)確率與時(shí)間消耗比較

由表4可知，在不同的數(shù)據(jù)量下，兩個(gè)聚類算法的聚類平均準(zhǔn)確率接近，但在時(shí)間性能上，F(xiàn)CEC聚類有明顯的大幅度提升。可見，通過自壓縮Canopy算法，大幅度減少了樣本點(diǎn)點(diǎn)對距離計(jì)算時(shí)間，為實(shí)現(xiàn)大規(guī)模表格聚類提供了可操作的可能。

3.3 基于FCEC的表格知識抽取的效果

通過對5 000和50 000個(gè)Wiki表格執(zhí)行基于等價(jià)壓縮的Web表格聚類(算法3)，分別得到自動(dòng)確定聚類中心的決策圖和聚類效果圖，如圖4所示。圖4中可見，不同灰度的點(diǎn)代表樣本點(diǎn)形成的不同的簇，簇與簇之間有所區(qū)分，當(dāng)選擇K=20時(shí)，二者的平均聚類準(zhǔn)確率分別為82.3%和80.5%。對于每一個(gè)簇，我們隨機(jī)選擇50個(gè)樣本點(diǎn)，并統(tǒng)計(jì)被歸屬到該簇但事實(shí)上并不屬于該簇的樣本點(diǎn)(已識別的離群點(diǎn)不計(jì)算在內(nèi))。聚類準(zhǔn)確率如式(8)所示。

圖4 聚類中心決策圖和聚類效果圖(N=5 000和50 000)

由于表格聚類效果直接影響表格知識抽取算法的結(jié)果，如果不通過聚類而直接執(zhí)行算法4抽取知識三元組，平均抽取準(zhǔn)確率不超過10%。而基于FCEC聚類的表格知識抽取后，通過隨機(jī)選取100個(gè)Wiki表的知識三元組抽取結(jié)果，可得所抽取的知識三元組的準(zhǔn)確率為67.3%，在不依賴良好的表格結(jié)構(gòu)和足夠的先驗(yàn)知識的情況下，該抽取方法達(dá)到了令人滿意的結(jié)果，且從對不正確的知識三元組的分析來看，尚有可提升的空間[24]。

不正確的知識三元組主要有以下三種情形：

(1) Case 1 (35%)： 表格聚類錯(cuò)誤。聚類后的水平表格里含有少數(shù)標(biāo)題或多級表頭的表格，而不是如表1中所示的純粹的水平表格。如表5所示Predicate (“2011”) 和 (“1970”) 需要相應(yīng)地加上表格標(biāo)題 (“人口數(shù)量最大的十個(gè)大都市區(qū)的人口” 和 “亞利桑那人口的種族比例”) 才具有一定的意義，但其中的概念屬性關(guān)系獲取較為復(fù)雜，是表格知識抽取的難點(diǎn)之一。

(2) Case 2 (33%)： 主體不出現(xiàn)在表格內(nèi)，它可能是維基條目名稱或出現(xiàn)在表格上下文的小標(biāo)題中。如表5所示，Subject (“葡萄牙語”) 需要該表的上文小標(biāo)題(“印尼語起源”)結(jié)合, 而Subject (“Jennifer Lewis”) 需要該表的上文小標(biāo)題(“杜克女子足球項(xiàng)目獲得的NSCAA全美榮譽(yù)”)，這類情況主要因?yàn)橹鲗?shí)體屬于表格下文中的父類概念下的子概念或整體與部分關(guān)系。類似地，Subject (“US Billboard Adult Top 40”) 屬于該表所在的維基主題 (“拯救我 (Remy Zero歌曲)”)的子屬性。和Case1相似，這類情況涉及表格上下文的非結(jié)構(gòu)化文本數(shù)據(jù)，目前尚未有理想的解決方案。

表5 知識三元組示例

4 總結(jié)

針對大規(guī)模Web表格數(shù)據(jù)，本文主要通過改善Web表格相似性度量、降低時(shí)間復(fù)雜度、自動(dòng)判斷聚類中心三個(gè)方面，提出了一種基于等價(jià)壓縮的Web表格快速聚類算法，用以發(fā)掘表格的形式結(jié)構(gòu)類型與特點(diǎn)，然后從相似形式結(jié)構(gòu)的表格中推測表格的語義結(jié)構(gòu)，從而在模板化的結(jié)構(gòu)中抽取知識，最終形成一套基于FCEC的Web表格知識抽取方法。從實(shí)驗(yàn)效果上看，在保證聚類準(zhǔn)確率的前提下，新方法相比原始方法在時(shí)間效率上有大幅度提升，在表格聚類后利用表格模板所抽取的知識三元組的準(zhǔn)確率也達(dá)到了令人滿意的結(jié)果，但在結(jié)合NLP方法提高所抽取的知識三元組的準(zhǔn)確率上仍有較大的提升空間。

此外，對于超大規(guī)模的Web表格，所提算法仍具有局限性，因此如何將所提算法進(jìn)行分布式計(jì)算以更快的速度處理超大規(guī)模數(shù)據(jù)值得探討。