基于DBSCAN算法的告警數(shù)據(jù)聚類研究

鄧翠艷，姚旭清

(1.太原理工大學(xué) 現(xiàn)代科技學(xué)院，太原 030027；2.中國(guó)移動(dòng)通信集團(tuán)山西有限公司，太原 030009)

通信網(wǎng)絡(luò)時(shí)刻會(huì)產(chǎn)生大量的告警數(shù)據(jù)，由于網(wǎng)絡(luò)設(shè)備的連通性，原始告警數(shù)據(jù)通常存在信息冗余、時(shí)間不同步、含有噪聲等一系列問(wèn)題[1]，無(wú)法直接完成對(duì)原始告警數(shù)據(jù)的關(guān)聯(lián)挖掘。告警關(guān)聯(lián)挖掘需要輸入各項(xiàng)事務(wù)數(shù)據(jù)集，因此首先需對(duì)原始的告警數(shù)據(jù)進(jìn)行轉(zhuǎn)換[2-3]，生成適合挖掘的事務(wù)集才能完成后期的相關(guān)工作。目前對(duì)于時(shí)間序列數(shù)據(jù)的挖掘，大部分研究都設(shè)定固定的時(shí)間窗口和滑動(dòng)步長(zhǎng)來(lái)建立事務(wù)數(shù)據(jù)庫(kù)[1]。但由于告警具有隨機(jī)性，采用固定滑動(dòng)時(shí)間窗口在告警頻發(fā)時(shí)段可能會(huì)把有關(guān)聯(lián)的告警截?cái)嗟讲煌氖聞?wù)集中，在告警稀疏的時(shí)間段會(huì)產(chǎn)生空的告警事務(wù)集，降低了告警關(guān)聯(lián)規(guī)則挖掘的準(zhǔn)確性，同時(shí)由于網(wǎng)絡(luò)短暫的振動(dòng)或不穩(wěn)定容易產(chǎn)生大量的噪音告警，影響關(guān)聯(lián)規(guī)則挖掘的準(zhǔn)確性。文獻(xiàn)[3-5]提出了多種聚類的智能算法，但是對(duì)于告警數(shù)據(jù)的聚類及冗余數(shù)據(jù)清除均無(wú)法滿足告警數(shù)據(jù)本身特征。DBSCAN聚類算法[6]是一種以密度為基礎(chǔ)的聚類分析算法，主要由可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為最終聚類的一個(gè)類別。在告警數(shù)據(jù)聚類中，以告警時(shí)間間隔作為度量距離的標(biāo)準(zhǔn)，最大密度相連的告警數(shù)據(jù)會(huì)被聚到同一個(gè)時(shí)間段，同時(shí)清除噪音告警。本文提出了一種基于DBSCAN算法和多約束算法的告警預(yù)處理方法。

1 告警數(shù)據(jù)預(yù)處理

伴隨設(shè)備產(chǎn)生并獲取大量告警數(shù)據(jù)后，需要先對(duì)告警數(shù)據(jù)進(jìn)行預(yù)處理。告警數(shù)據(jù)的預(yù)處理主要是完成對(duì)告警數(shù)據(jù)信息的數(shù)據(jù)集成、清洗、簡(jiǎn)化。本文涉及到的預(yù)處理方法主要包含活動(dòng)時(shí)間窗口設(shè)置、DBSCAN聚類、告警數(shù)據(jù)分段及有效的事物提取。

1.1 滑動(dòng)時(shí)間窗口

1) 時(shí)間窗口和窗口寬度。對(duì)于告警事件E，告警序列S={m,Ts,Te}，其中Ts是告警開始發(fā)生時(shí)間，Te是告警結(jié)束時(shí)間，m=(e1,t1)，(e2,t2),…,(en,tn)，ei∈E,Ts≤ti≤Te,i=1,…,n.子序列Sw={w,ts,te}為S的一個(gè)時(shí)間窗口，Ts

2) 滑動(dòng)步長(zhǎng)。告警序列在當(dāng)前窗口內(nèi)起始時(shí)間為ts，結(jié)束時(shí)間為te，則te-ts=W.窗口經(jīng)過(guò)s時(shí)間后滑動(dòng)到一個(gè)新的位置，新窗口的起始時(shí)間和結(jié)束時(shí)間分別為ts+s和te+s.則s為窗口滑動(dòng)步長(zhǎng)。

3) 告警時(shí)間間隔。告警序列中兩個(gè)告警發(fā)生的時(shí)間差。

