基于Kernel K-means的負(fù)荷曲線聚類

趙文清，龔亞強(qiáng)

（華北電力大學(xué) 控制與計(jì)算機(jī)工程學(xué)院，河北 保定 071003）

0 引言

電力負(fù)荷曲線聚類是配用電大數(shù)據(jù)挖掘的基礎(chǔ)［1］。負(fù)荷曲線聚類一直是電力負(fù)荷預(yù)測、分時(shí)電價(jià)、錯(cuò)峰管理、系統(tǒng)規(guī)劃的基礎(chǔ)，通過負(fù)荷分類和負(fù)荷特性分析，對于掌握電力負(fù)荷的變化規(guī)律和發(fā)展趨勢具有重大意義。高效的負(fù)荷聚類方法能為電力規(guī)劃、錯(cuò)峰管理等提供可靠的依據(jù)和準(zhǔn)確的指導(dǎo)［2］。因此，研究準(zhǔn)確的負(fù)荷曲線聚類具有重要意義。

電力負(fù)荷曲線的聚類分析，實(shí)際上就是衡量不同負(fù)荷曲線的相似性，以及把負(fù)荷曲線分類到不同的簇中。這就需要根據(jù)負(fù)荷特性進(jìn)行準(zhǔn)確、科學(xué)分類，以確保在同一類中的負(fù)荷曲線具有相同或相似的負(fù)荷特性，進(jìn)而合理地確定典型負(fù)荷曲線的歸類。在良好分類的基礎(chǔ)上，可以進(jìn)一步提高負(fù)荷預(yù)測精度、降低負(fù)荷管理的難度。聚類的結(jié)果要滿足類內(nèi)具有較高的緊密性，類間具有較高的分離性，體現(xiàn)出不同類型用戶之間的負(fù)荷特性差異［3］。

目前的電力負(fù)荷曲線聚類的方法很多，比較流行的有 K-means 聚類［4］、小波分析［5］、模糊 C 均值聚類算法（FCM）［6］、集成聚類算法［1］、自組織特征映射神經(jīng)網(wǎng)絡(luò)（SOM）［7］、極端學(xué)習(xí)機(jī)（ELM）［8］、云模型［9］等，同時(shí)還有一些在這些算法的基礎(chǔ)上進(jìn)行改進(jìn)的算法。

由于智能電網(wǎng)技術(shù)的快速發(fā)展，各種先進(jìn)的檢測裝置和計(jì)量設(shè)備在配電網(wǎng)中取得了廣泛的應(yīng)用。對負(fù)荷的檢測的時(shí)間越來越短，導(dǎo)致負(fù)荷數(shù)據(jù)的維數(shù)大幅提高，加大了負(fù)荷曲線聚類的難度。為了解決該問題，本文采用核方法將數(shù)據(jù)映射到高維空間中，加大數(shù)據(jù)的可分性，從而提高負(fù)荷曲線聚類的效果。

1 Kernel K-means

1.1 核函數(shù)

核方法是將數(shù)據(jù)映射到高維空間中，從而使數(shù)據(jù)可分性在高維空間中增大，聚類的效果相應(yīng)地得到提升［10］。核方法對映射到高維空間的維度并沒有太多的限制，高維空間甚至可以是無限維的。

核函數(shù)為核方法提供了一種映射的方式。核函數(shù)通過點(diǎn)積的方式將數(shù)據(jù)在高維空間中的關(guān)系表示出來，降低了在高維空間中討論數(shù)據(jù)映射的難度。下面將描述核函數(shù)是如何表示數(shù)據(jù)在高維空間的關(guān)系。

假設(shè)給定一組樣本數(shù)據(jù) x1、x2、…、xn，xi?RD，即每個(gè)樣本數(shù)據(jù)為D維向量，映射方程φ（x）將xi從空間RD映射到新空間Q，則核函數(shù)在新空間Q定義的點(diǎn)積為：

