大數(shù)據(jù)環(huán)境下高維數(shù)據(jù)的快速重復(fù)檢測方法

朱蔚恒　印　鑒　鄧玉輝　龍　舜　邱詩定

1(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院　廣州　510632)

2　　　(中山大學(xué)信息科學(xué)與技術(shù)學(xué)院　廣州　510006)

(tzhuwh@jnu.edu.cn)

?

大數(shù)據(jù)環(huán)境下高維數(shù)據(jù)的快速重復(fù)檢測方法

朱蔚恒1印鑒2鄧玉輝1龍舜1邱詩定1

1(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院廣州510632)

2(中山大學(xué)信息科學(xué)與技術(shù)學(xué)院廣州510006)

(tzhuwh@jnu.edu.cn)

Efficient Duplicate Detection Approach for High Dimensional Big Data

Zhu Weiheng1, Yin Jian2, Deng Yuhui1, Long Shun1, and Qiu Shiding1

1(CollegeofInformationScienceandTechnology,JinanUniversity,Guangzhou510632)

2(SchoolofInformationScienceandTechnology,SunYat-senUniversity,Guangzhou510006)

AbstractThe big data era has huge quantity of heterogeneous data from multiple sources be widely used in various domains. Data from multiple sources and of various structures make data duplication inevitable. In addition, such a large amount of data generates an increasing demand for efficient duplicate detection algorithms. Traditional approaches have difficulties in dealing with high dimensional data in big data scenarios. This paper analyses the deficiency of traditional SNM(sorted neighbour method) methods and proposes a novel approach based on clustering. An efficient indexing mechanism is first created with the help of R-tree, which is a variant of B-tree for multi-dimensional space. The proposed algorithm reduces the comparisons needed by taking advantage of the characteristics of clusters and outperforms existing duplicate detection approaches such as SNM, DCS, and DCS++. Furthermore, based on the apriori property of duplicate detection, we develop a new algorithm which can generate the duplicate candidates in parallel manner of the projection of original dataset and then use them to reduce search space of high-dimensional data. Experimental results show that this parallel approach works efficiently when high-dimensional data is encountered. This significant performance improvement suggests that it is ideal for duplicate detection for high dimensional big data.

Key wordsbig data; high dimension data; data mining; data preprocessing; duplicate detection

摘要大數(shù)據(jù)時代多源、異構(gòu)、海量的數(shù)據(jù)正逐漸成為各種應(yīng)用的主流.多源異構(gòu)不可避免地會使數(shù)據(jù)出現(xiàn)重復(fù)，同時龐大的數(shù)據(jù)量對重復(fù)檢測的效率提出了極高的要求，傳統(tǒng)技術(shù)在大數(shù)據(jù)環(huán)境下并不能很好地對高維數(shù)據(jù)進行重復(fù)檢測，就此問題展開研究，分析了傳統(tǒng)SNM類方法的不足，將重復(fù)問題概化為一類特殊的聚類問題，利用R-樹建立了高效的索引，利用聚類簇的特性減少了在R-樹葉子中比較的次數(shù)，利用重復(fù)檢測的Apriori性質(zhì)實現(xiàn)了對高維數(shù)據(jù)集并行處理.實驗結(jié)果表明，提出的算法能有效地提高高維數(shù)據(jù)的重復(fù)檢測效率.

關(guān)鍵詞大數(shù)據(jù);高維數(shù)據(jù);數(shù)據(jù)挖掘;數(shù)據(jù)預(yù)處理;重復(fù)檢測

重復(fù)檢測(duplicate detection)是指從多源數(shù)據(jù)集中檢查表達(dá)相同實體的重復(fù)記錄.現(xiàn)實生活中許多應(yīng)用需要整合來自不同數(shù)據(jù)源的數(shù)據(jù).在這些實際任務(wù)中，經(jīng)常會碰到這樣的問題：同一個實體在不同數(shù)據(jù)源中有不同的表達(dá)，這些表達(dá)之間存在一定的差異，不能直接一一對應(yīng)，這種現(xiàn)象稱之為重復(fù)記錄.導(dǎo)致重復(fù)記錄的原因很多，如多重數(shù)據(jù)結(jié)構(gòu)、名稱拼寫錯誤、不通用的別名、不同的縮寫、方言表達(dá)、不完全匹配的記錄以及數(shù)據(jù)由高精度系統(tǒng)導(dǎo)入低精度系統(tǒng)(從 64 b系統(tǒng)導(dǎo)入 32 b系統(tǒng))等.這些重復(fù)記錄為統(tǒng)計、數(shù)據(jù)分析、數(shù)據(jù)挖掘等任務(wù)造成了很大的困擾，并直接影響最終的結(jié)果.因此，在許多需要處理來自多個數(shù)據(jù)源數(shù)據(jù)的實際應(yīng)用中，如基于多個電商平臺社交網(wǎng)站數(shù)據(jù)的市場分析、網(wǎng)絡(luò)營銷等，必須要對這些來自多數(shù)據(jù)源的數(shù)據(jù)進行重復(fù)檢測.

隨著以博客、社交網(wǎng)絡(luò)、基于位置的服務(wù)為代表的新型信息發(fā)布方式的不斷涌現(xiàn)，以及云計算、物聯(lián)網(wǎng)等技術(shù)的興起，數(shù)據(jù)正以前所未有的速度在不斷地增長和累積，大數(shù)據(jù)時代已經(jīng)來到[1].對大數(shù)據(jù)時代的大部分應(yīng)用而言，收集數(shù)據(jù)已不再是發(fā)展的瓶頸，而如何保證收集到數(shù)據(jù)的一致性[2]正日漸成為必須面對的問題.

重復(fù)檢測問題是一個被廣泛研究的問題[3-4]，在統(tǒng)計學(xué)、人工智能、數(shù)據(jù)庫等領(lǐng)域均對其進行了深入的研究，針對重復(fù)檢測的各個方面提出了不少有效的方法.然而，隨著大數(shù)據(jù)時代來臨，傳統(tǒng)問題重新面臨新的挑戰(zhàn).大數(shù)據(jù)時代數(shù)據(jù)來源廣、結(jié)構(gòu)復(fù)雜、數(shù)量巨大[1]，多源數(shù)據(jù)必然導(dǎo)致重復(fù)記錄的產(chǎn)生；對大量非結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)處理也會導(dǎo)致重復(fù)記錄的增加；龐大的數(shù)據(jù)量則對重復(fù)檢測方法的效率提出了更嚴(yán)格的要求.因此大數(shù)據(jù)環(huán)境下的高維數(shù)據(jù)集對傳統(tǒng)的數(shù)據(jù)預(yù)處理，數(shù)據(jù)分析技術(shù)提出更高的要求.

