Top-K HUIs算法的比对分析

写在前面：最近在研究Top-k高效用挖掘算法，在老师的介绍下接触到这篇文献，该作者很贴心地为我们介绍了 top-k HUI mining 的几个关键方法，与其它高效用模式挖掘算法的对比评估，还有当下top-k算法的不足之处。本文记录对该文献翻译上的理解和自己的思考，如果错误还望指正。

介绍

​ 该段从频繁模式挖掘（FIM）入手，我们都知道频繁模式运用范围广，而且实现起来简单（频繁的反单调性），最典型的例子莫过于“啤酒和尿布”。然后介绍了在FIM基础上扩展出来的高效用项集挖掘（HUI），为什么会提出效用（utility）这个概念？我的理解是对比卖一颗钻石和一箱辣条，虽然钻石卖的少，但利润极高，反观辣条虽然量多但就没这么高的利润了。而FIM模式下是忽略了这些商品的本身价值，而且对于顾客在一次交易中多次购买同一件商品的行为，FIM模式下是无法识别的（因为它只统计该商品在多少条交易记录中出现，而不是在该交易中出现多少次）

​ 项(集)效用（item(set) utility）分为内部效用（internal utility，可以看成购买量）和额外效用（external utility，可以看成是单件利润）[Ps. 为什么这么命名我也没有想到一个合理的解释…]但这有个新的问题产生，以往FIM模式的特性：向下闭合性（ downward closure property，也就是反单调性）在高效用项集模式不适用，因为随着数量和利润的变化，单个商品的效用值会呈现不规律变化，那有没有其它方法可以利用反单调性这个思路呢？之后就提出了新的概念：Transaction Weighted Utilization(TWU)[Ps. 相定义定理可以去查阅HUI-Miner文献]。

​ 但对于高效用项集模式挖掘有一个很大的缺陷（这个在运行代码的过程中也可以感知到）：对于不同的阈值（minUtil），结果会大相径庭。文中提到在吴导的TKU算法文献中分析了这个现象，如下图：

至此，合理设置阈值（minUtil）就成了高效用项集模式挖掘的一大难题[Ps. u1s1，当初在学习HUIs的时候并没有意识到这一点，惭愧]。

​ 之后就有学者设计了Top-K挖掘模式[Ps. 这一点和排序算法问题中的Top-K问题是一致的，本质上都是求出当前最需要、最符合条件的k个信息，其它的可以忽略]

​ 最后作者介绍了该文献的目的是：探讨当下 top-k高效用项集挖掘 的发展趋势和未来方向。

背景知识和问题描述

​ 这一部分主要是介绍一些定义和性质，比如：什么是项(集)，什么是交易项(集)，为什么TWU<minUtil就会导致该项(集)的扩展集一定会是低效用…等等，通过其它文献大家都知道的，有需要的可以阅读原文，此章节略过。

实现Top-K高效用挖掘

这一部分就是重点了，其实在学习HUIs相关算法的过程中我们也能了解到，最初的发展是由像HUI-Miner这样的两步走算法（即第一步生成候选集(Candidate Itemset)，第二步挑选高效用项集），到后来的EFIM这样的一步走算法（即无需生成候选集，在扫描数据集的时候生成上边界值，然后根据这些边界值去筛选高效用项集），top-k的发展其实也是一样，该文献主要也从这个角度进行阐述：

Two-Phase

代表有 TKU、REPT 等算法

TKU算法

该算法提出时间很早，其文献在2012年发表，由这几位大佬共同完成：Cheng Wei Wu, Bai-En Shie, Philip S. Yu, Vincent S. Tseng。在第一步过程中，该算法会构造一个UP-Tree结构，并且生成潜在的k个高效用项集（PKHUIs），第二步自然就是从PKHUIs中挑选出top-k个HUIs。其中提出了五个不同的阈值自增策略（PE、MD、NU、MC、SE）

• PE策略：

  主要是通过一个Pre-evaluation (PE) matrix来构造阈值自增，该策略选择在UP-Tree构造前进行，目的是避免UP-Tree以0为阈值开始构造（也就是先提升一次）计算过程就是对矩阵横竖构造出来的二元项集进行赋值。而后我们选第k大的值作为提升后的阈值[Ps. 这里额外补充一点，类比排序里的top-k问题其实就是找出最前面k个信息，而我们的阈值设定是取这k个值里最小的那个，这样才有继续提升的空间]，以下是文献中的示意图：

  

• NU策略：

  全称为Node Utilities Strategy，如果有至少k个节点在UP-Tree中，当第k个节点的效用值大于当前设定的阈值，那么对把第k个节点的效用值设置为新的阈值。

• MD策略：

  在构造完UP-Tree之后，对根节点下的不同子节点进行组合（二元项集），求出它们的miu(X)值（具体参考原文定义5、6、7）在这些下限值（lowwe bound values）中挑选第k个值，若大于当前阈值，则更新阈值，否则不进行操作。

• MC策略：

  反复使用MD策略构建更大的高效用候选集，比较第k个项集的min值是否大于当前阈值，若不大于，则跳过。

• SE策略：

  用在第二步骤中，利用一个堆结构存储候选项集，并优先考虑效用值大的项集取设置阈值，同样是第k个项集的效用值比较

以上说的不是很详细，主要的UP-Tree结构需要重点理解，而且还有四种UP-Growth文献中设计的剪枝策略没有说明（DGU、DGN、DLU、DLN），有兴趣的还是要去查看原文，链接放在这里。

