アイテムの組み合わせ

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

Christopher Bruffaerts

Statistician

食料品店に戻る

店には何がある？

全商品の絵文字

今日は何にしますか？

パン_チーズ3

{"Bread", "Cheese", "Cheese", "Cheese"}

マーケットバスケット分析の焦点

パン_チーズ

{"Bread", "Cheese"}

部分集合と上位集合

私の店 − 集合

X = {"Bread", "Butter", "Cheese", "Wine"}

全商品の絵文字

X の部分集合 − アイテム集合

サイズ 0: { ${ \emptyset }$ }
サイズ 1: {"Bread"}, {"Wine"}, ...
サイズ 2: {"Bread", "Wine"}, ...

上位集合（スーパーセット）

{"Bread", "Butter"} は {"Bread"} の上位集合
{"Bread", "Butter", "Cheese", "Wine"} は {"Bread", "Butter"} の上位集合

アイテム集合グラフ

質問:

X のすべての部分集合の集合は？

X = {A, B, C, D}

アイテム集合の格子

積集合と和集合

積集合

{"Bread"} $\cap$ {"Butter"} = $\emptyset$

{"Bread", "Butter"} $\cap$ {"Butter", "Wine"} = {"Butter"}

library(dplyr)
A = c("Bread", "Butter")
B = c("Bread", "Wine")
intersect(A,B)

[1] "Bread"

和集合

{"Bread"} $\cup$ {"Butter"} = {"Bread", "Butter"}

union(A,B)

[1] "Bread"  "Butter" "Wine"

サイズ k のバスケットはいくつ？

質問:

サイズ n の集合からサイズ k の部分集合はいくつ？

「n 個から k 個を選ぶ」

$${n \choose k} = \dfrac{n!}{(n-k)! k!},$$ ここで

$n! = n \times (n-1) \times (n-2) \times ...\times 2 \times 1$

例:

店の商品から異なる2品のバスケット数:

全商品の絵文字

$${4 \choose 2} = \dfrac{4!}{(4-2)! 2!} = 6$$

可能なバスケット数は？

質問

サイズ n の集合から作れるバスケットは全部でいくつ？

二項定理

$$\sum_{k=0}^n{n \choose k} = 2^n$$

2^(n_items)

例

バスケット総数:

$$2^4 = 16$$

全商品の絵文字

Rでバスケット数を計算

Rでの組合せ

n_items = 4
basket_size = 2
choose(n_items, basket_size)

[1] 6

# すべての値をループ
store = matrix(NA, nrow=5, ncol=2)
for (i in 0:n_items){
  store[i+1,] = c(i, choose(n_items,i))}

出力

colnames(store)=c("size", "nb_combi")
store

     size nb_combi
[1,]    0        1
[2,]    1        4
[3,]    2        6
[4,]    3        4
[5,]    4        1

組合せ数のプロット

組合せ数がどれだけ速く増えるかを把握

n_items = 50
fun_nk = function(x) choose(n_items, x)
# 描画
ggplot(data = data.frame(x = 0),
    mapping = aes(x=x))+
  stat_function(fun = fun_nk)+
  xlim(0, n_items)+
  xlab("Subset size")+
  ylab("Number of subsets")

組合せの分布

数える準備はいいですか？

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