圖1為均勻滑動(dòng)窗口的示例。其中e1,e2,…,e9為告警事件，{(e1,5),(e6,6)(e3,7),…,(e7,34)}是一個(gè)告警序列。時(shí)間窗口寬度為8，滑動(dòng)步長(zhǎng)為5.

圖1 滑動(dòng)時(shí)間窗口示例Fig.1 Example of sliding time window

1.2 告警數(shù)據(jù)分段及事務(wù)提取約束條件

為了告警關(guān)聯(lián)規(guī)則挖掘的準(zhǔn)確性，告警數(shù)據(jù)在分段及提取告警事務(wù)數(shù)據(jù)過(guò)程中，各個(gè)時(shí)間段或事務(wù)之間的中心點(diǎn)距離(段間差異)越大越好，時(shí)間段內(nèi)或事務(wù)內(nèi)各個(gè)告警數(shù)據(jù)與中心點(diǎn)的距離(段內(nèi)差異)越小越好。本文均采用告警時(shí)間間隔作為距離的度量標(biāo)準(zhǔn)。

定義1中心點(diǎn)：對(duì)于一個(gè)包含n個(gè)告警數(shù)據(jù)的告警序列T={(e1,t1),(e2,t2),…,(en,tn)}的中心點(diǎn)為

T1/2=t1+(t2-t1)/2.

定義2段間差異：相鄰兩個(gè)時(shí)間段或事務(wù)中的中心點(diǎn)之間的平均距離。即

定義3段內(nèi)差異：各時(shí)間段或事務(wù)內(nèi)每條告警數(shù)據(jù)與該時(shí)間段或事務(wù)中心點(diǎn)的平均距離。即

定義4告警數(shù)據(jù)分段或事務(wù)提取總體質(zhì)量定義為：

總體質(zhì)量越大說(shuō)明分段或事務(wù)提取效果越好。

2 基于DBSCAN和多約束滑動(dòng)時(shí)間窗口算法

本文完成的主要工作有：

1) 根據(jù)原始告警數(shù)據(jù)的特點(diǎn)，利用DBSCAN密度聚類算法以時(shí)間維護(hù)將原流水告警數(shù)據(jù)劃分為多個(gè)告警事件時(shí)間戳。

2) 通過(guò)約束條件選取DBSCAN最佳輸入?yún)?shù)，在各個(gè)時(shí)間段利用滑動(dòng)時(shí)間窗口提取告警事務(wù)。

2.1 算法的提出

通信網(wǎng)中告警的發(fā)生具有不確定性，但相關(guān)性越強(qiáng)的告警數(shù)據(jù)會(huì)在某一個(gè)時(shí)間段內(nèi)產(chǎn)生的比較密集，相關(guān)性較弱或無(wú)相關(guān)性的告警數(shù)據(jù)產(chǎn)生的時(shí)間間隔會(huì)比較大，而且在其他因素的影響下會(huì)引起少量的噪音告警。若采用固定的滑動(dòng)時(shí)間窗口，在告警比較密集的時(shí)間段內(nèi)，相關(guān)性比較大的告警數(shù)據(jù)可能會(huì)截?cái)嗟讲煌氖聞?wù)中，在告警稀疏的時(shí)間段產(chǎn)生大量空的告警事務(wù)，且不能清除噪音告警，降低了告警關(guān)聯(lián)規(guī)則挖掘的效率和準(zhǔn)確性。DBSCAN算法是一種以密度為基礎(chǔ)的聚類分析算法，該算法在不需要預(yù)先指定聚類數(shù)量的情況下找出任何形狀的聚類，且能有效地分辨數(shù)據(jù)集中的噪音。因此可用DBSCAN算法先將告警數(shù)據(jù)分成多個(gè)告警產(chǎn)生比較密集的時(shí)間段，并根據(jù)約束條件確定輸入的最佳參數(shù)，然后利用滑動(dòng)時(shí)間窗在各個(gè)時(shí)間段進(jìn)行告警事務(wù)提取。該方法不僅可以減少噪音告警對(duì)告警事務(wù)提取的影響，而且能確定最佳的輸入?yún)?shù)，具有很大的靈活性和實(shí)用性。

2.2 時(shí)間窗口寬度和滑動(dòng)步長(zhǎng)選擇

滑動(dòng)時(shí)間窗口主要解決網(wǎng)絡(luò)設(shè)備時(shí)間不同步和告警事件時(shí)間間隔過(guò)小問(wèn)題，因此在聚類后的各個(gè)時(shí)間段用滑動(dòng)時(shí)間窗口法進(jìn)行事務(wù)提取。由于同一個(gè)時(shí)間窗內(nèi)的告警事件為同一事務(wù)，時(shí)間窗口寬度W的取值范圍為Gmax