其中，無需知道變換函數(shù)φ（x）的形式和參數(shù)，映射實(shí)際上是通過核函數(shù)H（xi，xj）完成的，即只需要給定核函數(shù)的形式就能完成數(shù)據(jù)從低維空間到高維空間的映射。常用的核函數(shù)有：多項(xiàng)式核函數(shù)H（xi，xj）=（xi·xj+1）d、高斯核函數(shù)H（xi，xj）=exp（-r‖xi-xj‖2）、感知器核函數(shù)H（xi，xj）=tanh［a（xi·xj）+d］。

通過上述方式，核函數(shù)可以輕易地將低維空間與高維空間聯(lián)系起來。核函數(shù)方法可以和不同的算法相結(jié)合，形成多種不同的基于核函數(shù)技術(shù)的方法，而且這兩部分的設(shè)計(jì)可以單獨(dú)進(jìn)行，并可以為不同的應(yīng)用選擇不同的核函數(shù)和算法。如SVM（Support Vector Machine）、Kernel K-means算法、核主成分分析 KPCA（Kernel Principal Component Analysis）等都是核函數(shù)與不同算法的結(jié)合。

1.2 算法描述

負(fù)荷曲線聚類的經(jīng)典聚類分析方法有基于層次、基于劃分、基于密度、基于模型等聚類算法，經(jīng)典聚類算法各有優(yōu)缺點(diǎn)［1］，本文為了進(jìn)一步提高聚類劃分的效果，采用Kernel K-means算法對負(fù)荷數(shù)據(jù)進(jìn)行研究。

Kernel K-means算法是K-means算法的推廣，也可以看作是它的一般形式。在K-means算法中，點(diǎn)與點(diǎn)之間的相似性是用距離來衡量的，但在Kernel K-means算法中，用核函數(shù)代替距離的作用衡量相似性。這樣就相當(dāng)于將數(shù)據(jù)的整個(gè)距離結(jié)構(gòu)改變，同時(shí)也可以看作是將數(shù)據(jù)映射到一個(gè)新的空間。Kernel K-means算法描述如下。

設(shè) A=｛x1，x2，…，xn｝為 n 個(gè)樣本的數(shù)據(jù)集，劃分A 為 K 類，Ck（k=1，2，…，K）代表一個(gè)聚類，δ（xi，Ck）表示指示函數(shù)，對應(yīng)各個(gè)樣本的所屬類別k。φ（xi）表示 xi（i=1，2，…，n）從空間 RD到新空間 Q 的變換，在核空間Q中，聚類Ck對應(yīng)的類中心為mk，公式如下：

其中，表示聚類Ck中的樣本個(gè)數(shù)。

空間RD中任意2點(diǎn)間的距離通過核函數(shù)表示為內(nèi)積的公式如下：

其中，選取高斯核作為核函數(shù) H（xi，xj）。

同理，類中每點(diǎn)xi到類中心mk的距離在新空間可表示為 D（xi，mk）=‖φ（xi）-mk‖2。

1.3 算法流程

Kernel K-means描述如下：

a.隨機(jī)初始化分類向量 δ（xi，Ck），構(gòu)造初始聚類 C1、C2、…、CK；

b.計(jì)算；

c.計(jì)算 F（xi，Ck），將 xi分配到最近的聚類中；

d.重復(fù)步驟 b、c，直到 δ（xi，Ck）不再變化。

2 算法優(yōu)化

2.1 核主成分分析

主成分分析PCA（Principal Component Analysis）是一種確定一個(gè)坐標(biāo)系統(tǒng)的直交變換。在這個(gè)新的坐標(biāo)系統(tǒng)下，變換數(shù)據(jù)點(diǎn)的方差沿新的坐標(biāo)軸可以得到最大化。這些坐標(biāo)軸經(jīng)常被稱為是主成分。PCA運(yùn)算是一個(gè)利用了數(shù)據(jù)集的統(tǒng)計(jì)性質(zhì)的特征空間變換。這種變換在無損或很少損失數(shù)據(jù)集的信息的情況下降低了數(shù)據(jù)集的維數(shù)［12］。

