クラスタリング

クラスタリング Hierarchal clustering，Spectral clusterin，クラスタ数推定はない 公⽴⼩松⼤学 藤⽥ ⼀寿 Ver.20230509

クラスタリングとは • クラスタリングとは，機械がデータをクラスタに⾃動で分けることで ある． • クラスタとはデータ点のかたまりのことで，何らかの基準でデータ点をグ ループ分けしてできたグループのことである． クラスタ • クラスタの意味は後で考える． データ 機械が何らかの 基準でデータ点 をまとめる． 3つクラスタがある

例：クラスタリングによる領域分割 • 画像を⾊の類似性により領域を分割する． • 類似した⾊をまとめるときにクラスタリングを⽤いる． 似た色をまとめる

グループにまとめる基準 • 機械がデータ点をグループにまとめるためには基準が必要である． • 基準の例 • ユークリッド距離 • 𝑑 𝒙, 𝒚 = 𝑥! − 𝑦! " + 𝑥" − 𝑦" " +⋯= 𝒙−𝒚 = 𝒙−𝒚 " • ミンコフスキー距離 • 𝑑 𝒙, 𝒚 = 𝑥! − 𝑦! # + 𝑥" − 𝑦" # +⋯ !/# = 𝒙−𝒚 # • マハラノビス距離 • 𝑑 𝒙, 𝒚 = 𝒙 − 𝒚 % Σ &! (𝒙 − 𝒚) • Σは共分散⾏列 • コサイン類似度 • 𝑆 𝒙, 𝒚 = cos 𝜃 = 𝒙⋅𝒚 𝒙 𝒚 距離：似ていれば似ているほど小さい値 類似度：似ていれば似ているほど大きな値

クラスタリング⼿法の分類 クラスタリング Partitional Distance-based K-means Model-based GMM Density-based DBSCAN Hierarchical Graph-based Spectral clustering Agglomerative Single-linkage Complete-linkage

k-means

⽤語の紹介 • データ点 データ点 • データセットに含まれる1つのデータ • クラスタ 2 (i) • データ点の集まり • セントロイド • クラスタの中⼼ 0 −2 −2 0 2 セントロイド

k-means • ユークリッド距離を基準にクラスタリングする⼿法 • k-meansでは，データ点が所属するクラスタとクラスタの中⼼である 「セントロイド」と呼ばれるベクトルを繰り返し求めることでクラス タリングを⾏う． クラスタが求まった． データ点 クラスタから セントロイド を求める． 所属クラスタ を決める． クラスタ クラスタ セントロイド セントロイド セントロイドはクラ スタの平均になる．

所属クラスタの決め⽅ • データ点が所属するクラスタはセントロイドを基準に決める． • データ点は，それに最も近いセントロイドが所属するクラスタに所属する． ２ １ 1 このデータ点はセントロイド2よりセ ントロイド1の方に近いためクラスタ 1に所属する． 遠い 2 近い このデータ点はセントロイド1よりセ ントロイド2の方に近いためクラスタ 2に所属する．

セントロイドの求め⽅ • クラスタに所属するデータ点の平均をセントロイドとする． 2 1 1 1 1 1 １ 1 1 1 1 クラスタ1に所属するデータ点の平均 ベクトル 2 2 2 ２ 2 2 2 2 2 クラスタ2に所属するデータ点の平均 ベクトル

K-meansのアルゴリズム • K-meansでは次の⼿順でクラスタリングを⾏う． 1. セントロイドを初期化する． 2. 各データ点の所属クラスタを決める． 3. セントロイドを計算する． 4. N回繰り返したら（所属クラスタの変更がなければ）終了．そうで なければ2へ．

クラスタリング結果 クラスタ 2 (a) 2 0 0 −2 −2 −2 0 学習前 2 (f) −2 0 学習後 2 Xがセントロイドを表している． 学習前はセントロイドはランダムに初期化されるため，クラスタの中心にない． 学習後はセントロイドはクラスタの中心に移動し，データ点もクラスタに所属している．

