基于壓縮矩陣的通信網告警關聯規則挖掘算法

摘要:提出了一種基于壓縮矩陣運算的電信告警關聯規則挖掘算法。它解決了apriori等算法需多次掃描數據庫的問題，通過掃描告警事務庫并進行壓縮變換得到壓縮告警關聯矩陣，對關聯矩陣進行運算得到告警間的關聯規則。仿真實驗證明，該算法與apriori等算法相比，時間效率有了明顯提高，同時有效節約了存儲空間。

關鍵詞:故障管理; 關聯規則; 數據挖掘

中圖分類號:TN915.07文獻標志碼:A

文章編號:1001－3695(2008)02－0342－03

故障診斷與定位是網絡管理的核心。當網絡發生故障時，要求及時找到網絡發生故障的位置和原因，以便快速排除故障，恢復網絡的功能。告警相關性分析是網絡故障診斷的重要手段之一，其作用在于消除告警冗余，進一步找到故障根源，以便進行故障快速定位和排除。告警相關性分析采用的方法很多，如人工智能#65380;數據挖掘#65380;專家系統等。其中，基于數據挖掘的告警相關性分析是目前研究的熱點。Apriori算法[1]是數據挖掘中發現頻繁項集之間關聯規則的經典算法。目前國內外對基于apriori及其改進算法的通信網告警關聯規則挖掘作了大量研究[2~4]，具有代表性的如芬蘭赫爾辛基大學的Heikki Mannila等人開發的TASA系統。但apriori等算法在對電信告警數據庫進行挖掘時，需要多次遍歷數據庫。由于電信告警數據庫是海量數據，采用該算法進行挖掘時效率比較低。本文在已有算法的基礎上，以算法的挖掘速度和存儲空間為著眼點，提出了一種基于矩陣運算挖掘告警關聯規則的算法。該算法只掃描一遍數據庫并采用壓縮存儲機制，既提高了算法的挖掘速度，又節約了存儲空間。

1相關問題描述

定義1告警。對某個時間點上發生的一個異常情況的描述稱為該時刻的一條告警。它可由三元組s=(t，s，m)表示，稱為告警三元組。其中:t(time)是告警時間;s(source)是告警源;m(message)代表告警消息。告警時間由告警發送者產生并記錄;告警源可以在不同層次上定位，可以是一個被管理網元或被管理對象;告警信息則包含有關告警的其他全部信息，如告警類型#65380;告警級別#65380;告警描述等。

