陳彥萍 洪明杰 楊小寶

（西安郵電大學(xué) 西安 710121）

1 引言

隨著互聯(lián)網(wǎng)信息技術(shù)的不斷發(fā)展，數(shù)據(jù)信息的潛在價(jià)值逐漸被重視，對(duì)企業(yè)的生產(chǎn)決策、市場(chǎng)銷售、經(jīng)濟(jì)效益、競(jìng)爭(zhēng)力提升等都有著重要作用［1］。然而由于數(shù)據(jù)信息共享、數(shù)據(jù)遷移、來(lái)自同一實(shí)體的不同表達(dá)、輸入拼寫錯(cuò)誤或是受數(shù)據(jù)來(lái)源不同等原因?qū)е铝讼嗨浦貜?fù)數(shù)據(jù)的存在，相似重復(fù)數(shù)據(jù)可能會(huì)影響程序運(yùn)行速度，同時(shí)也會(huì)占用更多存儲(chǔ)空間和傳輸帶寬和時(shí)間，消耗更多的網(wǎng)絡(luò)流量，更不利于后續(xù)的數(shù)據(jù)挖掘工作，精準(zhǔn)可靠的高質(zhì)量數(shù)據(jù)是數(shù)據(jù)挖掘的前提，是進(jìn)一步提取數(shù)據(jù)潛在價(jià)值的基礎(chǔ)，提高數(shù)據(jù)質(zhì)量［2］對(duì)于優(yōu)化資源利用、降低數(shù)據(jù)管理成本也有著重要意義。

相似重復(fù)記錄檢測(cè)是數(shù)據(jù)清洗中的關(guān)鍵步驟，是判斷該記錄是否表示的是現(xiàn)實(shí)世界中的同一實(shí)體。傳統(tǒng)的檢測(cè)相似記錄的方法主要是對(duì)記錄的相似度匹配：“排序 & 合并”［3～4］比較次數(shù)較多時(shí)間復(fù)雜度較高，鄰近記錄排序［5］算法（Sorted Neighbor?hood Method，SMN）的滑動(dòng)窗口大小設(shè)定對(duì)檢測(cè)效率影響很大，編輯距離算法［6～7］對(duì)字符拼寫錯(cuò)誤及字符縮寫檢測(cè)檢測(cè)率比較低，還有依據(jù)記錄內(nèi)碼序值［8］、基于tokens值［9］的相似檢測(cè)算法也都致力于減少記錄比較次數(shù)。隨著數(shù)據(jù)量的增加，數(shù)據(jù)來(lái)源的不同，數(shù)據(jù)結(jié)構(gòu)也不一樣，傳統(tǒng)方法面臨新的難題，聚類算法［10～11］應(yīng)用對(duì)于相似重復(fù)檢測(cè)有著顯著效果。文獻(xiàn)［12～14］根據(jù)關(guān)鍵屬性或?qū)傩詸?quán)重對(duì)數(shù)據(jù)集先進(jìn)行分組聚類處理，再進(jìn)行相似檢測(cè)，在處理大量數(shù)據(jù)中提高了檢測(cè)效率，文獻(xiàn)［14］針對(duì)高維數(shù)據(jù)用R-樹(shù)進(jìn)行索引，應(yīng)該聚類思想完成相似記錄的檢測(cè)，文獻(xiàn)［15～16］分別對(duì)重要屬性和非重要屬性進(jìn)行二次判斷，依據(jù)屬性進(jìn)行分組，并在記錄檢測(cè)時(shí)采用提取記錄字段相似度的特征向量的方法完成對(duì)相似記錄檢測(cè)。國(guó)內(nèi)外的研究學(xué)者對(duì)相似重復(fù)記錄檢測(cè)已經(jīng)有了廣泛的研究，提出了較多的方法，其中聚類分組思想是解決海量數(shù)據(jù)的相似重復(fù)檢測(cè)的有效途徑，但大數(shù)據(jù)時(shí)代數(shù)據(jù)的3V（Velocity、Variety、Volume）特點(diǎn)，如何提高檢測(cè)的效率和精度？本文使用K-modes算法進(jìn)行聚類分組方法，依據(jù)信息熵值來(lái)確定屬性權(quán)重并對(duì)屬性維度進(jìn)行約簡(jiǎn)，在聚類后的數(shù)據(jù)集中選擇性權(quán)重較大的字段逐項(xiàng)進(jìn)行比較，避免整條記錄相似參與匹配耗費(fèi)時(shí)間，提高了檢測(cè)效率。

