基于改進(jìn)的快速密度峰值聚類的調(diào)控系統(tǒng)故障定位算法

王 婷，王其兵，燕爭(zhēng)上，張秀麗，徐利美，石新聰，

朱燕芳2，強(qiáng) 彥3，郝 偉1

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

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

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

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

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

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

2) 對(duì)于每個(gè)數(shù)據(jù)點(diǎn)xi，找到密度ρi較高的最近點(diǎn)，并記錄能夠?qū)⑺鼈兎珠_的最短距離δi.

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

(1)

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

(2)

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

2 改進(jìn)的快速密度峰值聚類算法

雖然，F(xiàn)DPC算法取得了很多成就[8-15]，但是將其應(yīng)用于電力調(diào)控?cái)?shù)據(jù)中心設(shè)備的異常值檢測(cè)仍然面臨很多挑戰(zhàn)：

1) 在PDFC算法步驟(1)中，需要計(jì)算所有樣本點(diǎn)之間的距離，從而導(dǎo)致算法復(fù)雜度很高和較大的內(nèi)存占用量，在其他步驟中也面臨同樣的情況。在面臨電力調(diào)控?cái)?shù)據(jù)中心設(shè)備產(chǎn)生的海量運(yùn)行數(shù)據(jù)時(shí)無法進(jìn)行快速且有效的處理。

2) 閾值距離dc的選擇往往需要依靠個(gè)人經(jīng)驗(yàn)，這嚴(yán)重影響了聚類算法的最終結(jié)果。

3) 決策圖中異常值的確定沒有統(tǒng)一的規(guī)則，從而導(dǎo)致對(duì)聚類中心的選擇需要依賴手動(dòng)或僅僅是半自動(dòng)的。

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

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

2.1 構(gòu)建密度圖和決策圖

2.2 程序覆蓋圖(OM)

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

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

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

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

2.4 聚類中心的選擇和標(biāo)記

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

3 實(shí)驗(yàn)與結(jié)果

在本實(shí)驗(yàn)中，使用C語言進(jìn)行實(shí)驗(yàn)仿真。為了評(píng)估提出的IFDPC算法的有效性，收集了兩種類型的某電力調(diào)控?cái)?shù)據(jù)中心機(jī)房設(shè)備運(yùn)行數(shù)據(jù)，并進(jìn)行仿真實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)一

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

表1 從數(shù)據(jù)中心收集的每臺(tái)設(shè)備的性能參數(shù)Table 1 Performance parameters for each device collected from the data center

圖2 電力調(diào)控?cái)?shù)據(jù)中心設(shè)備的性能參數(shù)曲線Fig.2 Performance parameter curve of power-regulated data center equipment

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

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

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

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

圖6 案例一的電力調(diào)控?cái)?shù)據(jù)中心設(shè)備的性能參數(shù)日曲線Fig.6 Performance parameters of power control data center equipment in case one day curve of case 1

3.2 實(shí)驗(yàn)二

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

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

圖8是提出的IFDPC算法獲得的決策圖。圖中在初始時(shí)間點(diǎn)位置0.0～0.2的數(shù)據(jù)的環(huán)形現(xiàn)象基本消失，獲得的聚類結(jié)果明顯優(yōu)于原始FDPC算法，并且IFDPC算法獲得的聚類中心的特征更加明顯。由于調(diào)控?cái)?shù)據(jù)中心機(jī)房設(shè)備產(chǎn)生的數(shù)據(jù)往往是局部密度變化較大的數(shù)據(jù)類型，因此，以上實(shí)驗(yàn)結(jié)果充分表明了提出的IFDPC算法在處理調(diào)控?cái)?shù)據(jù)中心機(jī)房設(shè)備數(shù)據(jù)時(shí)的優(yōu)勢(shì)。

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

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

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

4 結(jié)語

提出了一種改進(jìn)的快速密度峰值聚類算法(IFDPC)，該算法在原始快速密度峰值聚類算法(FDPC)的基礎(chǔ)上，采用帶有遞減的本地自適應(yīng)窗口(LAW)的迭代覆蓋圖(OM)程序來構(gòu)建多維密度圖和決策圖，并將構(gòu)建的密度圖與FDPC算法進(jìn)行結(jié)合顯著減少了后續(xù)步驟處理的復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，提出的算法對(duì)電力調(diào)控?cái)?shù)據(jù)中心的機(jī)房設(shè)備的故障檢測(cè)達(dá)到了較高的準(zhǔn)確率。