基于云計算和量子粒子群算法的電力負荷曲線聚類算法研究

張少敏，趙 碩，王保義

（華北電力大學控制與計算機工程學院，河北 保定 071003）

0 引言

電力系統負荷分類就是利用各種聚類算法對選取的負荷數據樣本進行分類，從而挖掘不同類型負荷的特性，輔助電力系統決策。隨著電網智能化程度的加深，一線城市在用電高峰期間，面臨數百萬條記錄的電力數據采集規模，一年的數據存儲規模將從目前的GB級增長到TB級，甚至PB級[1]。同時，為了保證精細化、準確化控制，數據維度也從幾十向上百過渡。近年來，許多的學者將數據挖掘算法[2-3]、群體智能算法[4]和機器學習算法[5]引入到電力負荷預測中，這些改進算法幾乎都是通過大量迭代方式達到算法優化的目的，算法復雜度相當高。但在海量多維的智能電網數據上運行串行算法時將遭遇單機計算資源不足的瓶頸。

云計算技術在2003年由Google推出后，就作為一種新興的商業計算模型得到了人們的廣泛關注，智能電網的云存儲模型也在不斷發展。但針對智能電網云存儲中的海量電力數據的聚類分析算法研究卻很少。Prahastono等人[6]利用模糊C均值聚類算法，采用印度尼西亞的真實電力數據進行負荷特性分類研究。何曉峰等人[7]將PSO粒子群算法引入到模糊C均值聚類算法中，在一定程度彌補了模糊C均值聚類算法的不足，但PSO算法的微粒飛行速度難以控制，容易飛躍最優解，導致無法收斂于全局最優。

本文圍繞上述問題，將量子粒子群群體智能算法引入到傳統模糊C均值聚類算法中，提出了一種基于云計算的電力負荷曲線聚類的并行量子粒子群優化模糊C均值聚類算法，充分利用QPSO較強的全局搜索能力，克服了模糊C均值聚類算法的缺陷；并利用云計算MapReduce框架對聚類算法進行并行化改進，解決聚類海量高維電力負荷數據時單機運算資源不足的瓶頸，最后，在實驗室搭建云集群上測試改進算法的并行性和聚類質量，并驗證改進算法在實際應用中的性能。

1 模糊C均值聚類算法

1.1 算法描述

模糊C均值聚類算法（Fuzzy C-Means，FCM）[8]，按數據對象間的相似度，將整個數據集合分為C個模糊聚簇中，使得類內加權誤差平方和達到最小值。FCM聚類算法采用模糊劃分，對每個數據對象采用[0,1]之間的隸屬度表示其屬于各個聚簇的程度。根據標準化規定，一個數據對象對于C個聚簇中心的隸屬度之和等于1，即

FCM聚類算法的目標函數為

其中：μik∈[0,1]為第k個數據對象屬于第i個聚類中心的程度；Pi為聚類i的聚類中心；m∈[0,2]為加權指數；dik為第i個聚簇中心與第k個數據對象的歐氏距離(Euclidean Distance)，公式為

根據FCM聚類準則構造如下Lagrangian函數

根據Kuhn-Tucker定理對輸入變量求導，求得Jm(U,P)取最小值時的必要條件為

1.2 FCM算法的不足

從FCM算法描述中可以發現，式（5）和式（6）的計算量相當大，而針對海量、高維的數據，單機運行FCM算法進行電力負荷聚類分析需要很高的內存空間，運算效率較低，不能滿足電力控制實時性要求。運用云計算的MapReduce對算法進行并行化改進，以解決單機運算資源不足的問題。

此外，FCM算法是一種局部搜索算法，其迭代序列必收斂到目標函數的某個極小值或鞍點，易陷入局部最小值，影響最終聚類質量。為此，本文提出一種并行量子粒子群模糊C均值聚類算法(Parallel Quantum-Behaved Particle Swarm Optimization Fuzzy C-Means，P-QPSO-FCM)。

2 基于云計算的P-QPSO-FCM算法設計

2.1 量子粒子群算法

粒子群算法（Particle Swarm Optimization，簡稱PSO）是基于種群的進化搜索技術，但其不能保證算法的全局收斂，從基本粒子群算法模型可以得出，粒子的飛行速度相當于搜索步長，全局收斂性受其速度大小直接影響[5]。針對PSO算法的收斂性問題，Sun等人從量子學的角度提出了具有量子行為的粒子群算法（Quantum-Behaved Particle Swarm Optimization，QPSO）。其將每個粒子的飛行速度由粒子的飛行最優值和群體的飛行最優值動態調整。QPSO算法不僅參數少，并且搜索能力上優于PSO算法，并且收斂性有了很大的改進。QPSO算法中的粒子群將按照以下三個公式進行動態調整位置。

