大數(shù)據(jù)實體識別相關技術研究

莎仁　梁瓊芳　李長明　張家鑫

摘 要：爆炸式增長的信息量帶來嚴重的數(shù)據(jù)質(zhì)量問題。實體識別是數(shù)據(jù)清洗的一項關鍵技術，用以識別存在不同形式的同一對象，或區(qū)分同一形式的不同對象。介紹了實體識別相關技術，闡述了實體識別技術過程與方法，并對面向大數(shù)據(jù)的實體識別技術進行了展望。

關鍵詞：大數(shù)據(jù);數(shù)據(jù)質(zhì)量;實體識別

DOI：10. 11907/rjdk. 191621

中圖分類號：TP301 ? 文獻標識碼：A ??????????????? 文章編號：1672-7800（2020）003-0125-03

Research on Related Technologies for Big Data Entity Identification

SHA Ren1， LIANG Qiong-fang1， LI Chang-ming2， ZHANG Jia-xin1

（1. College of Information Science and Technology，Northeast Normal University;

2. Changchun Guanghua University， Changchun 130000， China）

Abstract： Data quality problems are particularly serious due to the explosive growth of information. Entity recognition is a key technology for data cleaning to identify different objects in different forms or to distinguish different objects in the same form. This paper outlines the problem of entity recognition， summarizes the technology of entity recognition and looks forward to the entity recognition technology for big data.

Key Words：big data; data quality; entity recognition

0 引言

隨著信息時代的來臨，數(shù)據(jù)量爆發(fā)式增長，這些規(guī)模龐大的數(shù)據(jù)具有巨大的挖掘價值，但也存在大量數(shù)據(jù)質(zhì)量問題，如重復數(shù)據(jù)、缺失數(shù)據(jù)、陳舊數(shù)據(jù)等，劣質(zhì)數(shù)據(jù)導致可用性大打折扣，數(shù)據(jù)清洗引起廣泛關注。實體識別（Entity Identification）是數(shù)據(jù)清洗的一項關鍵技術，其主要目的就是準確識別出同一實體，將數(shù)據(jù)對象與現(xiàn)實世界的真實實體一一對應，即對數(shù)據(jù)庫中元組對是否指代同一實體進行判別，以此達到去除冗余、消解不一致的數(shù)據(jù)清洗效果。本文主要根據(jù)大數(shù)據(jù)實體識別過程總結相關技術工作并展開討論。

1 實體識別

數(shù)據(jù)質(zhì)量可從6個維度定義：①精確性（Accuracy），指數(shù)據(jù)描述現(xiàn)實事物的接近程度;②完整性（Completeness），指數(shù)據(jù)集的完整程度;③時效性（Timeliness），描述數(shù)據(jù)的新舊程度;④一致性（Consistency），描述數(shù)據(jù)內(nèi)部的矛盾程度;⑤相關性（Relevancy），描述數(shù)據(jù)與應用需求的契合程度;⑥實體同一性（Entity identity），指數(shù)據(jù)描述同一個現(xiàn)實世界事物數(shù)據(jù)的冗余程度[1]。

實體同一性（Entity identity）是數(shù)據(jù)質(zhì)量的重要標準之一，描述同一個現(xiàn)實世界中事物的數(shù)據(jù)冗余程度。例如同一實體的不同表現(xiàn)形式，或命名相同但并不是同一現(xiàn)實事物。不同文獻對于實體識別有不同的名稱，比如對象識別（Object Identification）、記錄鏈接（Record Linkage）以及實體解析（Entity Resolution）等等[2]。因此，大數(shù)據(jù)實體識別的主要任務就是在海量數(shù)據(jù)中尋找描述同一事物的若干元祖。

下面對實體識別的常用概念進行形式化定義說明實體識別問題：

定義1? 復雜數(shù)據(jù)集合D{d1，d2，…，d|D|};

定義2? 真實世界的物理實體集合E{e1，e2，…，e|E|};

定義3? 數(shù)據(jù)集中記錄集合R{r1，r2，…，r|R|};

定義4? 記錄R的屬性集合A{a1，a2，…，a|A|};

