知識庫實體對齊技術(shù)綜述

莊　嚴(yán)　李國良　馮建華

(清華大學(xué)計算機(jī)科學(xué)與技術(shù)系　北京　100084)

(joyear2008@163.com)

?

知識庫實體對齊技術(shù)綜述

莊嚴(yán)李國良馮建華

(清華大學(xué)計算機(jī)科學(xué)與技術(shù)系北京100084)

(joyear2008@163.com)

A Survey on Entity Alignment of Knowledge Base

Zhuang Yan, Li Guoliang, and Feng Jianhua

(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)

AbstractEntity alignment on knowledge base has been a hot research topic in recent years. The goal is to link multiple knowledge bases effectively and create a large-scale and unified knowledge base from the top-level to enrich the knowledge base, which can be used to help machines to understand the data and build more intelligent applications. However, there are still many research challenges on data quality and scalability, especially in the background of big data. In this paper, we present a survey on the techniques and algorithms of entity alignment on knowledge base in decade, and expect to provide alternative options for further research by classifying and summarizing the existing methods. Firstly, the entity alignment problem is formally defined. Secondly, the overall architecture is summarized and the research progress is reviewed in detail from algorithms, feature matching and indexing aspects. The entity alignment algorithms are the key points to solve this problem, and can be divided into pair-wise methods and collective methods. The most commonly used collective entity alignment algorithms are discussed in detail from local and global aspects. Some important experimental and real world data sets are introduced as well. Finally, open research issues are discussed and possible future research directions are prospected.

Key wordsknowledge base; entity alignment; similarity propagation; probabilistic model; similarity function; blocking and indexing

摘要知識庫的實體對齊(entity alignment)工作是近年來的研究熱點問題.知識庫實體對齊的目標(biāo)是能夠高質(zhì)量鏈接多個現(xiàn)有知識庫，并從頂層創(chuàng)建一個大規(guī)模的統(tǒng)一的知識庫，從而幫助機(jī)器理解底層數(shù)據(jù).然而，知識庫實體對齊在數(shù)據(jù)質(zhì)量、匹配效率等多個方面存在很多問題與挑戰(zhàn)有待解決.從這些挑戰(zhàn)出發(fā)，對十幾年來的可用于知識庫實體對齊的技術(shù)和算法進(jìn)行綜述，通過分類和總結(jié)現(xiàn)有技術(shù)，為進(jìn)一步的研究工作提供可選方案.首先形式化定義了知識庫實體對齊問題；然后對知識庫的實體對齊工作進(jìn)行總體概述，并從對齊算法、特征匹配技術(shù)和分區(qū)索引技術(shù)3個方面詳細(xì)總結(jié)了各種可用方法和研究進(jìn)展，重點從局部和全局2個角度對主流的集體對齊算法進(jìn)行詳細(xì)闡述，并介紹了常用的評測數(shù)據(jù)集；最后對未來重點的研究內(nèi)容和發(fā)展方向進(jìn)行了探討和展望.

關(guān)鍵詞知識庫；實體對齊；相似性傳播；概率模型；相似性函數(shù)；分區(qū)索引

自20世紀(jì)90年代蒂姆·伯納斯·李發(fā)明萬維網(wǎng)(World Wide Web， WWW，簡寫為Web)以來，隨著Web技術(shù)的不斷向前發(fā)展，人們經(jīng)歷了以文檔互聯(lián)為主要特征的“Web 1.0”時代和基于社交網(wǎng)絡(luò)的以人與人互聯(lián)為主要特征的“Web 2.0”時代，正在邁向基于知識互聯(lián)的“Web 3.0”時代[1].知識互聯(lián)的目標(biāo)是實現(xiàn)人和機(jī)器都可理解的萬維網(wǎng)，使得我們的網(wǎng)絡(luò)更加智能化.在這種背景下，近十幾年來互聯(lián)網(wǎng)上產(chǎn)生了越來越多的大規(guī)模知識庫，這些知識庫包含娛樂、金融、政務(wù)、出版發(fā)行和生物醫(yī)學(xué)等互聯(lián)網(wǎng)上各個方面的知識，為人們更加智能地使用Web提供了更好的方案.

然而，由于任何機(jī)構(gòu)或組織都可以根據(jù)自己的需求和設(shè)計理念創(chuàng)建知識庫，因此知識庫中的數(shù)據(jù)也充滿多樣性和異構(gòu)性，并且存在很多相互的重復(fù)或補(bǔ)充.知識庫的對齊問題也吸引了越來越多的研究者的目光，尤其是在信息檢索、機(jī)器閱讀和知識問答等領(lǐng)域都具有重要的應(yīng)用價值.舉例來講，當(dāng)人們對某支股票感興趣的時候，系統(tǒng)可以根據(jù)需求將這只股票相關(guān)的政務(wù)、經(jīng)濟(jì)信息知識庫和公司信息知識庫以及股票行情變化規(guī)律知識庫對齊起來以自動獲得更加全面和準(zhǔn)確的總體情況，將綜合結(jié)果呈現(xiàn)給用戶，從而輔助用戶做出正確的交易決策.但是，由于數(shù)據(jù)質(zhì)量、對齊效率等多方面因素使得這些知識庫的對齊工作存在大量的困難和挑戰(zhàn).

知識庫一般使用RDFS(resource description framework schema)或者OWL(Web ontology language)等語言描述的本體構(gòu)建，這里的本體是一種采取不同的結(jié)構(gòu)化形式表示的形式化的世界知識，其中定義了類別(class)、屬性(property)和實例(instance)等基本元素，這些元素都可以看作是知識庫中的實體(entity).知識庫的對齊的研究工作開始于“本體匹配”(ontology matching)[2-4]，初期主要是針對本體類別的語義相似性進(jìn)行匹配.近幾年來，隨著知識庫規(guī)模的擴(kuò)大和實例數(shù)量的增加，不同知識庫之間的實例鏈接的重要性日益體現(xiàn)，知識庫中的實體對齊更加偏重于實例方面的匹配工作，這也是本文知識庫對齊的主要研究內(nèi)容.

實體對齊(entity alignment)也稱為實體匹配(entity matching)或?qū)嶓w解析(entity resolution)，是判斷相同或不同數(shù)據(jù)集中的2個實體是否指向真實世界同一對象的過程.數(shù)據(jù)庫領(lǐng)域中，對象共指的消解常被稱為記錄鏈接(record linkage)、重復(fù)檢測(duplicate detection)或記錄匹配(record matching)[5-7]；在自然語言處理和信息檢索領(lǐng)域，常稱之為共指消解(coreference resolution)[8-9]，屬于指代消解(anaphora resolution)中的一類工作；在語義Web領(lǐng)域，也稱之為引用調(diào)和(reference reconciliation)或?qū)ο蠛喜?object consolidation).這些工作在數(shù)據(jù)清洗、數(shù)據(jù)集成和數(shù)據(jù)挖掘等方面中起著重要的作用[10].

實體對齊相關(guān)問題從數(shù)據(jù)庫誕生之日起就被人們所重視，從20世紀(jì)六七十年代提出到現(xiàn)在,實體匹配技術(shù)也經(jīng)歷了一系列的發(fā)展變化.知識庫實體對齊是實體匹配發(fā)展到Web 3.0后，在不同知識庫的鏈接過程中提出的一種問題，這個問題可以通過將經(jīng)典的實體匹配技術(shù)應(yīng)用到知識庫領(lǐng)域，結(jié)合知識庫的特點進(jìn)行實體匹配來解決.不同知識庫的鏈接是實現(xiàn)Web 3.0提出的“知識之網(wǎng)”愿景的關(guān)鍵步驟，具有豐富的應(yīng)用場景和重要的意義，特別是萬維網(wǎng)聯(lián)盟的鏈接開放數(shù)據(jù)項目(linking open data project， LOD)[11]的興起和發(fā)展，為這方面的研究工作注入了更大的活力與動力，因此知識庫的實體對齊技術(shù)具有重要的研究價值，是當(dāng)前的熱點研究方向.

本文對當(dāng)前知識庫實體對齊技術(shù)進(jìn)行綜述，對知識庫實體對齊的相關(guān)算法和技術(shù)進(jìn)行系統(tǒng)化地總結(jié)，以期應(yīng)對這一領(lǐng)域所面臨的挑戰(zhàn)以及為進(jìn)一步研究工作提供幫助.

1問題描述

1.1知識庫實體對齊的相關(guān)概念

本文首先對論述的知識庫進(jìn)行定義.知識庫可以看作是對客觀世界的事物及其相互關(guān)系的一種形式化描述.當(dāng)前知識庫的定義有很多種，本文選擇六元組的方式進(jìn)行定義[12].這里采用RDF(resource description framework)規(guī)范定義一條事實三元組，即一條事實三元組分別由主語、謂語和賓語組成，可以簡寫為SPO(subject-predicate-object)，則知識庫的定義可以描述為

定義1[12]. 知識庫.一個知識庫是一個由以下方式構(gòu)成的六元組：KB=(I,L,R,P,FR,FP).其中I,L,R,P分別為1組實例、字面量、關(guān)系和屬性的集合；FR?I×R×I是一個SPO三元組表示賓語為實例的關(guān)系事實；FP?I×P×L是一個SPO三元組表示賓語為字面量的屬性事實.

明確知識庫的定義后對知識庫的實體對齊進(jìn)行形式化定義.知識庫的實體可以包括知識庫的任何一個元素，特別地，本文將知識庫的實體對齊定義為知識庫中的實例匹配，其形式化定義為[13]

Alignentity(KB1,KB2)={(e1,e2,con)|

e1∈KB1,e2∈KB2,con∈[0,1]}，

其中，con為一個刻畫實體相似性大小的數(shù)值，con越大則2個實體越相似.

2個知識庫實體對齊的過程如圖1所示，可以簡單描述為：給定2個知識庫和1組先驗對齊的數(shù)據(jù)(也可稱為對齊算法的訓(xùn)練數(shù)據(jù)，詳細(xì)內(nèi)容參見1.3節(jié))，在可選的調(diào)節(jié)參數(shù)和一系列相關(guān)的外部資源(或稱為背景數(shù)據(jù)，本文不涉及這方面的研究工作)共同控制下進(jìn)行實體匹配的計算最終得到對齊結(jié)果.其中實體對齊的詳細(xì)過程和相關(guān)算法是本文的主要研究內(nèi)容.

Fig. 1　Process of entity alignment of knowledge base.圖1　知識庫實體對齊過程

1.2對齊質(zhì)量和效率的評價相關(guān)概念

實體對齊效果的評價可分為質(zhì)量和效率2個方面.

1) 質(zhì)量評價主要是指對齊的準(zhǔn)確性和全面性的評價指標(biāo).我們知道，考慮一個二分類問題，可以將實例分成正類(positive)或負(fù)類(negative)，因此會出現(xiàn)4種情況：如果一個實例是正類并且也被預(yù)測成正類，即為真正類(true positive，TP);如果實例是負(fù)類被預(yù)測成正類，稱之為假正類(false positive,FP)；相應(yīng)地，如果實例是負(fù)類被預(yù)測成負(fù)類，稱之為真負(fù)類(true negative，TN);正類被預(yù)測成負(fù)類則為假負(fù)類(false negative，F(xiàn)N).常用的對齊質(zhì)量評價指標(biāo)有精度(precision)、召回率(recall)、F-measure以及使用圖形表示的precision-recall曲線等.下面對這4個度量指標(biāo)進(jìn)行簡要介紹[14-16].

① 精度.精度也稱為查準(zhǔn)率，用來衡量分類結(jié)果的質(zhì)量，定義為被分類器判斷為正類的實例中正確分類的比例，即：

② 召回率.召回率也稱為查全率，用來衡量分類器發(fā)現(xiàn)正確匹配的能力，定義為分類器將正類判斷為正類的比例，即：

③F-measure.F-measure也稱為f-score或f1-score，是綜合考慮精度和召回率的一個評價指標(biāo)，定義為精度和召回率的調(diào)和均值，即：

④precision-recall曲線.在指定參數(shù)條件下，在二維坐標(biāo)系中將召回率作為x軸、精度作為y軸繪制的曲線.實驗證明，在精度和召回率之間存在著相反的相互依賴關(guān)系：如果提高輸出的精度，就會降低其召回率，反之亦然.因此圖2中曲線右上角部分的值越高則分類器效果越好.

Fig. 2　Precision-recall curve.圖2　精度-召回率曲線

2) 效率評價主要是指對齊算法中一些分區(qū)索引技術(shù)對候選匹配對的篩選能力和準(zhǔn)確性的度量評價標(biāo)準(zhǔn).我們定義待匹配數(shù)據(jù)集中匹配實體對的數(shù)量為nM，不匹配的實體對數(shù)量為nN.類似地，經(jīng)過某種分區(qū)索引技術(shù)得到的候選對中正確匹配的數(shù)量為sM，不匹配的數(shù)量為sN.常用的對齊效率評價指標(biāo)有縮減率(reduction ratio，RR)、候選對完整性(pairs completeness，PC)、候選對質(zhì)量(pairs quality，PQ)等.下面對這3個度量指標(biāo)進(jìn)行簡要介紹[14].

① 縮減率.縮減率是用來衡量索引技術(shù)減少待匹配實體對數(shù)量能力的參數(shù)，定義為在不考慮候選對質(zhì)量的條件下，使用索引減少的實體對與全部待匹配實體對的比值，即：

② 候選對完整性.對應(yīng)與本節(jié)的召回率，是用來衡量索引產(chǎn)生的候選對的質(zhì)量的度量指標(biāo)之一，定義為索引產(chǎn)生的候選對中匹配對的數(shù)量與全部待匹配數(shù)據(jù)集中匹配實體對的數(shù)量的比值，即：

可以看出，這個指標(biāo)的值越低，則會有越多的匹配對被索引排除，會導(dǎo)致總體匹配的召回率降低.

③ 候選對質(zhì)量.對應(yīng)與本節(jié)的精度，是用來衡量索引產(chǎn)生的候選對的質(zhì)量的度量指標(biāo)之一，定義為索引產(chǎn)生的正確匹配的候選對數(shù)量與全部產(chǎn)生的候選對數(shù)量的比值，即：

可以看出，這個指標(biāo)的值越高，則該索引發(fā)現(xiàn)匹配實體對的能力越強(qiáng)，并會使總體匹配的精度有所提高.

1.3問題與挑戰(zhàn)

知識庫實體對齊，尤其是在大數(shù)據(jù)條件下，存在許多問題和挑戰(zhàn)，其中最突出是計算復(fù)雜度、數(shù)據(jù)質(zhì)量和先驗對齊數(shù)據(jù)的獲取問題，都需要根據(jù)知識庫實際情況設(shè)計有效算法進(jìn)行解決.

1) 計算復(fù)雜度挑戰(zhàn).一般進(jìn)行2個知識庫實體匹配的時候，為了發(fā)現(xiàn)所有的匹配對，需要將一個知識庫中所有實體與另一個知識庫中所有實體進(jìn)行比較，這將導(dǎo)致匹配算法的計算復(fù)雜度隨著知識庫的規(guī)模二次增長，在大數(shù)據(jù)條件下，其計算規(guī)模是難以接受的，而實際上可能的匹配對的數(shù)量不會超過規(guī)模較小的知識庫實體數(shù)量.為了解決這個矛盾，需要設(shè)計高效的算法在保證精度和召回率的前提下盡可能減少候選對的數(shù)量，使復(fù)雜的匹配計算只在最有可能的候選對中進(jìn)行.

