基于相似重復(fù)記錄的N-Gram算法的改進(jìn)與應(yīng)用

王旭東，段敬，溫志堅(jiān)，樓穎稚，陳偉，孔德云，黃豆豆

（1.國(guó)網(wǎng)山西省電力公司信息通信分公司，太原 030001；2.北京中電普華信息技術(shù)公司，北京 110000）

0 引言

隨著大數(shù)據(jù)時(shí)代的快速發(fā)展，數(shù)據(jù)的質(zhì)量問(wèn)題無(wú)疑成為相關(guān)人士的研究重點(diǎn)之一。由于數(shù)據(jù)量特別龐大，導(dǎo)致人們?cè)谑褂脭?shù)據(jù)的過(guò)程中發(fā)現(xiàn)了諸多的質(zhì)量問(wèn)題，例如臟數(shù)據(jù)，其中最突出的問(wèn)題之一就是存在很多相似重復(fù)數(shù)據(jù)，為此，本文將針對(duì)數(shù)據(jù)的相似重復(fù)性展開(kāi)深入地研究。

本文通過(guò)研究N-Gram算法，發(fā)現(xiàn)了其存在兩個(gè)缺陷，一是其只針對(duì)英文數(shù)據(jù)庫(kù)，缺少對(duì)漢字的處理；二是對(duì)待清洗數(shù)據(jù)進(jìn)行相似去重操作時(shí)，由于比較時(shí)采用特定大小的滑動(dòng)窗口，降低了去重效率?；谝陨蟽蓚€(gè)問(wèn)題，特提出了一種改進(jìn)的N-Gram算法，不僅引入了適合中文數(shù)據(jù)庫(kù)的算法，而且在對(duì)相似度高的數(shù)據(jù)記錄進(jìn)行去重操作時(shí)，采用動(dòng)態(tài)滑動(dòng)窗口策略，大大提高了算法的精確度。

1 數(shù)據(jù)預(yù)處理

（1）對(duì)待清洗的數(shù)據(jù)記錄進(jìn)行預(yù)處理時(shí)，需要去掉記錄中的所有的空格、換行、&、*、/等特殊符號(hào)以及一些難以辨識(shí)或無(wú)任何含義的字符。

（2）例如一些不能公開(kāi)的數(shù)據(jù)（身份證號(hào)、銀行卡號(hào)、手機(jī)號(hào)等）或者在數(shù)據(jù)庫(kù)中存在的大量的相同的字符串（如金額單位），通常用特殊字符******、￥等代替。

（3）對(duì)于數(shù)據(jù)記錄中的所有大小寫(xiě)不一的字母，統(tǒng)一大寫(xiě)或小寫(xiě)，便于比對(duì)。

（4）對(duì)于一些人名、地名、機(jī)構(gòu)名等，通常用眾所周知的簡(jiǎn)稱(chēng)進(jìn)行替換，如地名“上?！迸c“滬”可以相互替換。

（5）例如對(duì)電網(wǎng)PMS系統(tǒng)的數(shù)據(jù)進(jìn)行預(yù)處理時(shí)，首先刪除掉擴(kuò)展字段（在對(duì)數(shù)據(jù)進(jìn)行遷移過(guò)程中所設(shè)定的標(biāo)志字段），然后僅對(duì)PMS系統(tǒng)的業(yè)務(wù)字段進(jìn)行一一匹配，并計(jì)算出相似度。

2 算法過(guò)程描述

2.1 N-Gram算法過(guò)程（適用于英文和數(shù)值）

（1）思想：

任何一條數(shù)據(jù)記錄與構(gòu)成其的每一個(gè)詞都是息息相關(guān)的，因此，我們可以根據(jù)每個(gè)詞出現(xiàn)的概率，通過(guò)計(jì)算得出整條記錄的概率，即N-Gram值。該值代表了該條記錄的屬性，如果任意N條記錄的屬性值越相近，說(shuō)明這N條記錄的數(shù)據(jù)相似度越高，即N條記錄的數(shù)據(jù)重復(fù)的可能性越高，有助于我們進(jìn)行去重操作。

對(duì)預(yù)處理后的某條記錄進(jìn)行二元分割，即列出該條記錄所有長(zhǎng)度為2的子字符串，假設(shè)該條記錄的字符總長(zhǎng)為S，那么它的二元子字符串的個(gè)數(shù)就是S-N+1（其中N為固定窗口大小，此處N=2）。首先通過(guò)統(tǒng)計(jì)語(yǔ)料庫(kù)得出所有二元子串和單詞的數(shù)量，然后利用馬爾科夫概率計(jì)算公式，得出每條記錄的N-Gram值并將其作為自身的鍵值，最后對(duì)所有記錄按照既定的排序算法和排序規(guī)則進(jìn)行排序。

