機械学習 - K-means & 階層的クラスタリング

1. K-meansクラスタリング
2. 階層的クラスタリング

Transcript

1. クラスタリング1 K-means & 階層的クラスタリング 第4回 機械学習発展 （導入編） ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科 yusuke_yamamoto@acm.org
2. 授業資料 2 https://mlnote.hontolab.org/
3. 講義のトピック 機械学習 教師あり学習 教師なし学習 強化学習 ・クラスタリング ・データ圧縮 ・分類 ・回帰 … … 3
4. データを幾つかのクラスタに分割する手法 何らかの条件で類似するデータの集合 クラスタリングとは？ X Y 0 4 教師なし学習⼿法の1つで、
5. クラスタリングによる分析事例 5 サンフランシスコで撮影された 写真の位置情報 on Flickr 画像出展: https://www.buzzfeed.com/ L. Kennedy et al.: ”How flickr helps us make sense of the world: context and content in community-contributed media collections. In Proceedings of the 15th ACM international conference on Multimedia (MM ‘07)”, 631–640, 2007. 密度ベースの クラスタリング 撮影位置が密集している 場所をクラスタとして抽出 撮影位置密集場所に タグ付けされた情報を可視化
6. 私たちはどうやってグルーピングを⾏っているか？（1/2） 私たちは，直感的には何にもとづき 以下のデータをグルーピングするか？ Q. X Y 0 6
7. 私たちはどうやってグルーピングを⾏っているか？（2/2） データ間の距離 A. X Y 0 がある程度⼩さければ 同じグループと⾒なす． 近い 遠い 遠い 7
8. クラスタリングのアプローチ 1. 距離を計算できるようにデータを表現 2. 距離を定義し，データ間の距離を計算 3. 距離をもとにあるルールでデータをまとめる 鳴き声の⾼さ 0 鳴き声の⼤きさ 鳴き声の⾼さ 鳴き声の⼤きさ XY平⾯上での距離 が近いものをまとめる 8
9. クラスタリングのアプローチ 鳴き声の⾼さ 0 鳴き声の⼤きさ 鳴き声の⾼さ 鳴き声の⼤きさ XY平⾯上での距離 が近いものをまとめる ポイント クラスタリング手法の違いはデータをまとめるルールにある 9 1. 距離を計算できるようにデータを表現 2. 距離を定義し，データ間の距離を計算 3. 距離をもとにあるルールでデータをまとめる
10. 1 指定されたグループ数に強引にデータを分割する K-meansクラスタリング
11. K-meansクラスタリングの概要 A B D C E F G H I A B D C E F G H I 入力 ・ベクトルの集合（表データ） ・クラスタ数 出力 各ベクトルが所属するクラスタ 利用するケース データを決まった数のグループに 分けたいとき 11 N個のグループに分割 クラスタ数が決め打ちなのでトップダウンクラスタリングと呼ばれる
12. K-meansクラスタリングの利⽤例（1/2） 出典： https://mercan.mercari.com/articles/2016-06-21-160000/ 「社会⼈？」クラスタの平均傾向 「主婦？」クラスタの平均傾向 メルカリを使う時間帯によって メルカリユーザを9つのグループに分割 ※ ユーザは「時間帯ごとのアクセス回数の⽐率」でベクトル化 12
13. K-meansクラスタリングの利⽤例（2/2） 画像出典：https://jp.mathworks.com/help/images/color-based-segmentation-using-k-means-clustering.html 細胞の画像を各ピクセルの色の近さを考慮して K-meansクラスタリング．細胞核とそうでない箇所に分割 13
14. K-meansの直感的アイデア ＋ ＋ ＋ ⾚クラスタの重⼼が最も 近いので⾚に割り当て 各クラスタの重心との距離を計算し， 距離が最も近いクラスタに割り当てる ある点をどのクラスタに割り当てるか？ 14
15. K-meansのアルゴリズム（1/12） 各データをランダムにクラスタに割り当て 1. 15
16. K-meansのアルゴリズム（2/12） 各データをランダムにクラスタに割り当て 1. 16
17. K-meansのアルゴリズム（3/12） 各クラスタの重心を計算する 2. ＋ ＋ ＋ 17
18. K-meansのアルゴリズム（4/12） すべての点について，先ほど計算した クラスタ重心との距離を計算し， 最も距離が小さくなるクラスタに再割り当て 3. ＋ ＋ 18 ＋
19. K-meansのアルゴリズム（5/12） すべての点について，先ほど計算した クラスタ重心との距離を計算し， 最も距離が小さくなるクラスタに再割り当て 3. ＋ ＋ 19 ＋
20. K-meansのアルゴリズム（6/12） すべての点について，先ほど計算した クラスタ重心との距離を計算し， 最も距離が小さくなるクラスタに再割り当て 3. ＋ ＋ 20 ＋
21. K-meansのアルゴリズム（7/12） すべての点のクラスタ割り当てが 変わらなくなるまでステップ2と3を繰り返す 4. ＋ ＋ ＋ 21
22. K-meansのアルゴリズム（8/12） すべての点のクラスタ割り当てが 変わらなくなるまでステップ2と3を繰り返す 4. ＋ ＋ ＋ 22
23. K-meansのアルゴリズム（9/12） すべての点のクラスタ割り当てが 変わらなくなるまでステップ2と3を繰り返す 4. ＋ ＋ ＋ 23
24. K-meansのアルゴリズム（10/12） すべての点のクラスタ割り当てが 変わらなくなるまでステップ2と3を繰り返す 4. ＋ ＋ ＋ 24
25. K-meansのアルゴリズム（11/12） すべての点のクラスタ割り当てが 変わらなくなるまでステップ2と3を繰り返す 4. ＋ ＋ ＋ 25
26. K-meansのアルゴリズム（12/12） すべての点のクラスタ割り当てが 変わらなくなるまでステップ2と3を繰り返す 4. 26
27. 素朴な疑問2 データ点の距離は どう計算（定義）するのか？ Q. B A ？ 27
28. 実数値ベクトルの距離（1/4） A地点とB地点の距離はどの程度？ Q. 28 経度 緯度 • • A B
29. 実数値ベクトルの距離（2/4） • • Y X • • Y X ユークリッド距離 ・直線的な距離 ・別称 L2ノルム マンハッタン距離 29 ・各座標の差の総和 ・別称 L1ノルム 𝑑 𝒙, 𝒚 = & !"# $ 𝑥! − 𝑦! % 𝑑 𝒙, 𝒚 = & ! $ |𝑥! − 𝑦! | 経度 緯度 経度 緯度
30. 実数値ベクトルの距離（3/4） A B 数学：80点 英語：70点 数学：50点 英語：90点 AさんとBさんの距離はどの程度？ （どれくらい類似？） Q. ? 30
31. 実数値ベクトルの距離（4/4） • • Y X コサイン距離（類似度） ・ベクトルの⾓度 ・傾向の類似性を評価 31 𝑑 𝒙, 𝒚 = cos 𝒙, 𝒚 = 𝒙"𝒚 |%||𝒚| = 𝑥# 𝑦# + ⋯ + 𝑥$ 𝑦$ 𝑥# % + ⋯ + 𝑥$ % 𝑦# % + ⋯ + 𝑦$ % 数学 英語
32. カテゴリ値ベクトルの距離（1/3） B AさんとBさんの距離はどの程度？ （どれくらい類似？） Q. ? A Aさんの好きな寿司ネタ Bさんの好きな寿司ネタ はまち あじ たまご イクラ たまご バイ貝 イクラ 32
33. カテゴリ値ベクトルの距離（2/3） ジャカード係数 2つの集合に含まれる要素のうち共通する要素の割合 33 𝐽 𝐴, 𝐵 = |𝐴 ∩ 𝐵| |𝐴 ∪ 𝐵|
34. カテゴリ値ベクトルの距離（3/3） ジャカード係数 2つの集合に含まれる要素のうち共通する要素の割合 たまご はまち イクラ たまご あじ バイ⾙ イクラ ＝ 5 2 34 𝐽 𝐴, 𝐵 =
35. K-meansアルゴリズムの定式化（1/2） 35 入力 データ集合 𝑋 = {𝒙! , 𝒙" , … , 𝒙# } クラスタ数 𝐾 出力 クラスタ割り当て （各データに割り当てるクラスタ番号で1〜Kのいずれかを取る） 𝐶 = {𝑐& , 𝑐' , … , 𝑐( }
36. K-meansアルゴリズムの定式化（2/2） 36 アルゴリズム 1. 集合Xの全要素にランダムにクラスタ番号を割り当てる． 2. 各クラスタに割り当てられたデータのベクトルの平均 を計算し，クラスタの平均（重⼼）ベクトルを得る． 3. 平均ベクトルの集合を𝑀 = {𝒎# , 𝒎% , … , 𝒎& }とする．Xの 各要素と最も近いクラスタ平均を調べ，クラスタ番号 を割り当てる．つまり，以下を得る． c) = argmin &*+*, 𝒙) − 𝒎+ 4. クラスタ割り当てが変更されなくなるまで，ステップ1~3 を繰り返す． データxi の クラスタ番号 ユークリッド距離 （コサイン距離を使う時も）
37. Hands-on タイム1 以下のURLにアクセスして， K-meansクラスタリングを体験しましょう https://mlnote.hontolab.org/ 37
38. K-meansがやりたいこと K-meansの収束性（1/2） 38 データ集合 𝑋 = {𝒙! , 𝒙" , … , 𝒙# } クラスタ数 𝐾 クラスタCk の代表ベクトル 𝒎$ データxi がk番⽬のクラスタに属するか wi,k (0 or 1) 割り当てられたクラスタの代表ベクトルとの 差の総和を最小化するような mk を見つけたい SS𝐸 = 4 )-& ( 4 +-& , 𝑤),+ 𝒙) − 𝒎+ '
39. K-meansの収束性（2/2） 39 𝑆𝑆𝐸 = + +,! # + -,! . 𝑤+,- 𝒙+ − 𝒎- " 𝜕𝑆𝑆𝐸 𝜕𝒎- = 2 + +,! # 𝑤+,- (𝒙+ − 𝒎- ) = 0 ⟹ 𝒎- = 1 |𝐶- | + 𝒙!∈1" 𝒙+ （定番テク）最⼩化したい時は微分してゼロ ! !𝒙 𝒙 #= ! !𝒙 𝒙𝑻𝒙 = 2𝒙 これこそ重⼼ベクトル!! mk に重⼼ベクトルをセットし続ければSSEは局所最⼩値になる ⟹ + 𝒙!∈1" 𝑤+,- 𝒙+ − 𝒎- = 0 Ck に割り当てられた データのみ着⽬
40. 2 類似するデータを徐々にグルーピングする 階層的クラスタリング
41. 階層的クラスタリングの概要 入力 ベクトルの集合（表データ） 出力 各ベクトルが所属するクラスタ & その階層図（デンドログラム） 利用するケース A B D C E F G H I A B D C E F G H I 類似データを徐々にマージ ・クラスタ数を柔軟に決めたいとき ・クラスタが分かれていく様を 確認したいとき 41 徐々にクラスタを⼤きくするのでボトムアップクラスタリングと呼ばれる
42. 階層的クラスタリングの利⽤例1 出典：https://www.macromill.com/service/data_analysis/cluster-analysis.html 寿司ネタの選好度データから寿司ネタをクラスタリング 42
43. 階層的クラスタリングの利⽤例2 ヒト腫瘍DNAマイクロアレイデータから性質が 類似する標本（例: 肺がん）をクラスタリング 43 6 1. Introduction SID42354 SID31984 SID301902 SIDW128368 SID375990 SID360097 SIDW325120 ESTsChr.10 SIDW365099 SID377133 SID381508 SIDW308182 SID380265 SIDW321925 ESTsChr.15 SIDW362471 SIDW417270 SIDW298052 SID381079 SIDW428642 TUPLE1TUP1 ERLUMEN SIDW416621 SID43609 ESTs SID52979 SIDW357197 SIDW366311 ESTs SMALLNUC SIDW486740 ESTs SID297905 SID485148 SID284853 ESTsChr.15 SID200394 SIDW322806 ESTsChr.2 SIDW257915 SID46536 SIDW488221 ESTsChr.5 SID280066 SIDW376394 ESTsChr.15 SIDW321854 WASWiskott HYPOTHETICAL SIDW376776 SIDW205716 SID239012 SIDW203464 HLACLASSI SIDW510534 SIDW279664 SIDW201620 SID297117 SID377419 SID114241 ESTsCh31 SIDW376928 SIDW310141 SIDW298203 PTPRC SID289414 SID127504 ESTsChr.3 SID305167 SID488017 SIDW296310 ESTsChr.6 SID47116 MITOCHONDRIAL60 Chr SIDW376586 Homosapiens SIDW487261 SIDW470459 SID167117 SIDW31489 SID375812 DNAPOLYMER SID377451 ESTsChr.1 MYBPROTO SID471915 ESTs SIDW469884 HumanmRNA SIDW377402 ESTs SID207172 RASGTPASE SID325394 H.sapiensmRNA GNAL SID73161 SIDW380102 SIDW299104 BREAST RENAL MELANOMA MELANOMA MCF7D-repro COLON COLON K562B-repro COLON NSCLC LEUKEMIA RENAL MELANOMA BREAST CNS CNS RENAL MCF7A-repro NSCLC K562A-repro COLON CNS NSCLC NSCLC LEUKEMIA CNS OVARIAN BREAST LEUKEMIA MELANOMA MELANOMA OVARIAN OVARIAN NSCLC RENAL BREAST MELANOMA OVARIAN OVARIAN NSCLC RENAL BREAST MELANOMA LEUKEMIA COLON BREAST LEUKEMIA COLON CNS MELANOMA NSCLC PROSTATE NSCLC RENAL RENAL NSCLC RENAL LEUKEMIA OVARIAN PROSTATE COLON BREAST RENAL UNKNOWN FIGURE 1.3. DNA microarray data: expression matrix of 6830 genes (rows) and 64 samples (columns), for the human tumor data. Only a random sample ある標本（⾏）に対する遺伝⼦（列）の発現量の 程度．発現量は−6から6の範囲の値をとる． 図中では⾊と値（発⾔量）が対応 522 14. Unsupervised Learning CNS CNS CNS RENAL BREAST CNS CNS BREAST NSCLC NSCLC RENAL RENAL RENAL RENAL RENAL RENAL RENAL BREAST NSCLC RENAL UNKNOWN OVARIAN MELANOMA PROSTATE OVARIAN OVARIAN OVARIAN OVARIAN OVARIAN PROSTATE NSCLC NSCLC NSCLC LEUKEMIA K562B-repro K562A-repro LEUKEMIA LEUKEMIA LEUKEMIA LEUKEMIA LEUKEMIA COLON COLON COLON COLON COLON COLON COLON MCF7A-repro BREAST MCF7D-repro BREAST NSCLC NSCLC NSCLC MELANOMA BREAST BREAST MELANOMA MELANOMA MELANOMA MELANOMA MELANOMA MELANOMA FIGURE 14.12. Dendrogram from agglomerative hierarchical clustering with average linkage to the human tumor microarray data. chical structure produced by the algorithm. Hierarchical methods impose hierarchical structure whether or not such structure actually exists in the data. The extent to which the hierarchical structure produced by a dendro- 画像出典: T. Hastie et al. (2009): “The Elements of Statistical Learning”, Springer.
44. 階層的クラスタリングの直感的アイデア 「クラスタ距離が最も近いクラスタ同士を併合する」 操作を繰り返し，徐々にクラスタを大きくする 最も近いクラスタ 44
45. 階層的クラスタリングのアルゴリズム（1/14） 各データを個々のクラスタとして初期化 1. G B C D A H E I F 45
46. 階層的クラスタリングのアルゴリズム（2/14） 各データを個々のクラスタとして初期化 1. G B C D A H E I F 46
47. 階層的クラスタリングのアルゴリズム（3/14） G B C D A H E I F すべての点間の距離を計算し， 最も近い点同士をクラスタとして併合 2. 47
48. 階層的クラスタリングのアルゴリズム（4/14） G B C D A H E I F 最も近い点 すべての点間の距離を計算し， 最も近い点同士をクラスタとして併合 2. 48
49. 階層的クラスタリングのアルゴリズム（5/14） G B C D A H E I F 最新のクラスタ情報にもとづき， すべてのクラスタ間の距離を計算し， 最も近いクラスタ同士をクラスタとして併合 3. 49
50. 階層的クラスタリングのアルゴリズム（6/14） 最新のクラスタ情報にもとづき， すべてのクラスタ間の距離を計算し， 最も近いクラスタ同士をクラスタとして併合 3. G B C D A H E I F 最もクラスタ（点） 50
51. 階層的クラスタリングのアルゴリズム（7/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 51
52. 階層的クラスタリングのアルゴリズム（8/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 52
53. 階層的クラスタリングのアルゴリズム（9/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 53
54. 階層的クラスタリングのアルゴリズム（10/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 54
55. 階層的クラスタリングのアルゴリズム（11/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 55
56. 階層的クラスタリングのアルゴリズム（12/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 56
57. 階層的クラスタリングのアルゴリズム（13/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 57
58. 階層的クラスタリングのアルゴリズム（14/14） すべての点が1つのクラスタに併合される までステップ3の操作を繰り返す 4. G B C D A H E I F 58
59. デンドログラム • クラスタが併合されていく様子を表した樹形図 • 適当な高さで木を切ることで，任意の数のクラスタを抽出可 A E H B D G I C F 59
60. 素朴な疑問1 クラスタ間の距離は どう計算（定義）するのか？ Q. D A H E ？ 60
61. クラスタ間の距離の定義（1/7） 最短距離法 (single linkage; SL) B A C D E クラスタの要素間の最短距離 61 Cx Cy 𝑑'( (𝐶) , 𝐶* ) = min 𝒗!∈-! 𝒗"∈-" 𝒗) − 𝒗* 最長距離法 (complete linkage; CL) B A C D E クラスタの要素間の最⻑距離 Cx Cy 𝑑-( (𝐶) , 𝐶* ) = ma𝑥 𝒗!∈-! 𝒗"∈-" 𝒗) − 𝒗*
62. クラスタ間の距離の定義（2/7） 最短距離法 (single linkage; SL) B A C D E クラスタの要素間の最短距離 62 Cx Cy 最長距離法 (complete linkage; CL) B A C D E クラスタの要素間の最⻑距離 Cx Cy ◦ 計算コストが⼩さい ◦ クラスタサイズが揃いやすい × クラスタ同⼠が離れやすい ◦ 計算コストが⼩さい × クラスタが鎖状になりやすい × 外れ値に弱い
63. クラスタ間の距離の定義（3/7） 重心法（セントロイド法） (centroid method; CM) B A C D E クラスタの重⼼間の距離 × × 63 Cx Cy 𝑑-. (𝐶) , 𝐶* ) = 1 |𝐶) | ? )∈-! 𝒗) − 1 |𝐶* | ? *∈-" 𝒗)
64. クラスタ間の距離の定義（4/7） 重心法（セントロイド法） (centroid method; CM) B A C D E クラスタの重⼼間の距離 × 計算コストが⼤きい × 平均化により要素の散らばり情報が失われる × × 64 Cx Cy
65. クラスタ間の距離の定義（5/7） クラスタ内の全要素間の距離の平均 65 𝑑/0 (𝐶) , 𝐶* ) = 1 𝐶) |𝐶* | ? 𝒗!∈-! ? 𝒗"∈-" 𝒗) − 𝒗* 群平均法 (group average; GA) B A C D E Cx Cy
66. クラスタ間の距離の定義（6/7） 群平均法 (group average; GA) × 計算コストが⼤きい ◦ 外れ値に強い ◦ 最短距離法と最⻑距離法の折衷 66 クラスタ内の全要素間の距離の平均 B A C D E Cx Cy
67. クラスタ間の距離の定義（7/7） B A C D E B A F G I H ウォード法 (ward method) • 2つのクラスタを併合したと仮定したときの， クラスタ内の要素の散らばり具合 < • 計算コストは⾼いが，分類感度がよい × × 67
68. Hands-on タイム2 以下のURLにアクセスして， 階層的クラスタリングを体験しましょう https://mlnote.hontolab.org/ 68
69. 今後の予定 69 回 実施⽇ トピック 1 04/14 ガイダンス 2 04/21 pandas⼊⾨ 3 04/28 決定⽊からはじめる機械学習 4 05/12 クラスタリング1：k-means & 階層的クラスタリング 5 05/19 クラスタリング2：密度ベースクラスタリング 6 05/26 分類1：K近傍法 & 教師あり機械学習のお作法 7 06/02 分類2：サポートベクターマシン 8 06/09 分類3：ニューラルネットワーク⼊⾨