2 相關(guān)工作

圖1 重復(fù)檢測(cè)的流程圖

如圖1所示，一般對(duì)于重復(fù)檢測(cè)主要有兩大階段：數(shù)據(jù)預(yù)處理和相似重復(fù)記錄檢測(cè)。這兩大階段處理和檢測(cè)方法多種多樣。預(yù)處理階段是檢測(cè)過(guò)程的基礎(chǔ)，好的預(yù)處理方法對(duì)于檢測(cè)結(jié)果影響至關(guān)重要。

相似重復(fù)記錄檢測(cè)是在數(shù)據(jù)集中識(shí)別出類似記錄的過(guò)程，而聚類算法是將數(shù)據(jù)集相似數(shù)據(jù)進(jìn)行分類的過(guò)程，簇內(nèi)的對(duì)象保持一定相似性，簇間對(duì)象相異，所以運(yùn)用聚類的思想可以有效幫助找出每個(gè)簇內(nèi)相似重復(fù)率，在檢測(cè)大量數(shù)的記相似性上具有良好的效果。

2.1 K-modes聚類算法

K-modes［17］是對(duì) K-means算法的擴(kuò)展，保留了K-means算法效率的同時(shí)將K-means的應(yīng)用擴(kuò)大到離散數(shù)據(jù)，K-modes算法采用相異度來(lái)度量記錄之間相關(guān)程度，使用一個(gè)簇類的每個(gè)屬性出現(xiàn)頻率最大的那個(gè)屬性值作為代表簇的屬性值來(lái)更新modes。

設(shè) S=(U，A)是一個(gè)信息分類系統(tǒng)，U={x1，x2，…，xn}，A={a1，a2，…，an}， xi，xj∈ U(1 ≤ i，j≤ n)， xi和xj分 別 被 A 描 述 為 xi=(f(xi，a1)，f(xi，a2)，…f(xi， am)) 和 xj=(f(xj， a1)， f(xj， a2)， …f(xj， am))，xi和xj的距離定義為其中：

W是 n×k的｛0，1｝矩陣，n表示對(duì)象個(gè)數(shù)，k表示聚類個(gè)數(shù)，wil=1表示第i個(gè)對(duì)象被劃分到第l類的中心，Z={z1，z2，…zk}，zl(1≤l≤k)是第 l類的中心。

在約束條件（1）～（3）下達(dá)到極小化，K-modes聚類算法描述如下：

Step1：從數(shù)據(jù)集中隨機(jī)選擇k個(gè)對(duì)象作為初始聚類中心，k為聚類個(gè)數(shù)；

Step2：應(yīng)用簡(jiǎn)單匹配算法計(jì)算每個(gè)對(duì)象到中心的距離，并分配到離它最近的類中；

Step3：基于頻率重新計(jì)算各類的聚類中心；

Step4：重復(fù)Step3，Step4過(guò)程，直到目標(biāo)函數(shù)F不再發(fā)生變化為止。

圖2 K-modes聚類算法流程圖

代碼描述如下：

Radom（K）

for（int i=0；i＜num；i++）

｛

Int dis，mindis=0；

mindis=Distance（data［i］，center［0］）；

for（int j=0；i＜k；j++）

｛

dis=Distance（data［i］，center［j］）；

if（dis＜mindis）

｛

mindis=dis；

｝

BeCluster（data［i］）；

｝

If（UpdataCenter）

｛

for（int i=0；i＜num；i++）

｛

Int dis，mindis=0；

mindis=Distance（data［i］，center［0］）；

