基于粒計算和雙尺度相似性的負荷曲線集成聚類算法

孫園，李秋雨，黃冬梅，孫玉芹，胡安鐸，孫錦中

(1.上海電力大學數理學院，上海市 201306；2.上海電力大學電子與信息工程學院，上海市 201306)

0 引 言

近年來，隨著碳達峰、碳中和目標的提出，積極推動構建以新能源為主體的新型電力系統，全力消納清潔能源，深入推進電能替代成為了我國亟待解決的重要問題[1-2]。為此，國家逐漸提高可再生能源的接入比例，能源不再高度集中，用戶在用電選擇上趨于多樣性，由此而帶來的電力負荷曲線多樣化給傳統的電力數據挖掘技術帶來了挑戰。其中，電力負荷曲線聚類技術是分析了解用戶用電特征的重要手段，也是電力數據挖掘技術的基礎，對于負荷數據預處理，異常用戶檢測，需求側管理和用電用戶精細分類有著重要的意義[3]。

傳統的聚類算法往往通過數值距離度量數據間的相似性[4-7]，而電力負荷作為典型的時間序列數據，數據本身存在著自相關性，即不同時刻的電力負荷往往是有一定關聯的，因此在對電力負荷曲線進行聚類時，負荷曲線自身的形態也是十分重要的分類依據[8-9]。文獻[10]提出了一種基于奇異值分解的日負荷曲線降維算法，該算法針對形態特征相似數值距離相近的高維數據有良好的分辨效果，但是對于形態特征相異、數值距離相近的高維數據的分辨效果有待提升。對于大規模數據集，單一的聚類算法很難同時滿足聚類效率與聚類精度兩方面的要求。基于此，文獻[11]提出了一種結合重采樣的負荷曲線集成聚類模型，在聚類效率和聚類效果上對比單一聚類都有較大的提升。文獻[12]提出了一種基于雙尺度相似性的集成譜聚類算法，對于各種形態的負荷曲線數據都有良好的識別效果，但是由于基聚類質量的差異，導致集成后的聚類效果仍有提升空間。文獻[13]提出了一種基于改進模糊C均值的聚類算法，優化了初始聚類中心的選取方法，但是忽略了負荷曲線形態對聚類結果的影響。文獻[14]提出了一種基于改進K均值的聚類算法，從負荷形態和數值距離2個方面考慮負荷曲線的相似性，但是針對不同的情況，形態相似性和數值相似性在聚類時的權重配比也不同，一定程度上限制了該算法的實際應用范圍。

本文綜合考慮電力負荷曲線的數值相似性和形態相似性，提出一種基于粒計算和雙尺度相似性的集成聚類算法，以皮爾森相關系數作為補充，彌補歐氏距離在形態相似性度量上的局限性，對于一些數值比較接近、形態也比較相似的負荷曲線，有很好的分辨效果，并利用粒度距離挑選基聚類參與集成，顯著提高聚類的質量并增強算法的穩定性。

1 相似性度量

負荷曲線聚類的目的是將數值相近、形態相近的負荷曲線歸為同一類，因此在進行負荷曲線聚類時，相似性度量方式的選取十分重要。歐氏距離是最廣泛使用的相似性度量方式，但在負荷曲線形態相似性度量上存在缺陷，而皮爾森系數在負荷曲線的形態相似性度量上有著優異的表現。因此本文采用歐式距離和皮爾森相關系數2種相似性度量方法相結合的方式，綜合考慮負荷曲線的數值相似性和形態相似性，有效提升負荷聚類的效果。

1.1 基于數值距離的相似性度量

歐式距離是數值距離相似性的度量方式，對于2個長度為m的時間序列數據x=(x1,x2,…,xm)和y=(y1,y2,…,ym)，其歐氏距離dx,y為：

(1)

式中：xt為時間序列數據x的第t維的值；yt為時間序列數據y的第t維的值。

1.2 基于形態特征的相似性度量

皮爾森相關系數是形態特征相似性的度量方式，對于2個長度為m的時間序列數據x=(x1,x2,…,xm)和y=(y1,y2,…,ym)，其皮爾森相關系數ρx,y為：

(2)

2 粒計算基本概念

粒計算通過模擬人腦的認知機制，將數據粒化為不同大小的信息粒，信息粒越小，對數據的描述也越精細。粒計算作為一種信息處理的方法，為負荷聚類提供了新的手段，對處理聚類中的不確定性問題有良好的效果。運用粒計算解決相關問題的重點在于如何構造信息粒，不同的粒化模型，信息粒的構造方法也不相同，本文的信息粒構造方法如下[15]：

