论文部分内容阅读
频繁模式挖掘的目的是从数据集中挖掘出有价值的模式,为利益相关方提供决策依据,其中在不确定数据集中的频繁模式挖掘是目前研究的热点。近些年,随着数据量的剧增,单机计算环境很难满足大数据的计算需求,因此借助于分布式计算平台来保证数据处理的效率是一种常用手段。传统的不确定数据集频繁模式挖掘算法大多以期望、概率或者权重等单一指标为数据项的支持度,难以挖掘出更有价值的频繁模式。针对以上问题,本文采用集群计算框架,兼顾数据项的概率与权重,提出了基于Spark的UWEFP算法和FPEWU算法,用UCI公共数据集对两种算法进行实验验证,实验结果表明所提方法合理可行,在保证结果的同时提高了效率。具体研究内容如下:(1)提出了数据项最大权重概率值的概念并应用于新颖的剪枝策略中。剪枝策略利用数据项最大权重概率值对一项集进行剪枝,从而挖掘出可同时兼顾数据项概率和权重的频繁模式。(2)设计了一种具有FP-tree结构特征的UWEFP-tree,通过UWEFP-tree进行模式树的构建及频繁模式的挖掘。(3)提出了基于Spark的不确定数据集频繁模式挖掘算法UWEFP,结合Spark的优点,按事务分组,在各组中分别进行模式树的构建,挖掘出符合条件的初始频繁模式,再将初始频繁模式的支持度与用户定义的最小支持度作对比,挖掘出可同时兼顾数据项概率和权重的频繁模式。实验结果表明,UWEFP相对于其他传统的算法,可以快速有效的挖掘出频繁模式。(4)为了降低UWEFP-tree在建树过程中的空间复杂度,设计了频繁模式树FPEWU-tree,通过FPEWU-tree进行模式树的构建及频繁模式的挖掘。(5)为了降低UWEFP算法的空间复杂度,设计了FPEWU算法。区别在于,UWEFP算法以事务分组,FPEWU算法以数据项分组。FPEWU算法在各组中分别进行模式树的构建并挖掘出同时兼顾数据项概率和权重的频繁模式。实验结果表明,FPEWU相对于其他传统的算法,可以快速有效的挖掘出频繁模式。针对稀疏数据集,UWEFP算法执行效率优于FPEWU算法;针对稠密数据集,PEWU算法的执行效率优于UWEFP算法。