基于K-means的大數據相似重復記錄檢測

張平，程新蓮

（1.安徽職業技術學院 信息工程學院，安徽 合肥 230011；2.嘉善萬順達電子有限公司，浙江 嘉興 314100）

0 引 言

目前大多數企業的業務系統積累了大量業務數據，其中不乏許多的冗余數據，嚴重影響了數據分析和數據挖掘的結果，冗余的數據導致數據價值密度低。為了能夠從數據中獲取更精準的有價值的信息，有必須對數據進行清洗，也成為數據預處理。數據清洗就是從大量的數據中找出重復、無用或歧義的數據并去除，其中檢測出這些臟數據尤為重要。

近些年來國內外很多學者和專家都重視數據清洗工作的研究，大量學者都專注于相似重復記錄檢測的研究，相似重復記錄檢測是數據清洗工作的重要環節。目前大數據具有維度高、數據量大、數據結構復雜等特點，導致傳統的檢測方法對大數據的相似重復數據檢測時間效率和準確率都不高，大量的排序和比較工作耗費大量的時間，加上數據復雜，很多算法都不能有效進行檢測，因此，本文根據大數據的特點提出了通過聚類分組后再檢測相似重復記錄的方法，提高了檢測效率和檢測的準確率。

1 相似重復記錄

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

表1 學生信息表

如表1所示學號為100001和100002的兩條記錄，除了主鍵字段不同以外，其他字段的值都是完全相同的，故為完全重復記錄，而學號100001和100003的兩條記錄，除了主鍵字段相同以外，其他字段存在雖然表示方法不一樣，但是含義是一樣的字段，比如性別字段“1”表示男性的意思；還存在字段值意思相同的簡稱表示，比如學校使用全稱和簡稱表示，其實表示的都是一個意思；這些本質上是同一個含義而不容易發現的重復數據稱為相似重復記錄。本論文主要研究重點是相似重復記錄檢測問題。

2 相似重復記錄檢測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義1：假設維數據可以轉換為維度向量x（x，x，…，x）和x（x，x，…，x），則歐幾里得幾何距離可定義為：

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

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

輸入：個維度，個數據的數據集，假設初始聚類數目。

輸出：個相似重復記錄的聚類簇。

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

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

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

（4）用近鄰SNM算法對已經排序后的記錄簇進行相似重復記錄檢測。對每個簇內數據確定排序關鍵字的生成方案，設定滑動窗口大小為；

（5）對每個簇內每條記錄生成排序關鍵字，按照排序關鍵字對簇內記錄進行排序；

（6）采用滑動窗口對已經排序后的記錄比較進行相似重復記錄檢測。檢測設置閾值，如果相似度大于或者相似度為1的都歸集為相似重復記錄。

4 實驗分析

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

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

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

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

5 結 論

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