齊小剛，胡秋秋，姚旭清，劉立芳

(1.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710071；2.中國(guó)移動(dòng)集團(tuán)公司 山西有限公司，山西 太原 030002；3.西安電子科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710071)

通信網(wǎng)絡(luò)管理主要是對(duì)網(wǎng)絡(luò)的日常運(yùn)行進(jìn)行實(shí)時(shí)監(jiān)控，以保證通信網(wǎng)絡(luò)的高效可靠運(yùn)行。隨著信息技術(shù)的不斷發(fā)展，通信網(wǎng)絡(luò)規(guī)模持續(xù)擴(kuò)大，網(wǎng)絡(luò)結(jié)構(gòu)也日益復(fù)雜，使得網(wǎng)絡(luò)中任何設(shè)備發(fā)生故障或異常都會(huì)觸發(fā)其它互連設(shè)備，引發(fā)越來(lái)越多的告警數(shù)據(jù)，從而增加了故障診斷和定位的難度[1]。因此，從網(wǎng)絡(luò)告警數(shù)據(jù)中挖掘出有助于故障診斷和定位的知識(shí)信息是通信網(wǎng)絡(luò)管理的基礎(chǔ)。

告警相關(guān)性分析可將多個(gè)告警合并為一個(gè)具有更多信息的告警規(guī)則，從而找出引發(fā)故障的根源告警。典型的告警相關(guān)性分析方法有：基于場(chǎng)景的方法[2]、基于相似性的方法[3]和基于因果的方法[4]?；趫?chǎng)景的方法主要依據(jù)已有故障行為所抽象成的知識(shí)庫(kù)，需要專家知識(shí)或推理知識(shí)不斷更新知識(shí)庫(kù)，從而難以發(fā)現(xiàn)并解決新的故障行為；基于相似性的方法主要取決于所選擇的度量函數(shù)，對(duì)事先選取相似性度量函數(shù)要求很高；基于因果的方法需要建立比較精準(zhǔn)的模型，且只適合每個(gè)步驟之間有明顯因果關(guān)系的故障分析中。雖然以上方法在相應(yīng)的情景中可以進(jìn)行告警分析，但隨著告警數(shù)據(jù)類型和數(shù)據(jù)量的增多，上述方法一定程度上需要依靠專家經(jīng)驗(yàn)已逐漸不能滿足實(shí)際需求。因此，基于數(shù)據(jù)挖掘的告警相關(guān)分析研究倍受研究人員的關(guān)注，其中關(guān)聯(lián)規(guī)則挖掘算法和序列模式挖掘算法被廣泛應(yīng)用于通信網(wǎng)絡(luò)的告警相關(guān)性分析中。文獻(xiàn)[5]將關(guān)聯(lián)規(guī)則挖掘算法和群體智能算法應(yīng)用于通信領(lǐng)域，提出了基于粒子群優(yōu)化的告警關(guān)聯(lián)規(guī)則挖掘算法；同樣，文獻(xiàn)[6]將告警規(guī)則挖掘問(wèn)題轉(zhuǎn)化為蟻群旅行商問(wèn)題，提出基于小生境跳蟻群的告警關(guān)聯(lián)規(guī)則挖掘算法。文獻(xiàn)[7]提出了一種基于前綴樹(shù)和局部增長(zhǎng)樹(shù)數(shù)據(jù)結(jié)構(gòu)相結(jié)合的并行頻繁模式增長(zhǎng)算法，提高了告警關(guān)聯(lián)規(guī)則挖掘的效率。另外，考慮到告警發(fā)生具有時(shí)間上的先后順序，序列模式挖掘算法常常被用來(lái)識(shí)別網(wǎng)絡(luò)發(fā)生故障時(shí)告警之間存在的潛在時(shí)序關(guān)系[8]，并廣泛應(yīng)用于其他領(lǐng)域[9-10]。文獻(xiàn)[11]設(shè)計(jì)了一種基于扇形撲動(dòng)和父子規(guī)則的告警模式挖掘系統(tǒng)，該系統(tǒng)利用序列模式挖掘算法搜索序列模式，并利用父子規(guī)則找到與故障相關(guān)的告警規(guī)則；文獻(xiàn)[12]利用序列模式挖掘算法發(fā)現(xiàn)了網(wǎng)絡(luò)節(jié)點(diǎn)與問(wèn)題之間的關(guān)系。以上基于數(shù)據(jù)挖掘的告警分析方法都把告警看作是平等的，沒(méi)有考慮告警對(duì)網(wǎng)絡(luò)的影響等其他信息，因此，僅會(huì)挖掘出大部分出現(xiàn)頻繁的告警，卻很難發(fā)現(xiàn)那些發(fā)生次數(shù)少卻對(duì)網(wǎng)絡(luò)影響比較大的告警，從而難以挖掘到包含重要意義的告警知識(shí)。文獻(xiàn)[13]將告警看作是不平等的，并表示支持向量機(jī)適合于告警的權(quán)值分配，但支持向量機(jī)是需要大量訓(xùn)練數(shù)據(jù)集的有監(jiān)督算法，然而實(shí)際應(yīng)用中往往無(wú)法事先獲取大量有代表性的訓(xùn)練樣本；其次，該文獻(xiàn)提出的告警挖掘方法沒(méi)有考慮告警發(fā)生的時(shí)間順序，因此，無(wú)法挖掘到告警之間的時(shí)序關(guān)系。

