基于N-Gram算法的數(shù)據(jù)清洗技術(shù)*

馬平全， 宋 凱， 紀建偉

(1. 沈陽農(nóng)業(yè)大學 信息與電氣工程學院， 沈陽 110866； 2. 沈陽理工大學 自動化與電氣工程學院， 沈陽 110159)

基于N-Gram算法的數(shù)據(jù)清洗技術(shù)*

馬平全1，2， 宋 凱1，2， 紀建偉1

(1. 沈陽農(nóng)業(yè)大學 信息與電氣工程學院， 沈陽 110866； 2. 沈陽理工大學 自動化與電氣工程學院， 沈陽 110159)

針對數(shù)據(jù)庫中存在的大量相似重復數(shù)據(jù)，對相似重復記錄的屬性結(jié)構(gòu)以及產(chǎn)生原因進行了分析，采用N-Gram算法對數(shù)據(jù)記錄進行計算，得到代表每條記錄屬性的鍵值，即N-Gram值.依據(jù)該鍵值將數(shù)據(jù)庫中的數(shù)據(jù)記錄進行排序處理，建立有序的數(shù)據(jù)庫，并對其中的數(shù)據(jù)記錄進行相似度計算.運用排列合并的清洗思想對識別出來的相似重復數(shù)據(jù)記錄進行清洗，實驗結(jié)果表明，N-Gram算法有效提高了相似重復數(shù)據(jù)記錄的查全率和查準率.

相似度； 相似重復記錄； 屬性； 排序； 合并； 數(shù)據(jù)清洗； 查全率； 查準率

在第二次世界大戰(zhàn)期間，信息傳遞給戰(zhàn)爭雙方帶來了極大的便利，在戰(zhàn)爭進行過程中，人們漸漸地發(fā)現(xiàn)信息的重要性，各方都在不斷地更新自己的信息處理機制，加速信息的獲取.這種形式促進了電子計算機的產(chǎn)生，并在戰(zhàn)爭中起到了舉足輕重的作用.戰(zhàn)爭結(jié)束以后，電子計算機作為一種新的技術(shù)被保留下來，并且不斷地被開發(fā)，漸漸走進了人們的生活，人類逐漸進入了信息化時代，信息技術(shù)成為每一位新時代人所必備的技術(shù).

但隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)量不斷增加，大量的錯誤數(shù)據(jù)充斥其中，相似數(shù)據(jù)、重復數(shù)據(jù)和字段缺失數(shù)據(jù)等，這些垃圾數(shù)據(jù)的出現(xiàn)給人們帶來了很大的不便，甚至會給一些企業(yè)機關(guān)單位帶來嚴重的后果[1-3].因此，針對這些數(shù)據(jù)進行數(shù)據(jù)清洗變得迫在眉睫.

1 相似重復數(shù)據(jù)產(chǎn)生的原因

相似重復記錄是指在合并數(shù)據(jù)集的過程中，同一目標實體往往有著多條記錄，這些記錄之間雖然在形式上有所不同，但其所描述的目標卻是相同的一個.通常造成這種結(jié)果的原因是由于數(shù)據(jù)錄入時錯誤的拼寫、對名詞的縮寫以及不同的存儲類型，導致同一記錄實體有著多種不同表現(xiàn)形式，但這些記錄往往本意上都是表現(xiàn)同一條數(shù)據(jù)記錄[4-5].由于這種特殊原因，造成了其數(shù)據(jù)特征并不明顯，這對相似重復記錄的識別以及對其進行數(shù)據(jù)清洗造成了很大的困難.因此，清除數(shù)據(jù)庫中的相似重復記錄是提高數(shù)據(jù)庫使用率、降低消耗、提高數(shù)據(jù)質(zhì)量的一個重要途徑[6-7].

本文將相似重復記錄大致分為以下兩大類：

1) 完全重復記錄.這類記錄在數(shù)據(jù)庫中無論是字符還是數(shù)值，在屬性和表現(xiàn)形式上都是完全相同的.

