基于關(guān)聯(lián)規(guī)則挖掘算法的規(guī)則發(fā)現(xiàn)系統(tǒng)的設(shè)計和實現(xiàn)

逯曉鵬，楊芳南

（北京交通大學(xué)網(wǎng)絡(luò)管理研究中心，北京100044）

電信網(wǎng)多網(wǎng)的融合，促進了綜合網(wǎng)絡(luò)管理系統(tǒng)的發(fā)展。綜合網(wǎng)絡(luò)管理系統(tǒng)實現(xiàn)了對傳輸網(wǎng)、交換網(wǎng)和數(shù)字調(diào)度網(wǎng)等專網(wǎng)的統(tǒng)一監(jiān)控和管理。因此告警類型多、數(shù)量龐大是綜合網(wǎng)絡(luò)管理[1]系統(tǒng)的告警特點。有效地進行系統(tǒng)的告警故障管理，就需要對告警進行相關(guān)性分析。告警相關(guān)性分析中規(guī)則是其不可缺少的必要條件。目前，市場上提供了很多告警相關(guān)性分析的產(chǎn)品，許多都是利用以往總結(jié)的規(guī)則進行相關(guān)性處理。因此，規(guī)則的獲取成為目前市場上告警相關(guān)性分析亟待解決的一個問題。規(guī)則的獲取一般有兩種方式：通過網(wǎng)管方面專家的經(jīng)驗總結(jié)獲取規(guī)則；通過對告警數(shù)據(jù)的挖掘獲取它們之間的關(guān)聯(lián)關(guān)系，即挖掘規(guī)則信息。但是針對電信網(wǎng)絡(luò)不斷變化的需求，第1種方案很難適應(yīng)這種需求。因此需要更為精確的手段來獲取規(guī)則。關(guān)聯(lián)規(guī)則挖掘算法提供了一種好的手段來實現(xiàn)對告警數(shù)據(jù)的規(guī)則挖掘。

1 關(guān)聯(lián)規(guī)則挖掘算法

1.1 經(jīng)典Apriori算法

算法的核心思想：（1）通過掃描數(shù)據(jù)集，產(chǎn)生一個大的候選數(shù)據(jù)項集，計算每個候選數(shù)據(jù)項發(fā)生的次數(shù)。（2）基于預(yù)先給定的最小支持度生成一維大數(shù)據(jù)項集L1，基于L1和數(shù)據(jù)集中的數(shù)據(jù)，產(chǎn)生二維大數(shù)據(jù)項集L2。（3）用同樣的方法，直到生成N維大數(shù)據(jù)項集Ln，其中已不再可能生成滿足最小支持度的N+I維大數(shù)據(jù)項集。（4）從得到的大數(shù)據(jù)項集中導(dǎo)出滿足最小置信度的規(guī)則。

1.2 算法挖掘質(zhì)量改進

在經(jīng)典的Apriori算法基礎(chǔ)上，為了保證算法應(yīng)用的有效性和挖掘質(zhì)量的高效性，引入加權(quán)和序列模式的思想。其中，序列模式[2]是從時間上約束[3]關(guān)聯(lián)規(guī)則挖掘算法，增強告警數(shù)據(jù)的統(tǒng)計特性。在算法的應(yīng)用上，我們根據(jù)時間跨度將告警數(shù)據(jù)劃分為不同的時間序列，即事務(wù)，這樣也方便了每種項目集的支持度的計算。關(guān)聯(lián)規(guī)則算法挖掘告警數(shù)據(jù)的結(jié)果就是從數(shù)據(jù)當中挖掘出數(shù)據(jù)之間存在的統(tǒng)計規(guī)律即關(guān)聯(lián)關(guān)系，如果告警數(shù)據(jù)不存在統(tǒng)計規(guī)律也就不存在規(guī)則而言，我們不會挖一些隨機性的規(guī)則，那是毫無意義的。因為統(tǒng)計分析是在一定范圍內(nèi)分析數(shù)據(jù)信息之間存在的規(guī)律。序列模式的時間跨度約束了挖掘算法的分析范圍。

