高效用项集挖掘介绍

在这篇博文中,我要介绍一个数据挖掘中流行的问题,叫做“高效用项集挖掘”,或者更普遍地说是效用挖掘。我将概述这个问题,解释它为什么令人感兴趣,并为这个问题提供最新的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多种数据挖掘算法。

 

 

 

发表在 大数据, 数据挖掘 | 标签为 , | 留下评论

频繁子图挖掘算法介绍

在这篇博文中,我将介绍一种有趣的数据挖掘算法,叫频繁子图挖掘,它主要用来在图中挖掘有用模式。这一算法非常重要,因为数据在很多领域自然地以图来表示(比如社交网络、化学分子、国家路网)。因此,通过分析图形数据来发现有趣、意外、有用的模式是有必要的,它们可以用来帮助理解数据或者做决策。

什么是图?一点理论

在讨论图分析之前,我们先介绍几个定义。是一组有一些标签顶点。用一个例子来说明一下。参考下图:

这个图包含四个顶点(描绘成黄色的圆圈)。这些顶点都有“10”、“11”等标签。这些标签提供了有关顶点的信息。例如,把这张图想象成一个化学分子。标签10和11可以分别代表氢和氧这两种化学元素。标签不需要是唯一的。换句话说,同一个标签可以用来描述同一个图中的几个顶点。例如,如果上图表示化学分子,则标签”10″和”11″可分别用于代表氧和氢的所有顶点。

除了顶点,图中也包含。边是顶点之间的连线,这里用粗黑线表示。边也有一些标签。在本例中,使用了四个标签,即”20″、”21″、”22″和”23″。这些标签代表了顶点之间不同类型的关系。边的标签不唯一。

图的类型:连通图和非连通图

现实生活中可以找到许多不同类型的图。图分为连通图非连通图。让我们用一个例子来解释一下。参考以下两个图:

左边的图称为连通图,因为沿着边可以从任何顶点到其他顶点。例如,想象一下顶点代表着城市,边是城市之间的道路。这是一个可以沿着道路从一个城市到任何其他城市的连通图。如果图没有连通,则称它是一个非连通图。例如,右边的图是断开的,因为不能沿着边从其他顶点到达顶点A。在下面的文章中,我们将使用术语“图”来表示连通图。因此,我们下面讨论的所有图都是连通图。

图的类型:有向图和无向图

区分有向图和无向图也是很有用的。在无向图中,边是双向的,而在有向图中,边可以是单向的也可以是双向的。让我们用一个例子来说明一下。

左边是无向图,而右边是有向图。在现实生活中有向图的例子有哪些呢?例如,考虑一个图, 它的顶点表示位置,边为道路。有些道路可以双向行驶,而有些道路只能单向行驶(城市中的“单行道”)。

一些数据挖掘算法被设计成只处理无向图、有向图或两者都支持。

分析图

我们已经介绍了一些关于图的理论,那么我们可以做什么样的数据挖掘任务来分析图?这个问题有很多答案。答案取决于我们的目标是什么,也取决于我们正在分析的图的类型(有向图/无向图、连通图/非连通图、单个图或多个图)。

在这篇博文中,我将阐述一个被广泛研究的挖掘任务,称为频繁子图挖掘。子图挖掘的目的是在一组图(图形数据库)中发现令人感兴趣的子图。但我们如何判断一个子图是否令人感兴趣呢?这取决于应用场景。兴趣度可以用各种方式来定义。传统上,如果一个子图在一组图中出现多次,它就被认为是令人感兴趣的。换句话说,我们希望发现多个图共有的子图。例如,找出几种化学分子共有的化学元素, 这种类型的联系是很有用的。

在一组图中查找频繁子图的做法称为频繁子图挖掘。作为输入者,用户必须提供:
图数据库(一组图)
▪一个称为最小支持阈值的参数(minsup)。

然后,频繁子图挖掘算法将枚举输出所有的频繁子图。频繁子图是至少在图数据库中出现minsup次的子图。下面,让我们看一下包含以下三个图的图数据库:

现在,假设我们要发现至少出现在三个图中的所有子图。因此,我们将把最小参数设置为3。通过应用频繁子图挖掘算法,我们将得到至少出现在三个图中的所有子图的集合:

参考一下第三个子图(“频繁子图3”)。这个子图是频繁的,有3个支持度(频度),因为它出现在三个输入图中。这些出现以红色标出,如下:

