賀建英

（四川文理學(xué)院智能制造學(xué)院，四川達(dá)州 635000）

大數(shù)據(jù)時(shí)代獲取的數(shù)據(jù)中存在許多重復(fù)數(shù)據(jù)，會(huì)影響數(shù)據(jù)處理的結(jié)果。傳統(tǒng)重復(fù)記錄檢測技術(shù)不再適用。目前對重復(fù)檢測的主要思想有兩類:SNM 和DDR[1-2]。已有研究表明，數(shù)據(jù)維數(shù)越高，DDR 方法比SNM 更為理想，DDR 通過使用R-樹來構(gòu)建空間索引從而提高訪問效率。該文在DDR 方法的基礎(chǔ)上借助不確定性概念，把重復(fù)問題看成聚類問題，使用NSKSA(Not Sure K-value Spatital Algorithm)來構(gòu)建R-樹，其結(jié)構(gòu)更為緊湊，減少了訪問次數(shù)。同時(shí)提出高效的ADDR(Ameliorate Duplicate Dtectcion using Rtree)算法實(shí)現(xiàn)空間聚類的重復(fù)檢測操作。通過實(shí)驗(yàn)表明，在構(gòu)建R-樹時(shí)，NSKSA更為高效，ADDR 算法也能更有效地解決重復(fù)記錄的檢測問題。

1 相關(guān)工作

1.1 研究現(xiàn)狀

對重復(fù)記錄檢測問題的研究中，已出現(xiàn)了一系列相關(guān)的研究成果[3-7]。如最早期采用的“排序-合并”算法，首先對記錄進(jìn)行排序，然后再對鄰近記錄進(jìn)行比較來判斷其是否相等。韓京宇等人[8]提出了一種q-gram 層次空間聚類檢測方法，將數(shù)據(jù)映射成空間中的點(diǎn)，有效解決了傳統(tǒng)“排序-合并”算法中因部分相似記錄的字符位置敏感而不能排在鄰近位置的相關(guān)問題，提高了重復(fù)檢測的精度，但針對字符串的qgram 距離，仍存在一定的局限性。當(dāng)前普遍采用的是Hernandze 等人提出的SNM[1]、朱蔚恒和印鑒提出的DDR 方法[2]，以及基于這類方法的相關(guān)改進(jìn)方法。

重復(fù)檢測的目的是找到大量數(shù)據(jù)集中能表示現(xiàn)實(shí)世界中同一個(gè)實(shí)體的相關(guān)集合，是對數(shù)據(jù)集合進(jìn)行預(yù)處理操作。在大數(shù)據(jù)環(huán)境下，主要是對多種數(shù)據(jù)源和異構(gòu)的數(shù)據(jù)記錄檢查表達(dá)同一個(gè)實(shí)體的相關(guān)記錄，以達(dá)到對數(shù)據(jù)進(jìn)行清洗，為后續(xù)數(shù)據(jù)的進(jìn)一步使用排除干擾的目的[9-10]。在SNM 中提出了不同數(shù)據(jù)源進(jìn)行重復(fù)檢測的流程，如圖1 所示[8]。

圖1 對兩個(gè)數(shù)據(jù)源進(jìn)行重復(fù)檢測的流程

從圖1 的流程可以看出，對數(shù)據(jù)進(jìn)行重復(fù)檢測的影響有三個(gè)：一是對數(shù)據(jù)的清洗和標(biāo)準(zhǔn)化操作，這一步相當(dāng)于是預(yù)處理操作，如果對數(shù)據(jù)的預(yù)處理操作能做得更好，可以減少索引的建立。二是如何利用索引來減少記錄對的比較次數(shù)。三是相似度閾值的定義對最終算法的效率有很大的影響。

1.2 相關(guān)方法

1.2.1 SNM

