殷秀葉

周口師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 周口 466001

0 引 言

在信息化的時(shí)代，數(shù)據(jù)是企業(yè)成功的關(guān)鍵，而高質(zhì)量數(shù)據(jù)是保證企業(yè)健康發(fā)展的前提，企業(yè)在對(duì)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析的過(guò)程中，難免會(huì)受到“臟、亂”數(shù)據(jù)的影響，在大數(shù)據(jù)環(huán)境下，原始數(shù)據(jù)中可能存在著大量的相似重復(fù)記錄，這些記錄將會(huì)影響數(shù)據(jù)統(tǒng)計(jì)分析的效率與準(zhǔn)確性，如何有效的處理這些相似重復(fù)記錄顯得尤為重要[1].

相似重復(fù)記錄常用的檢測(cè)方法主要是排序-合并算法和二次聚類算法，這些算法在處理小數(shù)據(jù)集時(shí)有較高的效率，但隨著數(shù)據(jù)量的不斷增大，在大數(shù)據(jù)環(huán)境下，這些方法不能有效的提升檢測(cè)的效率，如在數(shù)據(jù)量較大時(shí)，排序-合并算法有大量的I/O開(kāi)銷.另外，基于字符位置的敏感性問(wèn)題，對(duì)排序的記錄不能保證相似記錄一定排在臨近的位置，不能有效的提升重復(fù)記錄檢測(cè)的記憶率(recall，識(shí)別出的相似重復(fù)記錄占整個(gè)數(shù)據(jù)集中所有重復(fù)記錄的百分比)和準(zhǔn)確率(precision，識(shí)別出的相似重復(fù)記錄中正確的識(shí)別占識(shí)別出的相似重復(fù)記錄的百分比).

1 相關(guān)工作

在相似重復(fù)記錄檢測(cè)上，已出現(xiàn)了一些成果，如早期的“排序-合并” 算法，首先對(duì)記錄進(jìn)行排序，然后比較鄰近記錄的字段是否相等，在解決重復(fù)記錄的檢測(cè)上，有著較高的效率.

文獻(xiàn)[2]通過(guò)等級(jí)法計(jì)算每個(gè)字段的權(quán)值,然后按照分組的思想[2]，選擇關(guān)鍵字段或字段某些位將大數(shù)據(jù)集分割成許多不相交的小數(shù)據(jù)集來(lái)解決數(shù)據(jù)量較大的問(wèn)題，提高相似重復(fù)記錄檢測(cè)效率.

文獻(xiàn)[3]提出了一種大數(shù)據(jù)量的重復(fù)記錄檢測(cè)方法，對(duì)于檢測(cè)出的重復(fù)記錄，保留一條記錄作為主記錄，其他重復(fù)記錄中的信息合并到主記錄[3].由于比較重復(fù)記錄需比較記錄間所有的屬性字段,因此比較次數(shù)影響比較算法的效率,作者以減少記錄間比較次數(shù)的思想，提高算法的效率.但由于有些記錄中的字段存在互斥的值(如性別的取值)，因此作者考慮了帶限制規(guī)則的重復(fù)記錄檢測(cè)方法，引入了限制規(guī)則.

文獻(xiàn)[4]通過(guò)計(jì)算屬性的權(quán)重，確定每一屬性對(duì)于記錄相似性檢測(cè)的重要性，然后多線程并發(fā)檢測(cè)記錄集，每個(gè)線程針對(duì)一個(gè)屬性對(duì)記錄集進(jìn)行排序；最后在每個(gè)線程中檢測(cè)相似重復(fù)記錄并且合并所有的檢測(cè)結(jié)果[4-5].

文獻(xiàn)[6]提出了一種q-gram層次空間的聚類檢測(cè)方法，將數(shù)據(jù)映射成q-gram空間中的點(diǎn)，并根據(jù)空間中的相似性通過(guò)層次聚類的方法來(lái)檢測(cè)相似重復(fù)記錄[6-7]，有效的解決了傳統(tǒng)的“排序-合并”算法中部分相似記錄由于字符位置敏感而不能排在鄰近位置的問(wèn)題，提高了檢測(cè)的精度，在大數(shù)據(jù)環(huán)境下有較好的伸縮性.