KPCA是線性PCA的非線性擴(kuò)展算法，它采用非線性的方法抽取主成分，即KPCA是在通過映射函數(shù)把原始向量映射到高維空間F，在F上進(jìn)行PCA［12］。 文獻(xiàn)［13］提出一種大規(guī)模數(shù)據(jù)集求解核主成分的計(jì)算方法，該方法首先利用Gram矩陣構(gòu)造一個(gè)Gram-power矩陣，然后將Gram矩陣的每一列作為每一步迭代算法的輸入樣本［13］。利用該方法可以有效解決傳統(tǒng)方法在大規(guī)模數(shù)據(jù)集下無法使用的問題。

KPCA與PCA具有本質(zhì)上的區(qū)別：PCA基于指標(biāo)，而KPCA是基于樣本的。KPCA不僅適合解決非線性特征提取問題，而且它還能比PCA提供更多的特征數(shù)目和更多的特征質(zhì)量。因?yàn)镵PCA可提供的特征數(shù)目與輸入樣本的數(shù)目是相等的，而PCA的特征數(shù)目僅為輸入樣本的維數(shù)。KPCA的優(yōu)勢是可以最大限度地抽取指標(biāo)的信息，但是KPCA抽取指標(biāo)的實(shí)際意義不是很明確［12］。

2.2 核矩陣的削減

從Kernel K-means算法中可以得出，比較樣本與類中心距離大小需要計(jì)算2個(gè)樣本的內(nèi)積。本文中將數(shù)據(jù)集中任意2個(gè)樣本間的內(nèi)積計(jì)算出來，組成核矩陣［12］。核矩陣H為n×n階矩陣，其中：

N條負(fù)荷曲線構(gòu)成數(shù)據(jù)集合。其中，每條負(fù)荷曲線都是由 D 維的向量組成。如果要構(gòu)造這樣一個(gè)核矩陣，矩陣的儲(chǔ)存空間將為 O（N2）。 當(dāng) N 較大時(shí)，矩陣計(jì)算量將會(huì)很大［11］。文獻(xiàn)［14-16］為了提高計(jì)算的效率，分別提出不同的解決策略。本文按照保留核矩陣中值較大的項(xiàng)、去除核矩陣中較小值的原則，再依據(jù)給定規(guī)則將核矩陣的某些項(xiàng)歸零［11］。這樣，可以減少計(jì)算時(shí)間，提高運(yùn)算效率。這種對核矩陣削減的算法描述如下。

a.將核矩陣H各行按升序進(jìn)行排列，每行得到一個(gè)排序向量 ri：rij（i=1，2，…，n；j=1，2，…，n）。

b.計(jì)算rij的一階導(dǎo)數(shù)，公式如下：

c.以降序方式排列 r′ij（j=1，2，…，n）。 若為排序的前10%，則令vij=1；否則，vij=0。10%為所給定的閾值。 得到的二值化向量 vi，vi=［vi1，vi2，…，vin］T。

e.根據(jù)v*計(jì)算得分向量s，公式如下：

f.取 s中最大值所屬聚類 j，即，定義：對任一數(shù)據(jù)樣本ai，其二值向量為 vi，如果viw=1，則ai屬于基數(shù)為w的聚類；否則不屬于聚類w。任一數(shù)據(jù)樣本ai，若使聚類基數(shù)w值有所增加，必然屬于聚類w。

g.令 v*=v*-vi，若 v*≠0，進(jìn)行下一次迭代，重復(fù)步驟 d、e；若 v*=0，進(jìn)入下一行，重復(fù)步驟 b—g。

h.假設(shè)ai所屬的聚類基數(shù)為wi，在第i行中，保留［H］ij值中較大的前wi項(xiàng)，其余所有項(xiàng)全部設(shè)置為0。削減后的核矩陣記為H*，其中的非0項(xiàng)個(gè)數(shù)記為nz。

3 實(shí)驗(yàn)分析

3.1 聚類評估指標(biāo)的選取

