高效用模式产生策略综述

高 曼，韩 萌，雷冰冰

北方民族大学 计算机科学与工程学院，银川 750000

1 引言

传统的模式挖掘主要考虑频率，假定每个项集出现在一个事务中的频次是一次，且具有同等的重要性，在很多实际生活中不具有使用性。如：商店销售中，面包与钻石被认为同等重要，这样就会出现利润高的项集没有被挖掘。因此基于上述问题提出高效用模式挖掘，高效用模式挖掘把钻石销售的利润很好地体现出来。

高效用模式挖掘是数据挖掘领域的一个重要研究内容，由于其计算过程包含对模式的内、外效用值的处理，计算复杂度较大，因此高效用模式挖掘算法的主要研究热点问题就是提高算法的时空效率。

在高效用项集挖掘的初期，基于先验方法[1]，设计了两阶段算法[2]，从具有高效用信息的数据库中寻找高效用项集。针对传统频繁项集挖掘中的向下闭包属性在高效用项集挖掘中不存在的问题，提出了事务加权效用（Transaction Weighted Utilization，TWU），利用TWU以减少挖掘高效用项集的搜索空间。虽然两阶段算法可以通过TWU 向下闭包属性减少搜索空间，但是这种算法由于生成和测试方法导致执行时间和内存使用过多，生成和计算候选对象和实际效用需要大量的数据库扫描。为此，提出了基于树的算法来克服两阶段算法的不足，如生成最近的高效用程序项集（GENerate recent High Utility Itemsets-Mine，GENHUI）[3]、增量数据库中挖掘高平均效用项集（Incremental Mining of High Average-Utility Itemsets，IMHAUI）[4]、压缩高效用项集挖掘（Compact High Utility Itemset-Mine，CHUI-Mine）[5]。因为产生候选项集会随着数据规模增大导致算法效率降低，所以进一步提出不产生候选项集的算法，如基于滑动窗口模型的数据流加权最大频繁模式挖掘（Weighted Maximal Frequent Pattern Mining over data streams based on Sliding Window model，WMFP-SW）[6]、基于模式增长方式的高效用模式挖掘算法（High Utility Pattern Mining based on Frequent Pattern growth，HUPM-FP）[7]、HUITWU（High-Utility Itemset Mining in Transaction Databases）[8]、用于事务修改的快速更新的高效用模式树（Fast Updated High Utility Pattern tree for transaction MODification，FUP-HUP-tree-MOD）[9]。

为了进一步提高算法的效率，将数据库进行投影以减少访问空间，如有效的高效用项集挖掘（EFficient high-utility Itemset Mining，EFIM）[10]、挖掘Top-k高效用项集的有效算法（efficient algorithm for mining Top-kHigh utility itemsets，TKEH）[11]、基于选择数据库投影挖掘高效用项集（Selective database Projection-based HUI Mining，SPHUI-Miner）[12]，还利用一些剪枝策略将不满足性质的子树进行剪枝，如算法EFIM、TKEH，利用两个上界子树效用性质来减少访问的空间，提高算法的时间与空间效率。

本文的主要贡献：

（1）从算法使用数据结构的角度分析两阶段算法和一阶段算法。

（2）分析基于树结构的高效用算法在计算过程是否产生候选项集。

（3）分析高效用模式算法用到的缩减搜索空间的策略。

2 一阶段与两阶段算法

最早的两阶段高效用算法是基于Apriori 将TWU这一概念应用于挖掘过程的算法。在第一阶段中生成候选对象的高估效用值应当不小于给定的阈值，然后再进行数据库扫描，计算它们的效用值，从而甄别出实际的高效用模式。因为两阶段算法产生大量的候选项集且扫描数据库多次，所以提出基于树的算法。本文主要介绍基于树的两阶段算法。基于树的算法减少了候选集产生的数量，也减少了数据库扫描次数，但是生成候选的数量还是比较大，进而提出了基于列表的一阶段算法来改善算法的时空效率。以下对基于树的两阶段算法和基于列表的一阶段算法进行比较分析。

2.1 基于树的两阶段算法

基于树的算法主要是根据数据库建立树结构，然后根据树结构得到高效用项集。两阶段算法首先产生候选项集，然后测试候选项集是否是真正的高效用项集。

为了解决基于Apriori 所带来的生成大量候选项集及数据库扫描次数较多的问题，提出了一种基于模式增长的算法UPTP[13]。该算法分为三个步骤：（1）扫描数据库两次，并构造全局效用模式树，降低节点的估计效用并对数据库中的事务进行调整；（2）采用效用模式增长算法，从全局效用模式树中，构造条件模式树，并根据前一个步骤记录的极小节点效用，降低路径效用，然后从条件效用模式树中递归地生成候选高效用项集；（3）从候选高效用项集中确定高效用项集，不需要扫描原始的数据库，高效地生成高效用项集。其中，前两个步骤为第一阶段，第三个步骤为第二阶段。UP-Growth（Utility Pattern Growth）[14]算法高效用项集的信息在一个效用模式树（Utility Pattern Tree，UP-Tree）中，在基于树的数据结构中进行维护，算法只需对数据库进行两次扫描就可以高效地生成候选项集。