SNM(Sorted Neighborhood Method）是利用排序函數(shù)、分塊（blocking）、窗口（window）的方式把整個(gè)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行排序，利用分塊把可能重復(fù)的記錄排在一起，最后使用窗口技術(shù)在一個(gè)固定長度的窗口中進(jìn)行兩兩比較，并標(biāo)識(shí)出重復(fù)的記錄。這種固定窗口長度的方式，在重復(fù)記錄不多時(shí)，也要進(jìn)行兩兩比較，造成時(shí)間上的浪費(fèi)。

1.2.2 DDR方法

通過分析SNM 方法的不足，朱蔚恒等人提出了一種基于聚類思想的高維數(shù)據(jù)重復(fù)檢測算法——DDR（Duplicate Dtectcion using R-tree）算法。該方法將重復(fù)檢測問題視為一類特殊的聚類問題。其核心思想是聚類，利用具有聚類特性的TGS 方法建立R-樹[11]，得到高效的索引，通過在R-樹的葉子中進(jìn)行重復(fù)比較，輸出重復(fù)記錄。最后利用Apriori 性質(zhì)對高維數(shù)據(jù)集進(jìn)行并行處理，提高重復(fù)檢測的效率。其具體操作可分為如下三步：

1）建立R-樹。利用R-樹的索引將空間對象及索引空間進(jìn)行近似處理，其思想來源于聚類。

2）對所建立的R-樹進(jìn)行遍歷。利用一個(gè)指定的閥值t對R-樹中的葉節(jié)點(diǎn)進(jìn)行兩兩的重復(fù)比較。對不是同一個(gè)MBR 目錄矩形的葉節(jié)點(diǎn)不再進(jìn)行比較，減少了比較次數(shù)。

3）利用Apriori 性質(zhì)，對高維數(shù)據(jù)進(jìn)行并行處理。采用Map-Reduce 方法來高效地實(shí)現(xiàn)對R-樹的遍歷及重復(fù)檢測工作。

1.2.3 方法的創(chuàng)新與改進(jìn)

重復(fù)記錄主要是因?yàn)橥粋€(gè)實(shí)體對象在不同數(shù)據(jù)源中采用了不同的表現(xiàn)形式，如表達(dá)方式的不同、簡寫、拼寫錯(cuò)誤或者人為刻意干擾等。從而產(chǎn)生大量的重復(fù)記錄。這些大量相似的重復(fù)記錄，對數(shù)據(jù)的后續(xù)處理，如數(shù)據(jù)分析、數(shù)據(jù)挖掘、數(shù)據(jù)統(tǒng)計(jì)等操作造成了很大的干擾，嚴(yán)重影響數(shù)據(jù)處理的最終結(jié)果。大數(shù)據(jù)環(huán)境下的多維數(shù)據(jù)重復(fù)檢測是一個(gè)亟待解決的難點(diǎn)問題。因?yàn)榇髷?shù)據(jù)環(huán)境下的數(shù)據(jù)來源不再單一，數(shù)據(jù)結(jié)構(gòu)不再統(tǒng)一（結(jié)構(gòu)化的數(shù)據(jù)、非結(jié)構(gòu)化的數(shù)據(jù)和半結(jié)構(gòu)化的數(shù)據(jù)），數(shù)據(jù)量非常龐大，這些都對重復(fù)檢測提出了新的挑戰(zhàn)。對如何提高多維數(shù)據(jù)重復(fù)檢測方法的效率更是提出了嚴(yán)格的要求。該文旨在研究如何提高多維數(shù)據(jù)重復(fù)檢測的方法，從而提高多維數(shù)據(jù)重復(fù)記錄的檢查效率。該文在通過分析DDR 方法構(gòu)建R-樹和利用Apriori 性質(zhì)采用Map-Reduce 方法對多維數(shù)據(jù)進(jìn)行去重的過程中主要關(guān)注如下兩點(diǎn):1）R-樹的構(gòu)建。2）對多維數(shù)據(jù)去重；多維數(shù)據(jù)去重的創(chuàng)新點(diǎn)從兩個(gè)方面入手：①在DKSC 算法[12]構(gòu)建R-樹的基礎(chǔ)上，研究更優(yōu)的NSKSA 構(gòu)建R-樹，使得高維數(shù)據(jù)構(gòu)建R-樹時(shí)花費(fèi)更少的時(shí)間，縮短構(gòu)建R-樹的過程。②在DDR 的基礎(chǔ)上研究更優(yōu)的ADDR 算法，提高對R-樹的遍歷過程，減少訪問R-樹的時(shí)間。從構(gòu)建R-樹和訪問R-樹這兩個(gè)方面提高效率，進(jìn)而提高多維數(shù)據(jù)去重的效率。

