一種關聯規則增量式挖掘算法研究

劉造新

摘要： 現有關聯規則更新算法都是基于支持度-置信度框架而提出的，僅針對大于最小支持度閉值的頻繁項集進行挖掘。為了提高告警關聯規則的完整性和準確性，在相關度AARSC算法基礎上，提出了一種增量式挖掘UAARSC算法(Updating-AARSC)。該算法對增量計算進行了改進，可以發現頻繁和非頻繁告警序列間的關聯規則。

關鍵詞： 關聯規則； 數據發掘； 滑動窗口； 增量計算

中圖分類號：TP3文獻標志碼：A文章編號：1006-8228（2012）03-20-02

An algorithm of associative rule increment mining

Liu Zaoxin

（Department of Information Engineering, Jiangxi Professional training College of transportation, Nanchang， Jiangxi 330013， China）

Abstract： The existing algorithms of association rule update are based on the framework of support-confidence and they mine only the frequent closure of the set value greater than the minimum support. To enhance the completeness and accuracy, the author presents in this paper an increment mining UAARSC algorithm based on the correlative AARSC algorithm. The algorithm improves incremental computation and may find the associative rules between the frequent and non-frequent alarm sequences.

Key words： associative rules； data mining； sliding window； incremental computation

0 引言

數據挖掘是從大量、不完整、有噪聲的隨機數據中，提取隱含在其中、人們不知道但又潛在有用的信息和知識的過程。Agrawal等人提出了挖掘關聯規則的一個重要方法—Apriori算法[1]。為了挖掘具有時序特征的告警關聯規則問題，Hatonen等在Apriori算法基礎上提出了基于滑動窗口的WINEPI算法[2]，并在TASA(Telecommunications Alarm Sequence Analyzer)系統中采用了該算法[3]。這些算法的處理過程一般分為兩個階段：⑴利用支持度發現頻繁告警序列；⑵利用置信度產生關聯規則。為了提高算法的效率、減少數據庫訪問次數，避免在第一階段中生成大量候選項目集，Han等人提出了基于FP樹生成頻繁項目集的FP-Growth算法，該算法將頻繁項集壓縮保存在一棵FP-tree中，在一定程度上提高了頻繁項集的存取速度，從而提高了挖掘頻繁項目集的效率。

以上算法都是在高支持度，高置信度的條件下，挖掘出告警關聯規則。但在挖掘電信網絡告警關聯規則時，以高支持度和高置信度為條件的算法具有一定局限性。如在分析某省電信網管告警數據庫連續6萬條告警記錄時發現，該數據庫中共有1738個網元上報告警：其中1個網元上報8521次告警，1個網元上報4729次告警，14個網元上報告警次數在1000～2000之間，12個網元上報告警次數在500～1000之間，而上報告警次數小于100次的網元有1669個，若在上述告警數據庫中采用Apriori、WINEPI或FP-Growth算法產生關聯規則，即使支持度設定為1%也只能發現28個網元之間的告警關聯關系，甚至設定為0.1%（己經很低了）仍然無法發現告警次數小于100的1669個網元之間的關聯關系。而這些非頻繁的告警序列之間也會存在一些關聯規則，這些告警間關聯規則在實際工作中對網管人員解決故障有很大的幫助。因此，挖掘在高置信度和低支持度（或者不考慮支持度）條件下的告警關聯規則具有重要的實際意義。

在實際網絡中非頻繁告警的種類是巨大的，而且具有很強的隨機性，挖掘這些告警間的關聯規則，對于網絡管理具有很大的實際意義。本文在分析以高相關度、高置信度為條件，在基于相關度統計的告警關聯規則挖掘AARSC算法(Alarm Association Rules Algorithm Based on Statistical Correlation)的基礎上，為了適應告警數據動態增加的特點，提出了一種增量式挖掘UAARSC算法(Updating-AARSC)。UAARSC算法可以發現頻繁和非頻繁告警序列間的關聯規則，從而提高了告警關聯規則的完整性和準確性。

1 關聯規則的增量式更新算法

目前關聯規則的更新算法，如FUP算法[4]、FUP2算法[5]和IUA算法[6]都是基于支持度-置信度框架下提出的，僅針對大于最小支持度閉值的頻繁項集進行挖掘。我們這里在基于相關度AARSC算法基礎上，提出一種在數據庫增加時的增量式挖掘UAARSC(Updating-AARSC)算法。

1.1 算法框架

設數據庫為D，新增數據庫為d。由于計算cov(X,Y)和δx在AARSC算法中耗時較多，因此在增量式挖掘算法中針對這兩部分進行改進。下面分別介紹增量計算cov(X,Y)和δx的方法。

算法中的符號說明。如表1所示。

表1算法中符號說明

[[&數據庫D&數據庫d&數據庫D∪d&窗口數&n1&n2&n1∪n2&均值&μi0&μi1&μi&]]

