張風(fēng)榮

摘 要： 大數(shù)據(jù)下的實(shí)體識(shí)別是提高數(shù)據(jù)實(shí)體同一性的關(guān)鍵步驟。本文概述了實(shí)體識(shí)別問(wèn)題，介紹了不同類(lèi)型的實(shí)體識(shí)別算法，重點(diǎn)分析了復(fù)雜數(shù)據(jù)類(lèi)型的大數(shù)據(jù)實(shí)體識(shí)別算法，最后對(duì)實(shí)體識(shí)別算法的相關(guān)研究進(jìn)行了展望。

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

1.引言

在現(xiàn)實(shí)信息應(yīng)用系統(tǒng)中如：多媒體、社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)等諸多領(lǐng)域每天都積累了ZB級(jí)的大數(shù)據(jù)，這些數(shù)據(jù)具有規(guī)模龐大、涌現(xiàn)的速度快、可挖掘的價(jià)值大等特點(diǎn)，但同時(shí)有大量劣質(zhì)數(shù)據(jù)存在，這些數(shù)據(jù)具有重復(fù)性、不完整性、陳舊性等特點(diǎn)。有關(guān)大數(shù)據(jù)質(zhì)量的系列問(wèn)題已經(jīng)引起產(chǎn)業(yè)界和學(xué)術(shù)界的關(guān)注和重視。劣質(zhì)數(shù)據(jù)降低了信息的可用性，給用戶提供錯(cuò)誤的信息，誤導(dǎo)用戶做出錯(cuò)誤的決策，從而給用戶造成損失。統(tǒng)計(jì)數(shù)據(jù)顯示，50%以上的數(shù)據(jù)倉(cāng)庫(kù)項(xiàng)目由于數(shù)據(jù)質(zhì)量問(wèn)題而不得不取消或延遲。在典型的信息系統(tǒng)項(xiàng)目中，時(shí)間和成本預(yù)算的30%～80%實(shí)際用于清理數(shù)據(jù)而非系統(tǒng)開(kāi)發(fā)。專(zhuān)家估算目前數(shù)據(jù)質(zhì)量問(wèn)題平均給每個(gè)企業(yè)增加的成本是企業(yè)收入的10%～20%。

目前，并沒(méi)有統(tǒng)一的數(shù)據(jù)質(zhì)量的定義形式。有關(guān)文獻(xiàn)從六個(gè)維度闡述了數(shù)據(jù)質(zhì)量的定義標(biāo)準(zhǔn)，包括：精確性（accuracy）、完整性（completeness）、時(shí)效性（timeliness）、一致性（consistency）、實(shí)體同一性（entityidentity）及相關(guān)性（relevancy）。其中，實(shí)體同一性指的是數(shù)據(jù)同應(yīng)用需求的契合程度，描述同一個(gè)現(xiàn)實(shí)世界事物的數(shù)據(jù)冗余程度。實(shí)體識(shí)別在數(shù)據(jù)質(zhì)量管理中有重要作用，是數(shù)據(jù)質(zhì)量管理的主流研究方向之一。本文主要從針對(duì)各種數(shù)據(jù)模型總結(jié)數(shù)據(jù)質(zhì)量中實(shí)體識(shí)別的算法的相關(guān)工作，并就其中的相關(guān)算法展開(kāi)論述。

2.實(shí)體識(shí)別問(wèn)題