2) 數(shù)據(jù)質(zhì)量挑戰(zhàn).知識庫對齊中的數(shù)據(jù)質(zhì)量問題主要是由于不同的知識庫的構(gòu)建目的和構(gòu)建方式不同，具體有以下5方面的表現(xiàn)：①相同實體有不同名字；②相同名字指代不同實體；③實體定義粒度不同；④相同的屬性在不同知識庫中具有不同的判別能力；⑤相同類別的實體在不同知識庫中具有不同數(shù)量的屬性.此外，由于格式、單位、大小寫、空格、縮寫名詞、錄入錯誤等也會給匹配過程帶來很多困難.通常，這類問題可以通過數(shù)據(jù)預(yù)處理技術(shù)進(jìn)行解決，但知識庫對齊中的數(shù)據(jù)質(zhì)量問題還需要綜合考慮知識庫架構(gòu)方面的因素設(shè)計相應(yīng)的算法來解決.

3) 先驗對齊數(shù)據(jù)的獲取挑戰(zhàn).先驗對齊數(shù)據(jù)也稱為訓(xùn)練數(shù)據(jù)，在知識庫實體對齊過程中具有重要作用，無論是對匹配的準(zhǔn)確度還是算法的收斂速度都會產(chǎn)生重要影響.然而，在知識庫中尤其是大規(guī)模的通用知識庫中這種先驗數(shù)據(jù)并不容易獲得.為了解決這個問題，需要針對知識庫的不同情況采用不同的方法：對于具有URI的實體，可以直接通過URI來判斷是否相等；對于實體名稱完全一樣的實體，可以確定它們相等的概率很大；對于具有OWL:sameAs屬性的實體，可以通過屬性值來判斷是否相等；對于具有OWL:Inverse Functional Property(IFP)屬性的實體，可以通過其一條事實的IFP屬性的賓語相等推導(dǎo)出其主語相等；如果以上條件都不滿足，還可以通過對每個知識庫的實體進(jìn)行IFP屬性的推導(dǎo)來啟發(fā)式地獲得近似的IFP，進(jìn)而獲得先驗對齊數(shù)據(jù)[17].通過這些手段可以部分地解決缺少訓(xùn)練數(shù)據(jù)的問題.此外主動學(xué)習(xí)及眾包算法等都可以作為獲得訓(xùn)練數(shù)據(jù)的有效手段，因此仍需將這些方法整合起來以便找出更多的高質(zhì)量的先驗對齊數(shù)據(jù).

2知識庫實體對齊技術(shù)概述

高效的實體對齊算法的設(shè)計與實現(xiàn)是解決知識庫實體對齊問題的關(guān)鍵手段，也是知識庫實體對齊過程的主要內(nèi)容.對齊算法設(shè)計的主要思路是利用多種實體匹配技術(shù)結(jié)合知識庫的特點和處理方法對知識庫中指向相同對象的實例進(jìn)行辨析以獲得對齊結(jié)果.實體對齊算法可以分為只考慮實例及其屬性相似程度的成對實體對齊和在成對對齊基礎(chǔ)上考慮不同實例之間相互關(guān)系用以計算相似度的集體實體對齊2類，2類算法的配合使用是解決知識庫實體對齊問題的主要內(nèi)容.而對實體屬性及相互關(guān)系相似程度的衡量需要用到多種類型的相似函數(shù)，稱為基于相似性函數(shù)的特征匹配.相似性函數(shù)同樣可以分為2類：1)可以用于實體匹配中屬性的相似性比較，即常用的文本相似性函數(shù)；2)用于實體匹配中的實體關(guān)系比較，稱為結(jié)構(gòu)相似性函數(shù).

高效的實體對齊算法需要有效解決1.3節(jié)提出的三大挑戰(zhàn)，尤其是大規(guī)模知識庫的匹配效率問題被認(rèn)為是當(dāng)前實體對齊的最大挑戰(zhàn)之一，除了選擇合適而高效的相似性函數(shù)之外，分區(qū)索引技術(shù)被廣泛地應(yīng)用于實體對齊過程中.可以說，分區(qū)索引技術(shù)是當(dāng)今大規(guī)模知識庫匹配的關(guān)鍵技術(shù)，通過高效的索引設(shè)計可以避免隨數(shù)據(jù)庫規(guī)模二次增長的計算復(fù)雜度，是解決知識庫對齊效率問題的有效手段.

知識庫對齊的詳細(xì)流程如圖3所示.待對齊的知識庫經(jīng)過數(shù)據(jù)預(yù)處理階段進(jìn)入實體對齊算法模塊，算法首先對待對齊數(shù)據(jù)進(jìn)行分區(qū)索引，降低計算復(fù)雜度，然后利用文本相似性函數(shù)進(jìn)行成對匹配，再通過結(jié)構(gòu)相似性函數(shù)或其他一些利用關(guān)系相似性的算法進(jìn)行集體匹配，最后將2方面結(jié)果結(jié)合起來形成最終對齊結(jié)果.第3～5節(jié)將對實體對齊算法以及可用于對齊算法的基于相似性函數(shù)的特征匹配技術(shù)和分區(qū)索引技術(shù)的內(nèi)容進(jìn)行詳細(xì)闡述.

Fig. 3　Process of knowledge base alignment in detail.圖3　知識庫對齊詳細(xì)流程

表1對本文中使用的符號進(jìn)行了匯總，以方便查閱.

Table 1　Summary of Notations

2.1數(shù)據(jù)預(yù)處理

數(shù)據(jù)的預(yù)處理也稱作數(shù)據(jù)的標(biāo)準(zhǔn)化，是實體匹配任務(wù)的重要步驟.實體匹配中數(shù)據(jù)的質(zhì)量問題包括數(shù)據(jù)的準(zhǔn)確性、完整性、一致性、有效性、適時性和可獲取性等方面問題，主要來源于數(shù)據(jù)的多源異構(gòu)性、數(shù)據(jù)定義的不一致性、數(shù)據(jù)表達(dá)的多樣性、數(shù)據(jù)的易變性等多個方面.數(shù)據(jù)的預(yù)處理需要綜合考慮這些方面，設(shè)計出完善的解決方案，為數(shù)據(jù)的進(jìn)一步處理打下良好的基礎(chǔ).在知識庫實體對齊過程中數(shù)據(jù)的預(yù)處理同樣重要，但由于知識庫是預(yù)先按照一定規(guī)則建立好的數(shù)據(jù)庫，數(shù)據(jù)的質(zhì)量有一定的保證，很多實體對齊算法在對數(shù)據(jù)做簡單的格式的整理或者停用詞的處理后直接進(jìn)行對齊，數(shù)據(jù)質(zhì)量問題和容錯處理可以在實體對齊算法過程中進(jìn)行.因此，在很多情況下知識庫實體對齊算法之前的數(shù)據(jù)預(yù)處理步驟的重要性并沒有像在數(shù)據(jù)挖掘等數(shù)據(jù)處理任務(wù)中那樣突出.隨著數(shù)據(jù)清洗與整合技術(shù)的發(fā)展，數(shù)據(jù)的預(yù)處理方面產(chǎn)生了大量的研究成果可以借鑒到實體對齊的研究中，具體內(nèi)容可以參見文獻(xiàn)[18-19]，Christen在專著文獻(xiàn)[20]中也專門針對實體匹配的數(shù)據(jù)預(yù)處理問題作了介紹，本文不再贅述.

2.2實體對齊算法

本文將在第3節(jié)對知識庫實體對齊算法作詳細(xì)介紹.知識庫實體對齊算法可分為成對實體對齊和集體實體對齊2類.所謂成對實體對齊，即將實體對齊問題看作是根據(jù)屬性相似性評分判斷待匹配實體對匹配與否的分類問題.Newcombe[21]與Fellegi和Sunter[22]給出了這種實體對齊分類方法的概率模型，用于實體對齊的大部分機(jī)器學(xué)習(xí)算法也屬于成對實體對齊，這部分內(nèi)容將在3.1節(jié)進(jìn)行詳細(xì)闡述.集體實體對齊又可以分為局部集體實體對齊和全局集體實體對齊.局部集體實體對齊也可稱為基于簡單關(guān)系的集體實體對齊，在計算實體相似性的時候?qū)嶓w的關(guān)聯(lián)實體屬性納入計算，即考慮待匹配實體對的鄰居的屬性集合，但并不將鄰居節(jié)點當(dāng)作平等的實體去計算結(jié)構(gòu)相似度，這部分內(nèi)容在3.2節(jié)進(jìn)行概述.全局集體實體對齊基于實體對齊是相互影響的觀察，通過不同匹配決策之間的相互影響調(diào)整實體之間的相似度，可以分為相似性傳播和基于概率模型的集體實體對齊方法.這類方法是當(dāng)前知識庫實體對齊的主流算法，也是本文的重點內(nèi)容，將在3.3節(jié)作具體闡述.

2.3基于相似性函數(shù)的特征匹配

本文將在第4節(jié)對知識庫實體對齊中的基于相似性函數(shù)的特征匹配作詳細(xì)介紹.很多實體對齊算法需要用到相似性度量函數(shù).一般在實際知識庫實體對齊過程中2個實體e1和e2的相似性函數(shù)定義為

sim(e1,e2)=(1-α)simAttr(e1,e2)+αsimNB(e1,e2)，

其中,simAttr(e1,e2)為對應(yīng)于實體對的屬性相似性函數(shù)，simNB(e1,e2)為應(yīng)于實體對的結(jié)構(gòu)相似性函數(shù)，0≤α≤1為二者的調(diào)節(jié)參數(shù).

本文將在4.1節(jié)對常用的文本相似性函數(shù)進(jìn)行介紹.首先介紹基于token的相似性函數(shù)，這種方法將待匹配的實體對看作是一系列token的集合；其次介紹基于編輯距離的相似性函數(shù)，這種方法將待匹配的實體對作為文本字符串整體處理；最后介紹結(jié)合兩者優(yōu)點的混合型相似性函數(shù).

結(jié)構(gòu)相似性中的關(guān)系匹配主要是針對實體對的鄰居節(jié)點的相似性，計算的基本思想是2個實體具有的相似節(jié)點越多，則它們越可能相似.本文4.2節(jié)將對常用的結(jié)構(gòu)相似性函數(shù)進(jìn)行介紹.

2.4分區(qū)索引技術(shù)

本文將在第5節(jié)對知識庫實體對齊中的分區(qū)索引技術(shù)作詳細(xì)介紹.我們知道，索引是對數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，使用索引可快速訪問數(shù)據(jù)庫表中的特定信息.在知識庫對齊中建立索引是通過剪枝過濾掉知識庫中不可能相似的實體對，使得相似的實體對盡量分配到一個或幾個區(qū)塊中成為候選對，最終的對齊處理只在這些候選對中進(jìn)行，從而達(dá)到提高匹配效率的目的.

這其中的一個關(guān)鍵問題就是索引鍵值的選擇問題.這里所謂索引鍵值就是知識庫中實體集合的一個或幾個屬性的函數(shù)，通過這些函數(shù)值來劃分待匹配實體集合，使得這些區(qū)塊可以包含所有的匹配實體對，并且產(chǎn)生的候選對越少越好.索引鍵值的選擇需要考慮3方面因素[20]：

1) 屬性值的質(zhì)量.因為任何作為索引鍵的屬性值的缺失或錯誤都可能導(dǎo)致實體的錯誤分類，從而影響對齊的結(jié)果，因此作為索引鍵值的屬性值要盡可能完整且正確.

2) 屬性值的分布.在實體數(shù)量一定的條件下，偏斜的屬性值的分布會導(dǎo)致部分分區(qū)中匹配對遠(yuǎn)大于其他分區(qū)，從而使匹配總數(shù)增加，而均勻分布的屬性值產(chǎn)生的匹配對最少.因此屬性值的分布要盡可能地均勻.

3) 區(qū)塊數(shù)量和大小的權(quán)衡.通過索引產(chǎn)生相對少量較大的分區(qū)可以減少潛在匹配實體對的丟失概率，但會產(chǎn)生較多的候選對；而大量較小的分區(qū)雖然能減少候選對的數(shù)量，但卻可能丟失更多的潛在匹配實體對.因此需要設(shè)計一種在盡量不丟失可能匹配的情況下使分區(qū)盡可能小的索引方案.

本文將可用于知識庫中的分區(qū)索引技術(shù)分為5類：1)基本的分區(qū)索引，即按照所選擇屬性的索引鍵值直接構(gòu)建分區(qū)；2)基于滑動窗口的分區(qū)索引，即所謂近鄰排序索引；3)基于相似性的分區(qū)索引，包括基于q-gram、基于后綴數(shù)組和基于Hash的索引；4)基于聚類的索引，包括Canopy聚類索引和基于StringMap的索引；5)動態(tài)索引，它所介紹的分區(qū)索引技術(shù)中唯一可以同時作用于屬性和關(guān)系的索引技術(shù)，具體內(nèi)容將在第5節(jié)中介紹.

3實體對齊算法

3.1成對實體對齊方法

3.1.1傳統(tǒng)概率模型的實體對齊方法

傳統(tǒng)概率模型對齊方法是一種基于屬性相似性的成對比較的方法，這種方法不考慮匹配實體間的關(guān)系，Newcombe[21]與Fellegi和Sunter[22]通過將基于屬性相似性評分的實體匹配問題轉(zhuǎn)化為分類問題(分為匹配、可能匹配和不匹配)建立了這個問題的概率模型.這種模型是實體對齊問題的重要方法，迄今為止有大量的實體對齊方面的工作建立在這種方法之上.

其中，e1,e2為待匹配的實體對;t1,t2為相似度閾值的下界和上界.這種簡單方法的最主要問題在于沒有體現(xiàn)不同屬性對于最終相似度的影響.一個重要的解決方案是為每個匹配的屬性對分配不同的權(quán)重，以體現(xiàn)其對對齊結(jié)果的重要性.Herzog在Fellegi-Sunter模型的基礎(chǔ)上通過建立基于概率的實體鏈接模型形式化地描述了這一思想[23]：定義2個待匹配的數(shù)據(jù)庫(同樣適用于知識庫)A和B，ei和ej分別為A和B中的實體，ei∈A，ej∈B；定義2個不相交的集合M和U：

定義比較向量x*為待匹配實體所有匹配的屬性形成的向量，比較空間X為所有可能的x*形成的空間；定義2個條件概率的比值R：R=P(x*∈X|M)P(x*∈X|U)，則Fellegi與Sunter的匹配決策規(guī)則可表述為

在假設(shè)比較向量x*中的屬性彼此獨立的條件下(實際中實體屬性很可能相關(guān)，但Herzog的實驗[23]表明這個假設(shè)仍然可以取得很好的匹配效果)，屬性的權(quán)重為

其中，ai和bi為待匹配實體對的第i個屬性，mi為假設(shè)2個實體相同其第i個屬性值相等的概率，ui為假設(shè)2個實體不相同其第i個屬性值相等的概率.基于這2個概率值，可以計算第i個屬性的權(quán)重wi為

設(shè)比較向量x*=(x1,x2,…,xn)，比較空間X=X1×X2×…×Xn，在條件獨立性的假設(shè)下，

可以看到，實體對匹配程度的大小等于各屬性權(quán)重之和.因此，通過全部匹配屬性的權(quán)重之和可以對實體匹配程度進(jìn)行判斷.