2) 相似重復記錄.這類記錄是指在數(shù)據(jù)庫中部分屬性字段相同或者相似，但卻是同一記錄實體的不同表現(xiàn)形式[8-9].

2 數(shù)據(jù)清洗

數(shù)據(jù)清洗是指通過某種方式來清除數(shù)據(jù)集中“臟數(shù)據(jù)”的技術(shù)，經(jīng)常作為提高數(shù)據(jù)使用率的一種途徑.到目前為止，數(shù)據(jù)清洗仍是一個模糊的概念，研究人員對數(shù)據(jù)清洗沒有給出一個標準定義，對數(shù)據(jù)清洗技術(shù)的理解仍是從字面意思上解釋的，比較通用的說法是數(shù)據(jù)清洗就是把數(shù)據(jù)庫中“臟”的數(shù)據(jù)記錄清洗掉，保留下“干凈”的數(shù)據(jù)記錄[10-11].

數(shù)據(jù)清洗的步驟與一般數(shù)據(jù)處理過程類似，主要內(nèi)容包括如下幾個方面.

1) 數(shù)據(jù)分析.數(shù)據(jù)分析基本上是所有數(shù)據(jù)處理過程的首要步驟，通過詳細分析源數(shù)據(jù)庫，檢測源數(shù)據(jù)庫中的錯誤數(shù)據(jù)和不一致數(shù)據(jù)的情況，從而來判定數(shù)據(jù)質(zhì)量上的問題.然而，如何準確了解數(shù)據(jù)集中的質(zhì)量問題是個難點，而這個問題僅依靠既有的元數(shù)據(jù)并不能達到預期目的.這便需要對具體的數(shù)據(jù)實例進行數(shù)據(jù)分析，從中提取出能夠代表整條記錄的元數(shù)據(jù)，這些元數(shù)據(jù)能夠自動改變數(shù)據(jù)之間的屬性，本文稱之為依附性，然后重點對這些實例的屬性進行分析，才能發(fā)現(xiàn)其中的數(shù)據(jù)質(zhì)量問題[12].

數(shù)據(jù)派生和數(shù)據(jù)挖掘都能夠較好地完成數(shù)據(jù)分析的任務，但兩者主要應用在不同的數(shù)據(jù)庫中.首先兩者最大的不同是作用范圍，數(shù)據(jù)派生主要是作用在單獨的屬性上，通過對單獨的屬性實例進行分析，從而得到大量的屬性信息，包括數(shù)據(jù)類型、數(shù)據(jù)單位、屬性沖突的次數(shù)和缺失信息的頻率等.而數(shù)據(jù)挖掘恰好與其相反，其主要應用在大型數(shù)據(jù)中心，通過對大型數(shù)據(jù)中心的海量信息進行分析，挖掘出屬性之間依賴關(guān)系和約束關(guān)系，這些關(guān)系往往是后期對多數(shù)據(jù)源中相似重復記錄進行數(shù)據(jù)清洗的一個重要依據(jù)，根據(jù)這些關(guān)系能夠較為完善地解決存在的問題[13-14].

2) 確定數(shù)據(jù)轉(zhuǎn)換規(guī)則和工作流.通過數(shù)據(jù)分析可得到一些信息，包括數(shù)據(jù)源的個數(shù)、錯誤數(shù)據(jù)的多少以及“臟數(shù)據(jù)”的主要類型等，通過這些信息建立合適的清洗步驟、轉(zhuǎn)換算法、查詢語句以及檢測算法等，從而確定主句轉(zhuǎn)換規(guī)則和工作流.

3) 數(shù)據(jù)驗證.在確定數(shù)據(jù)轉(zhuǎn)換規(guī)則和工作流之后，需要對其進行驗證，避免出現(xiàn)效率低下等問題.從數(shù)據(jù)源中抽出一部分數(shù)據(jù)當作樣本數(shù)據(jù)，然后利用上一步確定的數(shù)據(jù)轉(zhuǎn)換規(guī)則和工作流對抽出來的樣本進行驗證，并對驗證結(jié)果進行分析，對工作流和轉(zhuǎn)換規(guī)則進行相應的調(diào)整和改進[15-16].數(shù)據(jù)驗證這一過程往往需要進行多次，以達到盡可能高的效率以及高精度地進行數(shù)據(jù)清洗.

