基于動態層次K-Modes的電網數據聚類分析

林紅陽1，杜 翼1，劉 林1，易 楊1，蔡 菁，馬漢斌

(1. 國網福建省電力有限公司經濟技術研究院，福建 福州 350012；2. 國網信通億力科技有限責任公司，福建 福州 350000)

隨著電力工業的發展與電力計量體系的不斷完善，在電力用戶側積累了海量的歷史數據。針對既有數據，展開用戶用電行為特性的挖掘，可以為電力公司開展相應電價制定與需求側管理工作提供有益指導[1]。聚類分析是數據挖掘(data mining)的重要組成部分，作為一種無監督學習方法，根據其思想的不同，聚類算法主要可分為以下5種方法：劃分法(partitioning method)、層次法(hierarchical method)、基于密度法(density-based method)、基于網格的方法(grid-based method)、基于模型法(model-based method)，并且在此基礎上發展出更為靈活的組合及變形。而K-means算法作為一種基礎的劃分法，從提出以來就受到人們的普遍關注，至今仍有不少學者對K-means及其同類型方法在應用及算法上做出研究貢獻[2-11]。K-modes作為K-means的一種變形，能夠對類屬型數據進行分類，其主要區別在于中心和距離的定義[12]。而層次聚類法作為另一種廣泛被人們使用的算法，其優勢在于分類準確且可以生成直觀的分類樹，便于判斷類的數目；但其計算量過大，算法復雜度至少為O(n2)，僅適用于小規模數據聚類。也有將兩種或多種傳統聚類算法結合而成的新算法，例如層次K-means算法[3，11]。此類算法能夠保留每種算法的優良性并彌補算法缺陷，使得算法的適應性和準確性都得到提升。下面通過引入合適的聚類算法對廈門島內地區電力用戶數據進行試驗，以驗證算法的可行性，為進一步推廣至其他數據集籌備基礎。

1 算法介紹

1.1 K-modes算法

作為一種被普遍運用于各類問題的聚類算法，K-means常用于數值型數據的分類，距離一般采用歐氏距離，所以對其他類型數據，例如類屬型(0-1型)數據并不適用。作為改進，由Huang在1998年提出的K-modes算法在K-means的算法基礎上引入modes取代means(中心)，并提出差異匹配(matching dissimilarity)替代傳統的歐氏度量(距離)。正是引入差異度量(dissimilarity measure)這種距離計算方式，使得其能對類屬型數據進行有效的劃分。

K-modes算法從構造思想上與K-means基本一致[6，9]。定義信息集合(X,A,Q),其中X={xi|i=1,2,…,n}表示數據集合；A={ai|i=1,2,…,m}表示數據每一維度的屬性；Q={qi|i=1,2,…,k}表示k個分類，而{qi|i=1,2,…,k}表示每個類的中心(mode)。其中xij∈z,(i=1,2,…,n;j=1,2,…,m)表示樣本點xi在aj屬性上的取值。

定義任意兩點x,y的差異度量為d：

其中，

定義目標函數為

其中，

在上述3個條件下使目標函數F達到最小值，K-modes基本實現步驟如下：

1) 隨機選取k個modes。

2)計算每個數據點與k個modes的差異度量d(距離)，將每個數據點分入度量值最小的類。

3)判斷是否達到迭代終止條件(一般設置終止條件為分類結果不再改變)，若終止迭代則返回結果，否則進入步驟4)。

4)對每一類中所有數據點在每一維度上取眾數，更新每個類的mode：qzj=mode(xij|xi∈Qz),j=1,2,…,m,返回步驟2)。

1.2 層次K-means算法

K-means聚類算法復雜度為O(n)階，即不需要進行樣本點的兩兩距離計算，在處理一般聚類問題時速度較快。但K-means算法也存在2個公開問題：1)類數目無法自適應得到；2)算法僅能保證收斂到局部最優解。而層次聚類算法能夠得到較好的聚類結果，同時可以通過聚類系譜圖來指導確定類的數目，但由于其算法復雜度過大，當處理大規模數據時就會遇到困難。

