大數據下的實體識別算法研究

張風榮

摘 要： 大數據下的實體識別是提高數據實體同一性的關鍵步驟。本文概述了實體識別問題，介紹了不同類型的實體識別算法，重點分析了復雜數據類型的大數據實體識別算法，最后對實體識別算法的相關研究進行了展望。

關鍵詞： 數據質量 數據清洗 實體識別

1.引言

在現實信息應用系統中如：多媒體、社交網絡、物聯網等諸多領域每天都積累了ZB級的大數據，這些數據具有規模龐大、涌現的速度快、可挖掘的價值大等特點，但同時有大量劣質數據存在，這些數據具有重復性、不完整性、陳舊性等特點。有關大數據質量的系列問題已經引起產業界和學術界的關注和重視。劣質數據降低了信息的可用性，給用戶提供錯誤的信息，誤導用戶做出錯誤的決策，從而給用戶造成損失。統計數據顯示，50%以上的數據倉庫項目由于數據質量問題而不得不取消或延遲。在典型的信息系統項目中，時間和成本預算的30%～80%實際用于清理數據而非系統開發。專家估算目前數據質量問題平均給每個企業增加的成本是企業收入的10%～20%。

目前，并沒有統一的數據質量的定義形式。有關文獻從六個維度闡述了數據質量的定義標準，包括：精確性（accuracy）、完整性（completeness）、時效性（timeliness）、一致性（consistency）、實體同一性（entityidentity）及相關性（relevancy）。其中，實體同一性指的是數據同應用需求的契合程度，描述同一個現實世界事物的數據冗余程度。實體識別在數據質量管理中有重要作用，是數據質量管理的主流研究方向之一。本文主要從針對各種數據模型總結數據質量中實體識別的算法的相關工作，并就其中的相關算法展開論述。

2.實體識別問題

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

在不同的應用領域，有不同的方法描述實體識別的過程。在單數據源中，內部實體使用唯一標識符或特征屬性精確匹配來區別。在分布式系統中，由于不同的設計目的和角度，現實世界中的同一個實體也不可能有相同的標識符或者是相同的特征屬性，因此，必須采樣合適的方法實現實體識別。

3.實體識別過程

實體識別包括預處理階段、特征向量的選取、比較函數的選取、搜索空間的優化、決策模型的選取和結果評估六個階段。

預處理階段是實體識別過程的關鍵階段，在該階段中要實現數據的標準化處理包括空格處理、字符大小寫轉換、復雜數據結構的解析和格式轉換、上下文異構的消除等。隱馬爾科夫模型是在該過程中對數據進行標準化處理的常用方法。

特征向量是指能夠識別實體的屬性的集合。特征向量的選取方法包括領域專家手工指定和機器學習方法。決策模型是在搜索空間中進行特征向量比較中判斷實體是否匹配的決策模型的選取。一種是概率模型如Fellegiandsunter模型，另一種是基于經驗的模型，根據領域專家的經驗設置門限值。

評估結果有匹配、不匹配和可能匹配。不能確定的匹配結果需要人工進行評審，對評審過程中發現的問題進行調整或者改進決策模型，以期獲得更高精度的實體識別效果。

4.實體識別相關研究

早期的實體識別算法主要是利用記錄之間的相似性進行比較，運用規則的方法和閾值確定兩條記錄是否為同一個實體。在機器學習方法中動態生成相似性函數獲取一個分類器，有效結合多個屬性的相似性并且較準確地判定每對記錄是否能被匹配為同一實體。基于規則的方法是根據規則確定不同記錄是否描述同一實體。有學者提出了一個基于Map-Reduce框架的大數據實體識別算法，該算法首先通過屬性值計算記錄間的相似程度，而后基于圖聚類的方法實現實體識別。

復雜數據是指在現實應用中產生的如XML數據、圖數據和網絡數據等。同一實體具有不同的復雜的數據描述方式，為了有效對這些數據實施質量管理，必須對復雜數據進行快速有效的實體識別。復雜數據上的實體識別可以分為成對識別和成組識別。根據識別對象的不同，復雜數據的實體識別分為XML數據實體識別、圖結構數據實體識別和復雜網絡中節點的實體識別。

5.大數據下的實體識別算法展望

單數據源的實體識別算法已經趨于成熟，但在大數據環境下的實體識別技術還是比較少。同時，針對大數據環境下的復雜結構數據的研究剛剛起步，海量復雜數據上的實體識別技術，特別是圖數據上的實體識別技術的研究還處于初級階段，大規模圖集合上的數據實體識別的工作尚未開展。

需要支持更新復雜數據上的實體識別技術，不斷更新互聯網、社會網信息要求設計更新紛繁復雜數據上的增量實體識別技術，為更新的數據確定其所描述的實體。

6.結語

多類型的復雜數據要求設計實體識別技術。對互聯網信息、進行有效的查詢、集成和分析需要多類型復雜數據的實體識別技術。

參考文獻：

[1]王宏志，樊文飛.復雜數據上的實體識別技術研究[J].計算機學報，2011，34（10）：1843-1852.

[2]霍然，王宏志，等.基于Map-Reduce的大數據實體識別算法[J].計算機研究與發展2013，11：170-179.

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

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

[5]張建中，方正，等.對基于SNM數據清洗算法的優化[J].華南大學學報：自然科學版，2010，41（6）：2240-2245.

基金項目：山東省科技計劃（J15ln78），院級課題：2015LG001。