基于多目标进化算法的任务驱动模式挖掘研究

发布时间：2018-11-04 18:58

【摘要】：多目标优化问题是一类常见于各种科研以及工程应用中的问题,与经典单目标最优化问题不同,多目标问题中涉及到的各个目标相互之间存在着一定的冲突关系。目前在多目标领域存在很多不同类型的算法来解决该问题,而这其中,进化算法由于具有良好并行性、全局搜索以及对任何函数类可用等特性,在解决多目标优化问题上体现出了良好的性能,因此,多目标进化算法成为解决多目标优化问题的一个主流方法,并引起学者们的广泛关注。任务驱动的模式挖掘作为频繁模式挖掘领域的一个分支,由于其广阔的应用场景,例如商品组合推荐、网页打印区域推荐等等,已经越来越多地引起人们的关注。在这些任务驱动的应用中,推荐给用户的模式作为一个完整的任务并且该任务有许多子任务组成,因此这些模式称之为任务驱动模式。考虑到任务驱动模式中往往是一系列相互关联的子任务,因此子任务间的相关性较高,在挖掘过程中就需要考虑挖掘模式的完整性,以免影响用户的体验。传统任务驱动的模式挖掘算法采用对事务数据库(Transaction Database)的字典子集树进行深度优先遍历搜索的方式,在搜索的过程中利用剪枝的策略提高运行效率。然而基于字典子集树遍历的传统方法难以在实际应用中开展,因为算法需要根据具体问题的先验知识设置参数,例如:搜索时最小的支持度阈值min_sup,最小的占有度阈值min_occ以及支持度与占有度之间的一个偏好权值λ等,而且不同的参数对算法的结果影响很大,另外算法的效率也不尽人意。基于以上问题,本文对任务驱动模式挖掘问题进行了探索与研究,考虑从多目标优化的角度解决任务驱动模式挖掘问题,具体研究工作分为如下两部分:(1)本文从多目标优化的角度出发解决任务驱动模式挖掘问题,并提出了一种有效的多目标模式挖掘算法。在任务驱动模式挖掘领域中,传统算法需要用户设置一些必要的先验参数。而这些参数往往对传统算法有较大的影响,不同的参数使得算法的运行时间以及运行效果差别很大。因此,为了获得较好的性能,传统算法需要用户预先设置合适的参数。但在实际应用中,用户在缺乏具体问题先验知识的情况下难以选择出合适的参数,而且对于不同的问题其合适的参数也会大不相同。为了寻找合适的参数,用户需要尝试不同参数进行多次实验以寻找最佳效果,这样使得算法的运行代价昂贵,效率低下,最终难以在实际应用中展开。基于此,本文考虑多目标进化算法不需要根据具体问题设置先验参数这一良好特性,将任务驱动模式挖掘问题转化为一个3目标(支持度,占有度以及覆盖度)的多目标优化问题来处理。在经典多目标进化算法NSGA-II的基础上,本文提出了一种有效的多目标模式挖掘算法,简称MOPM。最后通过在真实数据集Smart Print数据集、Taobao数据集以及合成数据集IBM数据集上分别进行实验,结果表明,MOPM算法不需要根据具体问题设置先验参数,解决了传统算法中参数敏感性的问题,而且MOPM算法在实验效果以及运行效率上都较传统算法有一定的优势。因此,从多目标优化的角度来解决任务驱动模式挖掘问题是一种行之有效的方式。(2)本文提出了一种基于代理模型的多目标模式挖掘算法。从第一个研究工作中可以发现,用多目标优化的视角来解决任务驱动模式挖掘问题能够有效解决传统算法遇到的参数敏感性等挑战,促进了算法在实际中的应用。然而随着事务数据库规模的增大,MOPM算法在运行时效率会受到很大的影响。通过分析,发现由于进化算法在计算个体的3个目标值时都需要对事务数据库的全部数据进行遍历,因此真实评价个体的目标值代价昂贵。基于此,本文提出了一种基于代理模型的多目标模式挖掘算法,简称SA-MOPM,用以提高算法的运行效率。SA-MOPM算法采用改进的基于K-Prototype聚类算法的径向基函数网络模型作为代理模型,使径向基函数网络模型可以应用到离散的任务驱动模式挖掘问题上。在进化过程中利用代理模型对个体进行评估,因此可以大大降低适应度评估的代价。最后,本文在真实数据集Smart Print数据集、Taobao数据集以及合成数据集IBM数据集上分别进行实验,结果显示,在精度降低有限范围内,SA-MOPM算法的运行效率比MOPM算法有着更大的优势。因此,基于代理模型的多目标模式挖掘算法是解决大规模数据集上任务驱动模式挖掘问题的有效方法。
[Abstract]:......
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】