Association - apriori－Lung-Yu,Tsai 的部落格

關聯分析在資料探勘(data mining)中又有人稱之為購物籃分析(market basket anlysis)。

分析資料的交互關係進而發現資料中隱含人們所謂發現的關聯。

早期應用於商務找到消費者的在購物時的消費行為,因此又稱之為購物籃分析。

其中最基礎的演算法為apriori，在該演算法中關鍵的參數為Minimum Support，需定義資料與資料之間的最小相關程度，若制定太高則會難以找到淺在關聯，若制定太低則會有過多關聯資料難以凸顯出有高度價值之資料。

此演算法之演算代號:

* D:Transaction Database，儲存我們所要分析資料的資料庫
* T：Transaction，資料庫中的一筆資料（交易），T ∈ D
* Support：在 D 中，支持該 itemset 的 T 佔有的比例，Support( X ) = Occur( X ) / Count( D ) = P( X )
* Confidence：Conf( X → Y) = Support( X ∪ Y ) / Support( X ) = P( Y | X )
* Candidate Itemset：通過 apriori 合併操作所得到的 itemset
* Frequent Itemset：support 值大於 min support 之 itemset
* C(k)：含有 k 個元素之 candicate itemset 之集合
* L(k)：含有 k 個元素之 frequent itemset 之集合

此演算法主要演算流程:

1. 從 D中找出 C(1)
2. 再掃描 D 找出所有包含 C(1) 的 T，計算其 support，將 C(1) 中不符合 min support 的 itemset 剔除，結果即為 L(1)
3. 自 L(k) 來產生其他的 L(k+1)，直到找 L(k+1) 為空集合（k 由 1 開始）
4. 產生 L(k+1) 的首要步驟為合併 L(k) 來產生 C(k+1)
5. 在 C(k+1) 中，若有某 itemset 其所有含 k 項的 subset 不屬於 L(k)，即可將其自 C(k+1) 剔除
6. 掃描 D 找出所有包含 C(k+1) 的 T，計算其 support，將 C(k+1) 中不符合 min support 的 itemset 剔除，結果即為 L(k+1)
7. 枚舉此 L(k+1) 中的 itemset，將 itemset 分成兩個部份 {A}{B} 的所有可能（其中 A 含有 p 個項目，而 B 含有 (k+1)-p 個項目，1<=p<=(k+1)-1）
8. 判斷 P(itemset) / P(A) 是否大於等於 min confidence，若符合我們可以判斷存在 A => B 的 association rule

以下對演算法之流程進行簡易的流程推演:

已知有許多交易紀錄(如下表)，其中I1表示第一個商品、I2表示第二個商品，T1表示第一個交易紀錄，以此類推。