在實(shí)際的通信網(wǎng)絡(luò)中，各個(gè)告警對(duì)網(wǎng)絡(luò)的影響程度不同，且由同一故障引發(fā)的告警之間都存在時(shí)序關(guān)系，使得告警的發(fā)生、發(fā)生的順序以及告警發(fā)生對(duì)網(wǎng)絡(luò)設(shè)備和業(yè)務(wù)的影響程度對(duì)告警規(guī)則的挖掘都具有非常重要的作用。因此，如何根據(jù)告警的重要性分配相應(yīng)的權(quán)值，并建立相應(yīng)的加權(quán)告警數(shù)據(jù)挖掘模型來(lái)發(fā)現(xiàn)告警之間的時(shí)序關(guān)系是該文研究的關(guān)鍵問(wèn)題。

該文根據(jù)通信網(wǎng)絡(luò)告警數(shù)據(jù)的特點(diǎn)，利用熵值法為各告警分配權(quán)值以說(shuō)明其對(duì)網(wǎng)絡(luò)的影響程度，并系統(tǒng)地探索了一種基于投影和模式增長(zhǎng)的加權(quán)告警序列模式挖掘算法，來(lái)搜索告警數(shù)據(jù)中的加權(quán)告警序列模式以表示告警之間的時(shí)序關(guān)系。同時(shí)，將一種新穎的剪枝策略應(yīng)用于這種算法中，以減少挖掘過(guò)程中需要搜索的數(shù)據(jù)集大小。實(shí)驗(yàn)結(jié)果表明，該算法能快速有效地挖掘不同級(jí)別告警之間隱藏的時(shí)序關(guān)系，并包含更多的重要告警。

1 網(wǎng)絡(luò)故障與告警

網(wǎng)絡(luò)故障指網(wǎng)絡(luò)運(yùn)行過(guò)程中出現(xiàn)的導(dǎo)致網(wǎng)絡(luò)及設(shè)備無(wú)法提供正常服務(wù)的異?，F(xiàn)象。網(wǎng)絡(luò)告警是在系統(tǒng)中發(fā)生網(wǎng)絡(luò)故障時(shí)自動(dòng)觸發(fā)的消息記錄，用于傳輸所定義的信息。通常，這類消息都有其特定的含義并包括有關(guān)告警的告警名稱、設(shè)備信息、網(wǎng)元名稱以及告警發(fā)生的時(shí)間等，以通知網(wǎng)絡(luò)管理員系統(tǒng)中可能出現(xiàn)的故障[14]。但告警通常不包括關(guān)于網(wǎng)絡(luò)中故障的確切位置和問(wèn)題根源的明確信息。因此，需要通過(guò)分析告警數(shù)據(jù)從而發(fā)現(xiàn)和故障有關(guān)的告警信息來(lái)確定故障根源。

表1告警實(shí)例

屬性內(nèi)容屬性內(nèi)容屬性內(nèi)容告警設(shè)備類型PTN網(wǎng)元名稱53-147-XX-HW-PTN1對(duì)設(shè)備的影響無(wú)影響告警標(biāo)題ETL_LOS告警發(fā)生時(shí)間2018-10-30 01:45:49對(duì)業(yè)務(wù)的影響可能全阻告警級(jí)別三級(jí)告警告警清除時(shí)間2018-10-30 01:46:16

