張平，程新蓮

（1.安徽職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，安徽 合肥 230011；2.嘉善萬順達(dá)電子有限公司，浙江 嘉興 314100）

0 引 言

目前大多數(shù)企業(yè)的業(yè)務(wù)系統(tǒng)積累了大量業(yè)務(wù)數(shù)據(jù)，其中不乏許多的冗余數(shù)據(jù)，嚴(yán)重影響了數(shù)據(jù)分析和數(shù)據(jù)挖掘的結(jié)果，冗余的數(shù)據(jù)導(dǎo)致數(shù)據(jù)價(jià)值密度低。為了能夠從數(shù)據(jù)中獲取更精準(zhǔn)的有價(jià)值的信息，有必須對(duì)數(shù)據(jù)進(jìn)行清洗，也成為數(shù)據(jù)預(yù)處理。數(shù)據(jù)清洗就是從大量的數(shù)據(jù)中找出重復(fù)、無用或歧義的數(shù)據(jù)并去除，其中檢測(cè)出這些臟數(shù)據(jù)尤為重要。

近些年來國(guó)內(nèi)外很多學(xué)者和專家都重視數(shù)據(jù)清洗工作的研究，大量學(xué)者都專注于相似重復(fù)記錄檢測(cè)的研究，相似重復(fù)記錄檢測(cè)是數(shù)據(jù)清洗工作的重要環(huán)節(jié)。目前大數(shù)據(jù)具有維度高、數(shù)據(jù)量大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜等特點(diǎn)，導(dǎo)致傳統(tǒng)的檢測(cè)方法對(duì)大數(shù)據(jù)的相似重復(fù)數(shù)據(jù)檢測(cè)時(shí)間效率和準(zhǔn)確率都不高，大量的排序和比較工作耗費(fèi)大量的時(shí)間，加上數(shù)據(jù)復(fù)雜，很多算法都不能有效進(jìn)行檢測(cè)，因此，本文根據(jù)大數(shù)據(jù)的特點(diǎn)提出了通過聚類分組后再檢測(cè)相似重復(fù)記錄的方法，提高了檢測(cè)效率和檢測(cè)的準(zhǔn)確率。

1 相似重復(fù)記錄

大數(shù)據(jù)中的重復(fù)數(shù)據(jù)又分為完全重復(fù)數(shù)據(jù)和相似重復(fù)數(shù)據(jù)兩種情形。如果數(shù)據(jù)集中存在兩條記錄，除了主鍵字段不同，其他字段的值都相同，那么這兩條記錄即為完全重復(fù)數(shù)據(jù)。如果數(shù)據(jù)集中存在兩條記錄，除了主鍵字段不同以外其他字段在描述或格式書寫上存在差異，但是表示的內(nèi)在含義是相同的兩條記錄即為相似重復(fù)記錄。如表1所示。

表1 學(xué)生信息表

如表1所示學(xué)號(hào)為100001和100002的兩條記錄，除了主鍵字段不同以外，其他字段的值都是完全相同的，故為完全重復(fù)記錄，而學(xué)號(hào)100001和100003的兩條記錄，除了主鍵字段相同以外，其他字段存在雖然表示方法不一樣，但是含義是一樣的字段，比如性別字段“1”表示男性的意思；還存在字段值意思相同的簡(jiǎn)稱表示，比如學(xué)校使用全稱和簡(jiǎn)稱表示，其實(shí)表示的都是一個(gè)意思；這些本質(zhì)上是同一個(gè)含義而不容易發(fā)現(xiàn)的重復(fù)數(shù)據(jù)稱為相似重復(fù)記錄。本論文主要研究重點(diǎn)是相似重復(fù)記錄檢測(cè)問題。

2 相似重復(fù)記錄檢測(cè)

數(shù)據(jù)中存在大量的相似重復(fù)記錄影響了數(shù)據(jù)的質(zhì)量，為了能夠挖掘出有價(jià)值的信息，需要對(duì)數(shù)據(jù)進(jìn)行清洗，從多維復(fù)雜的數(shù)據(jù)集中把冗余數(shù)據(jù)檢測(cè)出來的過程稱為相似重復(fù)記錄檢測(cè)。

