パターン認識論 #7

パターン認識論 第７回 伊藤彰則 1

教師無し学習 (Unsupervised learning) ◦学習データから自分でパターンを見つ ける ◦ 「正解」はない（教師無し） ◦ しかし「発見されるパターンの良さ」は定 義する必要がある 2

例 この中からパターンを発見せよ 3

例 例えばこんな感じ 4

クラスタリング ◦与えられたデータをいくつかの塊（ク ラスタ）に自動的に分ける ◦分ける方法の分類 ◦ 階層的クラスタリング ◦ K-meansアルゴリズムとその変種 ◦ GMM ◦ 密度に基づくクラスタリング 5

階層的クラスタリング ◦ばらばらのデータを少しずつ併合する ことで集団を形成する C C A C A B D A B A C B D C A B D B D D 6

階層的クラスタリング ◦特徴 ◦ 2つのデータ間の距離（または類似度）が あればクラスタリングができる ◦ 例えば文字列とか ◦ 多次元空間上のデータである必要はない ◦ 計算量は少なくとも 𝑂(𝑛3 ) 7

数学的準備 ◦データ 𝐷 = 𝑥1 , … , 𝑥𝑛 ◦2つのデータ間の距離 𝑑(𝑥, 𝑦) ◦クラスタ 𝐶 ⊂ 𝐷 ◦クラスタ間の距離 𝑑(𝐶1 , 𝐶2 ) ◦クラスタの集合 𝐺 8

アルゴリズム 𝐶𝑖 ← 𝑥𝑖 for all i 𝐺 = {𝐶1 , … , 𝐶𝑛 } While 𝐺 > 1 𝐶𝑎 , 𝐶𝑏 ← arg min {𝑑(𝐶𝑎 , 𝐶𝑏 ) |𝐶𝑎 , 𝐶𝑏 ∈ 𝐺} 𝐶𝑎 ,𝐶𝑏 𝐶 ← 𝐶𝑎 ∪ 𝐶𝑏 Remove 𝐶𝑎 , 𝐶𝑏 from 𝐺 𝐺 ← 𝐺 ∪ {𝐶} End while 9

考慮すべき点 ◦クラスタ間距離の定義をどうするか ◦ サンプル間距離は与えられているとする ◦ 考え方 ◦ 2つのクラスタの全サンプル間距離の最小値 (Nearest-Neighbor) ◦ 2つのクラスタの全サンプル間距離の最大値 (Furthest-Neighbor) ◦ 2つのクラスタの全サンプル間距離の平均値 ◦ Etc… 10

クラスタ間距離の定義 𝑦𝑖 𝑥𝑖 min 𝑥𝑖 − 𝑦𝑗 max 𝑥𝑖 − 𝑦𝑗 最近隣法 Nearest-Neighbor 最遠隣法 Furthest-Neighbor 𝑖,𝑗 𝑖,𝑗 11

クラスタ間距離の定義 𝑦𝑖 𝑥𝑖 1 𝑁 𝑀 σ𝑖=1 σ𝑗=1 𝑁𝑀 𝑥𝑖 − 𝑦𝑗 平均距離 𝑥𝐺 − 𝑦𝐺 𝑥𝐺 , 𝑦𝐺 :各クラスタ の重心 重心間距離 12

クラスタ間距離の定義 ◦Ward法 𝑔 𝑦𝐺 𝑥𝐺 𝑁 𝐸 𝑋 =෍ 𝑖=1 𝑀 𝐸 𝑌 =෍ 𝑖=1 𝑥𝑖 − 𝑥𝐺 2 𝑁 𝐸 𝑋∪𝑌 =෍ 𝑁 𝑦𝑖 − 𝑦𝐺 2 +෍ 𝑖=1 𝑖=1 𝑥𝑖 − 𝑔 2 𝑥𝑖 − 𝑔 2 𝑑 𝑋, 𝑌 = 𝐸 𝑋 ∪ 𝑌 − 𝐸 𝑋 − 𝐸 𝑌 13

クラスタ間距離 距離定義の違いによるデモ 14

樹形図 (Dendrogram) ◦クラスタ構造の可視化 Cluster Dendrogram 10 17 19 8 13 20 2 4 2 12 6 10 14 15 11 16 8 4 7 18 1 5 3 9 7 18 dist(x) hclust (*, "single") 17 19 13 20 0 4 6 10 1 5 3 9 12 2 8 11 16 15 14 Height 0.6 0.4 0.2 0.0 Height 6 0.8 1.0 1.2 Cluster Dendrogram dist(x) hclust (*, "ward") 15

