基于改進K-means聚類算法的供電塊劃分方法

韓 俊，談 健 ，黃 河，喬黎偉

（1.國網(wǎng)江蘇省電力公司經(jīng)濟技術(shù)研究院 規(guī)劃評審中心，江蘇 南京 210008；2.國網(wǎng)江蘇省電力公司 發(fā)展策劃部，江蘇 南京 210008）

0 引言

對于供電范圍較大的供電區(qū)域，110 kV（35 kV）變電站數(shù)量龐大、布點散亂，如果直接進行該區(qū)域的網(wǎng)架結(jié)構(gòu)優(yōu)化研究工作，那么其工作量將會非常大，方向性比較難把握，任務(wù)艱巨，且不一定收到很好的成效。

傳統(tǒng)規(guī)劃常以行政區(qū)域為邊界來劃分供電區(qū)域，沒有考慮電網(wǎng)的實際情況。本文將影響供電區(qū)域劃分的多種因素考慮在內(nèi)，將各種因素的影響量化，探索數(shù)學(xué)約束條件，以求尋找一種綜合考慮電網(wǎng)實際情況的供電區(qū)塊劃分方法。

為了進一步提高配電網(wǎng)優(yōu)化規(guī)劃［1-12］的效率及精細化程度，避免對不存在聯(lián)絡(luò)關(guān)系的變電站進行無謂的搜索計算，本文以聚類分析思想為基礎(chǔ)，提出了基于改進K-means聚類算法的供電塊劃分方法，將大范圍的供電區(qū)域合理地切割成若干小規(guī)模的供電塊，分別針對各個供電塊開展網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化規(guī)劃研究，這樣層次清晰、工作重點明確，且規(guī)劃效果明顯。

1 基于改進的K-means聚類分析算法

1.1 聚類分析的概念

所謂聚類就是按照事物的某些屬性，把事物聚集成類，使類間的相似性盡可能小，類內(nèi)相似性盡可能大。聚類是一個無監(jiān)督的學(xué)習(xí)過程，它同分類的根本區(qū)別在于：分類是需要事先知道所依據(jù)的數(shù)據(jù)特征，而聚類是要找到這個數(shù)據(jù)特征。因此，在很多應(yīng)用中，聚類分析作為一種數(shù)據(jù)預(yù)處理過程，是進一步分析和處理數(shù)據(jù)的基礎(chǔ)［13］。

一個能產(chǎn)生高質(zhì)量聚類的算法必須滿足下面2個條件［14］：類內(nèi)數(shù)據(jù)或?qū)ο蟮南嗨菩宰顝?；類間數(shù)據(jù)或?qū)ο蟮南嗨菩宰钊酢?/p>

1.2 K-means聚類算法的基本原理

K-means聚類算法是一種硬聚類算法，是典型的基于原型的目標(biāo)函數(shù)聚類方法的代表，它以數(shù)據(jù)點到原型（類別中心）的某種距離之和作為優(yōu)化的目標(biāo)函數(shù)，利用函數(shù)求極值的方法來得到迭代運算的調(diào)整規(guī)則［15-16］。

1.3 K-means聚類算法的優(yōu)點和不足

a.與層次聚類相比，K-means聚類算法可以得到更緊密的簇，尤其是對球狀簇；

b.對大數(shù)據(jù)集，K-means聚類算法是可伸縮和高效率的；

c.K-means聚類算法嘗試找出使平方誤差函數(shù)值最小的k個劃分，當(dāng)結(jié)果簇是密集的，而且簇和簇之間區(qū)別明顯時，效果較好；

d.K-means聚類算法需要用戶預(yù)先指定聚類的個數(shù)，但在大多數(shù)實際應(yīng)用中，最終的聚類個數(shù)是未知的，這在一定程度上限制了該聚類算法的應(yīng)用；

e.對于k個初始中心點的選取是隨機完成的，而初始中心點選取的不同會導(dǎo)致不同的聚類結(jié)果，這種隨機選取初始聚類中心的方法將會引起聚類結(jié)果的不穩(wěn)定性。

1.4 K-means聚類算法的改進策略