for（int j=0；i＜k；j++）

｛

dis=Distance（data［i］，center［j］）；

if（dis＜mindis）

｛

mindis=dis；

｝

BeCluster（data［i］）；

｝

｝

else

return Cluster；

2.2 信息熵

“熵”（entropy）最早是由魯?shù)婪颉た藙谛匏梗≧u?dolf Clausius）于1854年提出的概念，其物理意義是體系混亂程度的度量，熵就越大則該體系越均衡。1948年克勞德·艾爾伍德·香農(nóng)（Claude Elwood Shannon）提出了“信息熵”的概念，用來(lái)描述信源的不確定度，第一次用數(shù)學(xué)語(yǔ)言闡明了概率與信息冗余度的關(guān)系，解決了信息的量化問(wèn)題。

假設(shè)離散型隨機(jī)變量X（信源）的取值集合A={a1， a1， … aq}，對(duì)應(yīng)的概率預(yù)測(cè) pi=P[X=ai]，則義為

即信源的所提供的的信息量，一般以2為底，單位比特（bit）。

3 信息熵的屬性權(quán)重計(jì)算和維度約簡(jiǎn)

對(duì)于一些包含多個(gè)屬性字段多元數(shù)據(jù)，不同屬性的提供的信息量不同，重要程度不同，需要確定這些屬性的重要程度，從屬性集合中去除某些非重要屬性，實(shí)現(xiàn)屬性維度的約簡(jiǎn)。

3.1 熵值計(jì)算屬性權(quán)重

屬性重要程度即為屬性權(quán)重，目前權(quán)重確定方式分為主觀賦權(quán)、客觀賦權(quán)和主客觀組合賦權(quán)三種方式。主觀賦權(quán)依據(jù)專家經(jīng)驗(yàn)來(lái)進(jìn)行賦權(quán)，主觀意愿較強(qiáng)，信息不能準(zhǔn)確量化，客觀賦權(quán)有充分的數(shù)理根據(jù)，具有較好的規(guī)范性。這里考慮到數(shù)據(jù)屬性之間都有著復(fù)雜的聯(lián)系，采用客觀賦權(quán)的熵值法來(lái)計(jì)算各個(gè)屬性的權(quán)重。

在聚類的簇中，可以將數(shù)據(jù)看做是n×m的矩陣，n表示簇類中的數(shù)據(jù)個(gè)數(shù)，m表示屬性個(gè)數(shù)，各字段屬性熵值可用以下方法來(lái)確定。

1）設(shè)某多維數(shù)據(jù)集A有m維屬性n條數(shù)據(jù)，xnm表示m屬性下第n條數(shù)據(jù)的值，可構(gòu)建屬性值的決策矩陣：

2）數(shù)據(jù)標(biāo)準(zhǔn)化處理，為了使不同量綱的數(shù)據(jù)具有可比性，對(duì)數(shù)據(jù)壓縮到［0，1］區(qū)間上，每列所有數(shù)據(jù)和為 1，即，計(jì)算第i條數(shù)據(jù)的j屬性所占的比重：

其中xij為屬性值，Mij表示屬性值比重。

3）第j維屬性的熵值：

4）易得 0≤Hj≤1，若 Mij均相等，那 Hj=1，不易區(qū)分各屬性優(yōu)劣程度，所以定義區(qū)分度Fj=1-Hj，當(dāng)屬性值分布較為均勻時(shí)，熵值Hj越大，區(qū)分度Fj越小，該屬性區(qū)分能力越弱，聚類作用也就較弱，反之亦然，所以Fj越大時(shí)，則該屬性就越重要。

5）計(jì)算第j維屬權(quán)重：

3.2 屬性維度約簡(jiǎn)

應(yīng)用熵值法確定屬性權(quán)重并約簡(jiǎn)非重要屬性。

表1 部分師生信息列表

