基于改進的快速密度峰值聚類的調控系統故障定位算法

王 婷，王其兵，燕爭上，張秀麗，徐利美，石新聰，

朱燕芳2，強 彥3，郝 偉1

(1.國網山西省電力公司電力科學研究院，太原 030000；2.國網山西省電力公司，太原 030000；3.太原理工大學 信息與計算機學院，山西 晉中 030600)

對電力調控數據中心機房中的設備進行準確故障定位不僅能夠幫助運維人員和管理者提高工作效率和掌控能力，而且可以為實際的運維作業與運維管理提供支持。然而，目前電力調控數據中心機房設備的種類繁多，且設備與設備之間相互關聯形成一種復雜的結構。此外，不同的設備在運行時產生的數據也存在著錯綜復雜的關系[1-2]。因此，當其中某個設備發生故障時，如果該故障不能被及時發現處理，將會使得調控數據中心無法正常運行，甚至可能陷入癱瘓的狀態，這將造成難以估計的損失。通常情況下，往往采用人工巡查的方式來對調控數據中心機房設備的故障進行檢測，這種方式雖然能夠從一定程度上降低數據中心設備發生故障的風險，但是由于人工巡檢需要根據設備編號逐一進行檢查，導致這種方式存在一定的滯后性，效率低。因此，迫切需要一種能夠對數據中心設備進行快速且準確的故障定位方法。設備在運行過程中會產生海量的運行數據，這些數據中往往會存在很多異常值，而這些異常值往往就是系統中的異常數據點。通常情況下，這些異常點往往與系統的故障存在密切關系[3-4]。因此，可以通過分析和挖掘不同設備在運行時產生的數據來捕捉這種異常。有效的異常值檢測方法可以及時捕捉到調控數據中心系統中的設備的各種異常運行狀態，幫助檢修人員及時發現并定位故障點位置，從而避免故障擴大，并最大程度的降低經濟損失。綜上所述，對調控數據中心機房設備產生的海量運行數據進行有效的異常值檢測是保證準確定位數據中心故障的關鍵環節。

基于調控數據中心設備產生的海量運行數據，提出了一種改進的快速密度峰值聚類(IFDPC)的異常值檢測算法。具體步驟是首先利用帶有遞減的本地自適應窗口(LAW)的迭代覆蓋圖(OM)程序來構建定位圖和多維密度圖。然后，通過將構建的密度圖與原始快速密度峰值聚類算法(FDPC)進行結合來降低后續步驟處理的復雜度。提出的IFDPC算法對參數變化不敏感從而可以對聚類中心的選擇過程進行持續優化。在兩個不同的電力調控數據中心上的實驗結果表明，提出的IFDPC算法能夠有效提高故障檢測的性能。

1 快速密度峰值聚類(FDPC)算法

對數據中異常點的檢測，最常用的是基于聚類[5]的算法。聚類算法的特點是通過識別數據集中的相似樣本來形成聚類中心，而異常點通常是距離聚類中心較遠的點。聚類算法的計算過程比較復雜的，從算法的角度分析，當聚類的簇數不確定時，聚類問題的復雜性往往是令人棘手。因此，RODRIGUEZ et al[6]提出了快速密度峰值聚類(FDPC)算法，該算法能夠處理非球面形狀數據，并提供了一個方便的決策規則來找到正確的聚類簇數[7]。該算法將聚類中心定義為具有局部密度最大值的位置點。更具體地，聚類中心具有以下特點：1) 聚類中心被具有更低密度的鄰居點包圍；2) 這些鄰居點遠離任何具有更高密度其他點。因此該算法主要關注的因素有兩個：局部密度和與更高密度點之間的距離。FDPC算法主要包括下述過程。

1) 首先選擇距離dc，并將其用于定義鄰居點。通過計算比dc更靠近的樣本點xi的數量來計算每個數據點xi的密度ρi.

2) 對于每個數據點xi，找到密度ρi較高的最近點，并記錄能夠將它們分開的最短距離δi.

3) 聚類中心定義為同時具有高密度ρi和較大距離δi的點xi.令(xi)i=1…N為樣本點。在FDPC的第一步中，計算每個數據點之間的歐幾里得距離dij.然后，選擇距離dc，最后為每個xi計算比dc更接近點xi的數據點的數量。然后根據下式獲得局部密度：

(1)

式中：K是核函數。在第二步中，計算點xi和任何其它具有更高密度的點之間的最小距離，如下式所示:

(2)

最終，聚類中心(δ,p)在形成的決策圖中被定義為離群點，這些離群點同時具有較高局部密度ρi和較大距離δi，而異常點則往往是具有極低局部密度和較大距離的點，即這些點會獨自成簇。通過將這些點找出并逐個進行標記，從而完成在計算量較小的情況下，快速找到異常點的目的。

2 改進的快速密度峰值聚類算法

雖然，FDPC算法取得了很多成就[8-15]，但是將其應用于電力調控數據中心設備的異常值檢測仍然面臨很多挑戰：

