频繁子图挖掘算法介绍

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

什么是图?一点理论

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

这个图包含四个顶点(描绘成黄色的圆圈)。这些顶点都有“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的创始人,。

 

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

发表评论

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