表1為某校部分師生信息的列表。因?yàn)閿?shù)據(jù)類型不同，需要將數(shù)據(jù)統(tǒng)一轉(zhuǎn)換為可計(jì)算的數(shù)值型數(shù)據(jù)，如學(xué)號(hào)、年齡、專業(yè)代碼是數(shù)值型的直接可以參與運(yùn)算，而姓名、性別字符型的需要轉(zhuǎn)換為數(shù)值才可以參與運(yùn)算。這里均采用Unicode編碼將字符轉(zhuǎn)換為10進(jìn)制的阿拉伯?dāng)?shù)字。如：姓名字段“李馳”對(duì)應(yīng)10進(jìn)制Unicode編碼為“26446 39536”，性別字段“男”對(duì)應(yīng)10進(jìn)制Unicode編碼為“30007”，之間轉(zhuǎn)換可以通過(guò)函數(shù)得以實(shí)現(xiàn)，表中的空值則默認(rèn)為0。以表1為例進(jìn)行屬性約簡(jiǎn)，過(guò)程如下：

1）構(gòu)建決策矩陣。

2）標(biāo)準(zhǔn)化處理后，應(yīng)用式（6）計(jì)算出每個(gè)屬性值所占比重，可得A對(duì)應(yīng)的矩陣

3）數(shù)據(jù)集共5條數(shù)據(jù)，n=5；Inn=1.6094，根據(jù)式（7）、（8）計(jì)算可得表2結(jié)果。

表2 師生信息屬性熵值、區(qū)分度、權(quán)重計(jì)算結(jié)果

所以，根據(jù)表1信息利用熵值法計(jì)算得出表2，各屬性權(quán)重所占比例：學(xué)號(hào)約占23.5%，姓名約占44.9%，年齡約占2.3%，性別約占0.4%。專業(yè)代碼約占28.8%，性別權(quán)重最小，可以視為非重要屬性去除。

如果數(shù)據(jù)集中存在屬性字段較多，可根據(jù)實(shí)際情況，保證數(shù)據(jù)檢測(cè)精度允許范圍內(nèi)人為選擇需要保留屬性字段個(gè)數(shù)，實(shí)現(xiàn)數(shù)據(jù)維度的約簡(jiǎn)，此步驟可以減少后續(xù)記錄匹配階段的匹配次數(shù)，提高檢測(cè)效率。

4 相似記錄匹配

在初步聚類分組和屬性約簡(jiǎn)后，需要對(duì)聚類的小數(shù)據(jù)集進(jìn)行相似重復(fù)記錄的檢測(cè)。由于數(shù)據(jù)類型的多樣性，可能存在數(shù)值型，中英文字符串等。

數(shù)值型數(shù)據(jù)可直接進(jìn)行計(jì)算，如年齡、身高、日期等。將數(shù)據(jù)集中數(shù)據(jù)映射到空間中的點(diǎn)，兩條記錄之間的相似性直接可以用空間距離反映，距離越遠(yuǎn)說(shuō)明差異越大。點(diǎn)x，y直接的距離D（x，y）可表示為

對(duì)于長(zhǎng)度較短的英文或中文，如：姓名，性別，可以數(shù)據(jù)采用Unicode編碼映射成為阿拉伯?dāng)?shù)字，利用式（9）計(jì)算兩字符串之間的相似度。

而對(duì)于長(zhǎng)度較長(zhǎng)的字符串，如：地址，采用編輯距離法計(jì)算字符串相似度?？梢酝ㄟ^(guò)直接將字符串中的每個(gè)漢字轉(zhuǎn)化為音形碼，再將所有音形碼合并起來(lái)進(jìn)行計(jì)算。字符串s1，s2直接的距離D（s1，s2）可表示為

其中d表示講字符串s1轉(zhuǎn)換為s2替換、插入、刪除字符所需的最少編輯操作次數(shù)。

這里采用單個(gè)字段逐條匹配。選擇權(quán)重最大的屬性計(jì)算該屬性下的各個(gè)數(shù)據(jù)值之間的距離，根據(jù)字段設(shè)置閾值θ判斷該字段值的相似性，再按照屬性權(quán)重大小逐一比較各字段值，直到整條記錄所有屬性比較完成為止。基于屬性權(quán)重的相似記錄匹配步驟：

