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

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

0 引言

臟數(shù)據(jù)是指數(shù)據(jù)不在給定范圍內(nèi)、數(shù)據(jù)格式非法或不規(guī)范編碼的數(shù)據(jù)，它是影響數(shù)據(jù)質(zhì)量的主要因素。在電力系統(tǒng)中，要保證數(shù)據(jù)質(zhì)量、提高數(shù)據(jù)利用效能的效率，同時(shí)為了有效利用電力數(shù)據(jù)來(lái)支撐電力系統(tǒng)運(yùn)行的決策管控和決策知識(shí)，電力行業(yè)數(shù)據(jù)中的臟數(shù)據(jù)檢測(cè)是其基礎(chǔ)和重要保障，對(duì)電力系統(tǒng)穩(wěn)定運(yùn)行管控具有重要支撐意義。隨著數(shù)字化和信息化在工業(yè)和能源等行業(yè)中的推進(jìn)，應(yīng)用數(shù)據(jù)呈指數(shù)級(jí)不斷增長(zhǎng)，每年應(yīng)用數(shù)據(jù)的體量以TB數(shù)量級(jí)在增長(zhǎng)。體量的不斷增長(zhǎng)在一定程度上使得數(shù)據(jù)的維度和密度在發(fā)生巨大變化，并且表現(xiàn)出了價(jià)值密度低的特點(diǎn)，并且摻雜了高比例的臟數(shù)據(jù)，這給傳統(tǒng)的臟數(shù)據(jù)檢測(cè)方法造成了困難。因此，研究人員提出了基于Spark和圖論的臟數(shù)據(jù)智能動(dòng)態(tài)檢測(cè)方法。

長(zhǎng)期以來(lái)，對(duì)臟數(shù)據(jù)檢測(cè)的研究取得了大量成效。在文獻(xiàn)[1]中，基于聚類(lèi)分析思想將數(shù)據(jù)的重復(fù)問(wèn)題映射為聚類(lèi)分析問(wèn)題，進(jìn)而就可以數(shù)據(jù)的相似性問(wèn)題；針對(duì)設(shè)備狀態(tài)信息噪聲的數(shù)據(jù)，提出了基于時(shí)間序列分析的數(shù)據(jù)清洗方法；而基于相似性測(cè)度的描述方法在判定記錄的一致性方面也有一定表現(xiàn)，例如在文獻(xiàn)[1]的文獻(xiàn)綜述中，針對(duì)模式匹配問(wèn)題，提出了基于實(shí)體解析的模式匹配算法。上述方法在處理低維度的小數(shù)據(jù)集時(shí)具有良好的性能，但面對(duì)維度高、規(guī)模大的數(shù)據(jù)時(shí)，其檢測(cè)性能大幅度降低，難以有效完成海量高維電力數(shù)據(jù)的臟數(shù)據(jù)檢測(cè)。

因此，該文在將數(shù)據(jù)記錄轉(zhuǎn)換為對(duì)應(yīng)指紋的基礎(chǔ)上，設(shè)計(jì)了基于圖論的指紋轉(zhuǎn)換策略，并結(jié)合普聚類(lèi)實(shí)現(xiàn)臟數(shù)據(jù)的智能檢測(cè)；此外，鑒于Spark計(jì)算資源配置的合理性和其數(shù)據(jù)處理的優(yōu)越性，提出了基于Spark和圖論的電力臟數(shù)據(jù)智能動(dòng)態(tài)檢測(cè)方法，有效提高了大規(guī)模電力應(yīng)用數(shù)據(jù)中臟數(shù)據(jù)檢測(cè)的準(zhǔn)確性。

1 檢測(cè)原理

1.1 Simhash算法

Simhash算法[1]將高維數(shù)據(jù)映射為對(duì)應(yīng)的低維二進(jìn)制串(下文簡(jiǎn)稱(chēng)“指紋”)，從而實(shí)現(xiàn)了數(shù)據(jù)與低維度二進(jìn)制串間的映射，算法的功能具體描述為如下步驟：1） 特征關(guān)鍵詞key的提取。即對(duì)待檢測(cè)的數(shù)據(jù)進(jìn)行關(guān)鍵詞key的提取。2） 初始化向量。將Ψ維的向量v和s初始化為0。3） 計(jì)算簽名?；趥鹘y(tǒng)的標(biāo)準(zhǔn)Hash算法（例如MD5算法等）計(jì)算關(guān)鍵詞key的簽名b(Ψ位)。4） 判斷簽名正負(fù)位。即在b中，如果第i位是+1，則在v中的對(duì)應(yīng)位置的數(shù)就設(shè)為+1，反之為-1。5） 關(guān)鍵詞簽名計(jì)算完畢之后，在v中，如果第i位的數(shù)字大于0，則s的對(duì)應(yīng)位置的數(shù)就設(shè)為+1，反之為0。6） 輸出s即為數(shù)據(jù)對(duì)應(yīng)的指紋。

