陳 亮 杜 璐 胡 康

(西安工程大學(xué)計算機科學(xué)學(xué)院 陜西 西安 710048)

0 引 言

在大數(shù)據(jù)時代，數(shù)據(jù)成為有價值的公司資產(chǎn)，可以減少和消除企業(yè)經(jīng)濟活動中的風(fēng)險，為企業(yè)的管理控制和科學(xué)決策提供合理依據(jù)，并預(yù)期給企業(yè)帶來經(jīng)濟利益[1]。公司或企業(yè)為了更好地做出決策，往往需要高質(zhì)量的數(shù)據(jù)[2]。但是由于各種原因，例如：重復(fù)輸入、不同數(shù)據(jù)源中數(shù)據(jù)采用不同的表示方式、多數(shù)據(jù)源合并造成重復(fù)等數(shù)據(jù)質(zhì)量問題，使數(shù)據(jù)中心中存在著很多的相似重復(fù)數(shù)據(jù)。這些“臟數(shù)據(jù)”導(dǎo)致了錯誤的分析結(jié)果，進而影響決策。因此數(shù)據(jù)清洗，尤其是數(shù)據(jù)清洗中的相似重復(fù)數(shù)據(jù)檢測變得尤為重要。

相似重復(fù)記錄檢測就是識別一對記錄是否表示為真實世界中的同一個實體。為了避免高代價的記錄比對，減少無意義的數(shù)據(jù)比對次數(shù)，有學(xué)者提出了一種分區(qū)算法，將大量的數(shù)據(jù)分成更小的子集[3-11]。如果相似記錄分布在同個子分區(qū)，在數(shù)據(jù)比對過程中僅與區(qū)中的記錄比對而不是全部數(shù)據(jù)[3]。常用的技術(shù)是分塊技術(shù)[4]和窗口技術(shù)[5]。其中，分塊技術(shù)將數(shù)據(jù)集分成互不相關(guān)的子集，在較小的子集內(nèi)數(shù)據(jù)聚類；窗口技術(shù)通過滑動窗口選中固定大小的數(shù)據(jù)依次與目標(biāo)數(shù)據(jù)來進行記錄比對。本文結(jié)合了分塊技術(shù)和窗口技術(shù)，提出了一種相似重復(fù)檢測算法，減少數(shù)據(jù)比較次數(shù)，提高算法運行效率。

1 相關(guān)工作

在相似重復(fù)記錄的檢測方面已經(jīng)有了一些成果。傳統(tǒng)的“排序&合并”算法先將數(shù)據(jù)庫中記錄排序，然后通過比較鄰近記錄是否相等來檢測完全重復(fù)記錄。在傳統(tǒng)的“排序&合并”思想的基礎(chǔ)上，有人提出了近鄰排序算法SNM(Sorted Neighborhood Method)[5-15]、分塊算法BLOCKING[4]和排序分塊算法SBM(Sorted Blocks Method)[3]。

SNM算法根據(jù)選定的若干個屬性字符串合并作為鍵對數(shù)據(jù)集排序，然后采用固定大小的滑動窗口進行聚類來識別相似重復(fù)記錄?；瑒哟翱诖笮〉倪x取難以控制，設(shè)定大了，勢必增加比較的次數(shù)和時間，選取過小，又可能造成算法結(jié)果遺漏[6]。BLOCKING算法采用“化整為零”的分區(qū)思想對數(shù)據(jù)排序、分塊和聚類，分塊間不做相似重復(fù)檢測。分塊的劃分直接影響到算法的結(jié)果，如果相似記錄都劃分在同分區(qū)，算法有著較高運行效率和滿意的結(jié)果，反之，算法大部分時間都是無意義的數(shù)據(jù)比對。SBM算法結(jié)合了分塊技術(shù)和窗口技術(shù)，利用滑動窗口選取數(shù)據(jù)分塊并聚類。該算法能夠通過滑動窗口技術(shù)改善了分塊劃分問題，但是仍存在一些問題：利用滑動窗口分塊導(dǎo)致每個分塊之間均有一定量的重復(fù)數(shù)據(jù)，導(dǎo)致了相同數(shù)據(jù)對多次比對的現(xiàn)象。

針對上述算法的問題，本文參考了MPN算法中滑動窗口思想和BLOCKING算法中的分塊思想[12-17]，提出了多排序字段分塊近鄰匹配算法(MBNM)，目的是為了改善BNM算法中數(shù)據(jù)多次重復(fù)匹配現(xiàn)象，提高算法運行效率。

2 分塊近鄰匹配重復(fù)檢測算法

