基于CUDA技術的海量電力負荷曲線聚類算法

吳 霜， 季 聰， 孫國強

( 1. 國網江蘇省電力有限公司經濟技術研究院，江蘇 南京 210008;2. 江蘇方天電力技術有限公司，江蘇 南京 211102;3. 可再生能源發(fā)電技術教育部工程研究中心(河海大學)，江蘇 南京 210098)

0 引言

隨著電力改革不斷推進和電力用戶需求的多元化發(fā)展，電力企業(yè)越來越關注用戶負荷、電量數據分析，希望通過數據挖掘來提高服務質量、創(chuàng)造增值效益。而用電信息采集、負荷控制等信息化系統的建設與應用，積累了海量的電力用戶負荷數據，為用戶數據分析提供了良好的數據基礎。

一直以來，電力專家和學者們都持續(xù)不斷地開展著負荷特性、負荷預測等數據挖掘課題的研究[1-3]，而負荷聚類分析是開展負荷特性分析、負荷建模等工作的基礎[4]。但隨著用戶側數據量的爆炸式增長，用戶負荷聚類分析面臨著對象眾多、數據量大等問題。Nvidia基于圖形處理單元(graphic process unit, GPU)的統一計算設備架構(compute uniform device architecture, CUDA)技術給出了令人鼓舞的解決方案，它通過大量線程并發(fā)機制，極大地加快了海量數據計算與分析的速度[5]。目前，CUDA技術已在電力系統諧波分析[6]、暫態(tài)穩(wěn)定[7-8]、狀態(tài)估計[9]等領域得到了廣泛的應用。

目前已有學者將CUDA技術用于加速文獻聚類[10-11]、圖形聚類[12]等，但在海量電力負荷曲線聚類中，CUDA技術的未見應用。因此，本文基于電力負荷曲線的特征，針對CUDA的技術特性，深入研究負荷曲線聚類算法的并行處理機制，采用待劃分數據與聚類中心的距離計算并行化、類別變化曲線數統計并行化、線程塊分配合理化等多個并行加速策略，極大地提升了用戶負荷曲線的聚類速度，取得良好的聚類結果和加速性能。

1 K-means聚類算法

K-means聚類算法原理簡單，可操作性強，是目前應用最為廣泛的聚類方法之一。它首先隨機選定一組初始聚類中心，經迭代使得聚類中心保持類間獨立、類內緊密，迭代期間不斷更新聚類子集和聚類中心。目前K-means聚類算法在圖形分割、流量監(jiān)測、負荷聚類等領域得到了廣泛的應用[13-15]。

K-means聚類算法的輸入為包含N個數據項的待劃分數據集X={x1,x2,…,xN}，其中xi=[xi1,xi2,…,xiD]，D為數據的維度。輸出則為K個聚類集合C={c1,c2,…,cK}，K為用戶自定義的聚類中心個數。K-means的目標是使屬于集合cK的數據xi到其所屬聚類中心mk的距離最小，即：

(1)

(2)

式中：nk為集合ck所包含的數據個數。K-means聚類算法的主要步驟如下。

Step 0：數據準備階段。準備好待劃分數據集X，選擇合適的K，設定算法停止迭代判定條件(一般為最大迭代次數或類別變化曲線條數占比)。

Step 1：初始聚類中心選擇。一般采用隨機選擇法選取聚類中心，目前也有大量學者提出了各種改進方法[16-17]。

Step 2：數據集歸類計算。采用歐式距離法計算各數據到聚類中心的距離，將各數據劃分到距離最短的聚類中心。距離計算公式如下：

(3)

Step 3：重新計算聚類中心。依據Step 2中的數據分類，重新計算各聚類中心。

Step 4：判斷是否滿足迭代結束條件，若是，則退出迭代，輸出聚類結果；否則返回Step 2。

2 K-means的CUDA加速策略

2.1 CUDA的加速原理

CUDA技術由Nvidia公司于2007年6月提出，與之前的通用圖形處理單元(general purpose GPU，GPGPU)不同，它采用標準C語言進行編碼，并且開放了大量基于C語言的應用程序接口(application programming interface，API)，極大地方便了基于GPU的并行編碼，為算法開發(fā)與設計提供了一種高性能、易維護的GPU并行計算平臺。

