基于局部密度的最小生成樹聚類算法及其在電力大數(shù)據(jù)的應(yīng)用

靳文星，王電鋼，張哲敏

(1.上海電力大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海 200090；2.國網(wǎng)四川省電力公司信息通信公司，四川 成都 610041)

0 引 言

近些年，針對電力大數(shù)據(jù)收集和存儲中數(shù)據(jù)量大、數(shù)據(jù)收集不精準的問題,先后提出并采用了K-means、K-medoids[1]和一些改進之后的K-means算法，但是這些算法的使用都必須初始化聚類中心。為了避免初始化聚類中心，在算法領(lǐng)域中的AP算法[2]將所有數(shù)據(jù)點都視為潛在的中心。K-AP[3]是AP算法的改進，它在消息傳遞過程中引入約束，利用K簇產(chǎn)生的直接結(jié)果，然而，由于每個點總是分配到最近的中心，導(dǎo)致這些算法不能發(fā)現(xiàn)任意形狀的聚類(即類簇)。還有一種快速搜索發(fā)現(xiàn)密度峰值[4](density peak，DP)的聚類算法，選擇局部密度最大的點作為聚類中心，將其余點作為密度最大的近鄰分配到同一個類別中。假設(shè)每個類簇都有收縮的密度核，大致保留了類簇的形狀，并提出了一種基于密度核的聚類算法，稱為Dcore[5]?；诿芏鹊木垲愃惴―BSCAN[6]將聚類定義為由稀疏區(qū)域分隔的稠密區(qū)域。它的關(guān)鍵思想是，設(shè)定集群的每個核心點，在每個核心點周圍給定半徑內(nèi)必須包含有參數(shù)設(shè)定數(shù)量的點(如參數(shù)設(shè)定為30，則若一點給定半徑范圍內(nèi)有超過30點，即認定此點為核心點)。Dcore和DBSCAN可以有效地識別具有任意形狀的數(shù)據(jù)集，但是它們必須設(shè)置許多參數(shù)。

針對電力大數(shù)據(jù)中無法高效識別具有任意形狀數(shù)據(jù)集的問題，提出了基于最小生成樹(minimum spanning tree，MST)和局部密度峰值(local density peak，LDP)的聚類算法，稱為LDP-MST，它在發(fā)現(xiàn)復(fù)雜數(shù)據(jù)時，不僅計算效率高，而且可以與其他先進的聚類方法相媲美。在LDP-MST中，首先找到局部密度峰值，將剩余的點分配到相應(yīng)的局部密度峰值；然后，定義一個新的基于共享鄰點的局部密度峰值之間的距離，并利用新的距離在局部密度峰值上構(gòu)造最小生成樹；最后通過不斷地去除最長邊，得到了最終的聚類。

1 基于局部密度峰值和共享鄰點的MST聚類

現(xiàn)有的基于MST的聚類算法，在整個數(shù)據(jù)集上構(gòu)造MST的時候，因為只利用樹中包含的邊緣信息對數(shù)據(jù)集進行劃分，導(dǎo)致數(shù)據(jù)的計算量很大，而且容易受到噪聲點的影響?；诖藛栴}，提出了一種基于局部密度峰值的最小生成樹聚類算法(以圖1所示的一個數(shù)集為例)。首先，選取相鄰區(qū)域中局部密度最大的點作為局部密度峰值，并將其余點分配到相應(yīng)的局部密度峰值附近，如圖1(a)所示；然后，定義一個新的局部密度峰值之間的距離分類(它考慮了歐幾里得距離和鄰點信息)，利用局部密度峰值和距離構(gòu)建MST，如圖1(b)所示。在此之后，根據(jù)新的距離不斷地去除最長的邊，并進行距離連線，直到得到期望的簇數(shù)。圖1(c)中鏈接不同簇之間的邊是需要從MST中更正的邊，最后得到如圖1(d)所示的聚類結(jié)果。整個算法過程由于只在局部密度峰值上構(gòu)造MST，減少了噪聲點的干擾，大大提高了算法的效率。

圖1 LDP-MST的主要思想

1.1 局部密度

為了找到局部密度峰值，首先定義點的局部密度。因為稠密區(qū)域的點與其近鄰點的距離總和通常小于稀疏區(qū)域的點與近鄰點的距離之和,在稠密區(qū)域，nb值較大；在稀疏區(qū)域，nb值較小，所以，點p的局部密度與nb(p)的值成正比，與點p和其相鄰點之間的距離成反比。利用這一特性，計算局部密度ρ(p)：

式中：nb(p)為到達自然特征值時的p的反向近鄰數(shù)；NNK(p)為p的反向k近鄰；d(p,q)為p和q之間的距離。

如圖2中給出了每個局部密度峰值的鄰域(圖中粗線表示)，其中包括其成員和一些額外的最近鄰域，在圖中用不同點間的連線表示。共享鄰點的數(shù)量和密度越大，表示它們之間的距離越小。

圖2 LDP的鄰點和共享鄰點

1.2 基于共享鄰點的局部密度峰值之間的距離

