● 摘要
关联规则挖掘是数据挖掘的重要组成部分，近年来关联规则挖掘领域发展非常迅速，很多研究者提出了大量有效的关联规则挖掘算法。本文研究了关联规则挖掘的历史、现状和未来的发展趋势，列举了到目前为止比较有效的关联规则挖掘算法，并重点描述了关联规则挖掘的经典算法——FP-Growth（Frequent Pattern Growth，频繁模式增长）算法。在此基础上，本文以FP-Tree（Frequent Pattern Tree，频繁模式树）数据结构为基础，调整了该数据结构中结点的排列方式，改变了FP-Tree中所有结点都按照项的全局支持度递减排列的方式，采用递归方法构建树的所有子树，构建过程中，以最大程度地共享结点为原则，使树的每个局部都实现了结点的最优排列，进而提出了基于FP-Tree的改进数据结构——BFP-Tree（Best Frequent Tree，最优单项前缀树）结构。另外，本文以FP-Growth算法为基础，分析了该算法所使用的FP-Tree以及条件FP-Tree的头表所使用的存储结构对挖掘效率的影响程度，将头表的链式存储结构改进为基于哈希思想构建的顺序存储结构，并对原始数据库中的频繁项进行ID映射，提出了基于FP-Growth算法的改进算法——HFP-Growth（Hash Frequent Pattern Growth，基于映射哈希表的频繁模式增长）算法。最后，将BFP-Tree数据结构和HFP-Growth算法相结合，分析了二者结合过程中可能出现的问题，给出了问题的解决策略和具体解决方法，最终提出了更优的关联规则挖掘算法——BHFP-Growth（Best Hash Frequent Pattern Growth，基于最优单项前缀树和映射哈希表的频繁模式增长）算法。本文在所提出的每一种改进之后，都进行了相应的实验验证。各实验的结果表明，对于同一个数据集，本论文提出的BFP-Tree数据结构中的结点数量大大低于FP-Tree，数据压缩率大大提高。另外，所提出的HFP-Growth算法和BHFP-Growth算法，在效率上都要优于传统的FP-Growth算法，而BHFP-Growth算法的挖掘效率比HFP-Growth算法更高。