大神的世界

一. 名字由來

Apriori演算法是經典的挖掘頻繁項集和關聯規則的資料探勘演算法

A priori在拉丁語中指「來自以前」

當定義問題時，通常會使用先驗知識或者假設，這被稱作「一個先驗」(a priori)

Apriori演算法的名字正是基於這樣的事實：

演算法使用頻繁項集性質的先驗性質，即頻繁項集的所有非空子集也一定是頻繁的。

Apriori演算法使用一種稱為逐層搜尋的迭代方法

其中k項集用於探索(k+1)項集。

首先，通過掃描資料庫，累計每個項的計數，並收集滿足最小支援度的項，找出頻繁1項集的集合。

該集合記為L1

然後，使用L1找出頻繁2項集的集合L2

使用L2找出L3，如此下去，直到不能再找到頻繁k項集

每找出一個Lk需要一次資料庫的完整掃描。

Apriori演算法使用頻繁項集的先驗性質來壓縮搜尋空間。

原文網址：https://itw01.com/FYYSEA5.html

二. 基本定義

資料庫（D）：存儲著二維結構的記錄集

所有項集（ I ）：所有項目的集合

記錄 （ T ）：在資料庫里的一筆記錄，T ∈ D

項集 ：同時出現的項的集合。定義為：k-itemset（k項集），k表示項數。

支持度 ：定義為 supp(X) = occur(X) / count(D) = P(X)

置信度 ：定義為 conf(X=>Y) = supp(X ∪ Y) / supp(X) = P(Y|X)

候選集 ：通過向下合併得出的項集。定義為C[k]

頻繁k項集：如果事件A中包含k個元素，那麼稱這個事件A為k項集

事件A滿足最小支持度閾值的事件稱為頻繁k項集。表示為L[k]

強規則：同時滿足最小支持度閾值和最小置信度閾值的規則稱為強規則

原文網址：https://read01.com/mEjNB4.html
 

三. 執行圖 （看圖比較好懂）

出自： https://www.sites.google.com/site/getallcodesyouwant/data-mining/apriori-algorithm

四. 執行步驟 （文字說明）

每個項都是候選1項集的集合C1的成員。

然後對每個項進行計數。

根據最小支援度從C1中刪除不滿足的項，從而獲得頻繁1項集L1。

對L1的自身連線生成的集合執行剪枝策略產生候選2項集的集合C2

掃描所有事務，對C2中每個項進行計數。

根據最小支援度從C2中刪除不滿足的項，從而獲得頻繁2項集L2。

對L2的自身連線生成的集合執行剪枝策略產生候選3項集的集合C3

掃描所有事務，對C3每個項進行計數。

根據最小支援度從C3中刪除不滿足的項，從而獲得頻繁3項集L3。

以此類推

對Lk-1的自身連線生成的集合執行剪枝策略產生候選k項集Ck

掃描所有事務，對Ck中的每個項進行計數。

根據最小支援度從Ck中刪除不滿足的項，從而獲得頻繁k項集。

Ck 來自 Lk-1 透過剪枝策略而得

剪枝策略有一項條件，就是 Ck 的項的子集必須包含在  Lk-1

以 C3 來說，因為 ( 1 , 2 ) 不在 L2 ，因此 (1, 2, 3) 不屬於 C3

原文網址：https://itw01.com/FYYSEA5.html

5. 相關假設

(1) 項集中的項依照字典排序

6. 缺點

耗時，因為每次都要掃描 D

7. Aprioritid

Database只会用到一次

对于每一个 instance 会产生一个集合的集合。

比如 instance = { i1 , i2 , i3 } 那么会产生 { {i1} , {i2} , {i3} }

然后可以用一个数组或者一个 Map 将 < TID , SetOfItemSet > 存放起来

TID一般为数字，对于每一个TID，维持一个和 CandidateK 同步的 K-SetOfItemSet

如果 K-SetOfItemSet 中的 ItemSet 存在于 CandidateK 中，那么 ItemSet.count ++

之所以和 Apriori 殊途同归是因为:对于每一个 < TID , SetOfItemSet >

每一次产生的集合都是 Instances[ TID ] 的子集

而它每次删除的都是一定不会出现在 LargeK 中的 ItemSet。

原文網址： https://blog.csdn.net/mrroylee/article/details/8885385

八. 示意圖

出自： http://www.dbs.ethz.ch/education/oho/SS_99/folien_online/oho-data-mining/sld025.htm

九、總結

Aprioritid 速度較快，因為計算支持度是利用 Ck

Apriori 則是利用 D

另外，Aprioritid 只有在第1次會利用 D 計算 C1