クラスタリング 距離と分類の考え方.

Presentation on theme: "クラスタリング 距離と分類の考え方."— Presentation transcript:

1 クラスタリング 距離と分類の考え方

2 梨農園で，手をかけ方を変えた梨の木 どんな手のかけ方の木から収穫された梨が高い利益？ 梨の木に実施した農作業は記録
潅水量，施肥量，農薬量，etc 穫れた梨の大きさ，色，味も評価 どんな梨（の集団）？集団内の数は？ 甘くて大きな梨 小さいけど甘い梨 大きいが水分が少ない梨 多様でよくわからない 自動でグループ分けする方法はないか？

3 階層的と非階層的 クラスタ(cluster)とは（ぶどう等の）房、群れ、集団
クラスタ分析とは，分析対象となる個体を　類似度にしたがって いくつかのグループに分割する手法 階層的　クラスタリング 個体間の類似度あるいは非類似度(距離)に基づき，もっとも似ている個体から　順に併合　しクラスタを作っていく方法 最終的にツリー状のデンドログラムが書ける 非階層的　クラスタリング ある初期分割からはじめて，与えられた評価基準に照らして良い分割結果が得られるように対象を分類しなおすことを繰返して，最終的な分割結果を得る手法 K-Means法がもっとも有名

4 階層的クラスタリング 距離が近いものからくっつけていく。または逆に遠いものを別クラスタに分ける。
さまざまなクラスタ間距離（　類似度　）の測定方法 NN（Nearest Neighbor）法、最短距離法 最長距離法 群平均法 重心法 ウォード（Ward）法

5 階層的クラスタリングの特徴をイメージで示すと
分散が小さい 順に併合していく

6 クラスタ間の距離もいろいろ 最短距離法 (nearest neighbor method) または 単連結法 (single linkage method) 最長距離法 (furthest neighbor method) または 完全連結法 (complete linkage method) 群平均法 (group average method)

7 テンドログラム 分析の対象となる個体がまとめられていくさまを樹形図の形で表したもの
ウォード法（後述）の場合，手順が進むにつれて「クラスター内の平方和」が増加していくので，明確なデンドログラムが描ける

8 最短距離法 http://www. vi. cs. is. nagoya-u. ac
最短距離法 対象すべての組合せに対し距離を求め，最短距離　をクラスタ間の距離とする 初期状態として，以下の座標のA,B,C,D,Eを考える 座標Aから座標B,C,D,Eへの距離，座標Bから座標C,D,Eへの距離，… として，各座標間のすべての距離を求める． 以下が距離行列（対称行列なので上三角行列）

9 座標D-E間が最も短い．D,Eは クラスタ を形成
A-DE間の距離はA-D間の距離 (赤線) 距離A-D　＜　距離A-E　だから (理由　最短距離をとる　) B-DE間の距離はB-D間の距離 (赤線) 距離B-D　＜　距離B-E　だから C-DE間の距離はC-E間の距離(青線) 距離C-D　＞　距離C-E　だから

10 再び最短距離の組合せを求める．今度はA-Bがクラスタ． A-B間の距離を0とする
AB-C間の距離はA-C間の距離（赤線） 距離A-C　＜　距離B-C　だから(理由　クラスタ内の点で最短距離 ) AB-DE間の距離はB-D間の距離 (青線) A-D, A-E, B-D, B-Eの中で距離B-Dが最短だから

11 クラスタを形成したABCとDEに関する距離を再計算
さらに最短距離の組合せを求める．今度はAB-Cがクラスタ． AB-C間の距離を0とする クラスタを形成したABCとDEに関する距離を再計算 最短なのはB-D間（赤線） さらに最短距離の組合せを求める．最後はABC-DEがクラスタ．

12 群平均法（group average method）
最短距離法と最長距離を折衷した方法 これらでは，クラスタ間の非類似度は，それらを構成する対象の対の距離の，最大または最小という 極端 な値で定義 ２つのクラスタの各々の中から１個ずつ個体を選んで個体間の距離を求め、それらの距離の平均値を２つのクラスタ間の距離とする クラスタ(t)に含まれる対象とクラスター(r)に含まれる対象の，可能なすべての対の非類似度（*）の平均により，両クラスタ間の非類似度を定義 (*) 距離は，非類似度を表す

13 ウォード法 各対象からクラスタの重心への距離の二乗和を最小化 階層的クラスタリングで，もっとも成功率が高い
つまり，クラスタ内の　ばらつき　を最小化 階層的クラスタリングで，もっとも成功率が高い いま， クラスタ{ A } に 要素eがn個あり，その各要素がp個の変数で表現されるとする． 　 ，　 をクラスタ{A}, {B} に属する i 番目の対象の第 k変数の値とすればクラスタ 内の平方和　　，　　は ただし

14 クラスタ{A}とクラスタ{B}を結合して新しく作ったクラスタ{C} 内の平方和は ここに これより つまり 　　　 は{A}と{B}の結合時の{C}での 平方和 の増分

