2007年9 月 西安电子科技大学学报（自然科学版） Sep.2007
第34卷 增 刊 JOURNAL OF XIDIAN UNIVERSITY Vol.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 Tong-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
()On[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-），女，电子科技大学博士研究生。
40 西安电子科技大学学报（自然科学版） 第34卷
Dynamic Pruning, LFPTDP）算法，使用分层的思想来逐层生成频繁项集，并且通过动态剪枝来删除小于最小支持
度的项集，有较好的时间和空间效率。
1 相关概念介绍
假设表示项集，数据库表示交易集，其中每个交易都是由中的项集所组
成并且有唯一的标识符。称为k
-项集，为项集的长度。当12{,,,}
mIiii="
12{,,,}
nDttt="I
TIDIk
IDt∈
且I时称作一个交易包含项集
。 项集的支持度表示为t⊆t
IID
中交易包含项集的百分比：SuppIort()Support_Count()/IIT=
，其中是数
据库T
D
中的交易数。关联规则由的形式给出，其中项集且
12I:Ir
⇒
12,
III⊂
21IIφ
=∩
。关联规则的置信度
表示为包含的交易中同时包含的概率：cor
2I
1Infidence()r
={}
DItt
⊆∈/
tD∈
。关联规则r的支持度表
示为：。
12support()support()rI=∪I
在交易数据库D
中，挖掘关联规则的问题就可以归结为：在给定最小支持度和最小置信度阈值的前提下，寻
找所有满足和m
的关联规则。具体的可以分解成求解以下两个子问题： minsupportinconfidence
1. 找到D
中所有的频繁项集，即不小于的项集。 minsupport
2. 根据不小于的条件产生所有关联规则：
minconfidence
2122IIIII⇒−⊂
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条交易，域表示交易数
据集，交易数据集是由五项组成的。这里用一个三元组TIDItemsets
125{,,,}III",,avt<>
来表示项集中不同项的出现次数
以及和最小支持度比较的布尔值[6]
，其中表示项的名称，v
表示该项出现的次数（即支持度计数），t
表示该项a