目前檢測(cè)相似重復(fù)記錄的主要方法有兩類：

排序比較檢測(cè)算法，先進(jìn)行數(shù)據(jù)集某幾個(gè)關(guān)鍵字段排序，經(jīng)過多輪排序，具有相同或相似的字段值的數(shù)據(jù)就會(huì)聚集在一起；還可以通過滑動(dòng)窗口在一定范圍內(nèi)從上往下逐一比較進(jìn)行相似記錄篩選來檢測(cè)相似記錄。

相似記錄轉(zhuǎn)換為相似度比較檢測(cè)。兩條記錄是否相似是通過比較李璐相似度進(jìn)行度量的，相似度的計(jì)算主要采用編輯距離的算法，距離公式的選擇有多種諸如歐式距離、余弦距離等。相似檢測(cè)的時(shí)候首先會(huì)根據(jù)距離公式計(jì)算一條記錄中的每個(gè)字段的相似度，在合并統(tǒng)計(jì)出整條記錄的相似度，同時(shí)會(huì)科學(xué)設(shè)定相似度的閾值范圍，接近閾值的篩選歸集為相似重復(fù)記錄，本文的算法就是基于該思想實(shí)現(xiàn)的。

國(guó)內(nèi)外學(xué)者目前對(duì)相似重復(fù)記錄檢測(cè)提出了很多方法，比如Hemandez等提出了近鄰排序（SNM）算法，該算法先分析數(shù)據(jù)確定關(guān)鍵字段，依據(jù)關(guān)鍵字段進(jìn)行排序，然后通過滑動(dòng)窗口對(duì)排序后相近鄰的記錄逐個(gè)比較找出相似的記錄。很多國(guó)外內(nèi)學(xué)者根據(jù)SNM算法提出了如多趟近鄰排序等改進(jìn)算法或者變步長(zhǎng)改進(jìn)了SNM算法提高了檢測(cè)精；梁雪提出了一種量子群與向量機(jī)相結(jié)合的算法檢測(cè)相似重復(fù)記錄，改善了檢測(cè)的精度；呂國(guó)俊等人提出了多目標(biāo)蟻群與二分類支持向量機(jī)結(jié)合的算法檢測(cè)相似重復(fù)記錄；張平等人采用q-gram將記錄映射為空間點(diǎn)，將大數(shù)據(jù)進(jìn)行劃分后采用改進(jìn)的SNM算法檢測(cè)，提高了檢測(cè)效率。以上這些方法在小數(shù)據(jù)量情況下檢測(cè)精度都有明顯的提高，但是針對(duì)大數(shù)據(jù)的檢測(cè)耗時(shí)問題沒有很好地解決。

本文對(duì)傳統(tǒng)檢測(cè)算法對(duì)大數(shù)據(jù)不能有效處理的情形，提出了一種本文提出K-means聚類分組在檢測(cè)的算法。首先通過改進(jìn)K-modes聚類算法對(duì)大數(shù)據(jù)集進(jìn)行相似聚類分組，然后再各分組中采用經(jīng)典的近鄰比較算法SNM提高檢測(cè)的精度。

3 K-means聚類分組檢測(cè)算法

3.1 K-means聚類分組檢測(cè)流程

聚類分析方法是將數(shù)據(jù)對(duì)象劃分成多個(gè)類或簇，是一種非監(jiān)督學(xué)習(xí)方法，通過聚類可以將大的數(shù)據(jù)集劃分成多個(gè)簇，在同一個(gè)簇中的數(shù)據(jù)之間相似度接近，而不同簇中的數(shù)據(jù)之間相似度差距較大，通過聚類可以較好地劃分?jǐn)?shù)據(jù)集。數(shù)據(jù)間的距離度量是根據(jù)編輯距離來度量的，采用不同的距離算法略有差異，聚類算法廣泛運(yùn)用于數(shù)據(jù)挖掘中數(shù)據(jù)集的劃分。

