王 超 楊 潔

（1.南京工程學(xué)院人工智能產(chǎn)業(yè)技術(shù)研究院 南京 211167）

（2.南京工程學(xué)院信息與通信工程學(xué)院 南京 211167）

1 引言

隨著我國(guó)電力系統(tǒng)的不斷發(fā)展以及人們生活質(zhì)量的不斷提高，電力系統(tǒng)的負(fù)荷特性變得越來(lái)越復(fù)雜，從而難以建立適用于不同負(fù)荷節(jié)點(diǎn)、不同時(shí)刻的負(fù)荷模型。然而負(fù)荷建模是電力系統(tǒng)調(diào)度、實(shí)時(shí)控制、運(yùn)行計(jì)劃和發(fā)展規(guī)劃的前提，負(fù)荷特性分析有助于提升負(fù)荷建模的精準(zhǔn)度。因此，對(duì)電力系統(tǒng)負(fù)荷進(jìn)行分析具有重要意義，聚類(lèi)分析是數(shù)據(jù)分析領(lǐng)域最重要的研究分支之一，被廣泛用于電力負(fù)荷分析，k-means 算法是聚類(lèi)分析中應(yīng)用最為廣泛的一種算法。

傳統(tǒng)的k-means 算法對(duì)初始聚類(lèi)中心敏感，聚類(lèi)結(jié)果隨不同的初始輸入而波動(dòng)。針對(duì)這個(gè)問(wèn)題，可以根據(jù)數(shù)據(jù)密度分布，基于距離公式計(jì)算每個(gè)點(diǎn)集所在區(qū)域的密度，然后依次根據(jù)權(quán)重找出下一個(gè)初始聚類(lèi)中心，不斷迭代得到k個(gè)初始聚類(lèi)中心［1～3］，也可以引入一個(gè)密度參數(shù)，并依據(jù)該參數(shù)選取k 個(gè)相對(duì)分散且密度參數(shù)較大的數(shù)據(jù)作為初始聚類(lèi)中心［4］。為了得到最合適的初始聚類(lèi)中心，Bian 等提出一種改進(jìn)的k-means 算法最佳聚類(lèi)數(shù)確定方法，對(duì)單一樣本類(lèi)的類(lèi)內(nèi)距離計(jì)算方法進(jìn)行優(yōu)化，使原有局部最優(yōu)的聚類(lèi)數(shù)優(yōu)化為全局最優(yōu)［5］。Cai 等實(shí)現(xiàn)了一種基于密度標(biāo)準(zhǔn)差優(yōu)化初始簇中心選取的改進(jìn)算法，通過(guò)計(jì)算樣本的平均密度和密度標(biāo)準(zhǔn)差，若小于密度標(biāo)準(zhǔn)差，則劃分為孤立點(diǎn)［6］。Wang等提出一種基于消息傳遞的算法，通過(guò)消息傳遞機(jī)制獲得高質(zhì)量的聚類(lèi)中心從而優(yōu)化聚類(lèi)的性能［7］。Asgarali Bouyer 等提出k 均值算法與粒子群優(yōu)化相結(jié)合，避免陷入局部最優(yōu)狀態(tài)，在有效性和穩(wěn)定性上有顯著提高，產(chǎn)生了高質(zhì)量且穩(wěn)定的聚類(lèi)結(jié)果［8］。Mao 等提出了基于灰色關(guān)聯(lián)度的初始聚類(lèi)中心選擇方法，能夠較好地找到初值，提高聚類(lèi)結(jié)果的穩(wěn)定性［9］。Feng 等提出了一種新的改進(jìn)的算法，通過(guò)建立最小生成樹(shù)，然后將其拆分為具有相關(guān)聚類(lèi)中心的k 個(gè)初始聚類(lèi)［10］。He 提出一種基于彩色空間通道的k 均值優(yōu)化初始中心聚類(lèi)分割方法，具有更高的穩(wěn)定性與準(zhǔn)確性［11］，以上方法都在一定程度上對(duì)算法的聚類(lèi)結(jié)果進(jìn)行了優(yōu)化。