k-meansの⽬的関数 • 良いクラスタリングとはどういうものか？ • データ点とそのデータ点が所属するクラスタのセントロイドとの距離の総和が最⼩ になるとき最適なクラスタリング結果が得られると考える． • データ点とそのデータ点が所属するクラスタのセントロイドとの距離の総和は， $ & データ点 𝐽 = # # 𝑟!% 𝒙! − 𝒎% !"# %"# ' 例えば，データ点1がクラスタ2に所属している場合， 𝑟!! = 0, 𝑟!" = 1, 𝑟!# = 0, 𝑟!$ = 0, … つまり，所属クラスタに対応する 𝑟!"のみ1で，それ以外0になる． セントロイド • 𝒙! はデータ点のベクトル， 𝒎" はクラスタ𝑘のセントロイド， 𝑟!" はデータ点𝑖がクラ スタ𝑘に所属していれば1，そうでなければ0となる指⽰変数である． • 良いクラスタリング結果を得るためには，この式を学習により最⼩化すれば良い． 学習を通し最⼤化もしくは最⼩化したい関数のことを⽬的関数という．

⽬的関数の最⼩化 • まず，𝑚" を固定した状態で⽬的関数を最⼩化する指⽰変数𝑟!" を求める． • ⽬的関数を各データ点に関する項に分解してみる． & • 𝐽 = ∑% !#$ ∑"#$ 𝑟!' 𝒙! − 𝒎" ( = ∑& "#$ 𝑟$" 𝒙$ − 𝒎" ( + ∑& "#$ 𝑟(" 𝒙( − 𝒎" ( … • データ点𝑖についての項は • 𝐽! = ∑& "#$ 𝑟!" 𝒙! − 𝒎" ( • である．これをそれぞれ最⼩化することで⽬的関数を最⼩化することができる． • 𝑟!" はデータ点𝑖がクラスタ𝑘に所属するときのみ1でそれ以外0であるので，𝐽! を最⼩ 化するには， 𝒙! − 𝒎" ( が最⼩になるクラスタ𝑘にデータ点𝑖を所属させれば良い． つまり，指⽰変数𝑟!" は • 𝑟!" = -1, if 𝑘 = argmin' 𝒙! − 𝒎' 0, otherwise ( 補⾜ 𝐽! = ∑% "#$ 𝑟!" 𝒙! − 𝒎" & + 𝑟') 𝒙' − 𝒎) ) + ⋯で ある． 𝑟'* は1つだけで1で，それ以外０だから， 𝐽' は𝐾個ある 𝒙' − 𝒎* ) のうちのどれか1つである． 𝐽' を最⼩化したければ， 𝐾個 ある 𝒙' − 𝒎* )のうち最⼩のものを選べば良い． = 𝑟'( 𝒙' − 𝒎( )

⽬的関数の最⼩化 ' ( • 次に，指⽰変数𝑟!" を固定した状態で⽬的関数𝐽 = ∑% !#$ ∑&#$ 𝑟!& 𝒙! − 𝒎& を最⼩化するセントロイド𝒎& を求める．⽬的関数の微分が0のとき⽬的関 数は最⼩と想定されるので， • )* )𝒎1 = −2 ∑% ! 𝑟!& 𝒙! − 𝒎& = 0 % • ∑% !#$ 𝑟!& 𝒙! − ∑!#$ 𝑟!& 𝒎& =0 • 𝑁& 𝒎& = ∑% !#$ 𝑟!& 𝒙! • 𝒎& = $ ∑% 𝑟 𝒙 %1 !#$ !& ! • つまり，⽬的関数を最⼩化するセントロイドは所属するデータ点の平均ベ クトルになる． • ここで𝑁" = ∑% !#$ 𝑟!" とした．これは，クラスタ𝑘に所属するデータ点の数である．