由于多排序字段分塊近鄰匹配算法(MBNM)是基于分塊近鄰匹配重復(fù)檢測算法(BNM)，所以簡單介紹BNM算法是非常必要。分塊近鄰匹配重復(fù)檢測算法基礎(chǔ)思想是：將較大的數(shù)據(jù)集分為較小的分塊，以分塊為基礎(chǔ)單位完成分塊之間的相互比較。優(yōu)先比較相似數(shù)據(jù)較多的分塊，而從達到在較短時間得到較完整的檢測結(jié)果的目標(biāo)。BNM算法的計算過程如下：

(2) 將排好序的數(shù)據(jù)集分成若干個大小相同的分塊bn，用ri來記錄數(shù)據(jù)，分塊尺寸為S。

(3) 分塊間比較，存在相似重復(fù)記錄記為1，否則記為0。返回分塊間對比的相似重復(fù)記錄數(shù)。

(4) 比較分塊延展值，根據(jù)設(shè)定的閾值判斷是否進行二次延展。否則，停止比較，返回相似重復(fù)記錄數(shù)。

(5) 合并分塊內(nèi)相似重復(fù)記錄結(jié)果，從而得到最終的檢測結(jié)果。

(1)

在實際情況中，最好的排序字段總是不知道或者是難以找到，這樣導(dǎo)致BNM算法檢驗相似重復(fù)記錄的結(jié)果正確性不高。

3 多字段分塊近鄰匹配算法

3.1 算法介紹

“多趟(multi-pass)”執(zhí)行方法很好地解決了排序字段難找問題，就是多次執(zhí)行單字段重復(fù)檢測算法，每次采用不同排序字段排序。算法如果選取了“不好”的字段，在使用該字段的迭代過程，不但得不到較好的結(jié)果，還增加了許多無意義的數(shù)據(jù)比較次數(shù)，浪費了大量的運行時間[6]。

圖1展示了MBNM算法的實現(xiàn)過程。比如說第4行第5列的方塊表示第4分塊中的全部記錄和第5個分塊中的全部記錄的比對，方塊中的“9”數(shù)字代表存在9對相似重復(fù)記錄對。分塊對(2，2)和(5，5)的相似重復(fù)記錄數(shù)最大，表示著該分塊與鄰近分塊數(shù)據(jù)更有可能是相似重復(fù)記錄。接著算法對(2，2)和(5，5)這兩個較大的相似重復(fù)記錄分塊對延展。如圖所示，算法選擇上近鄰塊對和右近鄰塊對作為該分塊對延展對，并比較新的分塊對得到各分塊對的相似重復(fù)記錄數(shù)。重復(fù)上述過程直到所有的分塊對比較結(jié)束。

圖1 MBNM算法演示圖

3.2 算法描述

參考“多趟”執(zhí)行方法中多排序字段的思想，提出多字段分塊近鄰匹配算法MBNM(Multi-keys Blocking Neighbor Mapping)。改進算法也采用多個關(guān)鍵字段排序，但不是采用多趟執(zhí)行的方式，而是多個排序字段一起執(zhí)行。接下來結(jié)合偽代碼詳細介紹多字段分塊近鄰匹配算法(MBNM)的四個階段：

(1) 數(shù)據(jù)預(yù)處理：

算法1數(shù)據(jù)預(yù)處理dataPre(set)算法

輸入：原始數(shù)據(jù)集set

輸出：處理后的數(shù)據(jù)集D

算法對屬性進行預(yù)處理。它將空格和標(biāo)點符號視為分隔符，將屬性的字符串拆分為單詞，并按詞法對單詞進行排序。

(2) 多關(guān)鍵字定義與排序：

算法2多關(guān)鍵字排序算法

sortData(D,Ks,N,w,LowThreshold)算法

輸入：待處理的數(shù)據(jù)集D和排序字段集Ks

(2) flag=true