上述算法挖掘的是全部的高效用项集，因为在生活中不需要进行完全挖掘，只需要找出用户所需要的个数即可，所以提出Top-k策略来实现。此类算法的主要特点是用户需要几个项集就设置k的值为多少。第一个基于Top-k算法的挖掘HUIs 是TKU（Top-kUtility itemset）[15]，是UP-Growth[14]的延伸算法。TKU遵循两阶段模型，并继承了两阶段的有用特性。在第一个阶段，生成潜在的Top-k高效用项集（Potential Top-kHigh Utility Patterns，PKHUIs），算法使用 PE（Pre-Evaluation）、MD（MIU of Descendants）、NU（Node Utilities）和 MC（MUIof Candidate）四种策略来提高内部最小效用阈值，并修剪搜索空间。在第二阶段，从第一阶段发现的PKHUIs集合中识别出Top-kHUIs。TKU 使用第五个策略SE（Sorting candidates and raising threshold by Exact utility of candidates）对候选项集进行排序，并提高内部阈值，TKU不仅要花费大量时间来查找Top-k高效用项集，而且它的一些提高阈值的策略也需要大量的内存。为了提高TKU 的性能，Ryang 和Yun 提出了一种名为REPT（Raising threshold with Exact and Pre-calculated utilities for Top-khigh utility pattern mining）[16]的算法。REPT 依赖于UP-Tree 结构，通过应用PUD（Preevaluation with Utility Descending order）、RIU（Real Item Utilities）来快速提高边界最小效用，从而提升TKU的性能。REPT通过各种策略（预效用降序、真实项集效用等）来缩小搜索空间，进而产生候选集，再通过支持降序等策略筛选高效用项集，因为REPT所提出的剪枝策略更加有效减少了搜索空间，所以算法性能比TKU好。

基于树的结构不仅适用于静态数据，还适用于动态数据，Ahmed 等人提出了类似于UP-Tree 的HUPMS（High Utility Pattern Mining over Stream Data）[17]来挖掘数据库为流数据的高效用模式。基于树状数据结构的滑动窗口模型，通过三个步骤从流数据中发现高效用模式。在第一步中，算法将事务插入到全局的HUSTree（High Utility Stream Tree）中，并计算它们的效用。在此阶段，每个插入的事务中项的节点效用按事务的效用添加。换句话说，HUS-Tree 中的节点使用了高估效用。在构建全局树之后，在第二步中，HUPMS通过使用模式增长的方法生成候选模式，其TWU 值不小于用户指定的最小效用阈值。在最后一步中，算法通过附加扫描计算候选对象的真实效用，生成高效用模式。对于基于滑动窗口模型的数据流，节点效用以逐批方式存储。虽然HUPMS解决了以前基于Apriori算法的问题，但是由于高估了效用，它仍然产生了大量的候选对象。因此提出SHU-Growth（Sliding window based High Utility Growth）[18]算法，通过减少生成的候选模式的数量来改进基于滑动窗口的高效用模式挖掘性能。算法通过引入减少全局估计效用（Reducing Global Estimated utilities，RGE）和减少局部估计效用（Reducing Local Estimated utilities，RLE）来减少过高估效用，从而减少搜索空间与候选模式。此算法总共包含三步：在第一步中，通过对数据流中当前窗口的单次扫描来构造全局树。在这个阶段，应用RGE 技术来减少头表中的高估效用和树中节点的高估效用。第二步，从构建的树中生成候选模式。当局部树直接从全局树中进行计算时，使用RLE技术来减少高估效用。在最后一步中，算法从候选对象中识别出一组高效用模式。与此同时，只要窗口已满且有新批到达，就可以通过删除最旧的批并反映新到达数据批来更新全局树。

现有的大部分高效用项集挖掘（High Utility Itemsets Mining，HUIM）算法都没有考虑事务的添加和删除。当数据库更新时，它们需要扫描整个数据库来重建数据结构。针对这一问题，提出了一种高效的树结构IHUP-Tree（Incremental High Utility Pattern Tree）[19]。构建初始的树，当新数据到达时需要将新到达的数据存储在树中，根据构建的树来挖掘模式，若数据获取已达到峰值且同时要删除旧数据，因为挖掘的是最近数据中的模式，所以之前的数据可以删除，这样既保证了内存中可以存储构建的树，又保证了有效挖掘模式，构建的IHUP-Tree 可以有效挖掘增量数据库的模式，当事务被添加到数据库或从数据库中删除时，通过调整IHUPTree来有效挖掘。基于IHUP-Tree可以高效地实现增量HUIM。IHUP-Tree也可以应用在交互式HUIM中。基于IHUP-Tree 的算法分两个阶段发现高效用项集（High Utility Itemsets，HUIs）。在阶段一中，采用了一种高估的技术来设置数据库中项目集的效用上限。被高估的效用不小于用户指定的最小效用阈值的项集被选为候选项。在第二阶段，候选项集通过再次扫描数据库进行验证。但是基于IHUP-Tree 的算法产生的候选对象太多，验证起来比较耗时。GENHUI[3]算法通过时间衰减模型来挖掘流数据上最近的高效用项目集，在此基础上设计了一种新的基于树的数据结构。该算法定期更新其树，将最近的效用信息反映到树中，无论何时执行更新过程，算法都会从树中删除过时的节点，只保留对挖掘结果有很大影响的信息。因此，当流数据在树状数据结构中不断累积时，该算法可以保持合理的内存使用界限。同时，该算法利用DTWU（Decayed Transaction Weighted Utilization）作为被高估的效用值，减少了搜索空间，从而有效地挖掘出一组潜在的HUIs。IMHAUI[4]算法使用模式增长方法，允许算法生成一组必要的候选项集。为了使算法在整个增量挖掘过程中始终保持树结构的紧凑性，采用了一种重构技术。

