基于網(wǎng)絡(luò)和時(shí)間約束的告警序列模式挖掘研究?

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

（南方電網(wǎng)調(diào)峰調(diào)頻發(fā)電有限公司 廣州 510630）

1 引言

隨著電力通信網(wǎng)絡(luò)及業(yè)務(wù)的快速發(fā)展，電力通信技術(shù)已經(jīng)成為電力生產(chǎn)的一個(gè)重要環(huán)節(jié)，電力通信傳輸網(wǎng)絡(luò)的可靠性成為影響著電力生產(chǎn)安全的重要組成部分［1］。

告警是故障的外在呈現(xiàn)，具有傳遞性和多方面、多環(huán)節(jié)顯現(xiàn)等特點(diǎn)［2～6］，即一條根告警會(huì)引起大量次要衍生告警，甚至可能引起“告警風(fēng)暴”。運(yùn)維人員如能第一時(shí)間對(duì)系統(tǒng)告警準(zhǔn)確判斷并及時(shí)處理，可以大大減少故障處理時(shí)間，迅速恢復(fù)業(yè)務(wù)系統(tǒng)正常使用，故告警相關(guān)性分析是故障分析和處理的基礎(chǔ)。

由于傳統(tǒng)手段依賴(lài)告警規(guī)則樹(shù)、白名單等先驗(yàn)知識(shí)，無(wú)法適應(yīng)網(wǎng)絡(luò)復(fù)雜多變的特點(diǎn)，而告警序列模式挖掘是實(shí)現(xiàn)告警相關(guān)性分析的重要方法。序列模式挖掘最早由 Agrawal和 Srikant提出［7］，序列模式是在一組有序的數(shù)據(jù)列組成的數(shù)據(jù)集中，經(jīng)常出現(xiàn)的那些序列組合構(gòu)成的模式。與關(guān)聯(lián)規(guī)則挖掘不同，序列模式挖掘的對(duì)象以及結(jié)果都是有序的，即數(shù)據(jù)集中的每個(gè)序列的條目在時(shí)間或空間上是有序排列的，輸出的結(jié)果也是有序的。由此可發(fā)現(xiàn)告警關(guān)聯(lián)知識(shí)，提供告警過(guò)濾，為進(jìn)一步實(shí)現(xiàn)從告警到故障提供支撐。

考慮電力傳輸網(wǎng)絡(luò)復(fù)雜多變，告警數(shù)量龐大、實(shí)時(shí)性強(qiáng)，本文旨在研究告警的設(shè)備交互和時(shí)間窗特征，提出一種基于網(wǎng)絡(luò)和時(shí)間約束的告警序列模式挖掘方法，從而能夠有效地發(fā)現(xiàn)告警關(guān)聯(lián)知識(shí)，支撐根告警分析和故障診斷，協(xié)助運(yùn)維人員進(jìn)行快速的告警定位和故障處理。

2 序列模式挖掘研究現(xiàn)狀

近年國(guó)內(nèi)外學(xué)者對(duì)序列模式挖掘做了大量的研究，序列模式挖掘就是從序列數(shù)據(jù)庫(kù)中找出所有滿(mǎn)足最小支持度的序列模式。通常需要引入約束以減少算法的搜索范圍，提高算法的有效性和執(zhí)行效率。在序列模式挖掘算法中，引入特定的約束條件，可有效引導(dǎo)算法以搜索出其所關(guān)心的序列模式，避免產(chǎn)生大量沒(méi)有價(jià)值甚至?xí)a(chǎn)生干擾作用的模式結(jié)論。

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

序列模式發(fā)掘非常適用于告警相關(guān)性分析，國(guó)內(nèi)外學(xué)者也做了相關(guān)研究。文獻(xiàn)［12］研究了序列模式挖掘在網(wǎng)絡(luò)告警分析中的具體應(yīng)用，提出了基于拓?fù)浼s束的互聯(lián)設(shè)備告警序列模式挖掘算法；文獻(xiàn)［13］提出了一種基于序列模式挖掘提取告警相關(guān)性規(guī)則的方法，構(gòu)造了引入時(shí)間約束的序列模式挖掘算法；文獻(xiàn)［14］討論了挖掘情景規(guī)則的常用算法，提出了基于序列模式挖掘的告警關(guān)聯(lián)分析的網(wǎng)管系統(tǒng)模型。

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

3 算法設(shè)計(jì)

3.1 告警序列模式挖掘關(guān)鍵定義

