Sparkでバスケット分析（１）

#マーケットバスケット分析とは

「金曜日の夜はオムツとビールが一緒に買われる」という例のあれです。バスケット分析では支持度(support),確信度(confidence),リフト(lift)の３つの指標を売上データから計算します。この記事はPySparkを使って実装するのが目的です。分析方法は他記事をご覧ください。Qiitaにもいくつかあります。

# 定義


```math
支持度(A⇒B)=P(A∩B)=\frac{AとBが含まれるカゴの数}{カゴの総数} 
```

```math
確信度(A⇒B) = \frac{P(A∩B)}{P(A)}=\frac{AとBが含まれるカゴの数}{Aが含まれるカゴの総数} 
```

```math
期待確信度(A⇒B) = P(B)=\frac{Bが含まれるカゴの数}{カゴの総数} 
```

```math
リフト(A⇒B) = \frac{P(A∩B)}{P(A)P(B)}=\frac{確信度}{期待確信度}
```





#サンプルデータ
R言語のアソシエーション分析の例題で用いられる[Groceries](https://github.com/stedy/Machine-Learning-with-R-datasets/blob/master/groceries.csv)を利用させてもらいます。解説記事やYoutubeのビデオもたくさんありますので、計算結果の確認が楽です。このファイルは1行が1バスケットになっていて、合計9835個のバスケットのデータが入っています。一行をトランザクションと呼ぶこともあります。先頭五行は次の通り。

```csv:groceries.csv
citrus fruit,semi-finished bread,margarine,ready soups
tropical fruit,yogurt,coffee
whole milk
pip fruit,yogurt,cream cheese ,meat spreads
other vegetables,whole milk,condensed milk,long life bakery product
```

# 支持度の計算

```py:support.py
# -*- coding: utf-8 -*-
import sys
from itertools import combinations
from pprint import pprint
from pyspark import SparkContext


# データ読み込み。トリムして小文字に正規化
sc = SparkContext()
baskets = (
    sc.textFile(sys.argv[1])
    .map(lambda row: set([word.strip().lower() for word in row.split(",")]))
).cache()

# カゴの総数
total = float(baskets.count())
 
result = (
    baskets
    # バスケットにIDを振る
    .zipWithIndex()

    # 商品のペアを作る。ソートするのは安定したペアにするため。
    .flatMap(lambda (items, basket_id): ((tuple(sorted(c)), (basket_id,)) for c in combinations(items, 2)))

    # 商品のペアをキーとして、バスケットの数を数える
    .reduceByKey(lambda a, b: a + b)
    .map(lambda pair_baskets: (pair_baskets[0], len(pair_baskets[1])))

    # 支持度を追加
    .map(lambda pair_count: (pair_count[0], (pair_count[1], pair_count[1] / total * 100)))

    # 支持度で降順にソート
    .sortBy(lambda (pair, stats): -stats[1])
)

# 支持度トップ10を表示
pprint(result.take(10))

```

## 支持度の結果

(野菜, ミルク)が全体9835のうち頻度736で支持度7.48%でトップでした。以下パンとミルク、ミルクとヨーグルトなどなど欧米人のデータだろうから順当な結果が得られています。

```shell-session
$ spark-submit support.py groceries.csv

[((u'other vegetables', u'whole milk'), (736, 7.483477376715811)),
 ((u'rolls/buns', u'whole milk'), (557, 5.663446873411286)),
 ((u'whole milk', u'yogurt'), (551, 5.602440264361973)),
 ((u'root vegetables', u'whole milk'), (481, 4.89069649211998)),
 ((u'other vegetables', u'root vegetables'), (466, 4.738179969496695)),
 ((u'other vegetables', u'yogurt'), (427, 4.341637010676156)),
 ((u'other vegetables', u'rolls/buns'), (419, 4.260294865277071)),
 ((u'tropical fruit', u'whole milk'), (416, 4.229791560752415)),
 ((u'soda', u'whole milk'), (394, 4.006100660904932)),
 ((u'rolls/buns', u'soda'), (377, 3.833248601931876))]
```

ならワースト10はなんなのか、ちょっと寄り道して見てみましょう。sortByのオーダーを`stats[1]`にすればOKですね。マヨネーズと白ワイン、ブランデーとアメ、ガムと赤ワイン、人工甘味料とドッグフード、電球とジャム、などなど笑える結果になりました。

```
[((u'mayonnaise', u'white wine'), (1, 0.010167768174885612)),
 ((u'chewing gum', u'red/blush wine'), (1, 0.010167768174885612)),
 ((u'chicken', u'potato products'), (1, 0.010167768174885612)),
 ((u'brandy', u'candy'), (1, 0.010167768174885612)),
 ((u'chewing gum', u'instant coffee'), (1, 0.010167768174885612)),
 ((u'artif. sweetener', u'dog food'), (1, 0.010167768174885612)),
 ((u'meat spreads', u'uht-milk'), (1, 0.010167768174885612)),
 ((u'baby food', u'rolls/buns'), (1, 0.010167768174885612)),
 ((u'baking powder', u'frozen fruits'), (1, 0.010167768174885612)),
 ((u'jam', u'light bulbs'), (1, 0.010167768174885612))]
```

# 確信度の計算
確信度は(X⇒Y)と(Y⇒X)は別物なので、全件を列挙するのにcombinationsではなくpermutationsを使いました。

```py:confidence.py
# -*- coding: utf-8 -*-
import sys
from itertools import permutations, combinations
from pprint import pprint
from pyspark import SparkContext


# データ読み込み。トリムして小文字に正規化
sc = SparkContext()
baskets = (
    sc.textFile(sys.argv[1])
    .map(lambda row: set([word.strip().lower() for word in row.split(",")]))
).cache()

# カゴの総数
total = float(baskets.count())

# バスケットにIDを振る
baskets_with_id = baskets.zipWithIndex()

# (商品のペア, それが含まれるバスケットの数)を作る。
pair_count = (
    baskets_with_id
    .flatMap(lambda (items, basket_id): [(pair, (basket_id,)) for pair in permutations(items, 2)])
    # 商品のペアをキーとして、それが含まれるバスケットのリストを作る
    .reduceByKey(lambda a, b: a + b)
    # バスケットの数を数えて追加 (pair, count)
    .map(lambda pair_baskets: (pair_baskets[0], len(pair_baskets[1])))
)

# 商品Xが含まれるバスケットの数
x_count = (
    baskets_with_id
    .flatMap(lambda (items, basket_id): [(x, (basket_id,)) for x in items])
    # 商品Xが含まれるバスケットのIDのリストを作る
    .reduceByKey(lambda a, b: a + b)
    # バスケットの数を数えて追加 (x, count)
    .map(lambda x_baskets: (x_baskets[0], len(x_baskets[1])))
)

# 確信度をXについて計算する
confidence = (
    pair_count
    # XをキーにJOINできるように変形
    .map(lambda (pair, count): (pair[0], (pair, count)))
    .join(x_count)

    # 確信度を追加
    .map(lambda (x, ((pair, xy_count), x_count)): (pair, (xy_count, x_count, float(xy_count) / x_count * 100)))
    
    # 確信度で降順にソート
    .sortBy(lambda (pair, stats): -stats[2])
)

pprint(confidence.take(10))



```
## 確信度の結果

結果は((商品X, 商品Y), (XYが含まれるカゴの数, Xが含まれるカゴの数、確信度%))のタプルになっています。確信度でソートしたところ、100%の確信度ではありますが、1度だけ出現するレアな組み合わせの例ばかりになってしまいました。

```
$ spark-submit confidence.py groceries.csv

[((u'baby food', u'waffles'), (1, 1, 100.0)),
 ((u'baby food', u'cake bar'), (1, 1, 100.0)),
 ((u'baby food', u'dessert'), (1, 1, 100.0)),
 ((u'baby food', u'brown bread'), (1, 1, 100.0)),
 ((u'baby food', u'rolls/buns'), (1, 1, 100.0)),
 ((u'baby food', u'soups'), (1, 1, 100.0)),
 ((u'baby food', u'chocolate'), (1, 1, 100.0)),
 ((u'baby food', u'whipped/sour cream'), (1, 1, 100.0)),
 ((u'baby food', u'fruit/vegetable juice'), (1, 1, 100.0)),
 ((u'baby food', u'pastry'), (1, 1, 100.0))]
```

そこで[Xが含まれるカゴの数,XYが含まれるカゴの数]でソートしてみたところ、次のような結果になりました。もっとも買われるのはミルクで、野菜やパン、ヨーグルトなどが一緒に買われる確信度が11%から29%と言う結果になりました。

```
[((u'whole milk', u'other vegetables'), (736, 2513, 29.287703939514525)),
 ((u'whole milk', u'rolls/buns'), (557, 2513, 22.16474333465977)),
 ((u'whole milk', u'yogurt'), (551, 2513, 21.92598487863112)),
 ((u'whole milk', u'root vegetables'), (481, 2513, 19.140469558296857)),
 ((u'whole milk', u'tropical fruit'), (416, 2513, 16.55391961798647)),
 ((u'whole milk', u'soda'), (394, 2513, 15.678471945881418)),
 ((u'whole milk', u'bottled water'), (338, 2513, 13.450059689614008)),
 ((u'whole milk', u'pastry'), (327, 2513, 13.01233585356148)),
 ((u'whole milk', u'whipped/sour cream'), (317, 2513, 12.614405093513728)),
 ((u'whole milk', u'citrus fruit'), (300, 2513, 11.937922801432551))]
```

# リフトの計算
ソースコード蒸発。見つかり次第掲載します。

# リフトの結果

ともかく、つまみらしきものを買う人は、単独でそれを買うよりも、酒と一緒に買う傾向が強く裏付けられました（笑。

```
[((u'cocoa drinks', u'preservation products'), 22352.27272727273),
 ((u'preservation products', u'cocoa drinks'), 22352.272727272728),
 ((u'finished products', u'baby food'), 15367.1875),
 ((u'baby food', u'finished products'), 15367.1875),
 ((u'baby food', u'soups'), 14679.104477611942),
 ((u'soups', u'baby food'), 14679.10447761194),
 ((u'abrasive cleaner', u'preservation products'), 14050.000000000002),
 ((u'preservation products', u'abrasive cleaner'), 14050.0),
 ((u'cream', u'baby cosmetics'), 12608.97435897436),
 ((u'baby cosmetics', u'cream'), 12608.974358974358)]
```

# まとめ
以上PySparkでマーケットバスケット分析を行いました。

この記事は大昔に書いて下書きのままになっていたので、現在のpysparkでは動かないところがあるかもしれません。