一種基于數據一致性的記錄比較方法

冉德彤，游宏梁

（中國國防科技信息中心北京1001421）

實體分辨（Entity Resolution）中，記錄比較的準確性直接影響能否準確、完整地識別相似重復記錄，如何得到更為準確的記錄比較結果一直是相關領域的研究熱點[1-2]。

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

針對該問題，文獻[8]提出了依據訓練數據選擇最優算法的方法，但該方法依賴訓練數據，在實際應用中獲取難度較大。文獻[9]提出了相似度調整的算法，利用數據集中的函數依賴關系調整相似度，以提高結果的準確性。然而，該算法以標準的函數依賴為基礎，所能表達的約束條件有限，當數據集中的約束超出其表達范圍時無法進行調整。

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

1 CFDs的基本概念

條件函數依賴是函數依賴的擴展，可表達更為具體的約束關系，是數據一致性研究中的一個重要概念[10-12]。下面介紹其定義。

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

根據定義1，標準的函數依賴可看作CFDs的一個特例。此外，對屬性值有限制的約束也可用CFDs表達。

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

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

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

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

2 結合數據一致性的記錄比較

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

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

由定義3可知，對于一致性違例的右部屬性，可依據其對應的左部屬性計算出CBS。CBS的優勢在于其不受右部屬性中錯誤和變體的影響，當所選擇相似度算法處理錯誤的能力不足時，結合CBS進行記錄比較有利于得到更準確的相似度向量。

結合數據一致性進行記錄比較的基本思想如下：依據條件函數依賴發現數據集中的一致性違例，計算違例中右部屬性的CBS，并與傳統記錄比較得到的相似度向量相結合，即可得到結合了數據一致性信息的記錄比較結果。

2.1 記錄比較中的一致性檢測

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

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

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

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

2.2 CBS的計算

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

現實數據中，很多CFDs的左部是一個屬性集合，此時由于存在多個FBS，計算一致性相似度需要對公式進行擴展。

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

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

2.3 加權公式

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

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

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

其中，α是CBS的權重。由于兩條記錄左部不滿足tp時，沒有依據判斷右部的一致性，故此時只計算sf。

2.4 方法流程

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

圖2 基于數據一致性的記錄比較方法

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

3 實驗分析

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

3.1 實驗設置

與文獻[15，16]類似，實驗使用實際數據"DBLPACM"進行測試。該數據為采自DBLP和ACM的文獻記錄，數據量分別為2 616、2 294條，兩來源間有2 224條記錄是相互重復的。

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

3.2 效果驗證

首先測試CBS方法對實體分辨結果的影響。實驗中以常用的Jaro-Winkler算法計算相似度，取α和θ的值為0.8、0.85，可得到圖3的結果。

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

3.3 效率驗證

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

圖3 兩種方法效果對比

圖4 兩種記錄比較方法運行時間對比

由圖4可知，兩種方法的運行時間較為接近，說明FBS方法耗時較長，而CBS方法在此基礎上增加的時間較短，且基本呈線性增長。這表示在傳統FBS方法的基礎上使用CBS方法不會額外消耗過多時間。

4 結論

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

[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]譚明超，刁興春，曹建軍.實體分辨研究綜述[J].計算機科學，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]譚明超，刁興春，曹建軍，等.一種基于函數依賴的屬性相似度調整算法[J].上海交通大學學報，2015（8）:1075-1083，1089.

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

[11]李建中，劉顯敏.大數據的一個重要方面:數據可用性[J].計算機研究與發展，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.