定義5? A的屬性值集合V{v1，v2，…，v|V|}，且滿足？ vi∈V，？rj∈R，aq∈A的情況下rj.aq=vi。

根據(jù)以上形式化定義，實體識別問題可以闡述為將數(shù)據(jù)源集合D的記錄集合R劃分為[R′]， [R′]中的每個集合與集合E中的物理實體一一對應。因此實體識別算法的輸入是R，輸出是經(jīng)過解析的記錄集合[R′]{r1，r2，…，r|E|}（[R′]是E的不相交子集集合，[R′]所有集合的并集為E）。

2 大數(shù)據(jù)實體識別過程

大數(shù)據(jù)實體識別過程為：首先對大數(shù)據(jù)進行分塊預處理，以提高識別效率。然后對分塊處理后的數(shù)據(jù)進行相似關系計算并匹配，匹配成功的數(shù)據(jù)為同一實體。實體識別過程如圖1所示。

2.1 預處理階段

預處理階段是實體識別過程的關鍵階段。在實體識別過程中，一般將實體對逐一比較。假設有大小為x和y的兩個數(shù)據(jù)集需要匹配，則要進行x*y次元組比較。但在大數(shù)據(jù)環(huán)境下，這樣比較非常耗時，計算代價高。因此，在實體對比較之前，為避免進行笛卡爾級別運算，提高實體識別效率 ，根據(jù)某種知識或規(guī)則將數(shù)據(jù)分成規(guī)模更小的數(shù)據(jù)塊（Block），只在塊內(nèi)進行數(shù)據(jù)比較，這種方法統(tǒng)稱為分塊技術（Block Technique）[3]。

2.1.1 固定分塊方法

最早的分塊方法是固定分塊方法（Fixed-Sized Partition）[4]，按照固定大小將數(shù)據(jù)分塊，每個元組只能插入到一個塊中。固定分塊方法大大提高了數(shù)據(jù)處理效率，但缺點也非常明顯：容易造成數(shù)據(jù)浪費及相關信息缺失。

2.1.2 相鄰排序方法

為彌補固定分塊缺陷，Hernandez & Stolfo[5-6]提出了相鄰排序分塊方法（Sorted Neighborhood），將元組進行排序，然后采用固定長度滑動窗口方式進行分塊，如圖2所示。但固定大小的滑動窗口會導致不相近的相似元組不能分到一個塊中，因此Yan等[7]提出了根據(jù)元組相似度改變滑動窗口大小的分塊方法。根據(jù)相似元組多少改變滑動窗口大小，這樣保證了每個塊中包含全部的相似度高的元組。

2.1.3 Canopy聚類方法

數(shù)據(jù)分塊可以看作是將相似元組聚類到一起，因此可使用聚類算法進行分塊。大多數(shù)聚類算法復雜度高，但分塊方法需要低計算復雜度且高速的聚類方法。因此，針對分塊特點，Han等[8]提出了Canopy聚類算法：首先將數(shù)據(jù)集中的每條記錄都映射到空間中，通過距離函數(shù)distance（x，y）快速計算鍵值距離，任取記錄中的一點并建立新的塊，將與該點距離小于一定閾值的并入到塊中，刪除距離遠的點。通過不斷迭代重復，將元組插入到不同塊中，直到距離大于一定的閾值，但該聚類方法對聚類中心的選取依賴性較高。

2.1.4 基于映射的分塊方法

Jin等[9]提出了一種基于映射的分塊方法，其基本思想是利用String Map算法將數(shù)據(jù)字符串映射到多維空間上，這樣可以保留字符串之間的原始相似度，然后將相似度大的對象插入到相同類中生成塊[10]。這種方法計算復雜度較高，因此在該算法的基礎上提出了基于double-embedding的索引技術[11]，將映射到多維空間的對象通過FastMap算法映射到更低維度的空間，最后利用KD-tree和近鄰相似度方法結合抽取對象從而生成塊。

2.2 相似匹配階段

實體進行分塊后，便對塊中數(shù)據(jù)進行實體匹配以達到識別效果。數(shù)據(jù)通過相似匹配方法將元組對分為匹配和不匹配，匹配的元組代表同一實體，不匹配的為不同實體，相關技術介紹如下。