2 R-樹及其改進(jìn)

2.1 R-樹的構(gòu)建基礎(chǔ)

通過分析DKSC 算法，發(fā)現(xiàn)該算法雖然可以動(dòng)態(tài)找出最優(yōu)K 值使得MBR 內(nèi)的數(shù)據(jù)更為緊湊，且能解決離群數(shù)據(jù)的干擾，但該算法仍然能在一定程度上導(dǎo)致MBR 區(qū)域的重疊，增加后續(xù)索引的訪問路徑。故該文在DKSC 算法的基礎(chǔ)上提出另一種動(dòng)態(tài)找出最優(yōu)值K 的聚類算法——NSKSA 來構(gòu)建R-樹，使MBR 減少重復(fù)區(qū)域，促使空間節(jié)點(diǎn)更為緊湊。另外在創(chuàng)建R-樹時(shí)，為存放空間數(shù)據(jù)的葉節(jié)點(diǎn)增加兩個(gè)屬性：Visited和Isbelong。其中，Visited是為了方便在R-樹建立好后，進(jìn)行重復(fù)檢測遍歷時(shí)用來標(biāo)記該節(jié)點(diǎn)是否已經(jīng)訪問過；Isbelong屬性用來表示節(jié)點(diǎn)中是否包含當(dāng)前正在進(jìn)行重復(fù)檢測的葉子節(jié)點(diǎn)的數(shù)據(jù)相重復(fù)的記錄，其初值均為0。

2.2 相關(guān)定義

1）R-樹及其節(jié)點(diǎn)

隨著空間索引結(jié)構(gòu)的不斷發(fā)展，空間結(jié)構(gòu)索引技術(shù)主要包含以下四類[13]：基于哈希的網(wǎng)格索引、基于二叉樹的索引、基于空間填充曲線的索引以及基于B-樹的索引。R-樹正是B-樹在高維空間中的擴(kuò)展，且它的基本思想是將空間數(shù)據(jù)進(jìn)行近似處理，是目前空間數(shù)據(jù)使用最為廣泛的一種空間索引結(jié)構(gòu)。R-樹的節(jié)點(diǎn)有兩類，一類是葉節(jié)點(diǎn)，另一類是非葉節(jié)點(diǎn)。根據(jù)2.1 節(jié)中的描述，把這兩類節(jié)點(diǎn)定義為如下形式：

葉節(jié)點(diǎn)：

非葉節(jié)點(diǎn)：

其中，Count為節(jié)點(diǎn)所含數(shù)據(jù)項(xiàng)或索引的個(gè)數(shù)，Level表示節(jié)點(diǎn)的類型，Visited表示該節(jié)點(diǎn)是否被訪問過，初值為0。Isbelong表示該節(jié)點(diǎn)中是否包含與其他節(jié)點(diǎn)相似的記錄，初值為0。＜Oi＜S＞,MBRi＞表示葉節(jié)點(diǎn)中的一個(gè)數(shù)據(jù)項(xiàng)，Oi代表第i個(gè)空間數(shù)據(jù)，MBRi為該空間數(shù)據(jù)在k維空間中的數(shù)據(jù)矩形，＜S＞代表每個(gè)數(shù)據(jù)項(xiàng)的步長，表明與該數(shù)據(jù)項(xiàng)同簇的數(shù)據(jù)項(xiàng)有S個(gè)，其初值為0。＜Pi,MBRi＞稱為索引項(xiàng)，Pi表示指向其子樹的根節(jié)點(diǎn)的指針，MBRi指包含子樹根節(jié)點(diǎn)的子樹空間索引的目錄矩形。

2）空間距離指標(biāo)