在移動(dòng)通信網(wǎng)絡(luò)中，一個(gè)告警實(shí)例通常包含告警標(biāo)題、網(wǎng)元名稱、告警級(jí)別等屬性，標(biāo)題為“ETH_LOS”的告警實(shí)例如表1所示，其中告警級(jí)別、對(duì)設(shè)備的影響和對(duì)業(yè)務(wù)的影響可以反映一個(gè)告警的重要程度。另外，通信網(wǎng)絡(luò)中的重要告警發(fā)生次數(shù)要遠(yuǎn)遠(yuǎn)小于一般告警的發(fā)生次數(shù)，但一個(gè)重要告警對(duì)網(wǎng)絡(luò)服務(wù)的影響卻比無(wú)數(shù)一般告警的影響大很多。因此，可為不同類型的告警分配不同的權(quán)值以反映其對(duì)網(wǎng)絡(luò)的影響程度。由于通信網(wǎng)絡(luò)的異構(gòu)性和復(fù)雜性使得告警類型有成千上萬(wàn)種，僅依靠專家經(jīng)驗(yàn)或主觀判斷無(wú)法快速且有效地為告警分配權(quán)值。熵值法[15]是一種根據(jù)評(píng)價(jià)指標(biāo)的信息熵，來(lái)計(jì)算評(píng)價(jià)對(duì)象權(quán)值的客觀賦值方法，因此可利用熵值法來(lái)計(jì)算告警屬性的信息熵，從而達(dá)到客觀計(jì)算告警權(quán)值的目的。該方法相對(duì)于主觀賦值法，計(jì)算更加科學(xué)化，且精度較高。

2 基于熵值法的告警權(quán)值設(shè)計(jì)

2.1 熵值法的相關(guān)概念

2.2 告警權(quán)值的設(shè)計(jì)方法

每個(gè)告警都包含許多不同的屬性，為了表明不同告警的重要程度，主要用對(duì)設(shè)備的影響、對(duì)業(yè)務(wù)的影響以及告警級(jí)別這三個(gè)屬性信息來(lái)表示各個(gè)告警對(duì)網(wǎng)絡(luò)的影響程度，并用熵值法來(lái)計(jì)算各個(gè)告警的權(quán)值。表2顯示了一些告警實(shí)例的相應(yīng)告警屬性，包括5個(gè)評(píng)價(jià)對(duì)象和3個(gè)評(píng)價(jià)指標(biāo)。

表2 一些告警信息實(shí)例

利用熵值法計(jì)算表2告警實(shí)例中的告警權(quán)值的步驟如下：

步驟2 根據(jù)式(1)標(biāo)準(zhǔn)化矩陣X=(xij)m×n，從而得矩陣Xnorm=(xij′)m×n，其結(jié)果為

xij′=xij-xmin/xmax-xmin。

(1)

步驟4 根據(jù)各個(gè)屬性的熵權(quán)，由式(2)可計(jì)算各個(gè)告警的權(quán)值分別為Wa=0.82，Wb=0.42，Wc=0.09，Wd=0.26，We=0.58。

(2)

結(jié)果顯示，告警越重要，其權(quán)值越大。因此，熵值法可以有效地確定通信網(wǎng)絡(luò)中告警的權(quán)值。

3 加權(quán)告警序列模式挖掘算法設(shè)計(jì)

3.1 算法相關(guān)概念定義

為了清晰描述加權(quán)告警序列模式挖掘問(wèn)題，下面定義該算法的一些相關(guān)概念。

前綴和后綴：假設(shè)每個(gè)告警序列中的項(xiàng)集都是按時(shí)間順序排列。已知告警序列α=〈e1e2...en〉和β=〈e′1e′2...e′m〉,(m≤n)，序列β為α的前綴，當(dāng)且僅當(dāng)：(a)e′i=ei(i≤m-1)；(b)e′m?em；(c)(em-e′m)中的所有頻繁項(xiàng)都在e′m后。若序列χ=〈e1e2...e′m〉,(m≤n)是序列α的前綴，則序列γ=〈e″mem+1...en〉是序列α以χ為前綴的后綴，其中e″m=em-e′m。

項(xiàng)集權(quán)重：對(duì)于給定項(xiàng)集e=(i1i2...im)，其中每個(gè)告警項(xiàng)ij∈e對(duì)應(yīng)的權(quán)重為wj，那么項(xiàng)集e的權(quán)重定義為該項(xiàng)集內(nèi)所有項(xiàng)的權(quán)重的平均值：

(3)

