張少敏，趙 碩，王保義

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

0 引言

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

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

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

1 模糊C均值聚類算法

1.1 算法描述

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

FCM聚類算法的目標函數(shù)為

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

根據(jù)FCM聚類準則構(gòu)造如下Lagrangian函數(shù)

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

1.2 FCM算法的不足

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

此外，F(xiàn)CM算法是一種局部搜索算法，其迭代序列必收斂到目標函數(shù)的某個極小值或鞍點，易陷入局部最小值，影響最終聚類質(zhì)量。為此，本文提出一種并行量子粒子群模糊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）。其將每個粒子的飛行速度由粒子的飛行最優(yōu)值和群體的飛行最優(yōu)值動態(tài)調(diào)整。QPSO算法不僅參數(shù)少，并且搜索能力上優(yōu)于PSO算法，并且收斂性有了很大的改進。QPSO算法中的粒子群將按照以下三個公式進行動態(tài)調(diào)整位置。

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

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

2.2 FCM算法改進思想

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

2.3 P-QPSO-FCM算法設計

2.3.1 數(shù)據(jù)預處理

首先對各維數(shù)據(jù)進行規(guī)范化，映射到[0,1]內(nèi)。

2.3.2 粒子編碼和適應度函數(shù)設計

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

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

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

2.3.3 P-QPSO-FCM算法執(zhí)行步驟

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

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

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

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

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

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

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

（8）全局最優(yōu)位置對應的聚類中心作為FCM算法的初始聚類中心，執(zhí)行FCM算法。

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

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

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

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

3 實驗與算例分析

3.1 實驗準備

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

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

3.2 測試數(shù)據(jù)集描述

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

3.3 聚類質(zhì)量對比實驗

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

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

從實驗結(jié)果看出，QPSO-FCM算法與另外兩種算法相比，不僅正確率高于后者5%到15%，且適應性函數(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 算例分析

3.4.1 目標函數(shù)值變化情況

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

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

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

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

3.4.2 P-QPSO-FCM并行性能

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

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

圖3 加速比與集群節(jié)點數(shù)關系圖Fig.3 Speedup in different sizes of datasets

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

3.4.3 提取日負荷特征曲線

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

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

表2 評價指標Table 2 Evaluation result

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

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

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

4 結(jié)語

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

[1] 袁鐵江, 袁建黨, 晁勤, 等.電力系統(tǒng)中長期負荷預測綜合模型研究[J].電力系統(tǒng)保護與控制, 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].電工技術學報, 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] 張志明, 金敏.基于灰關聯(lián)分段優(yōu)選組合模型的短期電力負荷預測研究[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] 何曉峰, 王鋼, 李海鋒.電力系統(tǒng)粒子群優(yōu)化模糊聚類算法及其應用[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] 唐成龍, 王石剛.基于數(shù)據(jù)間內(nèi)在關聯(lián)性的自適應模糊聚類模型[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].電力系統(tǒng)保護與控制, 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.