為了方便描述，該文仍采用歐式距離來表示空間數(shù)據(jù)之間的距離[14]，其用d表示。通過歐式距離可以方便地判斷兩個(gè)數(shù)據(jù)是否為鄰近空間數(shù)據(jù)，為方便表示，可定義一個(gè)用來衡量兩個(gè)空間數(shù)據(jù)距離的指標(biāo)R[15]，其定義如式（1）所示：

其中，m表示要判斷區(qū)域的空間數(shù)據(jù)的數(shù)量，A為要判斷空間數(shù)據(jù)的區(qū)域面積。判斷某一個(gè)空間數(shù)據(jù)是否為鄰近空間數(shù)據(jù)，可以通過式（2）來判定。

其中，f(i)代表第i個(gè)空間數(shù)據(jù)，第i個(gè)空間數(shù)據(jù)與某個(gè)指定空間數(shù)據(jù)的距離為di，當(dāng)di≤R時(shí)，則可以說第i個(gè)空間數(shù)據(jù)與該數(shù)據(jù)是鄰近空間數(shù)據(jù)，反之則不是。

3）聚類測量度函數(shù)

為進(jìn)一步判斷所生成的類是否緊湊，可根據(jù)所有簇內(nèi)中的數(shù)據(jù)與聚類中心的距離平方差的和最小的原則，定義一個(gè)測定函數(shù)來判斷，其函數(shù)的定義如式（3）所示[16]：

其中，第c個(gè)類的空間數(shù)據(jù)為Dc={dc1,dc2,…,dcn}，r為Dc中的數(shù)據(jù)，k為聚類數(shù)。若測定函數(shù)的值在逐漸減少，則說明聚類狀態(tài)逐步趨向于最佳狀態(tài)。這種方式僅僅對簇內(nèi)有效，不適用于整個(gè)數(shù)據(jù)空間。具有一定的局限性。

2.3 NSKSA構(gòu)建R-樹

NSKSA 的設(shè)計(jì)思想是先把整個(gè)空間區(qū)域看成一個(gè)類，此時(shí)k的值為1。找到該類中距離最大的兩個(gè)數(shù)據(jù)，對這兩個(gè)數(shù)據(jù)計(jì)算其余數(shù)據(jù)與它們的距離，利用歐式距離d和式（1）、（2）判斷哪些數(shù)據(jù)是這兩個(gè)數(shù)據(jù)的鄰近數(shù)據(jù)和非鄰近數(shù)據(jù)。并分別把與兩個(gè)數(shù)據(jù)為鄰近數(shù)據(jù)的集合放在一起形成一個(gè)新的類。特別地，如果一個(gè)數(shù)據(jù)同時(shí)是這兩個(gè)數(shù)據(jù)的鄰近數(shù)據(jù)時(shí)，則該數(shù)據(jù)將放在距離近的那個(gè)數(shù)據(jù)集中。然后把所有的非鄰近數(shù)據(jù)放在一個(gè)臨時(shí)的temp 類中，此時(shí)k的值為2。調(diào)用公式分別計(jì)算每個(gè)類（包括temp類）的聚類測量度，判斷此時(shí)聚類測量度的值是否在逐步減少。如果在減少，則分別對新生成的兩個(gè)類使用相同的方式，找到該類中距離最大的兩個(gè)數(shù)據(jù)，然后找到這兩個(gè)數(shù)據(jù)的鄰近數(shù)據(jù)和非鄰近數(shù)據(jù)，建立新的類，然后再把非鄰近數(shù)據(jù)繼續(xù)存儲(chǔ)在temp 類中，如果聚類測量度的值變化非常小或者沒發(fā)生變化，那么就停止對該類進(jìn)行進(jìn)一步的分類操作。此時(shí)k的值也隨之發(fā)生變化。對所生成的新類繼續(xù)遞歸調(diào)用此方法，會(huì)得到新的類和非鄰近數(shù)據(jù)，把每次得到的非鄰近數(shù)據(jù)均存放在temp 類中。此時(shí)的k值為所輸出的空間聚類個(gè)數(shù)。當(dāng)k的值和R-樹的節(jié)點(diǎn)能容納的最大個(gè)數(shù)M相等或者聚類測量度函數(shù)值變化不大時(shí)，停止遞歸。分別把k個(gè)類作為R-樹的子節(jié)點(diǎn)，把類中的數(shù)據(jù)作為子節(jié)點(diǎn)的MBR范圍內(nèi)的葉節(jié)點(diǎn)，因?yàn)镽-樹是一棵平衡樹，故需要對k值進(jìn)行均衡調(diào)整，把遞歸調(diào)用后生成的非鄰近數(shù)據(jù)分給數(shù)據(jù)小于平均值的類。