CUDA技術中，GPU被組織成3層計算資源：線程(Thread)、線程塊(Block)、線程網格(Grid)，其組織結構如圖1所示。

圖1 CUDA的線程組織形式Fig.1 Organization mode of threads in CUDA

CUDA通過將串行程序中相對獨立的簡單計算操作交由GPU中的大量線程并發(fā)執(zhí)行，從而使計算速度得到大幅度的提升。K-means聚類算法的核心部分在于計算待劃分數據與聚類中心的距離，該計算步驟恰恰屬于計算過程相對簡單獨立、重復性高的操作，可以交由GPU進行并行加速計算。

2.2 K-means的加速策略

從K-means聚類算法的原理可知，其計算量最大的部分在于待劃分數據與聚類中心的距離計算，該步驟具備高度的可拆分性，因此可采用CUDA對其進行加速處理。

加速策略1：待劃分數據與聚類中心的距離計算并行化。將N個待劃分數據分別指派給N個線程，各線程分別計算待劃分數據與聚類中心的距離，從而實現距離計算的高度并行。

加速策略2：類別變化曲線數統計的并行化。統計類別變化曲線數時一般采用累加法，采用CUDA加速時，可考慮線程塊內變化數目疊加后存于線程塊內的寄存器，再通過多個線程塊寄存器數據并行累加得到總變化數。線程塊寄存器的讀寫速度遠遠快于內存，因此可以節(jié)省大量的數據傳輸和讀寫時間。另外，塊間數據累加時采用二分并行疊加，計算復雜度可由N降低為log2(N)。

加速策略3：線程塊分配最優(yōu)化。由于GPU的一個線程束包括32個線程，因此無論計算能力高低，目前線程塊所包含的線程數均為32的倍數，在線程塊的分配上，需要根據聚類數據量的大小，合理分配線程塊的大小和線程塊的個數，保證每條負荷曲線有對應的線程處理。本文采用的GPU為Nvidia GeForce GTX960，其線程塊最大可處理1024個線程，在數據量較小時(例如4.1的2000條負荷曲線)，線程塊大小可設置為64、128，在數據量較大時(例如4.2的40 000條負荷曲線)，線程塊大小可設置為1024。

通過上述3個加速策略，可顯著提升K-means聚類算法的計算效率，這對于海量數據聚類具有極大的技術價值。

3 基于CUDA的K-means聚類算法實現步驟

基于CUDA的K-means聚類算法實現步驟如圖2所示。

圖2 基于CUDA的K-means聚類算法實現步驟Fig.2 Flow chart of CUDA based K-means clustering

Step 1：讀入用戶負荷數據，設定聚類個數、收斂條件等參數，本文以變化類別曲線占比ε為收斂判據，ε<0.001則認為達到收斂要求。

Step 2：將用戶負荷曲線從內存復制到GPU，并隨機選定K條負荷曲線作為初始聚類中心。

Step 3：根據用戶負荷曲線數量，采用加速策略3設定線程塊的大小、以及線程塊的數量。目前Maxwell架構的GPU線程塊支持最大線程數為1024，因此盡可能選擇線程塊大小為1024，線程塊數量為1+N/1024取整。

Step 4：N個線程與N條負荷曲線一一對應，N個線程分別計算N條負荷曲線與K個聚類中心的距離。

Step 5：根據距離大小將負荷曲線歸入最近的聚類中心，并計算生成新的聚類中心。

Step 6：采用加速策略2統計類別發(fā)生變化的負荷曲線條數，并計算變化條數占比ε，若ε<0.001，則執(zhí)行Step 7，否則轉到Step 4。

Step 7：將聚類結果從GPU復制到內存，并輸出。

4 算例分析

以江蘇電網企業(yè)用戶典型負荷日數據為例，進行聚類分析，驗證本文提出的并行聚類算法的效率。

4.1 基本測試

首先以江蘇電網2000個企業(yè)用戶的典型負荷日數據為例，進行聚類分析。計算機CPU為Intel Core I5-4590 @ 3.3GHz，GPU為NVIDIA GeForce GTX960，運行環(huán)境為Win 7，編譯環(huán)境為Visual Studio 2010。算法參數方面：設定聚類數K=4，收斂條件ε<0.001。