有很多工作建立在Fellegi與Sunter的研究基礎(chǔ)之上.Porter和Winkler在文獻(xiàn)[24-25]中使用屬性值的近似比較代替相等與否的二值比較，取得了較好的匹配質(zhì)量；Winkler等人在文獻(xiàn)[26]中將待匹配屬性值出現(xiàn)的頻率代入到mi和ui的計算當(dāng)中，他們認(rèn)為出現(xiàn)頻度較高的屬性對實體對的匹配貢獻(xiàn)越低，需要降低其權(quán)重；Winkler還結(jié)合貝葉斯網(wǎng)絡(luò)對屬性的相關(guān)性建模，并使用最大估計算法對參數(shù)進(jìn)行估計[27].在傳統(tǒng)概率模型對齊方法中會產(chǎn)生2類錯誤：1)相同實體被分類為不相等;2)不同實體被分類為相等.通常假定產(chǎn)生這2類錯誤的代價相等，但實際上經(jīng)常會有不相等的情況，文獻(xiàn)[28]正是基于這種觀察，提出一種基于代價優(yōu)化的決策模型，在傳統(tǒng)模型的基礎(chǔ)上將不同的代價賦予不同的匹配狀態(tài)，通過一個總體代價公式和貝葉斯公式產(chǎn)生一個代價最優(yōu)化決策規(guī)則.

3.1.2基于機(jī)器學(xué)習(xí)的實體對齊方法

基于Fellegi-Sunter模型的概率實體對齊方法取得了大量的研究成果，隨著機(jī)器學(xué)習(xí)及統(tǒng)計學(xué)習(xí)的發(fā)展，很多機(jī)器學(xué)習(xí)方法也應(yīng)用到實體對齊領(lǐng)域，并取得了巨大的進(jìn)展.機(jī)器學(xué)習(xí)方法將實體對齊問題看作是二元分類問題，根據(jù)是否使用標(biāo)注數(shù)據(jù)可以分為有監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)2類，而主動學(xué)習(xí)屬于有監(jiān)督學(xué)習(xí)，通過不斷交互獲得更加準(zhǔn)確的訓(xùn)練數(shù)據(jù).下面對這3類基于機(jī)器學(xué)習(xí)的實體對齊方法進(jìn)行介紹，由于很多基于概率模型的方法也使用了大量機(jī)器學(xué)習(xí)的技術(shù)，其相關(guān)內(nèi)容在這里只作概述，詳細(xì)內(nèi)容參見3.3.2節(jié)的具體算法.

3.1.2.1監(jiān)督和半監(jiān)督機(jī)器學(xué)習(xí)

監(jiān)督機(jī)器學(xué)習(xí)分類算法需要預(yù)先標(biāo)注部分實體匹配與否作為訓(xùn)練數(shù)據(jù)，使用訓(xùn)練數(shù)據(jù)的比較向量作為特征向量代入進(jìn)行計算去訓(xùn)練分類模型，然后使用訓(xùn)練好的模型對未標(biāo)注的數(shù)據(jù)進(jìn)行分類.一個典型的監(jiān)督機(jī)器學(xué)習(xí)的分類方法有3個步驟[29]：1)選擇合適的分類技術(shù)和分類模型，使用訓(xùn)練數(shù)據(jù)對模型進(jìn)行訓(xùn)練，并通過自動或手工的方式調(diào)節(jié)其中的參數(shù)；2)使用同樣格式的測試數(shù)據(jù)對訓(xùn)練出來的模型進(jìn)行評估，如果評估結(jié)果達(dá)不到要求則需要調(diào)節(jié)參數(shù)或者修改模型，同時要注意測試數(shù)據(jù)的過擬合問題；3)將測試好的模型應(yīng)用于實際數(shù)據(jù)進(jìn)行分類.

基于監(jiān)督學(xué)習(xí)的實體對齊方法可以分為2類:

1) 只通過屬性比較向量判斷一個實體對的匹配與否，屬于成對實體對齊.這類方法的主流技術(shù)有決策樹[29]、支持向量機(jī)(SVM)[30]和集成學(xué)習(xí)[31]等.決策樹方法是通過訓(xùn)練數(shù)據(jù)迭代生成一個規(guī)則樹，其內(nèi)部節(jié)點為判斷規(guī)則，葉子節(jié)點為規(guī)則的可能分類結(jié)果，通過這個生成的決策樹就可以判斷實體對是否相似.Cochinwala等人在文獻(xiàn)[32]中使用著名的分類回歸樹(CART)算法、線性分析判別算法和矢量量化方法進(jìn)行實體辨析；Elfeky等人在TAILOR工具包中實現(xiàn)了一種ID3決策樹算法[33]，并通過實驗證明其算法的匹配效果要高于傳統(tǒng)的概率模型方法.支持向量機(jī)方法是通過訓(xùn)練數(shù)據(jù)集在高維空間中產(chǎn)生一個分類超平面使得匹配和不匹配2類數(shù)據(jù)集的間距盡可能大，并以此分類真實數(shù)據(jù).Bilenko等人使用SVM方法獲得文本的基于向量空間模型的相似度估計，并在MARLIN系統(tǒng)中予以實現(xiàn)，實驗表明相對于決策樹模型SVM可以取得更好的分類效果.Christen在2階段實體鏈接分類模型中使用一種迭代的SVM分類算法[34]，實驗表明其匹配效果遠(yuǎn)高于TAILOR中的混合算法.實體對齊中的集成學(xué)習(xí)是指為了提高對齊質(zhì)量將多種基本的實體對齊系統(tǒng)結(jié)合起來形成一個單獨的解決方法.Chen等人在文獻(xiàn)[35]中提出了一種新的集成學(xué)習(xí)框架，使用2種監(jiān)督學(xué)習(xí)將多種基礎(chǔ)實體對齊系統(tǒng)和上下文特征結(jié)合起來，形成統(tǒng)一的聚類決策模型，實驗表明相比于其他基本匹配方法這種集成學(xué)習(xí)框架可以取得更高的匹配質(zhì)量.

2) 基于聚類的方法，如果只考慮屬性相似性，則仍屬于成對對齊的范疇.其主要思想是通過訓(xùn)練數(shù)據(jù)來學(xué)習(xí)如何更好地將相似的實體聚類到一起.Cohen和Richman提出了一種可擴(kuò)展的自適應(yīng)的實體名稱匹配和聚類技術(shù)[36]，通過訓(xùn)練樣本生成一個自適應(yīng)的距離函數(shù)，實驗表明通過訓(xùn)練這種自適應(yīng)技術(shù)可以有效地提高模型的準(zhǔn)確率.類似地，McCallum和Wellner在條件隨機(jī)場實體對齊模型中使用監(jiān)督學(xué)習(xí)的方法訓(xùn)練產(chǎn)生距離函數(shù)度量，通過在訓(xùn)練集中調(diào)整權(quán)重參數(shù)去最大化特征函數(shù)和學(xué)習(xí)參數(shù)之積，使得相似的實體聚類，從而在無向圖中產(chǎn)生正確的分區(qū)[37].Pasula等人使用半監(jiān)督機(jī)器學(xué)習(xí)算法和基于圖的概率關(guān)系模型進(jìn)行共指關(guān)系的發(fā)現(xiàn)[38]，這些內(nèi)容屬于集體實體對齊，將在基于概率模型的集體對齊方法中作詳細(xì)闡述.

3.1.2.2主動學(xué)習(xí)

監(jiān)督學(xué)習(xí)一個主要的瓶頸在于很難獲得足夠的訓(xùn)練數(shù)據(jù)進(jìn)行分類預(yù)測，主動學(xué)習(xí)通過與人的交互解決這個問題.基本思想是通過初始少量的訓(xùn)練數(shù)據(jù)集和設(shè)計高效的人機(jī)交互算法迭代式地訓(xùn)練分類模型，不斷提升分類效果.具體過程如下：1)通過初始訓(xùn)練數(shù)據(jù)集訓(xùn)練一個分類模型；2)分類所有的比較向量；3)將難于有效分類的候選對按照一定算法選出并詢問用戶進(jìn)行人工分類；4)將人工分類后的比較向量加入訓(xùn)練數(shù)據(jù)集；5)通過訓(xùn)練產(chǎn)生更好的分類模型；6)重復(fù)這個過程直到達(dá)到指定的停止標(biāo)準(zhǔn)或者最大迭代次數(shù)，獲得最終的分類模型.圖4為這一過程的示意圖.

Fig. 4　Diagram of human-computer interaction entity alignment process based on active learning.圖4　主動學(xué)習(xí)人機(jī)交互實體對齊過程示意圖

目前有很多基于主動學(xué)習(xí)的數(shù)據(jù)匹配研究.Sarawagi等人構(gòu)建的ALIAS系統(tǒng)[39]基于人機(jī)交互完成實體記錄鏈接和去重任務(wù).系統(tǒng)通過3個分類樹構(gòu)建一種集成式的分類模型，對于那些在3個分類樹模型下結(jié)果不同的比較向量則有用戶手工指定，再將分類結(jié)果代入模型進(jìn)行迭代以產(chǎn)生更好的分類結(jié)果.Tejada等人在文獻(xiàn)[40]中基于同樣的方法構(gòu)建了Active Atlas系統(tǒng).Arasu等人在以上研究的基礎(chǔ)上提出了一種新穎的應(yīng)用于數(shù)據(jù)匹配任務(wù)的主動學(xué)習(xí)算法[41]，將索引計數(shù)與主動學(xué)習(xí)相結(jié)合以提高算法運(yùn)行效率，多種分類算法都可以應(yīng)用到這個模型中，由用戶指定一個最小的準(zhǔn)確率，主動學(xué)習(xí)過程則在這個準(zhǔn)確率下獲得盡可能高的召回率，同時盡可能減少需要人工分類的數(shù)據(jù).實驗表明在大型數(shù)據(jù)庫匹配過程中這種方法明顯優(yōu)于ALIAS系統(tǒng)和Active Atlas系統(tǒng).

3.1.2.3無監(jiān)督機(jī)器學(xué)習(xí)

在缺乏訓(xùn)練數(shù)據(jù)并且無法利用人工匹配的情況下，可以通過無監(jiān)督的機(jī)器學(xué)習(xí)完成實體匹配任務(wù).無監(jiān)督機(jī)器學(xué)習(xí)的實體匹配的主要思想是利用聚類算法將比較向量相似的實體分配到相同的分類中，這種思想植根于Fellegi-Sunter概率模型分類方法.

Verykios等人提出了一種基于聚類的“boot-strapping”技術(shù)學(xué)習(xí)匹配模型[42].其基本思想基于交互訓(xùn)練，利用非常少的已標(biāo)記數(shù)據(jù)，采用無監(jiān)督學(xué)習(xí)，根據(jù)比較向量的相似性聚類實體.所有在同一聚類中的實體對對應(yīng)同一分類(匹配與否)，通過少量的已標(biāo)記數(shù)據(jù)的匹配情況去推理聚類中所有數(shù)據(jù)的匹配情況.Elfeky等人利用這種思路開發(fā)了實體鏈接工具TAILOR[33].Ravikumar和Cohen在文獻(xiàn)[43]中利用相似的思路提出一種無監(jiān)督學(xué)習(xí)下的層次圖模型框架進(jìn)行實體記錄的匹配，這種方法將組成比較向量的每個屬性字段建模成一個表示屬性值匹配與否的隱二元變量，將原有的產(chǎn)生式模型轉(zhuǎn)換為層次化的3層模型，并在一定約束條件下進(jìn)行推理實現(xiàn)實體記錄的匹配.Bhattacharya和Getoor在文獻(xiàn)[44]中采用基于隱狄利克雷分配(latent dirichlet allocation， LDA)模型的產(chǎn)生式模型進(jìn)行實體匹配的工作，這部分內(nèi)容屬于集體實體對齊，將在3.3.2節(jié)中作詳細(xì)闡述.

3.2局部集體對齊方法

知識庫中實體之間的關(guān)系對于實體對齊具有重要意義，可以有效地提高匹配的準(zhǔn)確率和召回率，關(guān)系相似性的作用在某些情況下可以超過屬性相似性.基于簡單關(guān)系的局部集體對齊方法，將實體本身屬性(其相似度以simAttr()表示)和與之有關(guān)聯(lián)實體(這里指其鄰居實體,其相似度以simNB()表示)的屬性分別分配不同的權(quán)重，并將其加權(quán)求和計算總體相似度，可形式化表達(dá)為

sim(e1,e2)=αsimAttr(e1,e2)+(1-α)simNB(e1,e2).

其中：

為了評價向量中每個分量的重要性，算法使用TF-IDF為其賦予權(quán)重，并為每個向量建立倒排表，通過簡單的過濾剪枝生成候選對，最后使用余弦相似性函數(shù)計算每個候選對的2個向量的相似性simname(e1,e2)和simdoc(e1,e2)，并輸出最終結(jié)果：

其中，wn為名稱向量的相似性權(quán)重.

實驗證明，這種方法具有較好的召回率和較快的運(yùn)行速度，可以應(yīng)用到大規(guī)模數(shù)據(jù)集中，但其準(zhǔn)確性有待進(jìn)一步提高.究其根本這種方法仍屬于成對的實體匹配方法，只是將實體的關(guān)系看作是實體的一類特殊屬性代入計算，并沒有真正地實現(xiàn)“collective”的方式.

3.3全局集體對齊方法

3.3.1基于相似性傳播集體對齊方法

基于相似性傳播的方法是一種真正實現(xiàn)了集體方式的實體對齊方法.它通過初始匹配以“bootstrapping”方式迭代地產(chǎn)生新的匹配[46-47].舉例來講，如果2個作者匹配，則與這2個作者具有“coauthor”關(guān)系的另外2個相似名字的作者會有較高的相似度，而這個相似度又會對其他作者匹配產(chǎn)生影響.在這種方法中，實體之間的相似度會隨著算法的迭代不斷變化，直到算法收斂或達(dá)到指定的停止條件.

這種方式綜合利用了實體對的屬性和關(guān)系，通過初始匹配在鄰域圖上不斷迭代完成所有匹配對的發(fā)現(xiàn)過程，具有較好的準(zhǔn)確性和可擴(kuò)展性.實驗表明可以在關(guān)系數(shù)量有限的大型知識庫中取得較好的匹配效果，但需要一定的人工參與.

3.3.2基于概率模型的集體對齊方法

基于概率模型的集體對齊方法通過為實體匹配關(guān)系和匹配決策建立復(fù)雜的概率模型來避免這種“bootstrapping”方式的問題.舉例來講，我們不需要知道任何2個作者的匹配關(guān)系，只要知道2個作者分別和另外2個作者互為“coauthor”，那么我們就認(rèn)為他們在一定條件下有可能匹配.基于概率模型的集體對齊方法一般采用統(tǒng)計關(guān)系學(xué)習(xí)進(jìn)行計算和推理，通過集成關(guān)系或邏輯表示、概率推理、不確定性處理、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等方法,以獲取關(guān)系數(shù)據(jù)中的似然模型.常用的概率模型有關(guān)系貝葉斯網(wǎng)絡(luò)模型[38,48]、LDA分配模型[44,49]、條件隨機(jī)場(conditional random field， CRF)模型[37,50]和Markov邏輯網(wǎng)(Markov logic networks， MLNs)模型[51-52]等，概率模型提供了一種標(biāo)準(zhǔn)的形式化關(guān)系建模方式，可以有效提高匹配效果，但是應(yīng)用到大規(guī)模知識庫上的效率問題是一個嚴(yán)重的瓶頸.這里簡單介紹4種常用概率模型在知識庫實體對齊中的應(yīng)用，并介紹一種匹配大規(guī)模知識庫的全局概率算法[53].

3.3.2.1基于LDA模型的實體對齊

Fig. 5　Comparison of Two LDA models.圖5　2種LDA模型的比較

為了解決實體辨析問題，為每個實體引入屬性va，通過概率修正實體屬性集合Va來獲得實體的引用r.從一個實體產(chǎn)生一個引用的概率為P(r|va)，其中r是可觀測的，實體a和群組z為隱含變量，修改后的模型如圖5(b)所示.

在給定α，β和V的條件下，文檔集的所有實體引用的生成概率為