以圖2 所示數(shù)據(jù)集作為初始空間數(shù)據(jù)的集合為例，假設(shè)兩個(gè)空間數(shù)據(jù)距離的指標(biāo)R=3，在圖中可以判斷R5和R6是距離最遠(yuǎn)的兩個(gè)空間數(shù)據(jù)。因此，以它們兩個(gè)為起點(diǎn)，分別計(jì)算這兩個(gè)數(shù)據(jù)到其他數(shù)據(jù)的空間距離。其值如表1、表2 所示。

表1 R5與其他空間數(shù)據(jù)的距離

表2 R6與其他空間數(shù)據(jù)的距離

因R=3，通過式（2）可知，在R5中滿足距離不大于3 的集合為{R1,R2,R5,R8,R9}，在R6中滿足距離不大于3 的集合為{R3,R6,R10}，剩下的{R4,R7}為非鄰近數(shù)據(jù)，放在temp 類中。此時(shí)得到兩個(gè)空間聚類，假設(shè)此時(shí)這兩個(gè)空間聚類是最優(yōu)的，那么只需要通過上述相同方法判斷temp 類中有沒有聚類，temp 中只剩下R4、R7且距離大于R，故不能生成新的聚類，此時(shí)k的值為2。建立樹時(shí)只需要建立一個(gè)子節(jié)點(diǎn)為2，跟節(jié)點(diǎn)為1 的樹，為了保持R-樹的平衡，故需要把非鄰近數(shù)據(jù)放在葉節(jié)點(diǎn)數(shù)不滿M的節(jié)點(diǎn)上。故得到的聚類簇為{R1,R2,R5,R8,R9}、{R3,R6,R10,R4,R7}兩個(gè)集合。構(gòu)建R-樹的算法如下所示：

算法1 構(gòu)建R-樹

根據(jù)改進(jìn)的R-樹算法，根據(jù)圖2 可以構(gòu)建如圖3 所示的R-樹。

圖3 改進(jìn)后構(gòu)建R-樹的結(jié)構(gòu)

3 利用改進(jìn)的R-樹進(jìn)行高維去重檢測

3.1 使用ADDR實(shí)現(xiàn)R-樹的高維去重處理

圖3 所建立的R-樹中，在葉節(jié)點(diǎn)內(nèi)部，數(shù)字表示的是空間數(shù)據(jù)的數(shù)據(jù)項(xiàng)。根據(jù)圖的結(jié)構(gòu)，對R-樹的遍歷過程描述如下：

1）當(dāng)訪問的節(jié)點(diǎn)為非葉節(jié)點(diǎn)時(shí)，直接設(shè)置該節(jié)點(diǎn)的Visited屬性為1，標(biāo)識(shí)該節(jié)點(diǎn)已經(jīng)訪問過。

2）繼續(xù)訪問該節(jié)點(diǎn)的MBR（目錄矩形）所包含的節(jié)點(diǎn)。

3）當(dāng)訪問到葉節(jié)點(diǎn)時(shí)，利用葉節(jié)點(diǎn)的上層節(jié)點(diǎn)的目錄矩形標(biāo)識(shí)對已經(jīng)訪問過的節(jié)點(diǎn)中可能包含重復(fù)記錄的節(jié)點(diǎn)，設(shè)置Isbelong=1。

4）遍歷葉節(jié)點(diǎn)中的每一個(gè)數(shù)據(jù)項(xiàng)，搜索所有已經(jīng)訪問過且與數(shù)據(jù)項(xiàng)O的距離小于閥值t的葉子，并保存在一個(gè)集合data 中。