定義1U=(x1,x2,…,xn)表示具有n條數據的集合，A=(a1,a2,…,am)表示每條數據具有m個特征，S=(U,A)表示一個信息系統。

定義2不可分辨關系I(B)。集合B是特征集A的子集，不可分辨關系I(B)可表示為：I(B)={(x,y)∈U×U|xi,aj=yi,aj,?a∈B},即若2個數據每個維度上的值都相同，則稱這2個數據具有不可分辨關系。

定義3信息粒度G(A)。對于一個信息系統S=(U,A)，U/A={X1,X2,…,Xk}表示數據集U在特征集合A上被劃分為k個不可分辨關系，即劃分為k個簇。信息粒度的測量方法有很多，本文采用文獻[16]提出的信息粒度的定義：

(3)

式中：|U|表示整個數據集中數據的個數；|Xi|表示第i個簇所包含數據的個數。信息粒度的大小描述了聚類的不確定性，信息粒越小，聚類的確定性越高。例如有4個物體，A物體為黑色方形，B物體為黑色圓形，C物體為白色方形，D物體為白色圓形。若按照形狀劃分，則物體A和C應劃分為一類，B和D劃分為一類。若按照顏色劃分，則物體A和B應劃分為一類，C和D劃分為一類。這2種劃分方法具有同樣的粒度大小，因此也具有相同的不確定性。若按照顏色和形狀2個特征進行劃分，則A、B、C和D四個物體各成一類，相較于前2種劃分方法，按照顏色和形狀進行劃分的方法粒度更小，確定性也更高。

定義4粒度距離d(p1,p2)對于2個信息粒度相同但具體分類情況不同的2種聚類方式，雖然其具有相同的不確定性，但是這2種聚類方式是不等價的。本文采用文獻[17]所定義的粒度距離來度量2個聚類結果的差異：

(4)

式中：[xi]p1表示基聚類p1中，數據xi所屬的簇中包含的數據集合；[xi]p2表示基聚類p2中，數據xi所屬的簇中包含的數據集合。粒度距離越大，表示2個聚類結果的差異性越大。

3 基于粒計算的集成聚類算法

聚類集成是一種將多個弱聚類集成為一個強聚類的方法，當選擇的基聚類在準確性和多樣性上都有良好的表現時，使用聚類集成能夠得到更好的聚類結果，并且算法將具有更好的穩定性。聚類集成算法通常比單一聚類算法聚類結果更好，也更加穩定。一般來說，聚類集成算法有2個主要步驟：生成基聚類和整合基聚類。傳統的集成聚類算法忽略了基聚類的質量和基聚類之間的差異性，所有的基聚類成員都參與到最終的集成中，這樣不僅會產生巨大的計算成本，并且低質量的基聚類也會對最終聚類結果的準確性產生影響。因此，本文提出一種基于粒度距離的基聚類選擇方法，綜合考慮基聚類的質量和多樣性，選擇部分基聚類參與集成。

3.1 基于粒度距離的基聚類挑選準則

傳統的集成聚類算法通常將所有的基聚類都納入集成框架中，然而并非所有的基聚類都對提升聚類結果有幫助，有些聚類質量較差的基聚類甚至會拉低最終的聚類質量。除此之外，由于聚類目標一致，所有基聚類都是將相似性強的數據歸為一類，因此會導致大部分基聚類所包含的信息幾乎沒有差異，即大部分基聚類在參與集成時所提供的信息是重復的，大大提高了計算成本。因此，本文提出一種基于粒度距離的基聚類挑選準則，目的是挑選出聚類質量好并且彼此間差異性較大的基聚類參與集成，即被挑選出來的基聚類應該與所有的基聚類盡可能相似，而相似部分則被認為是更加接近真實分類結果。與此同時，被挑選出來的基聚類之間應該有盡可能多的不同之處，以便在集成時提供更多的信息。

3.1.1 挑選首個基聚類

P=(p1,p2,…,pH)表示關于數據集U的H個基聚類的集合，d(pi,pj)表示2個基聚類之間的粒度距離，定義基聚類pi和其他所有基聚類的粒度距離和D(pi,P)為：

(5)

式中：pi和pj表示H個基聚類中不同的2個基聚類。D(pi,P)衡量了基聚類pi和其他基聚類的相似性，粒度距離和最小的基聚類pi擁有和其他基聚類最大的相似性，聚類結果更接近真實情況，應將其挑選出來并放入已選基聚類的集合S中，參與最后的集成。

3.1.2 挑選余下基聚類

