データ工学特論 第三回 木村昌臣

本日の話題 マーケットバスケット分析 記憶ベース推論 クラスタリング

マーケットバスケット分析

マーケットバスケット分析 買い物かごや 取引レコードでどの アイテムが一緒に 買われる傾向があるかを分析 分析をもとにアクションをとりやすい（実行可能） レイアウト計画 特売商品の品目調整 製品のバンドルの仕方 など ビール おむつ つまみ

マーケットバスケット分析で得られるもの 結果はアソシエーションルールとして得られる 商品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の購入確率（条件付確率） サポート=商品Aと商品Bの同時購入確率 リフト=商品B購入が条件の商品Aの購入確率と、商品Aの購入確率の比(商品Bを購入したという事実が商品Aの購入確率をどれだけ改善するかの指標)

手順 アイテムの水準と内容を正しく設定 同時購買表を解読してルールを生成 実行上の制限の克服 「ピザ」をアイテムにする？ トッピングに応じて別アイテムにする？ 同時購買表を解読してルールを生成 実行上の制限の克服

手順1. アイテムの水準と内容を適切に選ぶ ピザ チーズ増量ピザ オニオンピザ マッシュルームピザ ○ 分析しやすい ○　分析しやすい （組み合わせが少なくてすむ） ×　詳細な情報が落ちる　 抽象 チーズ増量ピザ ○　特定のアイテムに焦点を当てた 　　　分析ができる ×　ルールが複雑になり、 　　 分析に時間がかかる　 オニオンピザ 具体 マッシュルームピザ

バーチャルアイテム バーチャルアイテム コカコーラ製品 支払方法 ダイエットコーク コカコーラ 季節 コカコーラC2 実際には商品そのものとして 存在しないが 含めると解析が便利になる 仮想アイテム コカコーラ製品 まとめたもの 支払方法 （カード？現金？） ダイエットコーク コカコーラ 季節 コカコーラC2

（買ったものが）もし「オレンジジュース」であれば （いっしょに買うのは）「炭酸飲料」である 手順2.同時購買表を解読してルールを生成 ルール： もし「前件部」が成立すれば「後件部」も成立する 「前件部　⇒　後件部」と書く 例） （買ったものが）もし「オレンジジュース」であれば （いっしょに買うのは）「炭酸飲料」である 同時購買表には、「アイテムのどの組合わせがもっとも多いか」についての情報が 提供されている

手順3. 実行上の制限の克服 アソシエーションルールの生成は多段階 以下同様。アイテム数をAとすると、 単一のアイテムについての同時出現表を作成 2つのアイテムについての同時出現表を作成し、2アイテム間のルールを生成 3つのアイテムについての同時出現表を作成し、3アイテム間のルールを生成 4つのアイテムについての同時出現表を作成し、4アイテム間のルールを生成 以下同様。アイテム数をAとすると、 全部で 2A 程度のルールを扱わなければならない

マーケットバスケット分析の長所 結果が明確に理解できる 探索的なデータマイニングができる 可変長のデータで使える 計算方法が単純で理解しやすい

マーケットバスケット分析の短所 問題の規模が大きくなると指数関数的に計算量が増大する データの属性が限定的にしか扱えない（ひとつの特徴で識別されるデータ向き） 適切なアイテム数の決定が難しい まれにしか買われないアイテムの説明ができない

記憶ベース推論

2.記憶ベース推論(Memory Based Reasoning) 与えられた情報に対し、既知のデータから一番近い事例を探し出し、分類や属性値を予測 保険金請求のデータベースで、知りたい事例にちかいものを調べ、即座に請求に応じるべきか、調査を詳細に行うべきか判断 距離関数（事例間の距離）と結合関数（事例と予測を結びつけるもの）があればよい 既知のものの なかで 一番近い事例 与えられた 事例

手順 データの値の標準化 距離関数による与えられたデータに近い既存データの探索 2.によって得られた既存データ組より得た結合関数の値から予測

