论文部分内容阅读
随着数据流的不断发展和应用,在数据流环境下的数据挖掘已经成为获取信息的主要方式,尤其是最大频繁模式的挖掘已成为当今的研究热点,它能提供决策支持和商业预测,因此在实际中有很大应用价值。最小项目支持度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在运行时间和空间占用大小等性能上的优越性。