Aprioriアルゴリズム

Python で学ぶマーケットバスケット分析

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の原理
- 頻出集合の部分集合も頻出。
- 頻出と判明した集合を保持。
- 頻出と未判明の集合を刈り込む。

キャンドル = 非頻出
- -> {キャンドル, サイン} = 非頻出
{キャンドル, サイン} = 非頻出
- -> {キャンドル, サイン, ボックス} = 非頻出
{キャンドル, サイン, ボックス} = 非頻出
- -> {キャンドル, サイン, ボックス, バッグ} = 非頻出

Aprioriの実装

# Aprioriアルゴリズムをインポート
from mlxtend.frequent_patterns import apriori

# ワンホット化したノベルティギフトのデータを読み込み
onehot = pd.read_csv('datasets/online_retail_onehot.csv')

# 先頭を表示
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の実装

# 頻出アイテム集合を計算
frequent_itemsets = apriori(onehot, min_support = 0.0005, 
                            max_len = 4, use_colnames = True)

# アイテム集合数を表示
print(len(frequent_itemsets))

Aprioriの実装

# アイテム集合を表示
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...
...

Passons à la pratique !

Python で学ぶマーケットバスケット分析