本文針對傳統(tǒng)K-means聚類算法的不足，從初始中心點的選取和劃分數(shù)k的確定這兩方面提出相應(yīng)的改進措施。

1.4.1 選取初始中心點的方法

本文針對K-means聚類算法的不足，提出了改進的初始中心點的選取方法，通過樣本間平均距離［17］的引入，能夠很好地體現(xiàn)數(shù)據(jù)的分布情況，使得初始中心點盡可能地趨向于比較密集的范圍內(nèi)，從而進行更好的聚類。

假設(shè)待聚類對象 X=｛xi|xi?RP，i=1，2，…，n｝，k個聚類中心用 Z1、Z2、…、Zk表示，有如下定義。

定義 1 2 個 P 維向量 xi=（xi1，xi2，…，xiP）T和 xj=（xj1，xj2，…，xjP）T間的距離用歐氏距離表示：

定義2 樣本點間的平均距離dmean為：

1.4.2 最佳聚類劃分數(shù)k的選取方法

K-means聚類算法在供電塊劃分方面的應(yīng)用是以確定的供電塊劃分數(shù)k為前提對變電站進行分塊劃分的。在實際操作中，k值是難以準確界定的，本次研究以類間類內(nèi)劃分BWP（Between-Within Proportion）指標(biāo)［18］來確定供電塊劃分的最佳分塊數(shù)。BWP指標(biāo)是一種基于樣本幾何結(jié)構(gòu)，以數(shù)據(jù)集中某個樣本為研究對象，對聚類結(jié)果進行有效性分析的指標(biāo)，主要計算公式如下：

其中，ni為第 i個供電分塊中的變電站數(shù)；aBWP（k）為供電塊劃分為k個時BWP指標(biāo)的平均值；argmax［］為一函數(shù)，其返回aBWP（k）取最大值時的k值。

該指標(biāo)反映了單個樣本的聚類有效性情況，指標(biāo)值越大，說明單個樣本的聚類效果越好。通過計算數(shù)據(jù)集中所有樣本的BWP指標(biāo)的平均值來分析該數(shù)據(jù)集的聚類效果，平均值越大，說明該數(shù)據(jù)集的聚類效果越好。

2 基于改進K-means聚類算法的供電塊劃分方法

2.1 供電塊劃分與點的聚類劃分間差異性分析

2.1.1 變電站圓形等效供電半徑的折算

為了綜合考慮變電站配置和負荷密度等多種因素，在供電塊劃分過程中就必須考慮變電站的供電范圍，供電塊劃分問題也因此由平面點劃分的問題轉(zhuǎn)化為面積域劃分的問題。本次研究為了便于供電塊的劃分，把變電站的供電范圍近似等效為圓。

a.供電范圍內(nèi)負荷密度均勻的情況。

當(dāng)變電站圓形等效供電范圍內(nèi)負荷密度均勻時，可按照目前計算變電站圓形供電半徑的方法。從規(guī)劃區(qū)域的角度出發(fā)，根據(jù)變電站圓形供電范圍內(nèi)負荷密度的大小和供電圓的面積，折算出的等效供電半徑可按下式計算：

其中，R為變電站單臺主變?nèi)萘浚籒為主變臺數(shù)；T為滿足主變N-1條件下的最大負載率；cosθ為功率因數(shù)；M為變電站圓形供電范圍內(nèi)的負荷密度；r為變電站圓形供電范圍的半徑。

b.供電范圍內(nèi)負荷密度不均勻的情況。

變電站圓形等效供電范圍包含不同負荷密度區(qū)域時的示意圖如圖1所示。

圖1 基于不同負荷密度的變電站等效供電范圍Fig.1 Equivalent power-supplying range of substation based on different load densities

以負荷等價為紐帶，經(jīng)分析有下式成立：

其中，S1、S2分別為負荷密度 M1、M2下部分等效供電圓的面積。經(jīng)過數(shù)學(xué)分析，式（6）不一定存在滿足要求的解，故在求解變電站圓形等效供電范圍的半徑時不能按照上式獲得精確解。