模型采用無監(jiān)督學(xué)習(xí)的方法結(jié)合吉布斯采樣進(jìn)行集合實體解析.為了提高Dirichlet過程的推理效率，Bhattacharya等人在文中提出了一種聚類分塊算法，通過適時改變實體的標(biāo)簽，達(dá)到實體引用凝聚聚類的效果.LDA實體解析模型可以看作是考慮實體間關(guān)系的Dirichlet過程混合模型的擴(kuò)展，在真實世界數(shù)據(jù)集上的實驗表明這種方法還有待進(jìn)一步的研究和提高.

3.3.2.2基于CRF模型的實體對齊

以LDA為代表的產(chǎn)生式模型具有廣泛的應(yīng)用途徑，但其本身也具有很多不足之處：為了定義聯(lián)合概率，必須列出所有可能的觀察序列，實際中列出觀察序列的交互特征或長距離約束是不容易實現(xiàn)的，并且產(chǎn)生式模型很難使用各種高度重疊的、非依賴的、不同粒度的特征.因此，在一些相似性計算的問題上，產(chǎn)生了許多使用條件模型代替產(chǎn)生式模型的成功案例.

McCallum等人提出了一種基于圖劃分技術(shù)的CRF實體辨析模型[37]，這個模型以觀察值為條件產(chǎn)生實體辨析的決策.文中提出3種處理這種不確定性的條件模型，都屬于條件訓(xùn)練的無向圖模型，這種模型善于獲取屬性間的因果關(guān)系不是很明顯的具有相互依賴關(guān)系的數(shù)據(jù).設(shè)E為實體的集合，X為觀測隨機(jī)變量的集合，Y為每個實體唯一的整型標(biāo)識符隨機(jī)變量的集合，A為實體的所有屬性集合，則實體辨析問題可以表述為給定一組觀察及其上下文信息X，尋找最可能的實體標(biāo)識的集合Y和屬性集合A，即條件概率模型的實體辨析定義為通過訓(xùn)練去最大化P(Y,A|X).

模型1定義了條件隨機(jī)場模型進(jìn)行實體辨析的最一般形式，將所有實體的觀察值、標(biāo)識值和屬性都看作是無向圖的頂點，邊表明相連的節(jié)點具有依賴關(guān)系，模型中參數(shù)的捆綁模式定義為模板T，每一個圖中模版的實例定義為一個命中H.根據(jù)Hammersley-Clifford定理，將條件概率以指數(shù)形式表示為

其中，勢函數(shù)定義為特征函數(shù)f與學(xué)習(xí)參數(shù)λ的點積，(y,a,x:ht)為一個模版命中選定的(Y,A,X)的子集,Zx為歸一化函數(shù)使得y的概率分布之和為1.

為了避免在推理過程中模型的結(jié)構(gòu)變化，模型2在模型1的基礎(chǔ)上去掉了依賴實體數(shù)量的部分，使用指示2個觀察值(Xi,Xj)是否指向同一實體的二值隨機(jī)變量Yi j取代實體標(biāo)識節(jié)點Yi，同時引入附加的勢函數(shù)λl′×fl′(yi j,yjk,yik)去除不一致的決策，將不一致部分的學(xué)習(xí)參數(shù)λl′置為負(fù)值使得此部分為0概率，公式可以形式化表示為

當(dāng)模型2的屬性部分在實體對齊中不是必須時，我們可以將屬性部分去掉以進(jìn)一步簡化模型，得到一個更加直接、表達(dá)能力更強(qiáng)的無向圖模型——模型3：

Domingos等人在文獻(xiàn)[37]的基礎(chǔ)上提出了一種基于條件隨機(jī)場模型的多關(guān)系的實體鏈接算法[50]，并詳細(xì)闡述了公共屬性在多關(guān)系實體鏈接中的作用.算法將實體屬性作為頂點引入到無向圖中，同時引入稱為信息節(jié)點的二項節(jié)點，從而產(chǎn)生一個更加復(fù)雜的條件概率模型.模型的推理和參數(shù)的學(xué)習(xí)采用和文獻(xiàn)[37]相同的方法，并針對大數(shù)據(jù)量引入基于canopy的索引(參見5.4節(jié))來提高匹配效率.Wick等人在文獻(xiàn)[56]中提出一種基于條件隨機(jī)場的判別式層次模型，算法迭代地將實體劃分為樹結(jié)構(gòu)，觀察值作為葉子結(jié)點，樹的內(nèi)部節(jié)點將葉子節(jié)點的信息逐層匯總，進(jìn)行摘要，從而形成一個高度精簡而信息豐富的結(jié)構(gòu)進(jìn)行高效推理.實驗證明，在大規(guī)模數(shù)據(jù)集中，這種判別式層次模型相比于其他基于CRF的二元匹配模型快出幾個數(shù)量級，為概率模型在大規(guī)模知識庫的實體對齊上的應(yīng)用提供了一個有效的解決方案.

3.3.2.3基于Markov邏輯網(wǎng)的實體對齊

Markov邏輯網(wǎng)是一種結(jié)合一階謂詞邏輯和概率圖模型的復(fù)雜性和不確定性問題表示和處理方法[57-58].從概率統(tǒng)計的角度來看，Markov邏輯網(wǎng)不僅提供了一種描述Markov網(wǎng)的有效手段，還能夠靈活地在Markov網(wǎng)中融入模塊化知識域；同時，從一階謂詞邏輯的角度來看，Markov邏輯網(wǎng)給一階謂詞邏輯加入了不確定性處理能力，并且能夠允許知識域中存在不完整性和矛盾性等問題.Markov邏輯網(wǎng)在機(jī)器學(xué)習(xí)和人工智能等諸多領(lǐng)域都有重要應(yīng)用，也可以作為知識庫實體對齊的重要手段.

Singla和Domingos提出了一種將Markov邏輯網(wǎng)應(yīng)用到實體解析中的方法[51]，將其看作是傳統(tǒng)的Fellegi-Sunter概率模型的一般化形式.他們使用一階謂詞邏輯和Markov隨機(jī)場，VP算法[55]形成一個綜合性的實體解析解決方案.由于Markov隨機(jī)場和條件隨機(jī)場的內(nèi)在關(guān)系(CRF是給定觀察集合下MRF(Markov random field)的分布，也就是條件分布，具體內(nèi)容見3.3.2.2節(jié))，我們直接給出Markov隨機(jī)場的聯(lián)合分布形式：

其中，x{k}是圖中第k個團(tuán)的狀態(tài)；φk是勢函數(shù)；Z是歸一化因子，也稱為分區(qū)函數(shù).將勢函數(shù)用特征函數(shù)加權(quán)求和的指數(shù)形式代替，可得其線性對數(shù)模式為

其中，fj(x)∈{0,1}.

基于一階謂詞邏輯的知識庫可看作是在一個可能世界的集合上建立一系列硬性規(guī)則，其基本思想是讓那些硬性規(guī)則有所松弛，即當(dāng)一個世界違反了其中的一條規(guī)則時，這個世界存在的可能性將降低，但并非不可能.一個世界違反的規(guī)則越少，這個世界存在的可能性就越大.為此，給每個規(guī)則都加上了一個特定的權(quán)重，它反映了對滿足該規(guī)則的可能世界的約束力.則Markov邏輯網(wǎng)L可定義為一組二元項(Fi,wi)，其中,Fi表示一階謂詞邏輯公式，wi是一個實數(shù).這組二元項(Fi,wi)與一組有限常量集C={c1,c2,…,c|C|}一起定義了一個Markov網(wǎng)ML,C：

1)L中的任意閉原子(ground atom)都對應(yīng)了ML,C中的一個二值節(jié)點.若此閉原子為真，則對應(yīng)的二值節(jié)點取值為1；若為假，則取值為0.

2)L中的任意閉規(guī)則都對應(yīng)著一個特征值，若此閉規(guī)則為真，則對應(yīng)的特征值為1；若為假，則特征值為0這個特征值的權(quán)重為二元項中該規(guī)則Fi對應(yīng)的權(quán)重wi.

由此可知，ML,C的節(jié)點由 Markov邏輯網(wǎng)L中每個閉原子生成，邊由閉原子之間的關(guān)系生成.Markov邏輯網(wǎng)可看作是一個用以構(gòu)建Markov網(wǎng)的模板.由此可得一個閉Markov網(wǎng)中所蘊(yùn)含的可能世界x的概率分布為

其中，F(xiàn)表示邏輯網(wǎng)中公式的數(shù)量，ni(x)表示關(guān)于規(guī)則的取值為真的對應(yīng)閉規(guī)則Fi的個數(shù).

最大可能性問題是概率圖模型推理中的重要內(nèi)容，基本過程可表述為：給定證據(jù)變量集x，求變量集y最可能處于的狀態(tài)，在Markov邏輯網(wǎng)中，可以轉(zhuǎn)化為求以下最大化問題：

其中,wi表示子句的權(quán)重，ni(x,y)表示子句的閉子句的真值數(shù)量.計算最大可能性問題可轉(zhuǎn)換為典型的最大化加權(quán)的可滿足性問題，即尋找一組變量的賦值，使得所有被滿足的子句的權(quán)重之和最大.這類問題可以高效地通過類似MaxWalkSAT這類加權(quán)可滿足性問題解決器來計算[59].條件概率可以通過最小閉Markov網(wǎng)的吉布斯采樣來計算.Markov邏輯網(wǎng)的學(xué)習(xí)是指在Markov邏輯網(wǎng)結(jié)構(gòu)確定的前提下,學(xué)習(xí)和優(yōu)化模型的參數(shù).一般采用最大似然方法，但計算一個規(guī)則在世界中的閉規(guī)則的個數(shù)是不明智的，因此在封閉世界假設(shè)的前提下，我們采用判別訓(xùn)練進(jìn)行參數(shù)學(xué)習(xí).

在Markov邏輯網(wǎng)上進(jìn)行實體辨析，需要定義一系列等價謂詞公理，通過這些等價性公理以及其他一些公式，我們就可以在Markov邏輯網(wǎng)上進(jìn)行知識庫的集體實體對齊.

為了解決大規(guī)模知識庫上的實體對齊的效率問題，Rastogi等人在Markov邏輯網(wǎng)的基礎(chǔ)上提出了一個原則性的框架來擴(kuò)展任何通用的實體匹配算法[52].這個框架內(nèi)容主要包括：1)將實體匹配器建模成一個黑盒；2)匹配器的多重實例運(yùn)行在實體的有限子集上；3)通過跨實例的消息傳遞機(jī)制控制匹配器的交互.實驗證明，大規(guī)模數(shù)據(jù)集上這個算法無論在準(zhǔn)確率、召回率還是運(yùn)行時間上都可以取得較好的效果.

3.3.2.4基于全局概率算法的實體對齊

基于本體的大規(guī)模知識庫的實體對齊有很多新的挑戰(zhàn)，其中一個重要方面就是本體知識庫的結(jié)構(gòu)相對復(fù)雜，其對齊需要分別考慮類別、屬性以及實體和它們之間的相互關(guān)系，Suchanek等人針對這個問題提出了一種新型的基于概率的全局算法PARIS[53]，算法在不需要任何參數(shù)調(diào)節(jié)的條件下能夠高效地跨本體同時對齊類別、屬性、關(guān)系和實例.

Suchanek等人對實體對齊的全局概率模型進(jìn)行了如下形式化的定義：

1) 定義了逆函數(shù)性fun-1(r).逆函數(shù)性的大小表明事實三元組的同一關(guān)系中賓語相等對主語相等的決定能力，關(guān)系的逆函數(shù)值越大，如果關(guān)系中賓語相等，則主語相等的可能性也越大.

2) 結(jié)合全局逆函數(shù)性定義實例匹配的概率公式.在知識庫對齊中2個實例相等的邏輯規(guī)則表述為

轉(zhuǎn)換為概率公式表達(dá)：

如果考慮當(dāng)賓語不相等且全局函數(shù)性較高則主語相似的概率應(yīng)該較低，利用同樣的概率過程，可以得到：

因此，結(jié)合這2方面考慮將2個概率公式相乘，可以得到最終的實例匹配概率公式：

3) 定義的關(guān)系匹配的概率公式.不同于實例相等，更加廣泛的關(guān)系相等的判別應(yīng)該是包含關(guān)系的判別，即Pr(r?r′)，簡言之，就是一個本體知識庫中的關(guān)系r所對應(yīng)的主語賓語對同樣在另一個本體知識庫中的關(guān)系r′中，這樣的實體對所占的比例：

分子的值需要根據(jù)知識庫中已有的匹配實體對來計算，可得：

可轉(zhuǎn)化為概率公式：

同樣地可以將分母轉(zhuǎn)化為在另一個知識庫中有對應(yīng)實體的關(guān)系r所對應(yīng)的實體對：

Pr(r?r′)最終的表達(dá)形式為

然后，定義類別匹配的概率公式.類別相等可以表示為Pr(c?c′)，即在2個知識庫中的2個類別c和c′中相等的實例個數(shù)所占的比例，表述為

可以估計在2個知識庫類別中相等實例的數(shù)量為

因此，最終的類別相等概率可表述為

4) 給出算法描述.PARIS算法以2個待對齊的知識庫作為輸入，并假設(shè)每個知識庫中不存在重復(fù)的實例，算法的輸出為2個知識庫中帶有相似概率實體對的集合.算法的主要步驟為：①根據(jù)實例匹配概率公式計算2個知識庫中實例相似的概率；②根據(jù)關(guān)系匹配概率公式計算2個知識庫中包含關(guān)系的概率；③迭代執(zhí)行這2步直到算法收斂；④根據(jù)收斂后的數(shù)據(jù)和類別匹配概率公式計算類別的等價性.為了更快執(zhí)行效果，算法選擇一個較小的參數(shù)θ，并設(shè)定對于所有的關(guān)系對r和r′有Pr(r?r′)=θ，從第2輪迭代開始，將使用計算的結(jié)果值替代θ.為了加速算法的收斂速度，引入了一個逐步遞增的阻斷因子，使得算法能夠在幾步后收斂.

PARIS算法作為第1個在大規(guī)模知識庫工作的全局式概率算法，在沒有任何先驗知識、調(diào)節(jié)參數(shù)和訓(xùn)練數(shù)據(jù)的條件下，可以同時完成實例、關(guān)系和類別對齊，并取得良好的實驗效果.但是PARIS不能處理結(jié)構(gòu)異質(zhì)性，即無法匹配一個關(guān)系和一個實例或者一個實例和一個字符串，即使他們指向的是同一個事物，PARIS也不能匹配不同層級結(jié)構(gòu)的實體，比如作為同一個人出生地的國家和這個國家的城市則無法匹配.

表2對3.1～3.3節(jié)介紹的實體對齊算法進(jìn)行了分類匯總:

Table 2　Classification Summary Tables of Entity Alignment Algorithms

4基于相似性函數(shù)的特征匹配

4.1基于文本相似性函數(shù)的特征匹配

4.1.1基于Token的相似性函數(shù)

基于token的相似性函數(shù)使用某種函數(shù)將待匹配的文本字符串轉(zhuǎn)換為一系列子串的集合，我們稱這些子串為token，稱這個函數(shù)為標(biāo)記化函數(shù)，記為tokenize().常用的基于token的相似性函數(shù)有Jaccard相似性函數(shù)[60]、余弦相似性函數(shù)[16]和基于q-gram的相似性函數(shù)[16].

Jaccard系數(shù)等于2個集合的交與并的比值，可以用來衡量2個集合的相關(guān)性.Monge和Elkan在文獻(xiàn)[60]中給出了字符串相似性比較的Jaccard系數(shù)的形式化表示方式：

其中，s1和s2為給定的2個待比較的字符串.

基于Jaccard系數(shù)的相似性函數(shù)優(yōu)點在于集合相交操作是順序無關(guān)的，因此不同token的先后順序?qū)Χ攘拷Y(jié)果沒有影響.但是函數(shù)具有錯誤敏感性，token缺失或者錄入錯誤等情況會對結(jié)果產(chǎn)生很大的影響.

