Tag Archives: pattern mining

This post is a Chinese introduction to frequent subgraph mining (English here). 在这篇博文中，我将介绍一种有趣的数据挖掘算法，叫频繁子图挖掘，它主要用来在图中挖掘有用模式。这一算法非常重要，因为数据在很多领域自然地以图来表示(比如社交网络、化学分子、国家路网)。因此，通过分析图形数据来发现有趣、意外、有用的模式是有必要的，它们可以用来帮助理解数据或者做决策。 什么是图？一点理论… 在讨论图分析之前，我们先介绍几个定义。图是一组有一些标签的顶点和边。用一个例子来说明一下。参考下图： 这个图包含四个顶点（描绘成黄色的圆圈）。这些顶点都有“10”、“11”等标签。这些标签提供了有关顶点的信息。例如，把这张图想象成一个化学分子。标签10和11可以分别代表氢和氧这两种化学元素。标签不需要是唯一的。换句话说，同一个标签可以用来描述同一个图中的几个顶点。例如，如果上图表示化学分子，则标签”10″和”11″可分别用于代表氧和氢的所有顶点。 除了顶点，图中也包含边。边是顶点之间的连线，这里用粗黑线表示。边也有一些标签。在本例中，使用了四个标签，即”20″、”21″、”22″和”23″。这些标签代表了顶点之间不同类型的关系。边的标签不唯一。 图的类型：连通图和非连通图 现实生活中可以找到许多不同类型的图。图分为连通图或非连通图。让我们用一个例子来解释一下。参考以下两个图： 左边的图称为连通图，因为沿着边可以从任何顶点到其他顶点。例如，想象一下顶点代表着城市，边是城市之间的道路。这是一个可以沿着道路从一个城市到任何其他城市的连通图。如果图没有连通，则称它是一个非连通图。例如，右边的图是断开的，因为不能沿着边从其他顶点到达顶点A。在下面的文章中，我们将使用术语“图”来表示连通图。因此，我们下面讨论的所有图都是连通图。 图的类型：有向图和无向图 区分有向图和无向图也是很有用的。在无向图中，边是双向的，而在有向图中，边可以是单向的也可以是双向的。让我们用一个例子来说明一下。 左边是无向图，而右边是有向图。在现实生活中有向图的例子有哪些呢？例如，考虑一个图, 它的顶点表示位置，边为道路。有些道路可以双向行驶，而有些道路只能单向行驶（城市中的“单行道”）。 一些数据挖掘算法被设计成只处理无向图、有向图或两者都支持。 分析图 我们已经介绍了一些关于图的理论，那么我们可以做什么样的数据挖掘任务来分析图？这个问题有很多答案。答案取决于我们的目标是什么，也取决于我们正在分析的图的类型（有向图/无向图、连通图/非连通图、单个图或多个图）。 在这篇博文中，我将阐述一个被广泛研究的挖掘任务，称为频繁子图挖掘。子图挖掘的目的是在一组图（图形数据库）中发现令人感兴趣的子图。但我们如何判断一个子图是否令人感兴趣呢？这取决于应用场景。兴趣度可以用各种方式来定义。传统上，如果一个子图在一组图中出现多次，它就被认为是令人感兴趣的。换句话说，我们希望发现多个图共有的子图。例如，找出几种化学分子共有的化学元素, 这种类型的联系是很有用的。 在一组图中查找频繁子图的做法称为频繁子图挖掘。作为输入者，用户必须提供：▪图数据库(一组图)▪一个称为最小支持阈值的参数(minsup)。 然后，频繁子图挖掘算法将枚举输出所有的频繁子图。频繁子图是至少在图数据库中出现minsup次的子图。下面，让我们看一下包含以下三个图的图数据库： 现在，假设我们要发现至少出现在三个图中的所有子图。因此，我们将把最小参数设置为3。通过应用频繁子图挖掘算法，我们将得到至少出现在三个图中的所有子图的集合： 参考一下第三个子图（“频繁子图3”）。这个子图是频繁的，有3个支持度（频度），因为它出现在三个输入图中。这些出现以红色标出，如下： 现在一个重要的问题是如何设置minsup参数？在实际应用中，一般是通过试错法来确定参数。如果此参数设置得太高，则会找到很少的子图，而如果设置得太低，则会根据输入数据库找到数百万的子图。 现在，在实践中，哪些工具或算法可以用来查找频繁的子图？有各种频繁子图挖掘算法。其中最著名的是GASTON, FSG和GSPAN。 在单个图中挖掘频繁子图 除了发现几个图共有的子图外，频繁子图挖掘的问题也有一些变体，它包括在单个图中查找所有频繁子图而不是在图数据库中查找。方法几乎是一样的。目的也是发现频繁出现或令人感兴趣的子图。唯一的区别是支持度（频度）是如何计算的。对于这个变化，子图的支持度是它在单个输入图中出现的次数。例如，参考以下输入图： 这个图包含七个顶点和六个边。如果我们通过将minsup参数设置为2，在这个单图上执行频繁子图挖掘，可以发现以下五个频繁的子图： 这些子图是频繁的，因为它们在输入图中至少出现过两次。例如，参考“频繁子图5”。这个子图有2个支持，因为它在输入图中有两次出现。这两种情况分别用红色和蓝色突出显示在下面。 … Continue reading →