挑選出首個基聚類后，基聚類集P中還剩下H-1個基聚類等待挑選，將剩下的基聚類集合記為P′。在繼續挑選基聚類參與集成時，應當保證所挑選的基聚類pi與P′中基聚類的相似性最大并且與已選基聚類集S中的基聚類間的相異性最大。則基聚類pi的粒度距離和可進一步定義為：

(6)

D(pi,P′,S)越小，表示基聚類pi與未被挑選的基聚類之間的相似性越大，而與已被挑選的基聚類之間的相異性越大。基于此，將D(pi,P′,S)最小的基聚類pi挑選出來，并放入被挑選基聚類的集合S中，參與最后的集成，既能保證基聚類的質量，也能保證所挑選出的基聚類之間擁有較大的相異性，從而在集成時提供更多的信息。

3.2 構造相似度矩陣

在粒計算理論中，粒度的粗細代表了劃分能力的強弱，粒度越小，劃分能力越強，粒度越大，劃分能力越弱。因此，若2個數據在不同粒度水平都被劃分為同一類，則更傾向于認為這2個數據的真實標簽為同一類。如果2個數據在粒度較大的基聚類中被分為一類，而在粒度較小的基聚類中未被分為一類，則更傾向于認為這2個數據的真實標簽不是同一類。基于此，本文提出了一種基于粒度大小的相似度矩陣構建方式：

(7)

(8)

式中：δλ(xi,xj)表示不同粒度水平的基聚類，數據xi和xj是否在同一個簇中對最終xi和xj的相似度的影響程度大小；H′為基聚類的個數；kλ表示第λ個基聚類中有kλ個簇；Pλ(xi)表示xi在第λ個基聚類中被歸入的簇；aij為相似度矩陣An×n中第i行第j列的數據，表示數據xi和xj的相似程度，aij越大，表示數據xi和xj的相似度越大，因此所得的矩陣A=(aij)即為給定數據集U的相似度矩陣。

3.3 基于粒計算的聚類集成算法的算例分析

給定數據集U=(x1,x2,…,x10)，對此數據集采用5種不同的聚類算法得到5個基聚類P=(p1,p2,…,p5)，具體分類情況為：

(9)

粒度距離d(pi,pj)越大，表明基聚類pi和pj的差異性越大。

3.3.1 挑選首個基聚類

顯然，粒度距離和最小的基聚類p1擁有和其他基聚類最大的相似性，其聚類結果更接近真實情況，應將其挑選出來，并放入被挑選基聚類的集合S中。

3.3.2 挑選余下基聚類

顯然，粒度距離和最小的基聚類p4擁有與未被挑選的基聚類之間的最大相似性，且與已被挑選的基聚類之間的相異性最大，應當將其挑選出來，并放入被挑選基聚類的集合S中。

重復上一步，直到被選基聚類集合S中的基聚類個數大于等于H/2，得到最終參與集成的基聚類集合S={p1,p4,p5}。

3.3.3 構造相似度矩陣

3.4 層次聚類

層次聚類分為凝聚法和分裂法2種方式[18]，本文采用較為常用的凝聚層次聚類算法。層次聚類的每一步都是將aij最大的數據xi和xj歸為一類得到新的簇，并更新相似度矩陣，直到所有的數據最終歸為一類或達到設定的終止條件時，算法結束，得到最終的聚類結果。

3.5 聚類評價指標

聚類評價指標是評價聚類算法優劣，聚類結果好壞的有效手段，主要分為外部有效性指標、內部有效性指標和相對有效性指標。考慮到電力負荷數據大多為無標簽數據，因此本文僅采用內部有效性指標進行評價。

內部有效指標主要基于數據集的結構信息，從緊致性、分離性、連通性和重疊度等方面對聚類劃分進行評價，內部有效性指標主要有輪廓系數(silhouette coefficient，SIL)、戴維森堡丁指數(Davies-Bouldin index，DBI)、卡林斯基-哈拉巴茲指數(Calinski-Harabaz index，CHI)等[19-20]。

SIL描述了數據與所在簇的匹配程度，具體定義為：

(10)

式中：ai表示數據xi與同簇其他數據的平均歐式距離；bi表示數據xi與同簇其他數據的最小歐式距離。SIL指標描述了聚類結果的類內緊致度以及類間分離度，SIL越大，聚類結果越好。

DBI用類內數據到其聚類中心的距離估計類內的緊致性，用聚類中心之間的距離表示類間的分離性，具體定義為：

(11)

式中：f(Ci)表示第i個簇內數據之間的平均距離；d(Ci,Cj)表示第i個聚類中心和第j個聚類中心的歐式距離。DBI越小，類內越緊致，類間越分離，聚類效果越好。