(3) for(int i=1;i

(4) for(int j=1;j<=w-1;j++)

(5) for(v=j+1;j<=w;j++)

(6) flag=match(Dj,Dv, LowThreshold)

(7) if(flag==false)

(8) return fales;

(9) else return true

(2)

bn={ri|i=1,2,3,…,w}

(3)

(4)

式中：enm表示n分塊和m分塊間的相似重復(fù)數(shù)據(jù)存在率，dnnm表示n分塊和m分塊間的相似重復(fù)數(shù)據(jù)，bcnm表示n分塊和m分塊間的數(shù)據(jù)比較次數(shù)。

(3) 滑動窗口選取:

分塊近鄰匹配重復(fù)檢測算法(BNM)使用固定窗口，窗口大小的選取一直存在問題。窗口選擇過小會使得檢驗的結(jié)果不準(zhǔn)確，窗口選擇過大會增加不必要的比較。新的算法(MBNM)使用自適應(yīng)的滑動窗口。

首先，設(shè)置三個參數(shù):窗口最小值、窗口最大值、閾值。本文定義wmin=4。窗口初始值w=wmin(wmin≤w≤wmax)。如果兩個記錄的相似度大于閾值，則表示對應(yīng)窗口內(nèi)的排序足夠好。

(4) 分塊比較:

算法3比較算法

compare(blocks,bPairs,order)

輸入：待處理的數(shù)據(jù)集D和排序字段集Ks

輸出：比較結(jié)果bPairs

(1) for(k=0;k<=|Ks|-1;k++){

(2) bPairs={<1,1,-1,k>,…, }

(3) order[k]=sort(D,Ks[k],S,bPairs)

(4) bPairs=bPairs∪pairs

(5) }

(6) blocks=loadblocks(bPairs,S,order)

(7) compare(blocks,bPairs,order)

(8) bPairs=bPairs∪pBPs

blocks集合保存著分塊的數(shù)據(jù)；bPairs集合用于存放分塊對信息，分塊對信息采用一個三元組(分塊1編號，分塊2編號，相似重復(fù)記錄對數(shù))來表示。分塊之間對比形成如圖1的分塊矩陣，分塊矩陣存在對稱性，因此只分析行列式的右上部分。采用二元組(bn,bm)表示分塊之間的數(shù)據(jù)對比，相似重復(fù)記錄用(ri,rj)表，Cnm表示分塊n和分塊m之間存在相似重復(fù)數(shù)。

(bn,bm)={(ri,rj)|ri∈bn,rj∈bm}

(5)

|(bn，bm)|=dnnm

(6)

先計算各分塊內(nèi)的相似重復(fù)數(shù)，得到初始分塊對相似重復(fù)數(shù)據(jù)，即(bn,bn)，選取dnnn較大的分塊對(bn,bn)并向旁邊分塊擴展生成新分塊對，記作(bn，bm)+。

(bn，bm)+={(bn+1，bm),(bn，bm+1)}

(7)

為了確保分塊對能有較高的相似重復(fù)數(shù)據(jù)，設(shè)置分塊間隙R限制分塊對的擴展，減少比較次數(shù)。 |n+1-m|≤R&|m+1-n|≤R。

對比新分塊對得到各分塊對的相似重復(fù)記錄數(shù)。重復(fù)上述過程直到所有的分塊對比對過。

(5) 計算傳遞閉包:

由于成對的記錄的選取比對，導(dǎo)致運行的結(jié)果的不是關(guān)閉的，例如(ra,rb)和(rb,rc)被檢測出是重復(fù)記錄，但是最后的運行結(jié)果可能沒有(ra,rc)。因此，在算法最后中用傳遞閉包技術(shù)不僅能得到較好的重復(fù)記錄集，并能解決部分紕漏的問題。

3.3 算法復(fù)雜度分析

多字段分塊近鄰匹配算法得時間復(fù)雜度主要包括三部分，記作T1、T2、T3。T1表示多關(guān)鍵字選取的時間復(fù)雜度，根據(jù)檢測目標(biāo)來確定數(shù)據(jù)集DK，T1=O(N)；算法進行多次排序，排序后調(diào)用bPairs函數(shù)，因為DK的個數(shù)不大于k，T2≤(NlogN+2mw)，mlogN,T3=O(NlogN)。綜上所述，MBNM算法的時間復(fù)雜度為Θ(n((m+2w)/4+logn))。其他算法時間復(fù)雜度[3]如表1所示。

表1 時間復(fù)雜度比較

改進算法根據(jù)不同的關(guān)鍵字段排序，為了節(jié)約內(nèi)存，改進算法只保存排序后的數(shù)據(jù)的主鍵。改進算法在執(zhí)行時優(yōu)先選擇相似重復(fù)率較高分塊延展，降低了排序字段本身好壞對算法運行時間的影響。改進算法放棄延展過慢的分塊，進一步減少算法中無意義的數(shù)據(jù)比較，從而提高算法的運行效率。

4 實驗結(jié)果分析

4.1 實驗環(huán)境

實驗環(huán)境是 Lenovo PC CPU Inter(R)Core(TM)2 Duo E8400 @ 3.00 GHz，Ram 2.00 GB，Windows 7 32位操作系統(tǒng)。采用Eclipse Java編程工具實現(xiàn)算法，Java 環(huán)境Java 1.7以上。

實驗數(shù)據(jù)來源于某市國家電網(wǎng)用戶信息的采集數(shù)據(jù)，包括用戶的用電數(shù)據(jù)、部分試點事業(yè)單位的采集數(shù)據(jù)等，由于來源廣泛導(dǎo)致采集到的數(shù)據(jù)必然存在大量的重復(fù)。度量相似檢測算法有效性的三個主要標(biāo)準(zhǔn)包括查全率、查準(zhǔn)率和F值，評價算法復(fù)雜度的參考標(biāo)準(zhǔn)為運行時間。為了檢驗檢測算法的有效性，設(shè)計以下實驗。分別從數(shù)據(jù)源中提取四組數(shù)據(jù)，對四種算法進行比較，四組數(shù)據(jù)量分別為58.3、95.1、128.8和136.7萬。通過軟件和人工等方式對上數(shù)據(jù)分別處理，使之分別包含0.43、0.87、1.38和1.72萬條相似重復(fù)記錄。對數(shù)據(jù)集觀察分析后，確定使用其中的“name”、“contacts”、“title”三個字段為關(guān)鍵排序字段。

評價標(biāo)準(zhǔn)采用了查全率(Recall)、查準(zhǔn)率(Precision)、F值(F-score)和運行時間四個指標(biāo)來比較四種算法。查全率，查準(zhǔn)率，F(xiàn)值計算公式如下：

(1) 查準(zhǔn)率:

(8)

(2) 查全率:

(9)

(3) F值(F-score):

(10)

其中TP為被正確識別的重復(fù)元組數(shù)，F(xiàn)P為錯誤識別出的重復(fù)元組數(shù)，F(xiàn)N未識別出的重復(fù)記錄數(shù)。則TP+FP為識別出的重復(fù)元組數(shù)，包括正確識別的和錯誤識別的重復(fù)元組數(shù)。TP+FN為實際存在的重復(fù)元組總數(shù)。

4.2 相似重復(fù)檢測算法對比

MBNM算法使用的多關(guān)鍵字排序和自適應(yīng)滑動窗口來進行數(shù)據(jù)比較前的處理。由于分塊大小和分塊間隙對算法效率有直接影響。在保證四種不同算法的分析數(shù)據(jù)量相同的情況進行了比較實驗。四種算法有著明顯的差別，比較結(jié)果如下：

實驗表明，SBM由于只采用傳統(tǒng)的固定窗口，識別的結(jié)果受窗口大小影響較大。MPN算法由于固定滑動窗口，窗口選取過大或過小對查全率影響較大。由于MBNM采用自適應(yīng)滑動窗口和多趟檢測技術(shù)，大大減少記錄比對時間和總體測時間，既保證查全率又在一定程度上減少檢測時間，從而提高了查全率。如圖2所示。

圖2 查全率比較圖

實驗表明，MPN算法由于采用傳遞閉包，準(zhǔn)確率明顯較低。在數(shù)據(jù)量較小時，四者的查準(zhǔn)率差異較小，但隨著數(shù)量的增加，四者查準(zhǔn)率都有一定程度的降低，最終趨于穩(wěn)定。MBNM算法的查準(zhǔn)率更加穩(wěn)定且查準(zhǔn)率較高。如圖3所示。

圖3 查準(zhǔn)率比較圖

MPN、SBM、BNM、MBNM四種算法的F值與數(shù)據(jù)量之間的關(guān)系如圖4可以看出。算法的F值隨著數(shù)據(jù)量的增加而降低，并且四種算法的F值之間的差異越來越大，MBNM略優(yōu)于BNM算法。

圖4 F值比較圖

圖5比較結(jié)果表明，在相同機器、相同數(shù)據(jù)下，MBNM算法在時間復(fù)雜度上有較好的表現(xiàn)。由于利用自適應(yīng)滑動窗口降低了比較數(shù)據(jù)集，并利用K關(guān)鍵字多次排序一次執(zhí)行加快了數(shù)據(jù)檢測的效率。本文提出的算法的時間開銷與相似重復(fù)記錄的多少有關(guān)，相似重復(fù)記錄數(shù)越多，則時間復(fù)雜度越低，反之越高。

圖5 算法消耗時間比較圖

綜上所述，本文提出的多排序字段分塊近鄰匹配算法(MBNM)的運行效率優(yōu)于其他算法。

5 結(jié) 語

本文研究了如何檢測重復(fù)記錄，結(jié)合了窗口技術(shù)和分塊技術(shù)，提出了分塊近鄰匹配算法，該算法在限定的時間內(nèi)提高了相似重復(fù)記錄匹配的效率。算法通過實時的分塊匹配結(jié)果動態(tài)地改變了匹配數(shù)據(jù)的順序，優(yōu)先對更有希望是重復(fù)的數(shù)據(jù)對進行匹配，并舍棄較差的分塊對的比較。減少了算法的比較次數(shù)進而減少了算法的時間，并提出了多字段排序和自適應(yīng)滑動窗口技術(shù)改進算法，多個字段同時和自適應(yīng)滑窗進行分塊比較。最后并通過實驗和傳統(tǒng)“排序&合并”思想中的其他兩種算法比較驗證了該算法的有效性。接下來的工作就是優(yōu)化算法的某些過程，進一步縮短算法的運行時間和提高算法的效率并應(yīng)用到實際中去。