對告警信息進行加權(quán)是因為一般情況對于告警數(shù)據(jù)進行規(guī)則挖掘時，每條告警都是平等對待。但是實際情況下告警之間存在著輕重之分，從告警數(shù)據(jù)的直觀屬性（如：告警級別），可以分出輕重。嚴重告警往往是一些提示告警的根源告警。既然是尋找告警之間的關(guān)聯(lián)關(guān)系，因此告警網(wǎng)元之間的拓撲關(guān)聯(lián)關(guān)系更能體現(xiàn)它們之間這種告警關(guān)聯(lián)程度。因此分析網(wǎng)元在整個網(wǎng)絡(luò)的拓撲結(jié)構(gòu)對于區(qū)分告警之間輕重關(guān)聯(lián)關(guān)系是十分重要的。本文將利用相關(guān)研究中提到的層次分析法[4]來確定不同告警項目集的權(quán)值。層次分析法可以將定性問題定量化，因此它是一種較科學(xué)的確定告警權(quán)重的方法。

經(jīng)過對相關(guān)改進方法的深入研究，關(guān)聯(lián)規(guī)則挖掘算法在提高挖掘質(zhì)量上具有可行性。因此，可將其應(yīng)用到綜合網(wǎng)絡(luò)管理系統(tǒng)的規(guī)則發(fā)現(xiàn)系統(tǒng)中。

2 算法在綜合網(wǎng)絡(luò)管理中的應(yīng)用

為了將對經(jīng)加權(quán)[5]和序列模式處理的告警數(shù)據(jù)進行關(guān)聯(lián)規(guī)則的挖掘算法應(yīng)用到綜合網(wǎng)絡(luò)管理系統(tǒng)中，我們需要分析綜合網(wǎng)絡(luò)管理中的告警數(shù)據(jù)及其屬性，從而進行相應(yīng)的設(shè)計。

2.1 權(quán)值的設(shè)計

在綜合網(wǎng)絡(luò)管理系統(tǒng)中，對告警數(shù)據(jù)進行加權(quán)處理。首先考慮影響權(quán)值的因素，它們是告警級別和告警網(wǎng)元的拓撲關(guān)聯(lián)度數(shù)。對于告警級別，一般的綜合網(wǎng)絡(luò)管理系統(tǒng)數(shù)據(jù)庫當中都存放著一張告警級別表，這樣可以直接獲得級別信息。告警網(wǎng)元之間的連接線一般為復(fù)用段、再生段或邏輯連接線，因此可以通過分析數(shù)據(jù)庫中相應(yīng)的連接線表得到網(wǎng)元的拓撲結(jié)構(gòu)，計算不同網(wǎng)元對應(yīng)的拓撲關(guān)聯(lián)度數(shù)。

綜合網(wǎng)絡(luò)管理系統(tǒng)的局部網(wǎng)元拓撲結(jié)構(gòu)如圖1。

圖1 網(wǎng)元拓撲圖

其中，每個網(wǎng)元的拓撲度數(shù)即為與該網(wǎng)元連接的復(fù)用段的條數(shù)。

圖1給出綜合網(wǎng)絡(luò)管理系統(tǒng)中部分網(wǎng)絡(luò)資源的拓撲圖，每個網(wǎng)元之間的連接線數(shù)表明了它在整個網(wǎng)絡(luò)中的關(guān)聯(lián)強度。它們之間的關(guān)聯(lián)性描述為：某一傳輸網(wǎng)網(wǎng)元產(chǎn)生告警，在專網(wǎng)上會引發(fā)另一個與其關(guān)聯(lián)度強的傳輸網(wǎng)網(wǎng)元產(chǎn)生告警；在綜合網(wǎng)上會引發(fā)接入網(wǎng)的CT端或RT端產(chǎn)生告警。這就進一步說明了在綜合網(wǎng)絡(luò)管理系統(tǒng)中確定網(wǎng)元的拓撲關(guān)聯(lián)度，對于根告警的確定十分重要的。

根據(jù)上面得到的告警屬性值，建立層次結(jié)構(gòu)模型，就可以得到相應(yīng)的權(quán)值。

2.2 序列模式分析設(shè)計

對于序列模式，可以根據(jù)告警的發(fā)生時間對挖掘數(shù)據(jù)進行時間跨度的劃分，將它們分成等時間跨度的告警事務(wù)集，然后根據(jù)挖掘頻繁項目集算法挖掘滿足支持度的頻繁集。

