冉德彤，游宏梁

（中國(guó)國(guó)防科技信息中心北京1001421）

實(shí)體分辨（Entity Resolution）中，記錄比較的準(zhǔn)確性直接影響能否準(zhǔn)確、完整地識(shí)別相似重復(fù)記錄，如何得到更為準(zhǔn)確的記錄比較結(jié)果一直是相關(guān)領(lǐng)域的研究熱點(diǎn)[1-2]。

傳統(tǒng)的記錄比較方法又被稱為基于特征的方法（Feature-Based Similarity methods，F(xiàn)BS methods）[3-4]，該方法將記錄看作屬性的集合，逐屬性地進(jìn)行比較，以得到記錄對(duì)的相似度向量[5-6]。有研究表明，F(xiàn)BS方法中的相似度算法一般存在適用范圍[7]，而選擇最合適的算法又是NP難問題[8]，故準(zhǔn)確相似度的獲取成為了一個(gè)難題。

針對(duì)該問題，文獻(xiàn)[8]提出了依據(jù)訓(xùn)練數(shù)據(jù)選擇最優(yōu)算法的方法，但該方法依賴訓(xùn)練數(shù)據(jù)，在實(shí)際應(yīng)用中獲取難度較大。文獻(xiàn)[9]提出了相似度調(diào)整的算法，利用數(shù)據(jù)集中的函數(shù)依賴關(guān)系調(diào)整相似度，以提高結(jié)果的準(zhǔn)確性。然而，該算法以標(biāo)準(zhǔn)的函數(shù)依賴為基礎(chǔ)，所能表達(dá)的約束條件有限，當(dāng)數(shù)據(jù)集中的約束超出其表達(dá)范圍時(shí)無法進(jìn)行調(diào)整。

針對(duì)記錄比較的準(zhǔn)確性問題，本文利用數(shù)據(jù)集中的條件函數(shù)依賴（Conditional Functional Dependencies，CFDs）關(guān)系，提出了一種基于數(shù)據(jù)一致性的記錄比較方法（Consistence-Based Similarity method，CBS方法）。介紹了條件函數(shù)依賴的概念，所提方法的總體思想及關(guān)鍵步驟，并給出了實(shí)驗(yàn)過程和結(jié)果。

1 CFDs的基本概念

條件函數(shù)依賴是函數(shù)依賴的擴(kuò)展，可表達(dá)更為具體的約束關(guān)系，是數(shù)據(jù)一致性研究中的一個(gè)重要概念[10-12]。下面介紹其定義。

