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

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

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

0 引 言

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

隨著Web2.0的發展，因特網上出現了大量的擁有海量數據的百科知識社區，如百度百科、維基百科、搜狗百科、互動百科等。從這些社區中自動提取實體及其相關知識用于知識圖譜、自動問答系統構建，具有重要研究價值。

對大量百科詞條進行統計、對比、分析發現，現有的百科知識社區具有如下特點。

(1)不同百科社區數據異構，即語義上相同的實體在不同的百科社區，其數據表現形式不同；

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

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

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

(5)數據質量參差不齊。

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

本文主要貢獻如下：

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

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

1 相關工作

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

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

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

2.1 百科詞條的結構特征

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

定義1 選取百度百科和互動百科共有的詞條結構特征,將實體數據形式化表示為E=，其中：

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

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

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

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

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

2.2 基于知網與詞林的實體名稱語義相似度

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

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

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

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

2.3 實體摘要語義相似度

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

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

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

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

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

(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系數及類別深度的實體類別相似度

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

(2)

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

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

(3)

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

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對應實體E1的第x個屬性p1x，其屬性值為v1x。同時，對應實體E2的第y個屬性p2y，其屬性值為v2y,lcs(v1x,v2y)為屬性值的最長公共子序列。

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

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

(6)

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

融合實體名稱、摘要關鍵詞集合、類別及屬性等多種特征，采用式(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所示數據集上，使用粒子群算法選取式(7)中的權重參數及判定實體相似的閾值。

2.7 算法流程

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

輸出：sim(E1,E2)。

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

(2)提取實體摘要；

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

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

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

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

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

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

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

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

3 實驗與結果分析

3.1 數據收集

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

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

表1 實體對齊數據統計信息

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

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

表2 不同特征數及其比例

表3 屬性標準化

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

表4 屬性值歸一化示例

3.2 實驗結果分析

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

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

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

表5 部分實驗結果

圖1 不同特征實驗結果對比

圖2 不同算法實驗結果對比

4 結束語

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