圖2 告警時序圖

如圖2，在時間軸上，有著大量的告警產(chǎn)生。分析發(fā)生的告警，告警事件C總在告警事件A與B發(fā)生后的△t時間間隔內(nèi)發(fā)生，因此我們會考慮分析告警事件A，B和C之間可能存在明顯的關(guān)聯(lián)關(guān)系，即{A，B}→{C}。對于事件E，如果按照時間的先后順序，它也是發(fā)生在告警事件的A和B之后，但是沒有一個時間范圍來約定在多長的時間段內(nèi)它將會發(fā)生。因此對于告警事件A與B來說，告警事件E相對于他們的發(fā)生是隨機的，既然是隨機的也就不存在任何的關(guān)聯(lián)關(guān)系。如果不給予時間的約束，可能會同樣推出這樣的規(guī)則關(guān)系， 即{A，B}→{E}，但是實際上他們之間不存在這樣的關(guān)聯(lián)關(guān)系，從而影響挖掘結(jié)果的準確性。可見將序列模式應(yīng)用到告警相關(guān)性分析的規(guī)則挖掘中至關(guān)重要。

討論了序列模式引入的必要性，接下來應(yīng)該根據(jù)具體需求設(shè)計序列模式的時間跨度，本文所述系統(tǒng)設(shè)計中，將其作為參數(shù)，客戶可以根據(jù)需求設(shè)定不同的時間跨度，確定符合自身工程需求的時間跨度。

可以看到，加權(quán)[6]和序列模式都是在規(guī)則挖掘算法執(zhí)行之前對告警數(shù)據(jù)的處理。因此挖掘質(zhì)量的好壞，關(guān)鍵在于對挖掘數(shù)據(jù)的處理情況。

2.3 綜合網(wǎng)管中的關(guān)聯(lián)規(guī)則算法

結(jié)合前面介紹的關(guān)聯(lián)規(guī)則挖掘算法[7]和本節(jié)當中的算法改進設(shè)計，給出在綜合網(wǎng)絡(luò)管理中應(yīng)用的關(guān)聯(lián)規(guī)則算法模型。本文中，綜合網(wǎng)絡(luò)管理系統(tǒng)使用的關(guān)聯(lián)規(guī)則算法的挖掘?qū)ο笫歉婢瘮?shù)據(jù)，用于挖掘告警數(shù)據(jù)中的關(guān)聯(lián)規(guī)則。

下面用到的告警分類集是根據(jù)告警的屬性，即告警級別，告警類型，告警對象類型，告警所屬網(wǎng)元和告警原因，為比較對象劃分的告警類集合。

設(shè)告警分類集為I={i1,i2,…,im}；告警分類集中每種告警對應(yīng)的權(quán)值為W={w1,w2,…,wm}；用時間跨度將告警數(shù)據(jù)按時間順序劃分形成的對象告警集為t；Lk項告警頻繁項目集即Lk中每個元素是由I中k個不同的告警組成，且Lk的每個元素{ij1,ij2,…,ijk（}1≤ijk≤m），滿足最小支持度；Lk中的每個元素{ij1,ij2,…,ijk}存在的告警規(guī)則形如{ij1,ij2}→{ij3，…,ijk}，且前后兩個子集滿足條件：{ij1,ij2}∩{ij3,…,ijk}=Φ和{ij1,ij2}∪{ij3，…,ijk}={ij1,ij2,…,ijk}

挖掘綜合網(wǎng)絡(luò)管理中告警數(shù)據(jù)關(guān)聯(lián)規(guī)則的算法步驟如下：

（1）按時間跨度將預(yù)處理后的告警數(shù)據(jù)按時間順序劃分為多個告警集t，去除每個告警集t中的重復(fù)告警類。

（2）在劃分的所有的告警集t中，尋找1項告警頻繁項目集L1。

（3）以（k-1）項告警頻繁項目集Lk-1為基礎(chǔ)，在劃分的所有告警集t中，尋找第k項告警頻繁項目集Lk（k≥2），直到得到的Lk為空集為止。

（4）獲取告警頻繁項目集的集合L，L=L1∪L2∪…∪Ln（1＜n＜m）。