2.2.1 基于閾值方法

基礎的實體識別方法是設定閾值，將元組對比較向量中的每個相似度值簡單相加得到總的相似度，再與設定的閾值進行比較，根據(jù)比較結果判定元組對是否匹配。該方法缺陷顯而易見，首先是屬性值的簡單求和并沒有考慮到屬性的重要度，因此有很多根據(jù)屬性重要度設定權重計算相似度大小的改進方法;其次是求和過程中每個單獨相似性信息丟失了，因此研究出復雜的實體分類器，通過單個相似度進行實體識別，這種方法對閾值設定的專業(yè)度有很強的依賴性。

2.2.2 基于概率方法

通過概率方法可將實體識別問題作為貝葉斯推理問題[12]。設定不匹配U類和匹配M類，x為比較向量，通過判定規(guī)則將x劃分到U或M類中。當每個類的密度函數(shù)是已知時，x在U類和M類中的密度函數(shù)是不同的，這樣實體識別問題就成為一個貝葉斯推理問題。

判定規(guī)則描述如下：

x為元組對的一個比較向量，如果匹配類M的概率大于U的概率，則x被分到M中，否則分到U中。

利用貝葉斯定理可表示為

其比例[lx=p（x|M）p（x|U）]是似然率。這種判定規(guī)則稱為最小錯誤的貝葉斯測試（the Bayes test for minimum error），可保證錯誤的最小概率，是一個最優(yōu)的分類器。但是這種方法很難應用于現(xiàn)實生活中，因為需要已知[p（x|M）]，[p（x|U）]的分布和先驗概率[p（U）]和[p（M）]。但該方法假設獨立，即當[i≠j]時，概率[p（xi|M）]和概率[p（xj|M）]獨立。

2.2.3 有監(jiān)督分類方法

通過機器學習方法進行實體識別需要將一部分有標記的匹配元組對作為訓練集，訓練出分類器，再用分類器進行分類。比如一種基于SVM的自動分類算法，首先從訓練集中挑選出明顯是M類和U類的比較向量集合，用它們作為訓練集生成一個最初的SVM，再利用該SVM對剩下的比較向量進行分類，找到離SVM判定邊界最遠的比較向量加入訓練集，再得到第二個SVM，如此循環(huán)迭代直到滿足終止條件。

2.2.3 主動學習方法

有監(jiān)督的分類算法需要依賴訓練集，對訓練集的要求較高，訓練集必須盡可能代表整個數(shù)據(jù)庫中的元祖特征，訓練集的質(zhì)量決定最后實體識別算法的優(yōu)劣。為解決這個問題，提出了主動學習的方法。該方法初始只需要小的訓練集，然后建立一個交互式分類模型，通過向?qū)＜矣脩籼釂柕姆绞将@取訓練樣本。主動學習的實體識別方法可以在保證盡可能減少樣本數(shù)量的同時精確性依然很高，但顯而易見，該方法對專家用戶的依賴性比較高。

2.2.3 基于聚類的方法

目前很多實體識別方法都是通過聚類進行的。例如根據(jù)某個相似度對元組進行排序，再使用一個優(yōu)先隊列存放最近生成的類。將排序好的元組同優(yōu)先隊列的元組進行比較，相似便插入其中，并將該類移到優(yōu)先隊列的最頂端。若未成功匹配則建立新的類。

另一種聚類方法是基于圖的聚類，比如著名的CENTER聚類算法，首先將數(shù)據(jù)元組對生成圖，然后對圖進行聚類，聚類后的每個子圖為一個實體。CENTER聚類算法首先找到每個子圖的中心，然后將元組插入到距離最近的中心所代表的類里。這種聚類方式使得類中心的選取非常重要，會極大影響最終的分類結果，因此改進方法之一是若類的中心相似度高便合并兩個類。同時，還有基于密度的聚類，匹配元組密度大，不匹配的密度小。這種方法的好處是不需要根據(jù)全局閾值，只根據(jù)鄰居數(shù)量和密度就可達到聚類效果。

