基于網絡和時間約束的告警序列模式挖掘研究?

徐立坤 李建路 朱 珠 陳海平 王 林

（南方電網調峰調頻發電有限公司 廣州 510630）

1 引言

隨著電力通信網絡及業務的快速發展，電力通信技術已經成為電力生產的一個重要環節，電力通信傳輸網絡的可靠性成為影響著電力生產安全的重要組成部分［1］。

告警是故障的外在呈現，具有傳遞性和多方面、多環節顯現等特點［2～6］，即一條根告警會引起大量次要衍生告警，甚至可能引起“告警風暴”。運維人員如能第一時間對系統告警準確判斷并及時處理，可以大大減少故障處理時間，迅速恢復業務系統正常使用，故告警相關性分析是故障分析和處理的基礎。

由于傳統手段依賴告警規則樹、白名單等先驗知識，無法適應網絡復雜多變的特點，而告警序列模式挖掘是實現告警相關性分析的重要方法。序列模式挖掘最早由 Agrawal和 Srikant提出［7］，序列模式是在一組有序的數據列組成的數據集中，經常出現的那些序列組合構成的模式。與關聯規則挖掘不同，序列模式挖掘的對象以及結果都是有序的，即數據集中的每個序列的條目在時間或空間上是有序排列的，輸出的結果也是有序的。由此可發現告警關聯知識，提供告警過濾，為進一步實現從告警到故障提供支撐。

考慮電力傳輸網絡復雜多變，告警數量龐大、實時性強，本文旨在研究告警的設備交互和時間窗特征，提出一種基于網絡和時間約束的告警序列模式挖掘方法，從而能夠有效地發現告警關聯知識，支撐根告警分析和故障診斷，協助運維人員進行快速的告警定位和故障處理。

2 序列模式挖掘研究現狀

近年國內外學者對序列模式挖掘做了大量的研究，序列模式挖掘就是從序列數據庫中找出所有滿足最小支持度的序列模式。通常需要引入約束以減少算法的搜索范圍，提高算法的有效性和執行效率。在序列模式挖掘算法中，引入特定的約束條件，可有效引導算法以搜索出其所關心的序列模式，避免產生大量沒有價值甚至會產生干擾作用的模式結論。

文獻［7］最早提出序列模式挖掘的理論和方法，介紹了3種基于Apriori算法框架的AprioriAll，AprioriSome和DynamicSome算法；文獻［8］提出了基于序列模式的增長不產生候選集的FreeSpan算法；文獻［9］提出PrefixsSpan算法是對FreeSpan算法的改進，減少了投影數據庫和子序列連接次數；文獻［10］給提出了一種基于PrefixSpan算法的改進算法，該算法可以減少構建投影數據庫的時間開銷和降低支持度增加對算法效率的影響；文獻［11］提出了周期性一般間隙約束的序列模式挖掘問題。

序列模式發掘非常適用于告警相關性分析，國內外學者也做了相關研究。文獻［12］研究了序列模式挖掘在網絡告警分析中的具體應用，提出了基于拓撲約束的互聯設備告警序列模式挖掘算法；文獻［13］提出了一種基于序列模式挖掘提取告警相關性規則的方法，構造了引入時間約束的序列模式挖掘算法；文獻［14］討論了挖掘情景規則的常用算法，提出了基于序列模式挖掘的告警關聯分析的網管系統模型。

此外關于告警相關性分析的一些其他研究，文獻［6］研究了基于組合規則的電力通信網故障分析方法；文獻［15］系統地介紹了提出了網絡相關性和時間相關性概念模型，并將其應用于告警相關性分析；文獻［1］給出了電力通信故障防御軟件的研究及實際應用案例，這些研究成果可和序列模式挖掘相結合，完善告警序列模式挖掘的研究應用。

3 算法設計

3.1 告警序列模式挖掘關鍵定義

定義1 項目:序列中最小組成單位，比如電力傳輸網絡的某條告警。

定義2 項目集:各種項目組成的集合。

定義3 序列:不同項目集的有序排列，序列s可以表示為s=＜ s1，s2，…，si，…，sl＞；sj（1 ≤ i≤l）為項目集，也稱為序列s的元素。

定義4 k頻繁序列:如果頻繁序列的項目個數為k，則稱之為k頻繁序列，以Fk表示。

定義5 支持度:序列x在序列數據庫S中的支持度為序列數據庫S中包含序列x的序列個數，記為Support（x）。

定義6 序列模式:給定支持度閾值ξ，如果序列x在序列數據庫S中的次數不低于ξ，則稱序列x為序列模式。長度為1的模式成為1-模式。

定義7 置信度:對于模式a和模式b（a∈b）之間的蘊涵關系a ≥ b-a，定義置信度conf=fr（b，s）/fr（a，s）表征蘊涵關系的強度。

定義8 模式規則:告警數據集中置信度conf大于給定最小置信度minConf的兩個頻繁模式之間蘊含的關系，表示為a≥b-a with conf。

序列模式挖掘，就是給定一個序列數據庫S以及最小支持度min_sup，找出所有支持度大于min_sup的序列模式。基于序列模式，合理設置置信度，可到得到模式規則，即最終提交給用戶或作為故障管理系統基礎的告警關聯知識，支撐告警過濾、告警定位及故障診斷等應用。

3.2 網絡約束分析

電力通信傳輸網絡發生的一組告警，其所在網元設備相同（存在關系Re），或其所在傳輸段相同（存在關系Rc），或其所在的業務通道相同（存在關系Rb），則被認為這組告警具備網絡相關性。