所謂二元，即每條記錄的所有的詞，只與它前面最相近的那個(gè)詞有關(guān)，概率公式如下：

由于 P（W3|W1W2）比較難算，P（Wn|W1W2…Wn-1）更加難算，馬爾科夫提出一個(gè)假設(shè)，即每條記錄中下一個(gè)詞的出現(xiàn)僅僅依賴(lài)于前一個(gè)詞的出現(xiàn)，從而將N-Gram的概率公式簡(jiǎn)化為

（2）N-Gram算法流程

N-Gram算法流程大致分為三步，一是遍歷整個(gè)待清洗的數(shù)據(jù)庫(kù)，進(jìn)而得到該數(shù)據(jù)庫(kù)的語(yǔ)料庫(kù)和重復(fù)矩陣M；二是利用重復(fù)矩陣M計(jì)算數(shù)據(jù)庫(kù)中所有記錄的N-Gram值；三是根據(jù)N-Gram值的大小對(duì)所有數(shù)據(jù)記錄進(jìn)行合理排序。

2.2中文數(shù)據(jù)清洗過(guò)程

中文數(shù)據(jù)清洗采用的是中文字段匹配算法，該算法使用了典型文本字段的回歸結(jié)構(gòu)。算法的基本思想是先將A、B兩個(gè)字符串進(jìn)行分詞操作，生成各自的子字符串，然后將A的各個(gè)子串與B的子串進(jìn)行一一匹配，同時(shí)記錄兩個(gè)子串匹配度的最高情形。如果A的一個(gè)子字符串和B的一個(gè)子字符串是完全一樣的或者其中一個(gè)子串是另一個(gè)子串的簡(jiǎn)寫(xiě)形式，則相似度定為1，否則是0。依次遞歸匹配A的下一個(gè)子串，最后利用以下公式計(jì)算出字符串A和B的相似度，從而判定其相似性。A和B的相似度計(jì)算公式如下所示：

對(duì)于中文而言，其縮寫(xiě)通常僅有一種形式，即分詞首漢字的組合，例如：“山大”是“山東大學(xué)”的簡(jiǎn)稱(chēng)。本文采用Word 2000中的漢語(yǔ)自動(dòng)分詞系統(tǒng)對(duì)要匹配的字段進(jìn)行自動(dòng)分詞，或者說(shuō)是在字段文本中通過(guò)調(diào)用Word 2000來(lái)達(dá)到對(duì)分詞進(jìn)行切分標(biāo)記的目的。如“山大和北大都是大學(xué)”，該句自動(dòng)分詞后變?yōu)椤吧?大*和*北大*都是*大學(xué)*”。由此推出，“山大”被定為多個(gè)詞，而北大是一個(gè)詞。因此在對(duì)北京大學(xué)和北大進(jìn)行匹配時(shí)，可以使用外部文件處理替換后再進(jìn)行匹配，而對(duì)“山東大學(xué)”和“山大”的匹配，需要用算法對(duì)其進(jìn)行特殊處理?；貧w的中文字段匹配框架如圖1所示：

圖1 回歸中文字段匹配框架

（1）預(yù)處理1：首先用外部文件（表示領(lǐng)域知識(shí)的文件）對(duì)待匹配的字段值進(jìn)行處理，例如地址名詞“滬”即表示“上?！?，在下一步分詞時(shí)，將不對(duì)其進(jìn)行任何操作。

（2）預(yù)處理2：利用漢語(yǔ)自動(dòng)分詞技術(shù)，對(duì)經(jīng)過(guò)預(yù)處理1步驟后的結(jié)果字符序列進(jìn)行二次處理，如此一來(lái)，進(jìn)行過(guò)兩次預(yù)處理的字段值就會(huì)演變成含有分詞標(biāo)記的字符。

（3）經(jīng)過(guò)圖1所示的兩次處理后，便可以用回歸的中文字段匹配算法對(duì)字段值進(jìn)行進(jìn)一步的匹配。利用算法的相似度公式，計(jì)算出兩個(gè)字段值的相似度，也叫相似性。

3 算法改進(jìn)與效率優(yōu)化

改進(jìn)的N-Gram算法流程圖如圖2所示。

3.1本文算法原理