序列權(quán)重：對(duì)于給定項(xiàng)集α=〈e1e2...ek〉，其中每個(gè)項(xiàng)集ej∈α對(duì)應(yīng)的權(quán)重為w(ej)，那么序列α的權(quán)重定義為該序列內(nèi)所有項(xiàng)集的權(quán)重的平均值：

(4)

加權(quán)支持度：數(shù)據(jù)集D是元組〈sid,S〉的集合。那么告警序列T的加權(quán)支持度等于數(shù)據(jù)集D中含有T的序列個(gè)數(shù)和序列T的權(quán)值之積與D中所有序列的權(quán)值之和的比值：

(5)

加權(quán)告警序列模式：假設(shè)最小加權(quán)支持度閾值ξ(ξ∈(0,1])，若告警序列T的加權(quán)支持度滿足Wsup(T)≥ξ，則T為加權(quán)告警序列模式，有l(wèi)個(gè)項(xiàng)的加權(quán)告警序列模式稱為l-加權(quán)告警序列模式。

加權(quán)頻繁告警項(xiàng)：對(duì)于一個(gè)告警項(xiàng)i，若該項(xiàng)的加權(quán)支持度Wsup(i)不小于最小支持度閾值ξ，則該項(xiàng)i為加權(quán)頻繁告警項(xiàng)；否則，為非加權(quán)頻繁告警項(xiàng)。其中項(xiàng)i的加權(quán)支持度Wsup(i)等于當(dāng)前搜索的數(shù)據(jù)集中包含項(xiàng)i的序列數(shù)和項(xiàng)i的權(quán)值之積與原數(shù)據(jù)集D中所有序列的權(quán)值之和的比值。

3.2 算法的模型和剪枝策略

為了避免在加權(quán)告警序列模式挖掘過(guò)程中產(chǎn)生候選子序列影響算法效率，該算法采用了投影和模式增長(zhǎng)模型遞歸地挖掘加權(quán)告警序列模式。首先從加權(quán)告警序列數(shù)據(jù)集中搜索1-加權(quán)告警序列模式，從l=1開(kāi)始分別遞歸構(gòu)造以l-加權(quán)告警序列模式為前綴的投影數(shù)據(jù)集；然后從投影數(shù)據(jù)集中搜索加權(quán)頻繁告警項(xiàng)，并將其分別附加到l-加權(quán)序列模式后從而形成l+1-加權(quán)告警序列模式。

傳統(tǒng)的序列模式挖掘算法均遵循序列模式的全部子序列都是序列模式和非序列模式的任何超序列都肯定不是序列模式的向下閉合原則[9]。這里將該原則應(yīng)用于新提出的算法的剪枝策略中，以減少遞歸挖掘過(guò)程的計(jì)算負(fù)荷。下面介紹新提出的算法的剪枝策略。

對(duì)于l-加權(quán)告警序列模式sl，假設(shè)已經(jīng)搜索到〈sl〉-投影數(shù)據(jù)集中的所有加權(quán)頻繁告警項(xiàng)，并將每個(gè)加權(quán)頻繁告警項(xiàng)分別附加到l-加權(quán)告警序列模式sl后形成l+1-加權(quán)告警序列模式sl+1；然后分別從以包含〈sl〉的l+1-加權(quán)告警序列模式為前綴的后綴序列中刪除所有非加權(quán)頻繁項(xiàng)，形成〈sl+1〉-投影數(shù)據(jù)集。顯然，在這個(gè)遞歸過(guò)程中，許多非頻繁的加權(quán)告警子序列被修剪，極大地減少了對(duì)投影數(shù)據(jù)集的挖掘過(guò)程，且新提出的算法仍保持傳統(tǒng)序列模式挖掘中的向下閉合原則。

3.3 算法流程和算法分析

為了簡(jiǎn)潔，將“告警a”用“a”表示，以此類推。表3為網(wǎng)絡(luò)故障時(shí)的告警序列數(shù)據(jù)集實(shí)例。

對(duì)于表3的告警序列集，且給定ξ=0.5；各告警項(xiàng)的權(quán)值分別為wa=0.3，wb=0.2，wc=0.2，wd=0.4，we=0.3，wf=0.4，wg=0.9。該算法挖掘加權(quán)告警序列模式的詳細(xì)步驟如下:

表3 告警序列數(shù)據(jù)集實(shí)例

步驟1 根據(jù)式(4)可計(jì)算表3中4個(gè)告警序列的權(quán)重分別為0.26，0.28，0.31和0.39。

