一種關(guān)聯(lián)規(guī)則增量式挖掘算法研究

劉造新

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

關(guān)鍵詞： 關(guān)聯(lián)規(guī)則； 數(shù)據(jù)發(fā)掘； 滑動窗口； 增量計算

中圖分類號：TP3文獻標(biāo)志碼：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 引言

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

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

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

1 關(guān)聯(lián)規(guī)則的增量式更新算法

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

1.1 算法框架

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

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

表1算法中符號說明

[[&數(shù)據(jù)庫D&數(shù)據(jù)庫d&數(shù)據(jù)庫D∪d&窗口數(shù)&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數(shù)據(jù)庫中的相關(guān)系數(shù)為

cov(X,Y)=

=+

=

⑵ 增量計算δx

δx=

=

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

1.2 算法描述

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

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

輸出：S中滿足minCor和minConf的關(guān)聯(lián)規(guī)則。

方法：

⑴ [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

⑹ 將兩次挖掘結(jié)果，根據(jù)均值，調(diào)整、組合

⑺ 根據(jù)minCor和minConf，挖掘二項關(guān)聯(lián)規(guī)則

⑻ 生成多項集

2 實驗及其分析

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

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

圖1執(zhí)行時間比較

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

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

圖2增量數(shù)據(jù)執(zhí)行時間比較

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

3 結(jié)束語

本文針對實際網(wǎng)管系統(tǒng)數(shù)據(jù)逐漸更新的情況，提出了增量式更新算法，從理論推導(dǎo)和實驗結(jié)果兩方面證明了增量式挖掘更加有利于實際電信網(wǎng)絡(luò)中告警關(guān)聯(lián)規(guī)則的挖掘。

參考文獻：

[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] 馮玉才,馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報,1998.9

(4):301~306