張少敏,趙 碩,王保義
(華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院,河北 保定 071003)
電力系統(tǒng)負(fù)荷分類就是利用各種聚類算法對選取的負(fù)荷數(shù)據(jù)樣本進(jìn)行分類,從而挖掘不同類型負(fù)荷的特性,輔助電力系統(tǒng)決策。隨著電網(wǎng)智能化程度的加深,一線城市在用電高峰期間,面臨數(shù)百萬條記錄的電力數(shù)據(jù)采集規(guī)模,一年的數(shù)據(jù)存儲規(guī)模將從目前的GB級增長到TB級,甚至PB級[1]。同時(shí),為了保證精細(xì)化、準(zhǔn)確化控制,數(shù)據(jù)維度也從幾十向上百過渡。近年來,許多的學(xué)者將數(shù)據(jù)挖掘算法[2-3]、群體智能算法[4]和機(jī)器學(xué)習(xí)算法[5]引入到電力負(fù)荷預(yù)測中,這些改進(jìn)算法幾乎都是通過大量迭代方式達(dá)到算法優(yōu)化的目的,算法復(fù)雜度相當(dāng)高。但在海量多維的智能電網(wǎng)數(shù)據(jù)上運(yùn)行串行算法時(shí)將遭遇單機(jī)計(jì)算資源不足的瓶頸。
云計(jì)算技術(shù)在2003年由Google推出后,就作為一種新興的商業(yè)計(jì)算模型得到了人們的廣泛關(guān)注,智能電網(wǎng)的云存儲模型也在不斷發(fā)展。但針對智能電網(wǎng)云存儲中的海量電力數(shù)據(jù)的聚類分析算法研究卻很少。Prahastono等人[6]利用模糊C均值聚類算法,采用印度尼西亞的真實(shí)電力數(shù)據(jù)進(jìn)行負(fù)荷特性分類研究。何曉峰等人[7]將PSO粒子群算法引入到模糊C均值聚類算法中,在一定程度彌補(bǔ)了模糊C均值聚類算法的不足,但PSO算法的微粒飛行速度難以控制,容易飛躍最優(yōu)解,導(dǎo)致無法收斂于全局最優(yōu)。
本文圍繞上述問題,將量子粒子群群體智能算法引入到傳統(tǒng)模糊C均值聚類算法中,提出了一種基于云計(jì)算的電力負(fù)荷曲線聚類的并行量子粒子群優(yōu)化模糊C均值聚類算法,充分利用QPSO較強(qiáng)的全局搜索能力,克服了模糊C均值聚類算法的缺陷;并利用云計(jì)算MapReduce框架對聚類算法進(jìn)行并行化改進(jìn),解決聚類海量高維電力負(fù)荷數(shù)據(jù)時(shí)單機(jī)運(yùn)算資源不足的瓶頸,最后,在實(shí)驗(yàn)室搭建云集群上測試改進(jìn)算法的并行性和聚類質(zhì)量,并驗(yàn)證改進(jìn)算法在實(shí)際應(yīng)用中的性能。
模糊C均值聚類算法(Fuzzy C-Means,F(xiàn)CM)[8],按數(shù)據(jù)對象間的相似度,將整個(gè)數(shù)據(jù)集合分為C個(gè)模糊聚簇中,使得類內(nèi)加權(quán)誤差平方和達(dá)到最小值。FCM聚類算法采用模糊劃分,對每個(gè)數(shù)據(jù)對象采用[0,1]之間的隸屬度表示其屬于各個(gè)聚簇的程度。根據(jù)標(biāo)準(zhǔn)化規(guī)定,一個(gè)數(shù)據(jù)對象對于C個(gè)聚簇中心的隸屬度之和等于1,即
FCM聚類算法的目標(biāo)函數(shù)為
其中:μik∈[0,1]為第k個(gè)數(shù)據(jù)對象屬于第i個(gè)聚類中心的程度;Pi為聚類i的聚類中心;m∈[0,2]為加權(quán)指數(shù);dik為第i個(gè)聚簇中心與第k個(gè)數(shù)據(jù)對象的歐氏距離(Euclidean Distance),公式為
根據(jù)FCM聚類準(zhǔn)則構(gòu)造如下Lagrangian函數(shù)
根據(jù)Kuhn-Tucker定理對輸入變量求導(dǎo),求得Jm(U,P)取最小值時(shí)的必要條件為
從FCM算法描述中可以發(fā)現(xiàn),式(5)和式(6)的計(jì)算量相當(dāng)大,而針對海量、高維的數(shù)據(jù),單機(jī)運(yùn)行FCM算法進(jìn)行電力負(fù)荷聚類分析需要很高的內(nèi)存空間,運(yùn)算效率較低,不能滿足電力控制實(shí)時(shí)性要求。運(yùn)用云計(jì)算的MapReduce對算法進(jìn)行并行化改進(jìn),以解決單機(jī)運(yùn)算資源不足的問題。
此外,F(xiàn)CM算法是一種局部搜索算法,其迭代序列必收斂到目標(biāo)函數(shù)的某個(gè)極小值或鞍點(diǎn),易陷入局部最小值,影響最終聚類質(zhì)量。為此,本文提出一種并行量子粒子群模糊C均值聚類算法(Parallel Quantum-Behaved Particle Swarm Optimization Fuzzy C-Means,P-QPSO-FCM)。
粒子群算法(Particle Swarm Optimization,簡稱PSO)是基于種群的進(jìn)化搜索技術(shù),但其不能保證算法的全局收斂,從基本粒子群算法模型可以得出,粒子的飛行速度相當(dāng)于搜索步長,全局收斂性受其速度大小直接影響[5]。針對PSO算法的收斂性問題,Sun等人從量子學(xué)的角度提出了具有量子行為的粒子群算法(Quantum-Behaved Particle Swarm Optimization,QPSO)。其將每個(gè)粒子的飛行速度由粒子的飛行最優(yōu)值和群體的飛行最優(yōu)值動(dòng)態(tài)調(diào)整。QPSO算法不僅參數(shù)少,并且搜索能力上優(yōu)于PSO算法,并且收斂性有了很大的改進(jìn)。QPSO算法中的粒子群將按照以下三個(gè)公式進(jìn)行動(dòng)態(tài)調(diào)整位置。
其中:mbest為粒子群各個(gè)粒子最優(yōu)位置的中間位置;pgbest為粒子群全局最優(yōu)位置;pid為pid和pgbest的隨機(jī)加權(quán)點(diǎn)。α是QPSO的收縮擴(kuò)張系數(shù),隨著式(10)線性變化。
其中:α1和α2為α的初始值和最終值;t是當(dāng)前的迭代次數(shù);MAXITIER是初始設(shè)定的最大迭代次數(shù)。通過線性改變α值,本文將范圍設(shè)置為1.2到0.7,此時(shí)QPSO可以實(shí)現(xiàn)比較好的性能。
FCM算法是一種基于梯度下降的局部搜索算法,易陷入局部最小,且隨機(jī)選取初始聚類中心,不同的初始聚類中心導(dǎo)致不同的聚類結(jié)果。QPSO具有全局搜索能力,不易陷入局部最小。因此本文QPSO算法代替FCM的迭代過程,防止FCM陷入局部最優(yōu),以獲得比較好的整體聚類質(zhì)量,而且可減少算法迭代次數(shù),節(jié)省計(jì)算資源,提高聚類質(zhì)量。
2.3.1 數(shù)據(jù)預(yù)處理
首先對各維數(shù)據(jù)進(jìn)行規(guī)范化,映射到[0,1]內(nèi)。
2.3.2 粒子編碼和適應(yīng)度函數(shù)設(shè)計(jì)
在QPSO中,每個(gè)粒子都是由C個(gè)聚簇中心組成,數(shù)據(jù)對象的維度為D,因此每個(gè)粒子表示為C×D維向量,粒子位置Xp構(gòu)造如下。
其中,cpi為第p個(gè)粒子的第i個(gè)聚簇中心。
定義粒子群適應(yīng)度函數(shù)為目標(biāo)函數(shù)Jm(U,P),如式(2)所示。
2.3.3 P-QPSO-FCM算法執(zhí)行步驟
P-QPSO-FCM算法具體步驟如下。
(1)初始化聚簇?cái)?shù)目C、數(shù)據(jù)對象維度D、量子粒子群規(guī)模N和最大迭代次數(shù)runtimes。
(2)在樣本數(shù)據(jù)集上運(yùn)行一次FCM算法,將獲取的聚類中心按粒子編碼規(guī)則構(gòu)造粒子個(gè)體X1,即為第一個(gè)粒子位置;然后,利用獲取的聚類中心按歐氏距離完成一次粗聚類,得到C個(gè)粗聚簇:……,其中。
(3)從每個(gè)粗聚簇中隨機(jī)取出一個(gè)數(shù)據(jù)對象,獲取C個(gè)數(shù)據(jù)對象,按粒子編碼規(guī)則構(gòu)造粒子個(gè)體X2;迭代上述步驟,直到獲取N個(gè)粒子個(gè)體。
(4)初始化粒子群的各個(gè)粒子局部最優(yōu)位置pbest和全局最優(yōu)位置pgbest。
(5)對每個(gè)粒子按照適應(yīng)度函數(shù)Jm(U,P)計(jì)算適應(yīng)度,并由每個(gè)粒子的適應(yīng)度值按式(12)、式(13)更新粒子群的pbest、pgbest,根據(jù)式(7)獲取各個(gè)粒子最優(yōu)位置的中間位置mbest。
(6)根據(jù)式(8)~式(10)得到新一代粒子個(gè)體xid。
(8)全局最優(yōu)位置對應(yīng)的聚類中心作為FCM算法的初始聚類中心,執(zhí)行FCM算法。
這里,在確定QPSO的初始N個(gè)粒子個(gè)體位置時(shí)進(jìn)行了一定的算法優(yōu)化,傳統(tǒng)粒子群算法的初始粒子個(gè)體位置是隨機(jī)生成的,本文提出的改進(jìn)算法則是通過一次FCM聚類后,分別從生成的C個(gè)粗聚簇中隨機(jī)選取數(shù)據(jù)集構(gòu)造粒子個(gè)體,在不增加算法復(fù)雜度的前提下,所選取的N個(gè)粒子個(gè)體位置在一定程度上代表了該樣本數(shù)據(jù)集的真實(shí)分布,從而降低P-QPSO-FCM算法的迭代次數(shù)。
在Hadoop平臺上實(shí)現(xiàn)P-QPSO-FCM算法需要四個(gè)階段,分別用四個(gè)MapReduce任務(wù)實(shí)現(xiàn)。算法分布式流程圖如圖1 所示,其中,Job2和Job3為簡化的分布式流程,實(shí)際分布式流程與圖中Job1和Job2相似。
圖1 P-QPSO-FCM分布式運(yùn)行流程圖Fig.1 Flow chart of P-QPSO-FCM algorithm
實(shí)驗(yàn)室搭建的Hadoop平臺由9個(gè)節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)機(jī)器配置為Intel(R)Core(TM)i5-2400 4-core CPU@2.60 GHz,4 GB RAM,網(wǎng)絡(luò)帶寬為100 Mbit/s Hadoop版本為0.20.2,HBase版本為0.90.6。
在進(jìn)行map函數(shù)操作之前,底層框架需要對輸入進(jìn)行分片,以便多個(gè)map同時(shí)工作,而分片默認(rèn)是64 M。由于真實(shí)負(fù)荷數(shù)據(jù)有限,實(shí)驗(yàn)將首先測試QPSO-FCM算法性能,然后通過人工擴(kuò)展真實(shí)數(shù)據(jù)集,測試P-QPSO-FCM并行算法的并行性能。
所用數(shù)據(jù)為國際通用測試數(shù)據(jù)庫UCI[9]上的Wine、Iris和Breast-Cancer測試數(shù)據(jù)集。其次,進(jìn)行電力系統(tǒng)算例分析。選用2001年歐洲智能技術(shù)網(wǎng)絡(luò)(EUNITE)組織的中期電力負(fù)荷預(yù)測競賽提供的某地區(qū)97、98年真實(shí)負(fù)荷數(shù)據(jù)作為算例分析數(shù)據(jù)集,在此數(shù)據(jù)集上運(yùn)行P-QPSO-FCM算法以獲取相似日曲線,并驗(yàn)證該算法與FCM算法相比具有性能優(yōu)越性。
比較FCM算法、自適應(yīng)模糊聚類 (Adaptive FCM,AFCM)[10]與提出的QPSO-FCM算法的聚類質(zhì)量。AFCM中引入了自適應(yīng)度向量 W 和自適應(yīng)指數(shù) p,文獻(xiàn)[10]經(jīng)過大量實(shí)驗(yàn)表明AFCM可以得到更好的聚類質(zhì)量。FCM算法隨機(jī)選取C個(gè)數(shù)據(jù)對象作為初始聚類中心,所以聚類質(zhì)量波動(dòng)較大。
采用適應(yīng)度函數(shù)值和聚類正確率來測試聚類質(zhì)量,適應(yīng)性函數(shù)值越小、聚類正確率越高則聚類質(zhì)量越高,適應(yīng)度函數(shù)如式(2)所示。為了保證實(shí)驗(yàn)結(jié)果的客觀性,三種算法各運(yùn)行30次,并進(jìn)行歸一化處理,實(shí)驗(yàn)結(jié)果如表1所示。
從實(shí)驗(yàn)結(jié)果看出,QPSO-FCM算法與另外兩種算法相比,不僅正確率高于后者5%到15%,且適應(yīng)性函數(shù)值更小,聚類質(zhì)量更好,陷入局部最優(yōu)的可能性更小。因此該算法具有一定的優(yōu)越性。
表1 FCM算法、AFCM算法與P-QPSO-FCM算法聚類質(zhì)量對比Table 1 Comparison of the clustering quality of the algorithm FCM, AFCM and P-QPSO-FCM
3.4.1 目標(biāo)函數(shù)值變化情況
在電力負(fù)荷樣本數(shù)據(jù)分別運(yùn)行FCM算法和QPSO-FCM算法獲取每次迭代的目標(biāo)函數(shù)值,30次實(shí)驗(yàn)取其平均值作為最終實(shí)驗(yàn)結(jié)果。目標(biāo)函數(shù)值與迭代次數(shù)變化關(guān)系如圖2所示。
圖2 目標(biāo)函數(shù)值與迭代次數(shù)變化關(guān)系Fig.2 Objective function value and the number of iterations
從實(shí)驗(yàn)結(jié)果看出,F(xiàn)CM算法運(yùn)行時(shí)隨著迭代數(shù)的增加,目標(biāo)函數(shù)值逐漸平滑減小,沒有出現(xiàn)反復(fù)情形,這說明FCM算法在樣本數(shù)據(jù)集上執(zhí)行聚類操作有可能陷入局部最優(yōu),影響最終聚類效果,而QPSO-FCM算法在聚類過程中的目標(biāo)函數(shù)值雖然總體趨勢是減小,但隨著聚類迭代次數(shù)的增加,其目標(biāo)函數(shù)值也在不斷變化,不是梯度下降的,說明該算法不易陷入局部最優(yōu),保證了最終的聚類質(zhì)量。
本文提出的改進(jìn)算法正是利用了量子粒子群算法的全局搜索能力,結(jié)合FCM的較強(qiáng)的局部搜索能力,且人工設(shè)定參數(shù)較少,來提高算法聚類質(zhì)量。
3.4.2 P-QPSO-FCM并行性能
采用加速比(speedup)來測試P-QPSO-FCM算法的并行化性能。加速比是衡量并行系統(tǒng)或程序并行化的性能和效果的指標(biāo),如式(14)所示。
因EUNITE組織提供的兩年730條48維電力負(fù)荷數(shù)據(jù)量過小,無法表現(xiàn)出P-QPSO-FCM算法并行性能。故本實(shí)驗(yàn)首先將EUNITE組織所提供的真實(shí)電力負(fù)荷數(shù)據(jù)集人工擴(kuò)充為0.5 G、1 G、2 G等3個(gè)不同大小的數(shù)據(jù)集,分別在集群節(jié)點(diǎn)個(gè)數(shù)為1、3、5、9的云集群上運(yùn)行算法,分別記錄算法執(zhí)行時(shí)間,以計(jì)算加速比,實(shí)驗(yàn)結(jié)果如圖3所示。
圖3 加速比與集群節(jié)點(diǎn)數(shù)關(guān)系圖Fig.3 Speedup in different sizes of datasets
云集群的節(jié)點(diǎn)數(shù)為9,當(dāng)云集群節(jié)點(diǎn)數(shù)量達(dá)到一定數(shù)量時(shí),因算法執(zhí)行時(shí)間相當(dāng)多的消耗在了節(jié)點(diǎn)間的網(wǎng)絡(luò)傳輸?shù)阮~外消耗上,所以加速比將隨著云集群節(jié)點(diǎn)的增加而變差。但是從有限的節(jié)點(diǎn)上可以看出,隨著數(shù)據(jù)量的增加,P-QPSO-FCM聚類算法的加速比依然幾乎線性增加,且與較小數(shù)據(jù)集的加速比折線相差不大,說明算法的并行性能較好,且HBase的讀寫性能沒有成為算法的性能瓶頸。
3.4.3 提取日負(fù)荷特征曲線
目前,許多文獻(xiàn)[11]采用相似日法作為輔助策略來改善負(fù)荷預(yù)測精度。為了驗(yàn)證提出的算法的有效性,本文將其應(yīng)用于負(fù)荷預(yù)測樣本數(shù)據(jù)的預(yù)處理。
利用文獻(xiàn)[12]中的分離系數(shù)、分離熵以及有效性評價(jià)系數(shù)來評價(jià)FCM算法與本文提出的聚類算法在真實(shí)電力負(fù)荷的聚類效果,并確定樣本的聚類個(gè)數(shù)取值為10。實(shí)驗(yàn)結(jié)果表2所示。
表2 評價(jià)指標(biāo)Table 2 Evaluation result
從表4可以看出,本文的算法在三項(xiàng)指標(biāo)均優(yōu)于FCM算法。在云平臺上執(zhí)行P-QPSO-FCM算法,即按照平均負(fù)荷變化規(guī)律相似進(jìn)行聚類,形成K條負(fù)荷水平趨勢相似日曲線,實(shí)驗(yàn)結(jié)果如圖4所示。
圖4 日負(fù)荷特征曲線Fig.4 Load characteristic curve
本文集群節(jié)點(diǎn)數(shù)為9個(gè),并行性能測試采用的數(shù)據(jù)量最高是2 G。在實(shí)際應(yīng)用中,針對實(shí)際的存儲運(yùn)算數(shù)據(jù)量,云計(jì)算集群節(jié)點(diǎn)數(shù)可達(dá)到數(shù)以千計(jì)、萬計(jì),完全可以應(yīng)對海量、高維數(shù)據(jù)運(yùn)算時(shí)對資源的要求。基于云計(jì)算的P-QPSO-FCM聚類算法,不僅能滿足當(dāng)電力負(fù)荷數(shù)據(jù)量達(dá)到TB、PB級別時(shí)數(shù)據(jù)的存儲、運(yùn)算要求;而且經(jīng)過上述實(shí)驗(yàn)以及多種評價(jià)指標(biāo)對比表明:相對基于FCM聚類算法的選取相似日的預(yù)測方式,本文提出的聚類算法在一定程度上提高了聚類準(zhǔn)確度,進(jìn)而提高了負(fù)荷預(yù)測精度。
本文提出了基于云計(jì)算的電力負(fù)荷曲線聚類的并行量子粒子群優(yōu)化模糊C均值聚類算法,通過電力負(fù)荷樣本數(shù)據(jù)的算例分析和相關(guān)測試,表明該算法顯著提高了聚類質(zhì)量和效率,且并行化性能良好。
[1] 袁鐵江, 袁建黨, 晁勤, 等.電力系統(tǒng)中長期負(fù)荷預(yù)測綜合模型研究[J].電力系統(tǒng)保護(hù)與控制, 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ù)框架的支持向量機(jī)負(fù)荷建模[J].電工技術(shù)學(xué)報(bào), 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] 陳小平, 顧雪平.基于遺傳模擬退火算法的負(fù)荷恢復(fù)計(jì)劃制定[J].電工技術(shù)學(xué)報(bào), 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] 張志明, 金敏.基于灰關(guān)聯(lián)分段優(yōu)選組合模型的短期電力負(fù)荷預(yù)測研究[J].電工技術(shù)學(xué)報(bào), 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] 何曉峰, 王鋼, 李海鋒.電力系統(tǒng)粒子群優(yōu)化模糊聚類算法及其應(yīng)用[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] 李培強(qiáng), 李欣然, 陳輝華, 等.基于模糊聚類的電力負(fù)荷特性的分類與綜合[J].中國電機(jī)工程學(xué)報(bào), 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] 唐成龍, 王石剛.基于數(shù)據(jù)間內(nèi)在關(guān)聯(lián)性的自適應(yīng)模糊聚類模型[J].自動(dòng)化學(xué)報(bào), 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] 莫維仁, 張伯明, 孫宏斌, 等.短期負(fù)荷預(yù)測中選擇相似日的探討[J].清華大學(xué)學(xué)報(bào): 自然科學(xué)版, 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聚類算法在負(fù)荷曲線分類中的應(yīng)用[J].電力系統(tǒng)保護(hù)與控制, 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.