由Arai于2007年提出的層次K-means[3]從一定程度上解決了這些問題。其利用所有在特定k值下運行K-means所得到的結果，這些結果可能均收斂到局部最優解，但通過大量結果所帶來的信息，結合層次聚類算法對其進行轉換便能確定出更為準確的K-means初始值中心點。

層次K-means算法主要步驟如下：

1) 取定k值，并進行p次重復的K-means計算，得到聚類中心點集合；

2)結合層次聚類法，對步驟1)所得的聚類中心點集合進行再聚類；

3)將步驟2)所得的聚類中心點作為K-means的初始聚類中心點，并運行K-means算法得到最終聚類結果。

1.3 層次K-modes算法

考慮到K-modes算法對類屬型數據的適應性，以及其在迭代過程中與K-means算法的相似性，因此提出層次K-modes算法。將K-modes算法與層次聚類算法進行結合，繼承兩種算法的優點而直接作用于類屬型數據。值得注意的一點是差異度量(dissimilarity measure)的計算快于同等維度的二范數計算，因此從速度上層次K-modes也比層次K-means更具優勢。其算法實步驟與層次K-means類似，不過類中心必須使用mode，并且在層次聚類時也必須選取適合類屬型數據的距離公式進行計算。

1.4 動態層次K-modes算法

進一步，還希望借助聚類系譜圖來選取適合的k值。層次K-modes中，由于固定了k值，因此進行p次相同k值的K-modes并完成層次聚類后所生成的系譜圖所呈現的劃分很大程度上受到所選取k的影響，通常與初始選取的k值相同。為了克服這個弱點，提出讓每次K-modes的k值變動起來，從而弱化人為選取k值的影響[14]。在這種改動下，p次K-modes帶來更多的分類信息，從而能從更廣范圍內尋找更優的k值。

動態層次K-modes主要算法步驟如下：

2)利用層次聚類法對集合M中的modes進行分類；

3)通過系譜圖選定適當的k值以及對應的modes；

4)利用步驟3)中結果作為初始條件進行一次K-modes，并返回結果。

2 數據特征提取

將曲線數據按照曲線形態進行聚類，考慮到直接利用原始數據進行聚類會忽略掉時間序列上段與段間的形態差異，造成聚類結果不合理。

如文獻[13]將原始數據進行平滑后取一階差分值，將原始矩陣X轉化為差分矩陣D，其每一行為di，由一個m維行向量構成，表示第i個差分后樣本；更進一步，分別將“±0.1×差分樣本極差”作為閾值t(di)。

(1)

式中，j=1,2,…,m。

對所有差分樣本進行式(1)處理后得到類屬型矩陣C,為n×m維的矩陣。其每一行為ci，由一個m維行向量構成，以此來反映曲線形態。

圖1 特征提取

圖1為數據特征提取圖，圖中的曲線為某樣本xi在經過平滑后得到，經過差分及式(1)處理后得到的圓點，表示在每一時刻該樣本曲線的升、平、降3種狀態，將連續型的時間序列數據轉化成類屬型的離散狀態值，從而提取出樣本的形態特征，可利用動態層次K-modes算法進行聚類。

3 算法實驗

3.1 模擬數據試驗

為了檢驗動態層次K-modes相較于傳統K-modes的優良性，首先使用計算機模擬出一個維度為10，類數目為3，類內樣本量分別為500、200、50的曲線數據集，如圖2至圖4所示，其中雙峰形類樣本數為500，單峰型類樣本數為200，單谷型類樣本數為50。

圖2 雙峰型類

圖3 單峰型類

圖4 單谷型類

進行算法比較前，首先給出分類準確率的計算規則為

式中，ni為當前聚類結果中第i類包含正確分類中最多一類的數目。