當(dāng)前對重復(fù)檢測的研究主要基于如下思想：分塊(blocking)以及窗口(windowing)，其代表性方法是Hernandez和Stolfo[5]提出的SNM方法及其改進.在實踐過程中我們發(fā)現(xiàn)，當(dāng)進行相似性判別的維度較多時，此類方法的效率仍不理想.為了更有效地對高維數(shù)據(jù)進行重復(fù)檢測，本文借鑒了不確定性的概念，將重復(fù)問題的實質(zhì)視作對象不確定性的現(xiàn)實體現(xiàn)，由此可將重復(fù)檢測問題看成一類特殊的聚類問題，并據(jù)此提出了一種基于空間聚類的高效處理重復(fù)檢測問題的算法DDR(duplicate detection using R-tree)和一種利用DDR以及高維數(shù)據(jù)重復(fù)檢測的Apriori性質(zhì)進行剪枝的高維大數(shù)據(jù)重復(fù)檢測方法.實驗結(jié)果表明，在處理高維數(shù)據(jù)時與傳統(tǒng)的重復(fù)檢測算法相比DDR能節(jié)省大量的對比次數(shù)，而本文提出的重復(fù)檢測框架也能有效地處理大數(shù)據(jù)環(huán)境下的高維數(shù)據(jù)重復(fù)檢測問題.

1相關(guān)工作

1.1重復(fù)檢測研究現(xiàn)狀

重復(fù)檢測是數(shù)據(jù)預(yù)處理的一個重要問題，在不同場景下也被稱為實體匹配(entity matching)、對象匹配(object matching)、混合凈化(mergepurge)、記錄鏈接(record linkage)或記錄一致(record reconciliation).重復(fù)檢測問題在數(shù)據(jù)統(tǒng)計、數(shù)據(jù)分析和數(shù)據(jù)挖掘等領(lǐng)域有很多的實際應(yīng)用[3-4].

例如某從事郵件營銷的公司利用爬蟲從2個電商平臺采集到一些特定商品的用戶購買記錄，經(jīng)初步清洗后得到如表1所示數(shù)據(jù)集.從表1可以看出，雖然2個用戶信息并不完全一致，但它們非常類似，從郵件營銷的角度，將這2個用戶看作同一個人寄送促銷廣告是很合理的.類似這樣的記錄對在數(shù)據(jù)集中有很多，因此公司往往希望在寄送促銷廣告之前能通過ID、生日、性別、收貨地址等屬性把他們找出來，這就是一個典型的重復(fù)檢測問題.

Table 1　Information Collected from Various E-Bussiness Companies

一般地，對來自不同數(shù)據(jù)源的數(shù)據(jù)進行重復(fù)檢測的流程如圖1所示[5].來自2個不同數(shù)據(jù)源的數(shù)據(jù)在經(jīng)過清洗和標(biāo)準(zhǔn)化之后，利用高效的索引對數(shù)據(jù)進行初步的歸納整理，然后從若干角度對每一對記錄進行比較并得到一個相似度向量度量，最后利用一個有監(jiān)督的分類器判斷這一對記錄是否為重復(fù)記錄.

Fig. 1　Duplicate detection for two data sources.圖1　對2個數(shù)據(jù)源數(shù)據(jù)進行重復(fù)檢測的流程

從圖1中的流程可以看出，決定重復(fù)檢測效率的關(guān)鍵是如何利用索引來減小記錄對的比較次數(shù).近年來，相關(guān)領(lǐng)域的主要工作有：韓京宇等人[6]對大數(shù)據(jù)量的相似記錄檢測問題展開了研究，針對字符串的q-gram距離提出一種將數(shù)據(jù)映射為q-gram空間中的點，然后使用層次聚類定位潛在重復(fù)記錄來解決重復(fù)檢測問題.但此方法針對字符串的q-gram距離，有一定的局限性.龐雄文等人[7]根據(jù)概念依賴圖計算表的關(guān)鍵屬性并據(jù)此將數(shù)據(jù)劃分為記錄集進行重復(fù)記錄檢測，采取一種合并已匹配記錄的方法來減少比較的次數(shù).但他們的工作沒有考慮到重復(fù)往往缺乏傳遞性，即記錄A,B重復(fù)，記錄B,C重復(fù)，并不意味著記錄A,C重復(fù)，因此此方法在實際運用中效果往往不夠理想.Fan等人[8]研究了待重復(fù)檢測數(shù)據(jù)集中記錄屬性，提出了與聯(lián)系相關(guān)屬性間的一種新依賴關(guān)系，并提出了一種尋找這些依賴及關(guān)聯(lián)候選鍵(relative candidate keys)的算法.此方法研究重點在于如何找到關(guān)鍵屬性，對如何在大數(shù)據(jù)環(huán)境下高效地進行重復(fù)檢測未有涉及.當(dāng)前普遍采用的方法為Hernandez和Stolfo提出的SNM方法及一系列基于SNM的方法[3,9-10].

1.2SNM方法及其改進

SNM方法的核心思想是利用一個排序函數(shù)對整個數(shù)據(jù)集中的數(shù)據(jù)進行排序，將潛在可能重復(fù)的記錄排在一起(分塊).然后利用窗口技術(shù)對數(shù)據(jù)對比的空間進一步壓縮.傳統(tǒng)的SNM方法分為3個步驟：

1) 鍵值指派.在此階段，為每一條記錄指派一個用于排序的鍵值.通常，這個鍵值是根據(jù)屬性值的某些部分生成的.

2) 排序.所有記錄按鍵值進行排序.

3) 窗口化.一個固定長度的窗口在已經(jīng)排序的數(shù)據(jù)上滑動.窗口內(nèi)的每一對數(shù)據(jù)都兩兩進行比較，然后標(biāo)識出重復(fù)數(shù)據(jù).

