基于K-modes聚類分組的大數(shù)據(jù)相似重復(fù)記錄檢測研究

張 平，余 順

（安徽職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，安徽 合肥 230011）

隨著大數(shù)據(jù)時代的到來，大型企業(yè)數(shù)據(jù)日積月累，數(shù)據(jù)量龐大，如何從大數(shù)據(jù)中找出有價值的信息是當(dāng)前企業(yè)關(guān)注的熱點。大型企業(yè)存儲了大量的數(shù)據(jù)，但是數(shù)據(jù)質(zhì)量令人堪憂，集中表現(xiàn)在數(shù)據(jù)相似重復(fù)、冗余、錯誤、歧義等問題，多個數(shù)據(jù)源的合并加重數(shù)據(jù)的冗余。在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)的來源、數(shù)據(jù)量和維度不斷增加，使得數(shù)據(jù)質(zhì)量更加糟糕，數(shù)據(jù)質(zhì)量不斷下降，數(shù)據(jù)挖掘出有用的價值的信息就越困難。因此，如何解決對同一條數(shù)據(jù)因描述標準不統(tǒng)一而導(dǎo)致的數(shù)據(jù)冗余問題，即相似重復(fù)記錄檢測問題，逐漸成為數(shù)據(jù)預(yù)處理的核心問題。

針對相似重復(fù)記錄檢測，國內(nèi)外學(xué)者提出了很多的檢測方法：東北石油大學(xué)的袁滿等人改進了經(jīng)典的近鄰排序（SNM）算法，該算法先找出關(guān)鍵屬性進行排序，然后通過滑動窗口對相近鄰的記錄逐個比較找出相似記錄［1］；復(fù)旦大學(xué)的周傲英教授等人提出了以N-Gram值作為排序關(guān)鍵字對記錄排序，然后把N-Gram值映射成空間的點來聚類相似重復(fù)的記錄［2］；東南大學(xué)的韓京宇等人提出了一種分層次聚類的算法來檢測相似重復(fù)數(shù)據(jù)，該方法采用將數(shù)據(jù)映射成空間的度量點之間的相似度來找出相似數(shù)據(jù)［3］；暨南大學(xué)的朱蔚恒教授提出的通過構(gòu)建R-樹，減少R-樹中葉子比較次數(shù)進行降維來檢測相似重復(fù)記錄［4］。文獻中闡述的方法大多用到排序和比較的方法進行相似記錄比較，在時效上比較慢，應(yīng)用于大數(shù)據(jù)集的時候，排序和比較的時間復(fù)雜度將會很高，本文為了在保證檢測精度不變的情況下降低時間復(fù)雜度提出了基于K-mod es聚類分組檢測算法。

1 相似重復(fù)記錄

當(dāng)今是一個數(shù)據(jù)爆炸的時代，數(shù)據(jù)質(zhì)量問題已經(jīng)引起企業(yè)的重視。多源數(shù)據(jù)的合并導(dǎo)致業(yè)務(wù)系統(tǒng)中有很多冗余和不合要求的數(shù)據(jù)，這些數(shù)據(jù)主要包括重復(fù)記錄、錯誤的數(shù)據(jù)、不完整的數(shù)據(jù)、歧義的數(shù)據(jù)等。數(shù)據(jù)清洗就是從海量數(shù)據(jù)中找出這些冗余和不合要求的數(shù)據(jù)的過程，其中相似重復(fù)記錄的檢測尤其重要，它是整個數(shù)據(jù)清洗的關(guān)鍵環(huán)節(jié)［5］。

數(shù)據(jù)表中一條數(shù)據(jù)一般由若干個字段組成，如果數(shù)據(jù)庫中存在兩條記錄，他們除了主鍵不同以外其他字段都相同，我們稱為完全重復(fù)記錄。如果兩條記錄是同一個對象實體，除了主鍵不同，而其他字段在表述或者格式上不同的兩條記錄稱為相似重復(fù)記錄，如表1所示：

表1 學(xué)生信息表中的重復(fù)數(shù)據(jù)

表1為在校學(xué)生的四條記錄存在兩種重復(fù)類型，其中，學(xué)號2022001和2022005的兩條記錄除了學(xué)號不相同，其他字段值均完全相同，可以判定這兩條記錄即為完全重復(fù)記錄。而學(xué)號2022001和2022003的兩條記錄、學(xué)號2022002和2022004的兩條記錄除了主鍵不同以外，性別字段值、出生日期字段的值以及院系字段的值都是表述不一樣的，如性別屬性的值“男”和“Male”的縮寫“M”本質(zhì)一個意思，也可以判定這兩條記錄是同一條記錄，這樣的兩條數(shù)據(jù)即為相似重復(fù)記錄。

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

2.1 編輯距離與相似度