步驟2 掃描表3中的告警序列數(shù)據(jù)集。以告警項(xiàng)a為例，可以發(fā)現(xiàn)所有的告警序列里均發(fā)生了a，因此，根據(jù)概念可計(jì)算Wsup(a)=(0.3×4)/(0.26+0.28+0.31+0.39) =0.97。類似地，可計(jì)算所有告警項(xiàng)的支持度分別為a:0.97，b:0.65，c:0.48，d:0.97，e:0.73，f:0.97，g:0.73。

步驟3 將告警項(xiàng)看作1-序列，可得〈a〉，〈b〉，〈d〉，〈e〉，〈f〉，〈g〉為1-加權(quán)告警序列模式。分別挖掘以〈a〉，〈b〉，〈d〉，〈e〉，〈f〉，〈g〉為前綴的加權(quán)告警序列模式。

(i) 由于告警項(xiàng)c不是告警數(shù)據(jù)集的頻繁告警項(xiàng)，由向下閉合原則可知，后續(xù)挖掘過(guò)程中不會(huì)形成任何包含告警項(xiàng)c的加權(quán)告警序列模式，因此，根據(jù)剪枝策略，刪除所有以1-加權(quán)告警序列模式為前綴的后綴序列中的所有告警項(xiàng)c。

(ii) 以前綴〈a〉為例，其后綴包括〈(bd)bcb(ade)〉，〈(_b)(df)cb〉，〈(_d)(bf)abf〉 和〈(_f)bc〉。然后，刪除所有后綴序列中的告警項(xiàng)c，從而得到〈a〉-投影數(shù)據(jù)集，包含〈(bd)bb(ade)〉，〈(_b)(df)b〉，〈(_d)(bf)abf〉和〈(_f)b〉。

(iii) 掃描〈a〉-投影數(shù)據(jù)集，可知僅有項(xiàng)a，b，(_b)，d，(_d)，e，f，(_f)發(fā)生在〈a〉后可形成2-序列。計(jì)算a，b，(_b)，d，(_d)，e，f，(_f)的加權(quán)支持度，知b，d，(_d)，f為〈a〉-投影數(shù)據(jù)集的頻繁告警項(xiàng)(注：(_d)和d是不一樣的，d表示和前綴a在不同項(xiàng)集內(nèi)，(_d)表示和前綴a在相同項(xiàng)集內(nèi)。故(_d)和(ad)為相同含義，即(_d)出現(xiàn)在〈a〉-投影數(shù)據(jù)集的第一個(gè)和第三個(gè)序列中。)，將其分別添加到1-加權(quán)告警序列模式〈a〉后形成以〈a〉為前綴的2-加權(quán)告警序列模式：〈ab〉:0.65，〈ad〉:0.65，〈(ad)〉:0.65和〈af〉:0.65。

(iv) 由于a，(_b)，e，(_f)是〈a〉-投影數(shù)據(jù)集中的非加權(quán)頻繁告警項(xiàng)，因此，根據(jù)剪枝策略刪除所有以包含〈a〉的2-加權(quán)告警序列模式為前綴的后綴中的告警項(xiàng)a，(_b)，e，(_f)。以前綴〈ab〉為例，其包含〈(_d)bb(ade)〉和〈(_f)abf〉兩個(gè)后綴，刪除非頻繁告警項(xiàng)后，〈ab〉-投影數(shù)據(jù)集中包含〈(_d)bbd〉和〈bf〉。掃描〈ab〉-投影數(shù)據(jù)集，可知僅有告警項(xiàng)b，d，(_d)，f發(fā)生在2-序列〈ab〉后可形成3-序列。計(jì)算告警項(xiàng)b，d，(_d)，f的支持度，可知沒(méi)有加權(quán)頻繁項(xiàng)，從而不會(huì)有3-加權(quán)告警序列模式產(chǎn)生，因此以〈ab〉為前綴的遞歸挖掘過(guò)程結(jié)束。同樣地，〈ad〉，〈(ad)〉和〈af〉-投影數(shù)據(jù)集可以以同樣的方式遞歸地建立和挖掘。最后，就可以導(dǎo)出以〈a〉為前綴的所有加權(quán)告警序列模式。

類似地，通過(guò)遞歸地構(gòu)造并挖掘以〈b〉，〈d〉，〈e〉，〈f〉和〈g〉為前綴的投影數(shù)據(jù)集，從而可導(dǎo)出所有加權(quán)告警序列模式。綜上所述，該算法用于加權(quán)告警序列挖掘的算法流程如下：

