資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Apriori演算法的複雜度是多少？
Apriori演算法的計算複雜度受以下因素影響：
支援度閾值 -降低支援度閾值會導致更多項集被認為是頻繁的。這會對演算法的計算複雜度產生不利影響，因為需要生成和計算更多候選項集。
頻繁項集的最大大小也會隨著支援度閾值的降低而增加。隨著頻繁項集最大大小的增加，演算法需要對資料集進行更多次掃描。
項數（維數） -隨著項數的增加，需要更多空間來儲存項的支援度計數。如果頻繁項的數量也隨著資料的維數增加而增加，則由於演算法生成的候選項集數量增加，計算和I/O開銷也會增加。
事務數 -由於Apriori演算法需要對資料集進行多次掃描，因此其執行時間會隨著事務數的增加而增加。
平均事務寬度 -對於稠密資料集，平均事務寬度可能很高。這會透過兩種方式影響Apriori演算法的複雜度：隨著平均事務寬度的增加，頻繁項集的最大大小也會增加。事務寬度增加，事務中包含的項集更多。這將增加支援度計數期間執行的多次雜湊樹遍歷。
頻繁l-項集的生成 -對於每個事務，需要更新事務中每個項的支援度計數。假設w是平均事務寬度，此操作需要O(Nw)時間，其中N是事務總數。
候選集生成 -它可以生成候選k-項集，透過組合頻繁(k - 1)-項集的每一對來確定它們是否至少有k - 2個共同項。每個組合操作最多需要k - 2次相等性比較。在最佳情況下，每個組合步驟都會生成一個有效的候選k-項集。
在最壞情況下，演算法需要組合先前迭代中找到的每對頻繁(k - 1)-項集。因此，合併頻繁項集的總成本為
$$\mathrm{\displaystyle\sum\limits_{k=2}^w\:(k-2)|C_{k}|<\:合併成本\:<\displaystyle\sum\limits_{k=2}^w\:(k-2)|F_{k}-1|^2}$$
在候選集生成過程中還會生成雜湊樹來儲存候選項集。由於樹的最大深度為k，因此使用候選項集填充雜湊樹的成本為O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$) 。
在候選集剪枝過程中，需要檢查每個候選k-項集的k - 2個子集是否頻繁。由於在雜湊樹中查詢候選的成本為O(k)，因此候選集剪枝步驟需要O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)時間。
瀏覽量：1K+
