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

劉造新

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

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

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

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

在實(shí)際網(wǎng)絡(luò)中非頻繁告警的種類是巨大的，而且具有很強(qiáng)的隨機(jī)性，挖掘這些告警間的關(guān)聯(lián)規(guī)則，對(duì)于網(wǎng)絡(luò)管理具有很大的實(shí)際意義。本文在分析以高相關(guān)度、高置信度為條件，在基于相關(guān)度統(tǒng)計(jì)的告警關(guān)聯(lián)規(guī)則挖掘AARSC算法(Alarm Association Rules Algorithm Based on Statistical Correlation)的基礎(chǔ)上，為了適應(yīng)告警數(shù)據(jù)動(dòng)態(tài)增加的特點(diǎn)，提出了一種增量式挖掘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]都是基于支持度-置信度框架下提出的，僅針對(duì)大于最小支持度閉值的頻繁項(xiàng)集進(jìn)行挖掘。我們這里在基于相關(guān)度AARSC算法基礎(chǔ)上，提出一種在數(shù)據(jù)庫(kù)增加時(shí)的增量式挖掘UAARSC(Updating-AARSC)算法。

1.1 算法框架

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

算法中的符號(hào)說(shuō)明。如表1所示。

表1算法中符號(hào)說(shuō)明

[[&數(shù)據(jù)庫(kù)D&數(shù)據(jù)庫(kù)d&數(shù)據(jù)庫(kù)D∪d&窗口數(shù)&n1&n2&n1∪n2&均值&μi0&μi1&μi&]]

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

⑴ 增量計(jì)算cov(X,Y)

這部分耗時(shí)最大，在D∪d數(shù)據(jù)庫(kù)中的相關(guān)系數(shù)為

cov(X,Y)=

=+

=

⑵ 增量計(jì)算δx

δx=

=

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

1.2 算法描述

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

輸入：⑴ 告警數(shù)據(jù)庫(kù)D； ⑵ 告警增量數(shù)據(jù)庫(kù)d；⑶ 最小相關(guān)度minCor； ⑷ 最小置信度minConf；⑸ 滑動(dòng)窗口win和滑動(dòng)步長(zhǎng)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，挖掘二項(xiàng)關(guān)聯(lián)規(guī)則

⑻ 生成多項(xiàng)集

2 實(shí)驗(yàn)及其分析

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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é)報(bào),1998.9

(4):301~306