余 通 賓冬梅 黎 新 楊春燕 凌 穎
(廣西電網(wǎng)有限責(zé)任公司電力科學(xué)研究院,廣西 南寧530023)
冗余是指一個(gè)實(shí)體由多個(gè)不完全相同的記錄表示的現(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ù)集時(shí)表現(xiàn)出良好的性能,但單機(jī)環(huán)境下的計(jì)算資源無法滿足海量數(shù)據(jù)集的處理要求。為此,本文提出了數(shù)據(jù)冗余檢測算法ROFA,并基于Spark 和ROFA 設(shè)計(jì)了海量數(shù)據(jù)的冗余檢測策略,實(shí)現(xiàn)了海量數(shù)據(jù)的冗余檢測,解決了海量數(shù)據(jù)產(chǎn)生的瓶頸。
本文引用文獻(xiàn)[3]中Simhash 算法完成數(shù)據(jù)元組與對應(yīng)的二進(jìn)制串(指紋)的轉(zhuǎn)換。而為實(shí)現(xiàn)冗余數(shù)據(jù)的有效檢測,本文設(shè)計(jì)了指紋檢索樹(F-Indextree),并提出了基于F-Indextree 的指紋冗余檢測算法ROFA。
定義指紋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)計(jì)算記錄IDi的f 維指紋Si,并將Si均分為ω=f/r 段,用βk表示各段,βk為r bit 的二進(jìn)制串,即Si表示為β1…βω;
(3)以βk為節(jié)點(diǎn)構(gòu)建F-Indextree,若βk=βξ,則視為同個(gè)節(jié)點(diǎn),kξ∈[1,ω]。當(dāng)βk為葉節(jié)點(diǎn),則在其中插入Si的標(biāo)識flagi=(di,IDi),F(xiàn)-Indextree 中各個(gè)不同的路徑,分別表示不同的指紋;
(4)循環(huán)(2)至(3)Step,直到Si為空。
從F-Indextree 結(jié)構(gòu)可見,若需檢測指紋Si的相似性,則需遍歷指紋樹F-Indextree 至各個(gè)葉節(jié)點(diǎn)。為解決高時(shí)間復(fù)雜度,引入Hamming distance 并利用廣度優(yōu)先算法和結(jié)合抽屜原理,設(shè)計(jì)了基于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 的ω-μ 個(gè)βk是冗余的,則包含這ωμ 個(gè)βk的所有Sk都是冗余的。
(5)輸出Sk的葉節(jié)點(diǎn)的flagk,u={flagk}。
(6)輸出u,即為所檢索的冗余指紋。通過冗余指紋即可提取冗余的數(shù)據(jù)。
表1 算法的精確性比較
表2 SP-ROFA 算法檢測精度
表3 SP-ROFA 算法檢測結(jié)果
基于Spark 的性質(zhì),結(jié)合ROFA 算法,本文設(shè)計(jì)了海量數(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(),輸出冗余指紋。
為評估算法的有效性,本文在6 臺曙光I620-G10 服務(wù)器上搭建Spark 集群實(shí)驗(yàn)環(huán)境,實(shí)驗(yàn)數(shù)據(jù)來自UCI 的數(shù)據(jù)是家庭用電信息。此外,定義海明距離小于或等于3 的兩個(gè)指紋是相似的,指紋長度為64 位。標(biāo)準(zhǔn)hash 算法采用MD5。實(shí)驗(yàn)從檢測精度、召回率和算法對參數(shù)的敏感性三個(gè)維度進(jìn)行分析。
檢驗(yàn)ROFA 的有效性及其精確性,將其檢測結(jié)果與表1 中的算法對比。采用召回率(R)、準(zhǔn)確率(P)和F1-score(F1)作為評價(jià)標(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%的浮動(dòng)差異,但是仍具有良好的檢測效果和適用性。
由表1 和表2 中算法的平均P、R、F1的對比可知:SP-ROFA 和ROFA 的檢測精度、召回率和平衡性平均提高了約59.21%、2.1%和44.2%;并且在所有對比算法中,SP-ROFA 和ROFA 的召回率略低于其中的兩個(gè)算法,但它們的平均P 和F1最高,即本文算法的性能最優(yōu),具有更強(qiáng)的適用性。
檢測數(shù)據(jù)規(guī)模對檢測精度、召回率的影響,采用1.0GB、10.0GB、100.0GB 的數(shù)據(jù)來對SP-ROFA 的P、R 和F1進(jìn)行評估,見表3 所示。
由上表可見,當(dāng)數(shù)據(jù)以遞增到100GB 時(shí),SP-ROFA 的P、R和F1均在8%內(nèi)浮動(dòng),其平均P 為93%、平均R 為95%、平均F1為94%,算法具有良好的穩(wěn)定性和檢測效果。而隨著數(shù)據(jù)規(guī)模的快速增加,SP-ROFA 的P、R 和F1有所下降,但受數(shù)據(jù)快速增長的影響比較小,穩(wěn)定性高,適用于快速增長的海量數(shù)據(jù)冗余的檢測。
針對傳統(tǒng)方法難以有效完成海量數(shù)據(jù)的冗余檢測問題,設(shè)計(jì)了ROFA 算法,并提出了基于Spark 和ROFA 的海量數(shù)據(jù)冗余檢測策略SP-ROFA。實(shí)驗(yàn)結(jié)果表明,本文的算法有效、穩(wěn)定,并表現(xiàn)出良好的伸縮性和加速比,適用于海量數(shù)據(jù)的冗余檢測。接下來的任務(wù)是算法尋優(yōu),使其更好應(yīng)用于海量數(shù)據(jù)的處理中。