由于N-Gram算法是針對(duì)英文數(shù)據(jù)庫(kù)的，整個(gè)數(shù)據(jù)庫(kù)中只含有英文字符和數(shù)值，而實(shí)際上數(shù)據(jù)庫(kù)里的數(shù)據(jù)記錄除了英文和數(shù)值還有中文，因此需要引入中文數(shù)據(jù)庫(kù)的清洗算法，例如第2節(jié)提到的回歸中文字段匹配算法。假設(shè)有兩條記錄A和B，通過(guò)N-Gram算法所求得的概率分別為 P（SA）和 P（SB），通過(guò)回歸的中文字段匹配算法所求得的兩條記錄的相似度為match（A,B）和 match（B,A）（理論上 match（A,B）等于match（B,A））。

圖2 改進(jìn)的N-Gram算法流程圖

對(duì)N-Gram算法和回歸的中文字段匹配算法進(jìn)行合并，為了精確計(jì)算相似度，我們采用加權(quán)法（權(quán)重值的計(jì)算是按字節(jié)數(shù)占比計(jì)算的，一個(gè)中文占2個(gè)字節(jié)，一個(gè)英文或數(shù)值占1個(gè)字節(jié)），記錄A的相似度P（A）=1 match（A,B）+2 P（SA）,記錄 B 的相似度 P（B）=3 match（B,A）+4 P（SB），其中1是記錄A中文所占比例，記錄A英文或數(shù)值所占比例，3是記錄B中文所占比例，4是記錄B英文或數(shù)值所占比例。最后，通過(guò)比較P（A）與P（B）的值來(lái)得出相似重復(fù)記錄。

3.2動(dòng)態(tài)滑動(dòng)窗口策略

N-Gram算法在進(jìn)行相似重復(fù)記錄去重操作前，采用滑動(dòng)窗口的方法對(duì)待清洗數(shù)據(jù)進(jìn)行組內(nèi)比較。假設(shè)待清洗數(shù)據(jù)記錄數(shù)為W，N為窗口大小，則每次只比較窗口中的N條數(shù)據(jù)，而不是把每一條數(shù)據(jù)和剩余的其他所有數(shù)據(jù)進(jìn)行一一匹配。當(dāng)使用N-Gram算法時(shí)，滑動(dòng)固定大小窗口的次數(shù)為W-N+1，同時(shí)形成W-N+1個(gè)大小均為N的且相互重疊的窗口，具體如圖3所示。

由于N-Gram算法的滑動(dòng)窗口大小難以確定，而且要對(duì)窗口內(nèi)的所有記錄進(jìn)行比對(duì)，所以效率比較低，從而影響去重的準(zhǔn)確度。例如待清洗數(shù)據(jù)用W表示，則|W|為數(shù)據(jù)的長(zhǎng)度，如果將W分割成二元字符串集，其時(shí)間復(fù)雜度為O（|W|）2，如果將其分割成三元字符串集，則它的時(shí)間復(fù)雜度變?yōu)镺（|W|）3，如此的話(huà)，當(dāng)窗口大小越大時(shí)，分割后的字符串就會(huì)越大，所計(jì)算出的相似度就會(huì)愈加精確，對(duì)應(yīng)的時(shí)間復(fù)雜度就會(huì)隨之增大；相反，如果窗口大小選擇的越小時(shí)，其相應(yīng)的時(shí)間復(fù)雜度就會(huì)愈小，造成的花銷(xiāo)也會(huì)隨之降低。但是這樣的話(huà)，會(huì)因?yàn)樽址^(guò)小，導(dǎo)致后續(xù)進(jìn)行排序合并的時(shí)候，難以有效地聚合相似重復(fù)記錄，進(jìn)而導(dǎo)致部分?jǐn)?shù)據(jù)記錄被遺漏，影響相似度值的計(jì)算結(jié)果，進(jìn)而影響到算法的精確度。

圖3 滑動(dòng)窗口掃描排序數(shù)據(jù)集示意圖