上述动态算法都需要设置最小阈值，因为新的数据到达时效用可能会产生变化，所以设置固定的阈值不是很合理，若阈值设置太低，则会产生大量结果使得用户难以选择，若设置太高，则会使得产生结果太少，没有真正想要的结果。因此提出在算法运行过程中动态地设置最小阈值，使得阈值设置更具有合理性。在动态算法运行过程中选取哪一个参数作为最小阈值是一个难点，因此提出多种策略提高最小阈值。为了解决阈值难以设置的问题，Zihayat 等人提出了一种基于数据流挖掘HUIs的算法T-HUDS（Top-kHigh Utility itemset mining over Data Stream）[20]，它解决了需要用户设置阈值的困难，将第k个项集的效用作为最小效用阈值，动态地更新最小效用阈值，使得最小效用阈值更加合理，进一步提高算法的效率。T-HUDS 提出了一种新的高估效用模型 PrefixUtil（Prefifix Utility of itemset）来减少候选项集的生成，因为PrefixUti 比TWU 更接近真实效用。此算法采用类似于FP-Tree 的压缩结构，称作HUDSTree（High Utility Data Stream Tree）结构，且使用max-UtilList（Maximum Utility List）和 MIUList（Minimum Itemset Utility List）两个辅助列表。列表用于存储计算前缀和初始化且动态调整阈值所需的信息，使用最小Top-k效用在第二阶段用于设置阈值。

根据对上述两阶段算法的分析，可以得出两阶段算法的缺点是需要产生候选项集，然后对候选项集进行测试，从候选项集中选取出真正的高效用项集，此外，算法对于原始数据库需要进行多次扫描。为了减少候选项集的产生并减少数据库扫描次数提出一阶段算法，因为一阶段算法不需要进行测试，所以同等条件下数据库扫描次数少于两阶段算法。

2.2 基于列表的一阶段算法

基于列表的一阶段算法很多，按照产生的结果集进行分类可分为完全和压缩，压缩包括Top-k、闭合高效用等。

基于列表的完全高效用算法特点就是只要是高效用项集就会挖掘出，最早是由Liu等人提出的HUI-Miner[21]（High Utility Itemset Miner）。算法挖掘的是全部的高效用项集，不丢失任何一个高效用项集。HUI-Miner使用效用列表来存储项集的效用信息，用于修剪HUIMiner搜索空间的启发式信息。通过避免大量候选项集的生成和效用计算的开销，HUI-Miner可以有效地从构造的效用列表中挖掘高效用项集。因为HUI-Miner 算法的连接操作降低了该算法的性能，所以提出HUPMiner（High Utility Pattern Miner）[22]算法和 FHM（Fast High-Utility Miner）[23]算法改进HUI-Miner算法。HUPMiner 算法使用了一种新的数据结构，称为分区效用列表（Partitioned Utility List，PUL），它在分区级别维护效用信息。算法使用的修剪策略（LA-prune）主要旨在限制在PUL 构建过程中生成的事务标识符列表的总数。算法同时使用PU-prune 来减少搜索空间，提高算法效率。相比较HUI-Miner算法，FHM算法通过共现剪枝策略来减少连接操作。为了进一步减少连接操作，提出了IMHUP（Indexed list-based Mining of High Utility Patterns）算法。该算法使用索引效用列表（Indexed Utility list，IU-list）减少比较和链接操作，且不产生候选项集。IMHUP 算法扫描两遍数据库，第一遍计算TWU，根据TWU值对数据库进行修改，删除没有希望的项，对数据库中的项按升序排序，第二遍扫描修改后的数据库，建立全局IU-list。其中，列表按TWU升序排序，相同事务的列表中的条目通过索引信息链接。按照TWU 顺序，并与当前所选列表的后续列表进行连接操作，以创建二项集的局部IU-list，根据二项集创建三项集局部IU-list，类似地进行创建更长项集的操作。通过使用RUI（Reducing Upper-bound utilities in IU-lists）减少数据结构中的上界效用来减少搜索空间。为了进一步提高算法的效率，Deng 提出了一种新的数据结构PUN-list（PU-tree-Node list）[24]，该结构既保留了项目集的效用信息，又保留了项目集的效用上限，便于挖掘高效用项集。MIP（Mining high utility Itemset using PUN-lists）的效率主要通过三种技术来实现。首先，项目集由一个高度压缩的数据结构表示，称为PUN-list，这避免了昂贵重复的效用计算。其次，通过扫描项目集的PUN-list，可以有效地计算项目集的效用，利用短项目集的PUN-list 可以有效地构造长项目集的PUN-list。第三，通过使用位于PUN-list 中的效用上界作为剪枝策略，MIP直接从搜索空间中发现高效用项集，而不生成大量候选项。相比较其他的算法，如HUI-Miner，需要将效用列表中部分信息再次计算才可以获得效用上界，这使得MIP运行时间较优。

