基于多維相似度的整體式實(shí)體統(tǒng)一算法研究

范威振，陳占芳，劉燕龍

（長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長(zhǎng)春 130022）

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，信息數(shù)據(jù)逐漸呈現(xiàn)海量性、多源性、異構(gòu)性的趨勢(shì)。如何高效的整合信息數(shù)據(jù)為數(shù)據(jù)挖掘和數(shù)據(jù)分析提供基礎(chǔ)服務(wù)，是當(dāng)前研究的熱點(diǎn)［1-4］。多源異構(gòu)數(shù)據(jù)在集成的過(guò)程中，通常會(huì)出現(xiàn)一個(gè)現(xiàn)實(shí)世界實(shí)體（Entity）對(duì)應(yīng)多個(gè)表象（Reference）的現(xiàn)象，導(dǎo)致這種現(xiàn)象發(fā)生的原因可能是：拼寫錯(cuò)誤、命名規(guī)則不同、名稱變體、縮寫等等。而這種現(xiàn)象會(huì)導(dǎo)致集成后的數(shù)據(jù)存在大量冗余數(shù)據(jù)、不一致數(shù)據(jù)等問(wèn)題，從而降低了集成后數(shù)據(jù)的質(zhì)量，進(jìn)而影響了基于集成后的數(shù)據(jù)做分析挖掘的結(jié)果。分辨多個(gè)實(shí)體表象是否對(duì)應(yīng)同一個(gè)實(shí)體的問(wèn)題即為實(shí)體統(tǒng)一［5］。

實(shí)體統(tǒng)一的傳統(tǒng)做法通常是采用基于屬性特征的相關(guān)方法，這類方法旨在通過(guò)比較預(yù)設(shè)的相似度閾值與數(shù)據(jù)實(shí)體表象對(duì)應(yīng)的各個(gè)屬性特征的相似度數(shù)值，從而判斷不同的表象是否對(duì)應(yīng)同一實(shí)體。針對(duì)那些屬性特征完整、數(shù)據(jù)結(jié)構(gòu)統(tǒng)一的結(jié)構(gòu)化數(shù)據(jù)，這類傳統(tǒng)方法具有較好的度量效果。但在Web環(huán)境下，不同的數(shù)據(jù)源對(duì)相同的實(shí)體的描述不相同，普遍存在屬性特征不完整的情況，數(shù)據(jù)結(jié)構(gòu)也更多的呈現(xiàn)半結(jié)構(gòu)化或非結(jié)構(gòu)化，因此只通過(guò)屬性相似度無(wú)法準(zhǔn)確的完成實(shí)體統(tǒng)一。

比如從兩個(gè)系統(tǒng)中獲取到的兩條高校信息，如圖1所示，因?yàn)橄到y(tǒng)是在不同的年代由不同的公司開發(fā)的，其命名習(xí)慣、對(duì)實(shí)體的描述方式均不相同，屬性在很大程度上并不完整。因此，在這種情況下，判斷兩條數(shù)據(jù)是否指向同一個(gè)高校就不能只通過(guò)屬性相似度。

圖1 來(lái)自不同數(shù)據(jù)源的兩條高校信息

圖2 高校與學(xué)生數(shù)據(jù)之間的關(guān)聯(lián)

再比如說(shuō)在文學(xué)領(lǐng)域，常常會(huì)出現(xiàn)“多人重名”的情況，特別是中文名字翻譯成英文時(shí)，“重名”現(xiàn)象就更嚴(yán)重。此時(shí)，使用“姓名”這個(gè)屬性的相似度來(lái)判斷多個(gè)表象是否對(duì)應(yīng)同一個(gè)作者就不具有說(shuō)服性，而且實(shí)體統(tǒng)一的效果也不會(huì)很好。

以上的兩個(gè)例子，都說(shuō)明只使用屬性相似度已經(jīng)無(wú)法準(zhǔn)確的判斷多個(gè)實(shí)體表象是否對(duì)應(yīng)同一個(gè)實(shí)體。因此，必須挖掘?qū)嶓w表象內(nèi)部以及實(shí)體表象之間的關(guān)聯(lián)和相關(guān)信息。

