相関マイニング（バスケット分析）

バスケット分析
相関マイニング - 技術編 -

Karubi Namuru
Sep 26th, 2010

自己紹介

●
Karubi Namuru
●
博士（理学）
●
Twitter: @karubi
●
Facebook:
http://facebook.com/karubi
●
出身：広島 , 居住：東京 , Seongnam

今日の内容

●
バスケット分析とはなにか
●
どのようなときに有効か
●
どのように分析しているのか
●
基本的な手順
●
アプリオリアルゴリズム
●
FPGrowth

バスケット分析とはなにか

●
顧客が購入するものについて，「一緒に買われる商品」の組み
合わせを発見するための分析
●
顧客はさまざまな時間に，さまざまな量の，さまざまな商
品を組み合わせて購入する
●
アソシエーションルール
●
データの傾向
●
大量に蓄積している POS データや EC サイトのトランザ
クションデータを使う

どのようなときに有効か

●
たとえば，おむつを買う顧客は同時にビールも買う
●
併売商品の選定
●
商品陳列レイアウト
– 両方の商材を近くに陳列しておくほうが顧客ニーズを満
たす
– 両方の商材をあえて離して陳列して，店舗内の回遊をう
ながす
●
などなど


●
データの３つのレベル
●
顧客
●
アイテムセット
●
品目


デジタルカメラと液晶を保護するためのシートを購入する顧
客は，メモリカードも一緒に買う傾向がある

｛デジタルカメラ，液晶保護シート｝⇒｛メモリカード｝

｛ X ｝⇒｛ Y ｝

基本的な手順

●
全アイテムから全てのルールを洗い出す
●
全アイテムからｋ個を選ぶ
●
この全通りについて，意味のあるルールを見つける
●
このアイテムの各々が前提にくるか，結論にくるかで分け
方が変わる
●
全アイテムが前提に集まる場合と，全アイテムが結論に集
まる場合はルールにならないので排除する

価値のあるルール

●
a 種類のアイテムにおいて存在するルールの数
a

∑
b=2

a b
b
 2 −2

a 個のなかから b 個を選ぶ方法
a
●
 
b
●
b 個について，各々が前提になるか，または結論になるかのわけ
b
方 2
●
全部が前提に集まるか，または結論に集まる場合についてはルー
ルにならないので排除する 2b −2

価値のあるルール続

●
価値のあるルールの数：わずかな数
●
価値のないルールの数：多数（取るにたらない，説明不能）
→ 　効率よく探す必要がある

ある食料品店の例

●
以下のような POS トランザクションがある

顧客アイテム
1 オレンジジュース，炭酸飲料
2 牛乳，オレンジジュース，ガラスクリーナー
3 オレンジジュース，洗剤
4 オレンジジュース，洗剤，炭酸飲料
5 ガラスクリーナー，炭酸飲料


●
商品が同時に購入された数をかぞえてみる

オレンジガラスク牛乳炭酸飲料洗剤
ジュースリーナ
オレンジ 4
ジュース
ガラスク 1 2
リーナ
牛乳 1 1 1
炭酸飲料 2 1 0 3
洗剤 1 0 0 1 2


●
オレンジジュースと炭酸飲料は，他の 2 アイテムよりも一緒に
買われやすい
●
洗剤はガラスクリーナや牛乳とは一緒に買われない
●
牛乳は炭酸飲料や洗剤とは一緒に買われない


●
意味のあるルールかどうか
●
５つのトランザクションのうち，２つで炭酸飲料とオレン
ジジュースが一緒に出てくる
→ この２つのトランザクションがルールを支援している
support = 2/5 (40%)
●
炭酸飲料を含む３つのトランザクションのうち，２つがオ
レンジジュースをふくんでいる
→ 炭酸飲料を買えば，オレンジジュースも買う
confidence = 2/3(66.6%)


●
意味のあるルールかどうか

→ 　 confidence と support が大きいルール


●
炭酸飲料の購買を前提とした場合としない場合の，オレンジ
ジュースが出現する倍率
●
炭酸飲料とオレンジジュースを同時に購入するトランザク
ションは２つ
●
オレンジジュースを含むトランザクションは４つ
– リフト値　 2/4 （ 0.5 ）
– リフト値が１より大きい場合は，結果を前提としてほう
が割合が出現割合が大きくなる


●
それぞれ，最小 confidence と，最小 support のふたつを与
えて，各々のアイテムセットについて，与えられた最小
conficende と，最小 support より，それぞれの値が大きい
アソシエーションルールを発見する方法

support  X ∪Y α
support  X ∪Y / support  X  β


1.　 support ( X ∪ Y ) > α を満たすアイテムセットをすべて探し出
し，それぞれのサポートを計算する

2.　 support ( X ∪ Y ) / support ( X ) > β を満たすルールをさがす


{1,3,4}
{2,4,5}
{2,4,6}

●
全アイテムのサポートを求める
●
各アイテムセットのサポートを求める

{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}
{3, 5}, {4, 5}
●
{2, 4} は 0.66

FPGrowth アルゴリズム

●
アプリオリアルゴリズムの効率を改善するアルゴリズム
●
アプリオリアルゴリズムは全通りについて計算をする必要が
あったが， FPGrowth は FP-Tree という木構造に圧縮し
て， FP-Tree からルールを抽出する．
●
FP-Growth は途中経過に候補となるアイテムセットを生成し
ないため，アイテムセット全体を対象に計算することを抑える
ことができる．

→ つまり，アプリオリより高速にアソシエーションルールを抽
出することができる．


●
データ全体から全てのアイテムセットの support を計算
●
頻出ではないアイテムセットを削除
●
F をサポートの降順にソートする
●
データベースをスキャンして， FP-Tree を作る
●
ルートのラベルは null
●
各ノードは（アイテム名， Count ，次のリンク）
●
ヘッダテーブルは（アイテム名，ノードとのリンク）


{1,3,4}
{2,4,5}
{2,4,6}

サポート降順に　 {4,2,1,3,5,6} root

4
4
2
1
1 2
3
5
6 3 5 6


●
Conditional Pattern Base に分割
●
3 を含む集合
●
1 を含んで３を含まない集合 root

●
４を含んで，１と３を含まない集合
4
4
2
1
1 2
3
5
6 3 5 6

Mahout

PFPGrowth Parallel FP Growth Driver Class.

ParallelFPGrowthCombiner takes each group of dependent transactions
and compacts it in a TransactionTree
structure
ParallelFPGrowthMapper maps each transaction to all unique items
groups in the transaction.

ParallelFPGrowthReducer takes each group of transactions and runs
Vanilla FPGrowth on it and outputs the the To
K frequent Patterns for each group.

まとめ

●
バスケット分析の概要
●
アルゴリズム
●
アプリオリ
●
FP-Growth

●
ご質問は
@karubi or gogokarubi@gmail.com まで

相関マイニング（バスケット分析）

Recommended

Recommended

More Related Content

Featured

Featured (20)

相関マイニング（バスケット分析）