在變電站圓形等效供電范圍內(nèi)各種負荷密度的分塊所占面積求解的基礎(chǔ)上，得出變電站等效圓形供電范圍半徑近似解的表達式如下：

其中，m為變電站等效圓形供電范圍內(nèi)包含負荷密度的類數(shù)；Si（r′）為第i類負荷密度的分塊在變電站等效圓形供電范圍內(nèi)的面積，其為r′的函數(shù)；δ為靈敏度系數(shù)，表示誤差的范圍。

2.1.2 變電站界間距概念的定義及計算

a.問題的提出。

供電塊劃分的目的是為了便于各供電塊內(nèi)變電站之間聯(lián)絡(luò)結(jié)構(gòu)的優(yōu)化規(guī)劃，而變電站之間是否互聯(lián)與變電站之間的地理距離和變電站各自的供電范圍都有緊密的聯(lián)系。同時，變電站圓形等效供電范圍的確定就為變電站間互聯(lián)與否的判斷提供了參考依據(jù)。

從圖2可以看出，左圖中變電站sub1和變電站sub2間的地理距離d1，2小于右圖中變電站sub3和變電站sub4間的距離d3，4。假設(shè)變電站的供電范圍為圓形，在左圖中，由于變電站附近負荷密度過大，供電半徑很小，這2座變電站的供電范圍沒有交集，因此2座站互聯(lián)的可能性較??；相反在右圖中，由于變電站附近負荷密度很小，供電半徑較大，2座變電站的供電范圍出現(xiàn)了重合的部分，因而變電站之間建立聯(lián)絡(luò)的可能性較大。因此本文在進行供電塊劃分時，不能簡單地考慮變電站間的歐氏（地理）距離，故在此基礎(chǔ)上引入了變電站界間距的概念。

圖2 不同地理距離下2座變電站間的聯(lián)絡(luò)示意圖Fig.2 Schematic diagram of connection between substations for different geographic distances

b.變電站界間距的概念及計算方法。

變電站界間距是指在假定2座變電站供電范圍為圓形的前提下，其圓形供電范圍的近側(cè)圓弧之間相離程度的大小。設(shè)平面上2座變電站的編號為i、j，其坐標(biāo)分別為（xi0，yi0）和（xj0，yj0），等效圓形供電半徑分別為ri和rj，則兩者之間的歐氏（地理）距離d（i，j）和界間距 D（i，j）間的關(guān)系如下所示：

由上式可知，D（i，j）的取值有 3 種類型：D（i，j）>0；D（i，j）=0；D（i，j）<0。 不同取值情況下的變電站界間距示意圖如圖3所示。

D（i，j）>0表示2座變電站的圓形供電范圍沒有交集，說明2座變電站不存在共同帶負荷的情況，D（i，j）越大，2座變電站建立聯(lián)絡(luò)的可能性越小；D（i，j）≤0表示2座變電站的圓形供電范圍有交集，說明2座變電站可能存在共同帶負荷的情況，D（i，j）越小，變電站間建立聯(lián)絡(luò)的可能性越大。

2.2 改進K-means聚類算法在供電分塊中的應(yīng)用

2.2.1 供電塊初始聚類中心的形成

在已知供電塊劃分塊數(shù)k的基礎(chǔ)上，首先生成一組供電分塊初始聚類中心的位置集合。每座變電站都可以用二維平面上的一個點表示，每一個點存在（x，y）坐標(biāo)。結(jié)合變電站的實際地理位置，以變電站界間距的計算結(jié)果為依據(jù)，篩選出最可能存在于同一分塊內(nèi)的變電站，以其界間距的中心點作為分塊聚類中心的初始位置，迭代過程中利用每次迭代各供電分塊中變電站的不同，在初始位置的基礎(chǔ)上搜索，找到最終合理的位置值。供電分塊初始聚類中心形成的具體步驟如下。

圖3 不同取值情況下的變電站界間距示意圖Fig.3 Schematic diagram of distances between substation boundaries for different values

