基于Spark和圖論的電力臟數據智能動態檢測方法

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

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

0 引言

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

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

因此，該文在將數據記錄轉換為對應指紋的基礎上，設計了基于圖論的指紋轉換策略，并結合普聚類實現臟數據的智能檢測；此外，鑒于Spark計算資源配置的合理性和其數據處理的優越性，提出了基于Spark和圖論的電力臟數據智能動態檢測方法，有效提高了大規模電力應用數據中臟數據檢測的準確性。

1 檢測原理

1.1 Simhash算法

Simhash算法[1]將高維數據映射為對應的低維二進制串(下文簡稱“指紋”)，從而實現了數據與低維度二進制串間的映射，算法的功能具體描述為如下步驟：1） 特征關鍵詞key的提取。即對待檢測的數據進行關鍵詞key的提取。2） 初始化向量。將Ψ維的向量v和s初始化為0。3） 計算簽名。基于傳統的標準Hash算法（例如MD5算法等）計算關鍵詞key的簽名b(Ψ位)。4） 判斷簽名正負位。即在b中，如果第i位是+1，則在v中的對應位置的數就設為+1，反之為-1。5） 關鍵詞簽名計算完畢之后，在v中，如果第i位的數字大于0，則s的對應位置的數就設為+1，反之為0。6） 輸出s即為數據對應的指紋。

1.2 基于圖論的指紋轉換策略

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

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

輸出：極坐標下的圖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）。

該策略動態地實現了指紋在極坐標下的映射，最后輸出的圖中，不同節點就代表不同的指紋。

1.3 基于普聚類的臟數據智能識別模型

鑒于普聚類算法在處理高維數據中具有的優勢，為了提高臟數據的檢測精度，該文在指紋轉換策略的基礎上引入了普聚類算法，從而實現臟數據的智能識別，其數據模型如下。

1.3.1 無向權重圖和相似矩陣模型構建

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

定義度矩陣Dn×n，是個對角矩陣，其主對角線的值對應第i行的第i個點的度數，定義如公式（2）所示。

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

式中：xi和yj為2個頂點；wi，j和si，j為2個頂點xi和yj間的相似度；σ為2個頂點xi和yj間的方差。

1.3.2 拉普拉斯矩陣和無向圖切圖模型構建

拉普拉斯矩陣L=D-W（D為度矩陣，W為鄰接矩陣）。為了避免出現無向圖分割均勻的現象，該文采用RatioCut切圖，對每個切圖都可以同時兼顧最小化cut（A1，A2，...Ak）和最大化子圖點的個數，其表達式如公式（4）所示。

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

式中：hi為頂點i指示向量；T為向量的轉置。

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

由公式（7）可知，子圖i的RatioCut對應于對于k個子圖，其RatioCut函數表達式如公式（8）所示。

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

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

1.3.3 基于改進的普聚類臟數據智能識別算法

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

1.4 基于Spark的臟數據檢測策略

1.4.1 Spark計算框架

Spark框架是基于內存的計算分布式平臺，彈性分布式數據集（RDD）是其核心。Spark將各彈性分布式數據集的依賴串聯起來，以此來構造有向無環圖，并在RDD上執行Action函數操作，將有向無環圖作為作業提交給Spark執行。

基于RDD的性質，該文結合基于普聚類的臟數據智能識別模型（DDI）與Spark計算平臺，提出了基于Spark的臟數據檢測算法（SP-MATCH-new），解決了大規模電力行業應用數據一致性清理的問題，實現了對臟數據的有效處理和檢測。

1.4.2 實現基于Spark的臟數據檢測算法SP-MATCHnew

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

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

2 實例分析

為了驗證該方法的有效性和高效性，在I620-G20曙光服務器（16臺服務器節點）中搭建Spark平臺環境，配置見表1。

表1 實驗環境配置

實驗數據是用戶用電的負荷數據，來自電力企業的應用系統。在實驗中，采用文獻[1]中的提取指紋長度和特征關鍵詞的方法進行試驗；標準哈希函數采用MD5算法。

2.1 精確性和穩定性的分析

將該算法的檢測結果與文獻[2]中性能最好的COSY算法進行對比。采用記憶率（R）、準確率（P）和F1-score（F1）作為運行效果的評價標準， 且F1與算法性能呈正相關；實驗結果見表2。由表2可知SP-MATCH-new算法的平均檢測精度略高，但其平均召回率和F1相對遠大于COSY，由此可見，該算法具有更好的檢測效果。

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

檢驗數據規模對算法有關指標敏感度影響的實驗結果見表3。

表3 SP-MATCH-new指標檢測

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

2.2 算法效率分析

實驗將該算法與基于MapReduce的算法的執行時間進行對比，實驗結果見表4。由表4可知，相同條件下，SPMATCH-new算法比基于MapReduce的算法的執行效率提高了約79.2%；這是因為在SP-MATCH-new算法中，數據流的運行模式采用memory-to-memory的模式，該模式中只有在構建分布式彈性數據集的時候，數據I/0操作才涉及磁盤input/output流的開銷，作業處理結構比基于MapReduce的算法更加高效。因此，SP-MATCH-new具有更高的運行效率和執行效果。

表4 SP-MATCH-new算法的執行效率

3 結語

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