融合多種特征的實體對齊算法

喬晶晶，段利國+，李愛萍,2

(1.太原理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山西 太原 030024；2.武漢大學(xué) 軟件工程國家重點實驗室，湖北 武漢 430072)

0 引 言

知識庫在知識圖譜構(gòu)建、自動問答系統(tǒng)等領(lǐng)域具有重要作用[1]。但是人工構(gòu)建知識庫速度慢、規(guī)模小、難度大、易出錯、更新滯后，達(dá)不到實際需求的要求。如何自動構(gòu)建實用的海量知識庫具有較高的研究價值和應(yīng)用前景。

隨著Web2.0的發(fā)展，因特網(wǎng)上出現(xiàn)了大量的擁有海量數(shù)據(jù)的百科知識社區(qū)，如百度百科、維基百科、搜狗百科、互動百科等。從這些社區(qū)中自動提取實體及其相關(guān)知識用于知識圖譜、自動問答系統(tǒng)構(gòu)建，具有重要研究價值。

對大量百科詞條進(jìn)行統(tǒng)計、對比、分析發(fā)現(xiàn)，現(xiàn)有的百科知識社區(qū)具有如下特點。

(1)不同百科社區(qū)數(shù)據(jù)異構(gòu)，即語義上相同的實體在不同的百科社區(qū)，其數(shù)據(jù)表現(xiàn)形式不同；

(2)單一的百科社區(qū)實體覆蓋不全面、信息描述不完整，數(shù)據(jù)有缺失；

(3)不同百科社區(qū)分類體系不同，有的條目分類不準(zhǔn)確、不具體。甚至用戶可以自定義類別條目；

(4)存在實體歧義現(xiàn)象，即某一實體名稱對應(yīng)著多個語義不同的百科詞條頁面；

(5)數(shù)據(jù)質(zhì)量參差不齊。

上述現(xiàn)象的存在，為利用百科知識社區(qū)自動抽取數(shù)據(jù)構(gòu)建知識庫造成重重障礙，如何克服上述困難，綜合利用不同百科社區(qū)的知識資源的特征信息，自動對齊不同百科社區(qū)上的同義實體，并實現(xiàn)數(shù)據(jù)補全，具有較高的研究價值。

本文主要貢獻(xiàn)如下：

(1)利用詞語在知網(wǎng)與詞林中的語義信息，計算實體名稱及實體摘要相似度，提高實體對齊準(zhǔn)確率。

(2)提出采用權(quán)重因子反映類別標(biāo)簽在百科分類樹中的深度信息，計算實體類別相似度時，深度越大，說明分類越精確，實體相似度更高。

1 相關(guān)工作

知識庫的實體對齊始于“本體匹配”，即針對本體類別的語義相似度進(jìn)行匹配。Dutot[2]利用啟發(fā)式算法，反函數(shù)及上層語義信息實現(xiàn)多源知識庫實體對齊。張琦[3]利用Freebase共享網(wǎng)站數(shù)據(jù)，通過迭代模型和判別模型進(jìn)行實體對齊。隨著Web 3.0的發(fā)展，實體數(shù)量不斷增加，網(wǎng)絡(luò)百科社區(qū)規(guī)模不斷擴大，多源知識庫中實體對齊成為新的研究熱點[4,5]。現(xiàn)有的實體對齊方法融合實體的多種特征。王雪鵬等[6]建立了一個5層分類，356個類別，278個屬性的知識描述體系，綜合利用實體屬性、實體類別及非結(jié)構(gòu)化文本關(guān)鍵詞解決多源知識庫實體對齊問題，不足之處是只考慮知識庫中名稱相同的實體，未考慮名稱不同但實質(zhì)相同的實體對齊問題。文獻(xiàn)[7]基于互動百科、百度百科構(gòu)造中文資源描述框架(RDF)知識庫，將通過資源描述框架模式(RDFS)規(guī)范化的屬性作為特征，進(jìn)一步通過建模，獲取實體上下文信息，實現(xiàn)實體對齊。文獻(xiàn)[8]利用實體屬性值對作為特征模板，并引入屬性值的共現(xiàn)概率，使用擴展特征向量空間模型進(jìn)行實體消岐。徐慶等[9]利用實體類型、《同義詞詞林》編碼樹等特征計算實體相似度，具有借鑒意義。胡芳槐[10]對每篇文章的標(biāo)題和內(nèi)容建立倒排索引，選取相似度高于指定閾值的文章作為候選文章，將文章標(biāo)題的余弦相似度、文章內(nèi)容相似度、文章標(biāo)題的編輯距離等作為特征，使用支持向量機(SVM)判別兩個候選實體是否是同義實體。