1.2 基于圖論的指紋轉(zhuǎn)換策略

為了實(shí)現(xiàn)指紋在極坐標(biāo)下的動(dòng)態(tài)映射，研究人員提出了基于圖論的指紋轉(zhuǎn)換策略。首先，將指紋與十進(jìn)制數(shù)據(jù)進(jìn)行轉(zhuǎn)換，即將S=（si）映射為di（十進(jìn)制數(shù)）；其次，將di映射為二維坐標(biāo)下的數(shù)據(jù)點(diǎn)vi（極坐標(biāo)），并且有坐標(biāo)vi（ρi，θi）=（di，di）；再次，定義點(diǎn)與點(diǎn)之間的路徑邊Ei，j=│di，di│；最后，得到由指紋構(gòu)建的圖G=（V，E），從而將指紋動(dòng)態(tài)地映射到極坐標(biāo)下，具體步驟如下。

輸入：S=（si），即輸入指紋集

輸出：極坐標(biāo)下的圖G=（V，E）。

步驟1：For each siin S do 。

步驟2：di=convertTodec（si） then 。

步驟3：vi=Creat（（ρi，θi）=（di，di））。

步驟4：Ei，j=│di，di│。

步驟5：Update。

步驟6：if update=1 then goto步驟2。

Else

end for

步驟7：putout（G）。

該策略動(dòng)態(tài)地實(shí)現(xiàn)了指紋在極坐標(biāo)下的映射，最后輸出的圖中，不同節(jié)點(diǎn)就代表不同的指紋。

1.3 基于普聚類(lèi)的臟數(shù)據(jù)智能識(shí)別模型

鑒于普聚類(lèi)算法在處理高維數(shù)據(jù)中具有的優(yōu)勢(shì)，為了提高臟數(shù)據(jù)的檢測(cè)精度，該文在指紋轉(zhuǎn)換策略的基礎(chǔ)上引入了普聚類(lèi)算法，從而實(shí)現(xiàn)臟數(shù)據(jù)的智能識(shí)別，其數(shù)據(jù)模型如下。

1.3.1 無(wú)向權(quán)重圖和相似矩陣模型構(gòu)建

定義點(diǎn)vi（ρi，θi）=（di，di）和點(diǎn)vj（ρj，θj）=（dj，dj）之間的權(quán)重wi，j=Ei，j=│di-dj│，wi，j=wj，i，如果點(diǎn)vi和vj之間存在邊，則wi，j=Ei，j=│di-dj│＞0，反之，wi，j=Ei，j=│didj│=0。對(duì)任意點(diǎn)vi的度di為與之相連的所有邊的權(quán)重之和，其表達(dá)式如公式（1）所示。

定義度矩陣Dn×n，是個(gè)對(duì)角矩陣，其主對(duì)角線的值對(duì)應(yīng)第i行的第i個(gè)點(diǎn)的度數(shù)，定義如公式（2）所示。

定義鄰接矩陣Wn×n=[wi，j]，引入全連接法構(gòu)建鄰接矩陣Wn×n，此時(shí)鄰接矩陣即為相似矩陣，其表達(dá)式如公式（3）所示。

式中：xi和yj為2個(gè)頂點(diǎn)；wi，j和si，j為2個(gè)頂點(diǎn)xi和yj間的相似度；σ為2個(gè)頂點(diǎn)xi和yj間的方差。

1.3.2 拉普拉斯矩陣和無(wú)向圖切圖模型構(gòu)建

拉普拉斯矩陣L=D-W（D為度矩陣，W為鄰接矩陣）。為了避免出現(xiàn)無(wú)向圖分割均勻的現(xiàn)象，該文采用RatioCut切圖，對(duì)每個(gè)切圖都可以同時(shí)兼顧最小化cut（A1，A2，...Ak）和最大化子圖點(diǎn)的個(gè)數(shù)，其表達(dá)式如公式（4）所示。

基于拉普拉斯矩陣的特性，可以推導(dǎo)出新的方程，如公式（6）所示。

式中：hi為頂點(diǎn)i指示向量；T為向量的轉(zhuǎn)置。

由公式（5）和公式（6），可以得到新的方程，如公式（7）所示。

由公式（7）可知，子圖i的RatioCut對(duì)應(yīng)于對(duì)于k個(gè)子圖，其RatioCut函數(shù)表達(dá)式如公式（8）所示。

式中：H為hi的和，即指示向量的并集；tr（HTLH）為矩陣的跡。

由公式（8）可知，最小化tr（HTLH）即為RatioCut切圖的過(guò)程。