定義1 項(xiàng)目:序列中最小組成單位，比如電力傳輸網(wǎng)絡(luò)的某條告警。

定義2 項(xiàng)目集:各種項(xiàng)目組成的集合。

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

定義4 k頻繁序列:如果頻繁序列的項(xiàng)目個(gè)數(shù)為k，則稱(chēng)之為k頻繁序列，以Fk表示。

定義5 支持度:序列x在序列數(shù)據(jù)庫(kù)S中的支持度為序列數(shù)據(jù)庫(kù)S中包含序列x的序列個(gè)數(shù)，記為Support（x）。

定義6 序列模式:給定支持度閾值ξ，如果序列x在序列數(shù)據(jù)庫(kù)S中的次數(shù)不低于ξ，則稱(chēng)序列x為序列模式。長(zhǎng)度為1的模式成為1-模式。

定義7 置信度:對(duì)于模式a和模式b（a∈b）之間的蘊(yùn)涵關(guān)系a ≥ b-a，定義置信度conf=fr（b，s）/fr（a，s）表征蘊(yùn)涵關(guān)系的強(qiáng)度。

定義8 模式規(guī)則:告警數(shù)據(jù)集中置信度conf大于給定最小置信度minConf的兩個(gè)頻繁模式之間蘊(yùn)含的關(guān)系，表示為a≥b-a with conf。

序列模式挖掘，就是給定一個(gè)序列數(shù)據(jù)庫(kù)S以及最小支持度min_sup，找出所有支持度大于min_sup的序列模式?；谛蛄心Ｊ?，合理設(shè)置置信度，可到得到模式規(guī)則，即最終提交給用戶(hù)或作為故障管理系統(tǒng)基礎(chǔ)的告警關(guān)聯(lián)知識(shí)，支撐告警過(guò)濾、告警定位及故障診斷等應(yīng)用。

3.2 網(wǎng)絡(luò)約束分析

電力通信傳輸網(wǎng)絡(luò)發(fā)生的一組告警，其所在網(wǎng)元設(shè)備相同（存在關(guān)系Re），或其所在傳輸段相同（存在關(guān)系Rc），或其所在的業(yè)務(wù)通道相同（存在關(guān)系Rb），則被認(rèn)為這組告警具備網(wǎng)絡(luò)相關(guān)性。

假設(shè)n個(gè)具備網(wǎng)絡(luò)相關(guān)性的告警依次為a1，a2，…，an，滿(mǎn)足網(wǎng)絡(luò)相關(guān)性要求的計(jì)算公式，如式（1）所示:

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

3.3 時(shí)間約束分析

電力通信傳輸網(wǎng)絡(luò)發(fā)生的一組具有網(wǎng)絡(luò)相關(guān)性的告警，其發(fā)生時(shí)間基本處在一個(gè)有限或相對(duì)較短的時(shí)問(wèn)段內(nèi)，才被認(rèn)為具有時(shí)間相關(guān)性。

為定量地描述時(shí)間相關(guān)性，可定義時(shí)間窗來(lái)實(shí)現(xiàn)。時(shí)間窗是為了界定一組告警在時(shí)間上是否相關(guān)，假設(shè)從最初一條到達(dá)，到最后一條到達(dá)之間的最長(zhǎng)等待時(shí)間為T(mén)max。只有在時(shí)間窗內(nèi)發(fā)生的告警，才被認(rèn)為具有時(shí)間相關(guān)性。

設(shè)定n個(gè)具有時(shí)間相關(guān)性的告警的發(fā)生時(shí)間為:tl，ti，…，tn，則滿(mǎn)足時(shí)間相關(guān)性要求的計(jì)算公式，如式（2）所示:

3.4 告警序列模式挖掘流程

本文所述基于網(wǎng)絡(luò)和時(shí)間約束的告警序列模式挖掘算法流程，如圖1所示。

圖1 算法流程

步驟一:生成初始序列，獲取網(wǎng)絡(luò)管理系統(tǒng)中某段時(shí)間的告警記錄，進(jìn)行數(shù)據(jù)整理和預(yù)處理，生成初始序列。

步驟二:網(wǎng)絡(luò)約束分析，結(jié)合告警所涉及的設(shè)備集，進(jìn)行告警項(xiàng)目集分組，將單條的初始序列拆解為若干條序列，每條序列對(duì)應(yīng)一組存在網(wǎng)絡(luò)約束關(guān)系的設(shè)備。