針對使用部分特征進(jìn)行實體對齊準(zhǔn)確率不高的問題，本文綜合利用實體的名稱、摘要關(guān)鍵詞集合、類別、屬性-屬性值序列等多種特征計算實體相似度，最終實現(xiàn)實體對齊。

2 融合多種特征的實體相似度計算

2.1 百科詞條的結(jié)構(gòu)特征

網(wǎng)絡(luò)百科社區(qū)是互聯(lián)網(wǎng)中公開存在的包含大量用戶生成數(shù)據(jù)的集合，這些數(shù)據(jù)屬于半結(jié)構(gòu)化數(shù)據(jù)。中文領(lǐng)域使用率較高的網(wǎng)絡(luò)百科社區(qū)是百度百科和互動百科。百科中的每個實體均以網(wǎng)頁形式展現(xiàn)，統(tǒng)計分析發(fā)現(xiàn)，百度百科詞條包括“是否特色詞條、詞條名稱、摘要、信息框、目錄、內(nèi)容、參考資料、詞條標(biāo)簽、瀏覽次數(shù)、編輯次數(shù)、最近更新時間”等結(jié)構(gòu)標(biāo)簽，互動百科詞條包括“詞條名稱、摘要、基本信息、目錄、內(nèi)容、參考資料、開放分類、編輯次數(shù)、參與編輯人數(shù)、最近更新時間”等結(jié)構(gòu)標(biāo)簽，二者并不完全一致。為便于問題描述，本文給出如下定義。

定義1 選取百度百科和互動百科共有的詞條結(jié)構(gòu)特征,將實體數(shù)據(jù)形式化表示為E=，其中：

EN為實體名稱。網(wǎng)絡(luò)百科中知識的基本單元為詞條，除了消歧頁面，每個詞條對應(yīng)一個實體。本文選取詞條名稱作為實體名稱；

EK={w1,w2,…,wn|wi∈摘要、內(nèi)容、目錄、參考資料}-EN，為詞條自由文本的關(guān)鍵詞去除詞條名稱之后構(gòu)成的關(guān)鍵詞集合；

EC為實體類別，分別對應(yīng)百度百科中的詞條類別標(biāo)簽和互動百科中的開放分類，用于標(biāo)記實體的所屬類別。因為許多實體具有多種類別，例如，在百度百科中，詞條“魯迅”的類別標(biāo)簽有“文學(xué)家”、“文化人物”等。因此，EC進(jìn)一步表示為EC={c1,c2,…,cn}；

EP為實體屬性-屬性值序列,數(shù)據(jù)來源于百度百科中的信息框和互動百科中的基本信息框，包含一系列的“屬性-值”對，因此EP進(jìn)一步表示為EP={property,value}，其中property={p1,p2,…,pn}為屬性集合，value={v1,v2,…,vn}為屬性值集合，{pi,vi}為實體屬性與屬性值對。

對于兩個候選實體，要么是同義實體，要么不是。如果兩個實體的相似度足夠高，我們就認(rèn)為兩個實體是同義實體，也就是對齊的。由E=可知，每個詞條均可由實體名稱EN，摘要關(guān)鍵詞集合EK，類別EC，屬性-屬性值對EP這4部分來表示。4部分的信息各有特征，所含的信息量也不相同。因此，分別計算出兩個實體的名稱相似度、摘要關(guān)鍵詞相似度、類別相似度、屬性相似度，再分別賦予不同的權(quán)重，最終求得兩個實體總的相似度。下面分別介紹4個特征標(biāo)簽的相似度計算方法。

2.2 基于知網(wǎng)與詞林的實體名稱語義相似度