定義2告警序列與告警窗口。對于給定的事件集合E，事件序列S=(s，Ts，Te)是指發生在時間區間[Ts，Te]上按照增序排列的告警。其中:Ts為序列起始時間;Te為序列終止時間。S的一個窗口定義為Sw=(w，ts，te)，ts>Ts，te>Te，{ws|ts

定義3告警事務與告警事務庫。將在同一告警時間窗口內并且順序相同的告警序列組織在一起就形成了一個告警事務，記為Aij(i=1，2，…，M; j=1，2，…，N)。時間窗口按步長r進行滑動，從而形成不同的告警事務。這些告警事務的集合就組成了告警事務庫，告警事務庫是關聯規則挖掘算法的直接操作對象。

2基于壓縮矩陣的告警關聯規則挖掘算法

本算法挖掘不同告警項目之間的關聯規則時分兩步:由告警事務庫生成壓縮告警關聯矩陣;針對該矩陣進行關聯規則挖掘。

2.1壓縮告警關聯矩陣生成算法

生成告警關聯矩陣的主要目的是將告警事務庫中的數據變換為算法所需的矩陣形式。假設事務庫包含事務的數目是m，告警項目集AI={ai1，ai2，…，ain}包含項目個數為N。在內存允許的情況下，掃描事務庫后可以直接將告警事務庫影射為事務矩陣A[M][N]。其中，矩陣中的元素Aij(i=1，2，…，M; j=1，2，…，N)表示第i個事務中第j個告警項目發生的頻度且Aij∈{0，1}。由于告警關聯規則挖掘算法是一種布爾關聯規則頻繁項集的挖掘算法，在每個事務中僅判斷每種告警是否發生。若發生用1表示;否則用0表示。電信告警事務庫是海量數據庫，通常少則幾十萬條，多則百萬條事務。受限于內存容量，建立的告警關聯矩陣可能無法全部載入內存中，需要劃分成若干子矩陣分階段放入內存執行挖掘算法，使算法時間效率受到影響。在矩陣A[M][N]中，Aij(i=1，2，…，M; j=1，2，…，N)至少使用一個字節保存，而Aij是一個布爾量，只有0和1兩種取值。因此可以將Aij所占空間壓縮至一個比特位。考慮到挖掘結果是告警項目集之間的相關性，這里采用縱向壓縮的方式，即將告警項目在連續八個事務中的狀態用一個無符號字符型變量表示。假設基于上述思想掃描事務庫后得到的壓縮關聯矩陣為C[P][Q]，則有Q=N，P=M/8(M mod 8=0)或P=M/8+1(M mod 8≠0)。壓縮關聯矩陣生成算法描述如下:

輸入:告警事務數據庫D，初始化為零的矩陣C[P][Q]。

輸出:壓縮告警關聯矩陣C[P][Q]。

符號定義:tid為告警事務序號(從1開始);

Ttid為序號為tid的告警事務;

s_mask為8位位掩碼變量，初始時s_mask=0x80;i=1， j=1; C[P][Q]={0}。

while(!endof(D))

{ for all itemsets aik∈Ttid do{

C[i-1][k-1]=C[i-1][k-1]|s_mask;

// ′|′為邏輯或運算符

}

s_mask=s_mask>>1; j++;

if(j>8) then {

j=1; i++; s_mask=0x80;}

tid++;掃描下一個事務;

}

輸出壓縮告警關聯矩陣C[P][Q]

2.2基于壓縮矩陣的關聯規則挖掘算法

2.2.1產生候選1項集和頻繁集

與apriori算法中候選項集的概念類似，第一次迭代時每一個告警項目都是候選1項集。考慮到告警項目集合的大小N通常遠小于事務庫的大小M，且一般情況下有0

2.2.2產生候選2項集和頻繁集

2.2.4產生告警關聯規則

由挖掘算法生成的頻繁項集通過置信度產生告警關聯規則[6]。X#65380;Y是兩個頻繁項集(非空)，且XY，給定最小置信度為MinConf。如果Sup(Y)/Sup(X)≥MinConf成立，則產生規則XY-X，即在告警項目集X發生的條件下，時間窗口內告警項目集Y-X以Sup(Y)/Sup(X)的概率出現。

3算法性能測試及討論

本文用VC++ 6.0，在內存為512 MB，CPU為賽揚D 2.26 GHz，操作系統為Windows XP的計算機上實現了apriori算法和本文算法(CMatrix)。實驗中分別采用500~8 000條告警信息經過預處理后構成的告警事務數據庫來測試算法的性能。兩種算法運行時的參數均設定為:滑動窗口為6 min，窗口的滑動步長為2 min，最小支持度為2%，最小置信度為80%。兩種算法的性能曲線如圖1所示。

從圖1中可以看出，本文算法比apriori算法的執行效率高

很多。由于挖掘算法的大部分時間消耗在數據庫掃描上，apriori算法中對每一個候選項都要掃描一次數據庫，時間開銷大;本算法只需掃描數據庫一次，將得到的壓縮矩陣裝入內存中，大部分運算都在內存中進行，使I/O時間降為最低，并通過保存中間運算結果以及運用布爾運算的性質，有效提高了算法的時間效率，同時采用壓縮技術有效節約了存儲空間。

4結束語

本文針對電信網告警信息量大#65380;告警具有突發性等特點，提出了一種高效的基于壓縮矩陣運算挖掘關聯規則的算法。其核心思想是將對告警數據庫的挖掘轉換為對壓縮告警關聯矩陣的挖掘。實驗表明，本文算法的挖掘效率與apriori算法相比有很大的提高，對電信網海量告警相關性分析，快速#65380;準確地定位告警故障根源有重要的意義。

參考文獻:

[1]AGRAWAL R， SRIKANT R. Fast algorithm for mining association rules[R]. San Jose: IBM Almaden Research Center， 1994.

[2]吳揚揚，陳懷南.基于關聯規則的通信網絡告警相關性分析模型[J].通訊和計算機，2004，1(1):57－63.

[3]HATONEN K， KLEMETTINEN M， MANNILA H， et al.TASA:tele－communication alarm sequence analyzer or how to enjoy faults in your network[C]//Proc of IEEE Network Operations and Management Symposium. Kyoto:[s.n.]， 1996:520－529.

[4]劉康平，李增智.網絡告警序列中的頻繁情景規則挖掘算法[J].小型微型計算機系統，2003，24(5):891－894.

[5]毛廣莉，黃梓龍.電信網告警數據庫中的數據挖掘[J].計算機應用研究，2000，17(8):98－99.

[6]HAN Jia－wei， KAMBER M.數據挖掘概念與技術[M].范明，孟小峰，等譯.北京:機械工業出版社，2005:272－278.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”