频繁项集挖掘一直是数据挖掘领域中的一个重要研究课题。在数据库中挖掘频繁模式以便于更好的了解数据,并为决策提供支持。频繁项集挖掘的对象是客户交易数据库,每个交易是由客户产生的一组项的集合。如果一个项集的支持度(出现的事务数)不小于预定义的最小阈值,则此项集就被称为频繁项集。频繁项集挖掘的任务是枚举出交易数据库中的所有频繁项集。频繁项集挖掘可以应用于很多领域,且已经研究发展了二十多年。目前已经有几种成熟算法用高效挖掘频繁项集和发现其他类型的模式,如顺序模式和频繁子图模式。当下最流行的一些频繁项集挖掘算法包括Apriori,Eclat和FP-growth算法等。尽管频繁项集挖掘具有很强的功能,但却有一些严重的局限性。其中一个主要的问题是,频繁项集挖掘算法找到的模式数量的数目依赖最小阈值。如果最小阈值设置得太高,则不能找到那些比较重要的模式。但如果阈值设置得太低,则将会挖掘出数百万个模式,同时算法的运行时间将大量增加,并且消耗大量的内存。要设置合适的最小阈值,用户通常必须运行多次算法,需要尝试不同的阈值来找到足够的模式。太多的模式对于用户来说也是一个问题,因为需要花费时间进一步分析结果。一些研究表明传统的频繁项集挖掘算法会挖掘出许多频繁但并不重要的模式,因为它们的支持度(频率)可以由其子集的支持度表示出来。换句话说,一个模式内部的某些项集如果是频繁的,那么即使这些项集之间不相关,这个模式也会是一个频繁模式。因此,用户可能需要查看很多没有意义的频繁项集,最后只能找到少数一些有用的频繁项集。为了解决这个问题,一个新兴的研究课题是从统计学的角度来挖掘真正具有强相关性的项集,即对一个项集做任意的分割将其分为两个部分,这两个部分都具有强相关性。具有这种性质的项集称之为效能项集(Productive Itemset)。由于在研究中,是通过费舍尔精确检验来判别两个事物是否具有统计显著性来判断相关性,故这一种挖掘模式又可以称为统计显著性模式挖掘(Significant Pattern Mining。一些研究为了让结果更有意义,在提出项集在满足有效能的基础上,加上了非冗余的限定条件。非冗余项集是指,一个项集X不包含具有相同支持度的真子集。通过使用统计检验的方法来查找具有统计显著性的模式。其中最流行的算法就是OPUS-Miner。这个算法是一个经典的top-k算法,在数据集上寻找最大k个指定随着支持度单调变化的度量(Lift、Support、Cover或其他指标)的效能且非冗余的项集。OPUS-Miner是用反向枚举树来定义搜索空间,利用上述度量进行分支定界剪枝,减少算法运行消耗的时间。尽管这种算法可以发现许多有意义的模式,减少了大量无关联的结果,但非常依赖于度量的选取与k的选取。一个支持度偏低但是依然具有很强关联性的项集在k值很小的情况下就会被忽略。但如果k值选取的太大,OPUS-Miner的剪枝策略无法发挥效果,算法会蜕化为遍历所有可能的项集。因此,本篇研究其中一点是以用户给定的项集作为基础,构建一个查询-应答的模式来。用户提出自己感兴趣的项集或项集范围构成查询集。然后由算法给出查询集的支持度,冗余性,是否是有效能的项集一些相关信息。OPUS-Miner的第二个局限性在于其中它只支持静态数据库,当数据发生变化的时候,它必须要重新载入数据,无法在数据本身的存储结构进行改变。本论文通过定义在动态数据库中发现目标非冗余生产项目集的新问题来解决这些问题。提议的方法IDPI+(交互式发现效能项集)将事务存储在项集树结构中,然后可以支持交互查询,以识别包含特定项目的效能性和非冗余项目集。为了有效地同时处理多个查询,提出了一种新的数据结构——查询树。此外,为了处理动态数据库,还提供了高效的事务插入和删除算法来更新用来存储数据集的内存效用项集树。为了更有效地处理查询,本论文提出了IDPI+方法。它由四个部分组成:第一部分,一种改进版的项集树结构用来压缩数据库,称为内存效用项集树(MEIT)。首先,为了解决传统模式挖掘算法的局限性,一种名为项集树的高效数据结构被提出,它允许对数据库中的模式进行有针对性的查询。目标查询的目的是寻找包含数据库中某些特定项目的模式。它们让用户过滤了许多不感兴趣的模式,其中包含了很多无关的项集。项集树结构在静态或增量数据库中都有效地应答了关于项目集和关联规则的查询。而本论文提出的内存效用项集树是为交互式频繁项集挖掘而设计的,不但支持对数据库进行增加,也允许用户删除一些已经失去时效的数据,用以支持动态数据库。另外,内存效用项集树与项集树之间的另一项区别在于,在内存效用项集树节点中,来自父节点的项不会被存储。第二部分,一种名为查询树的新结构,用于计算有关项目集的支持度。IDPI+算法的第二个数据结构是一种名为查询树(QT)的新结构。它的设计目的是提高支持度计算并提高内存效用项集树的查询性能,通过用户定义的一个查询来检查项集X是否具有效用性和非冗余性。要确定这个性质,需要计算项集X所有非空子集的支持度。使用传统的方法来计算支持度,需要为每个项目集执行一个支持计数度的查询,这需要多次遍历项集树,显而易见这种算法很耗费时间。本论文提出了一个更好的算法是在查询树中存储X及其所有子集。然后,该结构通过使用新的查询处理算法来快速计算所有这些项目集的支持。另外,当用户给出大量查询的情况下,这些查询在一定程度上会有着相同的子集,而这些子集在查询树上对应的是同一个节点。故使用查询树这一结构,比执行多次单个查询的效率更高。第三部分,通过比较上述两种结构,获得查询树上所有节点代表项集的支持度。为了确定查询的项集是否有效用和非冗余的特性(需要查询的所有子集的支持度),在构建查询树之后,下一步是利用查询树与内存效用项集树比较来获得查询的项集及其子集的支持度,通过调用算法来计算支持度,然后将其信息存入查询树节点中。这部分也是这个系统的核心部分,我们解决了通过查询树如何高效的遍历数据集的问题,我们仅仅需要遍历一次数据集就可以得到查询树上的所有项集的支持度,算法明确定义了查询树节点与内存效用项集树节点的5种对比关系,让算法进行高效的搜索。第四部分,最后得到了一个拥有所有子集支持度的查询树。而这个查询树本质上等同于OPUS-Miner的反向枚举树的搜索空间,也就是说,算法的搜索空间并不是通过剪枝策略来得到的,而是通过用户给定的范围来拓展的。在OPUS-Miner中获取支持度主要是靠项的记录集做交集来得到的,算法最后得到的搜索空间上带有每个项集的支持度。通过查询树的结构进行深度优先搜索,将已经搜索过的节点所代表的项集的支持度记录下来,然后对每个正在搜索的节点进行费舍尔精确检验获得p值,判断项集的效能性与冗余性。本文从内存效用树的更新速度,查询树的构建与查询集的分布,以及运用查询树算法的运行时间等分别进行了实验。其中在运用查询树与分别查询的比对实验中,为每个数据集生成随机查询,数量从500到5000不等,项集的长度从2到10不等。然后在每组随机查询中应用IDPI+和标准方法进行对比,可以观察到,绝大部分所有情况下,IDPI+的速度都更快,除了在项集长度在8到10之间。原因是在这种情况下,查询树变得非常大,一个10-项集子集数量有1024个,构建这种查询树非常耗时。然而查询树一旦建立,只要查询集不变,可以反复用在不同的数据集上,当查询固定而数据集发生变化的时候,无需反复构建查询树。另一种情况,项集长度过高也不太可能是有用的项集(因为任意两个分区必须是正相关),并且长项集在实践中很少有用,因为它们通常代表了非常极端的情况。通常,处理查询的速度会受到查询集的影响,它们是否共享子集,以及数据库的性质。总体而言,本文面向实际出发,提出了一种新型的算法来挖掘交易数据库中具有统计显著性的频繁项集,为了实现交互性与可适用于动态数据库,提出了两种新型的数据结构,内存效用项集树与查询树,以及IDPI+算法来从动态数据库中获取指定查询项集的效能性和冗余性,成功构建了一个由用户引导的支持动态数据效能项集与非冗余项集挖掘的体系,扩展了该领域现有的研究范围。