Top-k高效用算法是为了解决最小阈值难以设置的问题而提出的，除了Top-k，其他算法都需要用户自行设置最小阈值，该类算法的主要特点就是不需要用户设置最小阈值，主要难点是如何在算法运行过程中提高最小阈值，最小阈值的初始值为0。现有的很多算法是基于模式增长，算法需要产生候选，为了提高算法效率提出 TKUL-Miner（Top-kUtility List Miner）[25]，它是一种高效挖掘Top-k高效用项集的新算法。它利用一种新的效用列表结构，在搜索树的每个节点上存储必要的信息，以便挖掘项集。该算法利用特定区域的搜索顺序快速提高边界最小效用阈值。此外，还提出了另外两种计算较小的高估效用策略，以有效地修剪没有希望的项集。该算法采用多种策略，快速提高最小效用，有效地缩减了搜索空间。kMHC（Top-kHigh utility itemset Mining using Co-occurrence pruning）[26]是 Duong 等人提出的一种基于效用列表结构的一阶段算法，是FHM算法的扩展。kHMC 使用RIU、CUD、COV（Coverage）来提高算法的最小效用阈值，它使用EUCPT（Estimated Utility Co-occurrence Pruning Strategy with Threshold）和传递扩展剪枝策略（Transitive Extension Pruning，TEP）。EUCPT 可以避免在FHM 中计算项目集效用的连接操作。kHMC 提出了一种新的剪枝策略TEP，TEP策略通过对项目集效用使用新的上限来减少搜索空间。Dawar等人[27]提出了一种从数据流中挖掘Top-k高效用项集的数据结构和算法。该算法是一个单一的阶段，不产生任何候选，不像许多算法工作在两个阶段，然后生成候选验证。KOSHU（Top-kOn-Shelf High Utility itemset miner）[28]是一种高效开采货架上的高效用项集的工具，它对商品上架时间、单位利润正负值进行考虑。KOSHU 引入了三种新的策略，即有效估计共现最大周期率剪枝、周期效用剪枝和一对二项集剪枝的并发剪枝，以减少搜索空间。KOSHU 是FOSHU[29]算法的Top-k版本。

闭合高效用算法的提出主要是解决结果集过大，使得用户无法快速准确地找到想要结果的问题。该类方法最大的特点就是没有丢失必要的信息。因为两阶段CHUD（Closed High Utility Itemset Discovery）产生大量的候选项集，所以提出一阶段算法CHUI-Miner[5]，其不需要产生候选项集，直接生成闭合高效用项集。CHUI-Miner提出EU-list（Extended Utility list）结构，且提出效用单位数组，使用TWU 和保留效用上界来减少搜索空间，提高算法效率。尽管CHUI-Miner 提高了算法效率，但是算法需要多次扫描数据集，降低了算法的效率，因此提出了EFIM-closed[30]，在一定程度上提高了算法效率。EFIM-closed 是基于投影和合并技术，采用基于深度优先的方法挖掘闭合高效用项集。算法提出两种不同的剪枝策略，分别是LU 和SU，减少搜索空间与运行时间。第一次提出投影与合并技术的算法是EFIM。投影与合并技术是一种非常有效的减少数据的扫描与存储的技术，此技术大大降低了算法的时间复杂度与空间复杂度。CHUI-Mine[5]用来发现闭合的HUIs和最大的HUIs，它们是HUIs 的紧凑表示。CHUI-Mine的主要优点在于两方面：首先，在效率方面，不像现有算法在挖掘过程中往往产生大量的候选项，CHUI-Mine直接计算项目集的效用，而不生成候选项。其次，在无损方面，与现有算法提供不完整的结果不同，CHUI-Mine可以在没有遗漏的情况下发现完全闭合的或最大的HUIs。将CLS-Miner[31]更有效地引入到CHUIs 中。与CHUD 不同，它是一个依赖于效用列表结构来发现CHUIs 的单阶段算法。从这个角度来看，CLS-Miner 类似于CHUI-Miner，但是有一些关键的区别：首先，CLSMiner 与CHUI-Miner 使用不同的搜索空间剪枝策略。一个重要的特性是，CLS-Miner的策略可以在搜索空间中完全构造效用列表之前删除项集，从而大大降低了挖掘CHUIs的成本。其次，CLS-Miner引入了一个高效的预检查方法，快速确定一个项集是否是另一个项集的子集。使用这种方法优化闭包计算和包含检查的操作，这些操作通常由闭合模式挖掘算法执行。但是需要注意的是，这两个操作在闭合模式挖掘算法中重复执行，因此这种预检查方法大大缩短了发现CHUIs 的时间。EFIM-closed 在密集数据集上有很多限制，由于这个算法需要多次扫描数据库，为了解决在稀疏与密集数据集上运行时间与内存上的有效性，提出了Hminer-closed[32]算法，使用修改的紧凑效用列表存储结构（Modified Compact Utility List，MCUL），只需要扫描一次数据库，在处理候选项时，根据CHUIs 对候选项进行向后检查，从而减少搜索空间，节省重建后向集合进行匹配的时间。在下一步中结合前向检查和构建候选项，以减少运行时间，合并类似的事务，以减少存储空间，修剪MCUL 后，立即更新 LA-prune 和 C-prune 的值，使得剪枝策略更有效。

平均高效用项集挖掘通过考虑项目集的长度（项目的数量）来更公平地度量项目集的效用。现有的很多方法可分为水平增长方法和模式增长方法。但是这两种方法都需要大量的计算才能找到实际的高平均效用项目集，因此提出基于列表的方法。FHAUI（Fast High Average Utility Itemset）[33]算法将效用信息保存到效用列表中，通过效用列表的连接挖掘出所有的具有高平均效用值的项集，同时FHAUI 算法还采用二维矩阵来有效减少二项效用值的连接比较次数。该算法属于一阶段算法，可以在不产生候选项集的情况下挖掘出所有的高平均效用项集，并且只需要扫描两次数据库。同时，给出改进效用列表结构IAU-list 和平均效用，采用二维矩阵来有效地减少效用列表之间比较连接的次数。Lin 等人[34]提出了一种平均效用（Average Utility，AU）列表结构来更有效地发现HAUIs（High Average-Utility Itemsets），提出了基于深度优先搜索算法HAUIMiner（High Average-Utility Itemset Miner），在不生成候选对象的情况下搜索空间，并提出了有效的剪枝策略来减少搜索空间，加快挖掘速度。目前很多平均高效用算法使用单一的高平均效用最小阈值，这限制了它们分析真实数据的有效性。因为不同的项目对用户来说并不同等重要。为解决这一问题，HAUIM-MMAU（High Average-Utility Itemset Mining with Multiple Minimum Average-Utility Thresholds）[35]算法提出多个最小效用阈值，使用产生和测试的方法挖掘HAUI，降低了算法效率。MEMU[36]提出了一种新颖的MAU-list 结构和一种排序枚举树（Sort Enumerate Tree，SE-Tree），在减少搜索空间的同时挖掘HAUIs。此外，还设计了一个更紧密的上限模型RTUB（Revised Tighter Upper-Bound）来修剪没有前途的项目集。模型RTUB 与传统AUUB（Average-Utility Upper Bound）模型相比较值更小。提出了三种基于RTUB 模型的剪枝策略，以减少搜索空间，更有效地挖掘HAUIs。

