Top-rank-k频繁模式挖掘算法优化及其并行化研究

作     者：龙玉航 

作者单位：湖南师范大学 

学位级别：硕士

导师姓名：唐文胜

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：大数据 并行化 Spark top-rank-k频繁模式 混合搜索 

摘      要：数据挖掘（Data Mining）是当前数据库和信息决策领域的前沿研究方向之一,top-rank-k频繁模式挖掘是数据挖掘中挖掘rank不大于k的频繁模式的方法,可以解决传统频繁模式挖掘支持度阈值设置困难的问题。但主流的top-rank-k频繁模式挖掘算法效率有待提高,且这类算法普遍基于串行设计,难于突破单机硬件资源限制,无力应对“大数据时代的海量数据挖掘任务,因此关于top-rank-k频繁模式挖掘算法优化及其并行化研究具有重要意义。本文的主要工作如下:（1）针对当前top-rank-k频繁模式挖掘时空耗费大的问题,提出了一种基于混合搜索的top-rank-k频繁模式挖掘算法HTK（Hybrid-search-based Algorithm of Top-rank-k Frequent Patterns）,其主要思想是:定义名为RSL（Static Doubly-linked List of Top-rank-k）的静态双链表存储top-rank-k频繁模式,采用1-模式的支持度及其在事务中后缀项的基数设计了模式区分方法,把模式区分为短模式和长模式。挖掘过程中,首先利用基于贪心策略的rank-first-search方法挖掘频繁短模式,始终连接RSL中尚未连接的rank最高的模式,使具有高rank的频繁模式优先产生;然后,利用长度最长的短模式,通过逐级搜索挖掘频繁长模式。此外,算法还设计了合理的剪枝策略,优化了包含索引的生成方式,使挖掘工作面对稀疏或稠密数据集同样有效。（2）为了应对海量数据的挖掘任务,提出了一种基于Spark的top-rank-k频繁模式并行挖掘算法STK（Spark-based Mining Algorithm of Top-rank-k Frequent Patterns）,其基本思想是:首先,引入分治思想,对项进行编组分发至各节点,并将事务根据各节点所属的项切割划分;然后各节点执行HTK算法,挖掘前缀项为该节点所属项的top-rank-k频繁模式;最后聚合各节点挖掘结果,输出目标模式。为实现负载均衡,STK还依据数据特性设计了负载均衡策略和数据划分方法。利用真实数据集与合成数据集,分别对提出的HTK和STK算法进行了实验验证,结果表明:HTK算法比现有单机算法具有更好的时空效率;STK算法能够有效挖掘大数据环境下的top-rank-k频繁模式。