K-means法 ◦ベクトル空間で定義された点のクラス タリング ◦ クラスタリングする点に座標があり、平均 できる ◦ 点の間にユークリッド距離が定義される ◦各クラスタに「代表点」（セントロイ ド）を定義 ◦ セントロイドとクラスタ内の点との距離 （誤差）の二乗和をすべてのクラスタに対 して加算したものを最小化 16

K-means法 ◦クラスタ重心と二乗誤差 ◦ クラスタが決まれば、二乗誤差を最小にす るセントロイドは各クラスタの重心 どちらの二乗誤差が小さい？ 17

K-means法 ◦クラスタを確定した後で あっても、他のクラスタ の重心により近い点があ る →その点は近い方の重心 のクラスタに移した方が 誤差の二乗和は減少 18

K-meansアルゴリズム 𝑥1 … 𝑥𝑁 :データ点 K:クラスタ数 セントロイド 𝑔1 , … , 𝑔𝐾 を適当に決める（初期化） Loop For 𝑖 ← 1, … , 𝑁 do 𝑘෠ 𝑖 ← arg min 𝑥𝑖 − 𝑔𝑘 2 𝑘 𝑁 𝑘 ← 𝑘෠ 𝑖 = 𝑘であるサンプル（k番目のクラスタ）の数 For 𝑘 ← 1, … , 𝐾 do 𝑔𝑘 ← σ𝑖:𝑘෠ 𝑖 =𝑘 𝑥𝑖 /𝑁(𝑘) Until クラスタに属するサンプルが変化しなくなる 19

K-means法の初期値 ◦K-means法の結果は初期値に依存 20

K-means法の初期値 ◦初期値をどう決めればいいか？ ◦ ランダムにサンプルを選ぶ ◦ たまたま外れ値を選ぶとよくない結果に ◦初期値の決め方（＋クラスタ数） ◦ LBGアルゴリズム ◦ K-means++アルゴリズム 21

LBG (Linde-Buzo-Gray) アルゴリズム ◦少ないクラスタ数から始めて、順次ク ラスタ数を倍に増やしていく ◦ 初期値依存性が少なく安定したクラスタリ ングが可能 ◦ ベクトル量子化(Vector Quantization, VQ) によく使われる ◦VQとは？ ◦ 多次元の連続値データを有限個のコードで 近似する ◦ 通信、パターン認識などに用いられる 22

LBGアルゴリズム 1. 全体の重心gを求める 2. ある小さい定数ベクトル εを用意し、𝑔 + 𝜖, 𝑔 − 𝜖 を新たな代表点とする 3. K-means法により代表 点を更新 4. すべての代表点について 2.に戻る 23

K-means++ ◦任意の個数の初期値をうまく選ぶ方法 ◦ 外れ値に当たったり、近いところに初期値 が固まったりしにくい ◦考え方 ◦ できるだけ互いに離れたサンプルを代表点 として選ぶ ◦ 確定的に選ぶのではなく、確率を使う 24

K-means++ ◦代表点を𝐶 = {𝑐1 , … , 𝑐𝐾 }とする ◦サンプルと代表点との最短距離 𝐷 𝑥|𝐶 = min 𝑥 − 𝑐𝑘 𝑘 ◦サンプルが次の代表点に選ばれる確率 𝑃 𝑥𝐶 ∝𝐷 𝑥𝐶 2 25

K-means++ 1. サンプル中からランダムに１個点を選び、 代表点𝑝1 とする。 2. 代表点集合 𝑃 = {𝑝1 }とする。 3. 確率 𝑃(𝑥|𝐶)に従ってサンプルxを選び、C に加える。 4. 代表点の数が目標未満なら3へ 26

GMM ◦GMMはクラスタリングアルゴリズムと して使える ◦ 𝑝 𝑥 = σ𝐾 𝑘=1 𝑤𝑘 𝑁(𝑥; 𝜇𝑘 , Σ𝑘 ) ◦ EMアルゴリズムにより学習 ◦ 𝑝 𝑥 𝑘 = 𝑁 𝑥; 𝜇𝑘 , Σ𝑘 𝑝 𝑥 𝑘 𝑝(𝑘) ◦𝑝 𝑘 𝑥 = 𝑝(𝑥) 𝑤𝑘 𝑁(𝑥; 𝜇𝑘 Σ𝑘 ) = σ𝑘 𝑤𝑘 𝑁(𝑥; 𝜇𝑘 Σ𝑘 ) 27

2 クラスタリング例 -2 -1 y 0 1 ４クラス、全共分散 赤のクラスタが2つに分 かれているところに注目 -1 0 1 2 3 x 28