基于树的方法，主要是通过效用上界来减少候选项集。基于列表的方法，通过效用上界和剪枝策略来减少搜索空间。基于列表的方法的缺点主要是算法过程中构建效用列表花费大量的代价且算法连接操作代价较大，主要优点是不需要对原始数据库进行多次扫描，且通过降低效用上界提高算法的效率。与两阶段算法相比较，一阶段算法可以直接挖掘高效用项集，不需要产生候选项集，也不需要扫描一遍原始数据库来测试候选项集，通过混合搜索机制有效地挖掘高效用项集，通过多种机制有效地存储效用信息，从而提高算法的效率。一阶段算法首先通过减少数据库的扫描来提高算法效率，因为扫描多次数据库需要花费大量的时间，将数据库的信息存储在列表中从而不需要多次扫描数据库；然后通过减少列表的连接操作来提高算法的效率，由于构建新的列表花费较大，通过构建更紧凑的效用列表来减少搜索空间，因为更紧凑的列表可以减少算法运行过程中的搜索，再通过更小的效用上界来减少搜索空间，从而提高一阶段算法的效率。

上述主要从一阶段、两阶段算法使用的数据结构角度进行分析，此外从算法使用的搜索方式进行划分，还可以划分为水平方式和深度优先。使用水平方式的两阶段算法最有代表性的就是Two-Phase[2]，使用深度优先搜索方式两阶段算法很多，如TKU、REPT等，一阶段算法都使用深度优先的方式进行搜索。与水平方式算法相比，深度优先算法性能更好。因为水平方式算法产生大量候选项集，且需要测试，需要多次扫描数据库，而深度优先的方式主要是构建数据结构来减少数据库的扫描次数，使得算法的效率得到有效的提升。

一阶段、两阶段算法的分析结果如表1所示。

表1 阶段算法

3 有无候选集

现如今，数据的数量与种类越来越多，由于目前的存储技术不能满足大量增长的数据全部保存的需求，多数的数据不能直接存储，因此需要通过挖掘动态数据得到有趣的模式。以下主要对基于树结构是否产生候选项集算法进行分析。

3.1 产生候选项集

静态数据产生候选项集的算法有TKU[15]、REPT[16]。TKU 算法使用UP-Tree 来维护高效用项目集的信息，UP-Tree 是在两次数据库扫描中构造的。UP-Tree 数据结构中计算事务加权效用，以提高查找高效用项目集的效率，UP-Tree 使用各种策略从事务数据库中删除不相关的信息。REPT 算法也是基于UP-Tree 的两阶段算法，产生大量的候选项集，且需要测试候选项集是否为高效用项集，该过程需要大量的时间。为了节约时间，提出了一种策略提高最小阈值，更有效准确和预先计算效用，在第二阶段确定实际的Top-k高效用模式。此外，有效提高阈值大大减少了搜索空间和生成的候选模式的数量，这使得此算法能够更快、更有效地挖掘Top-k高效用模式。

上述算法是基于静态数据库的两阶段模型算法。为了使算法更好运用于动态数据库，提出了基于树结构的增量算法，名为IHUP[19]。该算法提高了生成候选项集的效率及减少了数据库扫描的次数，使用树结构来记录项的效用信息。但是，IHUP 算法在第一阶段同样会产生大量的候选项集，严重影响了第二阶段的效用。虽然提出了增量式高效用模式（IHUP）挖掘算法，但其树结构IHUP-Tree 是冗余的，因此IHUP 算法的效率相对较低。为了解决这个问题，提出了一种增量压缩的高效用挖掘算法（incremental Compressed High Utility Mining，iCHUM）[37]。iCHUM 算法利用 TWU 构造树结构，即iCHUM-Tree。当新数据库添加到原始数据库时，iCHUM算法将更新iCHUM-Tree。高效用项集的信息保存在iCHUM-Tree 中，从而可以通过挖掘过程生成候选项集。为了提高算法性能，提出了基于时间衰减模型的增量算法GENHUI[3]。GENHUI 算法通过构建RHUI-Tree（Recent High Utility Itemsets Tree）与更新RHUI-Tree来挖掘高效用项集。RHUI-Tree由两部分组成，一部分是header table，另一部分是树。RHUI-Tree头表结构由两部分组成，一部分是项，另一部分是DTWU。算法将数据通过处理计算DTWU，再通过树的构建以及约束DTWU 来寻找高效用项集，GENHUI 需要产生候选。为了更有效地挖掘高效用项集，提出平均高效用项集。IMHAUI[4]算法采用了模式增长方法，允许算法生成必要的候选项集。采用的树结构是IHAUITree（Incremental High Average Utility Itemset Tree）。IHAUI-Tree 是由两部分组成，这两部分与RHUI-Tree[3]头表的组成类似，但是表中的内容不一样，只是IHAUITree[4]用到的是AUUB而不是DTWU。

