第34卷 增 刊 JOURNAL OF XIDIAN UNIVERSITY V ol.34 Sup.
通信网告警相关性分析中有效的关联规则挖掘算法
李彤岩， 李兴明
（电子科技大学 宽带光纤传输与通信网技术教育部重点实验室，四川 成都 610054）
摘要：关联规则挖掘算法是通信网告警相关性分析中的重要方法。
在处理数量庞大的告警数据库时，算法的效率显得至关重要，而经典的FP-growth 算法会产生大量的条件模式树，使得在通信网环境下挖掘关联规则的难度非常大。
针对上述问题，提出了一种基于分层频繁模式树的LFPTDP 算法，采用分层模式树的方法产生频繁项集，从而避免了产生大量的条件模式树，并用动态剪枝的方法删除大量的非频繁项。
算法分析及仿真表明，LFPTDP 算法具有较好的时间和空间效率，是一种适合于通信网告警相关性分析的关联规则挖掘算法。
关键词：关联规则；告警相关性分析；条件模式树；分层频繁模式树
中图分类号：TN915.07 文献标识码：A 文章编号：1001-2400(2007)S1-0039-04
An efficient method for association rules mined in telecommunication alarm correlation analysis
LI T ong-yan ， LI
Xing-ming (Key Laboratory of Broadband Optical Fiber Transmission and Communication Networks
of Ministry of Education, UESTC, Chengdu ，610054)
Abstract: The mining of association rules is one of the primary methods used in telecommunication alarm correlation analysis, in which the alarm databases are very large. The efficiency of the algorithms plays an important role in tackling large datasets. The classical FP-growth algorithm can produce a large number of conditional pattern trees which makes it difficult to mine association rules in telecommunication environment. In this paper, an algorithm LFPTDP based on the Layered Frequent Pattern Tree is proposed for mining frequent patterns and deleting infrequent items with dynamic pruning which can avoid producing conditional pattern trees. Analysis and simulation show that it is a valid method with better time and space efficiency, which is adapted to mining association rules in telecommunication alarm correlation analysis. Key words: association rules; alarm correlation analysis; conditional pattern tree; Layered Frequent Pattern Tree
关联规则挖掘是数据挖掘中的一个非常重要的研究领域，适合于通信网的告警相关性研究[1]，可以通过挖掘关联规则找出告警之间的相关性，从而有效的定位故障。
一个网络故障往往会在短时间内引发大量告警的产生，挖掘算法的效率直接影响到了故障的定位和网络性能的恢复，所以将研究的重点放在如何提高关联规则的挖掘效率方面。
FP-Tree （Frequent Pattern Tree ）以及FP-growth （Frequent pattern growth ）算法[2]避免产生大量的候选项集，是一种深度优先的挖掘算法。
其算法思想是将数据库中的频繁项压缩成一棵频繁模式树（FP-Tree ）的形式，FP-Tree 是一种可扩展的前缀树形压缩存储结构，树的节点包含了频繁模式的关联信息。
然后将这种压缩的数据库分成若干组条件模式树分别进行挖掘，每个条件数据库和一个频繁项集的数据库相关联，当原始数据量很大的时候，也可以结合划分的方法,使一个FP-tree 可以放入主存中。
FP-growth 是一种基于FP-Tree 的频繁模式挖掘算法，通过扫描FP-Tree 将发现的长频繁模式的问题转化成递归的发现一些短模式，然后连接后缀，可大大节省搜索空间。
构造FP-Tree 的过程只需要两次遍历交易数据库，第一次扫描数据库生成频繁1-项集集合并计算每个频繁项的个数，按照频繁项的降序排列成列表；第二次将扫描排序后的项集并生成FP-Tree 。
假设项集中的交易项数为，则转化为FP-Tree 的算法复杂度为。
对比Apriori 算法n ()O n [3]可知，FP-Tree 及FP-growth 算法在效率上有了很大的提高，并对不同长度的规则都有很好的适应性。
因为FP-Tree 在存储数据结构上有了很大的改进，以后的研究主要是针对存储结构的改进。
FPMAX 算法[4]基于FP-tree 结构来产生MFI-tree （maximal frequent itemsets tree ），用来挖掘存储最大频繁项集。
但是MFI-tree 是一种全局数据存储结构，当项集大时产生的数量会非常庞大，因为一个项集的产生需要经过成千上万次最大化的比较，
这使得FPMAX 算法变得非常复杂。
FPMAX ＊
算法[5]是其改进算法，它虽然使用的是MFI-tree 结构，但是在每个条件FP-Tree 中将创建局部的MFI-tree ，如果由条件FP-Tree 中产生的局部最大频繁项是全局最大的，就只需要和局部
MFI-tree 中的项集比较。
对比FPMAX 算法，FPMAX ＊
可以降低算法复杂度和提高算法效率，并且减少了内存的占用率。
集中以上几种算法的优点，笔者提出了一种基于动态剪枝的分层频繁模式树（Layered Frequent Pattern Tree with
—————————————— 收稿日期：2007-05-20
基金项目：国家自然科学基金资助项目（60572091） 作者简介：李彤岩（1980-），女，电子科技大学博士研究生。
Dynamic Pruning, LFPTDP ）算法，使用分层的思想来逐层生成频繁项集，并且通过动态剪枝来删除小于最小支持度的项集，有较好的时间和空间效率。
1 相关概念介绍
假设表示项集，数据库表示交易集，其中每个交易都是由中的项集所组成并且有唯一的标识符。
称为k -项集，为项集的长度。
当12{,,,}m I i i i ="12{,,,}n D t t t ="I TID I k I D t ∈且I 时称作一个交易包含项集。
项集的支持度表示为t ⊆t I I D 中交易包含项集的百分比：Supp I ort()Support _Count()/I I T =，其中是数据库T D 中的交易数。
关联规则由的形式给出，其中项集且12I :I r ⇒12,I I I ⊂21I I φ=∩。
关联规则的置信度表示为包含的交易中同时包含的概率：co r 2I 1I nfidence()r ={}D I t t ⊆∈/t D ∈。
关联规则r 的支持度表示为：。
12support()support()r I =∪I 在交易数据库D 中，挖掘关联规则的问题就可以归结为：在给定最小支持度和最小置信度阈值的前提下，寻
找所有满足和m 的关联规则。
具体的可以分解成求解以下两个子问题：
minsupport inconfidence 1. 找到D 中所有的频繁项集，即不小于的项集。
minsupport 2. 根据不小于的条件产生所有关联规则：minconfidence 2122I I I I I ⇒−⊂1。
由于第二个子问题在得知所有频繁项集和其支持度的前提下都可以直接在内存中解决，所以关联规则挖掘问题主要集中在如何寻找频繁项集上。
2 FP-Tree 及FP-growth 算法
FP-growth 算法[2]通过构造FP-Tree 结构来存储频繁模式的信息，并且通过频繁模式树增长的方式来实现频繁模
式的挖掘。
这种算法将庞大的数据库压缩到一个树型结构中，可以避免反复的扫描数据库和产生候选项集。
带有前缀的条件模式树将挖掘任务分成一个个小的任务去执行，以提高挖掘的效率。
2.1 FP-Tree 构建算法
（1）遍历数据库产生频繁项；
（2）将频繁项按照其支持度降序排列成列表的形式；
（3）创建FP-Tree 。
可以分为以下两个步骤：第一步是创建根节点并置为“null ”。
第二步将排序好的项构建成FP-Tree 的枝干。
如果新产生的枝和原来的共享同一个前缀的话，就将新枝连接在其后，并将节点的计数增加，否则就在根结点下创建一个新的节点，依此类推就创建好一棵FP-Tree 。
2.2 FP-growth 算法
（1）找出FP-Tree 中所有频繁模式的条件模式基； （2）在条件模式基的前提下创建条件FP-Tree ； （3）挖掘各个条件模式树以生成频繁项集。
3 LFPTDP 算法
在通信网告警关联规则挖掘的过程中，告警数量非常大，使得构建的FP-Tree 结构非常庞大，条件模式基也是海量的，并且同一个项在生成不同的条件模式基时要反复计数，从而造成挖掘效率较低。
LFPTDP 算法采用分层生成频繁项集的方法，避免了产生数量庞大的条件模式树，并且通过动态剪枝来提高挖掘的效率。
3.1 构造分层模式树（LFP-Tree ）
根据FP-Tree 的思想来构造频繁模式树，在每个节点只存储一个项，这样就会产生多个分枝。
而笔者采用分层的概念来构造分层频繁模式树LFP-Tree ，即第一层只包含频繁1项集及对应的支持度，第2层包含频繁2项集的支持度并以此类推。
下面通过一个实例来说明LFP-Tree 的构造过程。
表1展现了一个交易数据库。
代表交易的唯一识别，数据库中共有9条交易，域表示交易数据集，交易数据集是由五项组成的。
这里用一个三元组TID Itemsets 125{,,,}I I I ",,a v t <>来表示项集中不同项的出现次数以及和最小支持度比较的布尔值[6]，其中表示项的名称，v 表示该项出现的次数（即支持度计数），t 表示该项
a
增 刊 李彤岩等：通信网告警相关性分析中有效的关联规则挖掘算法 41
的支持度和最小支持度阈值（指支持度计数）的比较值，小于m 的表示为“0”，不小于m 的表示为“1”，这样就可以根据t 值来动态剪枝了。
minsup insup insup 表1 交易数据库举例
2
I 1
I 3
I 5I 4I 2I 2I 3I 2
I 1
I 4
I 1
I 3
I 4I 2I 3I 1I 3I 2
I 1
I 3
I 5
I 2
I 3
I 1
I
1:6:1I 1:1:0I 2:7:1I 3:7:1I 4:3:1I 5:2:1
I 1
:3:1
I 3:2:1I 2:2:1I 4:0:0I 1:1:0I 2:3:1I 3:1:0
I 1:5:1I 2:5:1
I 1:4:1I 1:1:0
I 1:1:0I 1:1:0I 2:1:0
I
图1 LFP-Tree 的构造过程
图1展现了LFP-Tree 的构造过程。
假定m 为2，首先遍历交易数据库，将交易所出现1-项集及其支持 insup 度计数表示出来，并按照项集的顺序排列在第1层：1:6:1I <>，2:7:1I <>，3:7:1I <>，<I 4 : 3 : 1>，
5:2:1I <>5I 1。
当t 的值为“0”时，此项集的向下链接即为空。
在生成LFP-Tree 第2层以上的过程中，采用和文
献[7]类似的反转方式进行，不是由链接，而是由链接，链接。
反转链接的好处是使得每一层的项集都是从开始的，保持了和前一层一致的顺序，方便进行挖掘。
第2层中的表示的是频繁2-项集的支持度计数，第层表示的是频繁-项集的支持度计数。
生成频繁2-项集的时候，从开始链接，和链接的只有，共同出现了4次，高于，所以在第2层中的链接表示为，和链接的支持度分别是5、5，记为、1I 2,,I "5I 14,,I I "n I 1,,n I I −"1I v k k 2I 2I 1I 12I I minsup 2I 1:4:1I <>3I 12,I I 1:5:1I <>2:5:1I <>，和链接的支持度分别是1、3、1，其中有两个支持度小于，则t 表示为“0”
，记为4I 123,,I I I minsup 1:1:0I <>、2:3:1I <>、，和链接的支持度分别是1、2、2、0，记为3:1:0I <>5I 1234,,,I I I I 1:1:0I <>、2:2:1I <>、3:2:1I <>、。
三元组
中t 为0的项被剪枝，
不再产生下一层的链接。
生成频繁3-项集时，从第2层中的开始连接，和链接的支持度为3，记为，和链接的的支持度为1，记为4:0:0I <>2I 3I 2I 1I 1:3:1I <>4I 2I 1I 1:1:0I <>，和链接的的支持度为1，记为，和链接的、支持度分别为1、1，记为5I 2I 1I 1:1:0<>I 5I 3I 1I 2I 1:1:0I <>、。
其中为0的项被剪枝，仅剩下一项，至此LFP-Tree 的构造结束。
2:1:0I <>t 1:
3:1I <>表2 生成的频繁-项集
k 1:6:1I 2:7:1I 3:7:1I 4:3:1I 5:2:1
I 1:3:1
I 3:2:1
I 2:2:1I 2:3:1
I 1:5:1I 2:5:1
I 1:4:1
I
12345
I I I I I ,,,,213132425251
,I I I I I I I I I I I I ,,,,321
I I I
图2 动态剪枝后的LFP-Tree
5I }} 图2是经过动态剪枝后的LFP-Tree ，从这个结构中可以清晰的看到产生的频繁-项集。
通过每一条链接可
以得到频繁1-项集为，频繁2-项集为，频繁3-项集为，生成的频繁-项集见表2。
LFP-Tree 构造算法的步骤如下：
k 1I ",
,213132425251,I I I I I I I I I I I I {,,,,321I I I {k Input: 交易数据库D ，最小支持度。
minsup Output: LFP-Tree 。
（1）遍历数据库D ，记录每一项的支持度计数并根据产生频繁1-项集； minsup （2）按照项集的顺序排列，以三元组的形式1I ,...,5I ,,a v t <>存储。
（3）遍历数据库D ，从的子集开始，寻找频繁2-项集，并按照的顺序排列，将频繁2- 2I 1I ",
,4I 项的集支持度计数存储在第2层相应的项集中。
按照这个思想，第层从k k I 的子集中寻找可以构成频繁-项集的项，直到层项集中只包含项或是为空时结束。
若三元组中t 为0，则将该组元素删除进行剪枝。
k k 1I 链接从第一层元素指向第二层和其构成2-项集的元素，由第二层元素指向第三层和其构成3-项集的元素，
一直链接到最后一层。
42 西安电子科技大学学报（自然科学版） 第34卷
（4）LFP-Tree 构造完成，这个分层树型结构中已经包含了所有的频繁模式。
3.2 基于LFP-Tree 的关联规则挖掘算法LFPTDP
LFPTDP 算法由于加入了动态剪枝并利用了反转层次生成LFP-Tree 的思想，能够动态的删除不频繁的项集，并且分层可以清晰的产生频繁-项集，避免了FP-Tree 中要重复计算节点支持度和产生大量的条件模式树。
k LFPTDP 算法:
（1）构造LFP-Tree 。
（2）确定树的深度即LFP-Tree 的层数。
n （3）由剪枝后的LFP-Tree 生成最大频繁模式：从第层到第1层的链接。
n 例如上面例子中LFP-Tree 的层数是3，输出的最大频繁模式是。
321I I I 3.3 算法分析
从算法的实现过程可看出，LFPTDP 算法的基本思想还是基于经典Apriori 算法[3]
的，
这样可避免产生大量的条件模式树，对于数据量大的告警关联规则挖掘来说可执行度要高得多。
在LFP-Tree 结构中，对于每一层的元素采用一个三元组来描述，其中代表了层的-项集支持度计数，t 表示了该项是否频繁，从而巧妙的删除了非频繁项。
在第层，只用记录和1，…，,,a v t <>v k k k 1k −层组成频繁-项集的那个项的三元组，这样就可以减少存储空间，同时具有相同前缀的频繁模式指向同一个上层频繁项，进一步节省了指针数和空间。
当一个LFP-Tree 构造完成后，这个分层树型结构中就包含了所有的频繁模式以及路径，其中最长的一条路径就是挖掘出来的最大频繁项集。
此外整个频繁告警数据压缩在一个分层树型结构中，对于告警数据库挖掘的动态更新也很有价值。
k 仿真结果（见图3）证明以上分析是正确的。
在处理通信告警方面，LFPTDP 算法比FP-growth 算法更加有效。
图3 两种算法时间及占用内存的比较
4 结论
在告警相关性分析中，有效的关联规则挖掘算法的研究显得至关重要。
在分析了经典算法之后，笔者提出了
一种基于LFP-Tree 的LFPTDP 算法，这种算法采用了分层模式树的方法来产生频繁项集，并用动态剪枝的方法删除大量的非频繁项，它既避免了FP-Tree 算法中产生大量的条件模式树，又使存储结构可以借鉴FP-Tree 算法，综合了几种算法的优点，具有较高的时间和空间效率。
参考文献
[1] Bouloutas, Calo A T, S Finkel A. Alarm Correlation and Fault Identification in Communication Networks [J]. IEEE Trans on Communications, 1994, 234 (42): 523-533.
[2] Han J, Pei J, Yin Y , et al. Mining Frequent Patterns without Candidate Generation: a Frequent-Pattern Tree Approach [J]. Data Mining and Knowledge Discovery, 2004, 1(8): 53-87.
[3] Agrawal R, Imielinski T , Swami A. Database Mining: a Performance Perspective [J]. IEEE Trans on Knowledge and Data Engineering, 1993, 5(6): 914-925.
[4] Grahne G , Zhu J. High Performance Mining of Maximal Frequent Itemsets [C]//Proc SIAM W orkshop High Performance Data Mining: Pervasive and Data Stream Mining, 2003.
[5] Grahne G , Zhu J. Fast Algorithms for Frequent Itemset Mining Using FP-Trees[J]. IEEE Trans on Knowledge and Data Engineering, 17(10): 1347-1362.
[6] Pi D C, Qin X L, Gu W F , et al. STBAR: a More Efficient Algorithm for Association Rule Mining [C]// Proceedings of the Fourth International Conference on Machine Learning and Cybernetics, Guangzhou, 2005: 18-21.
[7] Coenen F, Leng P, Ahmed S. Data Structure for Association Rule mining T -Trees and P-Trees [J]. IEEE Trans on Knowledge and Data Engineering, 2004, 16(6): 774-778.。
