如何发现频繁子结构?
频繁子结构的发现通常包含两个步骤。第一步，生成频繁子结构候选集。第二步，测试每个候选集的频率。大多数关于频繁子结构发现的研究都集中在第一步的优化上，因为第二步涉及子图同构测试，其计算复杂度过高(即NP完全问题)。
频繁子结构挖掘有多种方法，具体如下 −
基于Apriori的方法 − 基于Apriori的频繁子结构挖掘算法与基于Apriori的频繁项集挖掘算法具有相同的特征。频繁图的搜索从"规模"较小的图开始，并通过使候选集具有额外的顶点、边或路径，以自下而上的方式进行。图大小的表示取决于所使用的算法。
基于 Apriori 的子结构挖掘算法的主要设计复杂度在于候选集生成步骤。频繁项集挖掘中的候选集生成是真实的。例如，假设我们有两个大小为 3 的频繁项集:(abc) 和 (bcd)。
由它们生成的大小为 4 的频繁项集候选集很容易通过连接变为 (abcd)。然而，频繁子结构挖掘中的候选集生成问题比频繁项集挖掘中的更难，因为连接两个子结构的方法有很多种。
模式增长方法 − 基于 Apriori 的方法必须使用广度优先搜索 (BFS) 策略，因为它的候选集生成是逐级的。要确定大小为 (k + 1) 的图是否频繁，必须检查其所有对应的大小为 k 的子图，以获得其频率的上限。因此，在挖掘任何大小为 (k +1) 的子图之前，类 Apriori 方法通常必须完成大小为 k 的子图的挖掘。
因此，广度优先搜索 (BFS) 对于类 Apriori 方法是必不可少的。相比之下，模式增长方法在搜索方法上更具动态性。它可以使用广度优先搜索和深度优先搜索 (DFS)，后者消耗的内存更少。
模式增长图简单，但效率不高。瓶颈在于扩展图的效率低下。同一张图可能会被发现多次。例如，可能存在 n 个不同的 (n - 1) 条边图，它们可以扩展为同一个 n 条边的图。重复发现同一张图在计算上效率低下。我们将再次被发现的图称为重复图。
为了减少重复图的生成，每个频繁图都应尽可能保守地进行扩展。这一原则促成了几种新算法的设计。生成算法旨在减少重复图的生成。它无需搜索先前发现的频繁图进行重复检测。它不扩展任何重复图，但仍能保证发现完整的频繁图集合。
