林紅陽(yáng)1，杜 翼1，劉 林1，易 楊1，蔡 菁，馬漢斌

(1. 國(guó)網(wǎng)福建省電力有限公司經(jīng)濟(jì)技術(shù)研究院，福建 福州 350012；2. 國(guó)網(wǎng)信通億力科技有限責(zé)任公司，福建 福州 350000)

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

1 算法介紹

1.1 K-modes算法

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

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

定義任意兩點(diǎn)x,y的差異度量為d：

其中，

定義目標(biāo)函數(shù)為

其中，

在上述3個(gè)條件下使目標(biāo)函數(shù)F達(dá)到最小值，K-modes基本實(shí)現(xiàn)步驟如下：

1) 隨機(jī)選取k個(gè)modes。

2)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與k個(gè)modes的差異度量d(距離)，將每個(gè)數(shù)據(jù)點(diǎn)分入度量值最小的類。

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

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

1.2 層次K-means算法

K-means聚類算法復(fù)雜度為O(n)階，即不需要進(jìn)行樣本點(diǎn)的兩兩距離計(jì)算，在處理一般聚類問(wèn)題時(shí)速度較快。但K-means算法也存在2個(gè)公開(kāi)問(wèn)題：1)類數(shù)目無(wú)法自適應(yīng)得到；2)算法僅能保證收斂到局部最優(yōu)解。而層次聚類算法能夠得到較好的聚類結(jié)果，同時(shí)可以通過(guò)聚類系譜圖來(lái)指導(dǎo)確定類的數(shù)目，但由于其算法復(fù)雜度過(guò)大，當(dāng)處理大規(guī)模數(shù)據(jù)時(shí)就會(huì)遇到困難。

由Arai于2007年提出的層次K-means[3]從一定程度上解決了這些問(wèn)題。其利用所有在特定k值下運(yùn)行K-means所得到的結(jié)果，這些結(jié)果可能均收斂到局部最優(yōu)解，但通過(guò)大量結(jié)果所帶來(lái)的信息，結(jié)合層次聚類算法對(duì)其進(jìn)行轉(zhuǎn)換便能確定出更為準(zhǔn)確的K-means初始值中心點(diǎn)。

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

1) 取定k值，并進(jìn)行p次重復(fù)的K-means計(jì)算，得到聚類中心點(diǎn)集合；

2)結(jié)合層次聚類法，對(duì)步驟1)所得的聚類中心點(diǎn)集合進(jìn)行再聚類；

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

1.3 層次K-modes算法

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

1.4 動(dòng)態(tài)層次K-modes算法

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

動(dòng)態(tài)層次K-modes主要算法步驟如下：

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

3)通過(guò)系譜圖選定適當(dāng)?shù)膋值以及對(duì)應(yīng)的modes；

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

2 數(shù)據(jù)特征提取

將曲線數(shù)據(jù)按照曲線形態(tài)進(jìn)行聚類，考慮到直接利用原始數(shù)據(jù)進(jìn)行聚類會(huì)忽略掉時(shí)間序列上段與段間的形態(tài)差異，造成聚類結(jié)果不合理。

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

(1)

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

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

圖1 特征提取

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

3 算法實(shí)驗(yàn)

3.1 模擬數(shù)據(jù)試驗(yàn)

為了檢驗(yàn)動(dòng)態(tài)層次K-modes相較于傳統(tǒng)K-modes的優(yōu)良性，首先使用計(jì)算機(jī)模擬出一個(gè)維度為10，類數(shù)目為3，類內(nèi)樣本量分別為500、200、50的曲線數(shù)據(jù)集，如圖2至圖4所示，其中雙峰形類樣本數(shù)為500，單峰型類樣本數(shù)為200，單谷型類樣本數(shù)為50。

圖2 雙峰型類

圖3 單峰型類

圖4 單谷型類

進(jìn)行算法比較前，首先給出分類準(zhǔn)確率的計(jì)算規(guī)則為

式中，ni為當(dāng)前聚類結(jié)果中第i類包含正確分類中最多一類的數(shù)目。

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

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

如圖5中各子圖以及圖2至圖4，分類準(zhǔn)確度僅達(dá)到CE=47.87%，即該聚類結(jié)果大部分類都未能準(zhǔn)確對(duì)應(yīng)正確分類情況。

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

圖6 聚類系譜

從圖6中可見(jiàn)，聚類樹(shù)在k=3時(shí)的高度差最為明顯，可從k=3處進(jìn)行截取，同時(shí)返回對(duì)應(yīng)的中心(modes)。在此基礎(chǔ)上進(jìn)行一次K-modes可得到如圖7所示層次K-Modes聚類圖。

如圖7所示，在同樣k=3的情形下，動(dòng)態(tài)層次K-modes相較于傳統(tǒng)K-modes，分類準(zhǔn)確度達(dá)到CE=76.93%，明顯高于傳統(tǒng)K-modes；并且類數(shù)目k也能被正確確定，因此其分類效果明顯優(yōu)于傳統(tǒng)K-modes。

圖7 層次K-modes聚類

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

傳統(tǒng)K-modes算法與層次聚類算法結(jié)合，成功地將層次K-means的算法優(yōu)點(diǎn)移植到類屬型數(shù)據(jù)中。并且所提出的動(dòng)態(tài)層次K-modes算法還可以通過(guò)聚類系譜圖確定k值，一定程度上解決了k值須初始給定的公開(kāi)問(wèn)題。算法也具有更強(qiáng)的適應(yīng)性和異常點(diǎn)識(shí)別等優(yōu)良性質(zhì)，可以對(duì)真實(shí)數(shù)據(jù)給出有效聚類結(jié)果。

考慮到動(dòng)態(tài)層次K-modes算法從結(jié)果上雖然明顯優(yōu)于傳統(tǒng)K-modes算法，但在進(jìn)行聚類時(shí)仍會(huì)出現(xiàn)一定的錯(cuò)分現(xiàn)象，在后續(xù)工作中考慮引入robust思想，無(wú)須將所有樣本帶入聚類迭代過(guò)程，而是僅選取一部分重要樣本進(jìn)行迭代，以此提高算法準(zhǔn)確度。同時(shí)在特征提取方面，也希望引入更精細(xì)化的自適應(yīng)閾值給定，從數(shù)據(jù)角度提高聚類質(zhì)量。