孤立點(diǎn)的存在使聚類(lèi)中心的計(jì)算產(chǎn)生較大誤差，影響k-means 算法的聚類(lèi)效果。針對(duì)該問(wèn)題，美國(guó)著名經(jīng)濟(jì)學(xué)家托馬斯·謝林［12］提出了謝林模型，該模型所描述的是同質(zhì)性對(duì)于空間隔離的影響和作用。Yang 等引入謝林模型，使離群點(diǎn)自動(dòng)歸類(lèi)到其鄰域，同時(shí)，并對(duì)k-means 算法過(guò)程中的距離計(jì)算、初始聚類(lèi)中心選取環(huán)節(jié)進(jìn)行改進(jìn)［13］。Zhao等提出先利用算法數(shù)據(jù)進(jìn)行預(yù)處理，然后再對(duì)Canopy 結(jié) 果 進(jìn) 行k-means 細(xì) 聚 類(lèi) 的 優(yōu) 化 算 法［14］。Zhang 等提出基于離群因子的優(yōu)化聚類(lèi)算法，采用信息熵加權(quán)歐式距離作為相似性度量依據(jù)，利用k距離參數(shù)篩選出初始聚類(lèi)中心的候選集，最后根據(jù)其離群因子加權(quán)距離法優(yōu)化聚類(lèi)中心［15］。經(jīng)過(guò)實(shí)驗(yàn)結(jié)果表明，這些優(yōu)化后的算法比傳統(tǒng)的k-means算法具有更高的效率以及準(zhǔn)確率。

本文總結(jié)分析了各類(lèi)聚類(lèi)方法，對(duì)比其優(yōu)劣并針對(duì)k-means 算法對(duì)于孤立數(shù)據(jù)聚類(lèi)效果較差等缺點(diǎn)，考慮到變電站負(fù)荷數(shù)據(jù)的分散性，提出一種改進(jìn)型k-means 算法。該算法首先剔除離群點(diǎn)，再找出最佳聚類(lèi)中心數(shù)目并進(jìn)行分類(lèi)。實(shí)驗(yàn)結(jié)果表明，該算法可以使變電站負(fù)荷特性的聚類(lèi)效果進(jìn)一步提高，提高電力負(fù)荷分析與建模的精準(zhǔn)度。

2 聚類(lèi)相關(guān)技術(shù)簡(jiǎn)介

聚類(lèi)目的是對(duì)一組沒(méi)有標(biāo)簽的數(shù)據(jù)，按照特定的特征，把它們分成不同的類(lèi)，聚合成的一個(gè)類(lèi)叫做一個(gè)簇。本文將介紹幾種常見(jiàn)的聚類(lèi)算法以及聚類(lèi)評(píng)價(jià)指標(biāo)。

2.1 基于劃分的方法

基于劃分的方法就是逐步對(duì)簇中心不斷地迭代，每次迭代后再重新選擇聚類(lèi)中心，直到趨于穩(wěn)定。常見(jiàn)的代表算法有k-means，k-modes。本文提出的算法即是基于k-means 的改進(jìn)型算法，原算法內(nèi)容如下：

1）在數(shù)據(jù)集中隨機(jī)選擇初始化的k 個(gè)樣本作為數(shù)據(jù)中心；

2）計(jì)算數(shù)據(jù)集中每個(gè)樣本xi到k 個(gè)聚類(lèi)中心的距離，并將它們分配給最短間距的聚類(lèi)中心相對(duì)應(yīng)的聚類(lèi)；

3）針對(duì)每個(gè)類(lèi)別ci，再次找出它的聚類(lèi)中心aj（即屬于該類(lèi)的所有樣本的質(zhì)心），x 為樣本中數(shù)據(jù)。

計(jì)算方法如下：

重復(fù)上面兩步操作，直到達(dá)到某個(gè)中止條件（迭代次數(shù)、最小誤差變化等）。

2.2 基于層次的方法

這類(lèi)聚類(lèi)方法無(wú)需人為指定簇個(gè)數(shù)，并且距離閾值的選擇對(duì)最終聚類(lèi)結(jié)果影響不大，始終會(huì)傾向于給出更好地聚類(lèi)結(jié)果，而不像其他算法很依賴(lài)參數(shù)。代表算法有基于點(diǎn)分配的大規(guī)模聚類(lèi)算法CRUE（Clustering Using Representative）。基于層次的聚類(lèi)算法又包括自底而上的合并聚類(lèi)和自頂向下的分裂聚類(lèi)。