文獻(xiàn)[8]通過(guò)對(duì)CURE算法進(jìn)行改進(jìn)，利用預(yù)抽樣的概念，提高了隨機(jī)抽樣的準(zhǔn)確性，并改進(jìn)代表點(diǎn)的選擇方法[8]，通過(guò)基于距離影響因子的代表點(diǎn)選取策略，提高了代表點(diǎn)選取的合理性，提升了相似重復(fù)記錄檢測(cè)的準(zhǔn)確性.

以上方法在不同的方面取得了不同的效果，但均未考慮在大數(shù)據(jù)環(huán)境下，充分利用MapReduce的思想，提升相似重復(fù)記錄檢測(cè)的效率.

2 相似重復(fù)記錄檢測(cè)方法

2.1 思想描述

由于在數(shù)據(jù)集中會(huì)存在很多意思相同但表示方式不同的字段，如區(qū)域和區(qū)號(hào) (北京，010)，都表示區(qū)域信息，只是一個(gè)是用編碼的方式，一個(gè)是用漢字的方式，這部分字段的取值是一一對(duì)應(yīng)的，在進(jìn)行相似重復(fù)數(shù)據(jù)檢測(cè)計(jì)算時(shí)，權(quán)值是相同的，把這種屬性稱為同義屬性.

此種相似重復(fù)記錄檢測(cè)的總體思想是：考慮到大數(shù)據(jù)環(huán)境下數(shù)據(jù)量巨大的問(wèn)題，在相似重復(fù)記錄檢測(cè)中，首先通過(guò)加權(quán)法計(jì)算屬性的權(quán)重，為了提高屬性加權(quán)計(jì)算的效率，先利用過(guò)濾法過(guò)濾掉同義屬性，然后在計(jì)算屬性權(quán)重及排序時(shí)，只按照同義屬性中的一個(gè)進(jìn)行權(quán)值計(jì)算，然后將計(jì)算結(jié)果直接作為兩者共同的權(quán)值.

由于大數(shù)據(jù)環(huán)境中有很多這樣的字段，多體現(xiàn)為維度字段，因此能夠直接減少屬性加權(quán)計(jì)算時(shí)的數(shù)據(jù)集合，提升計(jì)算的效率.另外，由于同義屬性比較直觀，因此這部分內(nèi)容可由數(shù)據(jù)庫(kù)操作者直接指定，并不會(huì)給加權(quán)計(jì)算帶來(lái)額外的任務(wù)和開(kāi)銷.權(quán)重計(jì)算完成后，按照權(quán)值大小將數(shù)據(jù)集合進(jìn)行排序，然后利用MapReduce的思想，將數(shù)據(jù)集合按照不同的字段拆分成若干個(gè)小的數(shù)據(jù)集合，且相同的字段也劃分若干個(gè)集合，由MapReduce分別利用不同的Map任務(wù)處理各個(gè)小的數(shù)據(jù)集合中的相似重復(fù)字段，最終利用Reduce任務(wù)合并處理結(jié)果，提升重復(fù)記錄檢測(cè)的效率.

2.2 權(quán)重計(jì)算

設(shè)數(shù)據(jù)表T中有m個(gè)屬性，用向量C={C1，C2，…，Cm}來(lái)表示，其中Cm表示數(shù)據(jù)表T的第m個(gè)屬性，用向量W={W1,W2,…，Wm}來(lái)表示屬性的權(quán)重,其中Wm表示屬性向量C中第m個(gè)屬性的權(quán)重.考慮到屬性的取值變化情況，取值越多，說(shuō)明權(quán)重越大，因此，通過(guò)屬性取值的變化情況來(lái)衡量屬性的權(quán)重.

考慮到大數(shù)據(jù)環(huán)境下數(shù)據(jù)量過(guò)大的問(wèn)題，采用隨機(jī)抽樣法，每次選取固定數(shù)量的數(shù)據(jù)來(lái)統(tǒng)計(jì)在固定數(shù)量?jī)?nèi)每個(gè)屬性的取值變化個(gè)數(shù)，設(shè)countij為數(shù)據(jù)表T第i個(gè)屬性Ci在第j次隨機(jī)抽取的m條記錄內(nèi)取值的變化個(gè)數(shù)，k為隨機(jī)抽樣的次數(shù)，則Ci的權(quán)重Wi可表示為：

(1)

