高频繁度低效用模式挖掘算法及其在云计算下的实现研究

发布时间：2020-05-19 21:02

【摘要】：模式挖掘是数据挖掘技术中的一个重要的研究方向。对于传统的频繁模式挖掘和高效用模式挖掘,它们只能分别用来挖掘频繁模式和高效用模式。在许多实际应用场景下,这些传统的单纯的频繁模式挖掘和效用模式挖掘模型的范畴会比较狭窄,不能满足实际应用中的多样化分析需求,人们往往对频繁度和效用值都感兴趣,不单单只是频繁度或者效用值。为了解决这个问题,本文提出同时考虑支持度和效用值,进而挖掘更有价值的模式,其中一种就是高频繁度低效用模式,并提出了一个新颖的算法 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算法效率高。本文的思路和所提出的相关技术同样适用于挖掘其他类型的模式,比如低频繁度高效用模式。
【图文】：

分区所,节点,流水线,策略

一个父ＲＤＤ的分区被多个子ＲＤＤ分区所使用。比方，ｆｉｌｔｅｒ操作是窄依赖，逡逑ｒｅｄｕｃｅＢｙＫｅｙ操作是宽依赖，而当父ＲＤＤ不是基于Ｈａｓｈ策略分区的时候，ｊｏｉｎ操作逡逑也是宽依赖。图４－２表示一些常见的窄依赖和宽依赖。图中的每个圆角矩形表示一个逡逑ＲＤＤ，内部每个实体矩形表示ＲＤＤ的一个分区。逡逑逦ｆｒ＝ｆｉ逡逑ｊ逡逑ｍａ邋ｐ，ｆｉｌｔｅｒ逦ｇｒｏｕ邋ｐＢｙ邋Ｋｅｙ／ｒｅｄｕ邋ｃｅＢｙ邋Ｋｅｙ逡逑—－ａ逡逑—逦—Ｅｍｕｉｒ逡逑、逦＾邋ｕｎｉｏｎ逦ｊ0ｉｎ逡逑窄依赖逡逑图４－２常见的窄依赖和宽依赖逡逑窄依赖和宽依赖的的区别主要有两个方面。首先，窄依赖可以在集群中的一个节逡逑点上以流水线的方式执行多个转换操作，这个节点可以单独地计算出ＲＤＤ的一个分逡逑区，无需依赖其它的节点。比如，依次执行ｍａｐ和ｕｎｉｏｎ操作，这两个操作都是窄依逡逑１８逡逑

数据集中,阈值,数据集,运行时间

（ａ）邋Ｐｕｍｓｂ逦（ｂ）邋Ｃｏｎｎｅｃｔ逡逑图７－２邋ＨＦＬＵＰＢａｓｅ、ＨＦＬＵＰＢａｓｅＡｎｄＬＢｕ在不同数据集中的运行时间对比逡逑图７－１表示ＨＦＬＵＰＢａｓｅ、ＨＦＬＵＰ—ｌｂｕ在不同数据集中构造ＦＵＬ的次数，图逡逑７－２表示ＨＦＬＵＰＢａｓｅ、ＨＦＬＵＰＢａｓｅＡｎｄＬＢＵ在不同数据集中的运行时间。逡逑在图７－１和图７－２中，对于Ｐｕｍｓｂ数据集设置的最大效用阈值为０．９５５％，对于逡逑Ｃｏｎｎｅｃｔ数据集设置的最大效用阈值为１．８４３％。从图７－１邋（ａ）的Ｐｕｍｓｂ数据集中，可逡逑以发现当最小支持度阈值ＯＴ＞ｍ／ｐ；７邋＝邋７５％时，ＨＦＬＵＰＢａｓｅＡｎｄＬＢＵ构造ＦＵＬ的次数为逡逑１１５０６８
【学位授予单位】：浙江工商大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【相似文献】