莎仁　梁瓊芳　李長明　張家鑫

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

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

DOI：10. 11907/rjdk. 191621

中圖分類號(hào)：TP301 ? 文獻(xiàn)標(biāo)識(shí)碼：A ??????????????? 文章編號(hào)：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í)代的來臨，數(shù)據(jù)量爆發(fā)式增長，這些規(guī)模龐大的數(shù)據(jù)具有巨大的挖掘價(jià)值，但也存在大量數(shù)據(jù)質(zhì)量問題，如重復(fù)數(shù)據(jù)、缺失數(shù)據(jù)、陳舊數(shù)據(jù)等，劣質(zhì)數(shù)據(jù)導(dǎo)致可用性大打折扣，數(shù)據(jù)清洗引起廣泛關(guān)注。實(shí)體識(shí)別（Entity Identification）是數(shù)據(jù)清洗的一項(xiàng)關(guān)鍵技術(shù)，其主要目的就是準(zhǔn)確識(shí)別出同一實(shí)體，將數(shù)據(jù)對象與現(xiàn)實(shí)世界的真實(shí)實(shí)體一一對應(yīng)，即對數(shù)據(jù)庫中元組對是否指代同一實(shí)體進(jìn)行判別，以此達(dá)到去除冗余、消解不一致的數(shù)據(jù)清洗效果。本文主要根據(jù)大數(shù)據(jù)實(shí)體識(shí)別過程總結(jié)相關(guān)技術(shù)工作并展開討論。

1 實(shí)體識(shí)別

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

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

下面對實(shí)體識(shí)別的常用概念進(jìn)行形式化定義說明實(shí)體識(shí)別問題：

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

定義2? 真實(shí)世界的物理實(shí)體集合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í)體識(shí)別問題可以闡述為將數(shù)據(jù)源集合D的記錄集合R劃分為[R′]， [R′]中的每個(gè)集合與集合E中的物理實(shí)體一一對應(yīng)。因此實(shí)體識(shí)別算法的輸入是R，輸出是經(jīng)過解析的記錄集合[R′]{r1，r2，…，r|E|}（[R′]是E的不相交子集集合，[R′]所有集合的并集為E）。

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

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

2.1 預(yù)處理階段

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

2.1.1 固定分塊方法

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

2.1.2 相鄰排序方法

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

2.1.3 Canopy聚類方法

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

2.1.4 基于映射的分塊方法

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

2.2 相似匹配階段

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

2.2.1 基于閾值方法

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

2.2.2 基于概率方法

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

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

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

利用貝葉斯定理可表示為

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

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

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

2.2.3 主動(dòng)學(xué)習(xí)方法

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

2.2.3 基于聚類的方法

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

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

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

3 結(jié)語

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

參考文獻(xiàn)：

[1]劉顯敏， 李建中. 實(shí)體識(shí)別問題的相關(guān)研究[J]. 智能計(jì)算機(jī)與應(yīng)用， 2013， 3（2）：1-5.

[2]朱燦，曹健. 實(shí)體解析技術(shù)綜述與展望[J]. 計(jì)算機(jī)科學(xué)， 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.

（責(zé)任編輯：杜能鋼）

收稿日期：2019-04-28

作者簡介：莎仁（1993-），女，東北師范大學(xué)信息科學(xué)與技術(shù)學(xué)院碩士研究生，研究方向?yàn)榻逃髷?shù)據(jù);梁瓊芳（1993-），女，東北師范大學(xué)信息科學(xué)與技術(shù)學(xué)院碩士研究生，研究方向?yàn)榻逃诬浖?李長明（1990-），男，碩士，長春光華學(xué)院助教，研究方向?yàn)榇髷?shù)據(jù);張家鑫（1992-），男，東北師范大學(xué)信息科學(xué)與技術(shù)學(xué)院碩士研究生，研究方向?yàn)榻逃髷?shù)據(jù)。本文通訊作者：李長明。