基于局部密度的最小生成樹聚類算法及其在電力大數據的應用

靳文星，王電鋼，張哲敏

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

0 引 言

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

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

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

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

圖1 LDP-MST的主要思想

1.1 局部密度

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

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

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

圖2 LDP的鄰點和共享鄰點

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

由于歐幾里得距離不能很好地對復雜數據進行恰當度量，且由于大多時候都測量不到圖形點位置的先驗信息，導致不能直接得到準確的測量距離。基于局部密度峰值的共享鄰域，采用了一個新的距離，即基于共享鄰點的局部密度峰值之間的距離。

由于數據集中局部密度峰值分布不均勻，歐氏距離不適用于測量局部密度峰值之間的差異。所以使用基于鄰域的共享距離利用局部密度峰值之間的鄰域信息，縮短被稠密區域緊密相連的局部密度峰值之間的距離的方法更恰當地表示了局部密度峰值之間的差異。

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

圖3 各個方法距離的區別

1.3 算法流程

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

2 LDP-MST在電力大數據中的應用

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

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

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

圖4 LDP-MST算法聚類結果

圖5 歸一化處理后的數據分布

表1 異常值數據分布

3 結 語

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