1) 在PDFC算法步驟(1)中，需要計算所有樣本點之間的距離，從而導致算法復雜度很高和較大的內存占用量，在其他步驟中也面臨同樣的情況。在面臨電力調控數據中心設備產生的海量運行數據時無法進行快速且有效的處理。

2) 閾值距離dc的選擇往往需要依靠個人經驗，這嚴重影響了聚類算法的最終結果。

3) 決策圖中異常值的確定沒有統一的規則，從而導致對聚類中心的選擇需要依賴手動或僅僅是半自動的。

鑒于此，本文提出了一種改進的快速密度峰值聚類(IFDPC)算法以克服上述缺點，整體流程圖如圖1所示。 IFDPC的總體思路是，首先通過使用遞減窗口的迭代覆蓋圖OM過程來構建密度圖，減小問題的維數N，然后使用它提供的定位信息來改進步驟(2)和(3).該算法在處理非球面數據方面繼承了FDPC算法的高效性和準確性，并且可以考慮采樣點與相鄰采樣點之間的關系，從而大大減少了聚類中心的選擇和標記的計算，顯著提高了對異常點檢測的準確性。

圖1 改進的快速密度峰值聚類(IFDPC)算法流程圖Fig.1 Flowchart improved fast density peak clustering(IFDPC)algorithm

2.1 構建密度圖和決策圖

2.2 程序覆蓋圖(OM)

對于給定的固定窗口dc，OM的迭代過程使用半徑為dc的球域來搜索整個數據集。第一個觀測值x1用于構造第一個球B1(x1,dc)；然后，對于每個觀測值xi，首先檢查其是否至少屬于一個現有的球即計算xi與球心x1的距離是否小于半徑dc.如果是，則該球B1(x1,dc)的密度計數增加一。否則，將創建一個新的球Bk(xi,dc)，整個迭代計算過程如算法1所示。經過該迭代過程，最終獲得一個球集。該集合中包含的數據點數量將比原始數據集中包含的數據點數量少得多，并且該集合中每個數據點的局部密度ρi組合在一起能夠覆蓋整個原始數據集。

算法1:OverMap開始:OM(dc)OM 創建第一個球: S←B1(x1,dc) ρi(B1(x1,dc))←1 創建新球: forallx1,i>1do d←distance(xi,S) J←{j|d[j]

2.3 窗口尺寸遞減的迭代OM(LAW)

索引J將被儲存，從而能夠加載xi的母球并知道xi是否在下一個OM迭代中屬于該球域。在對所有觀測值xi進行處理之后，Nmin個點被設置為終端球的數量。然后，通過對得到的球點集合進行最后一次遍歷來重新評估密度計數。具體的，對于每個點xi，首先找到xi所屬的第一代球，將其密度計數增加1，之后加載距離xi更近的球的子代，重復該過程，直到xi不屬于任何一個球的子球。通過以上操作，可以獲得對于每個數據點xi，包含它的距離最近且局部密度較小的終端球cci.

2.4 聚類中心的選擇和標記

計算完每個點的ρi和δi后，使用δi作為縱坐標，ρi作為橫坐標來畫出決策圖，其中決策圖右上方的點就是簇的中心點，右上方有幾個點，就意味著分為幾個簇。聚類中心的選擇和標記的主要目標是為每個終端球找到距離最接近且局部密度最高的球作為該終端球所屬的聚類中心。具體的篩選過程如下：1) 密度非常低的點通常是噪音點，獨自成簇，可做好標記，不參與后面的分配；2) 可選擇兩個指標都在前50%的成立簇中心，剩余的每個數據點都被標記為包含它的最近的終端球。至此，整個聚類操作就結束。

3 實驗與結果

在本實驗中，使用C語言進行實驗仿真。為了評估提出的IFDPC算法的有效性，收集了兩種類型的某電力調控數據中心機房設備運行數據，并進行仿真實驗。

3.1 實驗一

首先從數據中心的每臺設備上(包括處理器，內存和I / O, 設備溫度等)獲得一組相同的性能參數作為構建的預測模型的輸入，如表1中所示。這組預選參數將被定期收集，其值可以作為預測硬件故障的可靠指標。采樣頻率為1 h，即每天采集24個采樣點，采樣時間為2018-07-28-2019-07-27，共365 d。此外，在得到原始的參數數據之后，首先對數據采用最大最小值歸一化方法[16]進行歸一化以消除由不同量綱的數據樣本對結果的不利影響并加快模型的訓練速度。然后，采用本文提出的IFDPC算法進行實驗。首先對從電力調控數據中心設備上收集的性能參數曲線進行可視化，結果如圖2所示。從圖2中可以看出該調控系統大部分曲線都趨向于正常狀態，僅存在少量異常情況，這說明系統在大部分時間下都處于正常狀態，而當系統出現異常時，收集的設備性能參數會與正常模式有很大的偏差。這些偏差數據正是算法要找出的異常點。這說明，提出的算法可以很好地捕獲調控系統中設備運行異常點，從而可以幫助管理人員快速定位故障位置。

表1 從數據中心收集的每臺設備的性能參數Table 1 Performance parameters for each device collected from the data center

圖2 電力調控數據中心設備的性能參數曲線Fig.2 Performance parameter curve of power-regulated data center equipment

