论文部分内容阅读
互联网与大数据时代的到来,各行各业的数据都呈现爆炸式的增长,对现有的存储方案以及数据挖掘带来重大的挑战。数据挖掘技术不仅能够有效地处理已有的数据,而且能够从海量的数据中挖掘出有价值的信息,从而为实际的生产、运营和发展提供正确的导向作用。频繁项集挖掘(Frequent Itemset Mining,FIM)是数据挖掘的一个基础方法,常被用来挖掘各个事物之间的联系。FIM仅考虑事物出现的次数,没有考虑其本身的价值,因而有学者提出了高效用项集挖掘(High-Utility Itemset Mining,HUIM)的方法。HUIM综合考虑事物本身的价值和频率两个因素,相比FIM拥有更实际的导向作用。HUIM的目的是在给定的数据集中挖掘出所有高于阈值的项集。针对现有的HUIM算法存在的执行时间长、占用内存高等问题,本文提出了基于改进数据集的高效用数据挖掘算法(Efficienthigh-utility itemset mining based on a novel data structure,EIM-DS)。为了进一步提升EIM-DS算法的执行效率,提出了基于多线程的EIM-DS算法。针对数据集过大而导致的单机无法在有限的时间内挖掘的问题,提出了基于分布式并行的HUIM算法。本文的主要工作如下:(1)提出了基于改进数据集的高效用数据挖掘算法来解决传统的高效用数据挖掘算法存在的耗时高、内存大的问题。首先,通过引入新的数据集结构来重构数据集,提高数据集的利用率;其次,提出了循环事务加权效用值(Transaction weighted utilization,TWU)剪枝的策略,来减少项集的长度;然后提出了构造树的概念来缩小搜索空间,使用压缩存储的方式来减少构造树的存储空间;最后,在搜索过程中提出了两种新的剪枝策略,即拓展集剪枝和局部TWU剪枝;同时提出了一种快速计算的方法来计算这两种上限,进一步缩小搜索空间和提高算法的执行效率。与现有的HUIM算法相比,EIM-DS算法在执行时间和内存两方面均有较好的表现。(2)由于EIM-DS算法中,提出的改进数据集和压缩存储后的数据有着只读不写的特性,可以被多个线程同时使用,本文因此提出了基于多线程的EIM-DS算法(T-EIM-DS)以进一步提升算法的效率。T-EIM-DS算法相比于单线程版本,执行时间随着线程数的增多而递减,内存增长小于其线程数。(3)依托Hadoop平台易部署、低开销和高伸缩性等特性,提出了一种分布式并行框架,使用EIM-DS算法和EFIM算法作为并行的算法,提出了两种分布式高效用项集挖掘算法:P-EFIM(Parallel EFficient high-utility Itemset Mining)算法和P-EIM-DS算法。首先,计算项集的TWU值并排序,根据排序后的项集序列对数据集进行重新编号和去除低效用项,以提高数据集的利用率。Map阶段将整个任务分解成多个独立的子任务,为了确保每个节点的负载均衡,提出了S型的分配策略将多个子任务均匀地分配到各个节点。在Reduce阶段,P-EFIM算法和P-EIM-DS算法分别采用EFIM算法和EIM-DS算法对子任务进行高效用项集挖掘。与同样采用MapReduce框架的PHUI-Growth算法相比,P-EFIM算法和P-EIM-DS算法在时间性能上有着明显的提升。本文提出了HUIM算法的改进算法,通过多线程的方式,进一步降低了算法的执行时间,引入了分布式计算,解决了大规模数据集难以挖掘的问题,拓宽了高效用项集挖掘领域的研究范围。