4) 數(shù)據(jù)清洗.在數(shù)據(jù)驗證過程中，對選擇的清洗策略進行了驗證，確定其可行性，并利用該策略進行數(shù)據(jù)清洗操作，數(shù)據(jù)清洗的流程如圖1所示.

圖1 數(shù)據(jù)清洗流程Fig.1 Flow chart of data cleaning

3 N-Gram算法

N-Gram算法是一種大詞匯連續(xù)語音識別中常用的語言模型，它遵循的思想是每一條數(shù)據(jù)的出現(xiàn)都有一定的概率，通過假設數(shù)據(jù)中所有詞的出現(xiàn)都會影響其之后的詞，但對已出現(xiàn)的詞并沒有任何影響.通過這種思想可以認為整條記錄的出現(xiàn)都有一定的概率，與記錄中的每一個詞均有關(guān)系.因此，本文根據(jù)每個詞出現(xiàn)的概率，給每條記錄計算出一個鍵值，即N-Gram值，該值在一定程度上代表了該條記錄的屬性，屬性越相近，相似程度越高，該值在數(shù)值上就越接近.根據(jù)這種特性對數(shù)據(jù)源中所有的數(shù)據(jù)進行排序能夠?qū)⑾嗨浦貜蛿?shù)據(jù)放到一起.

當某條記錄中第N個詞的出現(xiàn)概率并不是隨機出現(xiàn)時，而是與這條記錄的前N-1個詞息息相關(guān)，并且僅與這N-1個詞有關(guān)，與第N個詞后面的詞都沒有關(guān)系，每個詞出現(xiàn)的概率相乘，便得到整條數(shù)據(jù)記錄出現(xiàn)的概率，而每個詞出現(xiàn)的概率都可以直接從所有數(shù)據(jù)記錄的語料庫和重復矩陣中計算得到，這便是N-Gram算法模型.

統(tǒng)計語言模型的數(shù)學模型表達式為

(1)

(2)

式(2)即為“馬爾可夫假設”.二元的Bigram認為，每條語句中的所有詞僅和其前面最相近的那個詞有關(guān)，與其他任何詞都無關(guān)，則其概率表達式為

P(S)=P(w1w2…wn)=

(3)

三元的Trigram假設下一個詞的出現(xiàn)僅依賴于其前面的兩個詞，則其概率表達式為

(4)

算法過程描述如下.

1) 數(shù)據(jù)預處理.在進行數(shù)據(jù)清洗之前，首先對待清洗的數(shù)據(jù)進行數(shù)據(jù)預處理，將其中無法識別的字符串或者帶有標識性含義的標點進行處理，例如銀行系統(tǒng)中常用的“￥”和“＄”符號，以及處于對數(shù)據(jù)保密的原因所進行的加密處理符號“*”，這些字符串在后期進行數(shù)據(jù)清洗的時候，由于其具有相似性，會對清洗結(jié)果的準確性產(chǎn)生很大的影響.

例如，待清洗的數(shù)據(jù)庫中有如下5條數(shù)據(jù)：

①Johnny·Depp，California，PrincetonUniversity，Computer

②Tom·Hanks，Districtofcolumbia，HarvardUniversity，philosophy

③Tom·Hanks，Districtcolumbia，HarvardUniversity，philosophy

④Adam·Sandler，Alabamas，UniversityofCaliforniaBerkeley，PhysicalScience

⑤Leonardo·Dicaprio，Connecticut，UniversityofSou-thernCalifornia，Biology

對它們進行預處理之后的結(jié)果如下：

① s1=johnnydeppcaliforniaprincetonuniversityco-mputer