5）對葉節(jié)點(diǎn)內(nèi)部的數(shù)據(jù)項(xiàng)進(jìn)行對比，并重新建立一個(gè)方便后續(xù)查找的序。

6）遍歷結(jié)束。

此時(shí)對用改進(jìn)的方法構(gòu)建R-樹進(jìn)行遍歷操作后，葉節(jié)點(diǎn)內(nèi)進(jìn)行了重新排序。其具體算法如下：

算法2 對構(gòu)建的R-樹進(jìn)行遍歷并輸出重復(fù)記錄

輸入：構(gòu)建的R-樹

輸出：重復(fù)記錄對

在算法2 中，假定閥值t=2，對每個(gè)訪問過的葉節(jié)點(diǎn)內(nèi)部進(jìn)行分簇排序操作，并對兩個(gè)空間數(shù)據(jù)進(jìn)行檢測，判斷是否為重復(fù)數(shù)據(jù)并輸出，其遍歷后R-樹的結(jié)構(gòu)如圖4 所示。

在圖4 的R-樹遍歷過程中，首先訪問到的是非葉節(jié)點(diǎn)P1，然后訪問非葉節(jié)點(diǎn)中對應(yīng)的MBR 所包含的子節(jié)點(diǎn)P2、P3，P2中包含R1、R2、R5、R8、R9，緊接著訪問MBR 中的第一個(gè)節(jié)點(diǎn)R1，因除R1以外，沒有節(jié)點(diǎn)被訪問過，故直接對R1中的數(shù)據(jù)項(xiàng)進(jìn)行分簇排序操作，因?yàn)閞1、r2、r5它們兩兩之間的距離均小于等于閾值t=2，故它們在同一簇中，它們所對應(yīng)的步長也自動(dòng)加1，表明該數(shù)據(jù)項(xiàng)的后面有幾項(xiàng)和該數(shù)據(jù)項(xiàng)是在同一個(gè)簇中。而r3、r4在一簇中，r6為一簇。對每個(gè)訪問過的葉節(jié)點(diǎn)都要做一次這樣的分簇操作，并輸出是同一簇的數(shù)據(jù)對。此時(shí)在R1節(jié)點(diǎn)中輸出的重復(fù)記錄對為(4,2)，(4,3)，(2,3)，(9,11)，(1)。

圖4 遍歷后R-樹的結(jié)構(gòu)

3.2 ADDR算法的處理

利用聚類思想在葉節(jié)點(diǎn)的上一層所包含的目錄矩形所在的葉節(jié)點(diǎn)中，找到Isbelong為1 的葉節(jié)點(diǎn)，利用Map_Reduce 方法判斷是否有重復(fù)記錄。過程如下：在Map 函數(shù)中利用閾值t判斷葉節(jié)點(diǎn)中通過ADDR 算法輸出是否包含有潛質(zhì)的重復(fù)記錄對。將重復(fù)記錄對作為鍵，值設(shè)置為1，并讓這個(gè)鍵值對作為Reduce 函數(shù)的輸入，Reduce 函數(shù)對Map 函數(shù)的輸出結(jié)果進(jìn)行計(jì)數(shù)，有相同的鍵值就累計(jì)在一起。因數(shù)據(jù)集的維度可能有所不同，因此當(dāng)累計(jì)的值達(dá)到一個(gè)閾值h，就可以認(rèn)為兩條記錄是相同的，輸出重復(fù)記錄。因Map 工作機(jī)是獨(dú)立運(yùn)行的，故每個(gè)工作機(jī)上都會(huì)運(yùn)行一個(gè)ADDR 算法。會(huì)重復(fù)執(zhí)行很多次，最壞情況下會(huì)運(yùn)行n(n-1)/2,嚴(yán)重影響執(zhí)行效率。故該文最后借鑒文獻(xiàn)[2]使用高維數(shù)據(jù)的Apriori性質(zhì)進(jìn)行重復(fù)檢查。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)方法與實(shí)驗(yàn)數(shù)據(jù)

