通信网告警相关性分析中有效的关联规则挖掘算法第34卷增刊JOURNALOFXIDIANUNIVERSITYVol.34Sup.通信网告警相关性分析中有效的关联规则挖掘算法李彤岩，李兴明（电子科技大学宽带光纤传输与通信网技术教育部重点实验室，四川成都610154）摘要：关联规则挖掘算法是通信网告警相关性分析中的重要方法。在处理数量庞大的告警数据库时，算法的效率显得至关重要，而经典的FP-growth算法会产生大量的条件模式树，使得在通信网环境下挖掘关联规则的难度非常大。针对上述问题，提出了一种基于分层频繁模式树的LFPTDP算法，采用分层模式树的方法产生频繁项集，从而避免了产生大量的条件模式树，并用动态剪枝的方法删除大量的非频繁项。算法分析及仿真表明，LFPTDP算法具有较好的时间和空间效率，是一种适合于通信网告警相关性分析的关联规则挖掘算法。关键词：关联规则；告警相关性分析；条件模式树；分层频繁模式树中图分类号：TN915.07文献标识码：A文章编号：1011-2400(2007)S1-0039-04AnefficientmethodforassociationrulesminedintelecommunicationalarmcorrelationanalysisLITong-yan，LIXing-ming(KeyLaboratoryofBroadbandOpticalFiberTransmissionandCommunicationNetworksofMinistryofEducation,UESTC,Chengdu，610154)Abstract:Theminingofassociationrulesisoneoftheprimarymethodsusedintelecommunicationalarmcorrelationanalysis,inwhichthealarmdatabasesareverylarge.Theefficiencyofthealgorithmsplaysanimportantroleintacklinglargedatasets.TheclassicalFP-growthalgorithmcanproducealargenumberofconditionalpatterntreeswhichmakesitdifficulttomineassociationrulesintelecommunicationenvironment.Inthispaper,analgorithmLFPTDPbasedontheLayeredFrequentPatternTreeisproposedforminingfrequentpatternsanddeletinginfrequentitemswithdynamicpruningwhichcanavoidproducingconditionalpatterntrees.Analysisandsimulationshowthatitisavalidmethodwithbettertimeandspaceefficiency,whichisadaptedtominingassociationrulesintelecommunicationalarmcorrelationanalysis.Keywords:associationrules;alarmcorrelationanalysis;conditionalpatterntree;LayeredFrequentPatternTree关联规则挖掘是数据挖掘中的一个非常重要的研究领域，适合于通信网的告警相关性研究[1]，可以通过挖掘关联规则找出告警之间的相关性，从而有效的定位故障。一个网络故障往往会在短时间内引发大量告警的产生，挖掘算法的效率直接影响到了故障的定位和网络性能的恢复，所以将研究的重点放在如何提高关联规则的挖掘效率方面。FP-Tree（FrequentPatternTree）以及FP-growth（Frequentpatterngrowth）算法[2]避免产生大量的候选项集，是一种深度优先的挖掘算法。其算法思想是将数据库中的频繁项压缩成一棵频繁模式树（FP-Tree）的形式，FP-Tree是一种可扩展的前缀树形压缩存储结构，树的节点包含了频繁模式的关联信息。然后将这种压缩的数据库分成若干组条件模式树分别进行挖掘，每个条件数据库和一个频繁项集的数据库相关联，当原始数据量很大的时候，也可以结合划分的方法,使一个FP-tree可以放入主存中。FP-growth是一种基于FP-Tree的频繁模式挖掘算法，通过扫描FP-Tree将发现的长频繁模式的问题转化成递归的发现一些短模式，然后连接后缀，可大大节省搜索空间。构造FP-Tree的过程只需要两次遍历交易数据库，第一次扫描数据库生成频繁1-项集集合并计算每个频繁项的个数，按照频繁项的降序排列成列表；第二次将扫描排序后的项集并生成FP-Tree。假设项集中的交易项数为，则转化为FP-Tree的算法复杂度为。对比Apriori算法n()On[3]可知，FP-Tree及FP-growth算法在效率上有了很大的提高，并对不同长度的规则都有很好的适应性。因为FP-Tree在存储数据结构上有了很大的改进，以后的研究主要是针对存储结构的改进。FPMAX算法[4]基于FP-tree结构来产生MFI-tree（maximalfrequentitemsetstree），用来挖掘存储最大频繁项集。但是MFI-tree是一种全局数据存储结构，当项集大时产生的数量会非常庞大，...