為了能充分利用告警數(shù)據(jù)，防止將幾乎同時(shí)發(fā)生的告警截?cái)嗟絻蓚€(gè)告警事務(wù)集中，選擇的滑動(dòng)步長(zhǎng)應(yīng)該使相鄰兩個(gè)時(shí)間窗口有足夠的重疊?；瑒?dòng)步長(zhǎng)越小，相鄰兩個(gè)窗口重疊的告警數(shù)據(jù)越多，提取的事務(wù)就越多；滑動(dòng)步長(zhǎng)越大，相鄰兩個(gè)窗口重疊的告警數(shù)據(jù)越少，提取的事務(wù)就會(huì)相對(duì)減少。當(dāng)滑動(dòng)步長(zhǎng)大于時(shí)間窗口寬度時(shí)，就會(huì)遺漏部分告警信息。因此滑動(dòng)步長(zhǎng)s的取值范圍為Gmin

偽代碼如下：

3 實(shí)驗(yàn)評(píng)測(cè)

實(shí)驗(yàn)分別采用某省通信公司6月份的全量告警記錄和USENIX的計(jì)算機(jī)故障數(shù)據(jù)庫(kù)(CFDR)來(lái)自Intrepid的Blue Gene/P數(shù)據(jù)。針對(duì)原始通信公司告警數(shù)據(jù)信息冗余、字段不完整和噪音告警等問(wèn)題，對(duì)原始告警數(shù)據(jù)進(jìn)行數(shù)據(jù)清洗，并提取告警標(biāo)準(zhǔn)名、告警發(fā)生時(shí)間、告警對(duì)象設(shè)備類型、告警類別4個(gè)屬性來(lái)表述告警事件；BlueGene數(shù)據(jù)由Blue Gene/P Intrepid系統(tǒng)在6個(gè)月內(nèi)收集到的RAS日志消息組成，選取部分?jǐn)?shù)據(jù)并提取標(biāo)識(shí)符MSG_ID和消息發(fā)生時(shí)間表述一致的消息。利用DBSCAN算法在鄰域半徑為240 s，300 s，360 s和420 s下分別設(shè)置不同的鄰域閾值(MinPts)來(lái)計(jì)算告警數(shù)據(jù)分段的總體質(zhì)量和噪音數(shù)據(jù)百分比。

由圖2、圖3可以看出，在同一鄰域半徑下，隨著鄰域閾值增大，DBSCAN聚類密度越大，各聚類時(shí)間段內(nèi)的告警數(shù)據(jù)越密集，噪音數(shù)據(jù)隨之增多，分段質(zhì)量持續(xù)增加。在實(shí)際應(yīng)用中，清除過(guò)多的噪音數(shù)據(jù)可能會(huì)同時(shí)清除包含有很多信息量的數(shù)據(jù)。因此本文根據(jù)實(shí)際需求，在噪音數(shù)據(jù)百分比小于6%的情況下對(duì)兩個(gè)數(shù)據(jù)集分別選取使分段總體質(zhì)量最大的鄰域半徑和鄰域閾值。

圖2 不同鄰域半徑下告警分段的總體質(zhì)量Fig.2 Overall quality of alarm segmentation under different neighborhood radius

圖3 不同鄰域半徑下告警分段噪音百分比Fig.3 Noise percentage of alarm section under different neighborhood radius

本文設(shè)定時(shí)間窗分別為360 s和420 s，利用DBSCAN-滑動(dòng)窗口法、固定滑動(dòng)窗口法和基于近鄰傳播的滑動(dòng)窗口法分別計(jì)算在相同時(shí)間窗口寬度的不同滑動(dòng)步長(zhǎng)下所提取的事務(wù)數(shù)、段內(nèi)差異和事務(wù)集總體質(zhì)量，如圖4-圖6所示。

(a)某省通信公司數(shù)據(jù)集；(b)Blue Gene數(shù)據(jù)集圖4 不同滑動(dòng)窗口下告警數(shù)據(jù)集的變化Fig.4 Changes of alarm data sets under different sliding windows