② s2=tomhanksdistrictofcolumbiaharvardunivers-ityphilosophy

③ s3=tomhanksdistrictcolumbiaharvarduniversit-yphilosophy

④ s4=adamsandleralabamasuniversityofcaliforni-aberkeleyphysicalscience

⑤ s5=leonardodicaprioconnecticutuniversityofs-outherncaliforniabiology

2) 建立語料庫.掃描整個待清洗數(shù)據(jù)庫，根據(jù)N-Gram算法精度建立語料庫.當N值為2時，語料庫中每一個元素字符串的長度則為1，建立上述5條待清洗記錄的語料庫，如表1所示.

3) 分 割數(shù)據(jù)記錄，計算重復矩陣.按照N-Gram算法將這5條字符串分割成元字符串，例如，當N值為2時，這5條字符串經(jīng)過N-Gram算法分割后得到的字符串數(shù)組如下：

S1={“jo”，“oh”，“hn”，“nn”，…，“ut”，“te”，“er”}

S2={“to”，“om”，“mh”，“ha”，…，“op”，“ph”，“hy”}

S3={“to”，“om”，“mh”，“ha”，…，“op”，“ph”，“hy”}

S4={“ad”，“da”，“am”，“ms”，…，“en”，“nc”，“ce”}

表1 待清洗記錄語料庫
Tab.1 Corpus of records to be cleaned

名稱數(shù)量a24b5c16d9名稱數(shù)量e17f6g1h11名稱數(shù)量i31j1k3l13名稱數(shù)量m7n20o24p10名稱數(shù)量q0r21s16t16名稱數(shù)量u10v7w0x0名稱數(shù)量y11z0

S5={“l(fā)e”，“eo”，“on”，“na”，…，“l(fā)o”，“og”，“gy”}

對這些字符串數(shù)組建立重復矩陣M.在重復矩陣中，M(a，b)代表“ab”在整個數(shù)據(jù)庫中的數(shù)量，則有

4) 計算N-Gram值.根據(jù)式(4)及語料庫和重復矩陣，對這5條待清洗數(shù)據(jù)記錄進行計算，得到它們的N-Gram值，即

(p(jo)/p(o))(p(oh)/p(h))(p(hn)/p(n))…(p(er)/p(r))=

4.9×10-37

(5)

P(S2)=7.411×10-36

(6)

P(S3)=4.447×10-35

(7)

P(S4)=1.9e×10-51

(8)

P(S5)=3.7×10-50

(9)

5) 對數(shù)據(jù)進行清洗.根據(jù)步驟4)所得到的N-Gram值對待清洗數(shù)據(jù)記錄進行排序，對所得到的排序結(jié)果采用基本的字段匹配算法計算數(shù)據(jù)記錄之間的相似度，當相似度低于規(guī)定的閾值時，則判定兩者為相似重復記錄.

4 實驗結(jié)果及分析

本文根據(jù)上述算法設計了一個基于N-Gram算法的相似重復記錄數(shù)據(jù)清洗流程，通過查全率、查準率和運行速度3個因素對數(shù)據(jù)清洗過程和基于S-W算法的數(shù)據(jù)清洗技術(shù)進行對比.

查全率是評判數(shù)據(jù)清洗技術(shù)好壞的一個重要指標，查全率越高，代表所檢查出來的相似重復記錄越多，在一定程度上能夠代表數(shù)據(jù)清洗技術(shù)的性能.圖2為查全率曲線圖.從圖2中可以看出，在查全率方面，本文提出的算法較S-W算法有較大的優(yōu)勢，且隨著數(shù)據(jù)量的不斷增加，兩種算法的查全率都在不斷遞增.

圖2 查全率Fig.2 Recall ratio

查準率是評判數(shù)據(jù)清洗技術(shù)好壞的重要指標，是指所檢測出來的相似重復記錄中確實為相似重復記錄的比例，能夠真實地反映出一個算法的好壞.圖3為查準率曲線圖.從圖3中可以看出，本文提出的算法較S-W算法有較大優(yōu)勢，雖然隨著數(shù)據(jù)量的不斷增加，該優(yōu)勢有所減緩，但結(jié)合查全率的優(yōu)勢可以看出本文算法的優(yōu)點.