⽬的関数の最⼩化 • 変数を固定化して状態で，⽬的関数を最⼩化する指⽰変数𝑟34 とセント ロイド𝒎4 を求めた． • つまり，先のスライドで求めた指⽰変数𝑟34 とセントロイド𝒎4 では⽬的 関数を最⼩化していない． • ⽬的関数を最⼩化するには，変数を固定化して状態で⽬的関数を最⼩ 化する指⽰変数𝑟34 とセントロイド𝒎4 を交互に何度か求めることで，⽬ 的関数を最⼩化する指⽰変数𝑟34 とセントロイド𝒎4 を求める．

k-meansのアルゴリズム • k-meansの場合，先に⽰した⽬的関数を最⼩化することでクラスタリングを達成す る．⽬的関数を最⼩化するアルゴリズムは次のとおりである． 1. クラスタ数k，セントロイド𝑚1， … ，𝑚𝑗， … ， 𝑚𝑘 を初期化する． 2. データ点𝑖を最も近いセントロイドを持つクラスタに所属させる． 𝑟56 = 61, 3. if 𝑘 = argmin7 𝒙5 − 𝒎7 0, otherwise セントロイド𝒎" を次の式で求める． 𝒎6 = 1 G 𝑟56 𝒙5 ∑5 𝑟56 " 終了条件は難しい．所属クラスタは永遠に変 化し続ける場合もある． 5 4. 所属クラスタが変化しなかった場合，もしくは⽬的関数の値が収束した場合， もしくは指定の回数2，3を実⾏した場合は終了，そうでない場合2に戻る．

処理2：データ点をクラスタに所属させる すべてのデータ点について所 属クラスタを決定した結果 初期状態 2 (a) 2 (b) 処理2 0 セントロイド 0 セントロイド −2 −2 0 このデータ点は⻘xに近い ので⻘のクラスタに所属 2 −2 −2 このデータ点は⾚xに近いの で⾚のクラスタに所属 0 2

処理３：セントロイドの更新 処理2を適用した結果 2 セントロイドを計算した結果 (b) 2 0 0 −2 −2 −2 0 2 (c) −2 0 2 処理2で得られたクラスタに所属するデータ点の平均がセントロイドとなる・

k-meansの学習過程 2 (a) 2 (b) 2 0 0 0 −2 −2 −2 −2 0 −2 2 0 2 (c) −2 処理2 2 (d) 2 0 0 −2 −2 −2 0 2 −2 0 2 −2 処理3 (g) 2 (h) 2 0 0 −2 −2 −2 0 処理3 2 −2 0 処理2 0 2 処理2 0 −2 (f) 0 処理2 2 2 処理3 (e) −2 2 0 2 (i) −2 0 処理3 2

k-meansによる領域分割（減⾊）の例

k-meansの利点と⽋点 外れ値 • 利点 • 実装が簡単である． 外れ値に影響を受けやすい． • アルゴリズムが分かりやすい． • 結果を理解しやすい． • k-meansは空間をVoronoi cell（多⾓形）に分ける． • ⽋点 • 外れ値に弱い． • クラスタリング結果が初期値に依存する． • k-means++で改善 適切にクラスタリングで きる． 適切にクラスタリ ングできない． 混合等⽅ガウス分布のみ適切にクラスタリ ング出来ることが⽋点と書いたが，これが 利点の分かり易さを⽣み出している． • データの分布が混合等⽅ガウス分布のときにのみ適切にクラスタリングで きる（何をもって適切というかは難しい問題だが）．