Ahmed 等人提出HUPMS[17]算法，使用模式增长方法挖掘当前窗口中的所有高效用模式。此外，HUS-Tree对于交互式挖掘是非常有效的。该算法对于数据流上的增量式和交互式HUP 挖掘非常有效，并且显著优于很多的基于滑动窗口的HUP 挖掘算法。虽然HUPMS解决了以前基于Apriori 算法的问题，但是由于高估了效用，它仍然产生了大量的候选对象。因此提出SHUGrowth[18]，在构建全局 SHU-Tree（Sliding window based High Utility Tree）时使用RGE 技术减少头表和节点的高估效用，从而减少搜索空间和候选项集的数量。用项的高估效用大于最小窗口效用来判断项是否可以作为候选模式，若可以作为候选模式，则创建项的条件模式基，进一步确定候选模式。

慕欢欢等人提出一个数据流高效用项集挖掘算HUIDE[38]。算法首先综合考虑数据的信息特征，提出一种有效的效用度量方法，然后采用基于时间的滑动窗口技术更加准确地描述数据分布，构建一种高效用项集树（HUI-Tree）。最后遍历构建的树HUI-Tree挖掘高效用项集，减少了候选项集的产生及时间和空间的消耗。Yun等人提出了一种称为HUPID-Growth[39]（High Utility Patterns in Incremental Databases Growth）的算法来挖掘增量数据库中的高效用模式。此外，为了提高增量数据库的处理效率，提出了一种基于单次数据库扫描的HUPID-Tree（High Utility Patterns in Incremental Databases Tree）结构和一种新TIList（Tail-node Information List）数据结构。

3.2 不产生候选项集

一阶段算法并不都是不产生候选的算法，不产生候选的算法指的是没有候选项集的产生直接挖掘的是高效用项集，一阶段算法可能产生候选。

Lee等人提出了一种基于滑动窗口模型的数据流加权最大频繁模式（WMFPs）[6]挖掘算法，并给出了查找WMFPs 所需的数据结构，即滑动窗口最大频繁模式树和滑动窗口最大频繁数组。滑动窗口最大频繁模式树反映窗口更新和重构，滑动窗口最大频繁数组减少树扫描、挖掘单路径策略等，有效地反映数据流上最新信息的WMFP。

D2HUP[40]可以在不生成候选模式的情况下找到高效用模式，新颖之处在于使用高效用模式增长方法、前瞻性策略和线性数据结构。具体来说，通过模式增长方法去搜索一个反向集枚举树，并通过效用上边界来修剪搜索空间，在线性数据结构能够计算一个紧密的边界来进行强大的剪枝，并以一种高效和可伸缩的方式直接识别高效用模式。D2HUP 使用反向枚举树挖掘高效用模式，提出更紧凑的上界和不相关的项进行剪枝来提高算法的时间效率。使用CAUL（Chain of Accurate Utility List）结构维护每个枚举模式的原始效用信息，使人们能够有效地计算效用并估计严格的效用上限。

HUITWU[12]是一种新的HUITWU-Tree，用模式增长的方式寻找高效用项集，直接有效地计算数据库中项集的效用。HUPM-FP[7]是一个基于模式增长方式的高效用模式挖掘算法，可以从全局树上挖掘高效用模式，避免产生候选项集。该算法主要采用模式增长的方式来直接挖掘高效用模式，而不是从树上先得到候选项集，因此算法的时空效率都得到了提升。

基于事务修改是一种快速更新高效用模式树的算法（FUP-HUP-tree-MOD）[13]，可以有效地维护和更新构建的HUP-Tree，从而在不生成候选项的情况下动态挖掘数据库中的高效用项集。HUP-Tree保证从中计算到每个模式的效用值，不需要再扫描数据集来计算模式的效用值，从而使挖掘算法的时空效率得到较大的提高。

两阶段算法产生候选项集策略且需要对候选项集进行测试，一阶段算法直接生成高效用项集，因此产生候选项集的算法相较于不产生候选项集的算法性能更好。

基于树结构的高效用挖掘算法的分析结果如表2所示。

4 缩减空间策略

在数据库寻找高效用模式，无论是用树结构还是其他结构，如列表结构，都需要减少搜索空间，以降低算法的时间复杂度和空间复杂度。剪枝策略有很多，不同特征使用不同的剪枝策略。减少对数据库扫描次数的方法就是存储后续算法需要用到的信息，如构建树、列表、投影数据库来存储后续需要用到的信息，也就是数据库中重要的信息。

表2 基于树结构的高效用挖掘

4.1 剪枝策略

根据算法的结构不同使用不同剪枝技术。虽然使用的剪枝策略不同，但是剪枝的目的是相同的，就是减少搜索空间。