15 各段階で が最小になるように，クラスタを結合 具体例(http://nakaikemi. com/clusterexp
各段階で が最小になるように，クラスタを結合 具体例( 第１反復：すべての点の組のユークリッド距離を求めると などより， が最小

16 距離最小とは分散が最小．よってクラスタ{A},{B}を結合 し第１反復処理後のクラスタは 第２反復： AとBの重心は だから， 新しい距離表はAとBを１つの点（=重心）とみて

17 最小距離は だからクラスタ{D},{E}を結合 第３反復： 新クラスタ{D・E}の座標は重心 とみなし，距離表を更新

18 {A・B}と{C}の距離が最小だからこれらを結合 第４反復： すべての点を統合

19 本当にΔSが最小のもの？ 右の例で{A・B}を{C}と統合 同様に，{ A・B }と{ D・E }を併合の場合
ABの重心が(1.5,2.5)だから{A ・B}内 の分散（重心からの距離の平方和）は ABCの重心が　　　　　　　　　　　　　　　　　　　　　　だから， 　 クラスタ{A ・B ・C}内の分散を計算すると Cは１点のクラスタだから平方和 0 よって，この統合による平方和の増分は 同様に，{ A・B }と{ D・E }を併合の場合 { A・B } , { D・E } , {A・B ・D・E }内の平方和は，1, 2.5, 19.75 増分は19.75 – ( )= 同様に、{ C }と{ D・E }を併合の場合，増分は 10.17 よって{A・B}を{C}と統合を統合した場合が9.67で最小

20 ウォード法の結果をテンドログラムで表示 どこで切るかで クラスタ数 が変わる 2クラスタ 3クラスタ

21 非階層的クラスタリング K-Means法 クラスタ数は既知であると仮定したアルゴリズム ビジュアライズした例
各点にランダムにクラスタを割り当てる クラスタの重心を計算する 点のクラスタを，一番近い重心のクラスタに変更する 変化がなければ終了．変化がある限りは 2. に戻る． ビジュアライズした例 初期状態 ランダムにクラスタリング 色がクラスタ このあと，レポートとして出題

22 Step2：クラスタの重心を計算（×印が重心）

23 Step5：もっとも近い重心の色に置き換え
クラスタに変化があったので手続き２へ Step5：もっとも近い重心の色に置き換え

24 Step6：クラスタが変化したので重心を再計算
　　　　　　　　　： Step n：変化がなくなるまで 繰り返す ： ：

25 クラスタリングの注意点 各手法の特徴を無視したために，不適切な結果 クラスタリングの解釈 対象の問題にあった手法を選択すべき
クラスタリングは探索的 (exploratory) なデータ解析手法であって，分割は必ず何らかの主観や視点に基づいている データの要約などの知見を得るために用い，客観的な証拠として用いてはならない Cutting らの研究，New York Times紙の5000件の記事を分類 以下の話題を含むクラスタが発見される． 　　　　教育, 国内, イラク, 芸術, スポーツ, 石油, ドイツ統合, 裁判 おおまかな内容をクラスタから知ることができる [注意]クラスタリング結果は絶対的でも，普遍的でも，客観的でもない 「イラクと石油は湾岸戦争に関係するのでまとめるべき」は，あくまで一つの見方

26 どの方法から使うか Ward 法 群平均法 N 個の対象が k 個の属性ベクトルで記述されている場合，計算量が
k-means法は O(Nk) 階層的手法は O(N2) なので，k-means法を用いる方がよい． 階層構造が必要な場合には Ward 法 群平均法 を用いる．最短距離法や最長距離法はこれらの結果に不満な場合に試してる．

27 k-meansはクラスタ数が既知でないと
最初にクラス数を２にして実施 クラスタ数を増やしながら，結果を表示 納得のいくものを，その中から選ぶ 最初に戻って… 大きな収益をもたらす梨の栽培法は？ 各クラスタからの収益を計算 売上金額 ー 原価（肥料費，農薬費） ー 作業コスト

28 レポート ウォード法で用いた例題をK-means法でクラスタリングする経過を各Stepごとに色分けして示せ．
初期値のクラスタはできるだけランダムに つまり色の配置ができるだけ，バラバラになるように クラスタ数 ２ で実施せよ 提出には次ページ以降の レジュメを切り取って提出せよ． 足らなければコピーせよ

29 レポート（K-means法） 学籍番号 氏名 ．
初期値としてできるだけランダムに クラスタを設定し，色分け クラスタの重心を計算 　 各点を色のついた○で囲め 重心の位置を 上の座標に☓で示せ

30 第１回目の処理 クラスタの重心を計算 クラスタごとに色分け もっとも近い重心を見つけ， 重心ごとにクラスタを分ける 前回の重心を示した上で
各点を色のついた○で囲め 新しい重心の位置を 上の座標に☓で示せ

31 第 回目の処理 クラスタの重心を計算 クラスタごとに色分け もっとも近い重心を見つけ， 重心ごとにクラスタを分ける 前回の重心を示した上で
第　回目の処理 クラスタごとに色分け もっとも近い重心を見つけ， 重心ごとにクラスタを分ける クラスタの重心を計算 前回の重心を示した上で 各点を色のついた○で囲め 新しい重心の位置を 上の座標に☓で示せ

32 第 回目の処理 クラスタの重心を計算 クラスタごとに色分け もっとも近い重心を見つけ， 重心ごとにクラスタを分ける 前回の重心を示した上で
第　回目の処理 クラスタごとに色分け もっとも近い重心を見つけ， 重心ごとにクラスタを分ける クラスタの重心を計算 前回の重心を示した上で 各点を色のついた○で囲め 新しい重心の位置を 上の座標に☓で示せ