1.3.3 基于改進(jìn)的普聚類(lèi)臟數(shù)據(jù)智能識(shí)別算法

基于改進(jìn)的普聚類(lèi)臟數(shù)據(jù)智能識(shí)別算法的步驟如下：1） 輸入：樣本集S={s1，s2，…，sn}。2） 簇劃分C={c1，c2，…，cn}。3） 利用基于圖論的指紋轉(zhuǎn)換策略，構(gòu)建S={s1，s2，…，sn}的無(wú)向權(quán)重圖并生成相似矩陣S。4）構(gòu)建鄰接矩陣W，并生成度矩陣D。5）計(jì)算拉普拉斯矩陣L。6）構(gòu)建標(biāo)準(zhǔn)化拉普拉斯矩陣D-1/2.L.D-1/2。7）計(jì)算D-1/2.L.D-1/2最小的k個(gè)特征值的對(duì)應(yīng)特征向量fi...fk。8）基于行對(duì)fi...fk組成的矩陣標(biāo)準(zhǔn)化，生成特征矩陣F（n×k）。9）對(duì)F（n×k）中的k維樣本，通過(guò)DBscan算法并利用RatioCut數(shù)學(xué)模型，輸出簇劃分C{cm}，m=（1，2，3，...，m），表示聚類(lèi)維數(shù)。

1.4 基于Spark的臟數(shù)據(jù)檢測(cè)策略

1.4.1 Spark計(jì)算框架

Spark框架是基于內(nèi)存的計(jì)算分布式平臺(tái)，彈性分布式數(shù)據(jù)集（RDD）是其核心。Spark將各彈性分布式數(shù)據(jù)集的依賴串聯(lián)起來(lái)，以此來(lái)構(gòu)造有向無(wú)環(huán)圖，并在RDD上執(zhí)行Action函數(shù)操作，將有向無(wú)環(huán)圖作為作業(yè)提交給Spark執(zhí)行。

基于RDD的性質(zhì)，該文結(jié)合基于普聚類(lèi)的臟數(shù)據(jù)智能識(shí)別模型（DDI）與Spark計(jì)算平臺(tái)，提出了基于Spark的臟數(shù)據(jù)檢測(cè)算法（SP-MATCH-new），解決了大規(guī)模電力行業(yè)應(yīng)用數(shù)據(jù)一致性清理的問(wèn)題，實(shí)現(xiàn)了對(duì)臟數(shù)據(jù)的有效處理和檢測(cè)。

1.4.2 實(shí)現(xiàn)基于Spark的臟數(shù)據(jù)檢測(cè)算法SP-MATCHnew

為了應(yīng)對(duì)海量、高維化電力數(shù)據(jù)帶來(lái)的瓶頸，該文基于迭代的RDD和普聚類(lèi)算法設(shè)計(jì)了適用于海量電力數(shù)據(jù)中的臟數(shù)據(jù)的檢測(cè)策略。

對(duì)關(guān)系表Ek，k∈R,行號(hào)記為ID，表中第i行j列的屬性值為Ai,j且Ai,j∈Ai；檢測(cè)Ek中臟數(shù)據(jù)，SP-MATCH-new算法的描述如下：1） 輸入樣本集S={s1，s2，…，sn}。2）輸出簇劃分C={c1，c2，…，cn}。3） 調(diào)用SparkContext.textFile()方法和RDD.Cache()方法來(lái)讀取樣本S={s1，s2，…，sn}，并以RDD加載到內(nèi)存。4） 利用Simhash并輸出數(shù)據(jù)關(guān)鍵字元組的指紋RDD，并按格式＜key=IDi，value=si＞的形式存儲(chǔ)。5） 執(zhí)行Map，將指紋映射為新的鍵值對(duì)并以格式＜key=IDi，value=si＞的形式存儲(chǔ)6） Executor執(zhí)行Reduce操作,輸入Map的結(jié)果＜key=IDi，value=si＞。7） 以si為鍵進(jìn)行歸并。8） 調(diào)用相似矩陣生成方法，生成相似矩陣RDD鄰接矩陣RDD和度矩陣RDD。9） 調(diào)用拉普拉斯數(shù)學(xué)模型，生成拉普拉斯矩陣RDD并進(jìn)一步生成標(biāo)準(zhǔn)化拉普拉斯矩陣RDD。10） 對(duì)標(biāo)準(zhǔn)化拉普拉斯矩陣RDD調(diào)用數(shù)據(jù)步驟8）中的RDD，生成特征向量RDD。11） 將特征向量RDD緩存到內(nèi)存。12）DBscan.RatioCut（特征向量RDD）,生成DBscan.RatioCutRDD。13） 執(zhí)行Action，調(diào)用saveAsTextFile方法，并以＜key=si/valueslist=（ID1，…/…）＞的形式將簇劃分C{cm}，m=（1，2，3...，m）輸出；在輸出的結(jié)果中，通過(guò)對(duì)異常離散點(diǎn)的判斷，完成臟數(shù)據(jù)的識(shí)別。

