張 荃，陳 暉

（中國人民解放軍陸軍工程大學，江蘇 南京 210007）

0 引 言

當今的互聯(lián)網(wǎng)時代，“大數(shù)據(jù)”自提出以來就受到了人們的關注，它指的是一種規(guī)模大到在獲取、存儲、管理、分析方面大大超出了傳統(tǒng)數(shù)據(jù)庫軟件工具能力范圍的數(shù)據(jù)集合。大數(shù)據(jù)的價值在于對數(shù)據(jù)進行專業(yè)化處理，深度挖掘其中隱藏的信息，從而幫助對現(xiàn)有的數(shù)據(jù)進行處理，或者是對未來的工作做出合理預測等等[1]。

在大數(shù)據(jù)的應用中，數(shù)據(jù)挖掘是一個有效的方法，它一般分為數(shù)據(jù)采集、數(shù)據(jù)預處理、數(shù)據(jù)挖掘和數(shù)據(jù)呈現(xiàn)四個部分[2]。每個部分的工作量相關統(tǒng)計如圖1所示，可以清晰的看出，數(shù)據(jù)預處理是數(shù)據(jù)挖掘中的一個重要環(huán)節(jié)。從大數(shù)據(jù)的“低價值密度”這個特點的角度出發(fā)，也可以看出，大數(shù)據(jù)中存在很多無價值的數(shù)據(jù)，在挖掘大數(shù)據(jù)價值前，必須對數(shù)據(jù)進行預處理。

圖1 數(shù)據(jù)挖掘各項工作量占比

重復數(shù)據(jù)是數(shù)據(jù)庫中影響數(shù)據(jù)質(zhì)量的常見問題之一，它的存在破壞了數(shù)據(jù)的唯一性，占用數(shù)據(jù)庫的空間，降低了運行效率。清除重復數(shù)據(jù)，是提高數(shù)據(jù)挖掘有效性，充分發(fā)揮數(shù)據(jù)庫作用的重要環(huán)節(jié)之一。因此，本文主要針對重復數(shù)據(jù)進行處理，按照先對數(shù)據(jù)進行編碼轉(zhuǎn)換，再計算Jaccard相似度，從而找出重復的數(shù)據(jù)的思路?，F(xiàn)有的方法主要采用了datacleaner[3]的基礎模塊找出重復數(shù)據(jù)，由于需要對每個屬性單獨進行編碼，相對繁瑣。我們創(chuàng)新性的將數(shù)據(jù)轉(zhuǎn)換為一段文字，利用最小哈希（minhash）編碼方式[4]對該段文字進行統(tǒng)一的編碼，再計算Jaccard相似度，從而找出重復的數(shù)據(jù)。當數(shù)據(jù)量逐步增大時，minhash算法明顯縮短了運算時間，提升了重復數(shù)據(jù)處理的效率。

1 相關工作

1.1 重復數(shù)據(jù)定義

重復數(shù)據(jù)可以簡單的理解為具有相同信息的數(shù)據(jù)，本文主要針對人員數(shù)據(jù)集進行處理，同一個人的相同屬性的數(shù)據(jù)為重復數(shù)據(jù)。在現(xiàn)實生活中，一個人的各項信息可能被多次統(tǒng)計，例如在校園生活中，一個學生的信息被輔導員、授課教師、后勤管理者等分別統(tǒng)計過，當整個學校的人員信息匯集在一起后，該學生的信息將多次出現(xiàn)。本文中處理的重復數(shù)據(jù)主要包含以下幾類[5]：

（1）因填寫時筆誤、錄入電腦時識別不清等原因，造成數(shù)據(jù)的內(nèi)容存在一定程度的不同，但實際代表的是同一個人的信息。

（2）錄入數(shù)據(jù)時規(guī)定的不一樣，存在有時候?qū)懙氖侨Q，有時候?qū)懙氖强s寫，實際為同一信息的情況。

（3）數(shù)據(jù)來源于多個數(shù)據(jù)源，合并時產(chǎn)生的重復數(shù)據(jù)。

如表1所示，序號1和序號2的兩行數(shù)據(jù)，屬于重復數(shù)據(jù)情況一，因為書寫的問題，造成education-num實際為13，被錄入為18；序號1和序號3，屬于重復數(shù)據(jù)情況二，國家那欄存在全稱和縮寫的問題；序號1和序號4，屬于重復數(shù)據(jù)情況三，兩者完全相同。

表1 重復數(shù)據(jù)實例

1.2 重復數(shù)據(jù)清洗基本思路

