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

（廣西電力有限責(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ù)來支撐電力系統(tǒng)運(yùn)行的決策管控和決策知識(shí)，電力行業(yè)數(shù)據(jù)中的臟數(shù)據(jù)檢測是其基礎(chǔ)和重要保障，對(duì)電力系統(tǒng)穩(wěn)定運(yùn)行管控具有重要支撐意義。隨著數(shù)字化和信息化在工業(yè)和能源等行業(yè)中的推進(jìn)，應(yīng)用數(shù)據(jù)呈指數(shù)級(jí)不斷增長，每年應(yīng)用數(shù)據(jù)的體量以TB數(shù)量級(jí)在增長。體量的不斷增長在一定程度上使得數(shù)據(jù)的維度和密度在發(fā)生巨大變化，并且表現(xiàn)出了價(jià)值密度低的特點(diǎn)，并且摻雜了高比例的臟數(shù)據(jù)，這給傳統(tǒng)的臟數(shù)據(jù)檢測方法造成了困難。因此，研究人員提出了基于Spark和圖論的臟數(shù)據(jù)智能動(dòng)態(tài)檢測方法。

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

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

1 檢測原理

1.1 Simhash算法

Simhash算法[1]將高維數(shù)據(jù)映射為對(duì)應(yīng)的低維二進(jìn)制串(下文簡稱“指紋”)，從而實(shí)現(xiàn)了數(shù)據(jù)與低維度二進(jìn)制串間的映射，算法的功能具體描述為如下步驟：1） 特征關(guān)鍵詞key的提取。即對(duì)待檢測的數(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 基于普聚類的臟數(shù)據(jù)智能識(shí)別模型

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

1.3.1 無向權(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 拉普拉斯矩陣和無向圖切圖模型構(gòu)建

拉普拉斯矩陣L=D-W（D為度矩陣，W為鄰接矩陣）。為了避免出現(xiàn)無向圖分割均勻的現(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切圖的過程。

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

基于改進(jìn)的普聚類臟數(shù)據(jù)智能識(shí)別算法的步驟如下：1） 輸入：樣本集S={s1，s2，…，sn}。2） 簇劃分C={c1，c2，…，cn}。3） 利用基于圖論的指紋轉(zhuǎn)換策略，構(gòu)建S={s1，s2，…，sn}的無向權(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維樣本，通過DBscan算法并利用RatioCut數(shù)學(xué)模型，輸出簇劃分C{cm}，m=（1，2，3，...，m），表示聚類維數(shù)。

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

1.4.1 Spark計(jì)算框架

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

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

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

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

對(duì)關(guān)系表Ek，k∈R,行號(hào)記為ID，表中第i行j列的屬性值為Ai,j且Ai,j∈Ai；檢測Ek中臟數(shù)據(jù)，SP-MATCH-new算法的描述如下：1） 輸入樣本集S={s1，s2，…，sn}。2）輸出簇劃分C={c1，c2，…，cn}。3） 調(diào)用SparkContext.textFile()方法和RDD.Cache()方法來讀取樣本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é)果中，通過對(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)境，配置見表1。

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

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

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

將該算法的檢測結(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é)果見表2。由表2可知SP-MATCH-new算法的平均檢測精度略高，但其平均召回率和F1相對(duì)遠(yuǎn)大于COSY，由此可見，該算法具有更好的檢測效果。

表2 SP-MATCH-new算法檢測精度

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

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

由表3可知，當(dāng)數(shù)據(jù)以10倍規(guī)模遞增到1000 GB時(shí)，算法的檢測精度（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算法檢測的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é)果見表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操作才涉及磁盤input/output流的開銷，作業(yè)處理結(jié)構(gòu)比基于MapReduce的算法更加高效。因此，SP-MATCH-new具有更高的運(yùn)行效率和執(zhí)行效果。

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

3 結(jié)語

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