高效用挖掘是数据挖掘子领域模式挖掘（pattern mining） 的一个研究方向。模式挖掘的目标就是在给定数据库中找到一些新颖的、难以直接观察的、有用的模式。举个例子，我们可以挖掘出基因序列和疾病之间关系，从而帮助研制新药。

而我们要挖掘的数据可以是多样的：

• 关系数据库
• 图
• 文本
• 空间数据
• 序列，时间序列，等等

高效用项集挖掘的一个应用场景是对交易数据（transaction database） 挖掘。我也就以它为例介绍高效用项集挖掘。

设{a, b, c, d, e, …} 为某个商店一次交易所卖出的商品。a，b，c 为商品名，也即item 。则下表可以表示一个交易数据：

Transaction	items
T1	{a, b, c, d, e}
T2	{a, b, e}
T3	{c, d, e}
T4	{a, b, d, e}

频繁项集挖掘是 Agrawal 1993 年提出的问题。该问题可表述为给定一个交易数据且设定参数minsup>=1 , 要求输出所有出现频次大于等于minsup 的项集。例如：

如何去解决这个问题呢？最易想到的就是列出所有可能的项集（itemset），然后统计它们出现的次数。可是对于 n 个item，会有2^n -1种可能，逐一统计是不实际的。这个问题有几个经典的算法：Apriori，FPGrowth，H-Mine，LCM，PrePost 等等。

最经典的Apriori 算法的核心就是反单调性（anti-monotonicity）：设有项集 X 和 Y。如果 X 是 Y 的子集， 那么 Y 出现的次数不大于 X 出现的次数。这样就可以大大减少候选项集。

高效用项集挖掘就是频繁项集挖掘的一个延伸：
- 在同一交易中，items 可以出现超过一次（例如 3 瓶牛奶，两个苹果）
- 每个item 都有自己的利润
- 我们的目标变为找出产生高利润的项集

示例如下：

高效用项集挖掘更有实践意义，因为对于商店来说，他们通常更想要知道什么东西更赚钱，而不太关心它的出现次数。值得注意的是，该问题也可以用在其他领域上，utility不一定代表利润。

这一问题相比频繁项集挖掘更难，因为 utility 不满足反单调性。一个项集的子集产生的利润可能更高也可能更少。

目前有以下一些算法可以解决这一问题：

• Two-Phase（PAKDD 2005）
• IHUP（TKDE 2010）
• UP-Growth（KDD 2011）
• HUI-Miner（CIKM 2012）
• FHM（ISMIS 2014）

他们的核心思想都是找项集uility的上界（upper-bound），例如：TWU,然后再用 Apriori 去缩小搜索空间。

对这方面有兴趣的话我可以提供一个开源网站，里面有几乎所有的高效用挖掘的源码、测试数据、相关文档。

阅读更多

更多精彩内容