余 通 賓冬梅 黎 新 楊春燕 凌 穎

（廣西電網(wǎng)有限責(zé)任公司電力科學(xué)研究院，廣西 南寧530023）

冗余是指一個實(shí)體由多個不完全相同的記錄表示的現(xiàn)象，它是影響數(shù)據(jù)質(zhì)量的主要因素[1]。在應(yīng)用系統(tǒng)的信息采集中，數(shù)據(jù)信息的冗余檢測是數(shù)據(jù)質(zhì)量優(yōu)劣保證的關(guān)鍵，是有效實(shí)現(xiàn)數(shù)據(jù)清洗的保障。隨著信息化的發(fā)展的不斷深入，數(shù)據(jù)呈指數(shù)級膨脹，年數(shù)據(jù)量的增長從GB 級增長到了TB 級。這快速增長的數(shù)據(jù)體量使數(shù)據(jù)維度也在不斷擴(kuò)大，并且其中大部分?jǐn)?shù)據(jù)都是冗余的。這使傳統(tǒng)方法上的冗余檢測難度大大增加，因此，海量數(shù)據(jù)的冗余檢測已成為當(dāng)下廣泛研究的熱點(diǎn)[2-3]。

長期以來，冗余檢測的研究取得了大量的成效，這些研究在處理小數(shù)據(jù)集時表現(xiàn)出良好的性能，但單機(jī)環(huán)境下的計算資源無法滿足海量數(shù)據(jù)集的處理要求。為此，本文提出了數(shù)據(jù)冗余檢測算法ROFA，并基于Spark 和ROFA 設(shè)計了海量數(shù)據(jù)的冗余檢測策略，實(shí)現(xiàn)了海量數(shù)據(jù)的冗余檢測，解決了海量數(shù)據(jù)產(chǎn)生的瓶頸。

1 基于指紋檢索樹的數(shù)據(jù)冗余檢測算法

本文引用文獻(xiàn)[3]中Simhash 算法完成數(shù)據(jù)元組與對應(yīng)的二進(jìn)制串（指紋）的轉(zhuǎn)換。而為實(shí)現(xiàn)冗余數(shù)據(jù)的有效檢測，本文設(shè)計了指紋檢索樹（F-Indextree），并提出了基于F-Indextree 的指紋冗余檢測算法ROFA。

1.1 F-Indextree 的構(gòu)建

定義指紋Si的標(biāo)識符flag 為（di，IDi），其中IDi為Si的行標(biāo)，di為Si對應(yīng)的十進(jìn)制數(shù)。指紋檢索樹F-Indextree 的構(gòu)建Step 描述如下：

（1）初始化根節(jié)點(diǎn)為空集；

（2）計算記錄IDi的f 維指紋Si，并將Si均分為ω=f/r 段，用βk表示各段，βk為r bit 的二進(jìn)制串，即Si表示為β1…βω；

（3）以βk為節(jié)點(diǎn)構(gòu)建F-Indextree，若βk=βξ，則視為同個節(jié)點(diǎn)，kξ∈[1，ω]。當(dāng)βk為葉節(jié)點(diǎn)，則在其中插入Si的標(biāo)識flagi=（di，IDi），F(xiàn)-Indextree 中各個不同的路徑，分別表示不同的指紋；

（4）循環(huán)（2）至（3）Step，直到Si為空。

1.2 基于F-Indextree 的指紋冗余檢測算法

從F-Indextree 結(jié)構(gòu)可見，若需檢測指紋Si的相似性，則需遍歷指紋樹F-Indextree 至各個葉節(jié)點(diǎn)。為解決高時間復(fù)雜度，引入Hamming distance 并利用廣度優(yōu)先算法和結(jié)合抽屜原理，設(shè)計了基于F-Indextree 的指紋檢索算法。假設(shè)要在S=（fi）T中檢測出與Si冗余的部分，設(shè)定閾值為μ，即Hamming distance＜u的指紋是冗余的。則算法描述如下：

（1）F-Indextree（S），用創(chuàng)建指紋檢索樹T；

（2）將指紋Si按T 中指紋的方式分段，即將Si均分為ω=f/r段，Si=（α1…αω）。

（3）以廣度優(yōu)先檢索算法規(guī)則，求αi與βk的海明距離hi；

（4）引用抽屜原理規(guī)則判斷指紋的冗余性，若與Hammin distance（αi）=0 的ω-μ 個βk是冗余的，則包含這ωμ 個βk的所有Sk都是冗余的。

（5）輸出Sk的葉節(jié)點(diǎn)的flagk，u={flagk}。

（6）輸出u，即為所檢索的冗余指紋。通過冗余指紋即可提取冗余的數(shù)據(jù)。

表1 算法的精確性比較

表2 SP-ROFA 算法檢測精度

表3 SP-ROFA 算法檢測結(jié)果

2 基于Spark 和ROFA 的海量數(shù)據(jù)冗余檢測策略