圖3 查準率Fig.3 Precision ratio

隨著信息的不斷發(fā)展，數(shù)據(jù)記錄的不斷增多，運行時間也作為評判一個算法好壞的標準，本文對兩種算法的運行時間進行了對比，結(jié)果如圖4所示.從圖4中可以看出，數(shù)量級較低時，S-W算法較本文算法具有較大優(yōu)勢，隨著數(shù)量級的不斷增多，S-W算法的運行時間增長迅速，超過本文算法所提出的數(shù)據(jù)清洗算法運行時間.

圖4 運行時間對比Fig.4 Runtime comparison

5 結(jié) 論

通過對相似重復數(shù)據(jù)記錄的結(jié)構(gòu)及產(chǎn)生原因進行分析，提出了一種基于N-Gram算法的相似重復記錄的數(shù)據(jù)清洗技術(shù).該方法通過計算數(shù)據(jù)記錄之間的N-Gram值，將待清洗記錄進行排序，并對排序后的結(jié)果進行相似度檢測，從而提高了相似重復記錄的查全率和查準率，且隨著數(shù)量級的不斷增加，本文算法的運行時間優(yōu)于其他算法.

[1]楊東華，李寧寧，王宏志，等.基于任務合并的并行大數(shù)據(jù)清洗過程優(yōu)化 [J].計算機學報，2016，39(1)：97-108.

(YANG Dong-hua，LI Ning-ning，WANG Hong-zhi，et al.The optimization of the big data cleaning based on task merging [J].Chinese Journal of Computers，2016，39(1)：97-108.)

[2]羅景峰，劉艷秋，許開立.基于均勻設計與灰局勢決策的智能算法參數(shù)設定 [J].沈陽工業(yè)大學學報，2010，32(1)：84-89.

(LUO Jing-feng，LIU Yan-qiu，XU Kai-li.Parameter establishment of intelligent algorithm based on uniform design and grey situation decision [J].Journal of Shenyang University of Technology，2010，32(1)：84-89.)

[3]陳明.大數(shù)據(jù)分析 [J].計算機教育，2014(5)：122-126.

(CHEN Ming.Big data analysis [J].Computer Education，2014(5)：122-126.)

[4]吳斐，唐雁，補嘉.基于N-Gram的VB源代碼抄襲檢測算法 [J].重慶理工大學學報(自然科學)，2012，26(2)：86-91.

(WU Fei，TANG Yan，BU Jia.A VB source code plagiarism detection method based onN-Gram [J].Journal of Chongqing University of Technology (Natural Science)，2012，26(2)：86-91.)

[5]邵林，黃芝平，唐貴林，等.并行緩存結(jié)構(gòu)在高速海量數(shù)據(jù)記錄系統(tǒng)中的應用 [J].計算機測量與控制，2008，16(4)：527-529.

(SHAO Lin，HUANG Zhi-ping，TANG Gui-lin，et al.Application of parallel cache structure in high-speed mass data recording system [J].Computer Measurement and Control，2008，16(4)：527-529.)

[6]周典瑞，周蓮英.海量數(shù)據(jù)的相似重復記錄檢測算法 [J].計算機應用，2013，33(8)：2208-2211.

(ZHOU Dian-rui，ZHOU Lian-ying.Algorithm for detecting approximate duplicate records in massive data [J].Journal of Computer Applications，2013，33(8)：2208-2211.)

[7]付印金，肖儂，劉芳.重復數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進展 [J].計算機研究與發(fā)展，2012，49(1)：12-20.

(FU Yin-jin，XIAO Nong，LIU Fang.Research and development on key techniques of data deduplication [J].Journal of Computer Research and Development，2012，49(1)：12-20.)

