论文部分内容阅读
数据挖掘(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频繁模式。