频繁模式挖掘算法与剪枝策略研究

论文摘要

频繁模式挖掘是一类基本的数据挖掘问题,可以广泛应用于关联规则分析、相关性分析、孤立点分析、分类和聚类等多种数据挖掘任务,是一个具有重要理论意义和广阔应用前景的课题。本文对频繁模式挖掘问题进行了深入研究和探索,主要内容如下:1.对频繁序列挖掘问题进行深入研究,探讨典型的挖掘算法—GSP、SPADE、SPAM、PrefixSpan,在此基础上,应用新的扩展策略,提出了一种全新的、高效的频繁序列挖掘算法—FINDER。该算法采用深度优先策略枚举搜索空间,使用垂直位图与水平位图向量格式表示项集、事务数据库、序列,摒弃了以往算法所采用的复杂的散列技术和数据库的多遍扫描。FINDER算法采用频繁项集序列扩展策略,最大限度地减少非频繁扩展。最后采用权威数据集生成程序生成测试数据集,验证算法的正确性与有效性。新算法FINDER的效率虽然没有SPAM高,但是,效率接近于SPAM,与其他典型的算法相比,效率提高约3～5倍。2.对FINDER算法进行改进,采取格理论对枚举空间进行划分,设计并行序列挖掘算法pFINDER。pFINDER继承了FINDER的特性,仍然没有采用散列技术,具有较好的局部性特征。pFINDER采取中间数据的划分技术,减少了远程数据的同步与数据传输。因此,pFINDER算法具有良好的可伸缩性。3.结合加权频繁序列挖掘问题,改进FINDER,设计交互式加权频繁序列挖掘算法。该算法采取项重命名机制,把加权项转化为平凡项,使之适合于有效的频繁序列挖掘算法,简化了加权序列挖掘问题,特别适合于交互式挖掘。该算法对于实际应用特别有效。4.频繁模式挖掘是一项十分复杂的I/O密集型和计算密集型的挖掘任务,搜索空间的剪枝是有效提高效率的手段。通过对频繁模式挖掘算法搜索空间的深入研究,在认真分析现有剪枝策略的基础上提出新的搜索空间剪枝策略SEP和IEP。同时证明了相关的定理与推论,保证了两种剪枝策略的理论正确性。5.对典型的频繁模式挖掘算法进行分析,应用新的剪枝策略SEP与IEP,对文献资料上普遍认为比较高效的SPAM、SPADE、MAFIA、CHARM等频繁模式挖掘算法进行改进,形成新的频繁序列挖掘算法或频繁项集挖掘算法SPAM+、SPADE+、MAFIA+、CHARM+,结合公认的测试数据集或测试集生成程序,对各算法进行实验,并进行对比分析,以验证剪枝策略的正确性与有效性。实验表明,利用剪枝策略SEP、IEP改进后的算法SPAM+、SPADE+、MAFIA+、CHARM+分别比原来的算法效率提高最多达10倍,对大数据集,效率的提高也在30%～50%。6.所提出的SEP与IEP剪枝策略不仅可以大大改善算法的性能,同时,通过对多个算法的改进,也表明了该策略可以被多种算法和挖掘问题共用,表现了SEP、IEP独立于挖掘算法的特性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 图示
• 表格
• 第1章 绪论
• 1.1.研究工作的背景和意义
• 1.2.本文研究工作的内容和目标
• 1.3.本文主要研究成果和创新之处
• 1.4.本文的组织结构
• 第2章 频繁模式挖掘问题及相关研究
• 2.1.数据挖掘
• 2.1.1.数据挖掘定义及挖掘过程
• 2.1.2.数据挖掘任务的分类
• 2.1.3.模式的度量
• 2.2.关联规则挖掘
• 2.3.关联规则的生成
• 2.4.频繁模式挖掘的分类
• 2.4.1.频繁项集挖掘（FREQUENT ITIBEETS MINING）
• 2.4.2.最大频繁项集挖掘（MAXIMAL FREQUENT ITEMSET MINING）
• 2.4.3.频繁闭项集挖掘（FREQUENT CLOSED ITERSET MINING）
• 2.4.4.频繁序列挖掘（FREOUENT SEQUENCE MINING）
• 2.4.5.加权频繁模式挖掘（WEIGHTED FREQUENT PATTERN MINING）
• 2.4.6.频繁片段序列挖掘（FREQUENT EPISODE MINING）
• 2.4.7.频繁子树挖掘（FREQUENT SUBTREE MINING）
• 2.5.频繁项集挖掘的相关研究工作
• 2.5.1.搜索空间之词典序子集枚举树
• 2.5.2.搜索空间之ITEMSET-TIDSET—TREE
• 2.5.3.主要数据结构之FP-树
• 2.5.4.主要数据结构之位图
• 2.5.5.经典算法之APRIORI
• 2.5.6.经典算法之FP-GROWTH
• 2.6.频繁序列挖掘的相关研究工作
• 2.6.1.搜索空间之基于格的枚举树
• 2.6.2.主要数据结构之位图
• 2.6.3.经典算法之GSP
• 2.6.4.经典算法之SPADE
• 2.7.小结
• 第3章 频繁序列挖掘算法研究
• 3.1.引言
• 3.2.问题定义
• 3.3.相关的研究工作
• 3.3.1.GSP算法
• 3.3.2.SPADE算法
• 3.3.3.SPAM
• 3.3.4.PREFIXSPAN
• 3.4.基于格的枚举方法
• 3.4.1.格相关的定义
• 3.4.2.基于频繁项集扩展序列枚举方法
• 3.5.FINDER算法
• 3.5.1.基本FINDER算法
• 3.5.2.FINDER算法的剪枝策略
• 3.5.3.数据表达及支持度计算
• 3.6.实验与结果分析
• 3.6.1.测试数据集的统计特性
• 3.6.2.FINDER与SPADE和SPAM的性能比较
• 3.6.3.可扩展性实验
• 3.7.并行算法PFINDER的设计
• 3.7.1.搜索空间的划分
• 3.7.2.数据划分
• 3.7.3.负载均衡
• 3.7.4.PFINDER算法
• 3.8.交互式加权频繁序列挖掘算法IFINDER的设计
• 3.8.1.交互式参数表达
• 3.8.2.IFINDER算法
• 3.9.小结
• 第4章 频繁模式挖掘剪枝策略研究
• 4.1.引言
• 4.2.频繁模式的搜索空间
• 4.3.相关剪枝策略
• 4.3.1.频繁项集剪枝策略
• 4.3.2.频繁序列剪枝策略
• 4.4.SEP与IEP策略
• 4.4.1.SEP剪枝策略及剪枝算法
• 4.4.2.IEP剪枝策略及剪枝算法
• 4.5.SEP与IEP策略的应用
• 4.5.1.IEP策略在频繁项集挖掘中的应用
• 4.5.2.SEP与IEP策略在频繁序列挖掘中的应用
• 4.6.实验与结果分析
• 4.6.1.IEP在频繁项集挖掘中的剪枝效果
• 4.6.2.SEP与IEP在频繁序列挖掘中的剪枝效果
• 4.7.小结
• 第5章 总结及下一步研究工作展望
• 5.1.总结
• 5.2.下一步研究工作展望
• 参考文献
• 在学期间的研究成果
• 致谢