鄧翠艷，姚旭清

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

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

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

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

1.1 滑動時間窗口

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文完成的主要工作有：

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

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

2.1 算法的提出

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

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

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

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

偽代碼如下：

3 實驗評測

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

由圖2、圖3可以看出，在同一鄰域半徑下，隨著鄰域閾值增大，DBSCAN聚類密度越大，各聚類時間段內(nèi)的告警數(shù)據(jù)越密集，噪音數(shù)據(jù)隨之增多，分段質(zhì)量持續(xù)增加。在實際應用中，清除過多的噪音數(shù)據(jù)可能會同時清除包含有很多信息量的數(shù)據(jù)。因此本文根據(jù)實際需求，在噪音數(shù)據(jù)百分比小于6%的情況下對兩個數(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

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

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

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

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

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

(a)某省通信公司數(shù)據(jù)集；(b)Blue Gene數(shù)據(jù)集圖5 不同滑動窗口下段內(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 不同滑動窗口下事務集總體質(zhì)量情況Fig.6 Overall quality of transaction set under different sliding windows

4 結(jié)束語

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

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

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