串行方法迭代13次，計算時間為0.092 s，并行方法迭代次數12次，計算時間為0.302 s，計算速度反而降低。計算結果表明，串行方法與并行方法得到了相同的聚類結果，如圖3所示，其中負荷曲線均已歸一化處理。

圖3 負荷曲線聚類結果Fig.3 Clustering results of power load curves

2000條負荷曲線被劃分為4類，各類曲線條數如圖4所示。

圖4 各負荷特性類型所含曲線條數Fig.4 Number of all four type of load characteristics

(1) 全天型負荷。全天24 h負荷差異較小，這類曲線有941條。該負荷特性一般出現在三班倒的輕工、電子、食品加工等行業(yè)。

(2) 夜間型負荷。夜間負荷水平較高，白天反之，這類曲線有111條。該負荷特性一般出現在冶金、水泥等大型制造行業(yè)。

(3) 白天型負荷1。白天負荷較高，夜間反之，這類曲線有373條。該負荷特性一般出現在計算機軟件、商業(yè)等行業(yè)。

(4) 白天型負荷2。與白天型負荷1的區(qū)別在于中午會發(fā)生短時的負荷下降，這類曲線有575條。該負荷特性一般出現在輕工、餐飲等行業(yè)。

4.2 性能測試

為了說明4.1節(jié)遇到的并行方法計算時間反而增加的問題，仍然以4.1節(jié)的江蘇電網2000條企業(yè)典型負荷曲線為例，進行算例分析。測試手段為不斷增加聚類個數K，串行方法與并行方法計算時間及迭代次數如圖5、6所示。由圖5—6可以得出以下結論：

圖5 計算時間比較Fig.5 Comparison of computing time

圖6 迭代次數比較Fig.6 Comparison of iteration times

(1) 在聚類中心個數為4,10時，計算量較小，而并行方法由于增加了數據傳輸(負荷數據自內存拷貝GPU、聚類結果自GPU拷貝至內存)和線程同步時間，導致計算時間反而有所增加；

(2) 但隨著聚類中心個數的增加，計算量逐漸增加，并行方法的速度優(yōu)勢逐漸體現，在K=200時，加速比為2.01；

(3) 在迭代次數方面，串行方法與并行方法基本相當，并行方法由于GPU的計算精度為float類型(而CPU為double類型)，因此迭代次數略增(基本增加1次)。

很顯然，2000條負荷曲線的聚類分析遠遠稱不上是海量負荷數據，也不足以體現并行方法的加速性能，因此本文選取了江蘇電網4.1萬用戶典型負荷曲線，進行更大規(guī)模的測試與分析，串行方法與并行方法的計算時間及加速比如圖7所示。

圖7 計算時間及加速比(N=41 000，K變化)Fig.7 Computing time and speed-up ratio (N=41 000，K changes)

在數據量較大時，并行方法大幅度地提高了K-means聚類算法的計算效率，便最高加速比達到了16.2681倍，可見基于CUDA的并行K-means聚類算法加速效果顯著。需要說明的是：K=1000和K=2000時計算時間與加速比均小于K=500時，這主要是因為迭代次數的減少(K=1000時迭代33次，K=2000時21次，而K=500時101次)。

保持聚類中心個數K=500不變，負荷曲線數量從10 000增加到200 000條，進行聚類計算，串行方法與并行方法的計算時間及加速比如圖8所示。

圖8 計算時間及加速比(K=500，N變化)Fig.8 Computing time and speed-up ratio(K=500, N changes)

隨著負荷曲線條數的增加，K-means聚類算法的計算量成倍增加，而GPU的加速比也在持續(xù)增加，在N=207 000時，加速比達到了19.049，可見本文提出的并行方法計算速度快、適用能力強，極大地提升了海量負荷數據背景下的電力用戶負荷曲線聚類分析效率。

5 結語

在電力體制改革和售電市場放開的大環(huán)境下，電力用戶負荷特性分析將得到前所未有的關注，但用戶數據數量巨大，負荷分析計算量過大。在這樣的背景下，本文提出了基于CUDA技術的并行K-means聚類算法，并以江蘇電網企業(yè)用戶典型負荷曲線為例，進行了多組算例測試與分析，結果表明本文提出的并行方法加速比高、適應性強，可以作為海量負荷曲線聚類分析的有力工具。