クラスタリング

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

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

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

クラスタリング⼿法の分類

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

k-means

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

k-means • ユークリッド距離を基準にクラスタリングする⼿法 • k-meansでは，クラスタの中⼼である「セントロイド」と呼ばれるベ クトルを求めながらクラスタリングを⾏う． 学習 学習前の セントロイド クラスタ 学習後の セントロイド クラスタ 十分学習する と，セントロ イドはクラス タの中心とな る．

クラスタの決め⽅ • 学習したセントロイドからクラスタを決める． ２ １ 1 このデータ点はセントロイド2よりセ ントロイド1の方に近いためクラスタ 1に所属する． 遠い 2 近い このデータ点はセントロイド2よりセ ントロイド1の方に近いためクラスタ 1に所属する．

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

k-meansの⽬的関数 • 良いセントロイドと良いクラスタリング結果はどういうものか • データ点とそのデータ点が所属するクラスタのセントロイドとの距離の総 和が最⼩になるとき最適なクラスタリング結果が得られると考える． • データ点とそのデータ点が所属するクラスタのセントロイドとの距離の総 和は， データ点 セントロイド • 𝒙! はデータ点のベクトル， 𝒎" はクラスタjのセントロイド， 𝑟!" はデータ点 iがクラスタjに所属していれば1，そうでなければ0となる変数． • この式を最⼩にするよう学習すれば良い．学習を通し最⼤化もしくは最⼩ 化したい関数のことを⽬的関数という．

k-meansのアルゴリズム • k-meansの場合，先に⽰した⽬的関数を最⼩化することでクラスタリング を達成する．最⼩化するアルゴリズムは次のとおりである． • k-meansのアルゴリズム 1. クラスタ数k，セントロイド𝑚1， … ，𝑚𝑗， … ， 𝑚𝑘を初期化 2. すべてのデータ点を最も近いセントロイドを持つクラスタに所属させる 3. セントロイドcjを次の式で計算する 𝒄* = 1 & 𝑟+* 𝒙+ ∑+ 𝑟+* + 4. 各クラスタに所属するデータ点の個数が変化しなかった場合もしくは⽬ 的関数の値が収束した場合もしくは指定の回数2，3を実⾏した場合は 終了，そうでない場合2に戻る

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

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

k-meansの学習過程 処理2 処理3 処理2 処理3 処理2 処理2 処理3 処理2

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

k-meansの利点と⽋点 • 利点 • 実装が簡単である． • アルゴリズムが分かりやすい． • 結果を理解しやすい． • k-meansは空間をVoronoi cellに分ける． • ⽋点 • 外れ値に弱い． • クラスタリング結果が初期値に依存する． • k-means++で改善 • データの分布が等⽅ガウス分布のときにのみ適切にクラスタリングできる （何が適切なのかは難しい問題だが）

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

k-meansの応⽤ • クラスタリング • k個のクラスタにデータを分けることが可能 • データの類似性を調べるために使⽤できる クラスタ2 クラスタ1 セントロイド ２ １ セントロイド 近い 遠い 未知データ クラスタ1のセントロイドに近いか らクラスタ1に所属するデータだ．

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

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

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

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

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

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

混合係数 • 混合係数はすべて⾜すと1になる． • ∑$ !"# 𝜋! = 1 • つまり， 𝜋! は確率とみなせる．

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

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

負担率 • 逆に，𝒙が観測されたとき，それがガウス分布𝑘から⽣成された確率を 考える．ここでベイズ定理を⽤いて • 𝛾 𝑧! = 𝑝 𝑧! = 1 𝒙 = & '1 "# & 𝒙 𝑧! &(𝒙) =1 + ,(𝒙∣𝝁1 ,01 ) 234 +2 ,(𝒙∣𝝁2 ,02 ) = ∑5 1 • と書ける． • 𝛾 𝑧! は混合要素𝑘が𝒙の観測を説明する度合いと解釈できるを表す負 担率と考えることができる．

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