（5）取告警頻繁項目集集合L中的元素Lk，尋找并計算Lk每個元素中存在的滿足最小置信度的告警關(guān)聯(lián)規(guī)則，直到L中的所有告警頻繁項目集元素都處理完畢為止。

（6）將滿足要求的告警關(guān)聯(lián)規(guī)則放入待處理的規(guī)則庫，算法執(zhí)行完畢。

圖3 綜合網(wǎng)管系統(tǒng)中關(guān)聯(lián)規(guī)則挖掘算法流程圖

算法的流程如圖3。

上述給出了經(jīng)過加權(quán)和時間約束處理的關(guān)聯(lián)規(guī)則算法，應(yīng)用于挖掘綜合網(wǎng)絡(luò)管理系統(tǒng)的告警數(shù)據(jù)的關(guān)聯(lián)規(guī)則[8]。算法模型的建立使規(guī)則發(fā)現(xiàn)系統(tǒng)的實現(xiàn)成為可能。

3 系統(tǒng)設(shè)計

規(guī)則發(fā)現(xiàn)系統(tǒng)的執(zhí)行過程大體上分為3個階段：挖掘數(shù)據(jù)的預(yù)處理階段，規(guī)則的挖掘階段和挖掘規(guī)則的后處理階段。3個階段的功能各不相同，對于第1階段實現(xiàn)對挖掘數(shù)據(jù)的預(yù)處理：去噪音，去重復(fù)記錄，告警數(shù)據(jù)降維，賦權(quán)值和數(shù)據(jù)分類操作。這一階段是保證挖掘質(zhì)量重要環(huán)節(jié)。算法中引入的加權(quán)和序列模式也在這一階段完成。第2階段就是Apriori算法的執(zhí)行階段。第3階段是對挖掘規(guī)則的后處理階段，由于挖掘出來的規(guī)則很粗糙，并且有些是冗余的，因此需要對規(guī)則進行刪減和編輯，使其符合告警相關(guān)性分析的格式需求。

3.1 系統(tǒng)框架設(shè)計

圖4是規(guī)則發(fā)現(xiàn)系統(tǒng)的框架圖。

圖4 規(guī)則發(fā)現(xiàn)系統(tǒng)框架圖

其中，規(guī)則發(fā)現(xiàn)系統(tǒng)作為一個獨立的功能進行開發(fā)，但實際上在綜合網(wǎng)絡(luò)管理系統(tǒng)中，規(guī)則發(fā)現(xiàn)功能模塊和基于規(guī)則引擎的告警相關(guān)性分析模塊集成作為整個系統(tǒng)的告警相關(guān)性分析系統(tǒng)。前者為后者提供告警規(guī)則，后者利用告警規(guī)則進行告警相關(guān)性分析。

3.2 系統(tǒng)流程圖設(shè)計

系統(tǒng)執(zhí)行流程如圖5。

圖5 規(guī)則發(fā)現(xiàn)系統(tǒng)流程圖

4 系統(tǒng)實現(xiàn)

4.1 頻繁集發(fā)現(xiàn)分析

本文以傳輸網(wǎng)網(wǎng)管系統(tǒng)5個月的157 610條告警數(shù)據(jù)進行規(guī)則挖掘。

圖6給出算法在經(jīng)過加權(quán)處理和沒加權(quán)處理情況下，不同最小支持度下得到的告警頻繁項目集數(shù)坐標對照圖。

圖6 加權(quán)和沒有加權(quán)情況下頻繁集數(shù)的對照圖

可以看到，經(jīng)過加權(quán)處理的挖掘算法的曲線頻繁項目集數(shù)隨著最小支持度的增加，變化得比較緩慢，這是因為權(quán)值呈現(xiàn)了不同告警的輕重，從而不會輕易丟掉存在關(guān)聯(lián)的頻繁項目集，并且在0.1的支持度附近變化率最小。

4.2 挖掘規(guī)則結(jié)果分析

選定的規(guī)則挖掘結(jié)果的時間跨度為10 min，支持度和置信度分別為：0.1和0.95。挖掘規(guī)則中的兩條規(guī)則如下：

