基于K-means的大數(shù)據(jù)相似重復(fù)記錄檢測

張平，程新蓮

（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ù)價值密度低。為了能夠從數(shù)據(jù)中獲取更精準(zhǔn)的有價值的信息，有必須對數(shù)據(jù)進(jìn)行清洗，也成為數(shù)據(jù)預(yù)處理。數(shù)據(jù)清洗就是從大量的數(shù)據(jù)中找出重復(fù)、無用或歧義的數(shù)據(jù)并去除，其中檢測出這些臟數(shù)據(jù)尤為重要。

近些年來國內(nèi)外很多學(xué)者和專家都重視數(shù)據(jù)清洗工作的研究，大量學(xué)者都專注于相似重復(fù)記錄檢測的研究，相似重復(fù)記錄檢測是數(shù)據(jù)清洗工作的重要環(huán)節(jié)。目前大數(shù)據(jù)具有維度高、數(shù)據(jù)量大、數(shù)據(jù)結(jié)構(gòu)復(fù)雜等特點，導(dǎo)致傳統(tǒng)的檢測方法對大數(shù)據(jù)的相似重復(fù)數(shù)據(jù)檢測時間效率和準(zhǔn)確率都不高，大量的排序和比較工作耗費大量的時間，加上數(shù)據(jù)復(fù)雜，很多算法都不能有效進(jìn)行檢測，因此，本文根據(jù)大數(shù)據(jù)的特點提出了通過聚類分組后再檢測相似重復(fù)記錄的方法，提高了檢測效率和檢測的準(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é)號為100001和100002的兩條記錄，除了主鍵字段不同以外，其他字段的值都是完全相同的，故為完全重復(fù)記錄，而學(xué)號100001和100003的兩條記錄，除了主鍵字段相同以外，其他字段存在雖然表示方法不一樣，但是含義是一樣的字段，比如性別字段“1”表示男性的意思；還存在字段值意思相同的簡稱表示，比如學(xué)校使用全稱和簡稱表示，其實表示的都是一個意思；這些本質(zhì)上是同一個含義而不容易發(fā)現(xiàn)的重復(fù)數(shù)據(jù)稱為相似重復(fù)記錄。本論文主要研究重點是相似重復(fù)記錄檢測問題。

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

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

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

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

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

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

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

3 K-means聚類分組檢測算法

3.1 K-means聚類分組檢測流程

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

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

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

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

圖1 聚類分組的檢測流程圖

3.2 K-means聚類分組檢測算法

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

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

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

算法：基于的K-means聚類分組檢測算法

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

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

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

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

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

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

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

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

4 實驗分析

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

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

圖2 檢測精度和運行時間對比

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

5 結(jié) 論

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