大數(shù)據(jù)中的實(shí)體識(shí)別是指在給定的大數(shù)據(jù)集中準(zhǔn)確發(fā)現(xiàn)屬于同一實(shí)體的不同記錄并將其聚類(lèi)，使得每個(gè)實(shí)體簇在現(xiàn)實(shí)世界中表示同一對(duì)象的過(guò)程。實(shí)體識(shí)別是提高數(shù)據(jù)實(shí)體同一性方面質(zhì)量的關(guān)鍵步驟。從形式化角度定義實(shí)體統(tǒng)一性：給定一個(gè)數(shù)據(jù)實(shí)體的集合D和一個(gè)物理實(shí)體集合O，求解一個(gè)集合D的劃分P（其中P是由一系列D的不相交子集合構(gòu)成，且P中所有集合并的結(jié)果與D相同）及P與O之間的一一對(duì)應(yīng)關(guān)系。在實(shí)際應(yīng)用中，數(shù)據(jù)實(shí)體D很容易獲得，而物理實(shí)體集合O很難獲得。因此在數(shù)據(jù)量大的情況下評(píng)價(jià)給定實(shí)體解析算法的優(yōu)劣非常困難。也就是說(shuō)，只要求將表示同一物理實(shí)體的數(shù)據(jù)實(shí)體放入一個(gè)集合，而不要求建立P與O之間的關(guān)系，該問(wèn)題則稱(chēng)為實(shí)體識(shí)別問(wèn)題。因此，根據(jù)實(shí)際具體的需求，借助不同的方法學(xué)，針對(duì)適合的問(wèn)題定義，給出系統(tǒng)的解決方案。

在不同的應(yīng)用領(lǐng)域，有不同的方法描述實(shí)體識(shí)別的過(guò)程。在單數(shù)據(jù)源中，內(nèi)部實(shí)體使用唯一標(biāo)識(shí)符或特征屬性精確匹配來(lái)區(qū)別。在分布式系統(tǒng)中，由于不同的設(shè)計(jì)目的和角度，現(xiàn)實(shí)世界中的同一個(gè)實(shí)體也不可能有相同的標(biāo)識(shí)符或者是相同的特征屬性，因此，必須采樣合適的方法實(shí)現(xiàn)實(shí)體識(shí)別。

3.實(shí)體識(shí)別過(guò)程

實(shí)體識(shí)別包括預(yù)處理階段、特征向量的選取、比較函數(shù)的選取、搜索空間的優(yōu)化、決策模型的選取和結(jié)果評(píng)估六個(gè)階段。

預(yù)處理階段是實(shí)體識(shí)別過(guò)程的關(guān)鍵階段，在該階段中要實(shí)現(xiàn)數(shù)據(jù)的標(biāo)準(zhǔn)化處理包括空格處理、字符大小寫(xiě)轉(zhuǎn)換、復(fù)雜數(shù)據(jù)結(jié)構(gòu)的解析和格式轉(zhuǎn)換、上下文異構(gòu)的消除等。隱馬爾科夫模型是在該過(guò)程中對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理的常用方法。

特征向量是指能夠識(shí)別實(shí)體的屬性的集合。特征向量的選取方法包括領(lǐng)域?qū)＜沂止ぶ付ê蜋C(jī)器學(xué)習(xí)方法。決策模型是在搜索空間中進(jìn)行特征向量比較中判斷實(shí)體是否匹配的決策模型的選取。一種是概率模型如Fellegiandsunter模型，另一種是基于經(jīng)驗(yàn)的模型，根據(jù)領(lǐng)域?qū)＜业慕?jīng)驗(yàn)設(shè)置門(mén)限值。

評(píng)估結(jié)果有匹配、不匹配和可能匹配。不能確定的匹配結(jié)果需要人工進(jìn)行評(píng)審，對(duì)評(píng)審過(guò)程中發(fā)現(xiàn)的問(wèn)題進(jìn)行調(diào)整或者改進(jìn)決策模型，以期獲得更高精度的實(shí)體識(shí)別效果。

4.實(shí)體識(shí)別相關(guān)研究

早期的實(shí)體識(shí)別算法主要是利用記錄之間的相似性進(jìn)行比較，運(yùn)用規(guī)則的方法和閾值確定兩條記錄是否為同一個(gè)實(shí)體。在機(jī)器學(xué)習(xí)方法中動(dòng)態(tài)生成相似性函數(shù)獲取一個(gè)分類(lèi)器，有效結(jié)合多個(gè)屬性的相似性并且較準(zhǔn)確地判定每對(duì)記錄是否能被匹配為同一實(shí)體。基于規(guī)則的方法是根據(jù)規(guī)則確定不同記錄是否描述同一實(shí)體。有學(xué)者提出了一個(gè)基于Map-Reduce框架的大數(shù)據(jù)實(shí)體識(shí)別算法，該算法首先通過(guò)屬性值計(jì)算記錄間的相似程度，而后基于圖聚類(lèi)的方法實(shí)現(xiàn)實(shí)體識(shí)別。