例如在高校數(shù)據(jù)實(shí)體統(tǒng)一時(shí)，不但獲取到了高校的基本信息，而且還可以獲取到與高校相關(guān)的其他信息，如學(xué)生信息、教職工信息等。這些“上下文”信息同樣可以作為實(shí)體統(tǒng)一過(guò)程中的重要參考依據(jù)，如圖2所示。

再比如在社會(huì)關(guān)系網(wǎng)中，人們時(shí)常交往的對(duì)象總是志趣相投的；在研發(fā)領(lǐng)域，一個(gè)較為成熟的軟件團(tuán)隊(duì)通常會(huì)研發(fā)出高質(zhì)量的產(chǎn)品；在文學(xué)領(lǐng)域，興趣相投的學(xué)者可能會(huì)有所合作。這些“關(guān)系”信息對(duì)實(shí)體統(tǒng)一的過(guò)程也起到非常關(guān)鍵的作用。

1 實(shí)體統(tǒng)一算法

為了彌補(bǔ)傳統(tǒng)的實(shí)體統(tǒng)一算法存在的缺陷，本文采用了一種基于多維相似度的整體式實(shí)體統(tǒng)一算法。

本文采用一種基于圖的迭代聚類算法，來(lái)解決實(shí)體統(tǒng)一的問(wèn)題，算法用圖來(lái)表現(xiàn)各個(gè)表象之間的關(guān)聯(lián)，每個(gè)實(shí)體表象都看做是一個(gè)簇（Cluster）。算法的準(zhǔn)備階段需要完成兩項(xiàng)任務(wù)：一、確定一個(gè)較大的相似度閾值；二、計(jì)算各簇之間的相似度，并將結(jié)果放入優(yōu)先隊(duì)列Q中。算法在循環(huán)進(jìn)行實(shí)體統(tǒng)一時(shí)主要完成的任務(wù)是：在現(xiàn)有的匹配對(duì)中以相似度為依據(jù)找出最大的那組，如果該匹配對(duì)的相似度不大于預(yù)先設(shè)定的閾值，則算法結(jié)束，即實(shí)體統(tǒng)一工作完成，否則，將這個(gè)匹配對(duì)進(jìn)行合并，形成一個(gè)新的簇，并更新與合并前的簇相關(guān)的其他簇的相似度，同時(shí)將隊(duì)列Q中的數(shù)據(jù)進(jìn)行更新。算法結(jié)束時(shí)，每個(gè)簇都是一個(gè)實(shí)體，簇內(nèi)的表象均對(duì)應(yīng)該實(shí)體。算法的流程圖如圖3所示。

圖3 基于圖的迭代聚類算法流程圖

本文采用的算法與傳統(tǒng)實(shí)體統(tǒng)一算法的對(duì)比如表1所示。

表1 傳統(tǒng)實(shí)體統(tǒng)一算法與本文采用的算法對(duì)比表

本文采用的算法綜合使用多種相似度的度量，實(shí)體統(tǒng)一的過(guò)程是各匹配對(duì)彼此影響、循環(huán)往復(fù)不斷迭代的整體式的過(guò)程，因此將這種算法稱為基于多維相似度的整體式實(shí)體統(tǒng)一算法。基于多維相似度的整體式實(shí)體統(tǒng)一算法的詳細(xì)描述如表2所示。

表2 基于多維相似度的整體式實(shí)體統(tǒng)一算法

該算法的輸入是原始表象集S，預(yù)設(shè)較大的閾值γ，算法的輸出是統(tǒng)一后的簇集合C，其中每個(gè)簇都是一個(gè)實(shí)體，簇內(nèi)的表象均對(duì)應(yīng)該實(shí)體。

算法在第1行初始化了一個(gè)簇集合C和一個(gè)優(yōu)先隊(duì)列Q，集合中存儲(chǔ)的是未進(jìn)行實(shí)體統(tǒng)一的實(shí)體表象，即每個(gè)實(shí)體表象都被看做是一個(gè)簇；隊(duì)列Q用來(lái)存放匹配對(duì)。