現(xiàn)實世界中重復(fù)記錄數(shù)目是隨機的，可能會有很多條重復(fù)記錄，也可能僅有1，2條重復(fù)，而使用一個固定大小的窗口限定比較范圍，顯然并不合適.Yan等人[9]基于一個局部的距離單調(diào)假設(shè)提出了動態(tài)窗口的方法.Draisbach等人[10]則基于重復(fù)記錄密集的地方可能存在更多的重復(fù)記錄這一假設(shè)提出在重復(fù)檢測過程中根據(jù)窗口內(nèi)檢測到的重復(fù)記錄數(shù)來動態(tài)調(diào)整窗口大小，以提高比較效率的DCS方法和DCS++方法.與SNM相比，DCS及DCS++的效率有顯著提高.

1.3重復(fù)檢測問題的不足以及本文的工作

仔細(xì)分析SNM類方法，可以發(fā)現(xiàn)如下不足：SNM類算法基于鍵值指派，排序函數(shù)選擇對結(jié)果影響明顯，好的排序函數(shù)能有效降低比較的次數(shù).然而在實際應(yīng)用中，找到合適的排序函數(shù)并不是一件容易的工作；而且排序函數(shù)的實質(zhì)是將高維數(shù)據(jù)映射到一維空間上，在映射的過程中不可避免地會導(dǎo)致部分信息的損失，從而使得排序結(jié)果與實際存在一定的偏差，數(shù)據(jù)的維度越高，信息損失越大，因此SNM類算法并不能很好地伸縮.此外，重復(fù)檢測采取一種窗口內(nèi)所有記錄逐對比較的策略，在對比的過程中并沒有或者僅僅是基于假設(shè)有限利用之前判斷的結(jié)果，這樣做大大降低了重復(fù)檢測的效率.

為解決SNM類算法在處理高維數(shù)據(jù)時上述的不足，本文提出了一種基于聚類思想的高維數(shù)據(jù)重復(fù)檢測算法，保留高維數(shù)據(jù)信息并建立索引用于重復(fù)檢測，在檢測過程中有效地利用了之前比較的結(jié)果降低比較次數(shù).由圖1的重復(fù)檢測框架可知，對象之間是否重復(fù)是根據(jù)相似度向量來判斷的，因此相似度的定義對最終算法的效率有較大的影響，為使討論更加清晰，本文不失一般性采用了歐氏距離作為相似度判別標(biāo)準(zhǔn)，利用記錄間距離是否達(dá)到一個閾值t來判斷記錄對是否重復(fù).

2基于空間鄰居的重復(fù)檢測

2.1不確定性與重復(fù)檢測

現(xiàn)實生活中應(yīng)用能獲得的數(shù)據(jù)與真實數(shù)據(jù)之間往往存在一定的差異，測量儀器的誤差、人為疏忽而導(dǎo)致的輸入錯誤、基于隱私保護考慮而引入的擾亂等原因都會造成真實數(shù)據(jù)與觀察值之間的差異，這種差異被稱為不確定性.數(shù)據(jù)的不確定性可分為2類：存在級層次的不確定性(existential level uncertainty)和屬性層次的不確定性(attribute level uncertainty).其中后者是一個研究得較多的不確定模型，它假設(shè)對象某屬性的實際數(shù)據(jù)分布于一個封閉的不確定區(qū)間中，數(shù)據(jù)的出現(xiàn)服從一個該區(qū)間內(nèi)的概率密度函數(shù).

本文認(rèn)為，不同數(shù)據(jù)源之間會出現(xiàn)重復(fù)記錄的現(xiàn)象可視作不確定性在現(xiàn)實世界中的體現(xiàn).由于存在不確定性的影響，同一客觀對象在每個數(shù)據(jù)源中觀察到的屬性值會存在一定差異，這就導(dǎo)致了重復(fù)記錄的產(chǎn)生.因此，對數(shù)據(jù)集進行重復(fù)檢測的目的可視為希望通過重復(fù)檢測找到一個更接近現(xiàn)實世界的數(shù)據(jù)集.

2.2重復(fù)檢測與聚類

重復(fù)檢測是在一個大型數(shù)據(jù)集中尋找類似記錄的過程，這與數(shù)據(jù)挖掘中的聚類分析十分相似.聚類分析是一個將物理或抽象對象集分成相似對象類的過程，簇是相似數(shù)據(jù)對象的集合，聚類分析要求同一個簇中的對象彼此相似而與其他簇中的對象相異.如果將同一個客觀對象的重復(fù)記錄看成一個簇，那么重復(fù)檢測問題可以看成為一個特殊的聚類問題.

但在一般意義上，重復(fù)檢測問題并不僅僅是一個聚類問題，它是一個比一般聚類要求更嚴(yán)格的數(shù)據(jù)聚集問題.比較重復(fù)檢測過程和傳統(tǒng)的聚類算法可以發(fā)現(xiàn)：前者關(guān)注的重點是具體的記錄對，屬于同一個客觀對象的重復(fù)記錄兩兩之間的距離差異必須小于一個特定的閾值；而后者關(guān)注的重點是簇.一般地，在尋找簇的過程中并不會特定關(guān)注簇中每一對對象是否相似，常用的聚類算法如K-均值和BRICH等，并不保證簇內(nèi)每一對對象是相似的，基于密度的聚類方法僅要求簇內(nèi)的密度達(dá)到一個閾值就可以，若簇足夠大，那么處于同一個簇內(nèi)邊界2端的對象之間的差別是非常大的.可見，傳統(tǒng)的聚類方法并不能直接應(yīng)用于解決重復(fù)檢測問題.

然而，對比聚類分析及重復(fù)檢測的結(jié)果可以發(fā)現(xiàn)：雖然使用聚類算法發(fā)現(xiàn)的同一簇內(nèi)的對象不一定重復(fù)，但屬于同一個客觀對象的重復(fù)記錄必定在一個簇中.因此可以利用聚類分析來有效提高重復(fù)檢測的效率.

2.3利用R-樹進行高維索引

R-樹是B-樹在多維空間的擴展，是目前應(yīng)用最為廣泛的一種空間索引結(jié)構(gòu)，它按空間存儲數(shù)據(jù)，能有效提高高維數(shù)據(jù)的聚類效率.R-樹中有2種結(jié)點：葉子結(jié)點和中間結(jié)點、葉子結(jié)點記錄數(shù)據(jù)；中間結(jié)點記錄其子樹的索引空間.當(dāng)需要查找某一空間點的近鄰時，可以利用中間結(jié)點將搜索范圍限制在一個比較少的范圍.一棵M階的R-樹，其結(jié)點結(jié)構(gòu)可以描述如下：

葉子結(jié)點:

(Count,Level,〈OI1,MBR1〉,〈OI2,MBR2〉,…,〈OIM,MBRM〉),