基于树剪枝策略有很多，剪枝策略的主要方式是降低高估效用上界来减少可扩展的项，现有的子树效用和局部效用很好地减少了可扩展项的数量。EFIM[14]依赖于两个上界，采用子树效用和局部效用有效地修剪搜索空间，该算法的剪枝策略是对枚举树进行剪枝。EFIM-closed[30]与EFIM不同的是添加了闭合属性，也使用子树效用和局部效用对搜索空间进行缩减。MEFIM（Modified Efficient high-utility Itemset Mining）[41]是一种基于EFIM 的算法，该算法考虑到单位利润随着时间的变化可能不同，因此单位利润是动态变化的。该算法重新定义了效用的计算，为了提升算法的效率，使用子树效用和局部效用进行剪枝，剪枝策略与EFIM相同。EHNL（Efficient High utility itemsets mining with Negative utility and Length constraints）[42]克服了效用值为负值的局限，使用子树效用来减少搜索空间。但目前面临的主要问题是如何结合子树剪枝策略和负效用项集挖掘长度约束。为了解决这些问题，根据事务的效用值按非递增顺序对事务项进行排序，并在偏移指针的帮助下将负项保留在排序后的项的末尾。为了进一步减少可扩展项集，提高算法效率，提出DMHUPS（Discovering Multiple High Utility Patterns Simultaneously）[43]。DMHUPS也使用了局部剪枝，且该算法提出了更接近于真实效用的上界extUB（Extension Upper-Bound），更有效地减少了可扩展项的数量。

基于列表结构的剪枝策略主要是减少建立列表所需的计算，下面所述是在二项集计算时进行剪枝。FHM[23]提出剪枝策略EUCP（Estimated Utility Co-occurrence Pruning），它可以在不需要执行连接的情况下剪枝项集。CHUM（Closed+High Utility Itemset Mining）[44]、FDHUP（Fast algorithm for mining Discriminative High Utility Patterns）[45]、PHM（Mining Periodic High-Utility Itemsets）[46]、TKUL-Miner[25]用 EUCP 减少搜索空间，这些算法是提前计算项集对应的TWU，将效用存储在EUCS结构。TKEH[11]采用EUCP 和SUP 策略来有效地搜索空间。kHMC[26]使用EUCPT可以避免在FHM中计算项目集效用的连接操作。FHAUI[33]算法将效用信息保存到效用列表中，通过效用列表的比较来挖掘出所有的高平均效用值，同时FHAUI 算法还采用了一个二维矩阵（EUCS）来有效减少二项效用值的连接比较次数。

除了上述的基于列表的策略外，还有保留效用策略也使用广泛。HUI-Miner[21]构建效用列表，与CHUIMine 不同的是，它构建的列表第三部分的组成是RU（Remaining Utility），CHUI-Mine第三部分的组成是PU（Pivot-based remaining Utility），HUI-Miner缩减搜索空间的策略是所有IU（Itemset Utility）与RU 的和不小于给定的阈值则保留。为了解决HUI-Miner[21]昂贵的连接执行的操作，提出FHM（Fast High-Utility Miner）算法[23]。该算法提出共现剪枝策略来减少连接操作，并且还使用保留效用来减少搜索空间策略。

上述的剪枝策略不影响结果的完整性，因为上述的效用值都大于或等于实际的效用值，不会将实际的高效用模式忽略。子树效用、局部效用、判断二项集使用的效用值TWU、保留效用，都大于或等于实际效用，因此不会影响结果集的完整性。

4.2 投影策略

随着高效用模式挖掘算法在实际应用中的重要性逐步显著，其得到了越来越多的关注和研究，但是已知的一些算法存在着多遍数据集扫描以及产生大量候选项集、时效性不高等问题。这些问题使得高效用模式的挖掘效率大大降低，故提出基于投影的高效用项集挖掘算法。

EFIM[14]算法通过将数据库相关项进行投影来减少数据库的整体大小，还提出两种有效的剪枝策略（局部剪枝和子树剪枝）。子树剪枝策略有效地减小了效用上界，使得进一步扩展项集减少，从而减少搜索空间。与之前的其他数据结构（树结构与列表结构）相比，数据库投影是一个简单且非常有效的技术，如UP-Growth+[47]使用树结构进行挖掘，HUP-Miner[22]、HUI-Miner[21]和FHM[23]都使用列表进行挖掘，这些算法与EFIM 进行比较，无论是在执行时间、内存使用和访问节点的数量来看，都没有优于EFIM。算法为了能够挖掘效用值动态变化的情况，提出MEFIM[41]，它基于EFIM进行改进，同样用到了数据库的投影技术，使得数据库的规模减小，进而提高算法的时间效率和空间效率。iMEFIM 是MEFIM的改进，该算法提出p-set结构，不需要扫描全部的投影数据库，从而提高了算法的效率。EFIM 算法的缺点是需要多次扫描数据库，为了解决这个问题提出了DMHUPS[43]。DMHUPS 也使用了数据库投影的技术，且算法用到了IUData 列表，有效地获得初始的投影数据库。IUData列表的数据结构，用于存储长度为1的项目集及其在事务中的位置信息，从而有效地获取投影数据库。此结构可以避免多次扫描数据库，进而提高算法的效率。除了DMHUPS 算法还提出SPHUI-Miner[16]来改进EFIM 算法。SPHUI-Miner 是一种基于选择数据库投影的HUI 挖掘算法。该算法提出了一种高效的数据结构，称为HUI-RTPL（High Utility Itemset-Reduced Transaction Pattern List），它是一种对内存要求低的数据进行优化和紧凑表示的格式。还提出了两种新的数据结构，即选择性数据库投影效用列表和尾数列表，以缩减HUI 挖掘的搜索空间。数据库的选择性投影减少了数据库的扫描时间，使得提出的方法更加有效。它为维度更小的数据创建了独特的数据实例和新的投影，从而加快了HUI 挖掘的速度。投影技术不仅可以应用到挖掘完全高效用项集，还可以应用到闭合、Top-k高效用项集等。可以应用到闭合如EFIM-closed[30]算法，该算法在EFIM 的基础上进行改进，将EFIM 中用到的挖掘技术延伸至挖掘闭合项集中。应用到Top-k中如TKEH，该算法沿用了EFIM 中的技术挖掘项集，但是在EFIM的基础上不需要设置最小阈值，而是使用提高阈值的策略来初始化阈值。

