关联规则的精简方法研究

论文摘要

数据挖掘是指从大量数据中提取或“挖掘”知识。关联规则是数据挖掘当前研究的主要模式之一,用于确定数据集中不同域或属性之间的联系,找出有价值的多个域之间的依赖关系。发现频繁项集是关联规则挖掘中最基本、最重要的问题,自从Agrawal的开创性工作以来,有关研究从未停止过。当支持度阈值较低或数据集中存在长模式时,频繁项集挖掘可能产生大量频繁模式集,这将给人们的理解和从中发现有趣的模式造成一定的困难。为压缩庞大的频繁模式集,压缩的频繁项集挖掘是最近研究的一个热点问题,其中包括最大频繁项集挖掘和频繁闭项集挖掘。现有最大频繁项集挖掘算法,大多需要维护大量侯选项集并进行超集检测。当已有最大频繁项集数目较大时,超集检测将成为算法的瓶颈。本文首先提出了一种基于标记域FP-Tree的快速挖掘最大频繁项集算法BF-DMFI,该算法为FP-Tree中每个节点增加一个标记域,利用该域对节点进行有效的标记,从而减少了最大侯选频繁项集的数量,节约了超集检测时间,在一定程度上提高了算法的性能。按照搜索空间树的遍历策略,最大频繁项集挖掘算法分为宽度优先算法和深度优先算法。宽度优先算法大多需要维护大量候选项集并多次重复扫描数据库或搜索FP-Tree;而深度优先算法则需要递归构造频繁项的条件模式树并进行相应挖掘,这将加大算法的执行时间和所占用的内存空间。提出了一种基于FP-Tree的非递归深度优先挖掘算法DF-DMFI。该算法通过构造每个频繁节点的频繁子孙集和频繁前缀,连接生成最大频繁项集,利用MFI-Tree进行超集检测,并对FP-Tree进行有效的剪枝,从而保证了算法的执行效率。现有最大频繁项集和频繁闭项集挖掘算法,大多从事务数据库中直接挖掘,具有较高的时间和空间复杂度。提出了基于频繁项集的最大频繁项集（BFI-DMFI）和频繁闭项集挖掘算法（BFI-DCFI）。在BFI-DMFI算法中,通过逐个检测频繁项集在其集合中是否存在超集来判断该项集是不是最大频繁项集;在BFI-DCFI算法中,通过挖掘所有支持度相等的频繁项集中的最大频繁项集,组合生成频繁闭项集。利用此方法挖掘最大频繁项集和频繁闭项集在一定程度上降低了算法的时间和空间复杂度。在上述研究的基础上,本文最后设计并实现了一个关联规则挖掘工具原型。该原型可以挖掘出基于频繁项集、频繁闭项集和最大频繁项集的关联规则,并可根据用户自定义的规则进行约束挖掘,以进一步精简关联规则结果集。

论文目录

摘要

ABSTRACT

第一章绪论

1.1 数据挖掘概述

1.1.1 数据挖掘的兴起

1.1.2 数据挖掘的定义

1.1.3 数据挖掘面临的重要挑战

1.2 论文的研究内容和组织结构

1.2.1 论文的研究内容

1.2.2 论文的组织结构

第二章关联规则挖掘概述

2.1 关联规则挖掘

2.1.1 关联规则挖掘的基本概念

2.1.2 关联规则挖掘的步骤

2.1.3 频繁项集挖掘

2.2 由关联规则到相关分析

2.2.1 客观评价法

2.2.2 主观评价法

2.3 关联规则的精简方法

2.3.1 频繁闭项集挖掘

2.3.2 最大频繁项集挖掘

2.3.3 关联规则的其它压缩方法

2.4 本章小节

第三章基于标记域FP-Tree挖掘最大频繁项集

3.1 引言

3.2 相关知识

3.2.1 FP-Tree结构

3.2.2 深度优先搜索策略

3.3 基于标记域FP-Tree挖掘最大频繁项集算法BF-DMFI

3.4 算法分析与比较

3.5 本章小结

第四章基于FP-Tree深度优先挖掘最大频繁项集

4.1 引言

4.2 相关知识

4.2.1 多叉有序FP-Tree

4.2.2 MFI-Tree

4.3 基于多叉有序FP-Tree挖掘最大频繁项集

4.4 算法分析与比较

4.5 本章小结

第五章基于频繁项集挖掘最大频繁项集和频繁闭项集

5.1 引言

5.2 相关知识

5.3 基于频繁项集的最大频繁项集和频繁闭项集挖掘算法

5.3.1 基于完全频繁项集的最大频繁项集挖掘算法BFI-DMFI

5.3.2 基于完全频繁项集的频繁闭项集挖掘算法BFI-DCFI

5.4 算法分析和比较

5.5 本章小结

第六章关联规则挖掘工具原型设计与实现

6.1 开发环境

6.2 系统总体设计

6.3 工具原型的主要功能模块及实现方法

6.3.1 数据选择模块

6.3.2 算法选择模块

6.3.3 参数设置模块

6.3.4 挖掘结果展示模块

6.4 本章小结

第七章总结及进一步的工作

7.1 本文的主要工作

7.2 进一步的工作

参考文献

致谢

攻读硕士学位期间发表的学术论文

关联规则的精简方法研究

论文摘要

论文目录

相关论文文献

猜你喜欢