k-meansの改変 • k-meansでは，近いデータを同じクラスタとしてグループ分けした． • k-meansでは遠い近いの基準にユークリッド距離を⽤いた． • 𝑑 𝒙$ , 𝒙( = 𝒙$ − 𝒙( 0 𝒙$ − 𝒙( = 𝒙$ − 𝒙( • 基準として別のものを⽤いることも可能である． • コサイン類似度 • 𝑆 𝒙! , 𝒙" = 𝒙(' 𝒙) 𝒙' 𝒙) • コサイン類似度を使⽤した場合は⽬的関数を最⼤化する． • マハラノビス距離 • 𝑑 𝒙! , 𝒙" = % &! 𝒙! − 𝒙" Σ 𝒙! − 𝒙" • ミンコフスキー距離 • 𝑑 𝒙! , 𝒙" = ∑8 5 𝑥!5 − 𝑥"5 # !/# !/"

k-meansの応⽤ • クラスタリング • 𝑘個のクラスタにデータを分けることが可能である． • 既存のデータ点だけではなく未知のデータ点に対しても，所属クラスタを 決めることができる． クラスタ2 クラスタ1 セントロイド ２ １ セントロイド 近い 未知データ 遠い クラスタ1のセントロイドに近いか らクラスタ1に所属するデータだ．

k-meansの応⽤ • 量⼦化 • k-meansにより𝑘個のセントロイドを得ることができる． • k-meansはデータを𝑘個のセントロイドベクトルに代表させたと⾔える． • ⾔い換えれば，データをk個のベクトルに圧縮したといえる． • データを少数のベクトルに置き換えることを量⼦化（ベクトル量⼦化）と いう． クラスタ1 １ セントロイド クラスタ2 ２ １ ２ セントロイド たくさんあるデータ点をセ ントロイドに置き換える．

混合ガウス分布 (Gaussian mixture model)

model based clustering • データが何らかの混合分布から⽣成されたと考えてクラスタリングす る⽅法をmodel based clusteringという． • 混合ガウス分布を想定することがほとんど(Gaussian Mixture Model: GMM)である． • model based clusteringは混合分布のパラメタの推定問題となる．

分布とモデル • データはある確率分布から⽣じる．その確率分布は神様しか知らない． • 我々はそのデータがどのような確率分布から⽣成されたか想定（想像） することはできる． • 想定した確率分布をモデルという． ⼈は知ることはできない 真の確率分布 𝑝神様 データを⽣成した 確率分布は分から ない． 分からないから， ある確率分布から データが⽣成され たと想定しよう． ⽣成 データ

ガウス分布 • 釣鐘型の分布をガウス分布（正規分布）という． • 最もよく⽤いられる確率分布である． N (x|µ, • 1次元ガウス分布 • 𝑁 𝑥 𝜇, 𝜎 = $ (12 !/# exp − $ (2 # 𝑥−𝜇 ( 2 ) 2 • 𝜇は平均， 𝜎は分散である． µ x • D次元ガウス分布 • 𝑁 𝒙 𝝁, Σ = $ (1 $/# $ 3 !/# exp − $ ( 𝒙 − 𝝁 0 Σ 4$ 𝒙 − 𝝁 • 𝝁はD次元の平均ベクトル， Σは𝐷×𝐷の共分散⾏列，|Σ|はΣの⾏列式である．

混合ガウスモデル(GMM: Gaussian Mixture Model) • 複数のガウス分布からなる確率分布を混合ガウス分布という． • 𝑝 𝒙 = ∑J 4HI 𝜋4 𝑁(𝒙 ∣ 𝝁4 , Σ4 ) • 𝐾はガウス分布の数，𝑁はガウス分布，𝜋4 は混合係数， Σ4 は共分散⾏ 列を表す． • データが複数のガウス分布から⽣成されていると仮定したときの確率 モデルを混合ガウスモデルという． 1 p(x) (a) 0.5 0.2 0 x 1次元混合ガウス分布の例 3つのガウス分布が混合されている． 0.3 0.5 0 0.5 1 2次元混合ガウス分布の例 3つのガウス分布が混合されている． 左図は個々のガウス分布の様子とそれぞれの混合係数を表す． 右図は混合ガウス分布の確率分布を表す．

混合係数 • 混合係数はすべて⾜すと1になる． • ∑J 4HI 𝜋4 = 1 • つまり， 𝜋4 は確率とみなせる．

確率変数z • ここで，𝒛 = 𝑧$ , … , 𝑧" , … , 𝑧& ，𝑧" = 0,1 ， ∑" 𝑧" = 1という確率変数を導⼊する． • ∑" 𝑧" = 1だから，𝑧" = 1ならば，それ以外の要素は０である（1-of-k coding）． *+ ∏) &'( 𝜋& = 1× ⋯×𝜋& × ⋯×1となる． * 何故ならば𝑧& = 0ならば𝜋& + = 1だか らである． • 𝑝 𝑧" = 1 = 𝜋" • とする．これを書き⽅を変えると 5 % • 𝑝 𝒛 = ∏& "#$ 𝜋" • と書ける． • 𝒛の値が与えられた下での𝒙の確率分布は • 𝑝 𝒙 𝑧" = 1 = 𝑁(𝒙 ∣ 𝝁" , 𝚺" ) これはガウス分布𝑘のみを想定したときの 𝒙が⽣じる確率とみなせる． • これも書き直すと • 𝑝 𝒙 ∣ 𝒛 = ∏& "#$ 𝑁 𝒙 𝝁" , 𝚺" • と書ける． 5%

混合ガウス分布 • 𝒙と𝒛の同時分布は𝑝 𝒙, 𝒛 = 𝑝 𝒙 ∣ 𝒛 𝑝 𝐳 で与えられる． • これを𝒛について周辺化すると • 𝑝 𝒙 = ∑𝒛 𝑝 𝒙 ∣ 𝒛 𝑝 𝒛 = ∑J 4HI 𝜋4 𝑁(𝒙 ∣ 𝝁4 , 𝚺4 ) • となる．これは混合ガウス分布と同じ形である． ) ) * 𝑝 𝒙 = 7 𝑝 𝒙 ∣ 𝒛 𝑝 𝒛 = 7 : 𝜋& + : 𝑁 𝒙 𝝁& , 𝚺& ) 𝒛 = 7 : 𝜋& 𝑁 𝒙 𝝁& , 𝚺& 𝒛 &'( *+ ) &'( ) *+ * = 7 : 𝜋& + 𝑁 𝒙 𝝁& , 𝚺& *+ 𝒛 &'( = 7 𝜋& 𝑁 𝒙 𝝁& , 𝚺& 𝒛 &'( &'( 𝒛 = 𝑧$, … , 𝑧" , … , 𝑧& ，𝒛は1-of-k codingだから 𝑧& = 1, 𝑧,-& = 0． * + ∏) = 1× ⋯×𝜋& 𝑁 𝒙 𝝁& , 𝚺& × ⋯×1 = 𝜋& 𝑁 𝒙 𝝁& , 𝚺& となる． &'( 𝜋& 𝑁 𝒙 𝝁& , 𝚺& 𝒛は1-of-k codingだから𝑘種類ある．だからΣ𝒛 は𝑘回⾜していることになる．

負担率 • 逆に，𝒙が観測されたとき，それがガウス分布𝑘から⽣成された確率を 考える．ここでベイズ定理を⽤いて • 𝛾 𝑧4 = 𝑝 𝑧4 = 1 𝒙 = L M6 HI L 𝒙 𝑧4 L(𝒙) =1 N O(𝒙∣𝝁6 ,R6 ) 789 N7 O(𝒙∣𝝁7 ,R7 ) = ∑: 6 • と書ける． • 𝛾 𝑧4 は混合要素𝑘が𝒙の観測を説明する度合いと解釈できるを表す負 担率と考えることができる．

GMMを使ったクラスタリング • データは混合ガウス分布から⽣成されたと仮定する． • 混合ガウス分布を構成するガウス分布𝑘は，データ点がクラスタ𝑘から ⽣成される確率を表すとする． • 逆に考えれば，データ点が⽣成される可能性（負担率）が最も⾼いガ ウス分布に対応するクラスタにデータ点は所属すると考えられる． N (x|µ, クラスタ1はガウ ス分布1から生じ たと考える． 2 ) ガウス分布1 N (x|µ, 2 １ µ 2 ) ガウス分布2 クラスタ2はガウ ス分布2から生じ たと考える． 2 x ２ µ x ガウス分布の平均がセ ントロイドとなる．

最尤推定 • GMMを⽤いたクラスタリングは，GMMのパラメタを求める問題とな る． • GMMのパラメタを求めるのに最尤推定を⽤いる． • データ集合X = {𝒙I , … , 𝒙O }があり，これらが互いに独⽴に⽣成されたと 仮定する (i.i.d.: independent and identically distributed)． • このとき，log尤度は次のように書ける． J • ln 𝑝 𝑋 𝝅, 𝝁, 𝚺 = ∑O SHI ln ∑4HI 𝜋4 𝑁 𝒙S 𝜇4 , Σ4 • これを最⼤にするパラメタを最適解とし，このパラメタを探す最尤推 定という． 𝑝 𝑋 𝝅, 𝝁, 𝚺 はパラメタ 𝝅, 𝝁, 𝚺のときデータ集合 • しかし，解析的に求めることは困難である． 𝑋が出現する確率である．この確率が最も高いパ ラメタが良いパラメタということになる．この確 率を尤度という．logは単調増加関数なので尤度 の対数の最大値を取るパラメタは，尤度の最大値 を取るパラメタと一致する．

最尤推定
• 関数が最⼤値のとき微分は0の極値となる．尤度関数が最⼤のパラメタの
とき，尤度関数の微分は0となることが予想される．
• まず，平均𝝁& について尤度関数を微分する．
%

&

C#$

!#$

𝜕 ln 𝑝 𝑋 𝝅, 𝝁, 𝚺
𝜕
=
4 ln 4 𝜋! 𝑁 𝒙C 𝜇! , Σ!
𝜕𝝁"
𝜕𝝁"
%

=4
C#$

•

𝜋" 𝑁 𝒙" 𝜇" , Σ"
Σ"4$(𝒙C − 𝝁" ) = 0
&
∑!#$ 𝜋! 𝑁 𝒙C 𝜇! , Σ!

𝒙& 𝜇& , Σ&
= 𝛾(𝑧B& )は負担率なので
∑<
9:; @9 % 𝒙B 𝜇! , Σ!

logの微分 log 𝑓 𝑥

*

=

合成関数の微分 𝑓 𝑔 𝑥

@1 %

+(
• ∑)
𝛾(𝑧
)
Σ
&*
&'(
* (𝒙& − 𝝁* ) = 0

• と書ける．この式を満たす平均𝝁& を求めれば良い．

+! ,
+(,)
*

= 𝑓 * 𝑔 𝑥 𝑔* (𝑥)

最尤推定 TI • ∑O SHI 𝛾(𝑧S4 ) Σ4 (𝒙S − 𝝁4 ) = 0 • を解く． Σ) を両辺に書けるとΣ) Σ)*+ = 𝐼 となりΣ4TIは消えるとして 逆行列がないと計算できない… 整理すると， ∑F CDE - .CG 𝒙C • 𝜇4 = F ∑CDE -(.CG ) • 𝑁4 = ∑O SHI 𝛾(𝑧S4 )とおくと • 𝜇4 = I ∑O 𝛾 O6 SHI 𝑧S4 𝒙S % • 同様に微分が0となる共分散を求めると 1 0 Σ" = 𝑁" 4 𝛾 𝑧C" 𝒙C − 𝝁" 𝒙C − 𝝁" C#$ 𝑁& はクラスタkに割り当てられた実 質的な数と解釈できる．

最尤推定 • 最後に，混合係数𝜋4 を求める．混合係数には総和が1という制約条件が ある．この制約条件のもと尤度関数を最⼤化しなければならない． • このようなとき，ラグランジュの未定乗数法を⽤いる． • 𝐿 = ln 𝑝(𝑋 ∣ 𝜋, 𝝁, Σ) + 𝜆 ∑J 4HI 𝜋4 − 1 • という関数を考え，これを微分して0となる𝜋4 を求める．そうすると， 3 𝒙) 3 • ∑12+ ∑I 43 HDE H 𝜇) , Σ) +𝜆 =0 𝒙1 𝜇5 , Σ5 • となる．ここで再び負担率が登場する．