算法加權(quán)告警序列模式挖掘算法。

輸入:D表示告警數(shù)據(jù)集；W表示各個(gè)告警權(quán)值數(shù)據(jù)；ξ表示最小加權(quán)支持度閾值。

輸出: 所有加權(quán)告警序列模式。

步驟1 對(duì)于數(shù)據(jù)集D中的每個(gè)告警序列S，根據(jù)式(4)計(jì)算各個(gè)序列的權(quán)重W(S)。

步驟2 查找所有告警項(xiàng)，將各告警項(xiàng)看作1-序列，并計(jì)算其加權(quán)支持度，把加權(quán)支持度不小于ξ的1-序列加入1-加權(quán)告警序列模式數(shù)據(jù)集Seq1，令l=1(l代表序列中告警項(xiàng)個(gè)數(shù))。

步驟3 分別將Seql中的每個(gè)l-加權(quán)告警序列模式〈sl〉看作前綴，遞歸執(zhí)行以下步驟：

(i) 對(duì)于Seql中有相同前綴〈sl-1〉的序列模式〈sl〉，已得到〈sl-1〉-投影數(shù)據(jù)集中所有的非加權(quán)頻繁告警項(xiàng)z，根據(jù)剪枝策略，刪除所有以〈sl〉為前綴的后綴序列中的非加權(quán)頻繁告警項(xiàng)z，從而得到〈sl〉-投影數(shù)據(jù)集。

(ii) 搜索〈sl〉-投影數(shù)據(jù)集中所有的加權(quán)頻繁告警項(xiàng)；然后將每一個(gè)加權(quán)頻繁告警項(xiàng)附加到l-加權(quán)告警序列模式〈sl〉后，形成以〈sl〉為前綴的l+1-加權(quán)告警序列模式集Seql+1。

? 若〈sl〉-投影數(shù)據(jù)集為空，則遞歸結(jié)束； ? 若〈sl〉-投影數(shù)據(jù)集中所有告警項(xiàng)的加權(quán)支持度都小于ξ，則遞歸結(jié)束； ?l=l+1,并執(zhí)行步驟3。

由于該算法在挖掘加權(quán)告警序列模式過(guò)程中不會(huì)產(chǎn)生任何告警候選子序列，且基于剪枝的方法可以在挖掘過(guò)程中剔除權(quán)值較低告警，從而極大地縮減了投影數(shù)據(jù)集，減少了對(duì)非頻繁告警項(xiàng)的計(jì)算數(shù)量，因此，相對(duì)于傳統(tǒng)的序列模式挖掘算法，該算法可以顯著地提高挖掘過(guò)程中的執(zhí)行效率。雖然該算法需要花費(fèi)一定的時(shí)間和空間來(lái)計(jì)算和存儲(chǔ)告警序列的權(quán)值，但對(duì)于大量告警數(shù)據(jù)的挖掘和存儲(chǔ)來(lái)說(shuō)，這些都是可以忽略不計(jì)的量。另外，采用該算法挖掘告警數(shù)據(jù)集中的加權(quán)告警序列模式，不僅可以挖掘出更多的重要告警，而且可以過(guò)濾掉大量不重要告警，使所挖掘的告警時(shí)序關(guān)系更加有效和實(shí)用，對(duì)故障診斷和定位有很大的幫助。

4 實(shí)驗(yàn)結(jié)果與性能分析

為了驗(yàn)證將不同告警看作是不平等的更適用于移動(dòng)通信網(wǎng)絡(luò)的告警相關(guān)性分析，本部分采用大量實(shí)驗(yàn)，對(duì)新提出的加權(quán)告警分析方法和傳統(tǒng)將告警看作是平等的告警分析方法進(jìn)行告警時(shí)序關(guān)系挖掘性能比較。在傳統(tǒng)的基于數(shù)據(jù)挖掘的告警時(shí)序挖掘方法中，這里主要使用前綴投影序列模式挖掘(Prefix-Projected Sequential Pattern Mining, PrefixSpan)算法挖掘告警序列模式來(lái)表示告警之間的時(shí)序關(guān)系，因?yàn)樵撍惴ㄊ撬袀鹘y(tǒng)序列模式挖掘算法中性能最好的[16]，且文獻(xiàn)[11-12]均用該算法挖掘告警數(shù)據(jù)中的時(shí)序關(guān)系模式。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)主要使用中國(guó)移動(dòng)提供的真實(shí)數(shù)據(jù)集和IBM數(shù)據(jù)生成器生成的T40I10D100k數(shù)據(jù)集[17]來(lái)驗(yàn)證加權(quán)告警分析方法挖掘告警之間時(shí)序關(guān)系的有效性和高效性。

