基于项对索引链表的优化FP—Growth算法
【摘要】 提出了基于邻接矩阵思想的FP-Growth改进算法IPILFPG，它采用项对索引链表作为FP树的辅助存储，避免重复遍历路径，优化搜索过程.该算法显著降低挖掘存储空间以及时间复杂度，提高挖掘效率.通过实验验证其正确性，并与其它算法比较验证其高效性.
【关键词】 数据挖掘；关联规则；FP-Growth；邻接矩阵；约束路径；项对索引链表
0引言
Agrawal 1993年提出的关联规则在数据挖掘中的应用最为广泛[1-2]，.其中Jianwei.Han[3-4]等人在2000年提出的基于FP树的FP-Growth（Frequent-Pattern Growth）算法是一种基于模式增长的挖掘算法，该算法时间和空间效率较高.该算法将事务D构造为频繁模式树（FP-Tree），然后采用基于后缀模式增长，递归构造条件子树，并遍历子树从而挖掘产生频繁项集.其缺点是：构造FP子树需要大量内存空间；另外在每次递归挖掘都需要两次遍历条件模式基.
目前基于FP-Growth 算法采用数组和邻接矩阵技术FP-Growth的优化算法有FP-Growth+[5] ，CFPmine[6]，NHTFPG[7]等[8-10].文献[5，8]中提出在FP-Growth算法中遍历FP-Tree时构造构造项对频繁FP数组，用来约减每次递归挖掘时重复遍历条件模式基，提高挖掘算法的速度，但是每次递归产生大量数组占用空间相当可观.文献[6，9]中用了基于压缩FP-Tree的约束子树的挖掘方法，采用基于数组的技术快速构造压缩FP-Tree的约束子树（CFP-树）用以实现避免在挖掘过程中生成条件FP-Tree，减少内存占用；无需遍历条件子FP-Tree，来提高算法的效率；此方法的效率性相对较低.文献[7]中利用递归回溯的方式遍历频繁模式树以求取所有条件模式基，解决了对同一树路径多次重复遍历的问题，但是频繁模式树的所有条件模式基与事务规模相当，存储复杂度相当大.
在挖掘中采用数组构造邻接矩阵能有效约减重复遍历条件模式基次数，构造邻接矩阵在遍历数据事务或条件FP-Tree时同时产生，并不增加算法的复杂度.分析和研究以上算法，提出在挖掘过程中：（1）采用邻接矩阵构造项对链表，约减重复遍历条件模式基次数；（2）将项对链表有序化，用以加快挖掘速度.为此该文提出了针对FP-Growth的改进算法—项对索引链表算法IPILFPG（Indexed Pair of Items List FP-Growth），并且在这里提出用图的邻接矩阵和模式基的约束路径方法[11]构造项对索引链表.
[BT4]
1优化算法
1.1优化思想
如何减少遍历条件模式基次数，不产生条件模式子树，以加快挖掘速度，节约存储空间.文献[8]在遍历条件FP-Tree采用二维数组计数省去第一次遍历条件模式基.根据经典算法每次以α为后缀进行挖掘时，需要第一次遍历条件模式基得到计数列表L_α，由于在扫描数据事务D或后缀遍历FP树时同时可以得到二维数组计数表，由该计数表可以直接得到计数列表L_α，从而省去第一次遍历α为后缀的条件模式基集合.
由于数组表示邻接矩阵时，实际数项较少，存储空间较大，访问速度慢 .该文提出建立项对索引链表替代数组，链表的建立在扫描数据事务集合或后缀遍历FP树生成条件模式基的同时得到，这里还采用对链表进行排序策略.
1.3约束路径
定义4（偏序关系“”）：对于项集中任意两个项ij，ik∈I，若i
j ik当且仅当ij的序号小于ik的序号.任意项集可以按项支持度大小降序排列，可以把项集视为有序序列.
定义5（约束路径）设i1，i2，…，ik为项的序号，N是FP-Tree树中的一个结点，P是从树根到N的子路径.我们说P是被项集{i1，i2，…，ik}所约束的路径，如果存在N的子孙结点M，使得i1，i2，…，ik出现在从N到M的子路径中，并且i1对应于N结点，i1对应于M结点，结点M的计数值M.count称为约束子路径P的基计数.
利用约束路径原理，可以在遍历FP-Tree树时加快生成α（α≠{Null}）为后缀的项对索引链表.
[BT4]
2项对索引链表
定义3（项对索引链表）项对索引链表是将2-项集邻接矩阵用链表表示存储，链表记录事务集合D中（或FP-Tree中）2-项集出现的支持度计数并且按各项支持度排序的索引链表结构.
事务集合D中2-项集可以用项对来表示，项对描述了项与项之间的关系.我们可以用带权邻接矩阵描述2-项集在D中出现的次数.邻接矩阵中sup_count（i，j）为2-项集
2.1链表数据结构
（1）链表中头项节点（head-node）包括3个域：头项名（head-name）、头项兄弟节点链接指针（head-link）和孩子节点链接指针（child-link），链表头项节点按头项名支持度计数降序排序.
（2）链表中头项节点下的孩子节点（child-node）包括3个域：孩子节点项名（child-name）、该孩子节点项计数（child-count）和兄弟节点指针（brother-link），同头项节点下的孩子节点按支持度计数降序排序.
3.2实验结果分析
实验结果挖掘出的频繁集合完全一致，通过实验得到如下结论：
（1）时间复杂度方面：由于改进算法减少了遍历条件模式基的次数，特别在数据集稠密度稀疏时（稠密度因子a较大时，稠密度因子a为M条事务中子项的共享前缀数量与事务总数比），事务共享前缀较少，FP-Tree分枝较多的情况下，条件模式基产生较多，本改进算法用时明显减少.在支持度减小的情况下，改进算法运行时间明显减小.
（2） 空间复杂度方面：基于矩阵优化算法中，在矩阵中实际数项较少，在满足最小支持度的数据项n较大时，本改进算法节省大量存储空间.
[BT4]
4结束语
通过分析经典FP-Growth算法，提出采用构建项对索引链表，为每次后缀模式挖掘条件模式基的遍历次数提出约减，进而提高挖掘速度.在满足最小支持度的数据项n较大时，比基于数组矩阵优化算法压缩出更多的存储空间，尤其是在数据集稠密度稀疏时，本算法效果更加显著，在访问速度上链表明显快于矩阵数组.
参考文献
[1]
Han J，Kamber M.Data minig：concepts and techniques[M].Bering：Higher Education Press，2001.
[2]朱明.数据挖掘[M]（第二版）.合肥：中国科技大学出版社，2008.
[3]Han Jiawei，Pei Jiun，YinYinwen，et al.Mining frequent patterns without candidate gener-ation：a frequent-pattern tree approach [J].Data Mining and KnowledgeDiscovery，2004，8（1）：53-87.
[4]Liu Guimei， Lu Hongjun， Jeffrey Xu Yu， et al.AFOPT： An Efficient Implementation of Pattern Growth Approach.[EB/OL].[2013-05-20].http：//ceur-ws.org/Vol-90/liu.pdf.
[5]郭伟，叶德谦.改进的基于FP-tree的频繁项集挖掘算法[J]. 计算机工程与应用， 2007，43（19）：174-176.
[6]秦亮曦，苏永秀，刘永彬，梁碧珍.基于压缩FP-树和数组技术的频繁模式挖掘算法[J]. 计算机研究与发展， 2008，45（9）：244-249.
[7]凌绪雄，王社国，李洋，等.无项头表的FP-Growth算法[J]. 计算机应用， 2011.5， 31 （5）：1391-1394.
[8]杨云，罗艳霞. FP-Growth算法的改进[J]. 计算机工程与设计，2010，3（7）：1506-1509.
[9]田王君，蒋军辉，陈士慧.基于矩阵技术的频繁项目集挖掘算法[J].计算机工程，2011.8，16（37）：80-81，97.
[10]刘应东，冷明伟，陈晓云.基于邻接矩阵的FP-tree构造算法[J].计算机工程与应用，2011，47（7）：153-155.
[11]贲可荣.离散数学（第2版）[M].北京：清华大学出版社，2011.10：125，198-212.
[12]FP-Growth code . （2002-02-11） [2012-12-23].http：//adrem.ua.ac.be/～goethals/software/.
[13]Frequent Itemset Mining Dataset Repository. Datasets . （2006-01-21） [2012-12-23].
http：//fimi.ua.ac.be/data/.
Abstract：
In this paper，an improved algorithm IPILFPG is proposed，which is based on adjacency matrix and FP – Growth，it adopts the indexed pair of items list as auxiliary storage of FP tree，which avoids repeatedly traversing path and optimizes searching process. This algorithm significantly reduces storage space and time complexity，meanwhile improving the mining efficiency. In this article，we verify its correctness and efficiency comparison with other algorithms through experiments.
Keywords： Data mining； Association rules； FP - Growth； Adjacency matrix； Constraint path； Indexed pair of items list
（责任编辑：李家云）