论文部分内容阅读
模式挖掘是数据挖掘中最重要的领域,高效用项集挖掘是模式挖掘中的研究热点之一。由于演化计算能够避免高效用项集搜索空间组合爆炸式增长,近几年基于演化计算的高效用项集挖掘算法越来越受到关注。学者们提出了基于遗传算法(Genetic Algorithm,GA)、粒子群算法(Particle Swarm Optimization,PSO)、蝙蝠算法(Bat Algorithm,BA)等演化计算的高效用项集挖掘算法。这些方法通常通过迭代的改变编码向量产生新的候选项集。与GA、PSO、BA算法不同,我们提出了一个基于蚁群算法的高效用项集挖掘算法(HUIM-ACO),这种算法构造性地产生候选项集。在HUIM-ACO算法中,我们使用搜索路径来表达候选项集。最初我们将每个搜索路径按照概率进行初始化,每一步增加一个项目。同时我们提出了信息素矩阵,用于存储两个不同项目的信息素值,允许局部更新和全局更新,而且设计的蚂蚁路径能够有效计算高效用项集。与基于GA和PSO的高效用项集挖掘算法相比,HUIM-ACO算法能够在更短的时间内挖掘出更多的高效用项集。为了进一步提升HUIM-ACO算法的性能,在HUIM-ACO算法的基础上提出了基于Map Reduce的高效用模式挖掘算法(HUIM-ACO-MR)。该算法基于Map Reduce分布式计算框架,可以很好地解决在数据量过大时单机算法的性能瓶颈。为了保证数据的一致性并减少数据网络传输开销,我们提出了一种计算块最小效用值模型:首先通过块最小效用值筛选出每个数据块中的潜在高效用项集,最后从潜在高效用项集中计算出真正的高效用项集。HUIM-ACO-MR算法的缺点是在运行时需要反复的读写磁盘,从而影响了算法的性能,Spark具有优秀的内存计算能力,可以弥补此项的不足,因此我们设计实现了基于Spark的高效用模式挖掘算法(HUIM-ACO-S),HUIM-ACO-S算法与HUIM-ACO-MR算法一样,运用了块最小效用值策略,将蚁群算法分发到每个RDD上进行挖掘,最后从挖掘的结果集中筛选出高效用项集。