频繁子图挖掘
给定图的集合 和支持度阈值 ,频繁子图挖掘的目标是找到所有满足 的子图 。
约 712 字大约 2 分钟
2024-07-15
一种数据挖掘的任务是在图上发现一组频发出现的子结构,这种任务被称为:频繁子图挖掘(frequent subgraph mining)。阅读本章需要一定的对于图的基础知识,具体内容可以阅读 GFD 相关概念解释。
频繁子图挖掘
给定图的集合 G 和支持度阈值 minsup,频繁子图挖掘的目标是找到所有满足 s(g)≥minsup 的子图 g。
尽管该定义适用于所有类型的图,但是本节讨论的内容还是聚焦于 无向连通图。
频繁子图挖掘的计算量非常大,复杂性主要来自于两点:
坏消息是由于拓扑结构的引入,暴力枚举的方法已经变得不切实际。但是好消息是,先验原理对于子图仍然适用。所以仍然可以沿用 Apriori 方法的一般结构,将该算法分为 3 个主要步骤:候选生成、候选剪枝和支持度计数。
将一对频繁 (k-1)-子图合并成一个候选 k-子图。如果它们共享一个共同的 (k-2)-子图,则称该 (k-2)-子图为 核
。当给定一个共同的核,子图合并过程可以描述如下图:
这与前面第 2 节中提到的 Fk−1×F1 方法非常相似。
在产生候选 k-子图后,需要剪去 (k-1)-子图非频繁的候选项。
维护一个与每个频繁 (k-1)-子图都想关联的图 ID 标。如果新的候选 k-子图通过合并一对频繁 (k-1)-子图生成,就对它们的对应图 ID 表求交集。最后,子图的同构检查就在表中的图上进行。
a1e78
-improve(docs): use chinese punctuation于 1289a
-improve(docs): delete extra whitespace and blank lines于 c2111
-modify(docs): remanage folders and rename files于 aa2df
-docs: update docs于 7577d
-docs: update docs于 92ee3
-docs: update docs于 8f99a
-整理图片和文章于 8224a
-整理文章于 f86ee
-update于 93933
-新增文字+CRLF全部替换为LF于