聚類分析是按照樣本的特征將其分類到不同的類的過程，使同一類的個(gè)體具有盡可能高的相似性，而類別間則具有盡可能高的互異性。由于聚類分析是在沒有先驗(yàn)信息指導(dǎo)下的無監(jiān)督學(xué)習(xí)過程，因此評價(jià)聚類的效果在聚類分析中至關(guān)重要。

本文采用Davies-Bouldin指標(biāo)評價(jià)聚類質(zhì)量并確定最佳聚類數(shù)，其計(jì)算公式如下：

其中，Ri用來衡量第i類與第j類的相似度。

其中，Si用來度量第i個(gè)類中數(shù)據(jù)點(diǎn)的分散程度，計(jì)算公式如式（12）所示。

其中，Xl為第i類中第l個(gè)數(shù)據(jù)點(diǎn)；Ai為第i類的中心；Ti為第i類中數(shù)據(jù)點(diǎn)的個(gè)數(shù)；q取1時(shí)Si為各點(diǎn)到中心的距離的均值，q取2時(shí)Si為各點(diǎn)到中心的距離的標(biāo)準(zhǔn)差，它們都可以用來衡量類內(nèi)分散程度。

其中，Mij為第i類中心與第j類中心的距離；adi為第i類的中心點(diǎn)Ai的第d個(gè)屬性的值；p取1時(shí)表示1-范數(shù)，p取2時(shí)表示2-范數(shù)（表示2個(gè)類中心的歐氏距離）。

DBI是類內(nèi)距離之和與類外距離的比值。類內(nèi)對象距離越小，類間距離越大，DBI指標(biāo)也越小，聚類效果越好。DBI也可以優(yōu)化K值的選擇，最小的DBI指標(biāo)對應(yīng)的K就是最佳聚類個(gè)數(shù)。

3.2 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)［17］取自由美國能源部于2009年12月成立的 OpenEI（Open Energy Information）。 OpenEI是為政策制定者、研究人員、技術(shù)投資者、風(fēng)險(xiǎn)資本家及市場專業(yè)人士提供能源數(shù)據(jù)、信息等其他資源的網(wǎng)站。部分實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 24 h居民負(fù)荷數(shù)據(jù)Table1 Hourly data of residential load

3.3 結(jié)果分析

實(shí)驗(yàn)采用的機(jī)器配置為 Intel（R）Core（TM）i3-3110M 8-core CPU@2.40 GHz，4 GB RAM，MATLAB版本為MATLABR2014b。

首先考察KPCA對聚類效果的影響。當(dāng)采用KPCA進(jìn)行降維后，輸出的維度對聚類效果有較大的影響，比如取輸出維度為［1，30］時(shí)，聚類效果如圖1所示。

圖1 輸出維度對聚類效果的影響Fig.1 Effect of output dimension on clustering

由圖1可知，輸出維度的大小與聚類效果不是正比關(guān)系，當(dāng)輸出的維度太大或者太小，都不會(huì)得到最優(yōu)聚類。當(dāng)輸出維度為6時(shí)，得到DBI的值最小，聚類的結(jié)果最為理想。因此核主成分分析取6作為輸出維度。

實(shí)驗(yàn)再對聚類數(shù)與聚類效果進(jìn)行分析，分別采用3種算法進(jìn)行對比分析。第1種算法是傳統(tǒng)的K-means；第2種算法是Kernel K-means，即采用了核方法的K-means；第3種算法KPCA-K-K-means首先使用KPCA進(jìn)行降維處理，從而得到降維后的核矩陣，再削減核矩陣，最后使用K-means進(jìn)行聚類。利用MATLAB對上述3種算法編程，考察不同聚類數(shù)對聚類效果的影響，K-means、Kernel K-means、KPCAK-K-means以聚類數(shù)作為輸入，其中Kernel K-means與KPCA-K-K-means的核函數(shù)都選取高斯核函數(shù)，參數(shù)分別取r1=-0.1、r2=-1。聚類數(shù)與DBI對應(yīng)關(guān)系如表2所示。