4.3 其他

针对Top-k算法的策略与其他算法不同，Top-k的优点是不需要额外设置算法的最小阈值，主要策略是如何提高算法最小阈值。一般算法需要多种策略提高最小阈值。

REPT 通过PUD、RIU、RSD（Raising threshold with items in Support Descending order）、NU、MC、SEP（Sorting candidates and raising threshold by Exact and Pre-calculated utilities of candidates）提高最小效用阈值的方法有效地减少搜索空间。TKEH、kHMC 通过RIU、CUD、COV 来提高最小阈值，减少搜索空间。TKUL-Miner[25]是一种高效挖掘Top-k高效用项集的新算法。它利用一种新的效用列表结构，在搜索树的每个节点上存储必要的信息，以便挖掘项集。该算法利用特定区域的搜索顺序快速提高边界最小效用阈值。此外，还提出了另外两种计算较小的高估效用的程序策略，以有效地修剪没有希望的项集。该算法采用FSD（Firstlevel Search in TWU Decreasing-order）、RUZ（Reducing overestimated Utility by Sum_Zrutils）、FCU（First child pruning by using Sum_Cutil）等策略，快速提高了搜索的最小效用，有效地缩减了搜索空间。TKO（Top-kutility itemsets in One phase）[48]利用了 HUI-Miner 中的效用列表结构，提出了RUC、RUZ和EPB三种新的剪枝策略，提高了剪枝效率。TKU不仅使用TKO中的策略，还使用第五个策略（SE）对候选项集进行排序，并提高内部阈值。

通过对上述算法的描述，可以得出不同类型的算法使用的缩减搜索空间的方式不同，且大部分算法都使用多种策略，通过多种策略更大程度地减少搜索空间使得算法的效率更好。使用多种策略比使用单一策略的算法效果更好。

5 下一步工作

面对日益增长的海量数据和种类繁杂的数据，研究者可以深入探索以下几方面。

（1）迭代和交互。数据挖掘成为一个交互的过程是可取的，因此算法被设计来支持交互挖掘。增量的高效用项集挖掘（increment High Utility Itemset Mining，iHUIM）中使用的一些数据结构不适合交互式挖掘。为了解决现有算法的这些局限性，研究人员需要采用增量方法来支持迭代和交互式增量HUIM。有很多可能性，例如对最新的HUIs 进行增量挖掘，使用固定最小效用阈值的交互式HUIs 挖掘，以及不设置最小效用阈值的迭代式增量HUIs挖掘。

（2）大规模的数据。增量地挖掘大型数据库可能会导致较高的计算成本和较大的内存消耗。在批处理模型中，当插入新数据时，需要重复使用传统的HUIM 算法来获得更新的结果。然而，在大数据时代，渐进地处理数据并考虑先前分析的结果是至关重要的。iHUIM在处理大型数据库方面存在一些研究机会：如何设计一个并行的iHUIM 算法，如何基于现有的大数据技术开发一个iHUIM 算法。此外，其他有前途的领域可以考虑，如设计并行、分布式、多核和基于GPU的算法。

（3）非均质性。传统的关系或非关系数据库系统通常使用具有同类格式的单一模式或文件。在大数据时代，需要处理大量的异构数据。传统的数据挖掘技术旨在发现结构化数据中的有用知识。非结构化和/或半结构化数据中语义和异构模式的提取是数据挖掘和iHUIM 面临的主要挑战。因此，在调整iHUIM 以处理同类数据方面存在一些机会，包括逐步发现结构化数据、非结构化数据（可能包括文档、音频、视频、图像）和半结构化数据（即XML、JSON）。如何扩展现有的iHUIM算法来处理同构数据是一个重要的课题。

（4）动态复杂的数据。虽然已经开发了几种增量式HUIM算法，但在如何处理复杂数据等方面仍存在许多挑战。所有的iHUIM算法都是为了处理精确的数据而设计的，因此不适合处理不确定的数据。到目前为止，在动态序列数据中挖掘高实用模式的增量方法还没有被开发出来。因此，增量式高实用程序顺序模式挖掘也是一个有趣的主题。由于现实生活中的数据是动态的而不是静态的，因此大规模复杂数据的应用范围很广。这个原理很简单，但是在数据挖掘算法的设计中集成起来肯定是困难和复杂的。与静态环境相比，发现动态数据的环境比较复杂，而且更难处理。

（5）iHUIM在运行时间和内存方面的计算开销非常大。对于密集的数据库，或者包含大量条目或长事务的数据库，这取决于用户设置的最小高效用阈值。虽然目前的增量挖掘算法比以前的算法要快得多，但仍有改进的空间，例如开发出更紧凑的数据结构（如树、列表、图）、更有效的剪枝策略以及自适应挖掘方法。

6 总结

本文主要从算法的实现阶段进行分析，一阶段算法在时间与空间效率方面都要优于两阶段算法，主要原因是，两阶段算法需要产生候选项集，然后再验证候选项集是否为高效用项集。为了提高算法效率，提出一阶段算法直接挖掘高效用项集，不需要生成候选项集，从而节省了时间与空间，针对不同的问题采用不同的算法，将算法划分之后再进行分析。然后从算法的实现过程来看，针对是否产生候选项集进行分析，通过数据库采用的数据结构不同，使用的剪枝策略不同来分析广泛使用的策略。下一步研究的主要工作是如何进一步提高算法的效率。主要方法是进一步缩小效用上界，提出更紧凑的结构存储信息，减少数据库扫描次数等。