CHI指標通過計算類中各個數據與聚類中心的距離平方和來度量類內的緊密度，通過計算各類中心點與數據集中心點距離平方和來度量數據集的分離度，具體定義為：

(12)

式中：tr(SB)表示類間離差矩陣SB的跡；tr(SW)表示類內離差矩陣SW的跡。CHI越大，表示類內越緊致，類間越分離，聚類效果越好。

3.6 算法流程

基于粒計算和雙尺度相似性的集成聚類算法包括生成基聚類、挑選基聚類、計算相似度矩陣和層次聚類4個部分，算法流程如圖1所示。具體流程描述如下。

圖1 基于粒計算和雙尺度相似性的聚類集成算法流程Fig.1 Flow chart of clustering ensemble model based on granular computing and dual-scale similarity

步驟1：用K-means對數據U=(x1,x2,…,xn)分別采用歐氏距離和皮爾森系數作為相似性度量并進行H/2次聚類，得到基聚類集P=(p1,p2,…,pH)。

步驟2：計算每一個基聚類pi和其他基聚類的粒度距離和D(pi,P)。

步驟3：將粒度距離和D(pi,P)最小的基聚類pi放入集合S中。

步驟4：繼續計算剩下未被挑選的每一個基聚類pi的粒度距離和D(pi,P′,S)。

步驟5：將粒度距離和D(pi,P′,S)最小的基聚類pi放入集合S中。

步驟6：判斷集合S中基聚類個數是否大于等于H/2個。若不滿足，則跳轉到步驟4。若滿足，跳轉到步驟7。

步驟7：根據式(7)計算相似度矩陣中的每一個元素。

步驟8：對相似度矩陣用層次聚類，得到最終聚類結果。

4 算例分析

本文采用nationalgridus上的公開電力負荷數據集，數據集包含1 140條電力日負荷曲線，數據采樣間隔為1 h。

4.1 算法有效性分析

取各種聚類算法和和本文所提基于粒計算和雙尺度相似性的負荷曲線集成聚類算法進行比較，從內部指標SIL、DBI、CHI三方面對比分析所提基于粒計算的集成聚類的有效性。對比算法包括：

算法1：基于歐式距離度量負荷曲線相似性的K-means算法，簡稱kmeans_euclidean；

算法2：基于皮爾森相關系數度量負荷曲線相似性的K-means算法，簡稱kmeans_person；

算法3：基于歐氏距離的譜聚類算法，簡稱spec_euclidean；

算法4：基于雙尺度相似性和粒計算的集成聚類算法(本文算法)。

由上文所述的算法流程中，為了得到不同粒度大小的基聚類，在用K-means算法獲取基聚類時，聚類數將隨機從[kmin,kmax]中選取。由于過粗或過細的粒都無法在集成時提供有效的聚類信息，因此kmin取值為2，kmax取值為n1/2。

對本文中的數據集分別采用上述的4種聚類算法，得到的聚類結果如圖2、3所示。其中，圖2展示了譜聚類的聚類結果，雖然譜聚類算法在各項指標上與本文算法接近，但是從圖2中可以看出，譜聚類的聚類結果存在比較明顯的誤分類情況，誤分類主要存在于曲線的數值距離相近但是曲線形態不相似的2類負荷曲線中。圖3展示了本文算法的聚類結果。從圖3中可以看出本文算法的聚類效果很好，并不存在誤分類情況，即使是數值和形態都很接近的兩類數據，本文算法也可以很好地分辨出來。

圖2 譜聚類算法聚類結果Fig.2 Clustering results of spectral clustering

圖3 本文算法聚類結果Fig.3 Clustering results of the proposed method

不同算法的聚類指標如表1所示。從表1中可以看出：1)本文所提算法在內部指標SIL、DBI、CHI上均遠遠優于K-means算法，與譜聚類算法接近；2)基于粒計算的集成框架具有將2個或者2個以上的弱聚類整合成一個強聚類的能力。

表1 不同算法的聚類指標Table 1 Clustering indices of different algorithms

4.2 算法穩定性分析

考慮到參與集成的基聚類均存在穩定性不高，受初始點選取影響較大的特點，因此接下來對本文算法進行穩定性分析。用本文算法對上文數據集重復進行20次聚類，得到結果如表2所示。

表2 聚類指標穩定性分析Table 2 Stability analysis of clustering indices

由表2可以看出，本文算法克服了基聚類穩定性差的缺點，具有良好的穩定性。