最尤推定
• GMMを⽤いたクラスタリングは，GMMのパラメタを求める問題とな
る．
• GMMのパラメタを求めるのに最尤推定を⽤いる．
• データ集合X = {𝒙# , … , 𝒙, }があり，これらが互いに独⽴に⽣成されたと
仮定する (i.i.d.: independent and identically distributed)．
• このとき，log尤度は次のように書ける．
$
• ln 𝑝 𝑋 𝝅, 𝝁, 𝚺 = ∑,
2"# ln ∑!"# 𝜋! 𝑁 𝒙2 𝜇! , Σ!

• これを最⼤にするパラメタを最適解とし，このパラメタを探す最尤推
定という．
• しかし，解析的に求めることは困難である．

𝑝 𝑋 𝝅, 𝝁, 𝚺 はパラメタ 𝝅, 𝝁, 𝚺のときデータ集合
𝑋が出現する確率である．この確率が最も高いパ
ラメタが良いパラメタということになる．この確
率を尤度という．logは単調増加関数なので尤度
の対数の最大値を取るパラメタは，尤度の最大値
を取るパラメタと一致する．

最尤推定 • 関数が最⼤値のとき微分は0の極値となる．尤度関数が最⼤のパラメタ のとき，尤度関数の微分は0となることが予想される． • まず，平均𝝁! について尤度関数を微分する． @ . ?/! +/! 𝜕 ln 𝑝 𝑋 𝝅, 𝝁, 𝚺 𝜕 = ? ln ? 𝜋+ 𝑁 𝒙? 𝜇+ , Σ+ 𝜕𝝁𝜕𝝁@ =? ?/! • 𝜋- 𝑁 𝒙- 𝜇- , ΣΣ-&!(𝒙? − 𝝁- ) = 0 . ∑+/! 𝜋+ 𝑁 𝒙? 𝜇+ , Σ+ logの微分 log 𝑓 𝑥 ! = 合成関数の微分 𝑓 𝑔 𝑥 𝒙! 𝜇! , Σ! = 𝛾(𝑧2! )は負担率なので ∑5 + , 𝒙 𝜇 , Σ 2 3 3 234 2 +1 , 74 • ∑5 𝛾(𝑧 ) Σ 26 234 6 (𝒙2 − 𝝁6 ) = 0 • と書ける．この式を満たす平均𝝁! を求めれば良い． "! # "(#) ! = 𝑓 ! 𝑔 𝑥 𝑔! (𝑥)

最尤推定
4#
• ∑,
2"# 𝛾(𝑧2! ) Σ! (𝒙2 − 𝝁! ) = 0

• を解く． Σ6 を両辺に書けるとΣ6
整理すると，

Σ674 = 𝐼 となりΣ!4#は消えるとして
逆行列がないと計算できない…

∑:
9 :7; 𝒙7
• 𝜇! = 789
∑:
789 9(:7; )

• 𝑁! = ∑,
2"# 𝛾(𝑧2! )とおくと
• 𝜇! =

#
∑,
𝛾
,1 2"#

𝑁. はクラスタkに割り当てられた実
質的な数と解釈できる．

𝑧2! 𝒙2

• 同様に微分が0となる共分散を求めると
@

1
Σ- =
? 𝛾 𝑧?- 𝒙? − 𝝁- 𝒙? − 𝝁𝑁?/!

%

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

最尤推定 • 両辺𝜋𝑘 をかけると 𝜋𝑘 𝑁 𝒙𝑘 𝜇𝑘 , Σ𝑘 𝑁 ∑ • ∑𝑁 + 𝜆𝜋 = 𝑘 𝐾 𝑛=1 ∑ 𝑛=1 𝛾 𝑧𝑛𝑘 + 𝜆𝜋𝑘 = 0 𝜋 𝑁 𝒙 𝜇 , Σ 𝑛 𝑖 𝑖 𝑖=1 𝑖 • これを計算すると • 𝜆 = −𝑁 • を得る．これを⽤いると • 𝜋𝑘 = 𝑁𝑘 𝑁 • となる． @ ? 𝛾 𝑧?- + 𝜆𝜋- = 0 ?/! . 𝜆𝜋- = −𝑁- . 𝜆 ? 𝜋- = − ? 𝑁-/! -/! 𝜆 = −𝑁 4 . 𝛾 𝑧3% − 𝑁𝜋% = 0 3&' −𝑁𝜋- = −𝑁𝑁𝜋- = 𝑁

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

GMMのためのEMアルゴリズム 1. データ集合𝑋 = {𝒙# , … , 𝒙, }があるとする． 2. パラメタ𝝁! , Σ! , 𝜋! を適当な数値で初期化する． 3. 現在のパラメタで負担率を求める． 4. 3で計算した負担率を⽤い，パラメタ𝝁! , Σ! , 𝜋! を計算する． 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にお けるセントロイドの計算と対応する．