论文部分内容阅读
近几年来,不确定性数据广泛出现在传感器网络,Web应用等领域中,对不确定性数据挖掘算法的研究已经成为了数据挖掘领域的新热点。不确定性数据挖掘主要包括聚类、分类、频繁项集挖掘、孤立点检测等方面,其中频繁项集挖掘是重点研究的问题之一。本文首先阐述了不确定性数据的产生原因及表现形式,讨论了不确定性数据挖掘的研究现状,然后对传统数据中频繁项集挖掘的经典算法进行了介绍,重点讨论了不确定性数据中用于频繁项集挖掘的U-Apriori和UF-growth算法,以及不确定性数据流中用于频繁项集挖掘的UF-streaming和SUF-growth算法。其中U-Apriori算法和UF-growth算法分别是对经典算法Apriori和FP-growth的扩展和改进,而UF-streaming算法和SUF-growth算法都是基于树结构的,这几种算法都是不确定性数据挖掘中比较高效的算法。经过研究与分析发现,目前对于不确定性数据频繁项集挖掘算法的研究大都集中在完全频繁项集,而对于最大频繁项集和频繁闭项集挖掘算法的研究尚不多见。本文提出了一种不确定性数据挖掘最大频繁项集的UMF-growth算法,并通过一个实例详细介绍了该算法的工作原理。UMF-growth算法是在UF-growth算法的基础上提出来的,同样只需要对原始数据库扫描两次即可完成最大频繁项集的挖掘,与UF-growth算法不同的是,UMF-growth算法的挖掘过程分为两个步骤：第一步首先获得以每个频繁1-项集为后缀的局部最大频繁项集,第二步将得到的所有局部最大频繁项集按照FP-Tree的构建方式插入到UMF-Tree中,即可获得原始数据库中所有的全局最大频繁项集。为了进一步提高算法的执行效率,随后本文又提出了一种改进策略,即在构建UF-Tree之前先规定项集的有效位数。实验证明,UMF-growth算法性能良好且特别适用于稠密型不确定性数据集,对UMF-growth算法的改进策略可以有效地提高执行效率。