表2 聚類數(shù)與DBI的關(guān)系Table 2 Relationship between clustering number and DBI

由于3種算法的聚類效果都會(huì)受初始點(diǎn)的影響，因此對每個(gè)算法每一聚類數(shù)K，分別運(yùn)行10次，取最小的DBI值作為該算法的性能表現(xiàn)。表2對應(yīng)的曲線圖如圖2所示。

圖2 聚類數(shù)與DBI的關(guān)系曲線Fig.2 Chart of relationship between clustering number and DBI

從圖2可以看出，當(dāng)聚類數(shù)取值相同時(shí)，各算法所得DBI值中，K-means算法最大，Kernel K-means次之，KPCA-K-K-means最小。在聚類數(shù)的取值不同時(shí)，KPCA-K-K-means取 得的 DBI值 比 K-means、Kernel K-means 2種算法得到的DBI值都要小，可以得出KPCA-K-K-means算法對負(fù)荷曲線的劃分更加合理，可以提高聚類的準(zhǔn)確度。從圖中還可得出，當(dāng)聚類數(shù)K=5時(shí)，曲線具有明顯的拐點(diǎn)，由此可以確定最佳聚類數(shù)。

4 結(jié)論

本文針對負(fù)荷數(shù)據(jù)出現(xiàn)的新特點(diǎn)，提出使用KPCA方法對負(fù)荷數(shù)據(jù)進(jìn)行降維，同時(shí)保持?jǐn)?shù)據(jù)在高維空間中的映射，使數(shù)據(jù)具有較好的可分性，然后根據(jù)聚類算法Kernel K-means的原理，對負(fù)荷曲線進(jìn)行劃分。實(shí)驗(yàn)探究了不同聚類數(shù)與聚類效果的關(guān)系以及輸出維數(shù)對聚類效果的影響，表明本文方法可以有效地提高負(fù)荷曲線聚類的準(zhǔn)確性。但該方法聚類易受聚類數(shù)和初始分類影響，需要提前確定核函數(shù)參數(shù)，以及運(yùn)行時(shí)間增大等問題并沒有完全解決，這也是進(jìn)一步的研究方向。

［1］張斌，莊池杰，胡軍，等.結(jié)合降維技術(shù)的電力負(fù)荷曲線集成聚類算法［J］. 中國電機(jī)工程學(xué)報(bào)，2015，35（15）：3741-3749.ZHANG Bin，ZHUANG Chijie，HU Jun，et al.Dimensionality reduction technique combined with power load curve integrated clustering algorithm［J］.Proceedings of the CSEE，2015，35（15）：3741-3749.

［2］朱曉清.電力負(fù)荷的分類方法及其應(yīng)用［D］.廣州：華南理工大學(xué)，2012.ZHU Xiaoqing.Classification of power load and its application［D］.Guangzhou：South China University of Technology，2012.

［3］張忠華.電力系統(tǒng)負(fù)荷分類研究［D］.天津：天津大學(xué)，2007.ZHANG Zhonghua.Load classification of power system ［D］.Tianjin：Tianjin University，2007.

［4］白雪峰，蔣國棟.基于改進(jìn)K-means聚類算法的負(fù)荷建模及應(yīng)用［J］. 電力自動(dòng)化設(shè)備，2010，30（7）：80-83.BAI Xuefeng，JIANG Guodong.Load modeling based on improved K-means clustering algorithm and its application［J］.Electric Power Automation Equipment，2010，30（7）：80-83.

［5］張平，潘學(xué)萍，薛文超.基于小波分解模糊灰色聚類和BP神經(jīng)網(wǎng)絡(luò)的短期負(fù)荷預(yù)測［J］. 電力自動(dòng)化設(shè)備，2012，32（11）：121-125，141.ZHANG Ping，PAN Xueping，XUE Wenchao.Short-term load forecasting based on wavelet decomposition，fuzzy gray correlation clustering and BP neural network［J］.Electric Power Automation Equipment，2012，32（11）：121-125，141.