2.3 基于密度的方法

該方法是將數(shù)據(jù)密度較高的區(qū)域連接起來(lái)，針對(duì)于空間類(lèi)型數(shù)據(jù)進(jìn)行聚類(lèi)。這種集群方法將具有較高數(shù)據(jù)點(diǎn)密度的一組數(shù)據(jù)對(duì)象劃分為聚類(lèi)中心。常見(jiàn)的典型聚類(lèi)算法例如基于高密度連接區(qū)域的聚類(lèi)算法DBSCAN（Density-Based Spatial Clustering of Applications with Noise）。

2.4 基于網(wǎng)絡(luò)的方法

此類(lèi)算法的本質(zhì)是將數(shù)據(jù)集按照維數(shù)劃分為多層類(lèi)似網(wǎng)格的結(jié)構(gòu)，常見(jiàn)的基于網(wǎng)格聚類(lèi)的方法例如基于網(wǎng)格的多分辨率聚類(lèi)技術(shù)STING（Statistical Information Grid-based method）。

2.5 神經(jīng)網(wǎng)絡(luò)的方法

自組織映射（SOM）神經(jīng)網(wǎng)絡(luò)由輸入層和輸出層兩層結(jié)構(gòu)，輸出層中的節(jié)點(diǎn)代表其需要聚集的類(lèi)。這種方法不需要定義聚類(lèi)個(gè)數(shù)，SOM有很好的拓?fù)浣Y(jié)構(gòu)，可視性較好，但是需要調(diào)整很多參數(shù)。

2.6 聚類(lèi)評(píng)價(jià)指標(biāo)

1）Sum of Squared Error（和方差）

簡(jiǎn)稱(chēng)SSE，又稱(chēng)誤差平方和。該統(tǒng)計(jì)參數(shù)計(jì)算的是擬合數(shù)據(jù)和原始數(shù)據(jù)對(duì)應(yīng)點(diǎn)的誤差的平方和，計(jì)算公式如下：

式中，用yi表示真實(shí)的觀測(cè)值，用表示擬合值。SSE 越接近于0，說(shuō)明模型選擇和擬合更好，數(shù)據(jù)預(yù)測(cè)也越成功。

2）Elbow Method（肘部法則）

該方法通過(guò)以SSE 作為指標(biāo)，Elbow 意思是手肘，此種方法適用于k 值相對(duì)較小的情況，當(dāng)選擇的k 值小于真正值的時(shí)，k 每增加1，SSE 值就會(huì)大幅的減?。划?dāng)選擇的k 值大于最合適的值時(shí)，k每增加1，SSE值的變化就不會(huì)那么明顯。這樣正確的k值就會(huì)在這個(gè)轉(zhuǎn)折點(diǎn)elbow的地方。

3 改進(jìn)的k-means算法

3.1 局部離群因子

1）距離度量尺度

設(shè)對(duì)于沒(méi)有相同點(diǎn)的樣本集合D，共有n 個(gè)檢測(cè)樣本，數(shù)據(jù)維數(shù)為m，即：

式中，Xi為集合中任一檢測(cè)樣本，xi1、xi2、xi3以及xim為Xi各維度數(shù)據(jù)。

針對(duì)數(shù)據(jù)集D 中的任意兩個(gè)數(shù)據(jù)點(diǎn)Xi，Xj，通常使用Eucild（歐幾里得）距離：

式中，Xik和Xjk分別是Xi，Xj在第k維的坐標(biāo)。

2）第k距離（k-distance）

第k 距離就是距離o 第k 遠(yuǎn)的點(diǎn)到o 的距離（除了點(diǎn)o），記作dk(o)。

3）第k距離鄰域（k-distance neighborhood）

設(shè)O 為圓心，第k 距離鄰域是包含任意到圓心距離小于第k 個(gè)點(diǎn)到圓心距離的點(diǎn)的集合，記作Nk(o)。

4）可達(dá)距離（rechability distance）

基于上述第k距離，給定參數(shù)k時(shí)，數(shù)據(jù)點(diǎn)p 到數(shù)據(jù)點(diǎn)o 的可達(dá)距離reach-dist（p，o）為數(shù)據(jù)點(diǎn)o 的第k 距離和數(shù)據(jù)點(diǎn)p 與點(diǎn)o 之間的直接距離的最大值。