REPT算法

该算法由Heungmo Ryang, Unil Yun于2015年发表，与TKU算法很相似，使用PMUD（也就是降序排列的 Pre-evaluation matrix）不同点在于二项集的第一项被选为具有最大外部效用值的交易项中的项，也有四个自增策略（PUD、RIU、RSD、SEP）

• PUD策略

  使用PMUD矩阵构造出二元项集的下限值，若至少有k个项集在PMUD矩阵，那么对阈值进行第k大的效用值替换。目的同PE策略一样，也是为了提高UP-Tree的构造效率

• RIU策略

• RSD策略

  用来存储二元项集的准确效用信息，该矩阵基于各项的支持度（具体见原文定义6），然后选择N/2的最高支持度和N/2的最低支持度（意思是取排好序的两端各N/2个，其中N是候选集数量），替换思路和PUD策略一致。

• SEP策略

  是SE策略的plus版，它使用精确值而非预估值去提升阈值

原文还简单描述了一下REPT算法的计算思路，REPT算法原文链接在这里，在第一次扫描数据集的时候，使用的是real utility去自增阈值，而不是像TKU里的那样使用预估值(overstatement)；在第二次扫描构造树型结构的同时，使用RSD策略对阈值进行自增，这一环节和TKU很相似；在第二步（Phase II），使用SEP策略对候选集进行排序，并筛选出真正的 top-k HUIs。下图可以看出来REPT算法和TKU算法在实际运行中采取策略的不同：

One-Phase

代表有 TKO、KHMC 等算法

TKO算法

TKO算法和TKU算法是在同一篇文献里提出来的，原文链接放在这里。自打HUI-Miner算法起，对各项排序就成为一个很重要的环节，因为排序之后对交易项集的投影归并等操作实在是太方便。而TKO算法也是借鉴了HUI-Miner算法的设计思想，使用Utility-List结构替代候选集（Utility-List结构 很好理解，想知道怎么设计的可以阅读HUI-Miner算法）

该算法同样在第一次扫描数据集时使用PE matrix结构来自增阈值，第二次扫描开始构造一元项列表，在扫描的过程中利用DGU剪枝策略中介绍的性质，过滤掉那些低效用项，并且对每个交易项中的项事先要排好序。在之后用一元项列表两两间 并 操作构造二元项集列表。在第二次扫描过程中还构造了一个小根堆（TopK-CI-List）去存储k个高效用项集，每次阈值变化就取堆顶元素，堆节点增删都通过调整堆来实现。对阈值自增策略和检索空间进行剪枝采用了三个新策略（RUC、RUZ、EPB）

• RUC策略

  使用TopK-CI-List堆结构，把阈值直接与堆顶值进行比较，如果小于那么进行替换。

• RUZ策略

  给出了一个新定义Z-element和NZ-element，这两个定义就是对rutils(剩余效用值)的两种情况进行命名（因为最后一个项是必然没有rutils的）。而且定义NZEU(X)是项集X的所有NZ-element的iutils的和，当NZEU(X) + RU(X) < minUtil时，可以判定项集X的所有超集都不是top-k HUIs（当初看文献看到这里的时候，我想这和 reu = iutils + rutils < minUtil 这条性质没啥区别，看起来就像是把范围缩小了，因为只查看NZEU(X)）

• EPB策略

  该策略的目标是优先生成那些高效用值的候选项集，因为先扩展拥有最大预计效用值的项，这样可能得到高效用值，就可以更早地提高minUtil，进而剪枝更多的搜索空间。

KHMC算法

在2016年 Quang-Huy Duong, et al 发表该算法。在第一遍扫描数据集的时候，计算各项的效用值和TWU，然后使用RIU策略提升阈值；第二次扫描数据集的时候分别构造EUCST、CUDM和Utility-List等数据结构。其中EUCST是一个hash map数据结构，用于存储项集的TWU值（基于2014年的HFM算法中的EUCS加强版，这两个差别就是一个是三角矩阵的存储方式，一个是hash map），而CUDM存储的是项集的utility value。同样也设计了两个阈值自增长策略（CUD、COV）

• CUD策略

  在第二次扫描数据集的结束时刻提升minUtil，同样是利用CUDM里存储的第k大项效用值去和当前阈值作对比

• COV策略

  当项x的扩展集是项y的扩展集的子集时，项y可以作为对项x的覆盖，该方法主要是对一元项来估计其扩展的二元项集的效用值，同理，也可以用这个效用值对当前阈值进行提升。

• RIU策略

• RUC策略

Top-K算法间的比较

下图是对于当前top-k算法的自增策略汇总：

下图时对于当前top-k算法的剪枝策略汇总：

原文还在不同数据集的情况下测试了TKO和KHMC算法之间的差异性

参考

1. Srikumar Krishnamoorthy: A comparative study of top-k high utility itemset mining methods-https://arxiv.org/abs/1809.00792v1
2. Cheng Wei Wu, et al：Mining Top-K High Utility Itemsets-https://www.researchgate.net/publication/235949419_Mining_Top-K_High_Utility_Itemsets
3. Heungmo Ryang, Unil Yun：Top-k high utility pattern mining with effective threshold raising strategies-https://www.sciencedirect.com/science/article/abs/pii/S0950705114004481
4. Quang-Huy Duong, et al：An efficient algorithm for mining the top-k high utility itemsets, using novel threshold raising and pruning strategies-https://www.sciencedirect.com/science/article/abs/pii/S0950705116300582