［6］劉永光，孫超亮，牛貞貞，等.改進(jìn)型模糊C均值聚類算法的電力負(fù)荷特性分類技術(shù)研究［J］. 電測與儀表，2014，51（18）：5-9.LIU Yongguang，SUN Chaoliang，NIU Zhenzhen，et al.Research on the improved fuzzy C-means clustering algorithm based power load characteristic classification technology［J］.Electrical Measurement&Instrumentation，2014，51（18）：5-9.

［7］李智勇，吳晶瑩，吳為麟，等.基于自組織映射神經(jīng)網(wǎng)絡(luò)的電力用戶負(fù)荷曲線聚類［J］. 電力系統(tǒng)自動(dòng)化，2008，32（15）：66-70，78.LI Zhiyong，WU Jingying，WU Weilin，et al.Power customers load profile clustering using the SOM neural network［J］.Automation of Electric Power Systems，2008，32（15）：66-70，78.

［8］張少敏，趙碩，王保義，等.基于云計(jì)算和量子粒子群算法的電力負(fù)荷曲線聚類算法研究［J］. 電力系統(tǒng)保護(hù)與控制，2014，42（21）：93-98.ZHANG Shaomin，ZHAO Shuo，WANG Baoyi，et al.Research of power load curve clustering algorithm based on cloud computing and quantum particle swarm optimization［J］.Power System Protection and Control，2014，42（21）：93-98.

［9］宋易陽，李存斌，祁之強(qiáng).基于云模型和模糊聚類的電力負(fù)荷模式提取方法［J］. 電網(wǎng)技術(shù)，2014，38（12）：3378-3383.SONG Yiyang，LI Cunbin，QI Zhiqiang.Extraction of power load patterns based on cloud model and fuzzy clustering［J］.Power System Technology，2014，38（12）：3378-3383.

［10］TZORTZIS G F，LIKAS A C.The global Kernel K-means algorithm for cluster in feature space［J］.IEEE Transactions on Neural Networks，2009，20（7）：1181-1194.

［11］TSAPANOS N，TEFAS A，NIKOLAIDIS N，et al.A distributed framework for trimmed Kernel K-means clustering［J］.Pattern Recognition，2015，48（8）：2685-2698.

［12］史衛(wèi)亞，郭躍飛，薛向陽.一種解決大規(guī)模數(shù)據(jù)集問題的核主成分分析算法［J］. 軟件學(xué)報(bào)，2009，20（8）：2153-2159.SHI Weiya，GUO Yuefei，XUE Xiangyang.Efficient kernel principal component analysis algorithm for large-scale data set［J］.Journal of Software，2009，20（8）：2153-2159.

［13］胡中中.圖像信息多層次融合技術(shù)的研究［D］.南昌：南昌大學(xué)，2012.HU Zhongzhong.The research of multi-level fusion technology about image information［D］.Nanchang：Nanchang University，2012.

［14］ZHANG R，RUDNICKY A I.A large scale clustering scheme for Kernel K-means［C］∥International Conference on Pattern Recognition.Quebec City，Canada：IEEE，2002：289-292.

［15］CHITTA R，JIN R，HAVENS T C，et al.Approximate Kernel K-means：solution to large scale kernel clustering［C］∥ACM SIGKDD International Conference on Knowledge Discovery and Date Mining.San Diego，California，USA：［s.n.］，2011：895-903.

［16］SARMA T H，VISWANATH P，REDDY B E.A fast approximate Kernel K-means clustering method for large data sets［C］∥Recent Advances in Intelligent Computational Systems（RAICS）.Trivandrum，India：IEEE，2011：545-550.

［17］ERIC W.Commercial and residential hourly load profiles for all TMY3 locations in the United States［EB／OL］. （2013-07-02） ［2016-04-25］.http： ∥en.openei.org／datasets／dataset／commercialand-residential-hourly-load-profiles-for-all-tmy3-locations-in-theunited-states.