论文摘要
关联规则挖掘作为数据挖掘领域中最活跃的研究分支之一，其目的是发现数据集中潜在的、新颖的、并为人类所理解的数据项间的关系。概念格理论，又称形式概念分析，用于概念的发现、排序和显示，其核心数据结构是概念格。概念格通过概念间的泛化和特化关系来表示知识。作为一种知识表示模型，概念格能够为关联规则挖掘提供有力支持。本文分析了现有关联规则挖掘算法中存在的主要问题。针对多次数据集扫描、候选集过多等问题，提出了在经典概念格中自顶向下、通过频繁概念逐层求取所有频繁项集的关联规则挖掘算法。针对规则冗余、无法及时更新等问题，优化了量化扩展概念格的结构，提出了事务集新增、删除和修改时格上的更新操作，通过将更新操作添加到Godin算法的建格过程中，形成了一种量化扩展概念格的增量式建格算法；根据最小等价内涵、封闭集定义了非冗余关联规则的模式，证明了由该模式形成的非冗余规则集是完备的；以此为基础设计实现了基于量化扩展概念格的增量式非冗余关联规则挖掘算法及约束型关联规则的挖掘算法。通过对算法在不同形式背景下执行时间的分析，验证了本文提出的“基于经典概念格的关联规则挖掘”改进了Apriori算法在“求取频繁项集”和“生成关联规则”两个模块的执行效率；“基于量化扩展概念格的关联规则挖掘”在“生成关联规则”模块的效率和质量两方面都优于上述两个算法。通过对算法特性的总结，得出当存在大量频繁项集时，“基于量化扩展概念格的关联规则挖掘”性能最优；当形式背景规模较大、频繁项集数量较少时，虽然因建格时间过长，整体性能不如其余两个算法，但“基于量化扩展概念格的关联规则挖掘”可以根据事务变更及时更新并且能够快速挖掘约束型关联规则，因此该算法实用性更强。