Apriori algorithm[關聯規則演算法]

聽說Apriori algorithm是Data mining的始祖演算法

history:
1993年：提出關聯法則之數學模式( Agrawal et. al.)
1994年：Apriori演算法為最早被提出之關聯法則( Agrawal & Sirkant)
1995年：以Apriori演算法為基礎，加入時間屬性概念，
提出Mining Sequential Pattern (MSP)演算法，用於
發掘序列型樣或循序特徵 ( Agrawal & Srikant)

整理資料：

• Apriori 是學習「association rules」的經典演算法
• 試圖去找出滿足threshold最常見、出現的子集合
• Apriori uses a "bottom up" approach
• frequent subsets are extended one item at a time (candidate generation)
• Apriori uses breadth-first search and a tree structure to count candidate item sets

Apriori將關聯法則的發掘問題區分為：
找出 frequent itemset(就是Large)
由frequent itemset推導出association rule (關聯規則)
Apriori的困難與瓶頸：
產量大量Candidate
多次掃描資料庫
Terminology

D: Dataset
|D|: Dataset length
C: Candidate
L: Large
Lk: Large k-itemset (符合min support的dataset)
Ck+1: Lk 中 dataset 兩兩 join 成長度為 k+1之候選 dataset
large=frequent= covering=interesting=relevant