頻繁項集 的非空子集也必須是頻繁項集 非頻繁項集的任一超集也必然不是頻繁項集 如果K-維頻繁項集集合中包含單個項目i的個數小於K-1,則i不可能在頻繁K項集中（apriori演算法中並沒有用到這個性質，可以藉助這個性質來進行優化，性質會在後面舉例） ...
- apriori演算法的簡介：
- 利用的相關性質：
- 頻繁項集 的非空子集也必須是頻繁項集
- 非頻繁項集的任一超集也必然不是頻繁項集
- 如果K-維頻繁項集集合中包含單個項目i的個數小於K-1,則i不可能在頻繁K項集中（apriori演算法中並沒有用到這個性質，可以藉助這個性質來進行優化，性質會在後面舉例）
- 演算法的主要思想是：
- 第一步，通過迭代，檢索出食物資料庫給中所有的頻繁項集，主要依據用戶設定的最小支持度的閾值
- 第二步，用頻繁項集構造出滿足用戶最小信任度的關聯規則。其中第一步是占演算法的主要計算部分，我們也主要研究的是第一步。
- 迭代過程主要分為連接和剪枝兩個步驟：（由k-1維項集產生K維項集
- 連接：兩個項集的前K-2項相同，最後的K-1項不同，則連接產生的K維項集就是前K-2項加上兩個項集中不同的項
- 剪枝：利用性質一和性質二：如果新產生的項集有存在一個子集不在K-1維的頻繁項集中，則刪掉該新產生的項集
- 演算法的偽代碼
.png)
在第三步產生新的項集之後，需要統計每個項集的頻度，主要採取的演算法是，對資料庫中的每個條目，遍歷一遍候選項集，對每個包含該條目的候選項集計數加一。這樣的話需要重新掃描一遍資料庫，產生大量的計算
- 利用的相關性質：
- 演算法的問題：
- 在計算項目集 的支持度時需要對資料庫的全部記錄進行一遍掃描比較，一般情況下資料庫的規模會很龐大，這樣會極大的增加系統的I/O開銷。
- 在每一步中，產生候選項集時迴圈產生的組合過多，沒有排除不應該參與組合的元素，即沒有用到性質三
- 優化：主要考慮三個方面
- 第一，資料庫的壓縮，如果一個條目（或者說項目）不包含任何一個K-項集，那麼它不可能包含任何一個K+1項集，即在下一次的遍曆數據庫時，不需要再去對該條目進行檢查（通常做法是刪除該條目，或者將這個條目做上標記）。
- 第二，縮小候選項集的個數，即動態項集計數。在某個條目的統計之後，如果發現某個候選項集的計數已經滿足了最小支持度，那麼可以將這個項集直接放入到頻繁項集中，這樣以後就不用對該項集進行計數了
- 第三，在連接的步驟之前，先對項集進行利用性質三進行篩選，提前刪除不滿足的項集。對K-1項項集中的每一個元素進行計數，若某個元素的個數小於K-1，則將K-1項集中刪除包含該元素的項集。這樣可以極大的減小了可能產生的候選項集的數量。
- 優化的步驟如下：
.png)
.png)
.png)