處理重復數(shù)據(jù)的基本思路是：首先對數(shù)據(jù)進行編碼轉(zhuǎn)換，計算兩行數(shù)據(jù)間的相似度，當相似度大于閾值時，認定為重復數(shù)據(jù)[6]。計算相似度的方法有很多，歐式距離、漢明距離、Jaccard距離等，本文選取Jaccard系數(shù)，作為數(shù)據(jù)間相似程度的度量。

Jaccard系數(shù)的定義為，給定兩個集合A和B，Jaccard系數(shù)定義為集合A和集合B的交集與兩者并集的比值，即為：

Jaccard系數(shù)可以衡量集合的相似程度，越接近的集合，Jaccard系數(shù)值越高。

2 重復數(shù)據(jù)清洗算法

2.1 基于datacleaner和Jaccard系數(shù)的重復數(shù)據(jù)清洗

這種處理重復數(shù)據(jù)的思路就是：首先，利用datacleaner對數(shù)據(jù)進行編碼，接著計算出每兩行數(shù)據(jù)之間的Jaccard系數(shù)，根據(jù)Jaccard系數(shù)性質(zhì)，數(shù)值越大，說明兩行的數(shù)據(jù)越接近，當高于閾值時認為該兩行數(shù)據(jù)為重復行，刪除其中一行。Datacleaner是具有基礎編碼功能的模塊，可以實現(xiàn)用數(shù)值去編碼非數(shù)值變量，主要工作流程是：

1）數(shù)據(jù)中是數(shù)值變量的列，保留原有的數(shù)值，例如本文選用的人員數(shù)據(jù)中的age、education-num等；

2）數(shù)據(jù)中非數(shù)值變量的列，如workclass、education等，首先計算該列共有幾種不同變量記為n，然后將0到（n-1）的整數(shù)隨機的分配給這n種變量，完成非數(shù)值變量的編碼。

該方法的優(yōu)點是通過逐行比較所有數(shù)據(jù)，能夠較好的找出重復數(shù)據(jù)，算法的查全率和正確率都比較高。但也具有明顯的缺點，由于算法需要對每兩行數(shù)據(jù)進行對比，并將兩行數(shù)據(jù)中的每個元素進行對比，因此時間復雜度會很高，算法的效率較低。當數(shù)據(jù)量達到一定數(shù)量的時候，算法的耗時將難以估計。

2.2 基于minhash算法的重復數(shù)據(jù)清洗

為了解決時間復雜度問題，本文將minhash算法引入處理表格類數(shù)據(jù)的問題中。minhash算法一般是用于比較兩個集合或者兩個文檔間的相似度，在應用于表格類數(shù)據(jù)時，本文創(chuàng)新的將數(shù)據(jù)轉(zhuǎn)換為文檔，再利用算法計算相似度。

2.2.1 minhash算法簡介

minhash算法是LSH（Locality Sensitive Hashing，局部敏感哈希）中的一種，主要用來判斷兩個集合之間的相似性，因為這種方式計算的時間復雜度較低，所以適用于數(shù)據(jù)量大的集合。

主要功能有兩個：一是估算兩個集合的相似度，minhash可以控制計算值與實際值的誤差范圍，保證計算值得準確率；二是縮短計算的時間，傳統(tǒng)的方法需要逐行逐項比對集合中的值，當數(shù)據(jù)量很大時，會造成運算時間成幾何倍上漲，該算法中通過先提取出相似對，再進行逐項比對的方法，減少了很多工作量，從而縮短了時間。

2.2.2 minhash算法應用

minhash算法的實現(xiàn)流程一般為，將文檔劃分成子字符串（shingles），再利用哈希（hash）函數(shù)構(gòu)建簽名，最后對比簽名從而獲得相似度[7]。

1）劃分shingles

Shingles的定義是文檔中的子字符串，k-shingles指的是文檔中找到的長度為k的任何子字符串。目的是將文檔的長字符串，劃分為短字符串，這樣在比較字符串是否相等時，保留了文檔結(jié)構(gòu)的一部分，而不是僅僅看單個單詞，這樣當出現(xiàn)單詞順序排列不同但語意相同的情況時，更容易識別出來。本文中設定k=3，即從文檔中提取任意連續(xù)三個單詞的字符串。

2）設定hash函數(shù)

取x為整數(shù)，則hash函數(shù)為：

系數(shù)a和系數(shù)b是隨機選取的小于x最大值的整數(shù)。c是一個質(zhì)數(shù)，略大于x最大值。通過選擇不同的a、b、c的值，可以得到不同的hash函數(shù)。