K-means聚類是一種無監(jiān)督的學(xué)習(xí)，它可以把相似的對(duì)象聚集到同一個(gè)簇中。根據(jù)這個(gè)原理，可以考慮通過聚類把大數(shù)據(jù)中的記錄映射成一個(gè)個(gè)空間對(duì)象點(diǎn)，然后通過聚類把相似的記錄聚集到一個(gè)簇中，從而篩選出相似重復(fù)記錄。當(dāng)然，受聚類中心的點(diǎn)選擇的影響，各個(gè)聚集的相似重復(fù)記錄可能會(huì)有交叉現(xiàn)象產(chǎn)生，可以通過在各個(gè)簇內(nèi)進(jìn)行二次檢測(cè)就能很快剔除相似重復(fù)記錄。本文基于這個(gè)思想提出了一種在大數(shù)據(jù)環(huán)境下通過K-means聚類進(jìn)行分組，在從聚類后的簇中進(jìn)行二次SNM檢測(cè)，這樣就能確保精度的情況下減少大數(shù)據(jù)集排序的耗時(shí)問題

SNM近鄰排序算法思想：先根據(jù)專家經(jīng)驗(yàn)評(píng)估確定排序關(guān)鍵字段的生成方法，然后遍歷整個(gè)數(shù)據(jù)集，對(duì)每一條記錄生成排序關(guān)鍵字，按照排序關(guān)鍵字對(duì)記錄進(jìn)行排序，這樣數(shù)據(jù)集排序后使得相似記錄都處于鄰近位置，最后采用滑動(dòng)窗口對(duì)數(shù)據(jù)集進(jìn)行相似重復(fù)檢測(cè)。

聚類分組的檢測(cè)步驟主要分為聚類分組和組內(nèi)相似檢測(cè)兩個(gè)階段，第一階段采用K-means聚類對(duì)大數(shù)據(jù)集進(jìn)行分組，隨機(jī)選擇個(gè)聚類中心，通過聚類迭代，產(chǎn)生個(gè)聚類分組的數(shù)據(jù)相似簇，每個(gè)簇內(nèi)數(shù)據(jù)相似，不同簇間的數(shù)據(jù)有較大差異。第二階段采用經(jīng)典的SNM近鄰排序算法在聚類簇內(nèi)進(jìn)行檢測(cè)，確定排序關(guān)鍵字對(duì)相似簇進(jìn)行排序，在用滑動(dòng)窗口逐一比較檢測(cè)，從而確保了檢測(cè)的準(zhǔn)確性。具體檢測(cè)步驟如圖1所示。

圖1 聚類分組的檢測(cè)流程圖

3.2 K-means聚類分組檢測(cè)算法

means算法采用距離來劃分聚類，距離的計(jì)算方法采用經(jīng)典的歐式距離度量記錄與中心點(diǎn)之間的距離，把距離中心點(diǎn)近的點(diǎn)歸到同一個(gè)簇中，直到收斂。

定義1：假設(shè)維數(shù)據(jù)可以轉(zhuǎn)換為維度向量x（x，x，…，x）和x（x，x，…，x），則歐幾里得幾何距離可定義為：

定義2：假設(shè)有維的兩條記錄和，它們對(duì)應(yīng)于屬性R的字段值分別為和，則字段間相似度為S（，），則記錄的相似度為：

算法：基于的K-means聚類分組檢測(cè)算法

輸入：個(gè)維度，個(gè)數(shù)據(jù)的數(shù)據(jù)集，假設(shè)初始聚類數(shù)目。

輸出：個(gè)相似重復(fù)記錄的聚類簇。

（1）隨機(jī)選取個(gè)不同的數(shù)據(jù)對(duì)象作為初始聚類中心；

（2）計(jì)算數(shù)據(jù)集中個(gè)點(diǎn)到個(gè)聚類中心的歐式距離，將然后將每個(gè)對(duì)象分配到與其距離最小的聚類中心所在的簇中；

（3）在得到的個(gè)簇中，根據(jù)提出的簇中心點(diǎn)的更新方式選出新的中心點(diǎn)，迭代直到簇中心不發(fā)生變化，聚類過程結(jié)束，得到個(gè)的相似的聚類簇。