由圖4可以明顯看出，DBSCAN-滑動(dòng)窗口法能有效減少所提取的告警事務(wù)數(shù)，其原因是在DBSCAN對(duì)告警分段過(guò)程中清除了噪音告警數(shù)據(jù)，且在時(shí)間窗口提取事務(wù)過(guò)程中不會(huì)因該時(shí)間段告警稀疏而產(chǎn)生空事務(wù)集。由于BlueGene數(shù)據(jù)集在某時(shí)間段內(nèi)產(chǎn)生消息相對(duì)稀疏，因此滑動(dòng)窗口法產(chǎn)生了大量空的數(shù)據(jù)集，DBSCAN算法有效地消除了空事務(wù)集對(duì)事務(wù)提取的影響使事務(wù)集數(shù)量大大減少。由圖5和圖6可看出，DBSCAN-滑動(dòng)窗口法所提取事務(wù)的段內(nèi)差異和總體質(zhì)量均明顯優(yōu)于固定滑動(dòng)窗口和基于近鄰傳播的滑動(dòng)窗口法。由于段間差異隨著滑動(dòng)步長(zhǎng)的增加而增加，事務(wù)提取總體質(zhì)量也不斷增加，在這種情況下，段內(nèi)差異越小越好。在實(shí)際應(yīng)

用中，為了保證相鄰窗口有足夠多的重疊，應(yīng)根據(jù)實(shí)際要求和段內(nèi)差異設(shè)置最佳時(shí)間窗口寬度和滑動(dòng)步長(zhǎng)。

根據(jù)告警數(shù)據(jù)特點(diǎn)以及固定時(shí)間窗口提取事務(wù)數(shù)據(jù)集的不合理性，提出了一種基于DBSCAN算法和多約束的滑動(dòng)時(shí)間窗口法。實(shí)驗(yàn)結(jié)果證明，與固定的滑動(dòng)時(shí)間窗口法和基于近鄰傳播的滑動(dòng)窗口法相比，該算法在DBSCAN分段過(guò)程中能清除噪音告警，有效地減少了噪音告警對(duì)事務(wù)提取的影響，從而減小了事務(wù)提取的段內(nèi)差異，提高了事務(wù)提取的總體質(zhì)量。在實(shí)際應(yīng)用中，可根據(jù)實(shí)際需求及多約束條件選取最佳參數(shù)，更加充分利用告警數(shù)據(jù)。隨著通信網(wǎng)的發(fā)展，產(chǎn)生的告警數(shù)據(jù)越來(lái)越多，傳統(tǒng)的單機(jī)處理告警數(shù)據(jù)的效率會(huì)越來(lái)越低，因此接下來(lái)的研究應(yīng)側(cè)重于該將分布式數(shù)據(jù)處理應(yīng)用于告警預(yù)處理以及告警分析，從而提高告警關(guān)聯(lián)規(guī)則挖掘效率。

(a)某省通信公司數(shù)據(jù)集；(b)Blue Gene數(shù)據(jù)集圖5 不同滑動(dòng)窗口下段內(nèi)差異的變化Fig.5 Variation of the different in the lower segment of different sliding windows

(a)某省通信公司數(shù)據(jù)集；(b)Blue Gene數(shù)據(jù)集圖6 不同滑動(dòng)窗口下事務(wù)集總體質(zhì)量情況Fig.6 Overall quality of transaction set under different sliding windows

4 結(jié)束語(yǔ)

本文提出了一種DBSCAN算法和多約束滑動(dòng)時(shí)間窗口算法首先將分散的告警流水?dāng)?shù)據(jù)通過(guò)DBSCAN在時(shí)間軸上進(jìn)行有效的聚合，通過(guò)約束條件選取DBSCAN最佳輸入?yún)?shù)，在各個(gè)時(shí)間段利用滑動(dòng)時(shí)間窗口提取告警事務(wù)，實(shí)現(xiàn)告警數(shù)據(jù)信息的有效劃分。研究結(jié)論如下：

1) 實(shí)驗(yàn)結(jié)論表明通信網(wǎng)絡(luò)如在某一時(shí)間點(diǎn)產(chǎn)生故障告警信息，那么在某一時(shí)間窗口內(nèi)會(huì)急劇出現(xiàn)大量關(guān)聯(lián)故障告警信息。而本文基于DBSCAN和多約束滑動(dòng)時(shí)間窗口算法正好符合通信網(wǎng)絡(luò)故障特點(diǎn)，更好地切合了所研究的內(nèi)容。

2) 實(shí)驗(yàn)研究表明與固定的滑動(dòng)時(shí)間窗口法和基于近鄰傳播的滑動(dòng)窗口法相比，該算法在DBSCAN分段過(guò)程中能清除噪音告警，有效減少了噪音告警對(duì)事務(wù)提取的影響，從而減少了事務(wù)提取的段內(nèi)差異，提高了事務(wù)提取的總體質(zhì)量。在實(shí)際應(yīng)用中，可根據(jù)實(shí)際需求及多約束條件選取最佳參數(shù)，更加充分的利用告警數(shù)據(jù)。