定義1條件函數(shù)依賴的符號(hào)表示（CFDs Syntax）[13]。對(duì)于關(guān)系模式R，R上的一個(gè)條件函數(shù)依賴可記作φ:(R:X→Y,Tp），其中，1）用attr(R)表示R的屬性集合，X,Y∈attr(R)；2）R:X→Y表示一個(gè)標(biāo)準(zhǔn)的函數(shù)依賴；3）Tp是X、Y間的模式組（pattern tableau），由若干條模式元組tp構(gòu)成，?A∈X?Y，tp[A]定義了屬性A的取值，既可以是A定義域中的某個(gè)常數(shù)a，也可以定義域中的任意值（用"_"表示）。

根據(jù)定義1，標(biāo)準(zhǔn)的函數(shù)依賴可看作CFDs的一個(gè)特例。此外，對(duì)屬性值有限制的約束也可用CFDs表達(dá)。

定義2條件函數(shù)依賴的語義（CFDs Semantics）[13]。給定一個(gè)CFD：φ:(R:X→Y,tp），若實(shí)例I中任意兩個(gè)數(shù)據(jù)元組t1，t2都滿足如下條件，那么稱I滿足φ。其中，"?"是匹配符號(hào)，表示數(shù)據(jù)元組t與模式元組tp相匹配。為方便描述，下文將數(shù)據(jù)元組的屬性集X稱為左部，屬性集Y為右部。

根據(jù)定義2，CFDs的違例檢測(cè)可利用SQL語句，查詢不滿足條件的數(shù)據(jù)元組來完成。給定一個(gè)CFD：φ:(R:X→Y,tp），其違例的查詢分為以下兩步進(jìn)行[13]：

1）檢測(cè)單元組違例（single-tuple violations），即當(dāng)tp[Y]=a時(shí)，查詢左部與tp匹配，而右部與tp不匹配的數(shù)據(jù)元組t。這樣檢測(cè)出的每個(gè)違例是一條記錄。

2）檢測(cè)多元組違例（multi-tuple violations），即當(dāng)tp[Y]="_"時(shí)，查詢左部與tp匹配，而右部不相等的數(shù)據(jù)元組集合。此時(shí)的每個(gè)違例是一組記錄。

2 結(jié)合數(shù)據(jù)一致性的記錄比較

本文將以數(shù)據(jù)一致性為依據(jù)獲得的屬性相似度簡(jiǎn)稱為基于一致性的相似度（Consistence-Based Similarity，CBS），并將其定義如下：

定義3基于一致性的相似度（CBS）。給定一個(gè)CFD：φ:(R:X→Y,tp），若兩條記錄t1，t2左部與tp相匹配，說明其右部t1[Y]，t2[Y]有一定概率是匹配的，將這一概率稱為基于一致性的相似度CBS。

由定義3可知，對(duì)于一致性違例的右部屬性，可依據(jù)其對(duì)應(yīng)的左部屬性計(jì)算出CBS。CBS的優(yōu)勢(shì)在于其不受右部屬性中錯(cuò)誤和變體的影響，當(dāng)所選擇相似度算法處理錯(cuò)誤的能力不足時(shí)，結(jié)合CBS進(jìn)行記錄比較有利于得到更準(zhǔn)確的相似度向量。

結(jié)合數(shù)據(jù)一致性進(jìn)行記錄比較的基本思想如下：依據(jù)條件函數(shù)依賴發(fā)現(xiàn)數(shù)據(jù)集中的一致性違例，計(jì)算違例中右部屬性的CBS，并與傳統(tǒng)記錄比較得到的相似度向量相結(jié)合，即可得到結(jié)合了數(shù)據(jù)一致性信息的記錄比較結(jié)果。

2.1 記錄比較中的一致性檢測(cè)

第1節(jié)介紹了修復(fù)數(shù)據(jù)一致性時(shí)檢測(cè)一致性違例的方法，但該方法沒有考慮到數(shù)據(jù)集中存在的錯(cuò)誤，僅查詢t1[X]=t2[X]?tp[X]會(huì)降低一致性檢測(cè)的完整性。對(duì)此，本文在一致性檢測(cè)中引入了近似匹配符"≈θ"[14]。"≈θ"的含義是若兩個(gè)屬性值的相似度不低于閾值，則認(rèn)為兩屬性值匹配。特別的，當(dāng)ti[X]與tp[X]比較時(shí)，若tp[X]取值為"_"，則認(rèn)為兩個(gè)值匹配。這里的相似度可通過FBS的方法進(jìn)行度量。

用Qφ表示基于近似匹配符的一致性檢測(cè)方法，其語句如圖1所示。圖1中，V是FBS方法得到的相似度矩陣，每一行都是兩條記錄t1，t2的相似度向量；φ:(R:X→Y,tp）是給定的CFD，θ是近似匹配閾值。

圖1 記錄比較中的一致性違例查詢

經(jīng)Qφ檢測(cè)出的違例以二元組{相似度向量，記錄對(duì)id}的形式表示，接下來需計(jì)算這些記錄對(duì)的右部CBS。

2.2 CBS的計(jì)算

先考慮一個(gè)簡(jiǎn)單的情況。給定兩條記錄t1，t2和φ（:R:B→A，（_||_||_）），在t1[B]≈θt2[B]的情況下，一般可認(rèn)為t1[B]，t2[B]相似度越高，t1[A]，t2[A]越有可能描述同一屬性值。此時(shí)，可將t1[B]，t2[B]的FBS作為t1[A]，t2[A]的一致性相似度。用sf表示兩個(gè)屬性的FBS相似度，sc表示兩屬性的一致性相似度，可得到公式（1）：

現(xiàn)實(shí)數(shù)據(jù)中，很多CFDs的左部是一個(gè)屬性集合，此時(shí)由于存在多個(gè)FBS，計(jì)算一致性相似度需要對(duì)公式進(jìn)行擴(kuò)展。

定義2說明，對(duì)于φ:(R:X→Y,tp），當(dāng)X所有屬性都滿足tp時(shí)，可判斷t1[Y]，t2[Y]描述同一屬性值。故可以認(rèn)為，t1[Y]，t2[Y]相似的概率等于X中所有屬性同時(shí)滿足tp的概率。由此，本文提出公式（2），計(jì)算一致性違例記錄對(duì)中屬性Y的CBS。

公式（1）可看作公式（2）的特殊情況，當(dāng)X中僅有一個(gè)屬性時(shí)，兩公式計(jì)算結(jié)果相同。此外，當(dāng)記錄對(duì)（t1，t2）滿足多個(gè)φ時(shí)，屬性對(duì)（t1[Y]，t2[Y]）可能會(huì)得到多個(gè)CBS。對(duì)此，本文認(rèn)為：若（t1，t2）近似滿足多個(gè)φ，說明有多個(gè)依據(jù)同時(shí)支持（t1[Y]，t2[Y]）的一致性，其 CBS應(yīng)較高。因此，當(dāng)（t1[Y]，t2[Y]）對(duì)應(yīng)多個(gè)CBS時(shí)，取其中最大值作為屬性對(duì)的一致性相似度，即公式（3）。其中，Sc是根據(jù)不同φ計(jì)算所得的sc集合。

2.3 加權(quán)公式

在一個(gè)CFD的多元組違例中，可能存在CBS和FBS沖突的情況：當(dāng)兩條記錄的左部與tp匹配時(shí)，從數(shù)據(jù)一致性的角度看，其右部很有可能在描述同一屬性值，可推斷右部屬性的相似度較高；但作為一致性違例，其右部不與tp匹配，可能會(huì)由于相似度算法的局限性得到較低的相似度。

在上述情況下，并不能保證CBS更為準(zhǔn)確。例如，存在右部屬性并非描述同一屬性值，但因左部屬性中存在拼寫錯(cuò)誤，使二者CBS較高的情況。此時(shí)，或可結(jié)合兩種相似度度量方式，提高結(jié)果的穩(wěn)定性。

基于上述考慮，本文提出通過線性加權(quán)來結(jié)合CBS和FBS的公式，以提升結(jié)果的穩(wěn)定性，具體如公式（4）所示：

其中，α是CBS的權(quán)重。由于兩條記錄左部不滿足tp時(shí)，沒有依據(jù)判斷右部的一致性，故此時(shí)只計(jì)算sf。

2.4 方法流程

如圖2所示，基于數(shù)據(jù)一致性的記錄比較方法（即CBS方法）流程分為4步：首先，使用傳統(tǒng)的FBS方法進(jìn)行記錄比較：通過選定的相似度算法，逐屬性地計(jì)算候選記錄對(duì)的相似度向量，得到相似度矩陣Vf；然后，在Vf中執(zhí)行查詢Qφ，檢測(cè)其中的一致性違例；第三，依據(jù)公式（2）和公式（3）計(jì)算一致性違例中右部屬性的CBS；最后，依據(jù)公式線性加權(quán)CBS和FBS，得到結(jié)合一致性信息的記錄比較結(jié)果。

圖2 基于數(shù)據(jù)一致性的記錄比較方法

下面分析CBS方法的時(shí)間復(fù)雜度。在圖2的第2步中，對(duì)每個(gè)φ，CBS方法都需要查詢一次相似度矩陣，故發(fā)現(xiàn)所有違例的時(shí)間復(fù)雜度為O（n|Vf|），其中n是φ的數(shù)量，|Vf|是Vf的規(guī)模。在第3步中，對(duì)每個(gè)檢測(cè)出的一致性違例都需要進(jìn)行一次線性加權(quán)計(jì)算和賦值，最壞情況下要進(jìn)行|Vf|次，故此階段時(shí)間復(fù)雜度為O（|Vf|）。綜上，CBS方法時(shí)間復(fù)雜度為O（n|Vf|），所需時(shí)間和Vf的規(guī)模成線性關(guān)系。

3 實(shí)驗(yàn)分析

本文從兩個(gè)方面對(duì)CBS方法進(jìn)行了驗(yàn)證：1）效果驗(yàn)證，相比傳統(tǒng)的FBS方法，CBS方法得到的相似度矩陣是否有助于獲得更高的準(zhǔn)確率（Precision）、召回率（Recal）和F值（f-score）；2）效率驗(yàn)證，CBS方法比FBS方法多了一致性檢測(cè)、計(jì)算CBS、線性加權(quán)3個(gè)步驟，這對(duì)記錄比較的時(shí)間有多大影響。

3.1 實(shí)驗(yàn)設(shè)置

與文獻(xiàn)[15，16]類似，實(shí)驗(yàn)使用實(shí)際數(shù)據(jù)"DBLPACM"進(jìn)行測(cè)試。該數(shù)據(jù)為采自DBLP和ACM的文獻(xiàn)記錄，數(shù)據(jù)量分別為2 616、2 294條，兩來源間有2 224條記錄是相互重復(fù)的。

測(cè)試數(shù)據(jù)中，每條文獻(xiàn)由 title，authors，venue，year 4個(gè)屬性組成。易知數(shù)據(jù)中存在兩個(gè)條件函數(shù)依賴：一篇文獻(xiàn)只能在一個(gè)刊物上發(fā)表，出版方會(huì)盡量避免自己刊物上的文獻(xiàn)重名。本文在實(shí)驗(yàn)中利用這兩個(gè)條件函數(shù)依賴計(jì)算CBS，如φ1、φ2所示：

3.2 效果驗(yàn)證

首先測(cè)試CBS方法對(duì)實(shí)體分辨結(jié)果的影響。實(shí)驗(yàn)中以常用的Jaro-Winkler算法計(jì)算相似度，取α和θ的值為0.8、0.85，可得到圖3的結(jié)果。

由圖3可知，在相同匹配閾值下，CBS方法的準(zhǔn)確率、召回率及F值均優(yōu)于FBS方法，說明結(jié)合一致性信息進(jìn)行記錄比較可提升結(jié)果的準(zhǔn)確性。但是，當(dāng)取較低的記錄匹配閾值（0.65以下）時(shí)，CBS方法的3個(gè)指標(biāo)與FBS方法差距不大，這是由于一致性相似度需要在記錄對(duì)左部屬性的相似度均不低于θ時(shí)計(jì)算，而滿足這一條件的記錄對(duì)整體相似度不會(huì)太低，說明CBS方法對(duì)FBS較低的記錄對(duì)處理能力存在不足。

3.3 效率驗(yàn)證

設(shè)置α和θ分別為 0.8、0.85，隨機(jī)選取 0～3×105，以5×104為單位遞增的記錄對(duì)，比較CBS方法在不同規(guī)模數(shù)據(jù)中消耗的時(shí)間，可得到圖4。

圖3 兩種方法效果對(duì)比

圖4 兩種記錄比較方法運(yùn)行時(shí)間對(duì)比

由圖4可知，兩種方法的運(yùn)行時(shí)間較為接近，說明FBS方法耗時(shí)較長(zhǎng)，而CBS方法在此基礎(chǔ)上增加的時(shí)間較短，且基本呈線性增長(zhǎng)。這表示在傳統(tǒng)FBS方法的基礎(chǔ)上使用CBS方法不會(huì)額外消耗過多時(shí)間。

4 結(jié)論

為更好地處理屬性值的表述不一致，本文提出了一種基于數(shù)據(jù)一致性的記錄比較方法。通過條件函數(shù)依賴，該方法可以利用更為豐富的約束條件。公開測(cè)試數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果顯示，所提方法在準(zhǔn)確率、查準(zhǔn)率、F值上均優(yōu)于傳統(tǒng)方法，且不會(huì)額外消耗過多時(shí)間。但是，實(shí)驗(yàn)中也發(fā)現(xiàn)CBS方法對(duì)相似度過低的記錄對(duì)處理能力不足，這在進(jìn)一步的研究中還有待改進(jìn)。

[1]Papadakis G，Ioannou E，Niederée C，et al.Efficient entity resolution for large heterogeneous information spaces[C]//Proceedings of the Proceedings of the fourth ACM internationalconferenceon Web search and data mining，2011，ACM，535-544.

[2]Papadakis G，Ioannou E，Niederée C，et al.To compare or not to compare:making entity resolution more efficient[C]//Proceedings of the Proceedings of the International Workshop on Semantic Web Information Management，2011，ACM，3.

[3]Zitnik S，Subelj L，Lavbic D，et al.General Context-AwareData Matching and Merging Framework[J].Informatica，2013，24（1）:119-152.

[4]Nuray-Turan R，Kalashnikov D V，Mehrotra S.Adaptive connection strength models for relationship-based entity resolution[J].J Data and Information Quality，2013，4（2）:1-22.

[5]Leitao L，Calado P，Herschel M.Efficient and effective duplicate detection in hierarchical data[J].Ieee Transactions on Knowledge And Data Engineering，2013，25（5）:1028-1041.

[6]譚明超，刁興春，曹建軍.實(shí)體分辨研究綜述[J].計(jì)算機(jī)科學(xué)，2014，41（4）:9-12，20.

[7]Paradies M，Malaika S，Siméon J，et al.Entity matching for semistructured data in the Cloud[C]//Proceedings of the Proceedings of the 27th Annual ACM Symposium on Applied Computing，2012，ACM，453-458.

[8]Wang J，Li G，Yu J X，et al.Entity matching:How similar is similar[J].Proceedings of the VLDB Endowment，2011，4（10）:622-633.

[9]譚明超，刁興春，曹建軍，等.一種基于函數(shù)依賴的屬性相似度調(diào)整算法[J].上海交通大學(xué)學(xué)報(bào)，2015（8）:1075-1083，1089.

[10]耿寅融，劉波.基于條件函數(shù)依賴的數(shù)據(jù)庫一致性檢測(cè)研究[J].計(jì)算機(jī)工程與應(yīng)用，2012（3）:122-125.

[11]李建中，劉顯敏.大數(shù)據(jù)的一個(gè)重要方面:數(shù)據(jù)可用性[J].計(jì)算機(jī)研究與發(fā)展，2013，50（6）:1147-1162.

[12]Saha B，Srivastava D.Data quality:The other face of big data[C]//Proceedings of the 2014 IEEE 30th International Conference on Data Engineering，2014，IEEE，1294-1297.

[13]Fan W，Geerts F，Li J，et al.Discovering conditional functional dependencies[J].Ieee Transactions on Knowledge And Data Engineering，2011，23（5）:683-698.

[14]LiW， LiZ， Chen Q， etal.Discovering Approximate Functional Dependencies from Distributed Big Data[C]//Proceedings of the asiapacific web conference，2016，Springer，289-301.

[15]Xin J，Cui Z M，Zhao P P，et al.Active transfer learning of matching query results across multiple sources[J].Frontiers of Computer Science，2015，9（4）:595-607.

[16]Ferreira A A，Gon?alves M A，Laender A H.A brief survey of automatic methods for author name disambiguation[J].Acm Sigmod Record，2012，41（2）:15-26.