資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
