论文部分内容阅读
数据库技术的飞速发展以及各行各业数据量的指数级增长引领着人们步入大数据时代。如何快速而有效的从大量的未处理的数据中获取到人们所需要的信息已经引起了人们的重视。高效用模式挖掘作为数据挖掘领域中一个重要的研究课题,首次被提出主要用于解决频繁模式挖掘的缺陷,即频繁模式挖掘仅仅考虑模式出现的频率,而忽视了其他重要的信息,比如数量和利润,效用模式挖掘正好弥补了这个缺陷。目前已有很多算法被提出用于效用模式挖掘的基础问题。然而,考虑到各种实际因素,在效用模式挖掘的基础问题上延伸出了许多新的研究课题还有待解决,包括非确定性高效用模式挖掘、闭合高效用模式挖掘、增量型高效用模式挖掘以及top-n高效用模式挖掘等等。现有的增量型高效用模式挖掘算法和top-n高效用模式挖掘算法或者基于一个两阶段的模型,产生了大量的候选集、造成了规模性问题,或者基于一个垂直数据结构、产生了大量的连接操作、导致效率低下。为了解决上述问题,本文基于现有的d2HUP算法,使用了一种新的数据结构和多个新的剪枝策略,分别提出了两个新算法来解决增量型效用挖掘和top-n效用挖掘问题。本文首先对现有的高效用模式挖掘算法做一个综述性的分析及对比,主要表现在运行时间、内存使用、候选集数量以及规模性方面,并得出d2HUP算法是目前已知的最优的算法,尤其是在运行时间方面相比于其他的算法有1到2个数量级的提升,该算法作为后续增量型效用模式挖掘和top-n效用模式挖掘研究的基础算法。HUPTID算法是在d2HUP算法基础上提出的主要用于在数据库交易项记录增加和删除的情况下直接的挖掘出所有的高效用模式。首先,一个新的数据结构被提出用于增量型效用模式挖掘。第二,三个策略被提出用于各种可能的改变情况下减少不必要的挖掘操作,同时,对挖掘过程中可能出现的三种情况分别提出了相应的策略来进行剪枝。在实验部分,三种情况分别被分析,即交易项记录既有插入也有删除,交易项记录只有插入、以及交易项记录只有删除。结果表明HUPTID算法比目前已知的增量型效用模式挖掘算法效率高出了 1到2个数量级。TONUP算法也是在d2HUP算法基础上提出的主要用于解决top-n高效用模式挖掘问题。该算法首先对d2HUP算法本身进行了优化,然后提出了5个策略来尽可能快的提高阈值,并最终得到最优的阂值以及所需要的n个模式。实验表明,TONUP比目前已知的top-n高效用模式挖掘算法效率高到了 1到3个数量级,甚至优于在最优的阈值条件下执行的效用模式挖掘算法,效率高出了 2个数量级。