字段間的相似度是通過編輯距離轉(zhuǎn)換得到的。編輯距離的計算方法有歐式距離、曼哈頓距離、馬式距離等衡量方法，本文采用經(jīng)典的歐式距離度量字段間的編輯距離。假設(shè)m維數(shù)據(jù)看作m維度向量xi（xi1，xi2，…，xim）和xj（xj1，xj2，…，xjm），則歐幾里得幾何距離可定義為：

通過公式可以計算出字段間的編輯距離，根據(jù)編輯距離的計算結(jié)果構(gòu)造編輯距離和相似度之間轉(zhuǎn)換關(guān)系表，例如當(dāng)編輯距離為1時，可以轉(zhuǎn)換相似度為0.9，當(dāng)編輯距離為2時，可以轉(zhuǎn)換成相似度為0.8，以此類推，可以計算得到所有字段間的相似度。

記錄相似度是通過字段相似度累加求和得到的，兩條記錄的相似度檢測是通過字段相似度累加求和的結(jié)果。往往為了提高檢測精度，可以給根據(jù)每個字段的重要性設(shè)置權(quán)重w，通過權(quán)重來衡量字段的重要性，這樣可以提高相似記錄檢測的精度。

假設(shè)有m維的兩條記錄X和Y，它們對應(yīng)于屬性Ri的字段值分別為x和y，則字段間相似度為SRi（x，y），則記錄的相似度為：

為了更加準確的評價一條記錄相似度時經(jīng)常會對重要的屬性增加一個權(quán)重系數(shù)w，通過賦予不同字段不同數(shù)值的權(quán)重以突出該字段的重要性，這樣就能夠比較全面的評價字段間的相似度，從而提高檢測精度，其中權(quán)重之和為1，則加權(quán)的記錄相似度為：

2.2 相似重復(fù)記錄檢測過程

相似重復(fù)記錄檢測的方法主要是先進行全局的數(shù)據(jù)排序，先選出關(guān)鍵字段以關(guān)鍵字段進行排序，這樣同一關(guān)鍵字段的數(shù)據(jù)就會聚集在一起，然后通過定義字段間相似度進行逐個字段加權(quán)累加得到記錄的相似度，設(shè)定相似度的閾值，對所有記錄進行輪詢比較，若接近閾值的歸為相似記錄。重復(fù)記錄檢測的步驟如圖1所示：

圖1 相似重復(fù)記錄檢測過程

3 基于網(wǎng)格密度的K-modes聚類分組檢測

本文對傳統(tǒng)算法對大數(shù)據(jù)處理的局限性提出了一種“化大為小分而治之”的K-modes聚類分組檢測算法（KCG）。首先通過網(wǎng)格密度來改進K-mod es聚類算法效果，對大數(shù)據(jù)進行有效的相似聚類分組，然后再各分組中采用高效的Pair-wise比較算法［6］檢測出組內(nèi)所有相似重復(fù)記錄檢測。

3.1 K-mod es聚類

K-mod es算法是對K-means算法的擴展，該算法采用相異度來表示記錄之間的相關(guān)程度，在每個分類簇中選擇屬性值出現(xiàn)頻率最多的屬性值來更新modes［6，7］。

定義1（記錄間相異度）假設(shè)兩個記錄xi和xj的距離為：

算法1：基于K-mod es聚類分組算法

Input：數(shù)據(jù)集D（n個數(shù)據(jù)點，m個維度），k個初始聚類個數(shù)

Output：k個相似重復(fù)記錄的聚類簇

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

（2）計算數(shù)據(jù)集中所有對象到k個聚類中心的相異度，將然后將每個對象分配到與其相異度最小的聚類中心所在的簇中；

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

3.2 基于網(wǎng)格密度的K-mod es聚類

經(jīng)典的K-modes聚類算法在通常采用隨機選取初始聚類中心點，這種選取中心點的方法會對聚類結(jié)果有較大影響，會導(dǎo)致初始中心敏感的問題［8］。針對這一問題，本文采用基于網(wǎng)格密度的方法來改善初始聚類中心的選擇，解決初始中心敏感問題。該方法思路是增大初始簇中心之間的距離，增加了聚類間的差異性，從而得到較為滿意的聚類結(jié)果。

定義2（網(wǎng)格密度閾值MinS）：假設(shè)Oi和Oj分別為網(wǎng)格空間的兩個數(shù)據(jù)點，x為最小網(wǎng)格單元里的點個數(shù)，則網(wǎng)格密度閾值MinS的計算公式定義如下：

3.3 基于網(wǎng)格密度K-modes聚類分組的相似重復(fù)記錄檢測

相似重復(fù)記錄檢測是通過比較記錄各字段值的相似度檢測出重復(fù)記錄的過程，而聚類算法是將數(shù)據(jù)之間的相似度對數(shù)據(jù)進行分類的過程，數(shù)據(jù)被劃分為若干個簇，簇內(nèi)的所有數(shù)據(jù)具有相同或接近的相似度，而簇與簇之間是相異的，所以可以運用聚類的思想先從大數(shù)據(jù)集中找出相似重復(fù)記錄的簇，再在各個簇中進行相似檢測，這樣就能夠很好解決大數(shù)據(jù)環(huán)境下的檢測效率和精度。