余弦相似性是將2個文本字符串的token集合看作是2個n維的向量，通過計算這2個向量夾角的余弦值來評估這2個向量代表字符串的相似程度.一般使用詞頻-逆文檔頻率(tf-idf)計算每個向量中token的權(quán)重w，2個字符串s1和s2對應(yīng)文檔的向量表示為w11,w12,…，w1n，w21,w22,…，w2n，則s1和s2的余弦相似性可表示為

其中:

余弦相似性同樣具有基于token的相似性函數(shù)的順序無關(guān)的優(yōu)點，同時由于加入權(quán)重，可以更好地反映token的相似程度，但是與基于Jaccard系數(shù)的相似性函數(shù)一樣無法有效解決錯誤敏感性的問題，因此提出一種基于q-gram的相似性函數(shù).這種相似性函數(shù)使用字符串的q-gram作為token進(jìn)行相似性計算，由于q-gram產(chǎn)生的token是相互重疊的，因此可以有效地降低錯誤敏感性，代價是會產(chǎn)生更大的計算向量.

4.1.2基于編輯距離的相似性函數(shù)

與基于token的相似性函數(shù)不同，基于編輯距離的相似性函數(shù)將待匹配文本字符串看作一個整體，通過將一個字符串轉(zhuǎn)換成為另一個字符串所需要的編輯操作的最小代價作為衡量2個字符串相似性的度量，基本的編輯操作包括插入、刪除、替換、交換位置等.基于編輯距離的相似性函數(shù)可以有效地處理錄入錯誤等錯誤敏感性問題.常用的基于編輯距離的相似性函數(shù)有基于Levenshtein距離[61]、基于 Smith-Waterman距離[62]、基于affine gap距離[63]、基于Jaro和Jaro-Winkler距離[26,64]的相似性函數(shù).

給定2個字符串s1和s2，它們之間的Levenshtein距離等于將s1轉(zhuǎn)換為s2所需要的插入、刪除和替換操作的最小次數(shù).通常Levenshtein距離通過動態(tài)規(guī)劃來求解：算法初始化一個(|s1|+1)×(|s2|+1)的矩陣M,我們記M的第i行第j列的元素為Mi,j，其中0≤i≤|s1|，0≤j≤|s2|.M的值為

矩陣M中的值計算完成之后，M|s1|,|s2|即為Levenshtein距離.

基于Levenshtein距離的相似性函數(shù)可以降低相似性匹配的錯誤敏感性，但是它為每一個字符的每一次編輯操作都賦予相同的權(quán)重(次數(shù))，并不考慮不同字符或子串的重要程度，但實際上不同位置的子串編輯操作對相似性匹配的重要性可能不同，比如一些前后綴和縮寫詞的處理.基于 Smith-Waterman距離和基于affine gap距離的相似性函數(shù)就是為了解決這一問題提出的2種算法.

對于待匹配的2個字符串的前后綴差異的影響，可以使用基于Smith-Waterman距離的相似性計算來解決，它通過尋找2個字符串的最長公共子序列，將最長公共子序列之外的子串作為前后綴，在計算時將最長公共子序列的編輯操作賦予較高的權(quán)重，而前后綴賦予較低的權(quán)重來降低前后綴對相似性匹配帶來的影響.對于字符串中間的縮寫詞可能產(chǎn)生的影響，可以通過基于affine gap距離來解決.其基本思路是針對待匹配的2個字符串中一個字符串中間部分連續(xù)多個字符缺失的情況，對缺失子串整體賦予較低的權(quán)重，使得子串的缺失對相似性的影響要小于單個字符缺失累加帶來的影響.這2種相似性函數(shù)都可以通過動態(tài)規(guī)劃的算法進(jìn)行計算.

Jaro和Jaro-Winkler相似性函數(shù)可以針對字符位置交換操作進(jìn)行處理.其中Jaro距離的主要思想是通過比較2個字符串的公共部分來計算相似程度，所謂“公共”這里特指2個字符相等并且它們在字符串中的位置距離之差Δ不大于較小字符串長度的一半，即Δ≤0.5×min(|s1|,|s2|)，設(shè)t為公共部分發(fā)生位置交換的次數(shù)，δ為公共字符的集合，則Jaro相似性函數(shù)可以定義為

基于Jaro距離的相似性函數(shù)可以容忍少量的拼寫錯誤，但對于2個主體部分相同但前綴或者后綴不同的字符串的度量效果并不好.這類相似性函數(shù)在人名的對齊中應(yīng)用較多，在實踐中人們發(fā)現(xiàn)人名前半部分出現(xiàn)錯誤的可能性遠(yuǎn)小于中部和尾部，因此提出一種如果字符串前半部分相同則提高相似性度量值的算法公式：對于2個字符串s1和s2，以及共同前綴τ，Jaro-Winkler相似性函數(shù)可以表示為

simJaro-Winkler(s1,s2)=simJaro(s1,s2)+

|τ|×f×(1-simJaro(s1,s2)),

其中,f為前綴τ對整體相似度影響的一個常量.

4.1.3混合型相似性函數(shù)

基于token的相似性函數(shù)和基于編輯距離的相似性函數(shù)各有優(yōu)缺點，在實踐中為了更準(zhǔn)確地判斷相似性，經(jīng)常將兩者結(jié)合起來，構(gòu)成混合型相似性函數(shù)，當(dāng)然也會帶來更高的計算復(fù)雜度.常用的混合型相似性函數(shù)有擴(kuò)展的Jaccard相似性函數(shù)[65-66]、Monge-Elkan相似性函數(shù)[60]和soft TFIDF相似性函數(shù)[67].

擴(kuò)展的Jaccard相似性函數(shù)將傳統(tǒng)的Jaccard方法通過tokenize()函數(shù)形成的token的準(zhǔn)確匹配擴(kuò)展為相似性匹配，以容忍token的少量錄入錯誤.形式化上，使用simtoken(ti,tj) 作為2個字符串token的相似性度量，其中ti∈tokenize(s1)，tj∈tokenize(s2).token的共享集合定義為

其中，θ為相似性閾值.類似地可以定義只在s1不在s2中出現(xiàn)的token集合為

Unique(s1)={ti|ti∈tokenize(s1)∧

(ti,tj)?shared(s1,s2)},

以及只在s2不在s1中出現(xiàn)的token集合為

Unique(s2)={tj|tj∈tokenize(s2)∧

(ti,tj)?shared(s1,s2)}.

定義每個token的權(quán)重為w，則擴(kuò)展的Jaccard相似性函數(shù)可以形式化定義為

Monge-Elkan相似性函數(shù)用來對由多個詞構(gòu)成的字符串進(jìn)行相似性度量.簡單來說，它將與每一個ti最相似的tj的相似性度量值simtoken(ti,tj)求和后標(biāo)準(zhǔn)化，可以形式化表示為

close(θ,s1,s2)={ti|ti∈tokenize(s1)∧

?tj∈tokenize(s2):simtoken(ti,tj)>θ}.

對于每一個close(θ,s1,s2)中的ti，取與其相似性最大的tj，它們之間的度量值可表示為

則結(jié)合余弦相似性表達(dá)式(見4.1.1)可以得到soft TFIDF相似性函數(shù)的形式化表示方式：

4.2基于結(jié)構(gòu)相似性函數(shù)的特征匹配

結(jié)構(gòu)相似性是實體對相似性度量的重要組成部分，常用的相似性函數(shù)包括直接計算實體對的共同鄰居計數(shù)[68]、共同鄰居的Jaccard相關(guān)系數(shù)[47]、Adar評分[69]、Katz評分[70]和SimRank[71]等，下面對這5種函數(shù)進(jìn)行簡要介紹.

1) 共同鄰居計數(shù).它是一種最簡單直接的計算結(jié)構(gòu)相似性的方法，通過直接計算2個實體相同鄰居節(jié)點的個數(shù)來獲得實體對的結(jié)構(gòu)相似性，形式化表示為

其中,K為一個足夠大的常量能夠使得所有實體對的相似性計數(shù)值都小于1.

2) Jaccard相關(guān)系數(shù).它是一種非常常用的集合相似性的度量函數(shù).基于Jaccard系數(shù)的結(jié)構(gòu)相似性函數(shù)定義為實體對共同鄰居集合的交集與并集的比，形式化表述為

3) Adar評分.前面2種方法為每個匹配的鄰居賦予相同的權(quán)重，但實際中某些鄰居可能對實體相似度的影響大小并不相同，Adamic和Adar[69]正是基于這種觀察，提出了一種類似TF-IDF的為關(guān)系賦予權(quán)重的思路：存在關(guān)聯(lián)關(guān)系越多的實體其作為鄰居在計算中所分配權(quán)重越低，結(jié)合Jaccard相關(guān)系數(shù)，實體相似性度量中的Adar評分可以定義為

其中,u(e)為實體e關(guān)系的唯一性程度.可以看出，所有實體u(e)相等時，

4) Katz評分.有一些相似性度量考慮實體對之間關(guān)系的最短連接距離，其基本思想是如果2個實體之間由更多更短的關(guān)系路徑所連接，則它們更相似，形式化表述為

其中,paths(e1,e2)為e1和e2之間長度為l的路徑之和;β∈(0,1)是一個衰減系數(shù)，β越小則l越大的路徑對相似度貢獻(xiàn)就越小.

5) SimRank.它是一種基于圖的拓?fù)浣Y(jié)構(gòu)信息來衡量任意2個對象間相似程度的模型，該模型的核心思想為：如果2個對象被其相似的對象所引用，那么這2個對象也相似.

SimRank模型定義2個實體的相似是基于下面的遞歸思想：如果指向?qū)嶓w結(jié)點e1和e2的結(jié)點相似，那么e1和e2也認(rèn)為是相似的.這個遞歸定義的初始條件是：每個結(jié)點與它自身最相似.如果用記號I(e1)表示所有指向結(jié)點e1的結(jié)點集合(即入鄰點集合)，用simSimRank(e1,e2)表示2個對象間的SimRank相似度，則simSimRank(e1,e2)的數(shù)學(xué)定義式為

①simSimRank(e1,e2)=0，當(dāng)I(e1)=?或I(e2)=?；

②simSimRank(e1,e2)=1，當(dāng)e1=e2；

③ 在其他情況下，

其中，C∈(0,1)是一個衰減系數(shù).

表3分類匯總了常用于實體對齊特征匹配的相似性函數(shù):

Table 3　Classification Summary Tables of Similarity Function Based Feature Matching

Continued (Table 3)

5分區(qū)索引技術(shù)

Christen在文獻(xiàn)[72]中對數(shù)據(jù)庫實體匹配的索引技術(shù)進(jìn)行了總結(jié)，這些數(shù)據(jù)庫中的分區(qū)技術(shù)大部分也可以用于知識庫的對齊過程.本文在其基礎(chǔ)上對用于知識庫的分區(qū)索引技術(shù)進(jìn)行分類和介紹.以下符號用于各種索引計算復(fù)雜度的討論：nA=|A|和nB=|B|分別為知識庫A和B對應(yīng)的實體數(shù)量；b為通過索引鍵值分區(qū)的塊數(shù)(簡單起見，假設(shè)A和B的分區(qū)塊數(shù)相等).對于索引剪枝能力的考查需要考慮索引鍵值的分布，由于實體的屬性鍵值分布一般介于均勻分布和齊普夫率分布[15]之間，因此利用這2種分布產(chǎn)生的候選對數(shù)量(分別記為記為NU和NZ)作為其上下界進(jìn)行討論.

5.1基本的分區(qū)索引

基本的分區(qū)索引根據(jù)索引的定義直接選擇實體屬性作為索引鍵值進(jìn)行構(gòu)建，把具有相同索引鍵值的實體分配到同一區(qū)塊，使得相似性匹配只在同一區(qū)塊中進(jìn)行.最早是在數(shù)據(jù)庫記錄鏈接中提出[22]，通常采用標(biāo)準(zhǔn)的倒排表進(jìn)行實現(xiàn).相比于其他索引實現(xiàn)具有實現(xiàn)簡單、速度快的優(yōu)點，但索引鍵值的選擇對這種索引具有重要的影響，索引鍵值對應(yīng)屬性的缺失、錯誤或者分布的不均衡都會導(dǎo)致匹配的準(zhǔn)確率和效率的下降.在不考慮索引鍵值缺失和錯誤的條件下，在知識庫對齊中其產(chǎn)生的候選對數(shù)量的上下限分別為

5.2基于滑動窗口的分區(qū)索引

基于滑動窗口的分區(qū)索引也稱近鄰排序索引，最早是由Hernandez等人在多數(shù)據(jù)庫融合問題中提出[73]，其核心思想是使用一個固定大小的滑動窗口在一個按照索引鍵值排好序的記錄列表中滑動，如果窗口大小為w，則每一次移動新進(jìn)入窗口的記錄與前面w-1條記錄進(jìn)行匹配產(chǎn)生候選對，最前面一條記錄則移出窗口.該文提出了一種基于排序數(shù)組的方法，在知識庫實體鏈接過程中，將2個知識庫的索引鍵值按照一定的順序插入到一個數(shù)組中，通過將一個窗口中來自不同知識庫的實體進(jìn)行匹配產(chǎn)生候選對.這種索引方式相比于標(biāo)準(zhǔn)索引能夠發(fā)現(xiàn)更多的匹配對，但也付出了更高的計算代價，而且如果窗口的大小不足以覆蓋具有相同索引鍵值的所有記錄，則會丟失正確的匹配對；同時這種索引方式對排序是錯誤敏感的，匹配記錄如果因為排序的原因無法排在一起，也會丟失正確的匹配對.由于這種方式候選對的數(shù)量只與窗口大小有關(guān)，而與索引鍵值的分布無關(guān)，因此知識庫對齊中其產(chǎn)生的候選對的數(shù)量為

Christen在另一篇技術(shù)報告[74]中提出了一種基于倒排表的近鄰排序索引方法.這種方式結(jié)合了標(biāo)準(zhǔn)索引和基于數(shù)組的近鄰排序索引的特點，使用標(biāo)準(zhǔn)索引的倒排表代替數(shù)組存儲索引鍵值，同時滑動窗口產(chǎn)生候選對.當(dāng)w=1時，基于倒排表的近鄰排序索引退化成為標(biāo)準(zhǔn)索引;當(dāng)w>1時，這種索引產(chǎn)生的候選對是標(biāo)準(zhǔn)索引產(chǎn)生候選對的一個超集，并且w越大，產(chǎn)生的候選對就越多.同樣地，基于倒排表的近鄰排序索引是使用更高的計算代價從更多的候選對中發(fā)現(xiàn)正確的匹配對，它克服了標(biāo)準(zhǔn)索引召回率低和基于數(shù)組的近鄰排序索引窗口大小的問題，但同時也具有這二者的部分缺點：1)索引鍵值分布的不均衡會導(dǎo)致匹配數(shù)量的增大問題;2)索引鍵值錯誤敏感性問題.在不考慮索引鍵值缺失和錯誤的條件下，基于倒排表的近鄰排序索引在知識庫對齊中產(chǎn)生的候選對的數(shù)量的上下限分別為

