基于DBSCAN算法的告警數據聚類研究

鄧翠艷，姚旭清

(1.太原理工大學 現代科技學院，太原 030027；2.中國移動通信集團山西有限公司，太原 030009)

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

1 告警數據預處理

伴隨設備產生并獲取大量告警數據后，需要先對告警數據進行預處理。告警數據的預處理主要是完成對告警數據信息的數據集成、清洗、簡化。本文涉及到的預處理方法主要包含活動時間窗口設置、DBSCAN聚類、告警數據分段及有效的事物提取。

1.1 滑動時間窗口

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

2) 滑動步長。告警序列在當前窗口內起始時間為ts，結束時間為te，則te-ts=W.窗口經過s時間后滑動到一個新的位置，新窗口的起始時間和結束時間分別為ts+s和te+s.則s為窗口滑動步長。

3) 告警時間間隔。告警序列中兩個告警發生的時間差。

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

圖1 滑動時間窗口示例Fig.1 Example of sliding time window

1.2 告警數據分段及事務提取約束條件

為了告警關聯規則挖掘的準確性，告警數據在分段及提取告警事務數據過程中，各個時間段或事務之間的中心點距離(段間差異)越大越好，時間段內或事務內各個告警數據與中心點的距離(段內差異)越小越好。本文均采用告警時間間隔作為距離的度量標準。

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

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

定義2段間差異：相鄰兩個時間段或事務中的中心點之間的平均距離。即

定義3段內差異：各時間段或事務內每條告警數據與該時間段或事務中心點的平均距離。即

定義4告警數據分段或事務提取總體質量定義為：

總體質量越大說明分段或事務提取效果越好。

2 基于DBSCAN和多約束滑動時間窗口算法

本文完成的主要工作有：

1) 根據原始告警數據的特點，利用DBSCAN密度聚類算法以時間維護將原流水告警數據劃分為多個告警事件時間戳。

2) 通過約束條件選取DBSCAN最佳輸入參數，在各個時間段利用滑動時間窗口提取告警事務。

2.1 算法的提出

通信網中告警的發生具有不確定性，但相關性越強的告警數據會在某一個時間段內產生的比較密集，相關性較弱或無相關性的告警數據產生的時間間隔會比較大，而且在其他因素的影響下會引起少量的噪音告警。若采用固定的滑動時間窗口，在告警比較密集的時間段內，相關性比較大的告警數據可能會截斷到不同的事務中，在告警稀疏的時間段產生大量空的告警事務，且不能清除噪音告警，降低了告警關聯規則挖掘的效率和準確性。DBSCAN算法是一種以密度為基礎的聚類分析算法，該算法在不需要預先指定聚類數量的情況下找出任何形狀的聚類，且能有效地分辨數據集中的噪音。因此可用DBSCAN算法先將告警數據分成多個告警產生比較密集的時間段，并根據約束條件確定輸入的最佳參數，然后利用滑動時間窗在各個時間段進行告警事務提取。該方法不僅可以減少噪音告警對告警事務提取的影響，而且能確定最佳的輸入參數，具有很大的靈活性和實用性。

2.2 時間窗口寬度和滑動步長選擇

滑動時間窗口主要解決網絡設備時間不同步和告警事件時間間隔過小問題，因此在聚類后的各個時間段用滑動時間窗口法進行事務提取。由于同一個時間窗內的告警事件為同一事務，時間窗口寬度W的取值范圍為Gmax

為了能充分利用告警數據，防止將幾乎同時發生的告警截斷到兩個告警事務集中，選擇的滑動步長應該使相鄰兩個時間窗口有足夠的重疊。滑動步長越小，相鄰兩個窗口重疊的告警數據越多，提取的事務就越多；滑動步長越大，相鄰兩個窗口重疊的告警數據越少，提取的事務就會相對減少。當滑動步長大于時間窗口寬度時，就會遺漏部分告警信息。因此滑動步長s的取值范圍為Gmin

偽代碼如下：

3 實驗評測

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

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

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

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

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

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

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

用中，為了保證相鄰窗口有足夠多的重疊，應根據實際要求和段內差異設置最佳時間窗口寬度和滑動步長。

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

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

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

4 結束語

本文提出了一種DBSCAN算法和多約束滑動時間窗口算法首先將分散的告警流水數據通過DBSCAN在時間軸上進行有效的聚合，通過約束條件選取DBSCAN最佳輸入參數，在各個時間段利用滑動時間窗口提取告警事務，實現告警數據信息的有效劃分。研究結論如下：

1) 實驗結論表明通信網絡如在某一時間點產生故障告警信息，那么在某一時間窗口內會急劇出現大量關聯故障告警信息。而本文基于DBSCAN和多約束滑動時間窗口算法正好符合通信網絡故障特點，更好地切合了所研究的內容。

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