其中：mbest為粒子群各個粒子最優位置的中間位置；pgbest為粒子群全局最優位置；pid為pid和pgbest的隨機加權點。α是QPSO的收縮擴張系數，隨著式（10）線性變化。

其中：α1和α2為α的初始值和最終值；t是當前的迭代次數；MAXITIER是初始設定的最大迭代次數。通過線性改變α值，本文將范圍設置為1.2到0.7，此時QPSO可以實現比較好的性能。

2.2 FCM算法改進思想

FCM算法是一種基于梯度下降的局部搜索算法，易陷入局部最小，且隨機選取初始聚類中心，不同的初始聚類中心導致不同的聚類結果。QPSO具有全局搜索能力，不易陷入局部最小。因此本文QPSO算法代替FCM的迭代過程，防止FCM陷入局部最優，以獲得比較好的整體聚類質量，而且可減少算法迭代次數，節省計算資源，提高聚類質量。

2.3 P-QPSO-FCM算法設計

2.3.1 數據預處理

首先對各維數據進行規范化，映射到[0,1]內。

2.3.2 粒子編碼和適應度函數設計

在QPSO中，每個粒子都是由C個聚簇中心組成，數據對象的維度為D，因此每個粒子表示為C×D維向量，粒子位置Xp構造如下。

其中，cpi為第p個粒子的第i個聚簇中心。

定義粒子群適應度函數為目標函數Jm(U,P)，如式（2）所示。

2.3.3 P-QPSO-FCM算法執行步驟

P-QPSO-FCM算法具體步驟如下。

（1）初始化聚簇數目C、數據對象維度D、量子粒子群規模N和最大迭代次數runtimes。

（2）在樣本數據集上運行一次FCM算法，將獲取的聚類中心按粒子編碼規則構造粒子個體X1，即為第一個粒子位置；然后，利用獲取的聚類中心按歐氏距離完成一次粗聚類，得到C個粗聚簇：……，其中。

（3）從每個粗聚簇中隨機取出一個數據對象，獲取C個數據對象，按粒子編碼規則構造粒子個體X2；迭代上述步驟，直到獲取N個粒子個體。

（4）初始化粒子群的各個粒子局部最優位置pbest和全局最優位置pgbest。

（5）對每個粒子按照適應度函數Jm(U,P)計算適應度，并由每個粒子的適應度值按式（12）、式（13）更新粒子群的pbest、pgbest，根據式（7）獲取各個粒子最優位置的中間位置mbest。

（6）根據式（8）～式（10）得到新一代粒子個體xid。

（8）全局最優位置對應的聚類中心作為FCM算法的初始聚類中心，執行FCM算法。

這里，在確定QPSO的初始N個粒子個體位置時進行了一定的算法優化，傳統粒子群算法的初始粒子個體位置是隨機生成的，本文提出的改進算法則是通過一次FCM聚類后，分別從生成的C個粗聚簇中隨機選取數據集構造粒子個體，在不增加算法復雜度的前提下，所選取的N個粒子個體位置在一定程度上代表了該樣本數據集的真實分布，從而降低P-QPSO-FCM算法的迭代次數。

2.4 基于MapReduce的P-QPSO-FCM算法設計

在Hadoop平臺上實現P-QPSO-FCM算法需要四個階段，分別用四個MapReduce任務實現。算法分布式流程圖如圖1 所示，其中，Job2和Job3為簡化的分布式流程，實際分布式流程與圖中Job1和Job2相似。

圖1 P-QPSO-FCM分布式運行流程圖Fig.1 Flow chart of P-QPSO-FCM algorithm

3 實驗與算例分析

3.1 實驗準備

實驗室搭建的Hadoop平臺由9個節點組成，每個節點機器配置為Intel(R)Core(TM)i5-2400 4-core CPU@2.60 GHz，4 GB RAM，網絡帶寬為100 Mbit/s Hadoop版本為0.20.2，HBase版本為0.90.6。

在進行map函數操作之前，底層框架需要對輸入進行分片，以便多個map同時工作，而分片默認是64 M。由于真實負荷數據有限，實驗將首先測試QPSO-FCM算法性能，然后通過人工擴展真實數據集，測試P-QPSO-FCM并行算法的并行性能。

3.2 測試數據集描述

所用數據為國際通用測試數據庫UCI[9]上的Wine、Iris和Breast-Cancer測試數據集。其次，進行電力系統算例分析。選用2001年歐洲智能技術網絡(EUNITE)組織的中期電力負荷預測競賽提供的某地區97、98年真實負荷數據作為算例分析數據集，在此數據集上運行P-QPSO-FCM算法以獲取相似日曲線，并驗證該算法與FCM算法相比具有性能優越性。