算法的準(zhǔn)備工作在2-4行進(jìn)行，此時(shí)將集合C中的簇兩兩組合，形成一組，計(jì)算每組簇的相似度，并將該組的信息存入優(yōu)先隊(duì)列中。

算法的循環(huán)匹配的工作從第5行開始，循環(huán)體里完成的工作如下：

（1）算法的第6行，在隊(duì)列Q中以相似度為依據(jù)找出最大的那組。

（2）算法的第7行，判斷獲取到的最大的這個(gè)相似度是否大于算法輸入時(shí)預(yù)設(shè)的閥值γ，如果不大于，則循環(huán)結(jié)束，即實(shí)體統(tǒng)一過(guò)程完成；否則，進(jìn)行下面的步驟。

（3）算法的第8行，合并獲取到的該簇對(duì)。

（4）算法的第9行，更新簇集合C；算法的第10-14行，更新與相似度最大的簇對(duì)有關(guān)的簇；算法的15-19行，更新相似度最大的簇對(duì)的“鄰居”簇；

算法在第21行返回實(shí)體統(tǒng)一后的簇集合C，集合中的每個(gè)簇都是一個(gè)實(shí)體，簇內(nèi)的表象均對(duì)應(yīng)該實(shí)體。

2 相似度度量方法

由上文的介紹可知，只使用屬性相似度存在許多的不足，本節(jié)將詳細(xì)的介紹本方法中綜合使用的三種相似度度量方法。

2.1 屬性相似度度量

基于屬性的相似度作為實(shí)體統(tǒng)一過(guò)程中較為常用的參考依據(jù)，有關(guān)學(xué)者已做出了較深入的探索，已經(jīng)研究出了許多精確而有效的相似度度量方式，如基于文本字符的實(shí)體統(tǒng)一方式、基于標(biāo)記的實(shí)體統(tǒng)一方式、基于發(fā)音與語(yǔ)法規(guī)則的統(tǒng)一方式等等［6-8］。

2.2 上下文相似度度量

為了更加全面的衡量?jī)蓚€(gè)簇的相似程度，在使用屬性相似度的基礎(chǔ)上，還要考慮簇中表象對(duì)的上下文相似度。

在不同的環(huán)境下，實(shí)體表象的上下文有很大差異。如在文獻(xiàn)領(lǐng)域，針對(duì)作者這一表象，作者的合作者是其重要的上下文，隨著表象對(duì)間的合作者相同的個(gè)數(shù)增加，該表象對(duì)對(duì)應(yīng)一個(gè)實(shí)體的概率也在不斷的增加。

由此發(fā)現(xiàn)：在度量表象對(duì)上下文的相似度時(shí)，只需利用表象對(duì)的上下文進(jìn)行相應(yīng)的屬性相似度的運(yùn)算即可，不需要對(duì)兩個(gè)實(shí)體表象的上下文進(jìn)行限制，即兩個(gè)實(shí)體表象的上下文屬性不需要“一一對(duì)應(yīng)”。

2.3 關(guān)系相似度度量

在現(xiàn)實(shí)應(yīng)用的過(guò)程中，實(shí)體表象之間的關(guān)聯(lián)很復(fù)雜。比如在社會(huì)關(guān)系網(wǎng)中，人們時(shí)常交往的對(duì)象總是志趣相投的；在研發(fā)領(lǐng)域，一個(gè)較為成熟的軟件團(tuán)隊(duì)通常會(huì)研發(fā)出高質(zhì)量的產(chǎn)品；在文學(xué)領(lǐng)域，興趣相投的學(xué)者可能會(huì)有所合作。

實(shí)體表象之間的這種共現(xiàn)關(guān)系，暗含了“團(tuán)體”的存在，在很大程度上可以輔助判斷實(shí)體表象的同指關(guān)系，即有利于分辨多個(gè)表象是不是對(duì)應(yīng)同一個(gè)實(shí)體。因此，具有關(guān)聯(lián)性的實(shí)體表象之間連接的緊密程度，將是判斷多個(gè)實(shí)體表象是否指向同一實(shí)體的重要信息，本文中表象對(duì)間的關(guān)系相似度可通過(guò)計(jì)算具有關(guān)聯(lián)性的實(shí)體表象之間連接的緊密程度來(lái)衡量。