值得一提的是，調(diào)動學生的情緒并非是靈丹妙藥。在調(diào)動學生情緒時也要注意：忌濫用成災，要適可而止；忌牽強附會，要恰到好處；忌矯揉造作，要新穎自然。

3）求取minhash簽名

生成五個不同hash函數(shù)，取第一個hash函數(shù)，并將其應用于文檔中的所有shingle值，得到的所有值中最小值作為minhash簽名的第一個值。現(xiàn)在使用第二個hash函數(shù)，再次找到計算得到的最小哈希值，作為簽名的第二個值，以此類推，可以得到minhash簽名的完整向量，里面有五個值。對數(shù)據(jù)集中的每個文檔使用相同的五個哈希函數(shù)，并生成它們的簽名，然后可以通過計算相同的簽名數(shù)量來判斷文檔間的相似度。

2.3 數(shù)據(jù)轉(zhuǎn)換

對于表格類數(shù)據(jù)，對數(shù)據(jù)進行編碼時需要對每個元素分別進行編碼，通過逐行比較每列的對應元素，計算兩行數(shù)據(jù)的相似度。這種方法存在很多冗余的計算，時間復雜度很高，為了解決這個問題，本文將使用minhash算法優(yōu)化編碼方式，降低時間復雜度。

由于minhash算法是對集合進行處理，因此需要先對數(shù)據(jù)進行數(shù)據(jù)轉(zhuǎn)換，即將表格類數(shù)據(jù)轉(zhuǎn)換為文檔集合。圖2展示的是未進行數(shù)據(jù)轉(zhuǎn)換的數(shù)據(jù)，圖3為通過數(shù)據(jù)轉(zhuǎn)換后得到的文檔集合。

圖2 轉(zhuǎn)換前數(shù)據(jù)展示

圖3 轉(zhuǎn)換后數(shù)據(jù)展示

3 實驗驗證

3.1 數(shù)據(jù)來源

本文中使用的數(shù)據(jù)，來源于UCI公共數(shù)據(jù)集（UCI Public dataset），這個數(shù)據(jù)集是一個常用的標準測試數(shù)據(jù)集，主要用于提供機器學習和數(shù)據(jù)挖掘的訓練數(shù)據(jù)集。本次選用的數(shù)據(jù)集，是從1994年人口普查數(shù)據(jù)中提取的真實數(shù)據(jù)，主要包括：age（年齡）、workclass（工作種類）、education（教育情況）、education-num（受教育年限）、occupation（職業(yè)情況）、marital-status（婚姻狀況）、race（種族）、sex（性別）、hours-per-week（每周工作時間）、native-country（國籍等信息）。

人員數(shù)據(jù)是日常工作生活中常見的數(shù)據(jù)類別，一個人的信息可能被多個部門多次采集，容易產(chǎn)生重復數(shù)據(jù)，實現(xiàn)人員數(shù)據(jù)的清洗，更貼近工作生活的需求，對于現(xiàn)實問題具有借鑒意義。

3.2 基于datacleaner模塊的重復數(shù)據(jù)算法實現(xiàn)

3.2.1 數(shù)據(jù)編碼

通過datacleaner模塊，對數(shù)據(jù)進行編碼，編碼效果如圖4、圖5所示。

圖4 編碼前數(shù)據(jù)展示

圖5 編碼后數(shù)據(jù)展示

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

重復數(shù)據(jù)清洗的具體代碼實現(xiàn)描述如下：

算法1 基于datacleaner模塊的重復數(shù)據(jù)清洗

輸入：

編碼后的數(shù)據(jù)集adult_code_data.csv

輸出：

清洗后的數(shù)據(jù)集adult_clean_data.csv

1：利用列表生成式將adult_code_data寫入新列表data_rows中

2：for i 從 1 到 len(data_rows)-1:

3： for j 從 i+1 到 len(data_rows)：

4： 在列表list1中存入data_rows[i]

5： 在列表list2中存入data_rows[j]

6： for n 從1到data_rows總列數(shù)：

7： if list1[n] == list2[n]

8： 計數(shù)值 count+1

9： similarity = count/(列數(shù)*2 -count)

10： 將 count清零

11： if similarity＞threshold：

12： 在列表repeatnum中存入重復行的序號j

13：清除repeatnum中的重復數(shù)字

14：令x = 0

15：for y in repeatnum：

16： 刪除data_rows列表中的第（y-x）項

17： x +=1