3.3 聚類質量對比實驗

比較FCM算法、自適應模糊聚類 (Adaptive FCM,AFCM)[10]與提出的QPSO-FCM算法的聚類質量。AFCM中引入了自適應度向量 W 和自適應指數 p，文獻[10]經過大量實驗表明AFCM可以得到更好的聚類質量。FCM算法隨機選取C個數據對象作為初始聚類中心，所以聚類質量波動較大。

采用適應度函數值和聚類正確率來測試聚類質量，適應性函數值越小、聚類正確率越高則聚類質量越高，適應度函數如式（2）所示。為了保證實驗結果的客觀性，三種算法各運行30次，并進行歸一化處理，實驗結果如表1所示。

從實驗結果看出，QPSO-FCM算法與另外兩種算法相比，不僅正確率高于后者5%到15%，且適應性函數值更小，聚類質量更好，陷入局部最優的可能性更小。因此該算法具有一定的優越性。

表1 FCM算法、AFCM算法與P-QPSO-FCM算法聚類質量對比Table 1 Comparison of the clustering quality of the algorithm FCM, AFCM and P-QPSO-FCM

3.4 算例分析

3.4.1 目標函數值變化情況

在電力負荷樣本數據分別運行FCM算法和QPSO-FCM算法獲取每次迭代的目標函數值，30次實驗取其平均值作為最終實驗結果。目標函數值與迭代次數變化關系如圖2所示。

圖2 目標函數值與迭代次數變化關系Fig.2 Objective function value and the number of iterations

從實驗結果看出，FCM算法運行時隨著迭代數的增加，目標函數值逐漸平滑減小，沒有出現反復情形，這說明FCM算法在樣本數據集上執行聚類操作有可能陷入局部最優，影響最終聚類效果，而QPSO-FCM算法在聚類過程中的目標函數值雖然總體趨勢是減小，但隨著聚類迭代次數的增加，其目標函數值也在不斷變化，不是梯度下降的，說明該算法不易陷入局部最優，保證了最終的聚類質量。

本文提出的改進算法正是利用了量子粒子群算法的全局搜索能力，結合FCM的較強的局部搜索能力，且人工設定參數較少，來提高算法聚類質量。

3.4.2 P-QPSO-FCM并行性能

采用加速比（speedup）來測試P-QPSO-FCM算法的并行化性能。加速比是衡量并行系統或程序并行化的性能和效果的指標，如式（14）所示。

因EUNITE組織提供的兩年730條48維電力負荷數據量過小，無法表現出P-QPSO-FCM算法并行性能。故本實驗首先將EUNITE組織所提供的真實電力負荷數據集人工擴充為0.5 G、1 G、2 G等3個不同大小的數據集，分別在集群節點個數為1、3、5、9的云集群上運行算法，分別記錄算法執行時間，以計算加速比，實驗結果如圖3所示。

圖3 加速比與集群節點數關系圖Fig.3 Speedup in different sizes of datasets

云集群的節點數為9，當云集群節點數量達到一定數量時，因算法執行時間相當多的消耗在了節點間的網絡傳輸等額外消耗上，所以加速比將隨著云集群節點的增加而變差。但是從有限的節點上可以看出，隨著數據量的增加，P-QPSO-FCM聚類算法的加速比依然幾乎線性增加，且與較小數據集的加速比折線相差不大，說明算法的并行性能較好，且HBase的讀寫性能沒有成為算法的性能瓶頸。

3.4.3 提取日負荷特征曲線

目前，許多文獻[11]采用相似日法作為輔助策略來改善負荷預測精度。為了驗證提出的算法的有效性，本文將其應用于負荷預測樣本數據的預處理。

利用文獻[12]中的分離系數、分離熵以及有效性評價系數來評價FCM算法與本文提出的聚類算法在真實電力負荷的聚類效果，并確定樣本的聚類個數取值為10。實驗結果表2所示。

表2 評價指標Table 2 Evaluation result

從表4可以看出，本文的算法在三項指標均優于FCM算法。在云平臺上執行P-QPSO-FCM算法，即按照平均負荷變化規律相似進行聚類，形成K條負荷水平趨勢相似日曲線，實驗結果如圖4所示。

圖4 日負荷特征曲線Fig.4 Load characteristic curve

