论文部分内容阅读
模式挖掘是数据挖掘技术中的一个重要的研究方向。对于传统的频繁模式挖掘和高效用模式挖掘,它们只能分别用来挖掘频繁模式和高效用模式。在许多实际应用场景下,这些传统的单纯的频繁模式挖掘和效用模式挖掘模型的范畴会比较狭窄,不能满足实际应用中的多样化分析需求,人们往往对频繁度和效用值都感兴趣,不单单只是频繁度或者效用值。为了解决这个问题,本文提出同时考虑支持度和效用值,进而挖掘更有价值的模式,其中一种就是高频繁度低效用模式,并提出了一个新颖的算法 HFLUP(High Frequency and Low Utility Patterns Mining Algorithm)。挖掘高频繁度低效用模式的最简单直接的方法就是分为两阶段来挖掘,首先利用频繁模式挖掘算法来挖掘出所有的高频繁度模式,然后再从这些高频繁度模式中找出效用值低于用户指定的最大效用阈值的模式,即最终得到高频繁度低效用模式。但是这种两阶段的挖掘方式会产生大量的候选集,且需多次遍历数据库,磁盘I/0开销大,挖掘效率低。因此,为了避免这些问题,本文提出的高频繁度低效用模式挖掘算法HFLUP是一个不产生候选集的单阶段算法,并且只需要遍历数据库两次。本文还提出了一个新的数据结构,叫做FUL,用来存储模式的效用信息以及裁剪搜索空间的信息,通过FULs,算法可以高效地直接挖掘出高频繁度低效用模式且无需产生候选模式。为了减小搜索空间,提高挖掘效率,提出了有效的且规模可控的效用下界裁剪策略以及通过lookahead策略预先确定高频繁度低效用模式而无需递归枚举。大量实验表明:所提出的两个裁剪策略是有效且高效的,HFLUP算法在运行时间和内存消耗上大大优于两阶段的高频繁度低效用模式挖掘方法。本文的第二项工作是将所提出的算法并行化,以适应海量大数据处理的要求,以克服单机的物理内存局限所造成单机挖掘的低效率。本文采用云计算模式下的基于内存的分布式计算框架Spark来实现算法的并行化,提出了基于Spark的并行高频繁度低效用模式挖掘算法PHFLUPS(Parallel High Frequency and Low Utility Patterns Mining Algorithm Based on Spark),以便利用大规模分布式集群来并行挖掘大数据。对比实验表明,PHFLUPS算法比基于MapReduce的并行高频繁度低效用模式挖掘算法效率更高,并且在大规模数据集上并行化算法要比单机HFLUP算法效率高。本文的思路和所提出的相关技术同样适用于挖掘其他类型的模式,比如低频繁度高效用模式。