張 荃，陳 暉

（中國(guó)人民解放軍陸軍工程大學(xué)，江蘇 南京 210007）

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

如表1所示，序號(hào)1和序號(hào)2的兩行數(shù)據(jù)，屬于重復(fù)數(shù)據(jù)情況一，因?yàn)闀?shū)寫(xiě)的問(wèn)題，造成education-num實(shí)際為13，被錄入為18；序號(hào)1和序號(hào)3，屬于重復(fù)數(shù)據(jù)情況二，國(guó)家那欄存在全稱(chēng)和縮寫(xiě)的問(wèn)題；序號(hào)1和序號(hào)4，屬于重復(fù)數(shù)據(jù)情況三，兩者完全相同。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 minhash算法簡(jiǎn)介

minhash算法是LSH（Locality Sensitive Hashing，局部敏感哈希）中的一種，主要用來(lái)判斷兩個(gè)集合之間的相似性，因?yàn)檫@種方式計(jì)算的時(shí)間復(fù)雜度較低，所以適用于數(shù)據(jù)量大的集合。

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

2.2.2 minhash算法應(yīng)用

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

1）劃分shingles

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

2）設(shè)定hash函數(shù)

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

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

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

3）求取minhash簽名

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

3.1 數(shù)據(jù)來(lái)源

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

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

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

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

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

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

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

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

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

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

輸入：

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

輸出：

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

1：利用列表生成式將adult_code_data寫(xiě)入新列表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： 計(jì)數(shù)值 count+1

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

10： 將 count清零

11： if similarity＞threshold：

12： 在列表repeatnum中存入重復(fù)行的序號(hào)j

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

14：令x = 0

15：for y in repeatnum：

16： 刪除data_rows列表中的第（y-x）項(xiàng)

17： x +=1

18：以寫(xiě)入方式打開(kāi)新文件adult_clean_data.csv

19： for row in data_rows:

20： 寫(xiě)入文件adult_clean_data.csv

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

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

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

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

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

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

輸入：

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

輸出：

重復(fù)行的行號(hào)

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

2：for i 從 1 到 numDocs：

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

4： docID = words[0]

5： 在列表docNames中存入docID

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

7： 三個(gè)詞為一組形成一個(gè)shingle

8：def pickRandomCoeffs(k):

9： while k＞0:

10： randIndex =0到maxshingleID中隨機(jī)選擇一個(gè)數(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中寫(xiě)入hashCode

22： 在列表signatures中寫(xiě)入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的六個(gè)數(shù)據(jù)集，其中重復(fù)數(shù)據(jù)分別為100、200、300、1 000、2 000、3 000，分別用基于datacleaner的算法和基于minhash的算法處理數(shù)據(jù)集，選取兩個(gè)評(píng)價(jià)指標(biāo)來(lái)對(duì)比這兩種算法。

3.4.1 時(shí)間復(fù)雜度

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

圖6 算法時(shí)間對(duì)比圖

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

3.4.2 查全率

將算法消除的重復(fù)數(shù)據(jù)數(shù)量與實(shí)際的重復(fù)數(shù)據(jù)數(shù)量的比例[9，10]，定義為該算法的查全率，因?yàn)橐阎獢?shù)據(jù)的重復(fù)數(shù)量，所以可以較容易的得出這個(gè)比例值。公式如下：

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

兩個(gè)算法的比較如圖7所示。

圖7 算法查全率對(duì)比圖

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

4 結(jié) 語(yǔ)

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