另外一類近鄰排序索引方法稱為自適應(yīng)的近鄰排序索引[75-76],同樣是結(jié)合標(biāo)準(zhǔn)索引和近鄰排序索引特點改進(jìn)而來.這種索引方式可分為2類：1)動態(tài)選擇滑動窗口大小[75]，使用索引鍵值上的“boundary pairs”來確定窗口的大小和位置進(jìn)行分區(qū)，是具有相似度量值的實體盡可能分配在一起形成候選對；2)動態(tài)改變窗口移動的步長[76]，而標(biāo)準(zhǔn)索引和近鄰排序索引可以看作是這種“sorted blocks”方法的2個極端，即滑動窗口每次移動1則為標(biāo)準(zhǔn)索引，每次移動w-1則為鄰排序索引，通過參數(shù)來控制窗口重疊的程度.這2種索引方式都是“Blocking”和“Windowing”2種方法的結(jié)合，它們對原有近鄰排序索引作了改進(jìn)，性能上略有提高.

5.3基于相似性的分區(qū)索引

1) 基于q-gram的索引和基于后綴數(shù)組的索引

為了解決數(shù)據(jù)質(zhì)量對索引帶來的影響，基于q-gram的索引和基于后綴數(shù)組的索引方法在標(biāo)準(zhǔn)索引鍵值之上通過迭代的方式進(jìn)行轉(zhuǎn)換，生成部分列表，然后將這些列表進(jìn)行處理后形成字符串列表并生成倒排索引.所不同的是基于q-gram的索引是生成q-gram列表，然后根據(jù)用戶指定的閾值參數(shù)生成這些q-gram列表的指定長度的子列表組合，最后將這些組合轉(zhuǎn)化為字符串生成倒排表形成基于q-gram的索引[77];而基于后綴數(shù)組的索引方法是生成后綴數(shù)組[78].這2種索引方法可以部分地解決錯誤敏感性問題，但其代價是產(chǎn)生大量的匹配對.文獻(xiàn)[72]中的實驗表明，這2種索引方式并不適合大規(guī)模知識庫的對齊工作，這里不作進(jìn)一步的介紹.

2) Hash索引

Hash索引的核心思想包含4個方面：①定義一個關(guān)于一項或多項屬性的Hash函數(shù)，每個塊bi都有一個Hash值hi標(biāo)識；②將所有h(r)=hi的引用r都?xì)w入bi中；③所有的塊都互不相交；④實體解析算法僅在塊內(nèi)運(yùn)行.其中，h(x)為把x映射成一個整數(shù)的Hash函數(shù).

傳統(tǒng)的Hash算法負(fù)責(zé)將原始內(nèi)容盡量均勻隨機(jī)地映射為一個簽名值，屬于偽隨機(jī)數(shù)產(chǎn)生算法.傳統(tǒng)Hash算法產(chǎn)生的2個簽名，如果相等，說明原始內(nèi)容在一定概率下是相等的；如果不相等，除了說明原始內(nèi)容不相等外，不再提供任何信息.這種方式的Hash算法不能滿足一些相似性的計算，因此，要設(shè)計一種對相似內(nèi)容產(chǎn)生的簽名也相近的Hash算法.MinHash[79]是LSH[80]的一種，可以用來快速估算2個集合的相似度.MinHash最初用于在搜索引擎中檢測重復(fù)網(wǎng)頁，也可以應(yīng)用于大規(guī)模聚類問題或者用于實體對齊的索引.

hmin(S)為集合S中的元素h(x)后具有最小Hash值的元素，那么對2個集合A和B，hmin(A)=hmin(B)成立的條件是A∪B中具有最小Hash值的元素也在A∩B中.假設(shè)，h(x)是一個良好的Hash函數(shù)，它具有良好的均勻性，能夠把不同元素映射成不同的整數(shù)，可得Pr[hmin(A)=hmin(B)]=Jaccard(A,B)，即集合A和B的相似度為集合A,B經(jīng)過Hash后最小Hash值相等的概率.通過這個結(jié)論，可以根據(jù)MinHash來計算2個集合的相似度.一般有2種方法：

① 使用多個Hash函數(shù).為了計算集合A，B具有最小Hash值的概率，我們可以選擇K個Hash函數(shù)，用這K個Hash函數(shù)分別對集合A,B求Hash值，對每個集合都得到K個最小值，集合A,B的相似度為K個最小值中相同元素個數(shù)與總的元素個數(shù)的比值.

② 使用單個Hash函數(shù).針對第1種方法計算復(fù)雜度高的問題可以使用單個Hash函數(shù)來求解.定義集合S中具有最小Hash值的K個元素，只需要對每個集合求一次Hash，然后取最小的K個元素，集合A,B的相似度等于集合A中最小的K個元素與集合B中最小的K個元素的交集個數(shù)與并集個數(shù)的比值.

5.4基于聚類的分區(qū)索引

1) Canopy聚類索引

Canopy聚類索引是通過高效的計算索引鍵值之間的距離(相似性)進(jìn)行聚類，從而將索引鍵值對應(yīng)的實體記錄插入到互相重疊的聚類當(dāng)中，候選對則從每個聚類的實體對中產(chǎn)生[36,81-82].索引鍵值的相似性一般使用Jaccard或Cosine相似性度量來計算.Canopy聚類索引首先創(chuàng)建一個倒排表，此倒排表的鍵由實體屬性詞的集合或者詞的q-gram的集合產(chǎn)生，列表的內(nèi)容包含這些集合中的項所對應(yīng)的實體記錄的標(biāo)識.倒排表建立之后，算法通過以下5個步驟迭代地產(chǎn)生互相重疊的聚類：①將知識庫所有待匹配實體的標(biāo)識插入到集合P中；②隨機(jī)選擇P中的一個標(biāo)識rc作為新聚類Ci的中心，并計算集合P中所有其他點與該中心的索引鍵值的相似性；③選擇2個閾值tl與tt(tl≤tt)，將所有相似性大于tl的實體標(biāo)識插入到Ci中；④將所有相似性大于tt的實體標(biāo)識連帶rc移出P；⑤重復(fù)執(zhí)行步驟②～④，直到P??.從上面的算法可以看到tl與tt是2個重要的控制參數(shù)，如果tl=tt則產(chǎn)生的聚類不會重疊，如果tl=tt=1則聚類產(chǎn)生的索引分區(qū)與標(biāo)準(zhǔn)索引是相同的.由于聚類的大小決定于索引鍵值的分布、相似性函數(shù)的選擇和這2個參數(shù)，我們無法準(zhǔn)確地控制每個聚類的大小，也很難評估產(chǎn)生的候選對的數(shù)量.我們知道候選對的數(shù)量與聚類的重疊程度有關(guān)，假設(shè)每個實體記錄可能插入1～v個聚類中，則候選對數(shù)量的上下限分別為

以上形式的聚類索引稱為基于閾值的Canopy聚類索引，Christen在文獻(xiàn)[74]中提出了一種最近鄰Canopy聚類索引方法.這種方法的思想是使用2個最近鄰參數(shù)nl和nt分別替代基于閾值的參數(shù)tl與tt，使得算法可以準(zhǔn)確地控制每個聚類的大小，但是也會產(chǎn)生由于指定的聚類大小無法涵蓋所有索引鍵值對應(yīng)的實體而丟失匹配對的情況.最近鄰Canopy聚類索引方法可以準(zhǔn)確地計算聚類的數(shù)量和大小，其產(chǎn)生候選對的數(shù)量為

2) 基于StringMap的索引

基于StringMap的索引的核心思想是將索引鍵值轉(zhuǎn)換為對象映射到高維空間并保留索引鍵值之間的相似性，然后使用與Canopy索引同樣的方式聚類相似的實體對象[83].基于StringMap的索引建立有2個步驟:①迭代地產(chǎn)生n個高維空間坐標(biāo)系，將原有實體分別映射到這n個坐標(biāo)系下；②采用和Canopy索引類似的方法在高維空間下對索引鍵值相似的實體進(jìn)行聚類，所有包含相似索引鍵值的實體將被插入到同一個區(qū)塊中.這個過程中有3個關(guān)鍵問題需要考慮：①映射到高維空間時樞軸字符串的選擇，一般采用StringMap中的迭代的最遠(yuǎn)最優(yōu)先算法；②高維空間維度的選擇,實驗得到的比較理想的數(shù)值為15≤n≤25，如果維度選擇過大則可能導(dǎo)致維度災(zāi)難；③存儲高維對象的數(shù)據(jù)結(jié)構(gòu)的選擇,常用的存儲結(jié)構(gòu)有R-Tree[83]，KD-Tree[84]，Grid[85]等.

5.5動態(tài)分區(qū)索引

在大規(guī)模知識庫的實體對齊過程中，由于缺乏屬性的先驗知識和訓(xùn)練數(shù)據(jù)，特別是在找不到可以快速計算的距離度量的情況下，無法自動地選擇合適的索引鍵值.針對這種情況，McNeill等人在文獻(xiàn)[86]的基礎(chǔ)上提出了一種動態(tài)分區(qū)索引的方法[87]，其核心思想是記錄按照一定的次序(字母序)通過共享的屬性值劃分成區(qū)塊，對于超過指定大小的區(qū)塊態(tài)選擇共享屬性繼續(xù)分區(qū)直到所有區(qū)塊大小都小于指定閾值，將所有分區(qū)數(shù)據(jù)形成候選對以進(jìn)行相似性計算獲得最終結(jié)果.McNeill設(shè)計了2層的分區(qū)索引算法并對可能重復(fù)計算的候選對進(jìn)行了篩選，同時將算法并行化運(yùn)行于Hadoop集群上并取得了較好的實驗效果.

但是，McNeill等人的動態(tài)索引算法需要將基于屬性的索引鍵值預(yù)先固定順序，這個前提條件在通用知識庫上并不容易實現(xiàn).Lee等人針對這個問題提出了一種改進(jìn)的動態(tài)索引算法[17]，不需要預(yù)先確定知識庫索引鍵值的選擇順序，只是簡單地枚舉索引鍵值所有可能的組合，再逐步分塊得到所有合適大小的索引區(qū)塊.采用這種方法的原因有4點：1)選擇區(qū)分能力強(qiáng)的屬性很有可能由于表示方式或者錄入錯誤等原因?qū)е抡倩芈式档停覀儽仨氉畲蟪潭冉档瓦@種風(fēng)險；2)相同屬性在不同知識庫實例中的分辨能力不同，必須保證分區(qū)后2個知識庫中的區(qū)塊大小同時小于指定閾值；3)雖然枚舉所有組合可能導(dǎo)致大量的區(qū)塊產(chǎn)生，但由于每輪分區(qū)深度一般不會超過3層，所以所花費的計算代價并不大；4)這是最重要的一個原因，我們很難預(yù)先定義一個通用知識庫的索引鍵值選擇次序.算法過程簡要描述如下：算法首先將每個知識庫看作是一個大的分區(qū)；然后根據(jù)知識庫中先驗對齊的類別、實例和字面量構(gòu)建索引鍵值對，根據(jù)這些索引鍵值對遞歸地創(chuàng)建子分區(qū)，直到每個分區(qū)大小都小于指定閾值或者每對索引鍵值對都被使用后停止；最后算法將每次循環(huán)得到的分區(qū)并入候選對集合.在分區(qū)大小指定為一個較小的數(shù)值的情況下，每個分區(qū)內(nèi)實體相似性的計算代價可以看作常數(shù)時間，因此實體相似性的時間復(fù)雜度即為分區(qū)的個數(shù)，極大地減少了計算量，適合于大規(guī)模知識庫的實體對齊.

表4分類匯總了實體對齊中的分區(qū)索引算法:

Table 4　Classification Summary Tables of Blocking Algorithms in Entity Alignment

Continued (Table 4)

6常用測試數(shù)據(jù)集簡介

一般用于實體對齊算法效果評測的數(shù)據(jù)集可分為2類：1)實驗室中人工合成的專用評測數(shù)據(jù)集，我們稱為基準(zhǔn)測試數(shù)據(jù)集.這類數(shù)據(jù)集規(guī)模相對較小，結(jié)構(gòu)和內(nèi)容相對簡單，不能夠全面充分地測試算法的性能，但由于提供了匹配的標(biāo)準(zhǔn)結(jié)果，可以通過結(jié)果的比較從某一方面較為精確地反映算法的優(yōu)劣.這類數(shù)據(jù)集主要來自本體匹配工具評測平臺OAEI(ontology alignment evaluation initiative)*http:oaei.ontologymatching.org，具體測試數(shù)據(jù)集將在6.1節(jié)進(jìn)行介紹.2)各種機(jī)構(gòu)或組織根據(jù)實際需要通過各種數(shù)據(jù)采集手段從真實世界中抽取所需數(shù)據(jù)構(gòu)建的知識庫，將之用于對其算法評價，我們稱為真實世界測試數(shù)據(jù)集.這類數(shù)據(jù)集一般規(guī)模較大、結(jié)構(gòu)復(fù)雜多樣、匹配難度大，可以很好地對算法的效率和可擴(kuò)展性進(jìn)行充分的測試，但由于很難構(gòu)建標(biāo)準(zhǔn)結(jié)果，因此一般通過采樣或者人機(jī)結(jié)合的方式進(jìn)行結(jié)果準(zhǔn)確性的評測.這類數(shù)據(jù)集主要來自LOD項目[11]中的知識庫，常用的知識庫在6.2節(jié)進(jìn)行介紹.對這2類數(shù)據(jù)集的評測指標(biāo)主要采用1.2節(jié)介紹的precision、recall和F-measure，以及通過precision-recall曲線進(jìn)行可視化的結(jié)果展示.

6.1基準(zhǔn)測試數(shù)據(jù)集

OAEI是一個評測和比較本體匹配工具的國際比賽，從2009年開始增加了實例匹配的測試內(nèi)容，先后提供了6種實例對齊的測試數(shù)據(jù)集，這些數(shù)據(jù)集可以用于知識庫的實體對齊算法的評測，簡要介紹如下：

1) A-R-S測試數(shù)據(jù)集.其包括3個來源于文獻(xiàn)出版領(lǐng)域的數(shù)據(jù)集(eprints,rexa,Sweto-DBLP)，數(shù)據(jù)量從eprints的幾百個實例到rexa的1萬余個實例，再到Sweto-DBLP的160余萬個實例，變化幅度很大，可以很好地測試算法的擴(kuò)展性.

2) T-S-D測試數(shù)據(jù)集.其包括3個涵蓋多領(lǐng)域的根據(jù)不同結(jié)構(gòu)構(gòu)建的數(shù)據(jù)集(TAP,SwetoTestbed,DBpedia)，這3個數(shù)據(jù)集的數(shù)據(jù)量相對較大，主要評測的是算法的效率性能.

3) IIMB(Islab instance matching benchmark)測試數(shù)據(jù)集.其數(shù)據(jù)來自O(shè)KKAM項目，包含了關(guān)于演員、運(yùn)動員和企業(yè)公司的數(shù)據(jù).根據(jù)不同的修改策略，該測試集被劃分成 37 個子目錄，每個測試目錄含有約300個實例標(biāo)識符及 RDF 數(shù)據(jù)，這些修改后的RDF文檔需與一個原始的RDF文檔進(jìn)行匹配.由于提供了豐富的修改策略，這個測試集可以從不同方面較為全面地反映算法的性能，但受數(shù)據(jù)量的限制無法對算法效率和擴(kuò)展性進(jìn)行評測.

4) DI(data interlinking)測試數(shù)據(jù)集.它是一個規(guī)模較大的數(shù)據(jù)集，其提供的數(shù)據(jù)包主要包含了多個生物醫(yī)學(xué)領(lǐng)域的大型知識庫(dailymed,diseasome,drugbank,linkct,sider)和關(guān)于電影的大型本體知識庫 LinkedMDB，部分?jǐn)?shù)據(jù)集需要通過聯(lián)機(jī)查詢方式獲取.這個評測數(shù)據(jù)集的數(shù)據(jù)來自于真實世界的知識庫，數(shù)據(jù)量較大且結(jié)構(gòu)較為復(fù)雜，對算法提出了較高的要求.