本文基于這個思想提出了一種改進初始聚類中心K-mod es聚類算法先對大數(shù)據(jù)進行有效的分組，然后在分組中采用經(jīng)典的Pair-wise算法檢測出所有相似重復(fù)記錄檢測，算法的步驟如下圖2所示：

圖2 KCG相似重復(fù)記錄檢測步驟

算法2：KCG相似重復(fù)記錄檢測

Input：大數(shù)據(jù)集D（n個數(shù)據(jù)點，m個維度），k個聚類數(shù)

其中：δ為相似度閾值，是由相關(guān)領(lǐng)域?qū)＜姨幦〉?，用來判定兩條記錄是否是相似重復(fù)記錄。記錄的相似度為對應(yīng)字段的相似度之和，如果兩條記錄的相似度大于2δ，則判定兩條記錄不是相似重復(fù)記錄。

4 實驗分析

4.1 評價標準

相似重復(fù)記錄檢測的評價標準主要有3個指標：準確率P（Precision）、查全率R（Recall）和時間效率T（Time）［9］。準確率P是正確識別出來的重復(fù)記錄占識別出作為重復(fù)記錄的比例；查全率R是正確識別出來的重復(fù)記錄占數(shù)據(jù)集中實際的重復(fù)記錄比率。查全率R，查準率P可以用公式（4-1）和（4-2）表示：

其中，Rd代表原數(shù)據(jù)集實際的重復(fù)記錄集合，Rx代表識別出來的重復(fù)記錄集合。

4.2 實驗數(shù)據(jù)

本文采用開源Febrl數(shù)據(jù)集的數(shù)據(jù)，并使用生成器工具模擬產(chǎn)生本實驗所需的數(shù)據(jù)。Febrl數(shù)據(jù)集中每條記錄包含了18個字段信息：人的姓名、年齡、國籍、住址、電話等。本文對該數(shù)據(jù)集使用前進行了適當(dāng)?shù)奶幚恚捎蒙善鞴ぞ叻謩e生成了10、20、30、40和50萬條數(shù)據(jù)集用于相似重復(fù)檢測實驗對比。數(shù)據(jù)集中的數(shù)據(jù)由兩部分組成，50%為原始數(shù)據(jù)，50%根據(jù)原始數(shù)據(jù)模擬出的相似重復(fù)記錄。

4.3 實驗環(huán)境

服務(wù)器選用酷睿i9 CPU，物理內(nèi)存256GB，硬盤空間4T，操作系統(tǒng)Windows 10，數(shù)據(jù)庫為Mysql，程序采用Python語言編寫。

4.4 實驗結(jié)果分析

為了驗證方法的有效性和正確性，我們將該文所提出的聚類分組相似記錄檢測算法與經(jīng)典的SNM算法從檢測精度和運行時間兩個方面進行了對比實驗。

4.4.1 查準率對比

從圖3中可見，當(dāng)數(shù)據(jù)量較少時聚類分組方法檢測精度低于SNM方法，這是因為數(shù)據(jù)量較少時，分組時組間區(qū)分不明顯，產(chǎn)生交叉的重復(fù)數(shù)據(jù)故而導(dǎo)致檢測精度低。但隨著數(shù)據(jù)量不斷的增大，聚類分組的方法在檢測精度上明顯優(yōu)于SNM方法。

圖3 查準率比較

4.4.2 運行時間對比

從圖4可見，兩種方法在10、20、30、40和50萬條數(shù)據(jù)集下的運行時間，開始時聚類算法因為分組需要花費計算時間，時間較長，隨著數(shù)據(jù)量的增加，聚類分組體現(xiàn)出其處理大數(shù)據(jù)的優(yōu)勢，運行時間明顯比SNM算法更少，而且是數(shù)據(jù)量越大越明顯。

圖4 運行時間比較

5 結(jié)語

本文針對大數(shù)據(jù)環(huán)境下不能有效的檢測相似重復(fù)記錄的問題，提出了一種聚類分組的KCG算法來檢測大數(shù)據(jù)集中的相似重復(fù)記錄。該算法通過網(wǎng)格劃分方法解決初始中心點的敏感問題，能夠有效的進行相似重復(fù)記錄聚類分組，然后在分組的基礎(chǔ)上再分組的小范圍使用Pair-wise高效檢測算法進行組內(nèi)相似記錄檢測，在保證精度不降低的情況下提升了檢測的效率。通過實驗對比分析顯示，該方法的運行效率和檢測精度都高于直接檢測的算法，有效地解決了大數(shù)據(jù)量的相似重復(fù)記錄檢測問題。由于采用聚類算法的分組會導(dǎo)致相似重復(fù)分組數(shù)據(jù)交叉使得檢測的精度沒有較明顯的提高，接下來的工作就是要解決如何進一步提高檢測精度的問題對算法改進。