a.將供電區(qū)域內(nèi)的變電站編號為1、2、…、n，按式（8）計算任意 2 座變電站間的界間距，記為 D（i，j），并計算所有界間距的平均值，如下所示：

b.對所有界間距按照由小到大的順序進行排序，存入向量D中，將最小的界間距對應(yīng)的中心點作為第一個初始聚類中心，其坐標(biāo)z1計算方法如式（10）所示：

其中，center（xi，j，yi，j）為變電站 i和變電站 j的界間距的中心點坐標(biāo)。

c.計算出變電站次小界間距所對應(yīng)的中心點坐標(biāo)，同時算出它與先前已確定的初始聚類中心的距離并與界間距的平均值lmean進行比較，若它與先前已有初始聚類中心的距離均大于等于lmean，則將該界間距對應(yīng)的中心點作為下一個初始聚類中心；否則，重復(fù)步驟c。

d.當(dāng)初始聚類中心的個數(shù)沒有達到k，而所有界間距卻又全部經(jīng)過判斷時，則動態(tài)縮小界間距的平均值，并清空步驟c中尋找到的初始聚類中心，重復(fù)步驟c。

e.當(dāng)初始聚類中心的個數(shù)達到k時，則認為初始聚類中心完全形成，待迭代結(jié)束后求得最終的聚類結(jié)果。

2.2.2 最佳供電塊劃分數(shù)k的確定

設(shè)K=｛X，R｝為供電塊劃分的聚類空間，其中X=｛x1，x2，…，xn｝為變電站樣本集合，假設(shè) n 座變電站樣本被劃分為k個分塊，則有相似定義如下。

定義1 定義第i個供電分塊中的第j座變電站的最小塊間界間距b（i，j）為該變電站到其他每個供電分塊中變電站平均界間距的最小值，根據(jù)供電塊劃分的實際情況，應(yīng)該有 b（i，j）>0 成立，如下式所示：

其中，c表示供電塊被分為c類；nl為第l類供電塊中變電站數(shù)為第l類的第p個樣本為第i類的第j個樣本。

定義2 定義第i個供電分塊中的第j座變電站的塊內(nèi)界間距w（i，j）為該變電站到第i個分塊中其他所有變電站界間距折算值的平均值，如下式所示：

特別指出的是，根據(jù)變電站界間距的定義和計算方法，供電塊內(nèi)的變電站界間距計算值有正有負。為了提高供電塊劃分的有效性，在計算塊內(nèi)界間距w（i，j）時需要把變電站界間距折算成非負值。

圖4 變電站界間距折算示意圖Fig.4 Schematic diagram of distance conversion between substation boundaries

如圖4所示，左圖中變電站間界間距小于0，右圖中變電站間界間距大于0，且兩者絕對值相等。顯然，左圖中2座變電站的塊內(nèi)緊密性要強于右圖，因此左圖中變電站間界間距的折算值應(yīng)要小于右圖中變電站間的界間距，因此，引入折算因子ε。

定義3 定義第i個供電分塊中的第j座變電站的聚類界間距abw（i，j）為該變電站最小塊間界間距 b（i，j）與塊內(nèi)界間距 w（i，j）之和。

定義4 定義第i個供電分塊中的第j座變電站的聚類離差界間距sbw（i，j）為該變電站最小塊界間距 b（i，j）與塊內(nèi)界間距 w（i，j）之差。

定義5 定義第i個供電分塊中的第j座變電站的類間類內(nèi)劃分指標(biāo)BWP（i，j）為該變電站的聚類離差界間距和聚類界間距的比值，如下式所示：

BWP指標(biāo)是從變電站界間距測度考慮，就是使供電分塊內(nèi)變電站間界間距極小化而供電分塊間界間距最大化的劃分是最優(yōu)劃分。但是這樣可能會導(dǎo)致選取的劃分方案中某些供電分塊內(nèi)變電站數(shù)量過多，而某些供電分塊內(nèi)出現(xiàn)孤立變電站的情況。因此，為了解決這一問題，本文定義了供電塊劃分均衡性指標(biāo)，對aBWP（k）值較大的幾種劃分方案計算其均衡性水平，然后綜合考慮2種指標(biāo)水平確定供電塊最佳劃分數(shù)k。供電塊均衡性指標(biāo)β（k）的計算方法如式（15）所示：

