挖掘频繁闭项集并构建其格的快速算法研究

论文摘要

随着经济的发展,信息对于一个国家或者企业越来越重要,人们被淹没信息之中,却得不到更多有用的知识。因此数据挖掘技术应运而生,并越来越显示出强大的生命力。关联规则挖掘作为数据挖掘领域的一个重要研究分支,它的任务是发现所有满足支持度阈值和置信度阈值的强关联规则。近年来,关联规则挖掘研究己经成为数据挖掘中的一个热点,并被广泛应用于金融、市场营销、事务分析等应用领域。关联规则挖掘算法是关联规则挖掘研究的主要内容,传统的关联规则挖掘算法以挖掘频繁项集为主要任务,但挖掘所有频繁项集需要大量的工作量;较前的研究表明:传统的关联规则挖掘产生太多冗余规则,而挖掘频繁闭项集的数量远小于所有频繁项集的数量,而且频繁闭项集不会产生信息丢失。因此用挖掘频繁闭项集来代替挖掘所有频繁项集是一个不错的选择。但为了加快产生关联规则的速度,仅仅有频繁闭项集是不够的,需要将项集之间的关系用一种有效的数据结构保存起来,格就是这样一种结构。因此用挖掘频繁闭项集及其格结构算法来快速高效的产生关联规则是一个重要的研究方向。本文主要工作包括:1)总结了目前一些挖掘频繁闭项集算法的不足,并针对最新的CHARM算法和频繁闭项集及其格结构算法CHARML进行了深入分析。2)针对CHARML算法中消除冗余效率不高、建格效率较低等缺点,引入了preC的概念,并进而提出了一种改进算法:Q-CFIsL算法。该算法在CHARML基础上,继承了CHARML的优化策略,同时采用了一些新的方法克服了CHARML的不足;该算法基于垂直数据结构,采用了一种直接利用IT-Tree的线性消除冗余的有效方法来构建频繁闭项集格,从而实现了挖掘频繁闭项集与建格的统一,并通过实验表明:当最小支持度越小,Q-CFIsL算法的性能就越优越,优于当前最新的同类算法CHARML。3)结合Q-CFIsL算法,利用挖掘出的频繁闭项集格来挖掘最小关联规则,根据最小关联规则推导出所有满足条件的关联规则,并通过实验证明了最小关联规则的有效性。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 课题研究意义
• 1.2 国内外研究现状
• 1.3 本文的研究目的和研究内容
• 1.3.1 本文研究目的
• 1.3.2 本文的研究内容
• 1.4 论文组织结构
• 2 数据挖掘理论研究
• 2.1 数据挖掘的产生
• 2.2 数据挖掘的一般性讨论
• 2.2.1 数据挖掘的定义
• 2.2.2 数据挖掘的特点
• 2.2.3 数据挖掘的分类
• 2.2.4 数据挖掘的方法
• 2.2.5 数据挖掘功能
• 2.3 数据挖掘未来发展趋势
• 2.4 本章小结
• 3 关联规则
• 3.1 关联规则概述
• 3.2 关联规则的基本概念
• 3.2.1 购物篮分析－引发关联规则挖掘的例子
• 3.2.2 关联规则相关定义及性质
• 3.3 关联规则挖掘的分类
• 3.4 关联规则的挖掘过程
• 3.5 挖掘关联规则的经典算法
• 3.5.1 Apriori 算法
• 3.5.2 频繁模式增长（FP-Growth）算法
• 3.6 本章小结
• 4 经典频繁闭项集算法及频繁闭项集格算法
• 4.1 相关问题概述
• 4.1.1 基本概念
• 4.1.2 IT-TREE 基本属性
• 4.2 CHARM 算法及其基本思想
• 4.2.1 CHARM 描述
• 4.2.2 算法基本思想
• 4.2.3 算法示例
• L 算法'>4.3 CHARM_L算法
• L 算法描述'>4.3.1 CHARM_L算法描述
• 4.3.2 算法基本思想
• 4.3.3 算法示例
• 4.4 本章小结
• 5 QCFIsL：挖掘频繁闭项集及建格的快速算法设计与实现
• 5.1 问题的提出
• 5.2 preC 的概念和性质
• 5.2.1 preC 的概念
• 5.2.2 preC 的定理
• 5.3 Q-CFIsL 设计与实现
• 5.3.1 算法描述如下
• 5.3.2 算法实现
• 5.4 算法示例
• 5.5 算法实验及结果分析
• 5.6 本章小结
• 6 基于格结构提取关联规则算法
• 6.1 基于频繁项集关联规则挖掘
• 6.2 基于频繁闭项集格关联规则挖掘
• 6.3 本章小结
• 7 总结
• 致谢
• 参考文献
• 附录