Step1：計(jì)算出各屬性權(quán)重并選擇最大屬性權(quán)重的字段；

Step2：計(jì)算數(shù)據(jù)集中該屬性下各記錄值的相似度，大于該字段閾值則為相似，小于為不相似；

Step3：判斷是否比較到最后一個(gè)屬性，是則判定該條記錄為相似記錄，算法結(jié)束，否則繼續(xù)執(zhí)行Step1。

圖3 基于屬性權(quán)重的相似記錄匹配流程圖

在每個(gè)分組的聚類簇中并行化執(zhí)行該算法，每個(gè)小數(shù)據(jù)集中可判斷出相似的記錄。該算法需要對(duì)每個(gè)屬性字段設(shè)置閾值θ，閾值θ根據(jù)經(jīng)驗(yàn)設(shè)定，設(shè)置大了，容忍度提高，造成誤判；設(shè)置小了，造成漏判，所以需要根據(jù)實(shí)際應(yīng)用反復(fù)嘗試，看結(jié)果是否到達(dá)最優(yōu)。

5 實(shí)驗(yàn)設(shè)計(jì)

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用 Intel i7 2.6 GHz CPU，物理內(nèi)存8GB，硬盤空間500 GB，操作系統(tǒng)是Windows 7，數(shù)據(jù)庫(kù)軟件使用MY SQL，程序使用C++語(yǔ)言和Mi?crosoft Visual Studio 13.0開(kāi)發(fā)平臺(tái)。實(shí)驗(yàn)數(shù)據(jù)來(lái)源于某校信息中心包括學(xué)生基本信息、學(xué)生到課數(shù)據(jù)、校園卡消費(fèi)數(shù)據(jù)等，由于數(shù)據(jù)來(lái)源多樣，學(xué)生日?；顒?dòng)的重復(fù)性和歷史數(shù)據(jù)的積累。

5.2 實(shí)驗(yàn)設(shè)計(jì)

為了檢驗(yàn)論文中檢測(cè)算法的有效性，隨機(jī)提取定量的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，人工軟件結(jié)合的方式將相似重復(fù)數(shù)據(jù)量處理成一個(gè)準(zhǔn)確占比，通過(guò)實(shí)驗(yàn)結(jié)果的對(duì)比從三個(gè)主要指標(biāo)查全率、查準(zhǔn)率和運(yùn)行時(shí)間進(jìn)行驗(yàn)證。

從信息中心管理系統(tǒng)中分次隨機(jī)提取5000，10000，20000，50000，100000，200000條記錄的數(shù)據(jù)量，分別將數(shù)據(jù)處理成包含包43，89，208，479，789，1980條重復(fù)記錄的數(shù)據(jù)集。數(shù)據(jù)含屬性53個(gè)，包括學(xué)號(hào)、姓名、所屬院系、學(xué)院代碼、專業(yè)、班級(jí)、年級(jí)、身份證號(hào)、一卡通號(hào)、考勤類型、簽到時(shí)間、綜合成績(jī)、電話、家庭住址、宿舍等，表3只列出部分屬性字段及數(shù)據(jù)記錄。

表3 在校師生信息列表

從表4中試驗(yàn)結(jié)果看出，保留屬性權(quán)重和占比達(dá)80%以上時(shí)，查準(zhǔn)率和查全率均接近于90%，保留屬性權(quán)重和占比96.7%時(shí)，查準(zhǔn)率和查全率都高于98%。經(jīng)過(guò)多次試驗(yàn)表明，保留屬性權(quán)重和占比達(dá)95%以上時(shí)，可將誤差控制在容忍誤差內(nèi)。

表4 保留屬性數(shù)量與檢測(cè)精度對(duì)照表

