基于關聯規則挖掘算法的規則發現系統的設計和實現

逯曉鵬，楊芳南

（北京交通大學網絡管理研究中心，北京100044）

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

1 關聯規則挖掘算法

1.1 經典Apriori算法

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

1.2 算法挖掘質量改進

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

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

經過對相關改進方法的深入研究，關聯規則挖掘算法在提高挖掘質量上具有可行性。因此，可將其應用到綜合網絡管理系統的規則發現系統中。

2 算法在綜合網絡管理中的應用

為了將對經加權[5]和序列模式處理的告警數據進行關聯規則的挖掘算法應用到綜合網絡管理系統中，我們需要分析綜合網絡管理中的告警數據及其屬性，從而進行相應的設計。

2.1 權值的設計

在綜合網絡管理系統中，對告警數據進行加權處理。首先考慮影響權值的因素，它們是告警級別和告警網元的拓撲關聯度數。對于告警級別，一般的綜合網絡管理系統數據庫當中都存放著一張告警級別表，這樣可以直接獲得級別信息。告警網元之間的連接線一般為復用段、再生段或邏輯連接線，因此可以通過分析數據庫中相應的連接線表得到網元的拓撲結構，計算不同網元對應的拓撲關聯度數。

綜合網絡管理系統的局部網元拓撲結構如圖1。

圖1 網元拓撲圖

其中，每個網元的拓撲度數即為與該網元連接的復用段的條數。

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

根據上面得到的告警屬性值，建立層次結構模型，就可以得到相應的權值。

2.2 序列模式分析設計

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

圖2 告警時序圖

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

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

可以看到，加權[6]和序列模式都是在規則挖掘算法執行之前對告警數據的處理。因此挖掘質量的好壞，關鍵在于對挖掘數據的處理情況。

2.3 綜合網管中的關聯規則算法

結合前面介紹的關聯規則挖掘算法[7]和本節當中的算法改進設計，給出在綜合網絡管理中應用的關聯規則算法模型。本文中，綜合網絡管理系統使用的關聯規則算法的挖掘對象是告警數據，用于挖掘告警數據中的關聯規則。

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

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

挖掘綜合網絡管理中告警數據關聯規則的算法步驟如下：

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

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

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

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

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

（6）將滿足要求的告警關聯規則放入待處理的規則庫，算法執行完畢。

圖3 綜合網管系統中關聯規則挖掘算法流程圖

算法的流程如圖3。

上述給出了經過加權和時間約束處理的關聯規則算法，應用于挖掘綜合網絡管理系統的告警數據的關聯規則[8]。算法模型的建立使規則發現系統的實現成為可能。

3 系統設計

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

3.1 系統框架設計

圖4是規則發現系統的框架圖。

圖4 規則發現系統框架圖

其中，規則發現系統作為一個獨立的功能進行開發，但實際上在綜合網絡管理系統中，規則發現功能模塊和基于規則引擎的告警相關性分析模塊集成作為整個系統的告警相關性分析系統。前者為后者提供告警規則，后者利用告警規則進行告警相關性分析。

3.2 系統流程圖設計

系統執行流程如圖5。

圖5 規則發現系統流程圖

4 系統實現

4.1 頻繁集發現分析

本文以傳輸網網管系統5個月的157 610條告警數據進行規則挖掘。

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

圖6 加權和沒有加權情況下頻繁集數的對照圖

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

4.2 挖掘規則結果分析

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

挖掘規則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(信號丟失)}：對應的置信度為0.97。

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

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

以上規則是做加權處理的挖掘算法的挖掘結果，因此也顯示了挖掘結果的可行性和有效性。

4.3 系統應用

本系統已經成功地應用到朔黃鐵路綜合網絡管理系統中，實現了規則的自學習，提供了規則來源，完善了綜合網絡管理系統中告警相關性分析系統。

5 結束語

本文針對綜合網絡管理系統中對規則獲取的需求，設計和實現了規則發現系統，并將其成功地應用到朔黃鐵路通信網綜合維護管理系統中，解決了規則獲取和來源的問題。通過挖掘獲取的規則，實現了適應電信網絡動態變化的需求。

[1] 郭軍. 網絡管理[M] . 北京：北京郵電大學出版社，2006，4.

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

[3] 崔立新.約束性關聯規則發現方法及算法[J] .計算機學報，2000，23（2）：216-220.

[4] 肖海林，李興明. 層次分析法在通信網告警相關性分析中的應用研究[J] . 電信科學，2006（11）.

[5] 李彤巖，肖海林，李興明. 通信網告警加權關聯規則挖掘算法的研究[J] . 電子科技大學學報，2008（6）.

[7] Cai C H，Fu 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.