现在一个重要的问题是如何设置minsup参数?在实际应用中,一般是通过试错法来确定参数。如果此参数设置得太高,则会找到很少的子图,而如果设置得太低,则会根据输入数据库找到数百万的子图。

现在,在实践中,哪些工具或算法可以用来查找频繁的子图?有各种频繁子图挖掘算法。其中最著名的是GASTON, FSG和GSPAN。

在单个图中挖掘频繁子图

除了发现几个图共有的子图外,频繁子图挖掘的问题也有一些变体,它包括在单个图中查找所有频繁子图而不是在图数据库中查找。方法几乎是一样的。目的也是发现频繁出现或令人感兴趣的子图。唯一的区别是支持度(频度)是如何计算的。对于这个变化,子图的支持度是它在单个输入图中出现的次数。例如,参考以下输入图:

这个图包含七个顶点和六个边。如果我们通过将minsup参数设置为2,在这个单图上执行频繁子图挖掘,可以发现以下五个频繁的子图:frequent subgraphs in a graph

这些子图是频繁的,因为它们在输入图中至少出现过两次。例如,参考“频繁子图5”。这个子图有2个支持,因为它在输入图中有两次出现。这两种情况分别用红色和蓝色突出显示在下面。

在图数据库中发现模式的算法通常可以用来发现单个图中的模式。

结论

在这篇博文中,我们介绍了频繁子图挖掘的问题,包括发现在一组图中频繁出现的子图。这个数据挖掘问题已经被研究了15年之多,并提出了许多算法。有些算法是精确算法(会找到正确答案),而有些则是近似算法(不保证找到正确答案,但可能更快)。

一些算法也被设计来处理有向图或无向图,或者在单个图或图数据库中挖掘子图,或者同时做这两种。此外,子图挖掘问题还有其他几种变体,如在图中发现频繁路径,或在图中发现频繁树

此外,在一般数据挖掘中,还研究了与图有关的许多其他问题,如优化问题、社交网络中的社群检测、关系分类等。

对比其它类型的数据, 一般来说,与图有关的问题是相当复杂的。子图挖掘困难的原因之一是算法通常需要检查“子图同构”,即比较子图以确定它们是否等价。尽管如此,我认为这些问题是相当有趣的,因为有一些研究上的挑战。

希望你喜欢这篇博文。如果对这个话题感兴趣,我将来可能会在图挖掘上再写一篇博文。


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

 

发表在 图挖掘, 大数据, 数据挖掘 | 标签为 , , | 留下评论

招收数据挖掘领域博士和博士后,地点:中国,深圳

哈尔滨工业大学(深圳)工业设计研究中心正在招聘一名博士生和两名博士后研究人员进行数据挖掘/大数据方向的研究。

Harbin Institute of Technology (Shenzhen)

招聘条件:

  • 计算机科学博士学位,
  • 数据挖掘人工智能领域有着深厚的研究背景,
  • 在数据挖掘或人工智能领域的优秀会议或期刊上发表过论文,
  • 对数据挖掘算法的开发和应用有浓厚兴趣,
  • 211/ 985大学或国外优秀学校博士学位优先考虑。

成功申请人将:

  • 工作在与时间序列和空间序列相关方面或者其它与数据挖掘领域相关的理论或者工业应用。(确切的主题会根据申请人的优势讨论后确定)。
  • 加入由Philippe Fournier-Viger教授领导的优秀研究团队,Philippe Fournier-Viger教授是流行数据挖掘库SPMF的创始人,并且与其他领域的优秀研究人员有密切合作。
  • 工作在具有先进设备的实验室(实验室配备高端的工作站,用于大数据研究的服务器集群,GPU服务器,虚拟现实设备,身体传感器等)。
  • 以年薪17.6万元人民币聘用两年(其中51600来自学校,120,000来自深圳市政府)。请注意,博士后研究员不需要对工资支付任何税费,学校会提供低价格的租赁公寓(大约1500/月,很大地节省了住宿费用)。
  • 工作在全球计算机科学领域排名前50的大学之一,以及中国排名前10的大学之一。
  • 工作在中国东南部增长最快的城市之一深圳,这里污染低,全年气候温暖,接近香港。

如果您对此职位感兴趣,请尽快发送您的详细简历(包括出版物和参考文献清单)至Philippe Fournier-Viger教授(philfv8@yahoo.com ),可以申请2018年或2019年的博士后名额。

发表在 大数据, 数据挖掘, 研究 | 留下评论