Apriori 演算法
Python 的 Market Basket Analysis
Isaiah Hull
Visiting Associate Professor of Finance, BI Norwegian Business School
計算項集數量
$${n \choose k} = \frac{n!}{(n-k)!k!}$$
| 物品數 | 組合大小 | 組合數 |
|---|---|---|
| 3461 | 0 | 1 |
| 3461 | 1 | 3461 |
| 3461 | 2 | 5,987,530 |
| 3461 | 3 | 6,903,622,090 |
| 3461 | 4 | 5,968,181,296,805 |
計算項集數量
$$\sum_{k=0}^{n}{n \choose k} = 2^{n}$$
- $n = 3461 \rightarrow 2^{3461}$
- $2^{3461}>>10^{82}$
- 宇宙中的原子數：約 $10^{82}$。
減少項集數量
- 不可能評估所有項集。
- 甚至連逐一列舉都做不到。
- 如何在未評估前就刪除項集？
- 可設定最大 $k$ 值。
- Apriori 演算法提供另一做法。
- 不需列舉所有項集。
- 以合理規則做修剪。
Apriori 原則
- Apriori 原則。
- 頻繁集的子集也會是頻繁的。
- 保留已知為頻繁的集合。
- 修剪未知為頻繁的集合。
- Candles = 不頻繁
- -> {Candles, Signs} = 不頻繁
- {Candles, Signs} = 不頻繁
- -> {Candles, Signs Boxes} = 不頻繁
- {Candles, Signs, Boxes} = 不頻繁
- -> {Candles, Signs, Boxes, Bags} = 不頻繁
Apriori 實作
# Import Apriori algorithm
from mlxtend.frequent_patterns import apriori
# Load one-hot encoded novelty gifts data
onehot = pd.read_csv('datasets/online_retail_onehot.csv')
# Print header.
print(onehot.head())
50'S CHRISTMAS GIFT BAG LARGE ... ZINC WILLIE WINKIE CANDLE STICK \
0 False ... False
1 False ... False
2 False ... False
3 False ... False
4 False ... False
Apriori 實作
# Compute frequent itemsets
frequent_itemsets = apriori(onehot, min_support = 0.0005,
max_len = 4, use_colnames = True)
# Print number of itemsets
print(len(frequent_itemsets))
3652
Apriori 實作
# Print itemsets
print(frequent_itemsets.head())
support itemsets
0 0.000752 ( 50'S CHRISTMAS GIFT BAG LARGE)
1 0.001504 ( DOLLY GIRL BEAKER)
...
1500 0.000752 (PING MICROWAVE APRON, FOOD CONTAINER SET 3 LO...
1501 0.000752 (WOOD 2 DRAWER CABINET WHITE FINISH, FOOD CONT...
...
一起來練習吧！
Python 的 Market Basket Analysis
