高效用项集挖掘介绍

在这篇博文中,我要介绍一个数据挖掘中流行的问题,叫做“高效用项集挖掘”,或者更普遍地说是效用挖掘。我将概述这个问题,解释它为什么令人感兴趣,并为这个问题提供最新的Java算法实现的源代码以及数据集。

频繁项集挖掘
高效用项集挖掘问题是频繁模式挖掘问题的延伸。频繁模式挖掘是数据挖掘中的一个常见问题,包括在交易数据库中查找频繁模式。我来描述一下频繁项集挖掘的第一个问题。

参考下面的数据库。它是一个交易数据库交易数据库是包含一组客户交易的数据库。交易是顾客购买的一组物品。例如,在以下数据库中,第一个客户购买了”a”、”b”、”c”、”d”和”e”,而第二个客户购买了”a”,”b”和”e”。


          交易数据库

频繁项集挖掘的目的是寻找频繁项目集。针对这一问题,人们提出了许多流行的算法,如 Apriori算法、FPGrowth,算法、LCM算法、Eclat算法等。这些算法将交易数据库和称为最小支持度阈值的参数“minsup”作为输入。然后,这些算法返回至少在minsup交易中出现的所有项(项集)。例如,如果设置minsup=2,在我们的例子中,会找到一些这样的项集(称为频繁项集),如下:


          一些频繁项集

例如,参考项集{b,d,e}。它的支持度为3,因为它出现在三个交易中,并且被认为频繁,因为{b,d,e}的支持度不少于minsup

频繁项集挖掘有一些重要的局限性
频繁项集挖掘的问题很普遍。但在分析客户交易时,它有一些重要的局限性。一个重要的局限性是购买数量没有被考虑在内。那么,一个项目可能在一个交易中出现一次或零次。因此,如果一个顾客买了五个面包,十个面包或者二十个面包,被看做是一样的。

第二个重要的局限性是所有项都被视为具有同等的重要性,等重的效用。例如,顾客购买一瓶非常昂贵的葡萄酒或者一块便宜的面包,被认为是同样重要的。
因此,频繁模式挖掘可能找到许多不令人感兴趣的频繁模式。例如,你可能发现{面包,牛奶}是一种频繁模式。然而,从商业角度来看,这种模式可能并不令人感兴趣,因为它不会产生多少利润。此外,频繁模式挖掘算法可能错失了产生高利润的模式,例如{鱼子酱,葡萄酒}。

高效用项集挖掘
为了解决这些局限性,频繁项集挖掘问题被重新定义为高效用项集挖掘问题。在此问题中,交易数据库包含考虑了采购量以及每项交易的单位利润的交易,参考以下交易数据库。


包含物品数量和单位利润信息的交易数据库

参考交易T3,表示相应客户购买了两个单位的”a”项、六个单位的”c”项和两个单位的”e”项。再看看右边的表格,显示了每个项目的单位利润。例如,”a”、”b”、”c”、”d”和”e”项的单位利润分别为5美元、2美元、1美元、2美元和3美元。这意味着,出售的”a”的每个单位的利润为5美元。
高效用项集挖掘的问题是在数据库中找到在一起销售时产生高利润的项集(项组)。用户必须为称为”minutil“(最低效用阈值)的阈值提供一个值。高效用项集挖掘算法输出所有高效用项集,即产生最小“minutil”利润的项集。例如,参考用户将“minutil”设置为25美元。高效用项集挖掘算法的结果如下。


             高效用项集

例如,参考项集{b,d}。它被认为是一个高效用项集,因为它有40$的效用(产生40$的利润),这不低于用户已经设定为25$的 minutil。现在,让我们更详细地了解如何计算一个项集的效用(利润)。一般来说,交易中一个项集的效用是每个项集的数量乘以其单位利润。例如,参考下图,在T0交易中{a,e}的利润是1 x 5+1 x 3=8$。同样,{a,e}在交易T3中的利润是2 x 5+2 x 3=16$。现在,整个数据库中项集的效用是它出现在所有交易中的效用之和。因此,对于{a,e},它的效用是总和8$+16$=24$,因为它只出现在T0交易和T3交易中。


     如何计算项集{a,e}效用的说明

为什么高效用项集挖掘的问题令人感兴趣?
由于以下原因,高效用项集挖掘的问题相当令人感兴趣。
首先,从实际的角度来看,发现在客户交易中产生高利润的物品比那些经常购买的物品更有趣。

其次,从研究的角度来看,高效用项集挖掘的问题更具挑战性。在频繁项集挖掘中,关于项集的频度(支持度)有一个非常重要的性质,即一个项集的超集的支持度一定小于或等于该项集本身,通常被称为“Apriori 性质”或“反单调性”。这一性质可以有力地减小搜索空间,因为如果一个项集不频繁,那么我们知道它的所有超集也不频繁,那么我们就不用考虑它的任何超集。在高效用项集挖掘中,这一性质不成立。也就是说=一个项集的超集的效用可能高于、低于或等于该项集本身。例如,在前面的例子中,项集{a},{a,e}和{a,b,c}的效用分别为20$,24$和16$。

在这篇博文中,我将不详细介绍高效用项集挖掘算法的工作原理。但是一个关键的思想是使用具有反单调性的效用上界,以便能够减小搜索空间。
开源实现和数据集

近年来提出了几种高效用项集挖掘算法。我的开源数据挖掘库SPMF中提供了目前Java实现的最先进的算法。例如,它提供了Two-Phase算法(2005年)、UPGrowth算法(2011年)、HUI-Miner算法(2012年)和 FHM算法(2014年)的源代码。据我们所知, FHM算法是解决这个问题的最快算法之一。结果表明,它的速度是HUI-Miner算法的六倍,是UPGrowth算法的100倍,是Two-Phase算法的1000倍。你可以去SPMF网站试试FHM算法和上面的其他算法。在网站上,你将找到关于如何运行算法的说明以及数据集页面上的一些数据集。更新:最近,EFIM算法(2015年)被提出,并显示出超过FHM算法 1000倍,并且在SPMF中也有提供。

请注意,在高效用项集挖掘问题上也存在着一些变化,我在这篇博文中不会涉及这些变化。

结论
在这篇博文中,我概述了高效用项集挖掘问题的定义,希望你们喜欢。我将努力在未来继续发布类似这样有趣的数据挖掘问题的博文。希望你们喜欢阅读。

Philippe Fournier-Viger是计算机科学教授,也是开源数据挖掘软件SPMF的创始人,提供了120多种数据挖掘算法。

 

 

 

此条目发表在大数据, 数据挖掘分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注