挖掘規(guī)則1：{ALAR_OBJECT_TYPE=19(端口)，ALAR_TYPE=1(通信告警)，ALAR_LEVEL=2(主要告警)，ALAR_ST_ID=94(光道波長丟失)}?{{ALAR_OBJECT_TYPE=19(端口)，ALAR_TYPE=1(通信告警)，ALAR_LEVEL=2(主要告警)，ALAR_ST_ID=1(信號丟失)}：對應(yīng)的置信度為0.97。

挖掘規(guī)則2：{ALAR_OBJECT_TYPE=19(端口)，ALAR_TYPE=1(通信告警)，ALAR_LEVEL=2(主要告警)，ALAR_ST_ID=50(告警指示) →電路信號故障}：對應(yīng)的置信度為1。

需要說明的是本文的規(guī)則發(fā)現(xiàn)系統(tǒng)發(fā)現(xiàn)的規(guī)則一般為上述兩種類型：根告警規(guī)則和告警關(guān)聯(lián)故障規(guī)則。對于規(guī)則1而言，當端口發(fā)生光道波長丟失的告警時，會引發(fā)端口信號丟失的告警。光波是信號的載體，光波的丟失必然會導(dǎo)致信號的丟失，因此他們之間存在一定的關(guān)聯(lián)性。與此同時需要對挖掘的這種規(guī)則做執(zhí)行議程的設(shè)計即當檢測到實時告警滿足條件時，將后上報的引發(fā)告警進行根告警定位，過濾掉引發(fā)告警。對于規(guī)則2，它是對告警數(shù)據(jù)挖掘后發(fā)覺的高頻告警，高頻告警的產(chǎn)生，需要分析告警產(chǎn)生的原因，一般是故障直接導(dǎo)致，因此可以將該類告警直接轉(zhuǎn)為故障操作。不管是規(guī)則1還是規(guī)則2，這些規(guī)則信息都是告警數(shù)據(jù)的統(tǒng)計結(jié)果，并且規(guī)則信息也很粗糙，需要人為的對挖掘規(guī)則進行編輯和修改，使其符合相關(guān)性系統(tǒng)的需要。

以上規(guī)則是做加權(quán)處理的挖掘算法的挖掘結(jié)果，因此也顯示了挖掘結(jié)果的可行性和有效性。

4.3 系統(tǒng)應(yīng)用

本系統(tǒng)已經(jīng)成功地應(yīng)用到朔黃鐵路綜合網(wǎng)絡(luò)管理系統(tǒng)中，實現(xiàn)了規(guī)則的自學(xué)習(xí)，提供了規(guī)則來源，完善了綜合網(wǎng)絡(luò)管理系統(tǒng)中告警相關(guān)性分析系統(tǒng)。

5 結(jié)束語

本文針對綜合網(wǎng)絡(luò)管理系統(tǒng)中對規(guī)則獲取的需求，設(shè)計和實現(xiàn)了規(guī)則發(fā)現(xiàn)系統(tǒng)，并將其成功地應(yīng)用到朔黃鐵路通信網(wǎng)綜合維護管理系統(tǒng)中，解決了規(guī)則獲取和來源的問題。通過挖掘獲取的規(guī)則，實現(xiàn)了適應(yīng)電信網(wǎng)絡(luò)動態(tài)變化的需求。

[1] 郭軍. 網(wǎng)絡(luò)管理[M] . 北京：北京郵電大學(xué)出版社，2006，4.

[2] 姚偉力，王錫祿，宋俊德. 基于序列模式挖掘的告警相關(guān)性分析算法[J] . 北京郵電大學(xué)學(xué)報， 200（510）.

[3] 崔立新.約束性關(guān)聯(lián)規(guī)則發(fā)現(xiàn)方法及算法[J] .計算機學(xué)報，2000，23（2）：216-220.

[4] 肖海林，李興明. 層次分析法在通信網(wǎng)告警相關(guān)性分析中的應(yīng)用研究[J] . 電信科學(xué)，2006（11）.

[5] 李彤巖，肖海林，李興明. 通信網(wǎng)告警加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的研究[J] . 電子科技大學(xué)學(xué)報，2008（6）.

[7] Cai C H，F(xiàn)u W C，Cheng C H. Mining association rules with weighted items[D] . Hong Kong: The Chinese University of Hong Kong，2004.

[8] Malheiros M D.A model for alarm correlation in telecommunication networks[D] .Belo Horizonte: Feberal University of Miuas Gerais, 1997.