基于频繁模式链表的最大频繁项目集快速挖掘算法

摘要

频繁项目集挖掘是关联规则挖掘应用中的重要研究内容之一.目前,已提出了大量挖掘频繁项目集的算法,比较经典的算法有Apriori算法、FP-Growth算法等,主要从以下几个方面进行改进:(1)减少扫描数据库的次数,降低I/O负载代价,提高算法速度;(2)有效计算项目集的支持数,避免产生组合爆炸;(3)提出新的数据存储结构.在上述诸多算法中,计算项目集的支持数是发现频繁项目集中最耗时的工作,占据整个计算量的大部分工作.因此,不生成候选项目集或降低候选项目集的数量是减少开销的最好的手段.挖掘频繁项目集的缺点是,要考虑太多的候选项目集(大小为1的频繁项目集的21个候选子集都要考虑).由于最大频繁项目集中已经隐含了所有频繁项目集,因此可把频繁项目集挖掘问题转化为最大频繁项目集挖掘问题,本文使用更简单数据结构--频繁模式链表来存储包含最大频繁项目集的信息,并提出了一种新挖掘算法FPL-DMFI.采用了位串(bitstring)技术和位与操作,同时采用了压缩技术来缩小搜索范围,有效地提高了判断是否是最大频繁项目集的效率.该算法能通过并行投影和压缩技术扩展到大数据库中进行最大频繁项目集挖掘.由于FPL-DMFI算法处理长位串时挖掘效率相对不高,作者下一步的工作着重研究这方面的内容,同时研究最大频繁项目集挖掘算法如何应用于电力系统负荷预测模型中.