實體名稱雖然只是一個詞語，但是包含豐富的語義信息，本文采用如下算法計算兩個實體名稱的語義相似度。

算法1：實體名稱語義相似度算法

步驟1 借助百科詞條的同義詞或重定向功能，判斷兩個實體是否為同義詞。若為同義詞，其實體名稱語義相似度sim_en(E1,E2)記為1，否則轉(zhuǎn)步驟2。

步驟2 采用文獻(xiàn)[11]的方法計算實體E1及E2的詞條名稱語義相似度sim_en(E1,E2)。如果兩個實體的名稱既不在知網(wǎng)中也不在同義詞詞林中，記sim_en(E1,E2)為0。

2.3 實體摘要語義相似度

每個詞條的自由文本篇幅較大，若全部采用計算代價太高，而摘要包含了詞條最重要的語義信息，且篇幅短，處理速度快，計算成本小，所以本文通過計算兩個實體摘要的語義相似度來衡量兩個實體的相似度。

算法2：實體摘要語義相似度算法

步驟1 提取摘要部分關(guān)鍵詞。實體E1的關(guān)鍵詞集合EK1表示為詞序列{w11,w12,…,w1m}，實體E2的關(guān)鍵詞集合EK2表示為詞序列{w21,w22,…,w2n}。

步驟2 利用算法1計算EK1和EK2之間任意兩個關(guān)鍵詞的語義相似度sim_ek(w1i,w2j)。

步驟3 利用式(1)計算關(guān)鍵詞集合的實體語義相似度

(1)

w1i=max(sim_en(w1i,w21),sim_en(w1i,w22),…,sim_en(w1i,w2n)),w2j=max(sim_en(w2j,w11),sim_en(w2j,w12),…,sim_en(w2j,w1m))

2.4 基于Jaccard系數(shù)及類別深度的實體類別相似度

百科實體的類別標(biāo)簽集合為EC={c1,c2,…,cn}。利用式(2)來計算兩個實體E1及E2類別標(biāo)簽的相似度

(2)

式中：EC1為實體E1的類別標(biāo)簽集合，EC2為實體E2的類別標(biāo)簽集合，sim_ec(E1,E2)值越大，表示兩個實體的類別標(biāo)簽語義相似度越高。

權(quán)重因子反映類別標(biāo)簽在百科分類樹中的深度信息，深度越大，權(quán)重因子越高，說明分類越精確，實體相似度更高。考慮到百度百科缺乏明確的分類體系，此處使用的是互動百科分類樹。如果|EC1∩EC2|>1,α采用式(3)計算

(3)

式中：n=|EC1∩EC2|表示共有的類別標(biāo)簽的個數(shù)，h為分類樹的高度，di為第i個類別標(biāo)簽的深度。

2.5 基于最長公共子序列(LCS)的實體屬性相似度

通過LCS[7]方法計算實體屬性的相似度,具體算法描述如下:

算法3：實體屬性相似度算法

步驟1 利用式(4)求實體E1及E2共有屬性集

up(E1,E2)=property1∩property2

(4)

式中：property1為實體E1的屬性集，property2為實體E2的屬性集。

步驟2 利用式(5)計算兩個實體共有屬性pi的相似度

(5)

式中：pi對應(yīng)實體E1的第x個屬性p1x，其屬性值為v1x。同時，對應(yīng)實體E2的第y個屬性p2y，其屬性值為v2y,lcs(v1x,v2y)為屬性值的最長公共子序列。

步驟3 利用式(6)計算實體E1及E2屬性標(biāo)簽的相似度

sim_ep(E1,E2)=average(sim(pi))

(6)

2.6 融合多種特征的實體相似度

融合實體名稱、摘要關(guān)鍵詞集合、類別及屬性等多種特征，采用式(7)計算兩個百科實體的相似度

sim(E1,E2)=w1×sim_en(E1,E2)+w2×sim_ek(E1,E2)+w3×sim_ec(E1,E2)+w4×sim_ep(E1,E2)

(7)

sim(E1,E2)大于一定的閾值判定兩個實體可對齊，否則兩個實體不可對齊。在表1所示數(shù)據(jù)集上，使用粒子群算法選取式(7)中的權(quán)重參數(shù)及判定實體相似的閾值。

