数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究我们如何发现频繁子结构？
频繁子结构的发现通常包括两个步骤。第一步是生成频繁子结构候选。第二步测试每个候选的频率。大多数关于频繁子结构发现的研究都集中在第一步的优化上，因为第二步涉及子图同构测试，其计算复杂度过高（即 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 边图。重复发现同一个图在计算上效率低下。我们将第二次被发现的图称为重复图。
它可以减少重复图的生成，每个频繁图都应尽可能保守地扩展。这一原则导致了几种新算法的设计。生成算法旨在减少重复图的生成。它不需要搜索先前发现的频繁图进行重复检测。它不扩展任何重复图，但仍然保证发现完整的一组频繁图。
272 次浏览