最尤推定 • 両辺𝜋4 をかけると 𝒙4 𝜇4 , Σ4 + 𝜆𝜋4 = ∑O SHI 𝛾 𝑧S4 + 𝜆𝜋4 = 0 789 N7 O 𝒙S 𝜇3 , Σ3 N O 6 • ∑O SHI ∑: • これを計算すると • 𝜆 = −𝑁 • を得る．これを⽤いると • 𝜋4 = O6 O • となる． % 4 𝛾 𝑧C" + 𝜆𝜋" = 0 C#$ & 𝜆𝜋" = −𝑁" & 𝜆 4 𝜋" = − 4 𝑁" "#$ "#$ 𝜆 = −𝑁 5 7 𝛾 𝑧4& − 𝑁𝜋& = 0 4'( −𝑁𝜋" = −𝑁" 𝑁" 𝜋" = 𝑁

EM アルゴリズム • GMMでクラスタリングを⾏うためには混合ガウス分布のパラメタを決 める必要がある．しかし，解析的に求めることは困難である． • ここでEMアルゴリズムを⽤い，尤度関数を最⼤にするパラメタを探す ことにする． • 混合ガウス分布を⽤いたクラスタリングでは，EMアルゴリズムを⽤い 混合ガウス分布のパラメタを求める． • GMMを⽤いたクラスタリングは，EMアルゴリズムを⽤いGMMのパラメ タを求めることである．