定義為

5）局部可達(dá)密度（Local Rechability Density）

定義所有與點(diǎn)p 的距離小于等于k-distance（p）的數(shù)據(jù)點(diǎn)集合稱(chēng)為p 的k 最近鄰，此時(shí)數(shù)據(jù)點(diǎn)p的局部可達(dá)密度定義為它與k 最近鄰的數(shù)據(jù)點(diǎn)平均可達(dá)距離的倒數(shù)。

公式如下：

6）局部離群因子（Local Outlier Factor，LOF）

局部離群因子即點(diǎn)p 鄰域的平均局部可達(dá)密度與局部可達(dá)密度的比值。

計(jì)算方法如下：

3.2 算法

本文算法主要分為兩步，首先區(qū)分離群點(diǎn)集和正常點(diǎn)集（較高密度點(diǎn)集），再去除離群點(diǎn)集對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)。由于數(shù)據(jù)之間量綱的不相同，不方便比較。本算法對(duì)數(shù)據(jù)采用0-1 規(guī)格化處理，具體計(jì)算方法如下：

以下為算法流程：

輸入：數(shù)據(jù)集X；

輸出：正常數(shù)據(jù)集X1，離群點(diǎn)數(shù)據(jù)集X2，聚類(lèi)數(shù)k 和聚類(lèi)結(jié)果；

1）隨機(jī)選取k個(gè)中心點(diǎn)；

2）記錄k鄰域距離k-distance（p）；

3）獲取第k 距離鄰域內(nèi)的每一個(gè)點(diǎn)到中心點(diǎn)的距離，并按從小到大排序；

4）獲取每一個(gè)樣本點(diǎn)的離群因子值；

5）計(jì)算離群因子值；

6）根據(jù)閾值劃分離群點(diǎn)與正常點(diǎn)；

7）得到一個(gè)正常數(shù)據(jù)集X1和一個(gè)離群點(diǎn)數(shù)據(jù)集X2；去除離群點(diǎn)數(shù)據(jù)集X2；

8）對(duì)正常數(shù)據(jù)集X1進(jìn)行規(guī)格化處理；

9）將聚類(lèi)中心個(gè)數(shù)k設(shè)為2到8之間；

10）每次迭代30次，避免局部最優(yōu)；

11）計(jì)算不同簇?cái)?shù)所對(duì)應(yīng)的簇內(nèi)SSE值；

12）繪制簇內(nèi)SSE值與k值關(guān)系的曲線；

13）根據(jù)elbow method（肘部法則）判斷最佳聚類(lèi)數(shù)k；

14）用k-means進(jìn)行聚類(lèi)，獲得最終聚類(lèi)結(jié)果。

4 實(shí)驗(yàn)與分析

4.1 數(shù)據(jù)來(lái)源

變電站負(fù)荷特性分類(lèi)是利用各個(gè)變電站或負(fù)荷節(jié)點(diǎn)的負(fù)荷構(gòu)成統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分類(lèi)。本文實(shí)驗(yàn)數(shù)據(jù)來(lái)自山東省變電站用電負(fù)荷數(shù)據(jù)，主要包括站名、地區(qū)以及工業(yè)、居民、商業(yè)、農(nóng)業(yè)、其他這五個(gè)行業(yè)占變電站所有負(fù)荷的百分比，總共183 條數(shù)據(jù)。列舉前9行數(shù)據(jù)如表1所示。

表1 山東省變電站統(tǒng)計(jì)數(shù)據(jù)

4.2 實(shí)驗(yàn)流程

1）輸入變電站數(shù)據(jù)集；

2）采用原算法和改進(jìn)算法分別對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)分析；

3）根據(jù)SSE 與k 值關(guān)系生成聚類(lèi)評(píng)價(jià)函數(shù)圖，并對(duì)兩種算法生成的函數(shù)圖像對(duì)比；

4）統(tǒng)計(jì)兩種算法在不同類(lèi)別下SSE 值并做對(duì)比；

5）經(jīng)過(guò)比較，采用更優(yōu)算法聚類(lèi)結(jié)果作為最終實(shí)驗(yàn)結(jié)果；