クラスタリング例 2 ◦信頼区間の楕円はこんな感じ -2 -1 y 0 1 ガウス分布が交差している部分 ではクラスタが2つに分かれるこ とがある（それがいいかどうか は目的次第） -1 0 1 2 x 3 29

2 1 0 -2 -1 y -2 -1 y 0 1 2 クラスタリング例 -1 0 1 2 3 x 全次元全分布等分散にするとkmeansとほぼ同じ結果になる -1 0 1 2 3 x クラスタが入れ子になる場合があ る（正規分布近似をするため） この例は全次元等分散で重みが 分布ごとに異なる 30

Hard/Soft Clustering ◦いままでは1つのサンプルが1つのクラ スタに属していた ◦GMMの場合「クラスタに属する確率」 𝑃(𝑘|𝑥)が使える ◦ ある「強さ」で1つのサンプルが2つ以上の クラスタに属する→ソフトクラスタリング （ファジィクラスタリング） 31

外れ値の問題 6 4 -2 0 2 x[,2] 2 -2 0 x[,2] 4 6 ◦K-means法の結果 -2 -1 0 1 2 3 4 -2 x[,1] -1 0 1 2 3 4 x[,1] 左上の外れ値はどうクラスタリングするのがいいのか？ 32

外れ値の問題 ◦そもそも外れ値をクラスタに入れる必 要があるのか？ ◦ 応用によっては「点がある領域で連続して いる」ことが重要な場合がある ◦ どこからも離れた点は「ノイズ」として除 外する 33

DBSCAN データが「まとまって、つながっている」 部分を検出 ◦ 点の近さと密度による判定 ◦ 外れ値はクラスタに所属しない 1 2 3 4 例えばこんなデータをクラスタ に分けるとどうなるか -1 0 y 丸くないクラスタ -2 外れ値 -3 -2 -1 0 1 2 x 34

-3 -2 -1 0 x K=2 1 2 4 -2 -1 0 y 1 2 3 4 3 2 1 -2 -1 0 y -2 -1 0 y 1 2 3 4 K-meansの場合 -3 -2 -1 0 x K=3 1 2 -3 -2 -1 0 1 2 x K=4 35

DBSCAN 点の間の関係ではなく、次の性質に注目 ◦ ある部分にどれだけ点が密集しているか ◦ 密集した点が連続しているか 半径epsの中に点がminPts個 以上ある場合に、それらの点 が1つのクラスタに属する 外れ値は孤立したクラ スタになる 集団間の距離があれば 別クラスタになる 36

DBSCANアルゴリズム クラスタ番号 𝐶 ← 0 すべてのマークされていない点Pについて 点Pをマークする 𝑛 ← 𝑃から距離eps以内にある点の数 if n < minPts then Pを「ノイズ」としてマーク else 𝐶 ←𝐶+1 上の 点Pの近傍の点と、その eps 近傍にあって密度がminPts以 点をすべてクラスタCとしてマークする 37

-3 -2 -1 0 x Eps=1.0 1 2 4 -2 -1 0 y 1 2 3 4 3 2 1 y 0 -1 -2 -2 -1 0 y 1 2 3 4 クラスタリング例 -3 -2 -1 0 x Eps=1.1 1 2 -3 -2 -1 0 1 2 x Eps=1.2 minPts=5 38

-3 -2 -1 0 x minPts=1 1 2 4 -2 -1 0 y 1 2 3 4 3 2 1 y 0 -1 -2 -2 -1 0 y 1 2 3 4 クラスタリング例 -3 -2 -1 0 1 x minPts=5 2 -3 -2 -1 0 1 2 x minPts=10 Eps=1 39

演習 ◦ Irisデータ（講義第5回参照）を適当なアルゴリズ ムでクラスタリングし，可視化してください． • クラスタリングによる分類結果と元の 品種の対応がわかるとよい • 例えばこんな感じ • クラスタ数を３にしたとき，元の品種と クラスタリング結果の対応を見てみる 1 2 3 setosa 0 0 50 versicolor 2 48 0 virginica 36 14 0 40

どうやって計算すればよいか ◦ 例によって書ける人はRなりPythonなり 使ってください ◦ 書けない人用：Wekaを使う ◦ 各種クラスタリングができる ◦ EM (GMM) ◦ k-means ◦ 階層的クラスタリング ◦ 参考リンク ◦ https://www.tutorialspoint.com/weka/weka_clus tering.htm 41

• https://www.tutorialspoint.com/weka/weka_clus