中間結(jié)點:

(Count,Level, 〈CP1,MBR1〉,〈CP2,MBR2〉,…,〈CPM,MBRM〉),

其中，Count為結(jié)點的索引項或數(shù)據(jù)項的個數(shù)，Level表示結(jié)點類型，〈OIi,MBRi〉稱為數(shù)據(jù)項，OIi是第i個空間目標(biāo)的標(biāo)識，MBRi為該目標(biāo)在k維空間中的最小包圍矩形(簡稱為數(shù)據(jù)矩形)；〈CPi,MBRi〉稱為索引項，CPi是指向子樹根結(jié)點的指針，MBRi代表其子樹索引空間，為包圍其子樹根結(jié)點中所有目錄矩形或數(shù)據(jù)矩形的最小包圍矩形(簡稱為目錄矩形).

3高維數(shù)據(jù)的快速重復(fù)檢測算法

3.1本文使用的重復(fù)檢測處理框架

影響重復(fù)檢測效率的主要原因在于索引的效率以及記錄對的比較次數(shù)，為使討論更加清晰，在本文討論中簡化了相似度向量分類步驟，同時本文的討論中不對數(shù)據(jù)的具體類型、分布和依賴關(guān)系做約束，不失一般性，假設(shè)待處理數(shù)據(jù)集為n維向量集，利用2條記錄間的歐氏距離是否達(dá)到一個預(yù)定義的閾值t來判斷記錄對是否重復(fù).本文將重復(fù)檢測處理框架簡化如圖2所示的流程.

在圖2所示的重復(fù)檢測過程中，對來自不同數(shù)據(jù)源的數(shù)據(jù)清洗和標(biāo)準(zhǔn)化處理之后，本文提出的DDR算法利用R-樹作為空間索引，然后經(jīng)過一次遍歷將可能的記錄對進行比較，最后輸出結(jié)果.

Fig. 2　Duplicate detection framework proposed.圖2　本文算法所采用的重復(fù)檢測框架

算法1. DDR算法.

輸入：待處理數(shù)據(jù)集;

輸出: 重復(fù)記錄集.

DDR(Dataset){

①Build_R_tree(R,Dataset);*以R為根結(jié)點，建立R-樹*

②Traversal(R,t,0);*以t為閾值遍歷R-樹，輸出重復(fù)記錄*

③ }

3.2DDR中的遍歷

重復(fù)檢測需要對所有潛在可能重復(fù)的記錄對進行比較，一個簡單的思想是可以將之前搜索的結(jié)果作為后續(xù)搜索的啟發(fā).在DDR的遍歷中記錄了數(shù)據(jù)查找及對比過程中的相關(guān)信息，每次搜索都利用這些信息在已經(jīng)進行過重復(fù)檢測的數(shù)據(jù)中進行，這樣做能有效地減少搜索空間、提高搜索效率.

為適應(yīng)這種搜索策略，對R-樹進行了如下的修改：每層結(jié)點增加2個屬性Visited和Contain.Visited代表已經(jīng)訪問過該結(jié)點.該屬性在R-樹初始化時記錄為0，若該結(jié)點為葉子結(jié)點，那么在葉子結(jié)點的所有數(shù)據(jù)都被處理后該屬性記為1，若該結(jié)點為中間結(jié)點，那么當(dāng)其被遍歷時記為1.屬性Contain表示結(jié)點中是否可能包含與當(dāng)前正在進行重復(fù)檢測的葉子結(jié)點中的數(shù)據(jù)重復(fù)的記錄.當(dāng)開始訪問一個新的葉子結(jié)點時，先利用該結(jié)點的目錄矩形對R-樹已經(jīng)遍歷過的部分進行一次遍歷，在遍歷過程中利用距離閾值對各個結(jié)點的屬性Contain進行標(biāo)注，如果兩者的目錄矩形相交或距離小于閾值t，那么意味著該結(jié)點中可能包含重復(fù)記錄.

DDR中使用一個遞歸的遍歷算法，其基本思想如下：如果訪問到一個葉子結(jié)點，那么依次將該結(jié)點中的數(shù)據(jù)項與之前已經(jīng)進行過重復(fù)檢測的數(shù)據(jù)項進行對比，在對比的過程中利用R-樹的結(jié)構(gòu)可有效地壓縮搜索范圍，然后將該數(shù)據(jù)項與葉子結(jié)點內(nèi)部的數(shù)據(jù)項對比，在對比的過程中不斷優(yōu)化葉子結(jié)點數(shù)據(jù)項的排列.

算法2. DDR中的遍歷算法.