為了更好地展示提出的IFDPC算法的優勢，與原始FDPC算法相比，分別繪制了這兩種算法在進行故障定位時的決策圖，如圖3和圖4所示。其中圖3為原始FDPC算法獲得的決策圖，從圖3中可以看出，調控中心設備性能參數樣本集中只有一個明顯的聚類中心，而其他聚類中心則相對不明顯，這正符合原始的FDPC算法的特性，對于局部密度變化較大的數據該算法的識別能力較弱，因此，峰值密度較低的點可能被忽略或視為異常值。

圖3 案例一的原始FDPC算法的決策圖Fig.3 Decision chart of the traditional peak density clustering algorithm of case 1

圖4是提出的IFDPC算法獲得的決策圖，圖5為該算法實驗密度圖。從圖4中可以看出，提出的IFDPC算法能夠準確檢測到圖2中的異常曲線，而這些曲線則是與正常模式不同的設備異常情況。此外，從圖4中可以明顯看出，在處理局部密度變化較大的數據時，IFDPC算法與原始的FDPC算法相比結果有明顯提升，決策圖中右下角最明顯的聚類中心以及其他聚類中心，圖4中樣本點的3個特征值比圖3中更為明顯，這意味著IFDPC算法獲得的聚類中心比原始FDPC算法更加準確。

圖4 案例一的IFDPC算法的決策圖Fig.4 Decision chart of improved fast density peak clustering algorithm in case 1

圖5 IFDPC算法的密度圖Fig.5 Density chart of improved fast density peak clustering algorithm

此外，為了證明提出的IFDPC算法在以日為單位的采樣情況下也能準確地捕獲設備異常情況，從2018年7月28日-2019年7月27日，獲得了365條設備日性能參數曲線，結果如圖6所示。從圖6中可以看出，提出的IFDPC算法能夠從365條設備日性能參數曲線中準確找到具有異常情況的7條曲線，顯示出IFDPC算法對設備異常值檢測的出色性能。此外，圖6中的結果還說明了IFDPC算法可以有效解決FDPC算法在識別局部密度變化較大的數據時能力較弱的問題。

圖6 案例一的電力調控數據中心設備的性能參數日曲線Fig.6 Performance parameters of power control data center equipment in case one day curve of case 1

3.2 實驗二

為了在多種情況下比較本文提出的IFDPC算法的優勢，在另一個數據集上再次進行實驗對比。該數據集中的樣本來自2017年-2019年某電力調控數據中心機房設備產生的運行數據，數據的類型與表1中相同。該數據的采樣頻率為7 d.分別使用原始FDPC算法與提出的IFDPC算法進行實驗。圖7是原始的FDPC算法獲得的決策圖，從圖7中可以看出，在初始時間點位置0.0～0.2的數據具有相對密度和距離相對較大的特點，并且出現了環形現象。這顯示了原始的FDPC算法在處理復雜數據時存在一定的局限性。

圖7 案例二的原始FDPC算法的決策圖Fig.7 Decision chart of the original fast density peak clustering algorithm of case 2

圖8是提出的IFDPC算法獲得的決策圖。圖中在初始時間點位置0.0～0.2的數據的環形現象基本消失，獲得的聚類結果明顯優于原始FDPC算法，并且IFDPC算法獲得的聚類中心的特征更加明顯。由于調控數據中心機房設備產生的數據往往是局部密度變化較大的數據類型，因此，以上實驗結果充分表明了提出的IFDPC算法在處理調控數據中心機房設備數據時的優勢。

圖8 案例二的IFDPC算法的決策圖Fig.8 Decision chart for improving fast density peak clustering algorithm of case 2

此外，由于數據集二中的異常值分布在不同的年份，因此，無法直觀地用曲線來表示它們。為了更加直觀地觀察獲得的異常分布，根據提前制定的異常值判定規則，獲得了數據集中的異常值分布，結果如表2所示。從表2中可以看出，提出的IFDPC算法可以成功檢測到數據集二中的所有異常值，這些異常值的數量大約有13個。結果表明，相比于原始的FDPC算法，提出的IFDPC算法更加關注在不同年份下同一時期內的調控數據中心機房設備產生的運行數據的縱向對比。更近一步，IFDPC算法將注意力重點放在數據集中所有數據的局部變化上。通過在調控數據中心不同類型的機房設備產生的運行數據上進行實驗，結果表明提出的IFDPC算法對局部密度變化較大的數據類型的異常值檢測具有很好的效果，這說明了提出的IFDPC算法的有效性。

表2 獲得的異常值的分布列表Table 2 Distribution list of obtained outliers

4 結語

提出了一種改進的快速密度峰值聚類算法(IFDPC)，該算法在原始快速密度峰值聚類算法(FDPC)的基礎上，采用帶有遞減的本地自適應窗口(LAW)的迭代覆蓋圖(OM)程序來構建多維密度圖和決策圖，并將構建的密度圖與FDPC算法進行結合顯著減少了后續步驟處理的復雜度。實驗結果表明，提出的算法對電力調控數據中心的機房設備的故障檢測達到了較高的準確率。