2 實(shí)例分析

為了驗(yàn)證該方法的有效性和高效性，在I620-G20曙光服務(wù)器（16臺(tái)服務(wù)器節(jié)點(diǎn)）中搭建Spark平臺(tái)環(huán)境，配置見(jiàn)表1。

表1 實(shí)驗(yàn)環(huán)境配置

實(shí)驗(yàn)數(shù)據(jù)是用戶用電的負(fù)荷數(shù)據(jù)，來(lái)自電力企業(yè)的應(yīng)用系統(tǒng)。在實(shí)驗(yàn)中，采用文獻(xiàn)[1]中的提取指紋長(zhǎng)度和特征關(guān)鍵詞的方法進(jìn)行試驗(yàn)；標(biāo)準(zhǔn)哈希函數(shù)采用MD5算法。

2.1 精確性和穩(wěn)定性的分析

將該算法的檢測(cè)結(jié)果與文獻(xiàn)[2]中性能最好的COSY算法進(jìn)行對(duì)比。采用記憶率（R）、準(zhǔn)確率（P）和F1-score（F1）作為運(yùn)行效果的評(píng)價(jià)標(biāo)準(zhǔn)， 且F1與算法性能呈正相關(guān)；實(shí)驗(yàn)結(jié)果見(jiàn)表2。由表2可知SP-MATCH-new算法的平均檢測(cè)精度略高，但其平均召回率和F1相對(duì)遠(yuǎn)大于COSY，由此可見(jiàn)，該算法具有更好的檢測(cè)效果。

表2 SP-MATCH-new算法檢測(cè)精度

檢驗(yàn)數(shù)據(jù)規(guī)模對(duì)算法有關(guān)指標(biāo)敏感度影響的實(shí)驗(yàn)結(jié)果見(jiàn)表3。

表3 SP-MATCH-new指標(biāo)檢測(cè)

由表3可知，當(dāng)數(shù)據(jù)以10倍規(guī)模遞增到1000 GB時(shí)，算法的檢測(cè)精度（P） 和平衡性（F1）在6%內(nèi)浮動(dòng)，召回率（R） 在5%內(nèi)浮動(dòng)。其平均P為78%，平均R為96%，平均F1為84% 。隨著數(shù)據(jù)規(guī)模的快速增加，SP-MATCH-new算法檢測(cè)的P、R和F1，稍微降低P、F1的值，使它們的值在6%內(nèi)浮動(dòng)、R在5%內(nèi)浮動(dòng)，但算法受到的影響相對(duì)較小，能滿足巨增數(shù)據(jù)體量的性能要求，表現(xiàn)出較高的穩(wěn)定性。

2.2 算法效率分析

實(shí)驗(yàn)將該算法與基于MapReduce的算法的執(zhí)行時(shí)間進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果見(jiàn)表4。由表4可知，相同條件下，SPMATCH-new算法比基于MapReduce的算法的執(zhí)行效率提高了約79.2%；這是因?yàn)樵赟P-MATCH-new算法中，數(shù)據(jù)流的運(yùn)行模式采用memory-to-memory的模式，該模式中只有在構(gòu)建分布式彈性數(shù)據(jù)集的時(shí)候，數(shù)據(jù)I/0操作才涉及磁盤(pán)input/output流的開(kāi)銷(xiāo)，作業(yè)處理結(jié)構(gòu)比基于MapReduce的算法更加高效。因此，SP-MATCH-new具有更高的運(yùn)行效率和執(zhí)行效果。

表4 SP-MATCH-new算法的執(zhí)行效率

3 結(jié)語(yǔ)

針對(duì)單機(jī)環(huán)境下的計(jì)算資源和基于MapReduce的算法存在難以有效解決海量、高維化電力數(shù)據(jù)中臟數(shù)據(jù)檢測(cè)的問(wèn)題，研究人員設(shè)計(jì)了圖聚類(lèi)分析的臟數(shù)據(jù)檢測(cè)策略，并提出了基于Spark和圖聚類(lèi)分析的臟數(shù)據(jù)檢測(cè)算法，該算法有效解決了海量、高維化電力數(shù)據(jù)的臟數(shù)據(jù)檢測(cè)和計(jì)算資源的合理利用問(wèn)題，其算法高效、穩(wěn)定，具有良好的適用性。研究人員需要繼續(xù)研究如何提高算法的檢測(cè)精度等尋優(yōu)策略，使其更好地應(yīng)用于海量電力數(shù)據(jù)的處理中，為獲取更好的電力管控決策知識(shí)提供優(yōu)質(zhì)的數(shù)據(jù)支持。