為了挖掘?qū)嶓w表象之間隱藏的這種“團(tuán)體”特征，可以通過(guò)引入“相似團(tuán)”（Quasi-Clique）這種數(shù)據(jù)結(jié)構(gòu)來(lái)輔助操作。下面給出相關(guān)的定義。

對(duì)于無(wú)向圖G(V,E)而言，V(G)指G中所有頂點(diǎn)的集合，E(G)指G中所有邊的集合，size(V(G))指G中頂點(diǎn)的個(gè)數(shù)，size(E(Vi))指經(jīng)過(guò)Vi的所有邊的個(gè)數(shù)。

如果圖G中任一頂點(diǎn)起碼有γ(size(V(G))-1)個(gè)邊，即

則稱圖G為γ-相似完全圖，其中0≤γ≤1。

例如圖4（a）為1-相似完全圖，即完全圖，圖4（b）為0.7-相似完全圖。

圖4 完全圖和相似完全圖

對(duì)于G的子圖S而言，如果子圖S符合γ-相似完全圖的定義，則稱S為G的γ-相似團(tuán)圖（γ-Quasi-Clique）。其中，V(S)?V(G)、E(S)?E(G)。很顯然1-相似團(tuán)圖是完全圖，即為團(tuán)。

例如對(duì)于圖4（a）而言，其本身為1-相似團(tuán)圖，圖4（b）為其0.7-相似團(tuán)圖。

根據(jù)上面的定義，不難發(fā)現(xiàn)γ-相似團(tuán)具有一個(gè)非常好的特質(zhì)：圖的連接緊密程度與γ值的大小成正比。即當(dāng)γ的值越大時(shí)，圖中邊也就越多，圖中頂點(diǎn)間連接緊密的程度越高；反之，當(dāng)γ的值越小時(shí)，圖中邊的個(gè)數(shù)就越少，圖中頂點(diǎn)間的連接緊密程度越低。本文通過(guò)對(duì)“相似團(tuán)”的挖掘，來(lái)研究實(shí)體表象之間隱藏的“團(tuán)體”特征；用γ的值來(lái)度量“團(tuán)體”中實(shí)體表象之間的連接緊密程度，即實(shí)體表象之間的關(guān)系相似度。

基于上文的分析，(ca,cb)間關(guān)系相似度的度量過(guò)程是：第一步，用(ca,cb)的鄰接關(guān)系抽象出實(shí)體表象的關(guān)系圖G；第二步，在已有的關(guān)系圖中用相似團(tuán)挖掘算法找出γ較大的相似團(tuán)圖S；此時(shí)(ca,cb)間的關(guān)系相似度simrelationship(ca,cb)定義如下：

其中，γ代表了相似團(tuán)圖中頂點(diǎn)的連接緊密程度，size(V(S))表示相似團(tuán)圖S中頂點(diǎn)的個(gè)數(shù)，size(V(G))表示類(ca,cb)間公共頂點(diǎn)的個(gè)數(shù)。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文實(shí)驗(yàn)環(huán)境如表3所示。

表3 實(shí)驗(yàn)環(huán)境表

本文所采用的算法適用于多種復(fù)雜的場(chǎng)景，此處選擇對(duì)文獻(xiàn)信息進(jìn)行實(shí)驗(yàn)來(lái)研究算法的性能。數(shù)據(jù)集使用Patrick Reuther整理的DBLP數(shù)據(jù)集，該數(shù)據(jù)集是已經(jīng)標(biāo)注了統(tǒng)一后真實(shí)情況的部分DBLP網(wǎng)站上的文獻(xiàn)信息?？梢岳眠@些已經(jīng)處理后的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)來(lái)研究本文采用算法的準(zhǔn)確性和效率。

DBLP數(shù)據(jù)集是以XML的形式存在的，其信息描述格式如下：

實(shí)驗(yàn)使用了三個(gè)DBLP的數(shù)據(jù)集，其基本情況如表4所示。