假設(shè)數(shù)據(jù)表T中的m個(gè)屬性有2n個(gè)同義屬性，則計(jì)算權(quán)值的數(shù)據(jù)表T′的屬性數(shù)即為T-{n}，即假設(shè)數(shù)據(jù)表中有20個(gè)屬性，而同義屬性有8個(gè),則在計(jì)算權(quán)重時(shí)，可以去掉至少4個(gè)同義屬性，原本20個(gè)屬性的數(shù)據(jù)表，現(xiàn)在最多只需要對(duì)16個(gè)屬性進(jìn)行操作，效率能夠提升20%.同義屬性越多，效率提升的也越多.

2.3 相似重復(fù)數(shù)據(jù)處理

對(duì)于任意的屬性Ck，其在第i條記錄的取值與第j條記錄的取值的相似程度用S(Cik,Cjk)表示，Cik和Cjk的取值越接近，則S(Cik,Cjk)的取值越大，S(Cik,Cjk)的取值范圍為[0,1]，可以用式(2)來(lái)表示.

(2)

其中|Cjk|表示第j條記錄中字段Ck的長(zhǎng)度，se(p,Cjk)表示第i條記錄中字段 取值的某一個(gè)子串p與第j條記錄中字段Ck取值的每一個(gè)對(duì)應(yīng)子串的匹配程度，t代表子串的個(gè)數(shù).

對(duì)于兩條記錄Ci和Cj的相似度，可用如式(3)表示.

(3)

其中Same (Ci,Cj)表示記錄Ci和Cj的相似度，m表示關(guān)系表T中屬性的個(gè)數(shù)，Wk表示關(guān)系表T中屬性Ck的權(quán)值.

按照屬性的權(quán)值對(duì)數(shù)據(jù)表進(jìn)行排序，權(quán)值越大，排序越靠后，然后將大數(shù)據(jù)集按照屬性拆分成若干個(gè)小的數(shù)據(jù)集，利用MapReduce的處理機(jī)制，將各個(gè)小的數(shù)據(jù)集交給MapReduce中的若干個(gè)小的Map任務(wù)去處理，為了提高相似性檢測(cè)的合理性，數(shù)據(jù)集的拆分也多次進(jìn)行，以保證相同的數(shù)據(jù)能夠被分配到一組，提高相似重復(fù)字段檢測(cè)的記憶率.Map任務(wù)處理完成后，通過(guò)Reduce任務(wù)將處理結(jié)果合并，最終輸出處理后的結(jié)果.

3 實(shí) 驗(yàn)

為了驗(yàn)證算法的效率，實(shí)驗(yàn)采用Hadoop平臺(tái)，將算法與文獻(xiàn)[4]中提出的算法進(jìn)行了比較，實(shí)驗(yàn)的數(shù)據(jù)來(lái)自于高校半年內(nèi)學(xué)生在餐廳的刷卡信息，共有數(shù)據(jù)500多萬(wàn)條.

實(shí)驗(yàn)采用的環(huán)境為64位AMD皓龍6274 CPU,196G的內(nèi)存，代碼采用JAVA語(yǔ)言實(shí)現(xiàn)，在Hadoop-1.0.4上運(yùn)行.

文獻(xiàn)[4]提出的利用等級(jí)計(jì)算權(quán)重，然后利用優(yōu)先隊(duì)列算法進(jìn)行相似重復(fù)記錄檢測(cè)的方法是效率較高的一種算法，其思想是：首先利用組合賦權(quán)的思想，為每個(gè)屬性確定一個(gè)等級(jí)，再根據(jù)每個(gè)屬性的等級(jí)計(jì)算權(quán)重，然后采用多線程并發(fā)執(zhí)行的方式檢測(cè)相似重復(fù)記錄，并采用加速法減少多余的編輯距離計(jì)算，采用優(yōu)先隊(duì)列的重復(fù)聚類思想代替固定窗口大小的滑動(dòng)窗口方法.該算法具有較高的檢測(cè)精度和較小的時(shí)間復(fù)雜度.因此，選擇該算法(以IWM簡(jiǎn)稱該算法)與本文提出的算法(SPM)進(jìn)行比較，數(shù)據(jù)量共510萬(wàn)條，共有同義屬性3對(duì)，字段14個(gè).比較結(jié)果如表1所示.

表1 IWM算法與SPM算法的綜合比較

比較結(jié)果表明，在相同的機(jī)器上，由于本算法利用同義屬性降低了數(shù)據(jù)集，并利用Hadoop平臺(tái)加快了數(shù)據(jù)檢測(cè)的效率，因此在時(shí)間復(fù)雜度上有較好的表現(xiàn)，在算法的查準(zhǔn)率和查全率上，兩種算法的表現(xiàn)趨向一致.但由于不同數(shù)據(jù)集合中同義屬性存在的數(shù)量不同，因此本文提出的算法的時(shí)間開(kāi)銷與同義屬性的多少有關(guān)，同義屬性越多，則時(shí)間復(fù)雜度越低，反之越高，但只要同義屬性存在，都能不同程度的提高相似重復(fù)數(shù)據(jù)檢測(cè)的效率.