面對大數(shù)據(jù)的實體識別，目前主要通過分布式平臺并使用基于閾值、基于聚類以及兩者或多種技術相結合的方法達到大數(shù)據(jù)實體識別的目的，如李明達等使用Hyracks作為并行處理平臺，將n-Gram算法進行并行優(yōu)化實現(xiàn)了面向大數(shù)據(jù)的實體識別;霍然等使用Map-Reduce并行框架，通過圖聚類的方法進行大數(shù)據(jù)實體識別;李鵬等使用Map-Reduce框架在Hadoop平臺上將基于機器學習的算法并行，使其應用于大數(shù)據(jù)實體識別;胡志剛等將數(shù)據(jù)分塊后建立超圖模型，在Hadoop平臺上進行超圖聚類，等等。

3 結語

實體識別技術已經(jīng)相對成熟，但大數(shù)據(jù)實體識別技術剛開始引起重視。由于分塊技術主要用于提高實體識別算法效率，因此分塊技術計算復雜度低、耗時短，以及部分精確度較高的分塊技術并不適用，同時缺少針對實體識別的分塊技術;在數(shù)據(jù)方面，大多是對于簡單數(shù)據(jù)的實體識別，對于復雜結構的數(shù)據(jù)處理較少，特別是對圖數(shù)據(jù)的處理工作并不多;目前多為針對靜態(tài)數(shù)據(jù)的處理，而現(xiàn)今社會更需要大數(shù)據(jù)的實時識別，這些都是未來大數(shù)據(jù)實體識別技術的重點發(fā)展方向。

參考文獻：

[1]劉顯敏， 李建中. 實體識別問題的相關研究[J]. 智能計算機與應用， 2013， 3（2）：1-5.

[2]朱燦，曹健. 實體解析技術綜述與展望[J]. 計算機科學， 2015，42（3）： 13-17， 23.

[3]FISHER J，CHRISTEN P，WANG Q， et al. A clustering-based framework to control block sizes for entity resolution[C]. the 21th ACM? SIGKDD Intl Conference on Knowledge Discovery and Data Mining，2015：279-288.

[4]FELLEGI I P， SUNTER A B. A theory for record linkage[J]. Journal of the AmericanStatistical Association， 1969， 64（328）：1183-1210.

[5]HERN M A， STOLFO S J. The merge/purge problem for large databases[J]. ACM SIGMOD Record. 1995（24）：127-138.

[6]HERN M A，STOLFO S? J. Real-world data is dirty： data cleansing and themerge/purge problem[J]. Data mining and knowledge discovery，1998，2（1）：9-37.

[7]YAN S，LEE D，KAN M Y， et al. Adaptive sorted neighborhood methods for efficient record linkage[C]. Proceedings of the 7th ACM/IEEE-CS joint conferenceon Digital libraries，2007：185-194.

[8]HAN J，MICHELINE K. Data mining： concepts and techniques[J]. San Francisco，CA， itd： Morgan Kaufmann， 2001（5）：52-59.

[9]JIN L，LI C， MEHROTRA S. Efficient record linkage in large data sets[C]. Eighth International Conference on Database Systems for Advanced Applications， 2003.

[10]FALOUTSOS C，LIN K I. Fastmap： a fast algorithm for indexing， data-mining andvisualization of traditional and multimedia datasets[M]. ACM， 1995.

[11]ADLY N. E？cient record linkage using a double embeddingscheme.[C]. DMIN，2009：274-281.

[12]NEWCOMBE H B， KENNEDY J M， AXFORD S J， et al. Automatic linkage of vitalRecords[EB/OL]. http：//xueshu.baidu.com/usercenter/paper/show？paperid=09504bb66585863508df8b826e57445a.

（責任編輯：杜能鋼）

收稿日期：2019-04-28

作者簡介：莎仁（1993-），女，東北師范大學信息科學與技術學院碩士研究生，研究方向為教育大數(shù)據(jù);梁瓊芳（1993-），女，東北師范大學信息科學與技術學院碩士研究生，研究方向為教育支撐軟件;李長明（1990-），男，碩士，長春光華學院助教，研究方向為大數(shù)據(jù);張家鑫（1992-），男，東北師范大學信息科學與技術學院碩士研究生，研究方向為教育大數(shù)據(jù)。本文通訊作者：李長明。