基于Spark 的性質(zhì)，結(jié)合ROFA 算法，本文設(shè)計了海量數(shù)據(jù)冗余檢測算法。

基于Spark 和ROFA 的算法（Sp-ROFA）實(shí)現(xiàn)：

對關(guān)系表Ek，K∈R 行號記為ID，關(guān)系表的第i 行j 列的屬性值記為Ai，j且Ai，j∈Ai；檢測Ek中的冗余，算法描述如下：

輸入：數(shù)據(jù)關(guān)系表Ek

輸出：冗余記錄

Step1：通過SparkContext.textFile（）和RDD.Cache（）；

Step2：通過SimHash 方法生成指紋RDD；并按＜key=IDi，value=si＞的格式存儲；

Step3：Executor.Map（），Update（＜key=IDi，value=si＞）；

Step4：Executor.Reduce（＜key=IDi，value=Si＞）；

Step5：引入指紋檢索樹算法生成指紋檢索樹RDD；

Step3：執(zhí)行Executor 進(jìn)程，調(diào)用基于指紋檢索樹的指紋檢索算法，生成冗余RDD；

Step4：Action.saveAsTextFile（），輸出冗余指紋。

3 實(shí)例分析

為評估算法的有效性，本文在6 臺曙光I620-G10 服務(wù)器上搭建Spark 集群實(shí)驗(yàn)環(huán)境，實(shí)驗(yàn)數(shù)據(jù)來自UCI 的數(shù)據(jù)是家庭用電信息。此外，定義海明距離小于或等于3 的兩個指紋是相似的，指紋長度為64 位。標(biāo)準(zhǔn)hash 算法采用MD5。實(shí)驗(yàn)從檢測精度、召回率和算法對參數(shù)的敏感性三個維度進(jìn)行分析。

3.1 檢測精度和召回率分析

檢驗(yàn)ROFA 的有效性及其精確性，將其檢測結(jié)果與表1 中的算法對比。采用召回率（R）、準(zhǔn)確率（P）和F1-score（F1）作為評價標(biāo)準(zhǔn)；實(shí)驗(yàn)數(shù)據(jù)為4MB 且為單機(jī)環(huán)境，實(shí)驗(yàn)結(jié)果如表1 所示。

同樣地，在6 臺服務(wù)器上搭建Spark 集群環(huán)境檢驗(yàn)SP-ROFA 的精確性和召回率并與單機(jī)環(huán)境下的ROFA 的精確度和召回率對比。實(shí)驗(yàn)結(jié)果見表2 所示。

由表2 見，因SP-ROFA 僅僅是ROFA 在Spark 平臺上的并行化實(shí)現(xiàn)，因此，相同環(huán)境下，ROFA 的檢測精度、召回率和SP-ROFA 的在相當(dāng)?shù)乃缴?，平均檢測精度均約為96%，召回率均約為98%，F(xiàn)1均約為98%。此外，由于初始數(shù)據(jù)格式存在差異等因素，算法檢測效果表現(xiàn)相當(dāng)，存在1.05%的浮動差異，但是仍具有良好的檢測效果和適用性。

由表1 和表2 中算法的平均P、R、F1的對比可知：SP-ROFA 和ROFA 的檢測精度、召回率和平衡性平均提高了約59.21%、2.1%和44.2%；并且在所有對比算法中，SP-ROFA 和ROFA 的召回率略低于其中的兩個算法，但它們的平均P 和F1最高，即本文算法的性能最優(yōu)，具有更強(qiáng)的適用性。

3.2 算法對參數(shù)的敏感性分析

檢測數(shù)據(jù)規(guī)模對檢測精度、召回率的影響，采用1.0GB、10.0GB、100.0GB 的數(shù)據(jù)來對SP-ROFA 的P、R 和F1進(jìn)行評估，見表3 所示。

由上表可見，當(dāng)數(shù)據(jù)以遞增到100GB 時，SP-ROFA 的P、R和F1均在8%內(nèi)浮動，其平均P 為93%、平均R 為95%、平均F1為94%，算法具有良好的穩(wěn)定性和檢測效果。而隨著數(shù)據(jù)規(guī)模的快速增加，SP-ROFA 的P、R 和F1有所下降，但受數(shù)據(jù)快速增長的影響比較小，穩(wěn)定性高，適用于快速增長的海量數(shù)據(jù)冗余的檢測。

4 結(jié)論

針對傳統(tǒng)方法難以有效完成海量數(shù)據(jù)的冗余檢測問題，設(shè)計了ROFA 算法，并提出了基于Spark 和ROFA 的海量數(shù)據(jù)冗余檢測策略SP-ROFA。實(shí)驗(yàn)結(jié)果表明，本文的算法有效、穩(wěn)定，并表現(xiàn)出良好的伸縮性和加速比，適用于海量數(shù)據(jù)的冗余檢測。接下來的任務(wù)是算法尋優(yōu)，使其更好應(yīng)用于海量數(shù)據(jù)的處理中。