我們以△μi0表示告警次在D∪d與D中的均值差，即△μi0=μi－μi0；△μi1表示告警次在D∪d與d中的均值差，即△μi1＝μi一μi1。

⑴ 增量計算cov(X,Y)

這部分耗時最大，在D∪d數據庫中的相關系數為

cov(X,Y)=

=+

=

⑵ 增量計算δx

δx=

=

因此在數據庫D∪d中計算結果為分別在D和d上計算cov(X,Y)和δx的結果。再加上一個常數。通常來講，n1>>n2，因此每次都只需要計算很少的數據量。

1.2 算法描述

增量挖掘UAARSC算法的基本描述如下。

輸入：⑴ 告警數據庫D； ⑵ 告警增量數據庫d；⑶ 最小相關度minCor； ⑷ 最小置信度minConf；⑸ 滑動窗口win和滑動步長steP。

輸出：S中滿足minCor和minConf的關聯規則。

方法：

⑴ [cov2L，aver]=computeCorr(D，minCor，win，steP)

⑵ cov2LOld=cov2L，averOld=aver;

⑶ [cov2L，aver]=computerCorr(d,minCor，win，steP)

⑷ average=mean(D∪d，averOld，aver)，

⑸ averl＝average－ave， aver2＝average－averOld

⑹ 將兩次挖掘結果，根據均值，調整、組合

⑺ 根據minCor和minConf，挖掘二項關聯規則

⑻ 生成多項集

2 實驗及其分析

實驗采用的測試數據是某省電信公司連續二周的告警數據(15萬條記錄)。實驗中將告警類型標識和告警發生時間（單位/秒）作為關鍵字進行挖掘。告警時間窗設為5min，滑動步長設為2min；最小支持度1%，最小相關度0.5。

實驗1：告警記錄分別設為3、6、9、12、15萬條記錄；采用WINEPI算法、AARSC算法及其更新UAARSC算法(等量增加)分別進行挖掘。在執行效率方面，比較的結果如圖1所示。

圖1執行時間比較

相關矩陣AARSC算法比WINEPI的執行速度要快，主要是因為WINEPI算法產生頻繁候選集時，長度每增加一個，都要掃描一次數據庫，所以時間開銷很大；基于相關矩陣AARSC算法只需掃描一次數據庫，然后進行矩陣運算即可，因此執行時間比WINEPI少；從圖1可以看出，由于UAARSC算法利用前次的挖掘結果，僅需要計算增量部分的告警數據，因此執行效率最高。

實驗2：用五種不同的增量交易數據庫，以5萬條記錄為基準，分別增加4、3、2、1萬條記錄，比較更新算法在執行效率方面的優勢。結果如圖2所示。

圖2增量數據執行時間比較

數據庫記錄增加時，增量式挖掘算法在系統執行時間上有較大改進。主要是因為隨著數據庫記錄的增加，WINEPI和相關矩陣算法都要重新挖掘數據庫，而增量式挖掘算法只對新增數據進行挖掘，因此算法的效率有顯著提高。如圖2中告警記錄為15萬，新增1萬條告警記錄時，更新算法只需挖掘新增數據，然后與原有數據合并，產生關聯規則，而其他算法都只能重新挖掘15萬條告警記錄，因此算法效率有很大差別。

3 結束語

本文針對實際網管系統數據逐漸更新的情況，提出了增量式更新算法，從理論推導和實驗結果兩方面證明了增量式挖掘更加有利于實際電信網絡中告警關聯規則的挖掘。

參考文獻：

[1] Agrawal R,T.Imielinski,and A.Swami.Mining Association Rulesbetween Sets of items in LargeDatabases[C].Proeeedings of the 1993 ACM SIGMOD conference,Washington,D.C.,May 1993:207~216

[2] K.Hatonen,M.Klemettinen,H.Mannila,P.Ronkainen.Knowledge

discovery from telecommunication network alarm databases [C].Proceesing of the 12th Intemational Conference on Data Engineer,(ICDE'96) New Orleans,Louisiana,Feb.1996:115~122

[3] K. Hatonen, M.KLemettinen,H.Mannila,Portland,oregon.TASA:Telecommunications Alarm Sequence Analyzer or How to enjoy faults in your network [A].IEEE/IFIP 1996 Network Operations and Management symposium(NOMS'96)[C].,Kyoto,Japan,April 1996:520~529

[4] Cheung D.W.et al.Maintenance of Diseovered Association Rules inlarge Databases:An Incremental Updating Technique[C].In:Proeeedings of the 1996 International Conference on Data Engineering,New Orleans,louisiana,1996:106~114

[5] Cheung D.W.et al.A General Incremental Technique for UP dating Discovered Assoeiation Rules[C].In:Proceedings of the 1997 International Conference on DatabaseSystems for Advaneed Application. Melbourne,1997:185~194

[6] 馮玉才,馮劍琳.關聯規則的增量式更新算法[J].軟件學報,1998.9

(4):301~306