一种关联规则增量式挖掘算法研究

刘造新

摘要： 现有关联规则更新算法都是基于支持度-置信度框架而提出的，仅针对大于最小支持度闭值的频繁项集进行挖掘。为了提高告警关联规则的完整性和准确性，在相关度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