本文集群節點數為9個，并行性能測試采用的數據量最高是2 G。在實際應用中，針對實際的存儲運算數據量，云計算集群節點數可達到數以千計、萬計，完全可以應對海量、高維數據運算時對資源的要求?；谠朴嬎愕腜-QPSO-FCM聚類算法，不僅能滿足當電力負荷數據量達到TB、PB級別時數據的存儲、運算要求；而且經過上述實驗以及多種評價指標對比表明：相對基于FCM聚類算法的選取相似日的預測方式，本文提出的聚類算法在一定程度上提高了聚類準確度，進而提高了負荷預測精度。

4 結語

本文提出了基于云計算的電力負荷曲線聚類的并行量子粒子群優化模糊C均值聚類算法，通過電力負荷樣本數據的算例分析和相關測試，表明該算法顯著提高了聚類質量和效率，且并行化性能良好。

[1] 袁鐵江, 袁建黨, 晁勤, 等.電力系統中長期負荷預測綜合模型研究[J].電力系統保護與控制, 2012, 40(14):143-146, 151.

YUAN Tie-jiang, YUAN Jian-dang, CHAO Qin, et al.Study on the comprehensive model of mid-long term load forecasting[J].Power System Protection and Control,2012, 40(14):143-146, 151.

[2] BUYYA R, YEO C S, VENUGOPAL S.Market-oriented cloud computing: vision, hype, and reality for delivering IT services as computing utilities[J].High Performance Computing and Communications, 2009: 25-27.

[3] 王振樹, 李林川, 牛麗.基于貝葉斯證據框架的支持向量機負荷建模[J].電工技術學報, 2009, 24(8):127-134, 140.

WANG Zhen-shu, LI Lin-chuan, NIU Li.Load modeling based on support vector machine based on Bayesian evidence framework[J].Transactions of China Electrotechnical Society, 2009, 24(8): 127-134, 140.

[4] 陳小平, 顧雪平.基于遺傳模擬退火算法的負荷恢復計劃制定[J].電工技術學報, 2009, 24(1): 171-175, 182.

CHEN Xiao-ping, GU Xue-ping.Determination of the load restoration plans based on genetic simulated annealing algorithms[J].Transactions of China Electrotechnical Society, 2009, 24(1): 171-175, 182.

[5] 張志明, 金敏.基于灰關聯分段優選組合模型的短期電力負荷預測研究[J].電工技術學報, 2009, 24(6):115-120.

ZHANG Zhi-ming, JIN Min.Research on short-term electrical load forecasting based on optimized combination model of grey correlation segmentation[J].Transactions of China Electrotechnical Society, 2009,24(6): 115-120.

[6] PRAHASTONO I, KING D J, OZVEREN C S, et al.Electricity load profile classification using fuzzy C-means method[C] // 43rd International Universities Power Engineering Conference, 2008, 9: 1-5.

[7] 何曉峰, 王鋼, 李海鋒.電力系統粒子群優化模糊聚類算法及其應用[J].繼電器, 2007, 35(22): 40-44.

HE Xiao-feng, WANG Gang, LI Hai-feng.Power system clustering algorithm combining particle swarm optimization with fuzzy C means and its application[J].Relay, 2007, 35(22): 40-44.

[8] 李培強, 李欣然, 陳輝華, 等.基于模糊聚類的電力負荷特性的分類與綜合[J].中國電機工程學報, 2005,25(24): 73-78.

LI Pei-qiang, LI Xin-ran, CHEN Hui-hua, et al.The characteristics classification and synthesis of power load based on fuzzy clustering[J].Proceedings of the CSEE,2005, 25(24): 73-78.

[9] http://archive.ics.uci.edu/ml/index.html

[10] 唐成龍, 王石剛.基于數據間內在關聯性的自適應模糊聚類模型[J].自動化學報, 2010, 36(11): 1544-1556.

TANG Cheng-long, WANG Shi-gang.Adaptive fuzzy clustering model based on internal connectivity of all data points[J].Acta Automatica Sinica, 2010, 36(11):1544-1556.

[11] 莫維仁, 張伯明, 孫宏斌, 等.短期負荷預測中選擇相似日的探討[J].清華大學學報: 自然科學版, 2004,44(1): 106-109.

MO Wei-ren, ZHANG Bo-ming, SUN Hong-bin, et al.Method to select similar days for short-term load forecasting[J].Journal of Tsinghua University: Sci &Tech, 2004, 44(1): 106-109.

[12] 劉莉, 王剛, 翟登輝.k-means聚類算法在負荷曲線分類中的應用[J].電力系統保護與控制, 2011, 39(23):65-68, 73.

LIU Li, WANG Gang, ZHAI Deng-hui.Application of k-means clustering algorithm in load curve classification[J].Power System Protection and Control,2011, 39(23): 65-68, 73.