[8]Lillibridge M，Eshghi K，Bhagwat D.Improving restore speed for backup systems that use inline chunk-based deduplication [C]//Proceedings of the 11th USENIX Conference on File and Storage Technologies.New York，USA，2013：183-197.

[9]朱燦，曹健.實體解析技術(shù)綜述與展望 [J].計算機科學，2015，42(3)：8-12.

(ZHU Can，CAO Jian.Summary and prospect on entity resolution [J].Computer Science，2015，42(3)：8-12.)

[10]王琛.Web數(shù)據(jù)清洗及其系統(tǒng)框架研究 [J].計算機時代，2014(12)：42-44.

(WANG Chen.Research on Webdata cleaning and its system framework [J].Computer Era，2014(12)：42-44.)

[11]Geerts F，Mecca G，Papotti P，et al.The LLUNATIC data-cleaning framework [J].VLDB Endowment，2013，6(9)：625-636.

[12]Tan Y J，Jiang H，Sha H M，et al.SAFE：a source deduplication framework for efficient cloud backup ser-vices [J].Journal of Signal Processing Systems，2013，72(3)：209-228.

[13]殷秀葉.大數(shù)據(jù)環(huán)境下的相似重復記錄檢測方法 [J].武漢工程大學學報，2014，36(3)：66-69.

(YIN Xiu-ye.Method for detecting approximately duplicate database records in big data environment [J].Journal of Wuhan Institute of Technology，2014，36(3)：66-69.)

[14]Nguyen T T，Hui S C，Chang K.A lattice-based approach for mathematical search using formal concept analysis [J].Expert Systems with Applications，2012，39(5)：5820-5828.

[15]黨小超，高琪，郝占軍.基于小波變換的分布式WSN數(shù)據(jù)融合模型研究 [J].計算機工程與應用，2014，50(22)：97-101.

(DANG Xiao-chao，GAO Qi，HAO Zhan-jun.Research on model of distributed date aggregation in WSN based on wavelet transform [J].Computer Engineering and Applications，2014，50(22)：97-101.)

[16]譚霜，何力，陳志坤，等.云存儲中一致基于格的數(shù)據(jù)完整性驗證方法 [J].計算機研究與發(fā)展，2015，52(8)：1862-1872.

(TAN Shuang，HE Li，CHEN Zhi-kun，et al.A method of provable data integrity based on lattice in cloud storage [J].Journal of Computer Research and Deve-lopment，2015，52(8)：1862-1872.)

(責任編輯：鐘 媛 英文審校：尹淑英)

Data cleaning technology based onN-Gram algorithm

MA Ping-quan1,2, SONG Kai1,2, JI Jian-wei1

(1. College of Information and Electrical Engineering, Shenyang Agricultural University, Shenyang 110866, China; 2. School of Automation and Electrical Engineering, Shenyang Ligong University, Shenyang 110159, China)

Aiming at the plentiful approximately duplicate data in the database, the attribute structure of approximately duplicate records and the causing reason were analyzed. The data records were calculated with theN-Gram algorithm to get the key values, namelyN-Gram values, which represented the attribute of every record. According to the key values, the data records in the database were ordered so as to form a well-organized database. In addition, the similarity of data records in the database was calculated. The identified approximately duplicate records were cleaned by applying the arranged combination cleaning idea. The experimental results show that theN-Gram algorithm effectively increases the recall ratio and precision ratio of approximately duplicate data records.

similarity; approximately duplicate record; attribute; ordering; combination; data cleaning; recall ratio; precision ratio

2016-06-28.

遼寧省教育廳科學研究項目(LG201610).

馬平全(1975-)，男，遼寧丹東人，講師，博士生，主要從事信號檢測與處理等方面的研究.

17∶40在中國知網(wǎng)優(yōu)先數(shù)字出版.

http：∥www.cnki.net/kcms/detail/21.1189.T.20161222.1740.040.html

10.7688/j.issn.1000-1646.2017.01.13

TP 311.11

A

1000-1646(2017)01-0067-06