データ工学特論

データ工学特論
第三回
木村昌臣
本日の話題



マーケットバスケット分析
記憶ベース推論
クラスタリング
マーケットバスケット分析
マーケットバスケット分析


買い物かごや
取引レコードでどの
アイテムが一緒に
買われる傾向があるかを分
析
分析をもとにアクションをと
りやすい（実行可能）



レイアウト計画
特売商品の品目調整
製品のバンドルの仕方
など
おむつ
ビール
つまみ
マーケットバスケット分析で得られるもの

結果はアソシエーションルールとして得られる



商品Pを買う ⇒ 商品Qを買う
一緒に買われるものがわかるので実行に移しやすい
ただし、すべての結果（アソシエーションルール）が
有益とは限らない



木曜日には顧客はビールと紙おむつを一緒に買う
製品保証契約をつけた顧客は大型家電を買う
店のオープン時にはトイレットリングがよく売れる
マーケットバスケット分析で得られるもの

結果はアソシエーションルールとして得られる
有益!
商品Pを買う ⇒ 商品Qを買う
 一緒に買われるものがわかるので実行に移しやすい
説明はつくが得
 ただし、すべての結果（アソシエーションルール）が
られていなかっ
既存の知識
有益とは限らない
た知識




木曜日には顧客はビールと紙おむつを一緒に買う
大型家電を買う顧客は製品保証契約をつける
店のオープン時にはトイレットリングがよく売れる
説明不可能
マーケットバスケット分析の方法
オレンジジュース⇒炭酸飲料
信頼性: 2/4 = 0.5 (50%)
サポート: 2/5 = 0.4 (40%)
炭酸飲料⇒オレンジジュース
信頼性: 2/3 = 0.67 (67%)
サポート： 2/5=0.4(40%)
オレンジジュース
を買ったときに
それぞれを
買った回数
信頼性・サポート・リフト
の値が大きいルールのみ
採用する
信頼性・サポート・リフト

信頼性=商品Bが買われたときの商品Aの購入確率（条
件付確率）
N ( A  B)
P( A | B) 

N ( B)
サポート=商品Aと商品Bの同時購入確率
N ( A  B)
P( A  B) 
N

リフト=商品B購入が条件の商品Aの購入確率と、商品A
の購入確率の比(商品Bを購入したという事実が商品A
の購入確率をどれだけ改善するかの指標)
P( A | B) N ( A  B)  N

P( A)
N ( B) N ( A)
手順
1.
アイテムの水準と内容を正しく設定


「ピザ」をアイテムにする？
トッピングに応じて別アイテムにする？
2.
同時購買表を解読してルールを生成
3.
実行上の制限の克服
手順1. アイテムの水準と内容を適切
に選ぶ
ピザ
抽象
○ 分析しやすい
（組み合わせが少なくてすむ）
× 詳細な情報が落ちる
チーズ増量ピザ
オニオンピザ
マッシュルームピザ
○ 特定のアイテムに焦点を当てた
分析ができる
具体
× ルールが複雑になり、
分析に時間がかかる
バーチャルアイテム
バーチャルアイテム
実際には商品そのものとして
存在しないが
含めると解析が便利になる
仮想アイテム
コカコーラ製品
まとめたもの
支払方法
（カード？現金？）
ダイエットコーク
コカコーラ
コカコーラC2
季節
手順2.同時購買表を解読してルール
を生成
ルール：
もし「前件部」が成立すれば「後件部」も成立する
「前件部 ⇒ 後件部」と書く
例）
（買ったものが）もし「オレンジジュース」であれば
（いっしょに買うのは）「炭酸飲料」である
同時購買表には、「アイテムのどの組合わせがもっとも多いか」についての情報が
提供されている
手順3. 実行上の制限の克服

アソシエーションルールの生成は多段階




単一のアイテムについての同時出現表を作成
2つのアイテムについての同時出現表を作成し、2アイテ
ム間のルールを生成
3つのアイテムについての同時出現表を作成し、3アイテ
ム間のルールを生成
4つのアイテムについての同時出現表を作成し、4アイテ
ム間のルールを生成
以下同様。アイテム数をAとすると、
全部で 2A 程度のルールを扱わなければならない
マーケットバスケット分析の長所




結果が明確に理解できる
探索的なデータマイニングができる
可変長のデータで使える
計算方法が単純で理解しやすい
マーケットバスケット分析の短所




問題の規模が大きくなると指数関数的に計
算量が増大する
データの属性が限定的にしか扱えない（ひと
つの特徴で識別されるデータ向き）
適切なアイテム数の決定が難しい
まれにしか買われないアイテムの説明がで
きない
記憶ベース推論
2.記憶ベース推論(Memory Based
Reasoning)

与えられた情報に対し、既知
のデータから一番近い事例を
探し出し、分類や属性値を予
測


保険金請求のデータベースで、
知りたい事例にちかいものを調
べ、即座に請求に応じるべきか、
調査を詳細に行うべきか判断
距離関数（事例間の距離）と
結合関数（事例と予測を結び
つけるもの）があればよい
既知のものの
なかで
一番近い事例
与えられた
事例
手順
1. データの値の標準化
2. 距離関数による与えられたデータに近い既
存データの探索
3. 2.によって得られた既存データ組より得た結
合関数の値から予測
手順(1) 入力データの尺度変換