（4）用近鄰SNM算法對(duì)已經(jīng)排序后的記錄簇進(jìn)行相似重復(fù)記錄檢測(cè)。對(duì)每個(gè)簇內(nèi)數(shù)據(jù)確定排序關(guān)鍵字的生成方案，設(shè)定滑動(dòng)窗口大小為；

（5）對(duì)每個(gè)簇內(nèi)每條記錄生成排序關(guān)鍵字，按照排序關(guān)鍵字對(duì)簇內(nèi)記錄進(jìn)行排序；

（6）采用滑動(dòng)窗口對(duì)已經(jīng)排序后的記錄比較進(jìn)行相似重復(fù)記錄檢測(cè)。檢測(cè)設(shè)置閾值，如果相似度大于或者相似度為1的都?xì)w集為相似重復(fù)記錄。

4 實(shí)驗(yàn)分析

本文采用Febrl數(shù)據(jù)集的數(shù)據(jù)，通過生成器人工生成了10、20、30、40和50萬條數(shù)據(jù)集進(jìn)行相似重復(fù)記錄檢測(cè)的驗(yàn)證。實(shí)驗(yàn)為了能進(jìn)行有效對(duì)比，人為地增加相似重復(fù)記錄，故數(shù)據(jù)集中的數(shù)據(jù)由原始數(shù)據(jù)和相似重復(fù)數(shù)據(jù)構(gòu)成，它們之間的占比為各50%。

評(píng)價(jià)相似重復(fù)記錄檢測(cè)的評(píng)價(jià)標(biāo)準(zhǔn)主要從兩個(gè)方面一個(gè)是的準(zhǔn)確率和運(yùn)行時(shí)間。為了驗(yàn)證算法的有效性，我們將該文所提出的K-means聚類分組相似記錄檢測(cè)算法與文獻(xiàn)[2]所采用的經(jīng)典SNM算法從準(zhǔn)確率和運(yùn)行時(shí)間兩個(gè)方面進(jìn)行了對(duì)比實(shí)驗(yàn)，如圖2所示。

圖2 檢測(cè)精度和運(yùn)行時(shí)間對(duì)比

從圖2中可看出，從檢測(cè)精度上對(duì)比看，當(dāng)數(shù)據(jù)量較少時(shí)聚類檢測(cè)準(zhǔn)確率低于SNM方法這是因?yàn)榫垲悓?duì)小數(shù)據(jù)集會(huì)導(dǎo)致相似記錄在不同的簇中交叉，簇之間的距離差異不夠明顯，并不能將相似重復(fù)數(shù)據(jù)分散的不同的簇中，但隨著數(shù)據(jù)量的增大，聚類分組的方法明顯優(yōu)于SNM方法，檢測(cè)精度明顯改善。從時(shí)間上看，數(shù)據(jù)量較小采用聚類分類數(shù)據(jù)相對(duì)來說比較耗費(fèi)時(shí)間，檢測(cè)時(shí)間較長(zhǎng)，隨著數(shù)據(jù)量的增加，聚類分組體現(xiàn)出其處理大數(shù)據(jù)的優(yōu)勢(shì)，隨著數(shù)據(jù)量的不斷增大，檢測(cè)時(shí)間比SNM算法少的明顯。

5 結(jié) 論

本文針對(duì)大數(shù)據(jù)環(huán)境下相似重復(fù)記錄檢測(cè)時(shí)間效率和精度不佳的問題，提出了一種基于K-means聚類分組檢測(cè)算法。實(shí)驗(yàn)分析表明，該方法在大數(shù)據(jù)相似檢測(cè)方面優(yōu)勢(shì)明顯，運(yùn)行時(shí)間和檢測(cè)精度都比直接檢測(cè)算法都有明顯的提高。本文中聚類中心是隨機(jī)選擇的，對(duì)于不同的數(shù)據(jù)集應(yīng)用該算法可能會(huì)導(dǎo)致數(shù)據(jù)中心敏感問題，下一步將會(huì)對(duì)聚類算法進(jìn)行改進(jìn)，通過改善聚類中心敏感性問題，對(duì)大數(shù)據(jù)集能有效劃分，進(jìn)一步提高檢測(cè)的精度。