由于歐幾里得距離不能很好地對復(fù)雜數(shù)據(jù)進行恰當度量，且由于大多時候都測量不到圖形點位置的先驗信息，導(dǎo)致不能直接得到準確的測量距離?；诰植棵芏确逯档墓蚕磬徲?，采用了一個新的距離，即基于共享鄰點的局部密度峰值之間的距離。

由于數(shù)據(jù)集中局部密度峰值分布不均勻，歐氏距離不適用于測量局部密度峰值之間的差異。所以使用基于鄰域的共享距離利用局部密度峰值之間的鄰域信息，縮短被稠密區(qū)域緊密相連的局部密度峰值之間的距離的方法更恰當?shù)乇硎玖司植棵芏确逯抵g的差異。

以圖3所示的數(shù)據(jù)集為例，圖3(a)為局部密度峰值及其鄰域點，圖3(b)為用歐幾里得法構(gòu)造的局部密度峰值的MST圖像，圖3(c)為基于共享鄰點的距離構(gòu)造的MST圖像。局部密度峰值p和q在同一簇，q和o在不同簇，但是p和q之間的歐氏距離大于q和o之間的歐氏距離，所以用歐氏距離構(gòu)造的MST會出現(xiàn)錯誤。但是，基于共享鄰點的距離構(gòu)建的MST正確地保留了原始數(shù)據(jù)集的結(jié)構(gòu)。

圖3 各個方法距離的區(qū)別

1.3 算法流程

首先，使用局部密度峰值和基于共享鄰點的距離來構(gòu)建MST；然后，重復(fù)切割最長的邊(邊的長度是采用基于共享鄰點距離的)，并保證切割該邊導(dǎo)致的兩個簇的大小都大于松散估計的最小點數(shù)，直到找到給定數(shù)量的簇為止。對局部密度峰值進行聚類后，將每個剩余點分配到與對應(yīng)的局部密度峰值所屬的相同類簇中。LDP-MST算法主要包括以下步驟:1)搜索局部密度峰值;2)計算局部密度峰值之間基于共享鄰點的距離;3)采用基于MST的聚類算法對局部密度峰值進行聚類。

2 LDP-MST在電力大數(shù)據(jù)中的應(yīng)用

如今，智能電網(wǎng)建設(shè)速度不斷加快，與之而來的是大量的數(shù)據(jù)，這些數(shù)據(jù)主要來源于電網(wǎng)的發(fā)、輸、配、用四大環(huán)節(jié)。聚類分析可以從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取隱含在其中的人們事先不知道但又具有潛在價值的信息。其中，最具有顯著效果的聚類分析就是對用戶用電行為的聚類和異常檢測。用戶用電行為聚類基于用戶用電行為模式對相似性用戶進行劃分類別，而異常檢測主要是指檢測電力偷竊、電能表錯誤、計費錯誤等非技術(shù)損失造成的異常用電情況。

LDP-MST算法在電力大數(shù)據(jù)領(lǐng)域具有良好的應(yīng)用前景，尤其體現(xiàn)在異常值檢測中。異常值檢測的目標是將不屬于任何簇的樣本點與正常點進行區(qū)別，從數(shù)據(jù)的角度來說，就是找出樣本點數(shù)量較小的簇。故使用LDP-MST算法將樣本點較少的簇提取出來，就可以得到異常樣本。為驗證算法的實用性，以某網(wǎng)站3個月的訪問量和網(wǎng)絡(luò)流量為基礎(chǔ)，使用LDD-MST算法檢測了其中的異常值。

在進行聚類之前，先對數(shù)據(jù)進行了預(yù)處理，即用缺失點外的其他值的均值代替該屬性的缺失值。最終得到LDP-MST算法聚類結(jié)果如圖4所示。由于只通過聚類法不容易用肉眼判別聚類結(jié)果，所以要對數(shù)據(jù)進行歸一化處理。這里采取的歸一化的方式為圖5為歸一化處理后的數(shù)據(jù)。由圖可以看出，在3月之初以及4月中后期有一些數(shù)據(jù)的網(wǎng)絡(luò)流量與正常用戶訪問次數(shù)差距較大，明顯偏離了正常數(shù)值。將這些異常值輸出，并經(jīng)聚類分析和異常值判定后，得到如表1所示的異常值分布?？砂l(fā)現(xiàn)所提算法將數(shù)據(jù)集中的異常值全部檢測出來，說明LDP-MST算法對異常值檢測具有比較良好的效果。

圖4 LDP-MST算法聚類結(jié)果

圖5 歸一化處理后的數(shù)據(jù)分布

表1 異常值數(shù)據(jù)分布

3 結(jié) 語

上面提出了一種新的聚類算法LDP-MST，其核心思想是選擇局部密度峰值來構(gòu)建MST，避免了噪聲點的干擾，減少了基于MST的聚類算法的運行時間。電力綜合數(shù)據(jù)集的實驗表明，該聚類算法能較好地識別數(shù)據(jù)集中的復(fù)雜模式，且比現(xiàn)有的聚類算法更有效。在進行電力大數(shù)據(jù)的異常檢測時，算法在短時間內(nèi)有效地檢測出了異常結(jié)果。今后，將繼續(xù)完善本算法的缺點以及將這一基于聚類算法的異常檢測方法應(yīng)用到電力系統(tǒng)的更多方面。