データをあらわすベクトル列の各成分の値を標準
化する

下式のように入力ベクトルの第i成分についての平均μi
と分散σiを用いて標準化する（各成分が平均0、分散1
となる）
zi 

xi  i
i
もしくは、第i成分の最大値と最小値の間の幅Dを用い
て標準化する（最小値が0、最大値が1）
xi  xi
zi 
Di
min
手順(2) 距離関数による近傍データの取得

データ間の遠近を定義する距離関数より、与えられ
たデータに近い既存のデータを得る

距離関数は、通常は以下の公理を満たすことが要請され
る
同一性:
交換可能性:
三角不等式:

 
 
d ( x, y)  0 if and only if x  y
 
 
d ( x , y )  d ( y, x )
 
 
 
d ( x , y )  d ( y, z )  d ( x , z )
ただし、実用上は遠近さえ定義できればよいのでこれら
の公理のいくつかを満たさない距離を利用することもある
距離関数(1)

連続データについては以下のものが代表的：
Euclid距離:
 
d E ( x, y) 
 (x  y )
i
2
i
i
Manhattan距離:
 
d M ( x, y)   xi  yi
i
標準化絶対値
による距離:
 
 
d E ( x, y)
d N ( x, y) 
 
max d E ( x , y )
x, y
距離関数(2)

カテゴリカルデータの場合は、適宜決める必要が
ある。例えば、同一であれば1、異なれば0とする方
法がある
例)
d (m ale, m ale)  0
d (male, female)  1
d ( female, male)  1
d ( female, female)  0
距離関数(3)

連続データとカテゴリカルデータが混在する
場合、以下のようにして全体の距離を定義
することが多い



合計（すべての距離の和をとる）
ユークリッド距離（すべての距離の2乗和の平方
根をとる）
標準化合計（すべての距離の和をその最大値で
割って標準化する）
手順(3) 結合関数による予測


距離関数で近いとされたデータにもとづき予測を与
える結合関数を使って結果を予測する
結合関数の例)



与えられたデータに一番近いデータによる事例の結果
を返す関数
与えられたデータの近傍データk個による結果の平均を
返す関数
（このことからMBRをk-NN法と呼ぶことがある）
与えられたデータの近傍データk個の結果に対して重み
つき和をとり、その値を返す関数
など
記憶ベース推論の長所・短所

長所



似ている事例を用いて予測するためわかりやす
い
どのような形式のデータにも距離関数・結合関
数が定義可能であれば適用可能
短所


過去の事例をすべて探索するため、処理時間
が事例数に比例して長くかかる
過去の全事例を保存する記憶領域が必要
クラスタリング
クラスタリング


類似している塊（クラス
タ）に、レコードを分類
する手法
探索的データマイニン
グ

未知のデータを分類す
るため
2種類のクラスタリング

分割型



与えられたデータ群を複数のまとまり(=クラスタ)
に分割
クラスタ間に共通部分を設けないのが普通
階層型


似ている（=距離が近い）ものは先に、似ていな
いものは後にデータをまとめていく方法
デンドログラムを使って表現
K-means法




1967年 J.B.MacQueenが発表
分割型の代表的手法
あらかじめクラスタの数(=K)を指定する必要
あり
通常、数値データ（ベクトル）群の分割に利
用される
K-means法の手順
1. K個のデータをseedとする
2. 各データをどのseedに近いかにもとづいてグループ
化する
3. 各グループ毎に、含まれるデータの重心を計算す
る


1
xg 
xi

N c iC
4. 2.のseedの代わりに3.の重心を指定し、2.および3.
を重心が収束するまで繰り返す
K-means法の手順
K=分類（クラスタ）の個数
重心を導出*
収束するまで繰り返し
重心間の垂直二等分線(面)
により再分類
*最初は、ランダムにK個の点を選び、
種とする。
凝集型階層的クラスタ

距離が近いもの同士をまとめていく



その工程をグラフ化したものがデンドログラム
データ間の距離は記憶ベース推論のときと同様
のものを使う
クラスタ間の距離の定義によって結果が変わる



単一連結法（single linkage: 最近隣法）
完全連結法（complete linkage: 最遠隣法）
セントロイド法（comparison of centroids）
クラスタ間距離
simple
centroids
complete
凝集型クラスタリングの手順
1. 各データ間の距離を計算し、類似度行列を
作成する
2. もっとも距離が短いデータ組を見つけ、クラ
スタとして置き換える
3. クラスタから他のデータまでの距離を計算し
て、類似度行列を更新する
4. 2.と3.をすべてのデータがひとつのクラスタ
の中に含まれるまで繰り返す
簡単な例(1) 単一連結法
1
2
3
4
1
2
3
4
簡単な例(2) 単一連結法
1
C1
2
3
1
4
1
2
3
4
簡単な例(3) 単一連結法
1
C2
2
3
4
2
1
4
1
2
3
4
クラスタリングの長所・短所

長所



データの構造を把握しやすい
距離尺度（類似度）が与えられればどのようなデー
タに対しても適用可能
短所



距離尺度の定義が困難な場合に適用できない
K-means法ではseedの選び方によって結果が変わ
る場合がある
得られたクラスタの意味づけが難しい場合がある

Download Report