需要指出的是，該指標(biāo)為負型指標(biāo)，即指標(biāo)取值越小，供電塊的均衡性水平越高，在此基礎(chǔ)上確定供電塊劃分的最佳分塊數(shù)。

2.2.3 供電塊劃分的整體流程

基于改進K-means聚類算法的供電塊劃分詳細流程如圖5所示，圖中η為界間距平均值lmean的動態(tài)調(diào)整系數(shù)。

需要特別指出的是，當(dāng)聚類集合中只有1座變電站時，其聚類中心在迭代過程中保持不變。

3 實際算例分析

某地區(qū)遠景期規(guī)劃建設(shè)110kV（35kV）變電站28座，其中變電站布點規(guī)劃結(jié)果及負荷密度分布情況如圖6所示。

圖5 基于改進K-means聚類算法的供電塊劃分流程Fig.5 Flowchart of power-supplying block partition based on improved K-means clustering algorithm

選取該地區(qū)左下角為原點建立坐標(biāo)軸，則可以得到所有變電站的相對位置坐標(biāo)，以遠景期規(guī)劃變電站的配置規(guī)模和區(qū)塊負荷密度為基礎(chǔ)數(shù)據(jù)，折算每座變電站的圓形等效供電半徑。然后根據(jù)本文提出的基于改進的K-means聚類算法進行供電塊的劃分，供電塊劃分數(shù)k的取值范圍為2～10，不同劃分方案情況下平均BWP指標(biāo)和均衡性指標(biāo)β的計算結(jié)果如表1所示。

結(jié)合表1中不同供電塊劃分方案下的平均BWP值和供電塊劃分均衡性水平指標(biāo)β的對比分析，劃分數(shù)為9時的平均BWP值遠遠高于其他劃分方案，因此，該供電區(qū)域劃分方案選取劃分數(shù)為9時的方案為最佳供電塊劃分方案，供電塊最終劃分方案如圖7所示。

圖6 某地區(qū)遠景期變電站規(guī)劃布點及負荷密度分布圖Fig.6 Planned substation allocation and load density distribution for a region

表1 不同劃分方案情況下平均BWP指標(biāo)和均衡性指標(biāo)β的計算結(jié)果Table 1 Calculative average BWP index and equilibrium index β for different partition schemes

通過采用改進的K-means聚類算法將含28座變電站的供電區(qū)域合理地劃分為若干小規(guī)模的供電塊，供電塊內(nèi)的變電站間具有非常緊密的聯(lián)系，同時供電塊間變電站之間的聯(lián)絡(luò)相對較為薄弱。鑒于此特性，重點對各個供電塊開展配電系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化規(guī)劃將會以最有效、最便捷的路徑達到滿足整個地區(qū)配電系統(tǒng)的精益化規(guī)劃的需求。

圖7 某地區(qū)遠景期供電塊最佳劃分方案示意圖Fig.7 Schematic diagram of optimal power-supplying block partition scheme planned for a region

4 結(jié)論

為了進一步提高配電系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化規(guī)劃的效率及精細化程度，本文以聚類分析思想為基礎(chǔ)，提出了基于改進K-means聚類算法的供電塊劃分方法，主要工作如下：

a.從初始聚類中心的選取和最佳聚類劃分數(shù)的確定這2個方面對傳統(tǒng)的K-means聚類算法進行改進；

b.在透徹分析供電塊劃分與平面點的劃分間差異性的基礎(chǔ)上，以變電站圓形供電模型為基礎(chǔ)，提出了不同負荷密度下等效半徑的折算方法，同時定義了變電站界間距等概念，將供電塊的劃分問題由平面點的劃分轉(zhuǎn)化為面積域的劃分；

c.將改進的K-means聚類算法應(yīng)用到變電站供電塊的劃分中，建立了基于改進K-means聚類算法的供電塊劃分的詳細流程，最后通過實際算例驗證了本文所提方法的科學(xué)性和合理性。