基于分塊和滑窗技術(shù)的相似重復(fù)記錄檢測(cè)算法研究

陳 亮 杜 璐 胡 康

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

0 引 言

在大數(shù)據(jù)時(shí)代，數(shù)據(jù)成為有價(jià)值的公司資產(chǎn)，可以減少和消除企業(yè)經(jīng)濟(jì)活動(dòng)中的風(fēng)險(xiǎn)，為企業(yè)的管理控制和科學(xué)決策提供合理依據(jù)，并預(yù)期給企業(yè)帶來經(jīng)濟(jì)利益[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)致了錯(cuò)誤的分析結(jié)果，進(jìn)而影響決策。因此數(shù)據(jù)清洗，尤其是數(shù)據(jù)清洗中的相似重復(fù)數(shù)據(jù)檢測(cè)變得尤為重要。

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

(1)

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

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

3.1 算法介紹

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

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

圖1 MBNM算法演示圖

3.2 算法描述

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

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

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

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

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

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

(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) 滑動(dòng)窗口選取:

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

首先，設(shè)置三個(gè)參數(shù):窗口最小值、窗口最大值、閾值。本文定義wmin=4。窗口初始值w=wmin(wmin≤w≤wmax)。如果兩個(gè)記錄的相似度大于閾值，則表示對(duì)應(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集合用于存放分塊對(duì)信息，分塊對(duì)信息采用一個(gè)三元組(分塊1編號(hào)，分塊2編號(hào)，相似重復(fù)記錄對(duì)數(shù))來表示。分塊之間對(duì)比形成如圖1的分塊矩陣，分塊矩陣存在對(duì)稱性，因此只分析行列式的右上部分。采用二元組(bn,bm)表示分塊之間的數(shù)據(jù)對(duì)比，相似重復(fù)記錄用(ri,rj)表，Cnm表示分塊n和分塊m之間存在相似重復(fù)數(shù)。

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

(5)

|(bn，bm)|=dnnm

(6)

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

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

(7)

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

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

(5) 計(jì)算傳遞閉包:

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

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

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

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

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

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

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

實(shí)驗(yà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編程工具實(shí)現(xiàn)算法，Java 環(huán)境Java 1.7以上。

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

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

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

(8)

(2) 查全率:

(9)

(3) F值(F-score):

(10)

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

4.2 相似重復(fù)檢測(cè)算法對(duì)比

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

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

圖2 查全率比較圖

實(shí)驗(yàn)表明，MPN算法由于采用傳遞閉包，準(zhǔn)確率明顯較低。在數(shù)據(jù)量較小時(shí)，四者的查準(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é)果表明，在相同機(jī)器、相同數(shù)據(jù)下，MBNM算法在時(shí)間復(fù)雜度上有較好的表現(xiàn)。由于利用自適應(yīng)滑動(dòng)窗口降低了比較數(shù)據(jù)集，并利用K關(guān)鍵字多次排序一次執(zhí)行加快了數(shù)據(jù)檢測(cè)的效率。本文提出的算法的時(shí)間開銷與相似重復(fù)記錄的多少有關(guān)，相似重復(fù)記錄數(shù)越多，則時(shí)間復(fù)雜度越低，反之越高。

圖5 算法消耗時(shí)間比較圖

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

5 結(jié) 語(yǔ)

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