基于加权多重最小支持度的挖掘算法研究

摘要

随着数据流的不断发展和应用,在数据流环境下的数据挖掘已经成为获取信息的主要方式,尤其是最大频繁模式的挖掘已成为当今的研究热点,它能提供决策支持和商业预测,因此在实际中有很大应用价值。
　　最小项目支持度MIS(Minimum Item Support)是对数据流中的每个数据项,设置关键属性的支持度,以便对数据项进行修剪后的挖掘;而最大频繁模式MFPs(Maximal Frequent Patterns)是在MIS的基础上挖掘最大频繁模式。现有的最大频繁模式 MFPs虽然具有较高的压缩比,但只是考虑了支持度的挖掘条件,而没有区分每个频繁模式的权重,无法反应实际属性信息。因此对 MFPs算法进一步扩充和完善是十分有意义的。在分析和总结MFPs的算法优缺点的基础上,本文进一步做了以下的研究工作:
　　1.现有MFPs算法对频繁模式的挖掘过程中,会产生大量的中间集,耗费了大量的时间和空间,并且没有考虑到多重支持度的挖掘条件。针对上述问题,本文构造了数据存储结构CPLMS-tree(Compact Preorder Linked Multiple Supports tree),并提出了能够满足多重最小支持度的频繁模式挖掘算法MSCP-growth(Multiple Support-Conditional Pattern growth):通过数据结构中构建的属性 iflag来表示子序列是否为频繁项,mps来表示最小的MIS值,并将上述两个属性值作为修剪条件,通过对存储的频繁数据项设置不同的支持度来挖掘频繁模式,可以较大减少频繁模式候选集产生的数量,快速地获得有价值的频繁模式。最后通过实验将所提算法与传统算法PLWAP-Mine进行比较,验证了MSCP-growth算法在执行时间、频繁模式候选集和频繁模式产生的数量,以及空间占用大小等性能上优于PLWAP-Mine算法。
　　2.在数据流环境下,现有的加权最大频繁模式 WMFPs(Weighted Maximal Frequent Patterns)算法,对频繁模式的挖掘需要多次数据库扫描,并且没有充分利用加权因子与最小支持度相结合的优势,产生大量的无价值最大频繁模式候选集,针对上述问题,构造了一个新的数据存储结构MWS-tree(Maximal Weight Streams tree),通过利用最大加权值MW(Maximal Weight)为修剪条件,较大地减少了最大频繁模式的搜索范围;同时构建包含支持度索引信息的数组WMFP-array(Weighted Maximal Frequent Patterns array),通过此数组的支持度索引信息来减少对数据库扫描的次数,并以单一路径与数据项加权支持度相结合,减少遍历树结构的次数。
　　3.在 MWS-tree基础上,提出了最大加权数据流算法 MWS(Maximal Weight Streams),算法利用数据项的权重信息WI(Weight information)和最小支持度阀值δ进行最大频繁模式的挖掘,并对挖出的频繁模式进行子集检查操作,将最后结果存储于最大频繁模式数据结构 WMFP-tree(Weighted Maximal Frequent Patterns tree)中,最大限度地减少了不必要的挖掘操作。最后将算法MWS与传统算法IWFP以及其改进算法IWFP*进行对比,验证了算法MWS在运行时间和空间占用大小等性能上的优越性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 研究内容

1.4 组织结构

第二章 频繁模式挖掘算法的相关理论知识

2.1 基本概念

2.2 相关技术

2.3 MFPs相关算法

2.4 小结

第三章 多重最小支持度的挖掘算法

3.1 引言

3.2 基本定义

3.3 CPLMS-tree构造

3.4 MSCP-growth挖掘算法

3.5 实验结果及分析

3.6 小结

第四章 加权最大频繁模式挖掘算法

4.1 相关理论

4.2 MWS-tree构造

4.3 MWS算法

4.4仿真实验

4.5小结

第五章 总结与展望

5.1 工作总结

5.2 存在问题

5.3 未来研究方向

参考文献

致谢

攻读学位期间参加的科研项目

攻读学位期间发表论文