對于傳統的K-modes算法而言，k必須經由人工進行初始化。為了進行更客觀的比較，假定已知類數目為k=3，并利用K-modes算法對該模擬數據進行聚類，聚類結果如圖5所示。

圖5 普通K-modes聚類(k=3)

如圖5中各子圖以及圖2至圖4，分類準確度僅達到CE=47.87%，即該聚類結果大部分類都未能準確對應正確分類情況。

而使用動態層次K-modes算法對此模擬數據進行聚類，并不需要人為取定k值，而僅需通過返回的系譜圖來決定所希望的k值以及初始modes。取K-modes運行次數p=8，因此8次計算的k值分別為2～9。在層次聚類時選擇“hamming”距離，應用“average”的類間距計算方式，得到如圖6所示系譜圖。

圖6 聚類系譜

從圖6中可見，聚類樹在k=3時的高度差最為明顯，可從k=3處進行截取，同時返回對應的中心(modes)。在此基礎上進行一次K-modes可得到如圖7所示層次K-Modes聚類圖。

如圖7所示，在同樣k=3的情形下，動態層次K-modes相較于傳統K-modes，分類準確度達到CE=76.93%，明顯高于傳統K-modes；并且類數目k也能被正確確定，因此其分類效果明顯優于傳統K-modes。

圖7 層次K-modes聚類

3.2 真實數據試驗

所采用的真實數據為來自廈門某地區2016年3月1日至4月13日的用戶電流數據，為曲線數據。數據規模為44×9026×96，每一維度含義分別為：采集天數為44，用戶變壓器數目為9026，每日共96個觀測值(每日隔15 min一次觀測)。

考慮到用戶用電曲線基本以日為周期，因此對44天內所有用戶的每日96次觀測分別取平均值，將數據降維，得到矩陣X(9026×96)，其中矩陣每行xi為一個樣本，由一個96維行向量構成。

對X運用式(1)的數據處理方法，將其轉化成類屬型數據矩陣，并利用動態層次K-modes對數據進行分類。取K-modes的運行次數p=8，在層次聚類時同樣選擇“hamming”距離，類間距計算方式選擇“average”得到聚類系譜圖，如圖8所示。

對圖8聚類樹進行水平截斷，具有明顯高度差的分類情形為k=3、k=6。因此分別選取k=3和k=6的情形，給出中心(modes)作為初始值，進行K-modes聚類。

在k值為3的情形中，得到圖9所示分類結果。

圖9 層次K-modes聚類(k=3)

如圖9中3個子圖所示，前兩個類特征明顯，屬于雙峰型類，但峰型卻有差異；第一個類雙峰集中在30～70時段內，第二類中兩個峰在分布在24～50以及65至85時段內。在k=3的情形中，此算法抓住了曲線數據的主要形態特征給出合理的分類結果。

在k值為6的情形中，得到如圖10所示的分類結果。

圖10 層次K-modes聚類(k=6)

相較下，圖10所示的各類峰型均表現出較明顯的差異。相較于模擬數據，真實數據表現出了更復雜的分布特性。正是由于這種復雜性，很難簡單給出唯一的分類結果；正如圖8中聚類樹的枝干在k=3、k=6時都有明顯分化。

4 結 語

傳統K-modes算法與層次聚類算法結合，成功地將層次K-means的算法優點移植到類屬型數據中。并且所提出的動態層次K-modes算法還可以通過聚類系譜圖確定k值，一定程度上解決了k值須初始給定的公開問題。算法也具有更強的適應性和異常點識別等優良性質，可以對真實數據給出有效聚類結果。

考慮到動態層次K-modes算法從結果上雖然明顯優于傳統K-modes算法，但在進行聚類時仍會出現一定的錯分現象，在后續工作中考慮引入robust思想，無須將所有樣本帶入聚類迭代過程，而是僅選取一部分重要樣本進行迭代，以此提高算法準確度。同時在特征提取方面，也希望引入更精細化的自適應閾值給定，從數據角度提高聚類質量。