表4 實(shí)驗(yàn)使用數(shù)據(jù)集的描述表

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

通過(guò)上文的描述可知，本文所用算法的輸出結(jié)果是實(shí)體統(tǒng)一后的簇集合C，其中每個(gè)簇表示一個(gè)實(shí)體，簇中的元素為指向該實(shí)體的表象。為了更好的評(píng)價(jià)算法的準(zhǔn)確性和性能，可以將算法的輸出結(jié)果分為Set1,Set2,Set3,Set4四個(gè)集合，各集合意義如表5所示。

表5 算法輸出結(jié)果分類意義表

用Size(Seti)表示第i個(gè)集合內(nèi)元素的個(gè)數(shù)，則可以定義查準(zhǔn)率（Precision）、查全率（Recall）和F1：

其中，Precision表示在實(shí)驗(yàn)的所有結(jié)果中，實(shí)體統(tǒng)一正確的簇所占的比例，該比例反應(yīng)了實(shí)體統(tǒng)一的正確與否，即為查準(zhǔn)率；Recall表示實(shí)驗(yàn)的結(jié)果中，實(shí)體統(tǒng)一正確的簇在真實(shí)的簇中占到的比例，該比例反應(yīng)了實(shí)體統(tǒng)一的覆蓋程度，即為查全率；F1作為實(shí)體統(tǒng)一的綜合評(píng)價(jià)指標(biāo)。

3.3 實(shí)驗(yàn)結(jié)果分析

為了清晰的比較算法在三種相似度上的差異，針對(duì)每個(gè)數(shù)據(jù)集都進(jìn)行了三組實(shí)驗(yàn)：只使用屬性相似度(Attr)、使用屬性相似度和上下文相似度（Attr+Con）、三種相似度都使用（Attr+Con+Rela）。

將實(shí)驗(yàn)的結(jié)果，按照上文的評(píng)價(jià)標(biāo)準(zhǔn)可求得每組實(shí)驗(yàn)的Precision、Recall和F1，匯總后如圖5所示。

圖5 實(shí)驗(yàn)的結(jié)果對(duì)比圖

由圖5可知：

（1）對(duì)三個(gè)數(shù)據(jù)集來(lái)說(shuō)，Attr+Con+Rela組實(shí)體統(tǒng)一實(shí)驗(yàn)效果最好，整體性能最高。

（2）對(duì)于DataSet1上的三組實(shí)驗(yàn)結(jié)果，就準(zhǔn)確性進(jìn)行比較：Attr＜Attr+Con，Attr+Con＜Attr+Con+Rela；就 Recall和F1進(jìn)行比較是 Attr＞Attr+Con，Attr＜Attr+Con+Rela。

對(duì)于（1），證明綜合使用三種相似度，實(shí)驗(yàn)結(jié)果的整體性能得到了提升；對(duì)于（2），說(shuō)明相比于只使用屬性相似度而言，在綜合使用屬性相似度和上下文相似度時(shí)，算法的準(zhǔn)確性雖然得以提升，但如果數(shù)據(jù)之間存在一定的“自反性”，那么在一定程度上會(huì)干擾算法的判斷，從而影響算法的性能。

因此，可以得出結(jié)論：相比于只使用單一的屬性相似度，使用多種相似度可有效的提供實(shí)體統(tǒng)一的效果。

4 總結(jié)

針對(duì)傳統(tǒng)實(shí)體統(tǒng)一算法存在的弊端，本文采用了一種基于多維相似度的整體式實(shí)體統(tǒng)一算法。采用了一種基于圖的迭代聚類的整體式實(shí)體統(tǒng)一算法，綜合使用了屬性、“上下文”、“關(guān)系”等信息來(lái)進(jìn)行了相似度的度量，實(shí)體統(tǒng)一算法是各匹配對(duì)彼此影響、循環(huán)往復(fù)不斷迭代的整體式的過(guò)程。最后在多個(gè)數(shù)據(jù)集上進(jìn)行多組實(shí)驗(yàn)進(jìn)行對(duì)比，測(cè)試算法在實(shí)體統(tǒng)一方面的性能。