步驟三:時(shí)間約束分析，在網(wǎng)絡(luò)約束分析的基礎(chǔ)上，根據(jù)設(shè)定的時(shí)間跨度Δt，過(guò)濾掉時(shí)間窗之外的告警項(xiàng)目集，得到更新后的時(shí)間約束條件下的序列。

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

步驟五:規(guī)范生成，設(shè)定合適的置信度Conf，基于步驟四得到的序列模式，生成最終規(guī)則，即提供給用戶(hù)的告警關(guān)聯(lián)知識(shí)。

4 算例分析

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

表1 某段時(shí)間告警記錄

4.1 生成初始序列

為表述更清晰直觀，對(duì)告警類(lèi)型進(jìn)行映射，如表2所示。

表2 告警類(lèi)型映射表

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

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

表3 初始序列

4.2 網(wǎng)絡(luò)約束分析

由告警序列相關(guān)的告警設(shè)備，可知告警來(lái)自設(shè)備集M，其中設(shè)備集M=｛設(shè)備1，設(shè)備2，設(shè)備3，設(shè)備4，設(shè)備5，設(shè)備6，設(shè)備7｝，結(jié)合網(wǎng)絡(luò)管理系統(tǒng)得到設(shè)備連接關(guān)系如圖2所示。

圖2 SDH網(wǎng)絡(luò)傳輸拓?fù)鋱D

結(jié)合網(wǎng)絡(luò)管理系統(tǒng)業(yè)務(wù)開(kāi)通情況，可得到圖中包含的兩條電路，分別為設(shè)備1＜-＞設(shè)備3＜-＞設(shè)備4；設(shè)備2＜-＞設(shè)備5＜-＞設(shè)備6＜-＞設(shè)備7。故可將初始序列拆分為兩條子序列，如表4所示。

表4 網(wǎng)絡(luò)約束下的序列

4.3 時(shí)間約束分析

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

表5 時(shí)間約束下的序列

4.4 序列模式挖掘

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

圖3 序列模式挖掘

4.5 規(guī)則生成

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

類(lèi)似的規(guī)則依靠傳統(tǒng)手段不易獲得，需依賴(lài)傳輸設(shè)備及網(wǎng)絡(luò)非常精通的業(yè)務(wù)技術(shù)專(zhuān)家添加和維護(hù)。

4.6 實(shí)際驗(yàn)證

結(jié)合某電網(wǎng)公司3個(gè)月的傳輸網(wǎng)絡(luò)告警數(shù)據(jù)進(jìn)行了算法驗(yàn)證。該電網(wǎng)公司3個(gè)月期間共收到告警數(shù)據(jù)593561條，平均每條告警數(shù)量6000多條，給運(yùn)維人員的告警監(jiān)視和故障分析工作帶來(lái)了很大挑戰(zhàn)，之前采用人工配置維護(hù)白名單的方式，但是由于網(wǎng)絡(luò)拓?fù)浜驮O(shè)備類(lèi)型、型號(hào)等變化較快，導(dǎo)致告警關(guān)聯(lián)規(guī)則更新不及時(shí)，實(shí)際告警壓縮和分析效果不理想。

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

采用本文所述方法，該電網(wǎng)公司故障管理系統(tǒng)的告警關(guān)聯(lián)規(guī)則庫(kù)實(shí)現(xiàn)了自動(dòng)學(xué)習(xí)和更新，提升了告警壓縮率和故障處理效率。

表5 規(guī)則生成

5 結(jié)語(yǔ)

算例分析和實(shí)際驗(yàn)證表明，相較于傳統(tǒng)的人工配置告警白名單的告警過(guò)濾手段，基于網(wǎng)絡(luò)和時(shí)間約束的告警序列模式挖掘方法不依賴(lài)于專(zhuān)家經(jīng)驗(yàn)和先驗(yàn)知識(shí)，可識(shí)別復(fù)雜網(wǎng)絡(luò)的告警特征，提高告警序列模式挖掘的針對(duì)性和效率，可有效發(fā)現(xiàn)告警關(guān)聯(lián)知識(shí)，有利于告警的準(zhǔn)確有效定位，使運(yùn)維人員能及時(shí)發(fā)現(xiàn)故障并快速解決，提高了電力通信網(wǎng)可靠性及通信運(yùn)維管理水平，對(duì)電力業(yè)務(wù)運(yùn)行的安全性和穩(wěn)定性具有重大意義。