2.7 算法流程

輸入：來自百度百科和互動百科的1528個詞條頁面。

輸出：sim(E1,E2)。

(1)提取實體名稱、實體同義詞；

(2)提取實體摘要；

(3)對實體摘要進(jìn)行分詞、去停用詞得到實體摘要的關(guān)鍵詞集合；

(4)提取實體的實體類別；

(5)提取實體屬性-屬性值序列；

(6)根據(jù)2.2節(jié)基于知網(wǎng)與詞林的實體名稱語義相似度算法計算實體中兩兩之間的名稱相似度sim_en(E1,E2)；

(7)根據(jù)式(1)計算實體中兩兩之間的摘要相似度sim_ek(E1,E2)；

(8)根據(jù)式(2)、式(3)計算實體中兩兩之間的類別相似度sim_ec(E1,E2)；

(9)根據(jù)2.5節(jié)LCS算法計算實體中兩兩之間的屬性相似度sim_ep(E1,E2)；

(10)綜合(6)～(9)根據(jù)式(7)計算實體相似度sim(E1,E2)。

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)收集

本文數(shù)據(jù)選用從互動百科和百度百科隨機下載的包含圖書、人物、電影3類詞條共1528個頁面，能夠反映不同網(wǎng)絡(luò)百科的分類體系不同、數(shù)據(jù)異構(gòu)的特點。在表1所示的數(shù)據(jù)集上，使用粒子群算法選取式(7)中的權(quán)重參數(shù)及判定實體相似的閾值。選取準(zhǔn)確率(P)作為評價指標(biāo)，P=Na/Nr，其中Nr為人工判定能夠?qū)R的實體數(shù)，Na為本文算法能夠正確對齊的實體數(shù)。為了檢驗本文算法的有效性，與基于網(wǎng)絡(luò)語義標(biāo)簽的實體對齊算法、基于實體屬性與上下文主題的實體對齊等算法進(jìn)行了比較分析。

本文從互動百科及百度百科中分別隨機下載了包含人物、電影、圖書3類詞條的html頁面文檔，分析發(fā)現(xiàn)部分實體數(shù)據(jù)稀疏，特別是缺少關(guān)鍵屬性數(shù)據(jù)，因此人工方式對下載的數(shù)據(jù)進(jìn)行清洗，得到本文實驗的正式數(shù)據(jù)集，如表1所示。

表1 實體對齊數(shù)據(jù)統(tǒng)計信息

進(jìn)一步分析發(fā)現(xiàn)，表1所示數(shù)據(jù)集中，同一實體其實體名稱、摘要、屬性-屬性值序列、類別4個特征在百度百科和互動百科中各自所含的信息量也不一樣，具體區(qū)別見表2。

相同的屬性在不同的百科中可能具有不同的屬性名，比如“出生時間”與“出生日期”，計算屬性相似度前需對屬性及屬性值做標(biāo)準(zhǔn)化處理。本文通過人工比對分析的方式，對人物、圖書、電影3類實體在百度百科和互動百科中的屬性進(jìn)行匹配處理，具體數(shù)據(jù)見表3。百度百科480個人物類頁面共抽取157個不同的屬性，170個影視類頁面共抽取44個不同的屬性，180個圖書類頁面共抽取34個不同的屬性，互動百科376個人物類頁面共抽取152個不同的屬性，144個影視類頁面共抽取68個不同的屬性，178個圖書類頁面共抽取27個不同的屬性。百度百科互動百科3類頁面屬性名相同的屬性分別有94個、36個、15個，名稱不同含義相同的屬性分別有23個、14個、10個(含義相同的一組屬性為1個)。人物、圖書、電影3類實體標(biāo)準(zhǔn)化后的屬性個數(shù)分別有80個、44個、16個。

表2 不同特征數(shù)及其比例

表3 屬性標(biāo)準(zhǔn)化

相同屬性名其屬性值的表現(xiàn)形式可能不同，比如3 km和3000 m語義完全一樣，但表現(xiàn)形式卻不相同。為了增強屬性相似度的可信度，需要對屬性值的表現(xiàn)形式進(jìn)行歸一化。經(jīng)過對來自百度百科和互動百科的圖書、電影、人物3類共1528個詞條的對比分析，本文制定了21條規(guī)則實現(xiàn)實體屬性值表現(xiàn)形式的歸一化。表4是部分歸一化后的屬性值示例。