針對(duì)這一缺陷，本論文采用動(dòng)態(tài)滑動(dòng)窗口的NGram算法，窗口的大小由當(dāng)前窗口的大小、窗口內(nèi)第一條和最后一條記錄的距離以及最短記錄閾值確定。在算法開(kāi)始運(yùn)行的時(shí)候，為窗口設(shè)置一個(gè)最初的值，后續(xù)窗口的大小則在算法執(zhí)行中動(dòng)態(tài)得出。我們一般把窗口中的第一個(gè)和最后一個(gè)記錄之間的距離，即為窗口的大小。這樣可以去掉很多無(wú)用的比較操作，提升數(shù)據(jù)清洗效率。如果窗口內(nèi)第一個(gè)和最后一個(gè)記錄之間的距離等于距離閾值φ，這里我們默認(rèn)取φ=2，我們稱(chēng)其為最理想狀態(tài)。窗口是當(dāng)前正在處理的窗口Win?dow1，記錄r1和rw1分別表示窗口內(nèi)的第一條和最后一條記錄，二者之間的距離滿(mǎn)足distance（r1,rw1）＜φ,此時(shí)窗口Window1內(nèi)各記錄之間的平均距離為下一步窗口的大小需要通過(guò)以下公式推理：

推理得出：

4 實(shí)驗(yàn)結(jié)果與討論

（1）實(shí)驗(yàn)環(huán)境

硬件：一臺(tái)PC，操作系統(tǒng)：Windows 7 64位操作系統(tǒng)

軟件：GBase 8a MPP Cluster，GBase client 8.6.2.18-R2.82869

（2）實(shí)驗(yàn)數(shù)據(jù)分析

為了確保實(shí)驗(yàn)效果，以PMS系統(tǒng)的部分表數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)的總記錄條數(shù)為10326。在對(duì)數(shù)據(jù)進(jìn)行清洗前，首先對(duì)字段進(jìn)行合理地分類(lèi)并進(jìn)行預(yù)先處理；然后采用二元算法，分別計(jì)算不同數(shù)據(jù)類(lèi)型之間的N-Gram值，并對(duì)其進(jìn)行合并，獲得整條記錄的N-Gram值；最后根據(jù)N-Gram值對(duì)其進(jìn)行合理排序后，篩選出相似度大于某一閾值的數(shù)據(jù)記錄并進(jìn)行清洗，從而實(shí)現(xiàn)清洗數(shù)據(jù)的目的。本次試驗(yàn)數(shù)據(jù)來(lái)源于PMS系統(tǒng)，具體如表1-3所示（由于篇幅有限，在此僅列出部分?jǐn)?shù)據(jù)）：

表1 實(shí)驗(yàn)數(shù)據(jù)表

表2 實(shí)驗(yàn)數(shù)據(jù)表

表3 實(shí)驗(yàn)數(shù)據(jù)表

（3）實(shí)驗(yàn)結(jié)果分析

通過(guò)對(duì)PMS系統(tǒng)中的10326條實(shí)驗(yàn)數(shù)據(jù)進(jìn)行預(yù)處理，并且去掉難以辨識(shí)的字符和特殊符號(hào)，分別計(jì)算它們的N-Gram值，結(jié)果如圖4所示：

圖4 數(shù)據(jù)相似度

通過(guò)對(duì)圖4進(jìn)行分析，我們?nèi)〕鱿嗨贫却笥?.8的所有數(shù)據(jù)并將它們作為待清洗的數(shù)據(jù)，去除相似重復(fù)記錄，保留準(zhǔn)確數(shù)據(jù)，并按照清洗結(jié)果，對(duì)待清洗數(shù)據(jù)庫(kù)進(jìn)行更新和格式化。

在此處，通過(guò)實(shí)驗(yàn)?zāi)M，對(duì)本文提出的改進(jìn)的NGram算法與第2節(jié)所提到的傳統(tǒng)的N-Gram算法、回歸的中文字段匹配算法進(jìn)行比較，具體從查全率、查準(zhǔn)率、運(yùn)行時(shí)間等三方面展開(kāi)。查準(zhǔn)率和查全率的計(jì)算方法為：

圖5 各算法查全率比較

圖6 各算法查準(zhǔn)率比較

圖7 各算法運(yùn)行時(shí)間比較

5 結(jié)語(yǔ)

本文針對(duì)N-Gram算法進(jìn)行了優(yōu)化，先是基于NGram是針對(duì)英文數(shù)據(jù)庫(kù)的特點(diǎn)，將回歸的中文字段匹配算法引入其中，無(wú)論是查全率還是查準(zhǔn)率，都在一定程度上得以提高；然后為了在對(duì)待清洗數(shù)據(jù)進(jìn)行相似度比較后，能夠快速且準(zhǔn)確地刪除掉相似重復(fù)數(shù)據(jù)，特別引入了動(dòng)態(tài)滑動(dòng)窗口的想法，大大減少了比較次數(shù)，減少了算法的運(yùn)行時(shí)間，提高算法的運(yùn)行速率。