GMMのためのEMアルゴリズム 1. データ集合𝑋 = {𝒙I , … , 𝒙O }があるとする． 2. パラメタ𝝁4 , Σ4 , 𝜋4 を適当な数値で初期化する． 3. 現在のパラメタで負担率を求める． 4. 3で計算した負担率を⽤い，パラメタ𝝁4 , Σ4 , 𝜋4 を計算する． 5. 終了条件を満たしていなければ3に戻る． 2 2 2 L=1 0 0 −2 0 −2 −2 0 (a) 2 2 −2 −2 0 (b) 2 2 L=2 (d) 2 2 0 (f) 2 0 −2 0 (c) L = 20 0 −2 0 2 L=5 0 −2 −2 −2 −2 0 (e) 2 −2

GMMとk-means • GMMはデータが所属するクラスタを1つに絞らない． • GMMによるクラスタリングでは所属クラスタは負担率で表される． • 例えば，2つのクラスタに分ける場合，あるデータ点は⼀つのガウス分布の負担 率が0.8，もう⼀つのガウス分布の負担率は0.2となったとする．所属クラスタを 負担率で表すと，所属するかどうかを0か1ではなく連続値で表すことになる． • このように所属クラスタを連続値で表すやり⽅をsoft asignmentといい，soft asignmentを⾏うクラスタリングをsoft clustering (fuzzy clustering)という． • k-meansのようにクラスタに所属するかどうかを0か1で決めることをhard asignmentといい，このようなクラスタリングをhard clusteringという． 2 0 −2 −2 k-meansのクラスタリング結果 0 (b) 2 GMMのクラスタリング結果 所属クラスタがグラデーションになっている．

GMMとk-means • k-meansは同じ分散を持つ等⽅ガウス分布で構成されるGMMといえ る． • マハラノビス距離を⽤いた場合は，それぞれのクラスタが異なる分散，共 分散を持つことを想定している． • コサイン類似度を⽤いた場合は，混合von Mises Fisher分布を想定してい ることになる．

GMMとk-means • Eステップは，負担率を計算している．これはk-meansにおける所属 クラスタの計算に対応する． • Mステップでは，パラメタの計算をしている．これは，k-meansにお けるセントロイドの計算と対応する．

クラスタリング⼿法の分類 クラスタリング Partitional Distance-based K-means Model-based GMM Density-based DBSCAN Hierarchical Graph-based Spectral clustering Agglomerative Single-linkage Complete-linkage