6）對(duì)最終聚類(lèi)結(jié)果進(jìn)行負(fù)荷特性分析并歸類(lèi)。

4.3 實(shí)驗(yàn)結(jié)果

為了便于直觀理解SSE值與k值之間的關(guān)系和觀察拐點(diǎn)，將SSE 值擴(kuò)大10 倍，使得數(shù)據(jù)關(guān)系更加清晰。

1）原算法聚類(lèi)評(píng)價(jià)指數(shù)函數(shù)圖像如圖1 所示，此時(shí)函數(shù)曲線較為平滑，拐點(diǎn)并不明顯，不易確定最佳聚類(lèi)個(gè)數(shù)，容易造成聚類(lèi)效果不理想。

圖1 原算法聚類(lèi)評(píng)價(jià)函數(shù)

2）本文算法聚類(lèi)評(píng)價(jià)指數(shù)函數(shù)圖像如圖2 所示，此時(shí)通過(guò)肘部法則，判斷函數(shù)曲線在k=6 時(shí)拐點(diǎn)較為明顯，最佳聚類(lèi)個(gè)數(shù)為6。

圖2 改進(jìn)算法聚類(lèi)評(píng)價(jià)函數(shù)

本文基于誤差平方和（SSE）作為聚類(lèi)評(píng)價(jià)指標(biāo)，兩種算法得到的統(tǒng)計(jì)數(shù)據(jù)如表2 所示，由本文提出的改進(jìn)算法得到的各類(lèi)下SSE 的值相對(duì)于傳統(tǒng)k-means 算法的結(jié)果有了明顯的降低，各類(lèi)變電站負(fù)荷數(shù)據(jù)之間關(guān)系的緊密性顯著提高。綜上，本文提出的算法可以較為明顯地提升聚類(lèi)效果。

表2 兩種算法在不同類(lèi)別下SSE值統(tǒng)計(jì)數(shù)據(jù)

由表2 可知，當(dāng)聚類(lèi)數(shù)為6 時(shí)，SSE 值為0.0938數(shù)值最小，這也驗(yàn)證了肘部法則的準(zhǔn)確性。所以實(shí)驗(yàn)以聚為6類(lèi)作為最終結(jié)果，如圖3所示，圖中已將不同聚類(lèi)集以不同顏色標(biāo)注以便區(qū)分。其中6 個(gè)聚類(lèi)中心如表3所示。

圖3 最終聚類(lèi)結(jié)果分布圖

表3 各聚類(lèi)中心的負(fù)荷占比統(tǒng)計(jì)數(shù)據(jù)

綜上所述由表3 中各個(gè)聚類(lèi)中心的各行業(yè)耗能占比可以歸納為以下六類(lèi)負(fù)荷特性：

第1類(lèi)：高耗能工業(yè)負(fù)荷類(lèi)；

第2類(lèi)：普通工業(yè)負(fù)荷類(lèi)；

第3類(lèi)：工業(yè)居民混合負(fù)荷類(lèi)；

第4類(lèi)：居民工業(yè)負(fù)荷類(lèi)；

第5類(lèi)：農(nóng)業(yè)工業(yè)負(fù)荷類(lèi)；

第6類(lèi)：商業(yè)居民負(fù)荷類(lèi)。

5 結(jié)語(yǔ)

本文主要針對(duì)k-means 算法對(duì)于孤立數(shù)據(jù)（離群點(diǎn)）敏感等缺點(diǎn)，考慮到變電站負(fù)荷數(shù)據(jù)的分散性、復(fù)雜性以及隨機(jī)時(shí)變性，提出一種改進(jìn)型k-means 算法。該算法先剔除離群點(diǎn)，優(yōu)化初始聚類(lèi)中心的選擇，抗離群擾動(dòng)能力較強(qiáng)，再利用elbow method 找出最佳聚類(lèi)中心數(shù)目，最終再用k-means 對(duì)預(yù)處理后的數(shù)據(jù)進(jìn)行處理。經(jīng)過(guò)實(shí)驗(yàn)數(shù)據(jù)分析對(duì)比，該算法可以使變電站負(fù)荷特性數(shù)據(jù)的聚類(lèi)效果進(jìn)一步提高，提高電力負(fù)荷分析與建模的精準(zhǔn)度。