5) PR(persons-restaurants)測試數(shù)據(jù)集.它是較為常用的作為初始效果評測的數(shù)據(jù)集，包含了人和餐館的信息的對齊，每個數(shù)據(jù)集包含數(shù)百個到幾千個實例，實例主要是屬性信息，可以通過根據(jù)某些修改策略(主要是添加或刪除一些屬性)對數(shù)據(jù)集作不同程度地改變來進(jìn)行算法的測試.這個測試集規(guī)模小、結(jié)構(gòu)簡單、測試能力有限.

6) NYT(interlinking New York Times data)測試數(shù)據(jù)集.它是一個規(guī)模較大的數(shù)據(jù)集，數(shù)據(jù)來源于紐約時報的開放鏈接數(shù)據(jù)，內(nèi)容包含人、組織和地點3個方面，可以用來與真實世界的知識庫進(jìn)行對齊進(jìn)而評測算法的對齊質(zhì)量.

6.2真實世界測試數(shù)據(jù)集

LOD項目將大量基于RDF知識庫中的數(shù)據(jù)集鏈接起來.到2014年，LOD項目已經(jīng)采集了超過1 000個知識庫的600億條RDF三元組.在LOD項目云圖中，處于核心地位的有3個知識庫：Freebase,DBpedia,YAGO.這3個知識庫與其他知識庫存在大量的鏈接關(guān)系，同時它們之間也標(biāo)注了很多的共指關(guān)系.可以說，這3個知識庫是實體對齊算法的優(yōu)秀評測數(shù)據(jù)集.

1) Freebase[88].它由數(shù)據(jù)庫技術(shù)公司Metaweb創(chuàng)建，后被谷歌收購，成為谷歌知識圖譜的重要組成部分.Freebase中的數(shù)據(jù)來自于維基百科、IMDB、Flickr等眾多網(wǎng)站或數(shù)據(jù)集，由計算機(jī)和人共同維護(hù)，經(jīng)過非常嚴(yán)格的處理過程進(jìn)行增加或修改.Freebase使用MQL(Metaweb query language)查詢語言向用戶提供了數(shù)據(jù)訪問接口.其類別層次結(jié)構(gòu)較為簡單，但事實條目數(shù)量巨大，數(shù)據(jù)質(zhì)量較高，至2014年Freebase已經(jīng)包含了超過24億條三元組信息.谷歌公司決定于2015年6月將Freebase全部移入WikiData*https:www.wikidata.orgwikiWikidata:Main_Page，并使用WikiData的API提供數(shù)據(jù)服務(wù).

2) DBpedia[89].它由德國萊比錫大學(xué)和曼海姆大學(xué)的科研人員創(chuàng)建的多語言的綜合型知識庫.DBpedia處于LOD項目的最核心地位，被廣泛應(yīng)用于各種科研的實際系統(tǒng).其數(shù)據(jù)的主要來源是多種語言的維基百科中抽取出的結(jié)構(gòu)化信息，包含了眾多領(lǐng)域的實體信息.與Freebase 類似，DBpedia的類別結(jié)構(gòu)并不復(fù)雜，但其實例的屬性較多，且事實三元組的數(shù)量同樣巨大，截止2014年DBpedia三元組的數(shù)量已經(jīng)超過了30億條.

3) YAGO[90-91].它是一個由德國馬普所(Max Planck Institute，MPI)的科研人員構(gòu)建的綜合型知識庫.YAGO知識庫將維基百科、WordNet和GeoNames等數(shù)據(jù)源的知識整合在知識庫中，特別是將維基百科的分類體系和WordNet的分類體系進(jìn)行融合，為YAGO構(gòu)建了一個復(fù)雜的類別層次結(jié)構(gòu)體系，其類別的數(shù)量超過36萬條，但其實體數(shù)量和事實三元組條目相對較少，目前YAGO2包含了1 000多萬實體的1.2億條三元組信息，最新版的YAGO3則提供了多語言的版本.

7機(jī)遇與挑戰(zhàn)

知識庫的實體對齊技術(shù)來源于傳統(tǒng)的實體匹配技術(shù)，也可以借助數(shù)據(jù)庫、機(jī)器學(xué)習(xí)和自然語言處理的一些方法，并結(jié)合了當(dāng)前基于語義網(wǎng)知識庫的特點，是一個綜合性的研究方向.關(guān)于知識庫對齊和本體匹配的相關(guān)工作也有很多綜述性的文章.文獻(xiàn)[92]從信息檢索和數(shù)據(jù)挖掘角度對基于本體的開放網(wǎng)絡(luò)知識庫的構(gòu)建、知識融合、知識檢索、數(shù)據(jù)挖掘和系統(tǒng)應(yīng)用進(jìn)行全面地綜述，有利于我們從全局角度把握知識庫實體對齊的重要作用.文獻(xiàn)[3]對2001—2011年期間基于本體匹配的技術(shù)變遷進(jìn)行了總結(jié)，并分類匯總了期間出現(xiàn)的各種匹配工具，雖然文獻(xiàn)[3]綜述的是本體的架構(gòu)的匹配工作，但其中很多技術(shù)和思想也可以用于本文探討的知識庫實體對齊，其介紹的部分工具也可以用于實體對齊.文獻(xiàn)[4]是另外一篇比較有影響力的討論本體匹配的綜述性文章，文中對本體匹配工作的現(xiàn)狀和發(fā)展趨勢進(jìn)行了討論，同樣介紹了相關(guān)的系統(tǒng)和測試集，重點對本體匹配工作面臨的8大挑戰(zhàn)給予詳細(xì)的闡述，對知識庫的實體對齊工作有很大的啟發(fā)意義.近幾年隨著知識庫的發(fā)展，也出現(xiàn)了一些關(guān)于知識庫實體對齊的綜述性文章.文獻(xiàn)[93]從機(jī)器學(xué)習(xí)的角度對知識庫的實體鏈接工作相關(guān)的問題、技術(shù)和解決方案進(jìn)行了匯總和分析.文獻(xiàn)[94]則是最新的一篇從文獻(xiàn)綜述的角度對本體匹配和知識庫實體對齊統(tǒng)一考慮的文章，該文對2003年以來這一領(lǐng)域相關(guān)文獻(xiàn)的發(fā)展變化情況進(jìn)行了深入的分析，對文獻(xiàn)中涉及的系統(tǒng)進(jìn)行了詳細(xì)的分類匯總，并且對文獻(xiàn)中關(guān)注的問題和挑戰(zhàn)進(jìn)行了總結(jié)，為這一方向的深入研究提供了詳盡的資料支持.

根據(jù)文獻(xiàn)調(diào)研[94]，知識庫實體對齊的研究工作興起于2003年，并于2011—2013年達(dá)到一個高峰，目前仍處于高速發(fā)展時期，各類方法層出不窮，尤其是結(jié)合大數(shù)據(jù)的相關(guān)技術(shù)，在大數(shù)據(jù)條件下的知識庫實體對齊的算法研究和系統(tǒng)構(gòu)建成為了當(dāng)下研究的熱點.知識庫實體對齊雖然取得了豐碩的研究成果，但仍有許多亟待解決的問題，概括起來有6方面：

1) 并行與分布式算法.大數(shù)據(jù)條件下的知識庫由于數(shù)據(jù)量巨大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜，對實體對齊算法的效率和擴(kuò)展性提出很多挑戰(zhàn).目前很多研究著力于使用主流的并行或分布式算法應(yīng)對這些挑戰(zhàn)[95-97]，這些工作將對齊工作運(yùn)行于分布式的計算平臺(多核或者多處理器)或者并行的編程環(huán)境(MPI，Map-Reduce或者基于內(nèi)存計算的Spark等)，將對齊算法的不同步驟并行化，充分考慮不同模塊的負(fù)載均衡和高效的消息傳遞機(jī)制，以期達(dá)到對齊效率和效果的大幅度提升.

2) 實時算法.目前大部分對齊的研究工作都是離線處理，在某些應(yīng)用場景下可能需要實時地處理實體對齊，因此需要高效的實時算法來解決這個問題.當(dāng)前已經(jīng)有部分的實時實體對齊的研究工作[98-100]，但大部分都是針對具體應(yīng)用領(lǐng)域，數(shù)據(jù)結(jié)構(gòu)相對簡單且數(shù)據(jù)量較小.大規(guī)模知識庫的實時對齊算法可以考慮將離線和在線算法更好地結(jié)合起來，還可以考慮預(yù)先建立索引及應(yīng)用分區(qū)剪枝技術(shù)有效地減少候選對，并在不影響匹配質(zhì)量的前提下有效地降低跨知識庫查詢的通信代價.

3) 眾包算法.人機(jī)結(jié)合的眾包算法可以有效地提高匹配質(zhì)量，提供豐富的先驗對齊數(shù)據(jù)，尤其在大數(shù)據(jù)條件下，設(shè)計高效的眾包算法，可以以較小的代價產(chǎn)生巨大的效果[101-104].眾包算法的設(shè)計主要是考慮數(shù)據(jù)量、對齊質(zhì)量以及人工標(biāo)注三者重要性的權(quán)衡，要將眾包平臺與對齊模型有機(jī)結(jié)合起來，同時要能夠有效地判別人工標(biāo)注的質(zhì)量，這些方面都有待進(jìn)一步研究.

4) 跨語言知識庫對齊.隨著LOD項目的發(fā)展，多語言知識庫越來越多，建立跨語言的知識庫的鏈接能夠極大地豐富LOD的覆蓋范圍，提高不同知識庫的互補(bǔ)能力.目前已經(jīng)有部分跨語言知識庫對齊的研究工作，取得了一定的進(jìn)展[105-106]，但對齊質(zhì)量不高，對齊效果還有待進(jìn)一步提升.

5) 測試數(shù)據(jù)集及評價.當(dāng)前知識庫對齊研究的一個主要問題就是缺少可供研究者測試和評價算法的統(tǒng)一的測試評價平臺和數(shù)據(jù)集.雖然OAEI正致力于這方面的建設(shè)工作，但其測試平臺數(shù)據(jù)集的全面性和評測能力并不足以覆蓋當(dāng)前對齊算法的多樣性，很多算法仍使用自己構(gòu)建的數(shù)據(jù)集進(jìn)行測試.因此，迫切需要建立一個全面地適用于LOD環(huán)境的測試評價平臺，能夠統(tǒng)一地評價對齊算法的綜合能力，同時需要更加全面合理的評價指標(biāo)體系.

6) 實用系統(tǒng)的研發(fā).現(xiàn)有的大部分實體對齊的研究還停留在實驗室或原型系統(tǒng)階段，無法在真實系統(tǒng)中獲得廣泛應(yīng)用.構(gòu)建一個穩(wěn)定的、易用的、可擴(kuò)展的、有效集成多種算法的、能夠完成多種對齊任務(wù)的系統(tǒng)是未來研究的一個重要方向.

8總結(jié)

本文在對知識庫實體對齊的相關(guān)概念、算法、技術(shù)和存在問題深入研究的基礎(chǔ)上，總結(jié)了3大類實體對齊算法以及基于相似性函數(shù)的特征匹配和分區(qū)索引2類技術(shù)，對常用的測試數(shù)據(jù)集進(jìn)行了介紹，并探討了知識庫實體對齊工作的機(jī)遇與挑戰(zhàn).基于語義網(wǎng)的知識庫對齊的研究工作既是近些年來一個新興的重要課題，又有許多現(xiàn)有相關(guān)領(lǐng)域的研究成果可供借鑒，目前正處于高速發(fā)展階段，取得了一定的成果，但仍有大量的問題亟待解決.隨著知識庫數(shù)量和數(shù)據(jù)規(guī)模的不斷增加，將會有越來越多的算法和系統(tǒng)涌現(xiàn)出來，將不同的知識庫鏈接起來，形成“知識之網(wǎng)”并推動Web不斷向前發(fā)展.

參考文獻(xiàn)

[1]Sheth A, Thirunarayan K. Semantics Empowered Web 3.0:Managing Enterprise, Social, Sensor, and Cloud-Based Data and Services for Advanced Applications[M]. San Rafael, CA: Morgan and Claypool, 2013

[2]Shvaiko P, Euzenat J. Ten Challenges for Ontology Matching[C]Proc of on the Move to Meaningful Internet Systems. Berlin: Springer, 2008: 1164-1182