文中的實(shí)驗(yàn)主要從兩個(gè)方面進(jìn)行比較，一方面是R-樹的構(gòu)建算法NSKSA 與DKSC 和TGS 算法的比較。另一方面是DDR 與ADDR 算法的效率的比較。該實(shí)驗(yàn)用Java 語言來實(shí)現(xiàn)，使用百度地圖提供的Javascript API 獲取空間數(shù)據(jù)。為了驗(yàn)證方法的有效性，該文隨機(jī)生成了四組指定范圍內(nèi)的空間數(shù)據(jù)，并人為修改了全部的空間數(shù)據(jù)，把修改后的數(shù)據(jù)和原始數(shù)據(jù)組合在一起形成了新的數(shù)據(jù)集D1-D4，如表3 所示。

表3 數(shù)據(jù)集信息

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

首先比較該文NSKSA 構(gòu)建R-樹與DKSC 算法和TGS 算法構(gòu)建R-樹的時(shí)間消耗，如表4 所示。

表4 R-樹構(gòu)建時(shí)間實(shí)驗(yàn)結(jié)果

通過構(gòu)建R-樹索引在相同數(shù)據(jù)集情況下不同構(gòu)建方式所消耗的時(shí)間對比可以看出，TGS 所消耗的時(shí)間最少，因其采用分組的方式，所使用的時(shí)間復(fù)雜度最小。而DKSC 和NSKSA 構(gòu)建時(shí)間偏多，因?yàn)檫@兩種算法中都采用在聚類中動(dòng)態(tài)確定k值的大小，且還要不斷計(jì)算每次聚類的聚心值，用這個(gè)值去處理離群空間數(shù)據(jù)。而對NSKSA 而言，在最后還需要對非鄰居數(shù)據(jù)進(jìn)行一次處理，所以這兩種方式所花費(fèi)的時(shí)間稍微偏多。

對DDR 算法和ADDR 算法，使用數(shù)據(jù)集D4，利用一個(gè)有五個(gè)Map 工作機(jī)的Map-Reduce 系統(tǒng)，進(jìn)行重復(fù)檢測，利用了Apriori 性質(zhì)并設(shè)定不同的閾值，實(shí)驗(yàn)結(jié)果如表5 所示。

表5 8維數(shù)據(jù)集中不同算法比較次數(shù)

從表5 可以看出，隨著閾值t的增大，每個(gè)Map工作機(jī)上潛在重復(fù)的記錄的數(shù)量越來越多，這是因?yàn)殚撝翟酱?，相似?shù)據(jù)越多造成的。但當(dāng)閾值t確定時(shí)，很明顯ADDR 算法比DDR 算法中的重復(fù)記錄的數(shù)量要少近10%，從而導(dǎo)致重復(fù)候選集的數(shù)量也隨著減少。但從實(shí)驗(yàn)的最終結(jié)果來看，ADDR 算法中得到的重復(fù)記錄要比DDR 算法得到的重復(fù)記錄高5%左右，這是因?yàn)樵诮-樹時(shí)使用了NSKSA 算法，使得簇內(nèi)更為緊湊，產(chǎn)生的比較次數(shù)明顯減少，最終使Map 工作機(jī)上的重復(fù)記錄減少近10%，而重復(fù)記錄的有效重復(fù)數(shù)據(jù)提高近5%。

5 結(jié)束語

通過文中實(shí)驗(yàn)可以看出，該文的NSKSA 對R-樹的建立有比DKSC 和TGS 更好的聚類效果，使得建立的R-樹在遍歷時(shí)，訪問的節(jié)點(diǎn)數(shù)偏少，且節(jié)點(diǎn)間的比較次數(shù)也隨之減少。而ADDR 算法有助于進(jìn)一步提高重復(fù)檢測的效率，提高重復(fù)檢測的質(zhì)量。這兩個(gè)算法對大數(shù)據(jù)低維數(shù)據(jù)的重復(fù)檢測有一定的參考價(jià)值。但在NSKSA 中，R-樹節(jié)點(diǎn)所能容納的最大條目數(shù)M對建立R-樹有一定的影響，而ADDR 中，距離閾值t對重復(fù)記錄的檢測也有很大的影響，這兩個(gè)參數(shù)的最優(yōu)值還有待進(jìn)一步研究。