Traversal(R,t,MBR){

① ifR.Level=0 then {*若R是葉子結(jié)點遍歷一次R-樹，利用目錄矩形標(biāo)識已訪問過的結(jié)點中可能包含重復(fù)記錄的結(jié)點*

②Check_Visited(Root,MBR,t);

③ fori=1 toR.Count{*對葉子結(jié)點中每個數(shù)據(jù)項D，搜索所有已訪問過且與D潛在距離t相交的葉子并保存在集合data中*

④D=R.MBRi;

⑤data=R_Search(Root,D,t);

⑥ CompareDwith data in every leaf indataand output the duplication records;

⑦Compare_inside_leaf(R,i,t);*在葉子結(jié)點內(nèi)部進行逐一比較，并為葉子結(jié)點內(nèi)部數(shù)據(jù)建立一個便于查找的序*

⑧ } end for

⑨R.Visted=1;

3.3在葉子結(jié)點內(nèi)部進行比較

R-樹中的數(shù)據(jù)項皆保存于葉子結(jié)點內(nèi)，由于R-樹結(jié)構(gòu)的特點，每個葉子結(jié)點內(nèi)的數(shù)據(jù)項之間位置相近是潛在重復(fù)的.因此，有必要對葉子結(jié)點內(nèi)的數(shù)據(jù)項進行兩兩比較.與R-樹搜索策略類似，DDR在葉子結(jié)點內(nèi)部比較過程中記錄部分信息以提高后續(xù)的對比效率.

由2.3節(jié)中討論可知，本文將重復(fù)檢測看成一個特殊的聚類問題，相同實體對象的重復(fù)記錄將聚集成一個簇，簇中記錄兩兩間的距離小于閾值t，而簇外記錄至少與簇中一個記錄的距離大于t.以圖3為例，重復(fù)的判定閾值為t，點a屬于一個簇A，顯然a與簇內(nèi)任一點皆重復(fù)；點b，c與a的距離大于2t，顯然，b，c與A中任一點皆不可能是重復(fù)的；而點e與a的距離大于t小于2t，它與簇A中其他點可能重復(fù)也可能不重復(fù).直觀地可得到如下的性質(zhì)：

Fig. 3　Relation between points in the cluster and out of the cluster.圖3　簇外點與簇內(nèi)點的關(guān)系

性質(zhì)1. 如果一個記錄D與一個簇C中任一記錄距離大于2t，那么D與簇中任何記錄都不可能組成重復(fù)記錄對.

根據(jù)此性質(zhì)，DDR算法可以盡快判斷哪些點肯定不在同一簇中，從而避免了相關(guān)的對比.該算法對葉子結(jié)點內(nèi)的重復(fù)檢測過程如下：為R-樹葉子結(jié)點中每個數(shù)據(jù)項增加一個屬性S，它代表了滑動的步長.如果一個數(shù)據(jù)項的S=n，即意味著它后續(xù)的n個數(shù)據(jù)項與該數(shù)據(jù)項處于同一簇中，當(dāng)葉子結(jié)點內(nèi)部進行比較時，若記錄D與一個數(shù)據(jù)項OP的距離大于2t，那么意味著D與OP及其之后n個數(shù)據(jù)項都不可能是重復(fù)記錄.具體算法如算法3所示.

算法3. DDR中葉子結(jié)點內(nèi)部比較算法.

Compare_inside_leaf(R,i,t) {

①D=R.MBRi;

②Is_belong_to_a_cluster=0;

③ forj=1 toi-1 {

④dist=distance(D,R.MBRj);

⑤ Choose casedist*根據(jù)數(shù)據(jù)項之間的距離分別做判斷*

⑥ casedist≤t*在閾值t之內(nèi)的，輸出重復(fù)記錄對，同時在簇內(nèi)進行掃描，判斷數(shù)據(jù)項是否屬于該簇并進行對應(yīng)處理*

⑦Output(D,R.MBRj);

⑧Is_in_this_cluster=1;

⑨ fork=1 toR.Sj{*對簇內(nèi)每對數(shù)據(jù)項判斷*

⑩ ifdistance(D,R.MBRj+k)>tthen

{Is_in_this_cluster=0;}

else {Output(D,R.MBRj+k);} end if

t{Output(D,R.MBRj);} end if

下面以圖4所示葉子結(jié)點為例，討論DDR算法葉子結(jié)點內(nèi)重復(fù)檢測的過程.該葉子結(jié)點的初始狀態(tài)如圖4中Step1所示，結(jié)點所包含的前6個項的值分別是5,3,10,11,4,2.給定閾值t=2，在開始檢測之前，所有項的步長記為0.

Step1. 從項2開始，值3與值5間距離為t，它們屬于一個簇，輸出重復(fù)記錄對(3，5),同時項1的步長改為1，意味著它與其后的項在一個簇中.

Step2. 從項3開始，值10與值5距離大于2t，而項1步長為1，因此無需與項2進行比較.

Fig. 4　An example of traveling in the leaf node of R-tree.圖4　一個R-樹葉子結(jié)點遍歷的例子

Step3. 從項4開始，值11與值5距離大于2t，項1步長為1，因此無需與項2比較，項4直接與項3比較，值11與值10距離小于t，它們屬于一個簇，輸出重復(fù)記錄(11，10)，同時項3步長改為1.

Step4. 從項5開始，值4與值5距離小于t，輸出重復(fù)記錄對(4，5)，因為項1步長為1，所以需要繼續(xù)與項2比較.值4與值3距離小于t，輸出重復(fù)記錄對(4，3)，可以發(fā)現(xiàn)此3項兩兩互為重復(fù)記錄，因此它們形成一個簇，算法進行如下操作：將項5的位置移至第3，原來的項3、項4后移一位變成項4、項5，同時將項1，項2步長各加1.然后繼續(xù)比較.項3的值4與項4的值10之間距離大于2t，項4步長為1，因此項3與項5無需比較.

Step5. 從項6開始，值2與值5距離大于t小于2t，因此不能利用步長減少比較次數(shù)，項6與后續(xù)項2、項3進行比較，發(fā)現(xiàn)都是重復(fù)項，輸出(2,3),(2,4),但此2項皆與項1處于同一簇內(nèi)，因此不需要對其進行進一步處理.繼續(xù)項6與項4的比較，值2與值10距離大于2t，因此不必與項5比較.

3.4DDR算法分析

從3.1節(jié)討論中可知，DDR算法可以分為相對獨立的2部分：構(gòu)建R-樹以及利用R-樹查找重復(fù)記錄.下面分別對其效率進行討論：

傳統(tǒng)的R-樹的構(gòu)建方法稱為OBO(one-by-one) 方法，即從空樹開始，利用插入算法逐個插入記錄，直至生成整個R-樹.由于插入過程中需要保持R-樹的動態(tài)平衡，所以建樹代價較高.當(dāng)需要建立索引的數(shù)據(jù)已知且相對靜態(tài)時，可以采取批量加載的方法得到結(jié)構(gòu)優(yōu)化的R-樹，這樣能更快建立R-樹并保證其在查詢時能有更好的表現(xiàn).一般地，重復(fù)檢測問題是對已知數(shù)據(jù)進行批量檢測，因此，本文實驗中選取了一個時間復(fù)雜度為O(Snlogn)的批量加載方法TGS建立R-樹[11]，其中S是一個與處理數(shù)據(jù)集相關(guān)的參數(shù).

利用R-樹查找重復(fù)記錄的時間消耗主要在對記錄進行對比時的距離計算上，其比較次數(shù)與預(yù)定義的閾值有關(guān)，最壞情況下需要做n(n-1)2次比較.與建樹階段相比，查找重復(fù)記錄階段不僅有更高的時間復(fù)雜度，而且每一次比較也需要更多的單位時間.因此，整個算法的時間消耗主要與記錄對比次數(shù)相關(guān)，這與SNM，DCS，DCS++等算法是一致的.本文的第4節(jié)將通過實驗數(shù)據(jù)詳細(xì)比較DDR建樹和搜索2階段的效率以及DDR與SNM，DCS，DCS++等算法的效率.

3.5利用Apriori性并行地高速處理高維數(shù)據(jù)

利用R-樹索引的DDR算法能有效處理一定維度范圍內(nèi)的高維數(shù)據(jù)，然而高維數(shù)據(jù)本質(zhì)是稀疏的，當(dāng)維度數(shù)目足夠大時，必然會面對維災(zāi)難的問題，R-樹基于空間索引的優(yōu)勢將不再有效，其索引代價也不再可忽略.為解決這種超高維度數(shù)據(jù)的重復(fù)檢測問題，我們對此問題進行了深入的分析，發(fā)現(xiàn)高維數(shù)據(jù)在重復(fù)檢測中具有如下性質(zhì).

性質(zhì)2. 如果一對數(shù)據(jù)在高維上是重復(fù)的，那么它們在低維空間上的投影一定也是重復(fù)的(apriori性).

顯然，若記錄在各維度投影的數(shù)值不變，記錄間距離隨維度增加單調(diào)遞增.因此，若以t為閾值進行重復(fù)檢測，由此性質(zhì)可知：若一對高維記錄在某一低維空間上的投影不重復(fù)(距離大于閾值t)，那么它們在高維空間中也不可能是重復(fù)的(距離小于等于閾值t).為此，本文提出了一種并行地利用數(shù)據(jù)集在低維空間中的投影對其進行過濾，生成候選集來縮減搜索空間的方法.具體思想如下：對數(shù)據(jù)集在若干低維組合的投影進行重復(fù)檢測，利用Apriori性剔除大部分不可能重復(fù)的記錄對，得到潛在可能的重復(fù)記錄集，然后在高維下對這些潛在重復(fù)的記錄對進行檢測.

由于Apriori性質(zhì)非常適合于并行處理，因此本文采用了一個Map-Reduce的方法來高效地實現(xiàn)此過程，其中Map-Reduce函數(shù)如下：

Map函數(shù).每一個具體的Map函數(shù)實質(zhì)上就是一個利用閾值t對低維子空間中的數(shù)據(jù)投影集進行重復(fù)檢測DDR算法，其輸出為每個數(shù)據(jù)塊上潛在可能的重復(fù)記錄對.Map函數(shù)將原數(shù)據(jù)集在低維投影上距離小于閾值t的記錄對組合編碼為鍵，值記為1，并輸出鍵-值對作為Reduce函數(shù)的輸入.

Reduce函數(shù).對Map函數(shù)輸出的結(jié)果中具有相同鍵值的鍵-值對進行計數(shù)，將計數(shù)值等于n(Map工作機數(shù)目)的鍵值輸出，它所對應(yīng)的記錄對就是潛在重復(fù)的記錄對.

3.6大數(shù)據(jù)環(huán)境下高維數(shù)據(jù)的重復(fù)檢測

利用Apriori性質(zhì)的Map-Reduce方法能有效減少高維數(shù)據(jù)對計算的影響，但值得注意的是，在每一臺Map工作機上運行的是一個獨立的DDR算法.從3.4節(jié)分析中可以看到，最壞情況下DDR要進行n(n-1)2次比較，在大數(shù)據(jù)環(huán)境下這顯然是不可接受的.

深入分析SNM類算法在重復(fù)檢測中的作用可以發(fā)現(xiàn)，雖然使用散列排序函數(shù)會造成大量信息損失，不能為后續(xù)計算提供便利，但散列排序函數(shù)將大數(shù)據(jù)集分割為若干個小數(shù)據(jù)集縮減比較次數(shù)的方法能有效地減少數(shù)據(jù)集規(guī)模增長所帶來的計算量.為此，本文采用了如圖5所示過程對大數(shù)據(jù)環(huán)境下的高維數(shù)據(jù)進行重復(fù)檢測.

Fig. 5　Apriori property based duplication detection for high dimensional data.圖5　利用高維數(shù)據(jù)的Apriori性質(zhì)進行重復(fù)檢測

首先根據(jù)具體的距離定義利用散列函數(shù)將數(shù)據(jù)分割為若干相容的子集.每個子集分為2部分，核心區(qū)域以及擴展區(qū)域.全體核心區(qū)域的并集等于整個數(shù)據(jù)集，而且與核心區(qū)域中數(shù)據(jù)的潛在重復(fù)記錄都落在核心區(qū)域及其對應(yīng)的擴展區(qū)域中.圖6所示1維數(shù)據(jù)集重復(fù)記錄距離小于閾值l，實線方框所示為核心區(qū)域，虛線所表示為對應(yīng)擴展區(qū)域，顯然核心區(qū)域記錄所對應(yīng)的重復(fù)記錄必包含在其擴展后的區(qū)間內(nèi).

Fig. 6　Kernel area and expansion area.圖6　核心區(qū)域與擴展區(qū)域

雖然沒有一個簡單的方法預(yù)測數(shù)據(jù)在哪些子空間上具有較低的重復(fù)度，但是一般而言，數(shù)據(jù)在某維上投影的方差越大，意味著數(shù)據(jù)在該維上的分布越分散.因此，可以利用抽樣技術(shù)計算其在各維上的方差，然后將數(shù)據(jù)集分成n塊(n為Map工作機的數(shù)目)，每一塊中記錄了整個數(shù)據(jù)集在方差最大的n個m維空間上的投影(m為DDR算法最佳的收斂空間)，利用數(shù)據(jù)在這些維度上的投影和一個Map-Reduce過程對數(shù)據(jù)集進行初步處理，得到潛在的重復(fù)記錄對.最后根據(jù)定義對這些潛在重復(fù)記錄對進行判斷并輸出最終結(jié)果.

4實驗及結(jié)果分析

4.1實驗方法與實驗數(shù)據(jù)集

本文的實驗分為2部分：1)比較了DDR算法的有效性及其與SNM，DSC，DSC++算法在處理高維數(shù)據(jù)時效率的差別;2)通過實驗檢驗了本文提出的Map-Reduce過程對高維數(shù)據(jù)處理的效率和有效性.

本文所有實驗使用的代碼均為Java實現(xiàn)，同時為了使比較的數(shù)據(jù)集更具有可信性，本文選用了參考文獻[10]中所使用的Febrl數(shù)據(jù)集的數(shù)據(jù)生成器[12]人工生成了本文實驗中所使用的數(shù)據(jù).

4.2DDR算法實驗結(jié)果及分析

Febrl數(shù)據(jù)集中每條數(shù)據(jù)包含的信息為人的姓名、年齡、國籍、住址、電話…等18項信息.為更全面衡量算法的效率和伸縮性，本文對Febrl數(shù)據(jù)集中的數(shù)據(jù)進行標(biāo)準(zhǔn)化后，分別抽取其中2維、4維、8維和10維信息生成了100萬條數(shù)據(jù)和1萬條數(shù)據(jù)2種不同大小的數(shù)據(jù)集進行重復(fù)檢測.

每個數(shù)據(jù)集中的數(shù)據(jù)由2部分組成，其中50%為原始數(shù)據(jù)，另外50%為根據(jù)原始數(shù)據(jù)做改動的重復(fù)記錄.重復(fù)記錄的生成規(guī)則如下：對原始記錄每一維的數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，每條原始數(shù)據(jù)有0～9條對應(yīng)的重復(fù)數(shù)據(jù)，重復(fù)數(shù)量服從Zipf分布；每條重復(fù)數(shù)據(jù)有0～5處改動.

Fig. 7　Comparison of time for different DDR phases.圖7　DDR算法各階段效率比較

首先比較DDR算法中構(gòu)造R-樹階段以及利用R-樹進行搜索階段時間的消耗.圖7顯示了在不同維度的數(shù)據(jù)集中使用DDR算法進行重復(fù)檢測時建樹階段和搜索達(dá)到一定召回率所需的時間.在此實驗中，我們對4個不同維度各100萬條數(shù)據(jù)分別進行建樹和搜索.從圖7可以看出，要達(dá)到95%的召回率，針對4維、8維和10維3個數(shù)據(jù)集進行重復(fù)檢測所需時間與建樹時間接近，但它們建樹和搜索時間之和遠(yuǎn)小于2維數(shù)據(jù)集搜索時間所需，這是因為利用R-樹能有效地減少候選集，其帶來的效益提高遠(yuǎn)大于建樹所消耗的時間.從圖7還可以看出，要達(dá)到100%的召回率，4種不同維度數(shù)據(jù)所需搜索時間均遠(yuǎn)超其建樹時間.事實上，在我們的實驗中，當(dāng)召回率足夠大時，DDR算法中構(gòu)造R-樹階段所需時間消耗基本可以忽略.

重復(fù)檢測算法的時間消耗主要用于對比記錄，因此本文通過不斷調(diào)整匹配閾值的方法來分別檢測4種方法達(dá)到一定的召回率所需要的比較次數(shù).考慮到SNM，DCS，DCS++算法在處理大批量數(shù)據(jù)時表現(xiàn)不佳，在本次實驗中分別對2維、4維、8維和10維的數(shù)據(jù)集使用了1萬條記錄進行測試.表2顯示了DDR算法與SNM，DCS，DCS++算法比較的部分結(jié)果，圖8則顯示了4種算法在不同維度、不同召回率之下所需對比次數(shù)的曲線，從實驗結(jié)果可以看出，雖然4種算法在不同維度的數(shù)據(jù)集中的表現(xiàn)有所差別，但一般地，達(dá)到同樣的召回率DDR所需的比較次數(shù)少于SNM，DCS，DCS++算法.

Table 2Partial Results of Number of Comparison on 10-D Dataset

表2　10維數(shù)據(jù)集中部分比較次數(shù)

觀察實驗結(jié)果可以發(fā)現(xiàn)，當(dāng)召回率低于98%時，DDR方法優(yōu)勢明顯，而當(dāng)召回率達(dá)到99.9%時，DDR算法的優(yōu)勢大大削弱，這是因為本文所采用的實驗數(shù)據(jù)中的重復(fù)記錄是隨機生成的，某些記錄會與它的重復(fù)記錄有較大差距，當(dāng)召回率接近100%時，所需要搜索空間會比較大，接近于全局搜索.另外，數(shù)據(jù)集的維度越高，DDR的優(yōu)勢越突出.DDR在2維數(shù)據(jù)集中的表現(xiàn)與DSC++相比優(yōu)勢并沒有其在高維數(shù)據(jù)集中明顯，這是由R-樹對候選集的裁剪在高維時更明顯所導(dǎo)致的.

Fig. 8　Efficiency of four algorithms on datasets of 2-D,4-D,8-D,10-D.圖8　4種算法在不同維度的數(shù)據(jù)集中的效率比較

為了更有效地檢驗算法的伸縮性，本文針對2維、4維、8維和10維的數(shù)據(jù)集使用了100萬條記錄對DDR進行測試，比較結(jié)果如圖9所示.從圖9可以看出，隨著維度的增加，DDR所需比較次數(shù)明顯減少，但當(dāng)增加到8維以上，雖然比較次數(shù)依然減少但已不再明顯，這是由高維數(shù)據(jù)的稀疏性決定的.另外，雖然不同維度的數(shù)據(jù)集在比較次數(shù)有明顯的差別，但所消耗時間的差異并沒有如此顯著，這是因為相對于高維數(shù)據(jù)，低維數(shù)據(jù)在計算距離時所消耗的時間相對較少所導(dǎo)致的.

Fig. 9　Efficiency of DDR on datasets of 2-D,4-D,8-D,10-D.圖9　DDR在不同維度的數(shù)據(jù)集中的效率比較

4.3高維數(shù)據(jù)處理的效率

本文提出的大數(shù)據(jù)環(huán)境下重復(fù)檢驗框架效率取決于Apriori性的剪枝效率，而此效率與重復(fù)記錄的距離閾值緊密相關(guān).為檢驗剪枝效率，本文設(shè)計實驗如下:使用4.1節(jié)中生成重復(fù)記錄的方法生成一個10萬條100維的數(shù)據(jù)集，利用一個有10個Map工作機的Map-Reduce系統(tǒng)對其進行重復(fù)檢測，根據(jù)上文討論結(jié)果，每臺Map工作機中僅處理數(shù)據(jù)在其某10維上的投影.實驗通過調(diào)整不同的重復(fù)記錄距離閾值，衡量剪枝效率，結(jié)果如表3所示:

Table 3　Experimental Results of Pruning on 100-D Dataset

從表3可以看出，當(dāng)距離閾值在一定范圍時，利用Apriori性質(zhì)剪枝后得到的潛在重復(fù)記錄對數(shù)目遠(yuǎn)小于平均每個Map工作站得到的低維重復(fù)記錄數(shù).因此，本文提出的剪枝方法能有效減少需要進行重復(fù)檢測的潛在記錄對數(shù)目.

Fig. 10　Pruning efficiency using Apriori property.圖10　利用Apriori性質(zhì)剪枝效率

圖10顯示了隨距離閾值增加剪枝效率改變的曲線.從圖10可以看出，隨著距離閾值增加，全體Map工作站結(jié)果能組成的潛在重復(fù)記錄對在每個Map工作站所得結(jié)果中占比越來越高，但實際重復(fù)記錄對在潛在重復(fù)集中所占比例不斷降低.這意味著，隨著重復(fù)判定的距離閾值增加，利用Apriori性質(zhì)剪枝效果逐漸衰減，這是由高維空間數(shù)據(jù)的稀疏性所導(dǎo)致的.

5結(jié)束語

從第4節(jié)的實驗結(jié)果中可以看出，DDR算法在處理高維數(shù)據(jù)時明顯優(yōu)于傳統(tǒng)的重復(fù)檢測算法，而且當(dāng)數(shù)據(jù)維度小于10維時，維數(shù)越高算法優(yōu)勢越明顯.然而，從實驗中也可以看出DDR算法仍有如下不足：當(dāng)面對高維數(shù)據(jù)時，若要求達(dá)到99%以上的召回率，DDR的時間消耗仍然很大.這是因為重復(fù)檢測需要計算每一對潛在重復(fù)記錄之間的距離，所以即使DDR算法大大裁剪了候選重復(fù)記錄集的數(shù)目，仍需進行大量的計算.因此，如何針對不同的數(shù)據(jù)集確定一個合適的距離從而在召回率和比較次數(shù)之間達(dá)到一個合理的平衡有待進一步研究.我們正在研究如何利用抽樣及軟件測試中的缺陷率估計技術(shù)等方法為真實數(shù)據(jù)集確定一個合適距離.

從剪枝實驗結(jié)果可以看出，當(dāng)數(shù)據(jù)維度較高時，利用Apriori性質(zhì)和一個Map-Reduce過程進行剪枝能有效減少需要計算距離的潛在記錄對.但隨距離閾值增大剪枝效率會降低.因此，如何為高維數(shù)據(jù)挑選一個合理的距離閾值，從而在召回率和計算效率之間達(dá)到一個有效的平衡，也將是我們進一步研究的方向.

參考文獻

[1]Meng Xiaofeng, Ci Xiang. Big data management: Concepts, techniques and challenge[J]. Journal of Computer Research and Development, 2013, 50(1): 146-169 (in Chinese)(孟小峰, 慈祥. 大數(shù)據(jù)管理: 概念、技術(shù)與挑戰(zhàn)[J]. 計算機研究與發(fā)展, 2013, 50(1): 146-169)

[2]Li Jianzhong, Liu Xianmin. An important aspect of big data: Data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147-1162 (in Chinese)(李建中, 劉顯敏. 大數(shù)據(jù)的一個重要方面: 數(shù)據(jù)可用性[J]. 計算機研究與發(fā)展, 2013, 50(6): 1147-1162)

[3]Ahmed K E, Panagiotis G I, Vassilios S V. Duplicate record detection:A survey[J]. IEEE Trans on Knowledge and Data Engineering, 2007, 19(1): 1-16

[4]Christen P. A Survey of Indexing techniques for scalable record linkage and deduplication[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 24(9): 1537-1555

[5]Hernandez M A, Stolfo S J. The mergepurge problem for Large database[C]Proc of the 1995 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 1995: 127-138

[6]Han Jingyu, Xu Lizhen, Dong Yisheng. An approach for detecting similar duplicate records of massive data[J]. Journal of Computer Research and Development, 2005, 42(12): 2206-2212 (in Chinese)(韓京宇, 徐立臻, 董逸生. 一種大數(shù)據(jù)量的相似記錄檢測方法[J]. 計算機研究與發(fā)展, 2005, 42(12): 2206-2212)

[7]Pang Xiongwen, Yao Zhanlin, Li Yongjun. Efficient duplicate records detection method for massive data[J]. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2012, 38(2): 8-11 (in Chinese)(龐雄文, 姚占林, 李擁軍. 大數(shù)據(jù)量的高效重復(fù)記錄檢測方法[J]. 華中科技大學(xué)學(xué)報: 自然科學(xué)版, 2012, 38(2): 8-11)

[8]Fan W, Gao H, Jia X, et al. Dynamic constraints for record matching[J]. The VLDB Journal, 2011, 20(4): 495-520

[9]Yan S, Lee D, Kan M, et al. Adaptive sorted neighborhood methods for efficient record linkage[C]Proc of the 7th ACMIEEE-CS Joint Conf on Digital Libraries (JCDL’07). New York: ACM, 2007: 185-194

[10]Draisbach U, Naumann F, Szott S, et al. Adaptive windows for duplicate detection[C]Proc of the 28th Int Conf on Data Engineering (ICDE’12). Piscataway, NJ: IEEE, 2012: 1073-1083

[11]Alborzi H, Samet H. Execution time analysis of a top-down R-tree construction algorithm[J]. Information Processing Letters, 2007, 101(1): 6-12

[12]ANU Data Mining Group. Prototype software[CPOL]. 2014 [2014-06-01]. http:datamining.anu.edu.aulinkage.html

Zhu Weiheng, born in 1976. Lecturer. Receive his PhD from Sun Yat-sen University. His main research interests include database, data mining and pattern recognition.

Yin Jian, born in 1968. Professor and PhD supervisor at Sun Yat-sen University, China. Senior member of China Computer Federation. His main research interests include big data and data mining.

Deng Yuhui, born in 1974. PhD, professor and PhD supervisior. His current research interests cover data storage and data management, cluster computing, and green computing.

Long Shun, born in 1971. Associate professor at Jinan University, China. His main research interests include machine learning, data mining and information retrieval.

Qiu Shiding, born in 1989. Received his master degree at Jinan University in 2014, China. His main research interests include social network mining, large scale machine learning.

中圖法分類號TP391

通信作者：龍舜(tlongshun@jnu.edu.cn)

基金項目：國家自然科學(xué)基金項目(61472453,61272073,61401177,61572232,U1401256,U1501252)；廣東省自然科學(xué)基金項目(S2013020012865)；廣東省科技計劃基金項目(2013B010401017)

收稿日期：2014-11-06；修回日期：2015-05-05

This work was supported by the National Natural Science Foundation of China (61472453,61272073,61401177,61572232,U1401256,U1501252), the Natural Science Foundation of Guangdong Province of China (S2013020012865), and the Science and Technology Planning Project of Guangdong Province (2013B010401017).