基于粗集与位阵的关联规则挖掘算法研究

摘要

作为数据库研究领域中的热点，数据库中的知识发现(简称KDD)正在受到越来越多的关注。它被定义为在数据中寻找正确的、有趣的、潜在有用的并最终可以理解的模式。对关联规则的挖掘在许多数据挖掘任务中都有重要作用，有着广泛的应用范围。随着被挖掘的数据集在大小和复杂度上的飞速增长，研究高效可伸缩的挖掘算法对保证系统的可伸缩性和交互性至关重要。 关联规则挖掘算法使用格理论中的组合特性来将原始问题分解为许多更小的互相独立的问题。最有名的和最有影响力的算法包括Apriori算法和FP-growth算法。 粗集理论根据对一个系统的观察和测量所得的现实数据信息，从分类的观点，以集合近似、近似分类与不可分辨的概念为基础，通过知识约简从中发现、推理知识和分辨系统的特点、过程、预测系统的结果等。DM_R算法尝试利用粗集理论中关于等价类的概念，针对单维布尔关联规则问题提出的一种挖掘算法，并利用兴趣度对规则进行评价。DM_R算法借助不可分辨关系的概念，将事务数据库按照交易集合划分等价类。该算法从k-候选项集中可以直接产生k-频繁项集，同时还可以生成(k+1)-候选项集而无需搜索数据库，因此DM_R算法只需在生成1-候选项集时对数据库进行一次搜索，这会大大减少计算时间。 通过对各项交易设定不同的MIF值，用户可以灵活控制不同的关联规则的最小支持度阈值，可以发现包含非频繁交易的具有较低支持度的关联规则以及具有较高支持度的包含频繁交易的关联规则，同时又不会引入过多无意义规则。 由于现实世界事务数据库中，数据是随时间的变化而变化的，当前已发现的最大频繁项集可能不再生效，而新的有效最大频繁项集有待于重新去发现。因此，迫切需要设计高效的算法来管理、维护和更新已挖掘出来的最大频繁项集。目前国内外在对这一问题的相关研究中提出了Pincer Search、IUA、FIUA、FUFIA、FUMFIA等算法，这些算法主要是针对频繁模式树来进行单双向剪枝与重构，需要额外的存贮空间和较大的运算开销。 对此，本文提出了一种增量式更新最大频繁项集算法FAUMFI(Fast A1gorithm for Updating Maximum Frequent Itemsets)，该算法将充分利用已有的一切信息(如旧的最大频繁项集、原来的BitMatrix等)，以高效地发现最新事务数据库中所有的最大频繁项集，并分析了算法的效率。

目录

文摘

英文文摘

声明

第一章绪论

1.1课题的提出和意义

1.2数据挖掘概述

1.3关联规则挖掘概述

1.4本课题的国内外研究现状

1.5本文的研究内容与目标

1.6本文的贡献

1.7本文的组织

第二章数掘挖掘的基本理论与经典的关联规则挖掘算法

2.1关联规则的基本理论

2.1.1关联规则的基本概念

2.1.2关联规则挖掘的方法步骤

2.1.3关联规则的种类

2.1.4关联规则挖掘的任务

2.2 Apriori算法

2.2.1Apriori算法流程

2.2.2候选集生成与利用Apriori属性剪枝

2.2.3性能分析

2.3 FP-growth算法

2.3.1FP树

2.3.2FP-growth算法流程

2.3.3性能分析

2.4对关联规则挖掘算法的一些改进

2.5小结

第三章基于粗集的单维布尔关联觇则的挖掘算法

3.1引言

3.2挖掘关联规则的DM_R算法

3.2.1使用等价类概念挖掘候选项集

3.2.2使用多个最小支持度阈值挖掘频繁项集

3.2.3关联规则的生成

3.3本章小结

第四章基于位阵的更新最大频繁项集算法

4.1引言

4.1.1相关的概念与理论

4.1.2最大频繁项集的更新

4.2更新最大频繁项集的算法

4.2.1最大频繁项集的增量式更新算法(情况1)

4.2.2最大频繁项集的增量式更新算法(情况2)

4.2.3最大频繁项集的增量式更新算法(情况3)

4.3仿真分析

4.3.1实验数据的介绍

4.3.2仿真分析

4.4本章小结

第五章结束语

5.1本文工作总结

5.2有待进一步研究的问题

参考文献

附录

致谢

攻读硕士期间发表的论文和主要研究成果