表4 移動(dòng)告警數(shù)據(jù)信息

由于通信網(wǎng)絡(luò)具有規(guī)模大、異構(gòu)、互連等特點(diǎn)，使得告警數(shù)據(jù)具有信息量大但不完全、冗余和相關(guān)等特點(diǎn)。因此，對(duì)于2018年7月內(nèi)一周的中國(guó)移動(dòng)真實(shí)告警數(shù)據(jù)，首先對(duì)其進(jìn)行數(shù)據(jù)清洗，數(shù)據(jù)信息如表4所示；并選擇告警標(biāo)題、網(wǎng)元名稱、告警發(fā)生時(shí)間、告警級(jí)別、對(duì)設(shè)備的影響、對(duì)業(yè)務(wù)的影響和告警清除時(shí)間7個(gè)屬性來(lái)描述一個(gè)告警實(shí)例。然后利用熵值法對(duì)不同的告警分配不同的權(quán)值。同時(shí)，由于大部分告警的時(shí)序關(guān)系在10 min內(nèi)發(fā)生，因此利用窗口寬度為600 s和滑動(dòng)步長(zhǎng)為480 s的滑動(dòng)窗口得到告警序列數(shù)據(jù)集；其次由于不同設(shè)備的告警延遲在2 min內(nèi)，則每個(gè)序列中的項(xiàng)集由窗口寬度為60 s和滑動(dòng)步長(zhǎng)為50 s的滑動(dòng)窗口得到。T40I10D100k數(shù)據(jù)集包含100 k條序列和942個(gè)項(xiàng)，每個(gè)序列的平均長(zhǎng)度為40，最大潛在序列模式長(zhǎng)度為10。由于該數(shù)據(jù)集中每個(gè)項(xiàng)都沒(méi)有權(quán)值，故將數(shù)據(jù)集中的每個(gè)項(xiàng)視為告警項(xiàng)，并為每個(gè)項(xiàng)隨機(jī)生成(0.0, 1.0]的權(quán)值。

4.2 實(shí)驗(yàn)評(píng)估

第一個(gè)實(shí)驗(yàn)主要在中國(guó)移動(dòng)數(shù)據(jù)集上評(píng)估新提出的加權(quán)告警序列模式挖掘算法挖掘加權(quán)告警序列模式和傳統(tǒng)序列模式挖掘算法挖掘告警序列模式在不同支持度閾值(加權(quán)支持度閾值或支持度閾值)下的性能，主要以告警模式數(shù)量(加權(quán)告警序列模式或告警序列模式，即時(shí)序關(guān)系)和重要告警覆蓋率為評(píng)判指標(biāo)。其中，告警模式數(shù)量不包含1-告警模式的數(shù)量；重要告警覆蓋率指包含重要告警的告警模式數(shù)除以總告警模式數(shù)的百分比。由于一級(jí)告警和二級(jí)告警共占總告警量不足1%，因此，統(tǒng)一將一級(jí)告警、二級(jí)告警和三級(jí)告警看作重要告警，四級(jí)告警看作不重要告警。

從圖1(a)中可以看出，新提出的算法和所對(duì)比的傳統(tǒng)算法挖掘的告警模式數(shù)量都會(huì)隨著支持閾值的增加而減少，但新提出的算法挖掘的告警模式數(shù)比傳統(tǒng)算法挖掘的告警模式數(shù)少。圖1(b)顯示，新提出的算法所得的重要告警覆蓋率總是大于傳統(tǒng)算法所得的重要告警覆蓋率。其原因是所對(duì)比的傳統(tǒng)算法將所有告警都看作平等的，因此，會(huì)挖掘出包含大量高頻卻不重要告警的告警模式；而利用新提出的算法挖掘加權(quán)告警序列模式能夠過(guò)濾掉許多包含不重要告警的告警模式，并挖掘出包含重要告警的告警模式。因此，新提出的算法挖掘的告警模式數(shù)比所對(duì)比的傳統(tǒng)算法挖掘的告警模式數(shù)少，且新提出的算法所得的告警模式的重要告警覆蓋率有顯著的優(yōu)勢(shì)。也就是說(shuō)，傳統(tǒng)的基于簡(jiǎn)單支持計(jì)數(shù)的序列模式挖掘所發(fā)現(xiàn)的告警序列模式中，那些權(quán)值較小的不重要的告警不會(huì)包含在加權(quán)告警序列模式中。由此可知，加權(quán)告警分析方法在通信網(wǎng)絡(luò)的告警時(shí)序關(guān)系分析中具有很大的優(yōu)越性。圖2為移動(dòng)數(shù)據(jù)集在不同支持閾值下加權(quán)告警序列模式的分布情況。

