论文部分内容阅读
数据挖掘是一个重要的研究领域，这个研究领域是在数据库中发现模式的计算过程。数据挖掘过程的总体目标是从数据中提取有用的信息和知识，并将其转换为一种可以理解的结构进行进一步的使用。在数据挖掘中一个基本的任务是频繁项集挖掘(FIM)。频繁项集挖掘包括发现在事务数据库中频繁的一起出现的项集。有许多被开发出来的算法能有效地发现频繁项集。但是为解决这个问题的这些算法存在着一些主要的缺陷。他们认为所有项有相同的重要性（如单位利润或重量）而且不考虑项的数量，通常这些假设在真实的应用中并不成立。 为了解决这个问题，发现高效用项集(HUIs)的任务具有的效用不低于用户指定的最小效用阈值已成为一个主要的研究问题。高效用项集是一个重要的数据挖掘任务。然而对于用户来说指定最小效用阈值并不是一项容易的任务。用户通常不知道什么样的阈值是最合适他们的需求而且他们也不能预测这个项集数量。选择一个合适的阈值直接影响发现高效用项集的数量，因此它也直接影响算法的效率和有效性。为了解决这个问题，top-k高效用项集挖掘任务被提出。 在top-k高效用项集挖掘中，用户必须指定一个用于指示项集数量的参数k而不是指定一个最小效用阈值。top-k高效用项集挖掘是在事务数据库中具有最高效用的发现k项集的过程。近年来，针对这一任务已经提出了一些算法。在这些算法中，结果项集的数量由用户控制，返回的结果没有被用户用于数据分析。然而，即使这样它仍然占用了昂贵的运行时间和内存消耗。这个是因为目前的算法往往产生大量的候选项集但却无法有效地修剪搜索空间。在本文中，为了解决这个问题，提出了一个叫做KHMC的新颖算法，它能更有效的发现top-k高效用项集。与其他几个top-k高效用项集挖掘算法不同的是KHMC利用一个单一的阶段去搜寻发现高效用项集。此外，该算法海采用了RIU，CUD，和COV三种策略来更有效的提高其内部最小效用阈值，从而减小了搜索空间。这个COV策略引入了一个新颖的覆盖的概念。在本文中提出的这个覆盖的概念可以在高效用项集挖掘中用来修剪搜索空间，或者在top-k高效用项集挖掘中提高阈值。此外，为计算项集效用KHMC依靠一个叫做EUCPT的新颖同现修剪技术可以避免执行耗资源的链接操作。另外还提出一个叫做TEP的新颖修剪策略用来减少搜索空间。 为了评估本文提出的算法的性能，在六个具有不同特点的数据集上进行了大量的实验。结果表明在做top-k高效用项集挖掘中该算法消耗的内存和运行时间比最先进的TKO和REPT算法更优。