18：以寫入方式打開新文件adult_clean_data.csv

19： for row in data_rows:

20： 寫入文件adult_clean_data.csv

3.3 基于minhash的重復數(shù)據(jù)算法實現(xiàn)

3.3.1 數(shù)據(jù)轉(zhuǎn)換

我們獲得的數(shù)據(jù)是csv格式的，首先對數(shù)據(jù)進行轉(zhuǎn)換，主要目的是將數(shù)據(jù)轉(zhuǎn)換為文檔的樣式，轉(zhuǎn)換結(jié)果已在上文提到，此處不進行贅述。

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

算法實現(xiàn)描述如下：

算法2 基于minhash算法的重復數(shù)據(jù)清洗

輸入：

創(chuàng)新成文檔格式的adult_articles.train

輸出：

重復行的行號

1：定義hash函數(shù)個數(shù)為numHashes，文檔行數(shù)為numDocs

2：for i 從 1 到 numDocs：

3： 將第i行的每個詞存入列表words中

4： docID = words[0]

5： 在列表docNames中存入docID

6： for index 從 0 到 len(words)-2:

7： 三個詞為一組形成一個shingle

8：def pickRandomCoeffs(k):

9： while k＞0:

10： randIndex =0到maxshingleID中隨機選擇一個數(shù)

11： 在列表randlist中存入randIndex

12： k = k-1

13： return randList

14：coeffA = pickRandom(numHashes)

15：coeffB = pickRandom(numHashes)

16：for docID in docNames:

17： shingleIDSet = 第docID行的shingle

18： for i 從 0 到 numHashes：

19： for shingleID in shingleIDSet：

20： hashCode=(coeffA[i]*

shingleID+coeffB[i])%nextPrime

21： 在列表signature中寫入hashCode

22： 在列表signatures中寫入signature，得到文檔第docID行完整簽名

23：for i 從 0 到 numDocs：

24： sig1 = signatures[i]

25： for j 從 i+1 到 numDocs：

26： sig2 = signatures[j]

27： for k 從 0 到 numHashes：

28： count = count +(sig1[k]== sig2[k])

29： estJsim = count/numHashes

30： if estJsim＞threshold:

31： 輸出 docNames[i]和

docNames[j]

3.4 算法比較

將我們選取的數(shù)據(jù)集，截取其中一部分人員信息，構(gòu)成數(shù)據(jù)量為500、800、1 000、3 000、5 000、10 000的六個數(shù)據(jù)集，其中重復數(shù)據(jù)分別為100、200、300、1 000、2 000、3 000，分別用基于datacleaner的算法和基于minhash的算法處理數(shù)據(jù)集，選取兩個評價指標來對比這兩種算法。

3.4.1 時間復雜度

這兩種算法都按照先將數(shù)據(jù)轉(zhuǎn)換編碼，再計算相似度的方法，從數(shù)據(jù)編碼開始，到完成相似度計算的時間[8]，六個數(shù)據(jù)集通過兩種算法運行后的具體時間如圖6所示。

圖6 算法時間對比圖

我們可以看出，當數(shù)據(jù)量逐步增大的時候，minhash算法的時間明顯小于datacleaner算法，說明minhash算法在處理大數(shù)據(jù)量數(shù)據(jù)時，具有時間優(yōu)勢。

3.4.2 查全率

將算法消除的重復數(shù)據(jù)數(shù)量與實際的重復數(shù)據(jù)數(shù)量的比例[9，10]，定義為該算法的查全率，因為已知數(shù)據(jù)的重復數(shù)量，所以可以較容易的得出這個比例值。公式如下：

Nt表示算法消除的重復數(shù)據(jù)個數(shù)，N表示實際的重復數(shù)據(jù)個數(shù)。

兩個算法的比較如圖7所示。

圖7 算法查全率對比圖

從圖7中可以看出，datacleaner算法和minhash算法的查全率基本相同，都能將大部分的重復數(shù)據(jù)找出。

4 結(jié) 語

本文主要是實現(xiàn)了重復數(shù)據(jù)清洗的工作，主要思路是對數(shù)據(jù)進行編碼后，計算相似度，從而找出重復數(shù)據(jù)。比較了基于datacleaner算法和基于minhash算法的兩種清洗方式，創(chuàng)新的將人員數(shù)據(jù)轉(zhuǎn)換為文檔格式進行編碼，基于minhash算法的方式在時間復雜度上進行了優(yōu)化，得到了明顯的效果。如何更好的提高清洗算法的查全率是下步研究的重點。