数据的价值和意义在于能够指导实践,而数据价值的发现离不开数据挖掘技术。模式挖掘作为数据挖掘领域基础的且重要的研究分支,在诸多领域都有广泛的应用。随着数据量的不断增加和数据维度的增高,传统模式挖掘方法通常会面临极大的时空开销。演化计算(evolutionary computation,EC)作为一种通用的优化方法,在很多实际应用问题中表现出的性能卓越,对它的研究几乎已经渗透到各个领域。近年来,使用演化计算的相关方法来解决模式挖掘问题逐渐成为一个热门话题。本文研究了更高效率的高效用项集挖掘(high-utility itemset mining,HUIM)方法和更加完备的模式挖掘问题模型及其求解方法。现有基于演化计算的高效用项集(high-utility itemsets,HUIs)挖掘方法,在有限时间内通常只能挖掘到部分满足条件的高效用项集;若能挖掘出全部的高效用项集,往往耗时严重。这一问题会随着最小效用阈值的降低、高效用项集的数量的增多而变得更加突出。为了提高挖掘高效用项集的效率,提出了基于改进二进制粒子群优化算法的高效用项集挖掘方法(HUIM based on an improved binary particle swarm optimization,HUIMIBPSO)。在HUIM-IBPSO算法中,为了提高挖掘高效用项集的效率,提出了包括针对高效用项集的邻域探索策略、重启策略、粒子运动方向调整策略和修复策略在内的多种策略。此外,为了减少对重复粒子的适应度评估,降低算法的整体耗时,HUIM-IBPSO算法中引入了一种适应度值散列技术。为了进一步提高挖掘高效用项集的效率,提出了基于改进遗传算法的高效用项集挖掘方法(HUIM based on an improved genetic algorithm,HUIM-IGA)。在HUIM-IGA算法中,为了维持种群的多样性,从而减少在演化过程中高效用项集的遗漏,算法设计了一种种群多样性维持策略。此外,精英策略在一定程度上防止了在算法的运行过程中高质量解的丢失。在真实数据集上的实验表明,提出的HUIM-IBPSO算法和HUIM-IGA算法无论是在收敛速度、挖掘的高效用项集的数量,还是在算法耗时方面,都优于最新的基于演化计算的高效用项集挖掘方法。为了提高模式挖掘问题模型的完备性,以挖掘在一些实际应用场景中,用户关心的那些出现频繁且完整,同时具有较高效用值的模式,提出了基于支持度、占有度和效用值的三目标模式挖掘问题模型。针对该多目标优化问题模型,提出了一种改进的多目标演化算法(improved multi-objective evolutionary algorithm for highly qualified pattern mining,MOEA-PM),以得到一组最优折衷解。在MOEA-PM算法中,提出了一种新的种群初始化策略,用于保证种群在可行解空间中的有效分布。通过分析问题模型的性质,还提出并使用了一种辅助工具,用来加快算法的收敛速度。在真实数据集上的实验结果表明,提出的三目标问题模型能够发现事务数据集中出现频繁、效用值高,同时相对完整的模式。与目前最新文献上基于多目标进化算法的模式挖掘方法相比,MOEA-PM算法在运行效率、结果质量和收敛速度方面都有较好的表现。
暂无评论