圖1 中國(guó)移動(dòng)告警數(shù)據(jù)集的分析結(jié)果

圖2 移動(dòng)數(shù)據(jù)集的k-加權(quán)告警序列模式分布

圖3 移動(dòng)數(shù)據(jù)集下支持度閾值與運(yùn)行時(shí)間關(guān)系

圖4 IBM生成數(shù)據(jù)集的分析結(jié)果

為了驗(yàn)證所提加權(quán)告警分析方法的適用性和有效性，在數(shù)據(jù)集T40I10D100k上進(jìn)行第二個(gè)實(shí)驗(yàn)。在本實(shí)驗(yàn)中，將支持閾值設(shè)置在0.02到0.08之間以找到足夠多的序列模式來(lái)驗(yàn)證算法性能，且將權(quán)值大于0.5的項(xiàng)視為是重要的告警項(xiàng)。如圖4所示，總體結(jié)果與第一個(gè)實(shí)驗(yàn)結(jié)果相似，與傳統(tǒng)告警分析方法相比，都呈現(xiàn)了較大的優(yōu)勢(shì)。通過(guò)上述分析，新提出的算法在搜索通信網(wǎng)絡(luò)中告警的時(shí)序關(guān)系時(shí)，比以往的基于數(shù)據(jù)挖掘的告警分析方法具有更好的性能。

為了驗(yàn)證新提出的算法挖掘告警之間時(shí)序關(guān)系的高效性，在移動(dòng)數(shù)據(jù)集上對(duì)新提出的算法和傳統(tǒng)算法挖掘告警模式的效率進(jìn)行了測(cè)試。圖3顯示了在移動(dòng)數(shù)據(jù)集的各支持度閾值下兩個(gè)方法挖掘告警模式的運(yùn)行時(shí)間。顯然，在不同支持度閾值的情況下，新提出的算法在效率上有很大的優(yōu)勢(shì)。其主要原因是新提出的算法運(yùn)用了文中所設(shè)計(jì)的剪枝策略，在挖掘過(guò)程中剔除了后綴序列數(shù)據(jù)集中的非頻繁告警項(xiàng)，大大縮減了投影數(shù)據(jù)集的規(guī)模，從而減少大量的非頻繁告警子序列的計(jì)算，提高了搜索告警時(shí)序關(guān)系的執(zhí)行效率。

綜上性能研究表明，加權(quán)告警序列模式挖掘算法在挖掘通信網(wǎng)絡(luò)中的告警時(shí)序關(guān)系時(shí)，具有很好的性能和效率。因此，文中提出的加權(quán)告警分析方法更適合于通信網(wǎng)絡(luò)告警。

5 總 結(jié)

根據(jù)移動(dòng)通信網(wǎng)絡(luò)告警數(shù)據(jù)的特征，考慮到網(wǎng)絡(luò)中不同告警對(duì)網(wǎng)絡(luò)的影響程度不同且告警的發(fā)生有一定的序列關(guān)系，提出了一種高效的加權(quán)告警分析方法。首先，采用熵值法為不同的告警分配不同的權(quán)值；然后提出了一種加權(quán)告警序列模式挖掘算法來(lái)搜索告警數(shù)據(jù)中的時(shí)序關(guān)系，并采用了一種新穎的剪枝策略來(lái)縮減需要搜索的數(shù)據(jù)集大小，以減少非頻繁告警子序列的計(jì)算數(shù)目。實(shí)驗(yàn)結(jié)果表明，該加權(quán)告警分析方法可以有效地減少告警模式的數(shù)量，并包含更多的重要告警，有利于網(wǎng)絡(luò)管理人員及時(shí)地進(jìn)行故障診斷和定位。此外，該加權(quán)告警分析方法在執(zhí)行效率方面有很大的優(yōu)勢(shì)。因此，文中提出的加權(quán)告警分析方法為告警相關(guān)分析提供了一種有效的方法。