在文獻(xiàn)［13］中提出的根據(jù)屬性權(quán)重的分組方法實(shí)際也是先對(duì)數(shù)據(jù)進(jìn)行聚類，在小數(shù)據(jù)集中檢測(cè)相似重復(fù)記錄，為提高檢測(cè)精度采用了多趟分組查找技術(shù)，該方法具有較好的檢測(cè)結(jié)果。因此選擇等級(jí)分組方法作為本文的對(duì)照，為便于處理，等級(jí)分組檢測(cè)法法命名為WGM（Weight Grouping Meth?od），本文檢測(cè)方法命名為 BKCM（Based on K-modes Cluster Method），分別已處理過(guò)的數(shù)據(jù)集完成檢測(cè)。為了實(shí)驗(yàn)具有可比性，兩種方法的分組數(shù)和聚類個(gè)數(shù)和閾值都取相同的值，在小數(shù)據(jù)集檢測(cè)中都采用多線程并行完成，在BKCM方法中保留屬性權(quán)重和占比95%的屬性以確保檢測(cè)精度。

5.3 實(shí)驗(yàn)結(jié)果及分析

表5、表6、圖4、圖5為兩種方法在查準(zhǔn)率和查全率的比較，從中可以看出BKCM方法的查準(zhǔn)率和查全率都不低于WGM方法，隨著數(shù)據(jù)量的增大兩種方法都會(huì)略微下降，且BKCM是在設(shè)置約簡(jiǎn)屬性的情況下，如果人為設(shè)置更低的容忍度，增加保留屬性個(gè)數(shù)，檢測(cè)精度也會(huì)更高。

表5 WGM與BKCM方法查準(zhǔn)率比較

表6 WGM與BKCM方法查全率比較

圖4 WGM與BKCM方法查準(zhǔn)率比較

從表7兩種方法的運(yùn)行時(shí)間上可以看出，BKCM在檢測(cè)同量的數(shù)據(jù)時(shí)完成的時(shí)間要小于WGM，在數(shù)據(jù)量增加時(shí)優(yōu)勢(shì)也越加明顯，原因在于在小數(shù)據(jù)集檢測(cè)過(guò)程中，BKCM約簡(jiǎn)了記錄屬性個(gè)數(shù)，減少了記錄相似匹配次數(shù)，縮短了檢測(cè)時(shí)間，對(duì)于大量數(shù)據(jù)處理效果更明顯。

圖5 WGM與BKCM方法查全率比較

表7 WGM與BKCM方法時(shí)間比較

通過(guò)多次試驗(yàn)，BKCM方法在檢測(cè)精度和時(shí)間效率上都和理論分析是一致的，總體都優(yōu)于WGM方法的相似檢測(cè)方法，尤其是對(duì)于數(shù)據(jù)屬性維度非常多的數(shù)據(jù)，檢測(cè)效果明顯。

6 結(jié)語(yǔ)

本文針對(duì)相似重復(fù)記錄檢測(cè)問(wèn)題展開(kāi)了研究分析，采用了多種有效的策略和方法。首先應(yīng)用K-means聚類方法對(duì)于數(shù)據(jù)進(jìn)行處理，運(yùn)用聚類本身特點(diǎn)在簇中查找相似記錄更為有效。其次，為提高檢測(cè)效率再依據(jù)屬相權(quán)重對(duì)屬性進(jìn)行約簡(jiǎn)，并在檢測(cè)過(guò)程中采用多線程并行處理。實(shí)驗(yàn)表明，該方法能有效地檢測(cè)相似重復(fù)記錄，對(duì)提高數(shù)據(jù)質(zhì)量有著顯著效果，同時(shí)也對(duì)上層數(shù)據(jù)應(yīng)用分析階段提供了可靠的數(shù)據(jù)信息。但在實(shí)際使用中發(fā)現(xiàn)該方法仍有一些問(wèn)題需要解決，如：聚類簇個(gè)數(shù)以及字段閾值設(shè)定的問(wèn)題，都需要人為干預(yù)進(jìn)行，由于這兩個(gè)指標(biāo)設(shè)定對(duì)記錄檢測(cè)的精度有一定影響，所以針對(duì)這些不足后續(xù)工作還需要進(jìn)一步研究。