4 結(jié) 語(yǔ)

以上對(duì)相似重復(fù)記錄檢測(cè)進(jìn)行了相關(guān)介紹，通過(guò)識(shí)別同義字段，直接減少了數(shù)據(jù)集的屬性個(gè)數(shù)，降低了在權(quán)重計(jì)算階段的工作量.另外，論文對(duì)相似重復(fù)數(shù)據(jù)的判定給出了公式，并將數(shù)據(jù)集按照屬性的權(quán)重進(jìn)行拆分，將拆分后的若干小數(shù)據(jù)集通過(guò)MapReduce進(jìn)行處理，充分提高了相似性重復(fù)記錄檢測(cè)的速度.對(duì)于同義字段的公式判定，將在后續(xù)工作中進(jìn)行研究.

致 謝

本研究在選題及論文寫作的過(guò)程中，陳立勇老師提出了很多寶貴的意見(jiàn)，謹(jǐn)致謝意.感謝國(guó)家自然科學(xué)基金委員會(huì)對(duì)項(xiàng)目的開(kāi)展提供的支持.

[1] 李建中,劉顯敏.大數(shù)據(jù)的一個(gè)重要方面:數(shù)據(jù)可用性[J] .計(jì)算機(jī)研究與發(fā)展, 2013,50(6) :1147-1162.

LI Jian-zhong,LIU Xian-min. An important aspect of big data：data usability[J]. Journal of Computer Research and Development, 2013,50(6) :1147-1162.(in Chinese)

[2] 李星毅,包從劍,施化吉.數(shù)據(jù)倉(cāng)庫(kù)中的相似重復(fù)記錄檢測(cè)方法[J]. 電子科技大學(xué)學(xué)報(bào),2007,36(6):1273-1277.

LI Xing-yi, BAO Cong-jian, SHI Hua-ji. A method for detecting approximately duplicate database records in data warehouse[J]. Journal of University of Electronic Science and Technology of China, 2007,36(6):1273-1277. (in Chinese)

[3] 龐雄文,姚占林,李擁軍.大數(shù)據(jù)量的高效重復(fù)記錄檢測(cè)方法[J].華中科技大學(xué)學(xué)報(bào),2010,38(2):8-11.

PANG Xiong-wen, YAO Zhan-lin, LI Yong-jun. Efficient duplicate records detection method for massive data[J]. Journal of Huazhong University of Science and Technology,2010,38(2):8-11. (in Chinese)

[4] 周典瑞,周蓮英.海量數(shù)據(jù)的相似記錄檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用,2013,33(8):2208-2211.

ZHOU Dian-rui,ZHOU Lian-ying. Algorithm for detecting approximate duplicate records in massive data[J]. Journal of Computer Application,2013,33(8):2208-2211. (in Chinese)

[5] 敖莉,舒繼武,李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].軟件學(xué)報(bào),2010, 21(5):916-929.

AO Li, SHU Ji-wu, LI Ming-qiang. Data deduplication techniques[J]. Journal of Software, 2010,21(5):916-929. (in Chinese)

[6] 韓京宇,徐立臻,董逸生.一種大數(shù)據(jù)量的相似記錄檢測(cè)方法[J].計(jì)算機(jī)研究與發(fā)展, 2005,42(12) :2206-2212.

HAN Jing-yu,XU Li-zhen,DONG Yi-sheng. An approach for detecting similar duplicate records of massive data[J]. Journal of Computer Research and Development, 2005,42(12):2206-2212. (in Chinese)

[7] 邱越峰.一種高效的檢測(cè)相似重復(fù)記錄的方法[J].計(jì)算機(jī)學(xué)報(bào),2001,24(1):69-77.

QIU Yue-fen. An efficient approach for detecting approximately duplicate database records[J]. CHINESE J.COMPUTERS, 2001,24(1):69-77. (in Chinese)

[8] DEAN J，GHEMAWAT S. MapReduce: simplified data processing on large clusters[C]// In Proceedings of the 6th Symposium on Operating Systems Design and Implementation, New York：NY，2004.