假設n個具備網絡相關性的告警依次為a1，a2，…，an，滿足網絡相關性要求的計算公式，如式（1）所示:

式中R表示關系；1≤x≤n，l≤y≤n。

3.3 時間約束分析

電力通信傳輸網絡發生的一組具有網絡相關性的告警，其發生時間基本處在一個有限或相對較短的時問段內，才被認為具有時間相關性。

為定量地描述時間相關性，可定義時間窗來實現。時間窗是為了界定一組告警在時間上是否相關，假設從最初一條到達，到最后一條到達之間的最長等待時間為Tmax。只有在時間窗內發生的告警，才被認為具有時間相關性。

設定n個具有時間相關性的告警的發生時間為:tl，ti，…，tn，則滿足時間相關性要求的計算公式，如式（2）所示:

3.4 告警序列模式挖掘流程

本文所述基于網絡和時間約束的告警序列模式挖掘算法流程，如圖1所示。

圖1 算法流程

步驟一:生成初始序列，獲取網絡管理系統中某段時間的告警記錄，進行數據整理和預處理，生成初始序列。

步驟二:網絡約束分析，結合告警所涉及的設備集，進行告警項目集分組，將單條的初始序列拆解為若干條序列，每條序列對應一組存在網絡約束關系的設備。

步驟三:時間約束分析，在網絡約束分析的基礎上，根據設定的時間跨度Δt，過濾掉時間窗之外的告警項目集，得到更新后的時間約束條件下的序列。

步驟四:序列模式挖掘，設定頻繁模式閾值C，找出度大于給定閾值的所有頻繁模式。頻繁模式的發現過程包括迭代的兩個階段，頻繁模式和剪枝，依次得到1-項集，2-項集，3-項集，…，l-項集。

步驟五:規范生成，設定合適的置信度Conf，基于步驟四得到的序列模式，生成最終規則，即提供給用戶的告警關聯知識。

4 算例分析

表1為某電網公司某段時間告警記錄數據，以此告警數據記錄為例，給出本文所述基于網絡和時間約束的告警序列模式挖掘方法的算例分析。

表1 某段時間告警記錄

4.1 生成初始序列

為表述更清晰直觀，對告警類型進行映射，如表2所示。

表2 告警類型映射表

基于告警類型映射表，可得到告警序列S=｛A（0），A（1），B（1），C（2），C（2），D（2），G（2），E（3），G（4），F（5），F（6），E（10），F（12），D（35）｝，K（i），K表示具有不同屬性的告警事件，i表示事件發生的相對時間。

告警序列S，即初始序列，可用表3方法表示。

表3 初始序列

4.2 網絡約束分析

由告警序列相關的告警設備，可知告警來自設備集M，其中設備集M=｛設備1，設備2，設備3，設備4，設備5，設備6，設備7｝，結合網絡管理系統得到設備連接關系如圖2所示。

圖2 SDH網絡傳輸拓撲圖

結合網絡管理系統業務開通情況，可得到圖中包含的兩條電路，分別為設備1＜-＞設備3＜-＞設備4；設備2＜-＞設備5＜-＞設備6＜-＞設備7。故可將初始序列拆分為兩條子序列，如表4所示。

表4 網絡約束下的序列

4.3 時間約束分析

假定時間跨度Δt=15s，過濾掉時間窗之外的告警項目集，可得到時間約束條件下的序列，如表5所示。

表5 時間約束下的序列

4.4 序列模式挖掘

假定頻繁模式的閾值C=2，找出度大于給定閾值的所有頻繁模式。頻繁模式的發現過程包括迭代的兩個階段，頻繁模式和剪枝，依次得到1-項集，2-項集，3-項集，4-項集，如圖3所示。

圖3 序列模式挖掘

4.5 規則生成

假定置信度為70%，基于上一小節得到的序列模 式 ＜A，C，E，F＞，生 成 最 終 規 則 :R_LOS-＞MS_AIS-＞AU_AIS-＞TU_AIS。

類似的規則依靠傳統手段不易獲得，需依賴傳輸設備及網絡非常精通的業務技術專家添加和維護。

4.6 實際驗證

結合某電網公司3個月的傳輸網絡告警數據進行了算法驗證。該電網公司3個月期間共收到告警數據593561條，平均每條告警數量6000多條，給運維人員的告警監視和故障分析工作帶來了很大挑戰，之前采用人工配置維護白名單的方式，但是由于網絡拓撲和設備類型、型號等變化較快，導致告警關聯規則更新不及時，實際告警壓縮和分析效果不理想。

采用本文所述方案，對不同的時間窗、支持度、置信度進行算法驗證，分別得到的規則數如表5所示。經過業務專家深入細致的比對和核實，發現時間窗設置為15s，支持度設置為3次，置信度設置為70%時效果最佳。既避免了規則數過少失去挖掘分析的意義，又避免規則數過多，部分規則不符合實際需求的情況。

采用本文所述方法，該電網公司故障管理系統的告警關聯規則庫實現了自動學習和更新，提升了告警壓縮率和故障處理效率。

表5 規則生成

5 結語

算例分析和實際驗證表明，相較于傳統的人工配置告警白名單的告警過濾手段，基于網絡和時間約束的告警序列模式挖掘方法不依賴于專家經驗和先驗知識，可識別復雜網絡的告警特征，提高告警序列模式挖掘的針對性和效率，可有效發現告警關聯知識，有利于告警的準確有效定位，使運維人員能及時發現故障并快速解決，提高了電力通信網可靠性及通信運維管理水平，對電力業務運行的安全性和穩定性具有重大意義。