基于Spark 的海量數據冗余檢測方法

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

（廣西電網有限責任公司電力科學研究院，廣西 南寧530023）

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

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

1 基于指紋檢索樹的數據冗余檢測算法

本文引用文獻[3]中Simhash 算法完成數據元組與對應的二進制串（指紋）的轉換。而為實現冗余數據的有效檢測，本文設計了指紋檢索樹（F-Indextree），并提出了基于F-Indextree 的指紋冗余檢測算法ROFA。

1.1 F-Indextree 的構建

定義指紋Si的標識符flag 為（di，IDi），其中IDi為Si的行標，di為Si對應的十進制數。指紋檢索樹F-Indextree 的構建Step 描述如下：

（1）初始化根節點為空集；

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

（3）以βk為節點構建F-Indextree，若βk=βξ，則視為同個節點，kξ∈[1，ω]。當βk為葉節點，則在其中插入Si的標識flagi=（di，IDi），F-Indextree 中各個不同的路徑，分別表示不同的指紋；

（4）循環（2）至（3）Step，直到Si為空。

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

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

（1）F-Indextree（S），用創建指紋檢索樹T；

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

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

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

（5）輸出Sk的葉節點的flagk，u={flagk}。

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

表1 算法的精確性比較

表2 SP-ROFA 算法檢測精度

表3 SP-ROFA 算法檢測結果

2 基于Spark 和ROFA 的海量數據冗余檢測策略

基于Spark 的性質，結合ROFA 算法，本文設計了海量數據冗余檢測算法。

基于Spark 和ROFA 的算法（Sp-ROFA）實現：

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

輸入：數據關系表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：執行Executor 進程，調用基于指紋檢索樹的指紋檢索算法，生成冗余RDD；

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

3 實例分析

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

3.1 檢測精度和召回率分析

檢驗ROFA 的有效性及其精確性，將其檢測結果與表1 中的算法對比。采用召回率（R）、準確率（P）和F1-score（F1）作為評價標準；實驗數據為4MB 且為單機環境，實驗結果如表1 所示。

同樣地，在6 臺服務器上搭建Spark 集群環境檢驗SP-ROFA 的精確性和召回率并與單機環境下的ROFA 的精確度和召回率對比。實驗結果見表2 所示。

由表2 見，因SP-ROFA 僅僅是ROFA 在Spark 平臺上的并行化實現，因此，相同環境下，ROFA 的檢測精度、召回率和SP-ROFA 的在相當的水平上，平均檢測精度均約為96%，召回率均約為98%，F1均約為98%。此外，由于初始數據格式存在差異等因素，算法檢測效果表現相當，存在1.05%的浮動差異，但是仍具有良好的檢測效果和適用性。

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

3.2 算法對參數的敏感性分析

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

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

4 結論

針對傳統方法難以有效完成海量數據的冗余檢測問題，設計了ROFA 算法，并提出了基于Spark 和ROFA 的海量數據冗余檢測策略SP-ROFA。實驗結果表明，本文的算法有效、穩定，并表現出良好的伸縮性和加速比，適用于海量數據的冗余檢測。接下來的任務是算法尋優，使其更好應用于海量數據的處理中。