范威振，陳占芳，劉燕龍

（長春理工大學(xué) 計算機科學(xué)技術(shù)學(xué)院，長春 130022）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 相似度度量方法

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

2.1 屬性相似度度量

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

2.2 上下文相似度度量

為了更加全面的衡量兩個簇的相似程度，在使用屬性相似度的基礎(chǔ)上，還要考慮簇中表象對的上下文相似度。

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

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

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

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

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

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

對于無向圖G(V,E)而言，V(G)指G中所有頂點的集合，E(G)指G中所有邊的集合，size(V(G))指G中頂點的個數(shù)，size(E(Vi))指經(jīng)過Vi的所有邊的個數(shù)。

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

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

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

圖4 完全圖和相似完全圖

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

例如對于圖4（a）而言，其本身為1-相似團圖，圖4（b）為其0.7-相似團圖。

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

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

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

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

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

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

表3 實驗環(huán)境表

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

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

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

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

3.2 評價標準

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

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

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

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

3.3 實驗結(jié)果分析

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

將實驗的結(jié)果，按照上文的評價標準可求得每組實驗的Precision、Recall和F1，匯總后如圖5所示。

圖5 實驗的結(jié)果對比圖

由圖5可知：

（1）對三個數(shù)據(jù)集來說，Attr+Con+Rela組實體統(tǒng)一實驗效果最好，整體性能最高。

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

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

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

4 總結(jié)

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