表4 屬性值歸一化示例

3.2 實驗結(jié)果分析

在表1所示的實驗用數(shù)據(jù)集中，包含百度百科詞條830個，互動百科詞條698個，實驗中為每個詞條賦予一個5個字母組成的ID,ID號是唯一的，第一個字母表示詞條來源，百度百科用字母B表示，互動百科用字母H表示。第二個字母表示詞條類別，人物類用字母P表示，電影類用字母M表示，圖書類用字母B表示。最后3位數(shù)字標(biāo)識實體編號，每種百科的每類實體重新編號。不同類別的實體對齊結(jié)果稀疏、意義不大，因此本實驗僅對齊來自不同百科相同類別的實體。為了客觀展示本文的實驗效果，與基于網(wǎng)絡(luò)語義標(biāo)簽的實體對齊算法進(jìn)行比較，本實驗也限定對齊實體名稱相同的實體。從每種百科的每類實體中隨機抽取編號等距的6對實體計算實體相似度及對齊結(jié)果，實驗結(jié)果如表5所示。人工判定能對齊的12對實體和不能對齊的6對實體中，基于實體屬性與上下文主題的實體對齊算法只考慮實體屬性及上下文主題特征，有4對與人工標(biāo)注結(jié)果不一致，基于網(wǎng)絡(luò)語義標(biāo)簽的實體對齊算法有2對與人工對齊結(jié)果不一致，本文算法對齊結(jié)果只有1對與人工對齊結(jié)果不一致。

圖1所示為實體名稱、屬性、類別、摘要4種特征及其綜合在人物類、影視類和圖書類中的準(zhǔn)確率。4種特征綜合使用的準(zhǔn)確率在3種類別中都達(dá)到了92%以上。其中影視類實體特征信息完整表述準(zhǔn)確，4類特征及其綜合準(zhǔn)確率都為最高。

圖2顯示幾種方法實驗結(jié)果的比較。第一種方法基于擴展特征向量空間模型方法只利用實體中的屬性值-對作為特征模板，雖然引入屬性值的共現(xiàn)概率進(jìn)行實體判歧，但準(zhǔn)確率較低。第二種方法基于實體屬性及上下文主題特征進(jìn)行相似度計算，準(zhǔn)確率較略有提高。第三種方法基于網(wǎng)絡(luò)語義標(biāo)簽對齊實體，其準(zhǔn)確率雖略有提高，但是只考慮實體名稱相同的實體對齊，未考慮實體名稱不同但表達(dá)實質(zhì)相同實體的對齊問題。由圖2可知，實體名稱及實體類別影響因子的使用提高了實體對齊的準(zhǔn)確率。本文算法綜合考慮各種特征，準(zhǔn)確率最高，取得較好的實驗結(jié)果。

表5 部分實驗結(jié)果

圖1 不同特征實驗結(jié)果對比

圖2 不同算法實驗結(jié)果對比

4 結(jié)束語

本文注意到利用網(wǎng)絡(luò)知識社區(qū)提取知識進(jìn)而構(gòu)建知識庫是目前比較可行的方法。但是不同網(wǎng)絡(luò)社區(qū)，其數(shù)據(jù)結(jié)構(gòu)并不一致，這為自動獲取準(zhǔn)確的知識造成了障礙。本文提出了融合詞條名稱、摘要、屬性-屬性值序列、類別等多種詞條特征的實體詞條相似度計算方法判斷實體之間是否能夠?qū)R，取得較為滿意的實驗結(jié)果。不同的社區(qū)有關(guān)實體的數(shù)據(jù)無論在質(zhì)量還是完善程度方面都參差不齊，單純依靠單一的網(wǎng)絡(luò)社區(qū)來獲取知識具有較大的局限性，如何對數(shù)據(jù)正確性和可靠性進(jìn)行甄別以自動獲取高質(zhì)量的數(shù)據(jù)是下一步研究的目標(biāo)。