手順(1) 入力データの尺度変換 データをあらわすベクトル列の各成分の値を標準化する 下式のように入力ベクトルの第i成分についての平均μiと分散σiを用いて標準化する（各成分が平均0、分散1となる） もしくは、第i成分の最大値と最小値の間の幅Dを用いて標準化する（最小値が0、最大値が1）

手順(2) 距離関数による近傍データの取得 データ間の遠近を定義する距離関数より、与えられたデータに近い既存のデータを得る 同一性: 距離関数は、通常は以下の公理を満たすことが要請される ただし、実用上は遠近さえ定義できればよいのでこれらの公理のいくつかを満たさない距離を利用することもある 同一性: if and only if 交換可能性: 三角不等式:

距離関数(1) 連続データについては以下のものが代表的： Euclid距離: Manhattan距離: 標準化絶対値 による距離:

距離関数(2) カテゴリカルデータの場合は、適宜決める必要がある。例えば、同一であれば1、異なれば0とする方法がある 例)

距離関数(3) 連続データとカテゴリカルデータが混在する場合、以下のようにして全体の距離を定義することが多い 合計（すべての距離の和をとる） ユークリッド距離（すべての距離の2乗和の平方根をとる） 標準化合計（すべての距離の和をその最大値で割って標準化する）

手順(3) 結合関数による予測 距離関数で近いとされたデータにもとづき予測を与える結合関数を使って結果を予測する 結合関数の例) など 与えられたデータに一番近いデータによる事例の結果を返す関数 与えられたデータの近傍データk個による結果の平均を返す関数 （このことからMBRをk-NN法と呼ぶことがある） 与えられたデータの近傍データk個の結果に対して重みつき和をとり、その値を返す関数 など

記憶ベース推論の長所・短所 長所 短所 似ている事例を用いて予測するためわかりやすい どのような形式のデータにも距離関数・結合関数が定義可能であれば適用可能 短所 過去の事例をすべて探索するため、処理時間が事例数に比例して長くかかる 過去の全事例を保存する記憶領域が必要

クラスタリング

クラスタリング 類似している塊（クラスタ）に、レコードを分類する手法 探索的データマイニング 未知のデータを分類するため

2種類のクラスタリング 分割型 階層型 与えられたデータ群を複数のまとまり(=クラスタ)に分割 クラスタ間に共通部分を設けないのが普通 似ている（=距離が近い）ものは先に、似ていないものは後にデータをまとめていく方法 デンドログラムを使って表現

K-means法 1967年 J.B.MacQueenが発表 分割型の代表的手法 あらかじめクラスタの数(=K)を指定する必要あり 通常、数値データ（ベクトル）群の分割に利用される

K-means法の手順 K個のデータをseedとする 各データをどのseedに近いかにもとづいてグループ化する 各グループ毎に、含まれるデータの重心を計算する 2.のseedの代わりに3.の重心を指定し、2.および3.を重心が収束するまで繰り返す

K-means法の手順 K=分類（クラスタ）の個数 重心を導出* 重心間の垂直二等分線(面) により再分類 収束するまで繰り返し 　　種とする。

凝集型階層的クラスタ 距離が近いもの同士をまとめていく その工程をグラフ化したものがデンドログラム データ間の距離は記憶ベース推論のときと同様のものを使う クラスタ間の距離の定義によって結果が変わる 単一連結法（single linkage: 最近隣法） 完全連結法（complete linkage: 最遠隣法） セントロイド法（comparison of centroids）

クラスタ間距離 simple centroids complete

凝集型クラスタリングの手順 各データ間の距離を計算し、類似度行列を作成する もっとも距離が短いデータ組を見つけ、クラスタとして置き換える クラスタから他のデータまでの距離を計算して、類似度行列を更新する 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の選び方によって結果が変わる場合がある 得られたクラスタの意味づけが難しい場合がある