復(fù)雜數(shù)據(jù)是指在現(xiàn)實(shí)應(yīng)用中產(chǎn)生的如XML數(shù)據(jù)、圖數(shù)據(jù)和網(wǎng)絡(luò)數(shù)據(jù)等。同一實(shí)體具有不同的復(fù)雜的數(shù)據(jù)描述方式，為了有效對(duì)這些數(shù)據(jù)實(shí)施質(zhì)量管理，必須對(duì)復(fù)雜數(shù)據(jù)進(jìn)行快速有效的實(shí)體識(shí)別。復(fù)雜數(shù)據(jù)上的實(shí)體識(shí)別可以分為成對(duì)識(shí)別和成組識(shí)別。根據(jù)識(shí)別對(duì)象的不同，復(fù)雜數(shù)據(jù)的實(shí)體識(shí)別分為XML數(shù)據(jù)實(shí)體識(shí)別、圖結(jié)構(gòu)數(shù)據(jù)實(shí)體識(shí)別和復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的實(shí)體識(shí)別。

5.大數(shù)據(jù)下的實(shí)體識(shí)別算法展望

單數(shù)據(jù)源的實(shí)體識(shí)別算法已經(jīng)趨于成熟，但在大數(shù)據(jù)環(huán)境下的實(shí)體識(shí)別技術(shù)還是比較少。同時(shí)，針對(duì)大數(shù)據(jù)環(huán)境下的復(fù)雜結(jié)構(gòu)數(shù)據(jù)的研究剛剛起步，海量復(fù)雜數(shù)據(jù)上的實(shí)體識(shí)別技術(shù)，特別是圖數(shù)據(jù)上的實(shí)體識(shí)別技術(shù)的研究還處于初級(jí)階段，大規(guī)模圖集合上的數(shù)據(jù)實(shí)體識(shí)別的工作尚未開(kāi)展。

需要支持更新復(fù)雜數(shù)據(jù)上的實(shí)體識(shí)別技術(shù)，不斷更新互聯(lián)網(wǎng)、社會(huì)網(wǎng)信息要求設(shè)計(jì)更新紛繁復(fù)雜數(shù)據(jù)上的增量實(shí)體識(shí)別技術(shù)，為更新的數(shù)據(jù)確定其所描述的實(shí)體。

6.結(jié)語(yǔ)

多類(lèi)型的復(fù)雜數(shù)據(jù)要求設(shè)計(jì)實(shí)體識(shí)別技術(shù)。對(duì)互聯(lián)網(wǎng)信息、進(jìn)行有效的查詢、集成和分析需要多類(lèi)型復(fù)雜數(shù)據(jù)的實(shí)體識(shí)別技術(shù)。

參考文獻(xiàn)：

[1]王宏志，樊文飛.復(fù)雜數(shù)據(jù)上的實(shí)體識(shí)別技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（10）：1843-1852.

[2]霍然，王宏志，等.基于Map-Reduce的大數(shù)據(jù)實(shí)體識(shí)別算法[J].計(jì)算機(jī)研究與發(fā)展2013，11：170-179.

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

[4]李明達(dá)，王宏志，張佳程，等.PEIF：基于并行機(jī)群的大數(shù)據(jù)實(shí)體識(shí)別算法[J].2013，11：211-220.

[5]張建中，方正，等.對(duì)基于SNM數(shù)據(jù)清洗算法的優(yōu)化[J].華南大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，41（6）：2240-2245.

基金項(xiàng)目：山東省科技計(jì)劃（J15ln78），院級(jí)課題：2015LG001。