綜合以上算例分析可得：本文算法的聚類性能優于傳統的K-means算法和譜聚類算法，并且能夠將幾個聚類性能較弱且穩定性也較差的基聚類集成為一個聚類性能強、穩定性好的強聚類。在對于歐式距離和負荷形態都比較接近的負荷聚類問題上，傳統聚類無法有效解決，而本文算法則對解決此類問題有著優異的表現。

4.3 基聚類數量選取對聚類結果的影響

本文提出的算法綜合考慮了不同基聚類之間的相似性，可以有效提升聚類效果，并且基聚類的數量對于最終的聚類結果也有一定影響，算法采用了基于歐氏距離的K-means算法和基于皮爾森相關系數的K-means算法作為基聚類，且2種基聚類數量之比為1∶1，每種基聚類個數對于最終聚類結果的影響如圖4所示。

圖4 基聚類個數H對聚類結果的影響Fig.4 The influence of base clustering number on clustering results

由圖4可以看出，基聚類個數越多，集成聚類的效果越好，當每種基聚類的個數H大于6時，聚類結果趨于穩定。

在挑選基聚類參與集成時，應當綜合考慮基聚類的質量和彼此之間差異性，挑選出合適的基聚類參與集成，若挑選出的基聚類數量較少，則無法在集成時提供有效信息；若挑選出的基聚類數量較大，則會降低計算效率且質量差的基聚類會拉低最后聚類效果。圖5展示了基聚類數量分別為12、16、20時，基聚類選取的數量對最終結果的影響。

由圖5可知，當挑選出的基聚類數量為H/2時，各項聚類指標達到最優。

圖5 挑選出的基聚類個數對聚類結果的影響Fig.5 The influence of the number of selected base clusters on the clustering results

本文算法采用了基于歐氏距離的K-means算法和基于皮爾森相關系數的K-means算法作為生成基聚類的算法，按照不同比例選取基聚類算法，得到結果如表3所示。

表3 不同比例的基聚類選取方案的聚類指標對比Table 3 Clustering index comparison of base clustering selection schemes with different proportion

由表3可以看出，當2種基聚類算法之比為1∶1時，聚類各項指標達到最優。

4.4 粒度大小對聚類結果的影響

為了獲得不同粒度大小的基聚類，在生成基聚類時，聚類數在[2,kmax]中隨機選取。根據粒計算理論，過粗或者過細的信息粒在聚類集成時都無法提供太多的信息，且kmax取值過大時算法不收斂，因此kmax的取值應當適中，通過4.5節中的實驗表明，kmax值約為n1/2時，聚類算法的性能最優。

kmax越大，基聚類得到的簇也越多，即信息粒的個數越多，粒度越小，圖6展示了粒度大小對最終聚類結果的影響。由圖6可知，kmax取值為30時，各項聚類指標達到最優，也就是CHI曲線和SIL曲線的最大值點和DBI曲線的最小值點。

圖6 粒度大小對聚類結果的影響Fig.6 The influence of granularity on clustering results

4.5 本文算法在不同數據集上的最優參數對比

對比實驗的數據采用nationalgridus上的公開電力負荷數據集，數據集分別包含1 140條日負荷曲線，1 079條日負荷曲線和1 288條日負荷曲線。

對于3個數據集分別采用本文算法對其聚類，調整基聚類的比例分別為1∶2、1∶1、2∶1，得到的聚類指標如表4所示。

表4 基聚類比對不同數據集上的影響Table 4 The influence of base clusters’ proportion on different data sets

由表4可以看出，3個數據集上的最優基聚類比均為1∶1，且各類指標較另外2種比例都有較大提升。

本文算法在3個數據集上的最優參數，包括最優基聚類數、最優粒度大小和最優基聚類比例，如表5所示。

表5 算法在不同數據集上的最優參數Table 5 The optimal parameters of the algorithm on different data sets

由表5可以看出，算法在不同數據集上最優基聚類數和最優基聚類粒度則有隨數據量增長而變大的趨勢(上述所有實驗均采取運行20次取均值的方法得到最終的聚類指標)。

5 結 論

本文提出了一種基于粒計算和雙尺度相似性的集成聚類算法，通過構造粒度大小不同的基聚類，并用粒度距離來衡量基聚類之間的相似性，綜合考慮參與集成的基聚類的質量以及基聚類間的差異性，在保證聚類質量的前提下挑選出彼此差異性較大的基聚類參與集成，最后基于粒計算理論構建出相似度矩陣，采用層次聚類法對相似度矩陣聚類，得到最后的聚類結果。算例分析表明，基于粒計算的集成框架能有效提升聚類質量，提高算法的穩定性，所提算法在電力負荷曲線聚類上有著優異的表現。