[3]Bernstein P A, Madhavan J, Rahm E. Generic schema matching, ten years later[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 695-701

[4]Shvaiko P, Euzenat J. Ontology matching: State of the art and future challenges[J]. IEEE Trans on Knowledge & Data Engineering, 2013, 25(1): 158-176

[5]Bleiholder J, Naumann F. Data fusion[J]. ACM Computing Surveys, 2008, 41(1):137-153

[6]Elmagarmid A K, Ipeirotis P G, Verykios V S. Duplicate record detection: A survey[J]. IEEE Trans on Knowledge & Data Engineering, 2007, 19(1): 1-16

[7]Naumann F, Bilke A, Bleiholder J, et al. Data fusion in three steps: Resolving inconsistencies at schema-, tuple-, and value-level[J]. Bulletin of the Technical Committee on Data Engineering, 2006, 29(2): 21-31

[8]Wang H F. Survey: Computational models and technologies in anaphora resolution[J]. Journal of Chinese Information Processing, 2002, 16(6): 9-17

[9]Zhao J. A survey on named entity recognition, disam-biguation and cross-lingual coreference resolution[J]. Journal of Chinese Information Processing, 2009, 23(2): 4-17

[10]Hu Wei, Bai Wenyang, Qu Yuzhong. Research on resolving object coreference on the semantic Web[J]. Journal of Software, 2012, 23(7): 1729-1744 (in Chinese)(胡偉, 柏文陽, 瞿裕忠. 語義Web中對象共指的消解研究[J]. 軟件學(xué)報, 2012, 23(7): 1729-1744)

[11]Bizer C, Al E. Linked data-the story so far[J]. International Journal on Semantic Web & Information Systems, 2009, 5(3): 1-22

[12]Lacoste-Julien S, Palla K, Davies A, et al. SIGMa: Simple greedy matching for aligning large knowledge bases[C]Proc of the 2013 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 572-580

[13]Li Juanzi, Tang Jie, Yi Li, et al. RiMOM: A dynamic multistrategy ontology alignment framework[J]. IEEE Trans on Knowledge & Data Engineering, 2009, 21(8): 1218-1232

[14]Christen P, Goiser K. Quality and Complexity Measures for Data Linkage and Deduplication[M]. Berlin: Springer, 2007

[15]Witten I H. Managing Gigabytes[M]. San Francisco, CA: Morgan Kaufmann, 1999

[16]Naumann F. An Introduction to Duplicate Detection[M]. San Rafael, CA: Morgan and Claypool, 2010

[17]Lee S, Hwang S. ARIA: AsymmetRy resistant instance alignment[C]Proc of the National Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2014: 94-100

[18]Batini C, Scannapieco M. Data Quality: Concepts, Methodologies and Techniques[M]. Berlin: Springer, 2006

[19]Lee Y W, Pipino L L, Funk J D, et al. Journey to data quality[J]. Electronic Library, 2006, 25(6): 793-794

[20]Christen P. Data Matching[M]. Berlin: Springer, 2012

[21]Newcombe H B, Kennedy J M, Axford S J, et al. Automatic linkage of vital records[J]. Science, 1959, 130(3381): 954-959

[22]Fellegi I P, Sunter A B. A theory for record linkage[J]. Journal of the American Statistical Association, 1969, 64(328): 1183-1210

[23]Herzog T N, Scheuren F J, Winkler W E. Data Quality and Record Linkage Techniques[M]. Berlin: Springer, 2007

[24]Porter E H, Winkler W E, Census B O T, et al. Approximate string comparison and its effect on an advanced record linkage system, RR9702[R]. Washing DC: US Bureau of the Census, 1997: 190-199

[25]Winkler W E. String comparator metrics and enhanced decision rules in the Fellegi-Sunter model of record linkage[C]Proc of the Section on Survey Research Methods. Washington DC: ASA, 1990: 354-359

[26]Winkler W E, Thibaudeau Y. An application of the Fellegi-Sunter model of record linkage to the 1990 U.S. decennial census, RR9109[R]. Washington DC: US Bureau of the Census, 1991

[27]Winkler W E. Methods for record linkage and Bayesian networks, RRS200205[R]. Washington DC: US Bureau of the Census, 2001

[28]Verykios V S, Moustakides G V, Elfeky M G. A Bayesian decision model for cost optimal record matching[J]. VLDB Journal, 2003, 12(1): 28-40

[29]Han J W, Kambe M. Data Mining: Concepts and Techniques[M]. San Francisco, CA: Morgan Kaufmann, 2006

[30]Vapnik V. The Nature of Statistical Learning Theory[M]. Berlin: Springer, 2000

[31]Kantardzic M. Data Mining[M]. Hoboken, NJ: John Wiley & Sons, 2011: 235-248

[32]Cochinwala M, Kurien V, Lalk G, et al. Efficient data reconciliation[J]. Information Sciences, 2001, 137(14): 1-15

[33]Elfeky M G, Verykios V S, Elmagarmid A K. TAILOR: A record linkage toolbox[C]Proc of 2012 IEEE Int Conf on Data Engineering (ICDE 2012). Piscataway, NJ: IEEE, 2002: 17-28

[34]Christen P. Automatic training example selection for scalable unsupervised record linkage [G]LNAI 5012: Advances in Knowledge Discovery and Data Mining, 12th Pacific-Asia Conf. Berlin: Springer, 2008: 511-518

[35]Chen Z, Kalashnikov D V, Mehrotra S. Exploiting context analysis for combining multiple entity resolution systems[C]Proc of the 2009 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2009: 207-218

[36]Cohen W W, Richman J. Learning to match and cluster large high-dimensional data sets for data integration[C]Proc of the 2002 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 475-480

[37]McCallum A, Wellner B. Conditional models of identity uncertainty with application to noun coreference[C]Proc of Advances in Neural Information Processing Systems 17. Cambridge, MA: MIT Press, 2005: 905-912

[38]Pasula H, Marthi B, Milch B, et al. Identity uncertainty and citation matching[C]Proc of Advances in Neural Information Processing Systems 15. Cambridge, MA: MIT Press, 2003: 1425-1432

[39]Sarawagi S, Bhamidipaty A. Interactive deduplication using active learning[C]Proc of the 2002 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 269-278

[40]Tejada S, Knoblock C A, Minton S. Learning domain-independent string transformation weights for high accuracy object identification[C]Proc of the 2002 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 350-359

[41]Arasu A, G?tz M, Kaushik R. On active learning of record matching packages[C]Proc of the 2010 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2010: 783-794

[42]Verykios V S, Elmagarmid A K. Automating the approximate record matching process[J]. Information Sciences, 2000, 126(1): 83-98

[43]Ravikumar P, Cohen W. A hierarchical graphical model for record linkage[C]Proc of the 20th Conf in Uncertainty in Artificial Intelligence. Banff, Canada: AUAI, 2004: 454-461

[44]Bhattacharya I, Getoor L. A latent Dirichlet allocation model for unsupervised entity resolution[C]Proc of the 6th SIAM Int Conf on Data Mining. Philadelphia, PA SIAM, 2006: 47-58

[45]Li Juanzi, Wang Zhichun, Zhang Xiao, et al. Large scale instance matching via multiple indexes and candidate selection[J]. Knowledge-Based Systems, 2013, 50: 112-120

[46]Dong X. Reference reconciliation in complex information spaces[C]Proc of the 2005 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2005: 85-96

[47]Bhattacharya I, Getoor L. Collective entity resolution in relational data[J]. ACM Trans on Knowledge Discovery from Data, 2007, 1(2): 2007

[48]Tang Jie, Li Juanzi, Liang Bangyong, et al. Using Bayesian decision for ontology mapping[J]. Journal of Web Semantics, 2006, 4(4): 243-262

[49]Hall R, Sutton C, Mccallum A. Unsupervised deduplication using cross-field dependencies[C]Proc of the 2008 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 310-317

[50]Domingos P. Multi-relational record linkage[C]Proc of the KDD-2004 Workshop on Multi-Relational Data Mining. New York: ACM, 2004: 31-48

[51]Singla P, Domingos P. Entity resolution with Markov logic[C]Proc of 2006 IEEE Int Conf on Data Mining (ICDM 2006). Piscataway, NJ: IEEE, 2006: 572-582

[52]Rastogi V, Dalvi N, Garofalakis M. Large-scale collective entity matching[J]. Proceedings of the VLDB Endowment, 2011, 4(4): 208-218

[53]Suchanek F M, Abiteboul S, Senellart P. PARIS: Probabilistic alignment of relations, instances, and schema[J]. Proceedings of the VLDB Endowment. 2011, 5(3): 157-168

[54]Bansal N, Blum A, Chawla S. Correlation clustering[C]Proc of the 43rd Annual Symp on Foundations of Computer Science (FOCS 2002). Piscataway, NJ: IEEE, 2002: 238-247

[55]Collins M. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms[C]Proc of the Conf on Empirical Methods in Natural Language Processing. Stroudsburg, PA: ACL, 2002: 1-8

[56]Wick M, Singh S, Mccallum A. A discriminative hierarchical model for fast coreference at large scale[C]Proc of the 50th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2012: 379-388

[57]Xu Congfu, Hao Chunliang, Su Baojun, et al. Research on Markov logic networks[J]. Journal of Software, 2011, 22(8): 1699-1713 (in Chinese)(徐從富, 郝春亮, 蘇保君, 等. 馬爾可夫邏輯網(wǎng)絡(luò)研究[J]. 軟件學(xué)報, 2011, 22(8): 1699-1713)

[58]Kok S, Domingos P. Statistical predicate invention[C]Proc of the 24th Int Conf on Machine Learning. New York: ACM, 2007: 433-440

[59]Richardson M, Domingos P. Markov logic networks[J]. Machine Learning, 2006, 62(12):107-136

[60]Monge A E, Elkan C P. The field matching problem: Algorithms and applications[C]Proc of 1996 ACM SIGKDD Conf on Knowledge Discovery & Data Mining. New York: ACM, 1996: 267-270

[61]Navarro G. A guided tour to approximate string matching[J]. ACM Computing Surveys, 2001, 33(1): 31-88

[62]Smite T F, Waterman M S. Identification of common molecular subsequences[J]. Journal of Molecular Biology, 1981, 147(1): 195-197

[63]Waterman M S, Beyer T F S A. Some biological sequence metrics[J]. Advances in Mathematics, 1976, 20(3): 367-387

[64]Winkler W E. Overview of record linkage and current research directions, RRS 200602[R]. Washington DC: US Bureau of the Census, 2006

[65]Ananthakrishna R, Chaudhuri S, Ganti V. Eliminating fuzzy duplicates in data warehouses[C]Proc of the VLDB Endowment. New York: ACM, 2002: 586-597

[66]Naumann F, Weis M. DogmatiX tracks down duplicates in XML[C]Proc of the 2005 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2005: 431-442

[67]Cohen W W, Ravikumar P, Fienberg S E. A comparison of string distance metrics for name-matching tasks[C]Proc of the IJCAI-2003 Workshop on Information on the Web. San Francisco, CA: Morgan Kaufmann, 2003: 73-78

[68]Vazquez A. Growing networks with local rules: Preferential attachment, clustering hierarchy and degree correlations[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2003, 67(5): 369-384

[69]Lada A A, Eytan A. Friends and neighbors on the Web[J]. Social Networks, 2001, 25(3): 211-230

[70]Katz L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43

[71]Jeh G, Widom J. SimRank: A measure of structural-context similarity[C]Proc of the 2002 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 538-543

[72]Christen P. A survey of indexing techniques for scalable record linkage and deduplication[J]. IEEE Trans on Knowledge and Data Engineering, 2012, 24(9): 1537-1555

[73]Hernandez M, Hern’Andez M A, Stolfo S. The mergepurge problem for large databases[C]Proc of 1995 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1995: 127-138

[74]Christen P. Towards parameter-free blocking for scalable record linkage[R]. Canberra, Australia: Australian National University, 2007

[75]Yan S, Lee D, Kan M Y, et al. Adaptive sorted neighborhood methods for efficient record linkage[C]Proc of Int Conf on Digital Libraries. New York: ACM, 2007: 185-194

[76]Draisbach U, Naumann F. A generalization of blocking and windowing algorithms for duplicate detection[C]Proc of 2011 Int Conf on Data and Knowledge Engineering (ICDKE 2011). Piscataway, NJ: IEEE, 2011: 18-24

[77]Baxter R, Christen P. A comparison of fast blocking methods for record Linkage[C]Proc of ACM SIGKDD Workshop on Data Cleaning, Record Linkage and Object Consolidation. New York: ACM, 2003: 25-27

[78]Aizawa A, Oyama K. A fast Linkage detection scheme for multi-source information integration[C]Proc of Int Workshop Challenges in Web Information Retrieval and Integration. Piscataway, NJ: IEEE, 2005: 30-39

[79]Broder A Z. On the resemblance and containment of documents[C]Proc of the Int Conf on Compression and Complexity of Sequences. Piscataway, NJ: IEEE, 1997: 21-29

[80]Kim H, Lee D. Harra: Fast iterative hashed record linkage for large-scale data collections[C]Proc of the 2000 ACM SIGKDD Conf on Int Conf on Extending Database Technology. New York: ACM, 2010: 525-536

[81]Mccallum A, Nigam K, Ungar L H. Efficient clustering of high-dimensional data sets with application to reference matching[C]Proc of the 2000 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2000: 169-178

[82]Christen P. Development and user experiences of an open source data cleaning, deduplication and record linkage system[J]. ACM SIGKDD Explorations Newsletter, 2009, 11(11): 39-48

[83]Liang J, Chen L, Mehrotra S. Efficient record linkage in large data sets[C]Proc of the 8th Int Conf on Database Systems for Advanced Applications. Piscataway, NJ: IEEE, 2003: 137-146

[84]Noha A. Efficient record linkage using a double embedding scheme[C]Proc of 2009 IEEE Int Conf on Data Mining (ICDM 2009). Piscataway, NJ: IEEE, 2009: 274-281

[85]Aggarwal C C, Yu P S. The IGrid index: Reversing the dimensionality curse for similarity indexing in high dimensional space[C]Proc of the 2000 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2000: 119-129

[86]Borthwick A, Goldberg A, Cheung P, et al. Batch automated blocking and record matching: US, US 7899796 B1[P]. 2011-03-01

[87]Mcneill W P, Kardes H, Borthwick A. Dynamic record blocking: Efficient linking of massive databases in MapReduce[C]Proc of 2012 Int Workshop on Quality in DataBases. New York: ACM, 2012: 1-7

[88]Bollacker K, Cook R, Tufts P. Freebase: A shared database of structured general human knowledge[C]Proc of the 22nd AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2007: 1962-1963

[89]Bizer C, Lehmann J, Kobilarov G, et al. DBpedia—A crystallization point for the Web of data[J]. Web Semantics Science Services & Agents on the World Wide Web, 2009, 7(3): 154-165

[90]Suchanek F M, Kasneci G, Weikum G. YAGO: A core of semantic knowledge[C]Proc of the 2007 Int Conf on World Wide Web. Berlin: Springer, 2007: 697-706

[91]Suchanek F M, Kasneci G, Weikum G. YAGO: A large ontology from wikipedia and wordnet[J]. Web Semantics Science Services & Agents on the World Wide Web, 2007, 6(3): 203-217

[92]Wang Yuanzhuo, Jia Yantao, Liu Dawei, et al. Open Web knowledge aided information search and data mining[J]. Journal of Computer Research and Development, 2015, 52(2): 456-474 (in Chinese)(王元卓, 賈巖濤, 劉大偉, 等. 基于開放網(wǎng)絡(luò)知識的信息檢索與數(shù)據(jù)挖掘[J]. 計算機(jī)研究與發(fā)展, 2015, 52(2):456-474)

[93]Shen Wei, Wang Jianyong, Han Jiawei. Entity Linking with a knowledge base: Issues, techniques, and solutions[J]. IEEE Trans on Knowledge & Data Engineering, 2015, 27(2): 443-460.

[94]Otero-Cerdeira L, Rodríguez-Martínez F J, Gómez-Rodríguez A. Ontology matching: A literature review[J]. Expert Systems with Applications, 2015, 42(2): 949-971

[95]Kirsten T, Kolb L, Hartung M, et al. Data partitioning for parallel entity matching[J]. Proceedings of the VLDB Endowment, 2010, 3(2): 1-8

[96]Dal Bianco G, Galante R, Heuser C A. A fast approach for parallel deduplication on multicore processors[C]Proc of 2011 ACM Symp on Applied Computing. New York: ACM, 2011: 1027-1032

[97]Kim H, Lee D. Parallel linkage[C]Proc of the 2007 ACM Int Conf on Information and Knowledge Management. New York: ACM, 2007: 283-292

[98]Bhattacharya I, Getoor L. Query-time entity resolution[C]Proc of the 2006 ACM SIGKDD Conf on Knowledge Discovery and Data Mining. New York: ACM, 2006: 529-534

[99]Christen P, Gayler R. Towards scalable real-time entity resolution using a similarity-aware inverted index approach[C]Proc of the 7th Australasian Data Mining Conf. Sydney, NSW, Australia: Australian Computer Society, 2008: 51-60

[100]Christen P, Gayler R, Hawking D. Similarity-aware indexing for real-time entity resolution[C]Proc of the 2009 ACM Int Conf on Information and Knowledge Management. New York: ACM, 2009: 1565-1568

[101]Wang J, Kraska T, Franklin M J, et al. CrowdER: Crowdsourcing entity resolution[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1483-1494

[102]Vesdapunt N, Bellare K, Dalvi N. Crowdsourcing algorithms for entity resolution[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1071-1082

[103]Demartini G, Difallah D E, Cudré-Mauroux P. Large-scale linked data integration using probabilistic reasoning and crowdsourcing[J]. VLDB Journal, 2013, 22(5): 665-687

[104]Demartini G, Difallah D E, Cudré-Mauroux P. ZenCrowd: Leveraging probabilistic reasoning and crowdsourcing techniques for large-scale entity linking[C]Proc of the 2012 Int Conf on World Wide Web. New York: ACM, 2012: 469-478

[105]Wang Z, Li J, Wang Z, et al. Cross-lingual knowledge linking across wiki knowledge bases[C]Proc of the 2012 Int Conf on World Wide Web. New York: ACM, 2012: 459-468

[106]Wang Z, Li J, Tang J. Boosting cross-lingual knowledge linking via concept annotation[C]Proc of the 23rd Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2013: 2733-2739

Zhuang Yan, born in 1979. PhD candidate. His main research interests include knowledge base, database, and data cleaning and integration.

Li Guoliang, born in 1980. Associate professor in Tsinghua University. His main research interests include large-scale data management, knowledge base, and crowd computing.

Feng Jianhua, born in 1967. Professor in Tsinghua University. His main research interests include big data, privacy, and knowledge base.

中圖法分類號TP311.13; TP182

基金項目：國家自然科學(xué)基金優(yōu)秀青年科學(xué)基金項目(61422205)；國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2015CB358700)

收稿日期：2015-07-15；修回日期：2015-10-16

This work was supported by the National Natural Science Foundation for Excellent Young Scholars of China (61422205) and the National Basic Research Program of China (973 Program) (2015CB358700).