基于最大频繁项目集的数据挖掘关联规则算法研究

摘要

数据挖掘是致力于数据分析和理解、揭示数据内部蕴藏知识的技术，它成为未来信息技术应用的重要目标之一。经过十几年的努力，数据挖掘产生了许多新概念和方法。特别是最近几年，一些基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。像其它新技术的发展历程一样，数据挖掘技术也必须经过概念提出、概念接受、广泛研究和探索、逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段，迫切需要在基础理论、应用模式、系统构架以及挖掘算法和挖掘语言等方面进行创新。关联规则挖掘是数据挖掘中成果颇丰而且比较活跃的研究分支，留给研究者的是更深入的课题。面对大型数据库，关联规则挖掘需要在挖掘效率、可用性、精确性等方面得到提升。因此，需要探索新的挖掘理论和模型；需要对一些传统的算法进行改进；也需要研究新的更有效的算法等。鉴于目前数据挖掘技术和关联规则挖掘研究的现状和发展趋势，本文选择了基于最大频繁项目集的关联规则算法作为研究对象，并开展相关工作。
　　 本文针对客户数据库海量数据挖掘时间问题，为提高挖掘效率，从多方面满足用户分析数据的需求，论文借鉴了基于FP-tree最大频繁项目集挖掘DMFIA算法的相关思想，通过使用不同的数据分析方法，并灵活调整最小支持度数，提出了一种新的基于客户数据库的最大频繁项目集算法，可以从不同的角度分析数据，有效地减少了算法的执行时间。通过进一步分析发现原DMFIA算法和基于客户数据库的最大频繁项目集算法不能有效地解决客户序列视图数据库的数据挖掘问题，针对这一问题，借鉴以上算法相关思想，结合序列模式提出了一种新的基于序列模式的项目级最大频繁序列集算法，即将大于或等于最小支持度数s的项目按支持度由小到大的顺序开始做循环运算，但在对MFCSd进行循环运算时，若MFCSd中的元素，即以客户序列为单位的每一项，若所包含事务的项目支持度均大于或等于进行循环运算的某一频繁项目支持度数，提取出来形成MFCSk；对MFCSk中以客户序列为单位的每一项，则统计该客户序列在备份MFCS的支持度数flag，如果flag＞=s'(通常s=s')，则直接将该客户序列输出到最大频繁序列集MFSd，否则将MFCSd该客户序列中的事务相互组合形成集合，然后提取集合中所有元素，逐一进行循环运算；算法的时间复杂度将取决于对MFCSd进行多次循环运算，何时MFCSd为空，因此这是决定算法执行时间的关键。基于序列模式的事务级最大频繁序列集算法是在基于序列模式的项目级最大频繁序列集算法的基础上的进一步研究，即将以事务为单位的每一项，即取大于或等于最小支持度数s的事务按支持度由小到大的顺序，以类似于基于序列模式的项目级最大频繁序列集算法逐一循环计算的方式挖掘数据库中的数据。接着，本文阐述了挖掘最大频繁项目序列集ISS_DM算法，针对该算法不能有效地解决客户序列视图数据库的数据挖掘问题，结合序列模式提出了改进ISS_DM算法，并进行了相应的验证，结果表明，在进行相同数据量的算法执行时间对比实验中，改进算法执行时间明显优于原算法。最后，针对数据仓库领域的数据挖掘问题，将基于序列模式的项目级最大频繁序列集算法和改进ISS_DM算法分别同数据仓库的多维模型相结合，提出了针对数据仓库多维模型的基于序列模式的项目级最大频繁序列集算法和改进ISS_DM算法。
　　 总之，本文通过对基于FP-tree的最大频繁项目集的DMFIA算法和ISS_DM算法的研究，针对数据库领域的客户序列视图数据库数据挖掘问题及数据仓库领域的多维模型，提出了一系列创新算法。实践表明，算法有较好的实用性、可操作性和创新性，具有较好的理论价值，所设计的算法在挖掘效率和对大型数据库挖掘的可用性方面具有较好的应用前景。

目录

文摘

英文文摘

声明

第一章 绪论

1.1引言

1.2研究背景

1.3创新性工作

1.4本章小节

第二章 数据挖掘技术

2.1数据挖掘技术的产生背景

2.1.1数据挖掘技术的商业需求分析

2.1.2数据挖掘产生的技术背景分析

2.2数据挖掘概念

2.2.1从商业角度看数据挖掘技术

2.2.2数据挖掘的技术含义

2.2.3数据挖掘研究的理论基础

2.3数据挖掘技术的分类问题

2.4数据挖掘常用的知识表示模式与方法

2.4.1广义知识挖掘

2.4.2关联知识挖掘

2.4.3类知识挖掘

2.4.4预测型知识挖掘

2.4.5特异型知识挖掘

2.5不同存储形式下的数据挖掘问题

2.5.1事务数据库中的数据挖掘

2.5.2关系型数据库中的数据挖掘

2.5.3数据仓库中的数据挖掘

2.6本章小节

第三章 序列模式挖掘算法的研究

3.1序列模式

3.1.1序列模式的概念及定义

3.1.2一些相关概念及定义

3.2序列模式挖掘的一些主要算法

3.3应用领域

3.4本章小节

第四章 关联规则DMFIA算法的研究

4.1引言

4.2挖掘最大频繁项目集DMFIA算法

4.2.1频繁项目集和最大频繁项目集

4.2.2 FP-tree频繁模式树

4.2.3基于频繁模式树FP-tree的DMFIA算法

4.3挖掘最大频繁项目(序列)集新算法

4.3.1基于客户数据库的最大频繁项目集算法

4.3.2基于序列模式的项目级最大频繁序列集算法

4.3.3基于序列模式的事务级最大频繁序列集算法

4.3.4时间复杂度

4.4本章小节

第五章 关联规则ISS_DM算法的研究

5.1基本概念与解决方法

5.2对项目集格空间理论的发展

5.3项目序列集格空间和它的操作

5.4基于项目序列集操作的关联规则挖掘算法

5.4.1关联规则挖掘空间定义

5.4.2三个实用算子

5.4.3最大频繁项目序列集的生成算法

5.4.4 ISS-DM算法执行示例

5.5算法分析

5.6实验数据与分析

5.7基于最大频繁项目序列集挖掘ISS_DM算法的改进

5.8本章小节

第六章 基于数据仓库的关联规则算法研究

6.1数据仓库

6.1.1数据仓库的多维数据模型

6.1.2建立多维数据模型

6.2基于数据仓库多维模型改进DMFIA算法

6.3基于数据仓库多维模型改进ISS-DM算法

6.4本章小节

结论

参考文献

致谢

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