5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

はじパタ党力解説: 第10ç«  クラスタリング

5
Last updated at Posted at 2020-12-13

「はじめおのパタヌン認識」の第10章「クラスタリング」の解説です。
前半(10.3たで)は、郚分空間法ず倉わり難しい数匏も出おこず理解しやすかったです。10.4 確率モデルによるクラスタリングで数匏が出おきお難しくなり、぀いにEMアルゎリズムは理解を攟棄したした:cold_sweat: ずいっおも、理解できなかったずいうより、時間かかるわりに、䜿うかの自信がなかったのでほずんど読たず飛ばしたした。タむトルの「党力」に恥じる行為ですがお蚱しください。
※はじパタ勉匷系は蚘事「文系瀟䌚人がはじパタで機械孊習を数匏含めお理解した奮闘蚘」にたずめたした。

参考リンク

内容

10.1 類䌌床ず非類䌌床

10.1.1 距離の公理

クラスタリングは、デヌタやクラスタ間の類䌌床、たたは非類䌌床に埓っお、䌌たものを集めおクラスタを䜜る方法です。画像䞭の色や明るさなどの類䌌した性質を持぀領域を他領域ず区別するセグメンテヌションやベクトル量子化など広い分野で利甚されおいたす。
デヌタやクラスタ間の類䌌床を枬る基本的な尺床が距離です。ある尺床d(x,y)が距離であるために、次の距離の公理を満たす必芁がありたす。

  1. 非負性: d(x,y) ≧ 0
  2. 反射埋: d(x,y) = 0 ずなるのは x = y であるずきのみに限る
  3. 察称性: d(x,y) = d(y,x)
  4. 䞉角䞍等匏: d(x,z) ≩ d(x,y) + d(y,z)

10.1.2 ミンコフスキヌ距離

距離尺床には、よく䜿われるナヌクリッド距離がありたす。それ以倖にもミンコフスキヌ距離ず呌ばれる䞀般的な距離の定矩から、様々な距離を掟生させるこずができたす。
d次元のデヌタがN個あり、i番目のベクトルを$x_i=(x_{i1},\ldots,x_{id})^T$ずするず、2぀のベクトル$x_i, x_j$間の距離は以䞋の匏です。

d(x_,x_j)=( \sum_{k = 1}^d |x_{ik} - x_{jk}|^a )^{1/b}

このaずbの倀を倉えお様々な距離を生み出したす。
aの倀が倧きければ特城間の差に倧きな重みが加えられたす。
bの倀が倧きければ差分环乗和に察する重みが小さくなりたす。
以䞋がaずbの倀を倉えお掟生した距離です。
※䞀般的にミンコフスキヌ距離はa=bで定矩されおいるこずが倚いようです。たた、a!=bだず距離の公理を満たさなくなるこずもあり、掟生させる堎合には泚意が必芁です。詳しくはコメント欄を参照ください。

No. a b 距離 匏
1 1 1 ミンコフスキヌ距離
(マンハッタン距離/垂街地距離)
$d(x_i, x_j) = \sum_{k = 1}^d |x_{ik} - x_{jk}|$
2 2 2 ナヌクリッド距離 $d(x_i, x_j) = (\sum_{k = 1}^d |x_{ik} - x_{jk}|^2)^{\frac{1}{2}}$
3 2 1 ナヌクリッド距離の2乗 $d(x_i, x_j) = \sum_{k = 1}^d |x_{ik} - x_{jk}|^2$
4 ∞ ∞ チェビシフ距離 $d(x_i, x_j) = \lim_{a \rightarrow \infty}(\sum_{k = 1}^d |x_{ik} - x_{jk}|^a)^{\frac{1}{a}}$
$= \max_k |x_{ik} - x_{jk}|$

ミンコフスキヌ距離の掟生ではないですが、距離の公理を満たすものずしおキャンベラ尺床がありたす。デヌタ正芏化の仕組みが内包されおいたす。原点に近いほど分母が小さくなり、重みづけされたす。

d(x_i, x_j) = \sum_{k = 1}^d \frac{|x_{ik} - x_{jk}|}{|x_{ik}| + |x_{jk}|}

ベクトル間の角床($\cos \theta$)を甚いたコサむン類䌌床がありたす。蚘事「蚀語凊理100本ノック-87:単語の類䌌床」でやりたした。
※方向䜙匊は、コサむン類䌌床のこず。「方向䜙匊」はベクトルだず思っおいたので、混乱したした。2本のベクトルがどれくらい同じ向きを向いおいるのかを衚す指暙で、1に近いほど2本のベクトルは同じ向きに近いです。取り埗る倀は-1から1たでであり、負の倀があるので距離の公理は満たしおいたせん。

d(x_i, x_j) = \frac{x_i x_j}{|x_i| |x_j|} 
= \frac{\sum_{k = 1}^d x_{ik} x_{jk}}{\sqrt{(\sum_{k = 1}^d x_{ik}^2) (\sum_{k = 1}^d x_{jk}^2) }}

距離の皮類はこの蟺が非垞にわかりやすかったです。

10.2 非階局クラスタリング(K-平均法)

非改装クラスタリングの代衚的手法である**K-平均法(K-means法)**です。d次元のN個のデヌタ$D=\{x_1, \ldots, x_N\}, x_i \in \mathbb R^d$をデヌタ間の類䌌性(距離)を尺床にあらかじめ定めたK個のクラスタに分類したす。蚘事「K-means 法を D3.js でビゞュアラむズしおみた」は芋るだけで抂芁が理解できるほど、すばらしい蚘事です。
別蚘事「蚀語凊理100本ノック-97(scikit-learn䜿甚):k-meansクラスタリング」でも䜿いたした。

  • 各クラスタの代衚ベクトルの集合: $M = \{ \mu_i, \ldots, \mu_K \}$
  • k番目の代衚ベクトルが支配するクラスタ: $M(\mu_k)$
  • i番目のデヌタがk番目の代衚ベクトルが支配するクラスタ$M(\mu_k)$ぞの垰属有無を衚す垰属倉数: $q_{ik}$(䞋匏参照)
{q_{ik} = \left\{
\begin{array}{ll}
1 & \boldsymbol{x_i} \in M(\boldsymbol{\mu_k})\\
0 & otherwize
\end{array}
\right.}

K平均法の評䟡関数を以䞋に蚭定。$q_{ik}$が1の堎合に代衚ベクトルずの距離を最小化させたす。

J(q_{ik}, \mu_k)= \sum_{i=1}^{N}\sum_{k=1}^{K}q_{ik}||x_i-\mu_k||^2

$\mu_{ik}$を偏埮分により最適化したす。

\frac{\partial J(q_{ik}, \mu_k)}{\partial \mu_k}=2\sum_{i=1}^Nq{ik}(x_i-\mu_k)=0\\
⇒\mu_k=\frac{\sum_{i=1}^Nq_{ik} x_i}{\sum_{i=1}^N q_{ik}
}

最埌の圢を芋るず、各クラスタの代衚ベクトルは、そのクラスタに垰属するデヌタの平均ベクトルになっおいるこずがわかりたす。$\mu_{ik}$を最適化したしたが、$q_{ik}$ず同時に最適化が難しいので、次の手順で逐次的に最適化を実斜したす。

0. 初期化

N個のデヌタをランダムにK個のクラスタに振り分け、それぞれのクラスタの平均ベクトルを求め、$\mu_k(k=1, \ldots, K)$ずしたす。

1. q最適化

$\mu_k$を固定し、垰属倉数$q_{ik}$を以䞋に埓っお決定。

q_{ik} = \left\{
\begin{array}{ll}
1 & k = argmin_j ||\boldsymbol{x_i}-\boldsymbol{\mu_j}||^2\\
0 & otherwize
\end{array}
\right.

K-平均法の収束先は初期倀に䟝存するため、最適解に近い解を埗るためには䜕回か初期倀を倉えお実行する必芁がありたす。各代衚ベクトルが支配する領域は、代衚ベクトル間のボロノむ境界で決たりたす。
代衚ベクトルは平均ベクトルなので、デヌタベクトルず䞀般に䞀臎をしたせん。代衚ベクトルをデヌタベクトルに限定した方法を**K-メドむド法(K-medoids法)**ず蚀いたす。代衚ベクトルに平均ベクトルを䜿うため、K-平均法はデヌタ間の距離を定矩する必芁がありたす。䞀方で、代衚ベクトルにデヌタベクトルを䜿うK-メドむド法はデヌタ間の非類䌌床行列(距離の行列でもOK)が定矩できれば蚈算できたす。
メドむドは、クラスタ内のデヌタ点のうち、その点以倖のクラスタ内の他の点ずの比類䌌床(距離でもOK)の総和が最初うになる点です。以䞋を満たす$x_i$が代衚ベクトル$\mu_k$の領域のメドむドです。

i = \arg \min_{x_i \in M(\mu_k)}\sum_{y \in \{M(\mu_k) - x_i\}} d(x_j, y)

K-平均法が距離の2乗で誀差が評䟡されるのに察しお、K-メドむド法は1乗なので、倖れ倀の圱響が少ないです。

2. Όの最適化

$q_{ik}$を固定し、セントロむド$\mu_k$を決める(䞊で玹介した偏埮分の匏)。

3. 繰り返し

「1. q最適化」ず「2. Όの最適化」を収束するたで繰り返したす。

10.3 階局クラスタリング(融合法)

クラスタリングされおいないデヌタから、類䌌床が高い順に融合しお埐々に倧きなクラスタを䜜り、最終的に1぀のクラスタに統合しおいく方法を階局的クラスタリングたたは融合法ず蚀いたす。デヌタ・クラスタを融合する過皋を**暹状図(dendrogram)**ず呌ばれる圢で衚珟できたす。
以䞋が融合法の手順です。

  1. n = Nずしたす
  2. n × n の距離行列を䜜りたす
  3. 最も距離が近い2぀のデヌタやクラスタをたずめお、䞀぀のクラスタにしたす
  4. n = n - 1ずしたす
  5. n > 1 であれば2ぞ戻りたす。n = 1 であれば終了したす。

類䌌床を枬る尺床は、ミンコフスキヌ距離、キャンベラ尺床などを䜿いたす。クラスタ間の類䌌床は、以䞋のような様々なものがありたす。

参考: 階局的クラスタリング入門の入門

10.3.1 単連結法

2぀のクラスタ間で最も類䌌床の高いデヌタ間の距離をクラスタ間の距離にする方法を**単連結法(single linkage method)**ず蚀いたす(最短距離法ずも呌ぶようです)。
以䞋が単連結法によるクラスタリングの特城です。

  • クラスタに1぀デヌタが远加されるず、他クラスタずの距離は小さくなるか、たたは倉化しない(最短距離なので圓然)。
  • 倧きなクラスタができる傟向がありたす。
  • あるクラスタから同じ距離に2぀のクラスタがある堎合、どちらを遞んでも結果は同じ(途䞭経過は少し倉わるが、2぀が最短距離なので次の融合で2぀目のクラスタが察象ずなrimasu
  • )。
  • 近いデヌタが別なクラスタに属する連鎖効果が衚れる堎合がありたす(近いデヌタから融合しおいくので蛇のように長现くなっおいくむメヌゞ)

10.3.2 超距離

2぀のデヌタ$x_i, x_j$が融合する盎前のクラスタ間の距離を**超距離(ultrametric)**ず蚀い、$\widetilde{d}(x_i,x_j)$で衚したす。
※「超距離」は、超距離法のようなものがあるのかず混乱したしたが、距離の皮類・呌び方に぀いおの解説の章です。わかりにくい・・・

10.3.3 完党連結法

単連結法が最近傍距離を基準にしたのに察しお、完党連結法(complete linkage method)は最遠隣距離をクラスタ間の距離にする方法です。以䞋が特城です。

  • クラスタに1぀デヌタが远加されず、他クラスタずの距離は倧きくなる(単連結法の逆)か、たたは倉換しない。
  • 倧きなクラスタになりにくく、同じようなサむズのクラスタができる傟向。
  • 連鎖効果は珟れない(遠いデヌタを遞んでいくから)

10.3.4 矀平均法

矀平均法(group average method)は2぀のクラスタ内の党おのデヌタ察間の距離の平均でクラスタ間の距離を決めたす。クラスタ内デヌタの平均ベクトル間ではないのが泚意点です。

10.3.5 りォヌド法

りォヌド法(Ward method)は、クラスタAずBの距離を、それらを融合したずきのクラスタ内倉動の増分で定矩し、距離の小さなクラスタから融合したす。クラスタ内倉動の増分は以䞋の匏で衚したす。

\begin{align}
d(A, B) & = \sum_{x \in A, B} d(x, \mu_{AB})^2 - (\sum_{x \in A} d(x, \mu_A)^2 + \sum_{x \in B} d(x, \mu_B)^2) \\
& = S_{AB} - (S_A + S_B) 
\end{align}

䞊蚘の匏の補足です。぀たり、平均ずの距離の差(各クラスタ内のばら぀きを考慮)をもっお、融合の基準ずしたす。

匏 説明
$d(x,y)$ ナヌクリッド距離
$\mu_{AB}$ クラスタAずBを融合したクラスタの平均ベクトル
$\mu_A$ クラスタAの平均ベクトル
$\mu_B$ クラスタBの平均ベクトル
S 倉動、぀たり平均からの距離(偏差)の2乗

りォヌド法は階局法の䞭でもっずも粟床が高いらしいです。
これ以倖に重心法やメディアン法がありたす。

10.4 確率モデルによるクラスタリング

K-平均法や融合法によるクラスタリングは、1぀のデヌタは1぀のクラスタにのみ分類されるため、ハヌドクラスタリングず呌ばれたす。ハヌドクラスタリングに察しお、確率モデルを䜿い所属クラスタを確率的に決める゜フトクラスタリングがありたす。倚くの確率モデルは単峰性の確率分垃しか衚珟できないので、耇数の確率モデルの重み付け線圢和で党䜓の確率分垃をモデル化したす。クラスタ数をK、k番目のクラスタの確率モデルを$p_k(x)$ずし、党䜓の確率分垃を$p(x) = \sum_{k = 1}^K \pi_k p_k(x)$で衚したす。
$\pi_k$がk番目の確率モデルの重み(混合比)です。このような確率モデルを混合分垃モデルず蚀いたす。確率モデルに正芏分垃を䜿う堎合、**混合正芏分垃モデル(混合ガりス分垃モデル)**ず呌ばれたす。混合正芏分垃モデルを䜿う堎合、最初にクラスタ数Kを決める必芁がありたす。
※「はじめおのパタヌン認識茪読䌚 10章埌半」(Slideshare)が非垞に参考になり、芋ながら理解しおいきたした。

10.4.1 混合正芏分垃モデル

k番目のクラスタを衚すd次元正芏分垃関数を以䞋で評䟡したす。芁は倚倉量正芏分垃モデルです。参考に1倉数の正芏分垃を2行目に蚘茉。
※N は「正芏分垃」を衚す英語 "normal distribution" の頭文字から取られおいる

\begin{eqnarray}
\mathcal{N}(x|\mu_k, \Sigma_k) & = & 
\frac{1}{(2\pi)^{1/d} |\Sigma|^{1/2}} \exp (- \frac{1}{2} (x - \mu_k)^T \Sigma_k^{-1} (x - \mu_k) )\\
\mathcal{N}(x|\mu, \sigma^2) & = & 
\frac{1}{(2\pi)^{1/2} |\sigma|^{1/2}} \exp (- \frac{1}{2} (x - \mu)^2 |\sigma|^{1/2} )
\ \ *1倉数正芏分垃\\
\end{eqnarray}

党䜓の分垃は、線圢和なので、以䞋で衚したす。

p(x) = \sum_{k = 1}^K \pi_k \mathcal{N}(x|\mu_k, \Sigma), \;\; 
0 \leq \pi_k \leq 1, \;\; 
\sum_{k = 1}^K \pi_k = 1

$\pi_k$を混合比ず呌び、混合正芏分垃モデルのパラメヌタは以䞋で衚したす。

\pi = (\pi_1, \ldots , \pi_K), \;
\mu = (\mu_1, \ldots , \mu_K), \;
\Sigma = (\Sigma_1, \ldots , \Sigma)

$\mu_k$はd次元ベクトル、$\Sigma_k$はd×d察角行列で (d+1)d/2個の異なる芁玠を持぀ので、党䜓で K(混合比)+dK(平均ベクトル)+(d+1)dK/2(共分散行列の察角分)個のパラメヌタを求める必芁がありたす。
※混合ガりスモデル (Gaussian Mixture Model, GMM) が党般的に参考になりたす。

10.4.2 隠れ倉数ず事埌確率

混合正芏分垃モデルでは、デヌタからK組の混合比、平均ベクトル、共分散行列を掚定するために、1぀のデヌタがどのクラスタに属するかを掚定する必芁がありたす。1぀のデヌタがK個のクラスタのどこに属するかを衚珟するK次元倉数を䜿いたす。これはOne-Hot Encoding衚珟で属するクラスタ$z_k$が1ずなりたす。

z = (z_1, \ldots , z_K)^T, \;\; 
\sum_{k = 1}^K z_k = 1, \;\;
z = (0, \ldots , 0, 1, 0, \ldots , 0)^T

この倉数は、倉数xが所属する隠れたクラスタを指定しおいるため、隠れ倉数ず呌ばれたす。もずもず提䟛されたデヌタになく、正解ラベルを自分で蚭定する倉数なので、隠れ、ず呌ぶむメヌゞでしょうか。
倉数xず隠れ倉数zの同時分垃はベむズの定理を元いお以䞋に分解できたす。

p(x, z) = p(z)p(x \mid z)

この䞭で$p(z_k=1)=\pi_k$なので、**隠れ倉数の分垃p(z)**は以䞋のように衚珟できたす。
※以䞋の匏の$z_k$郚分は$z_k$乗ずいう意味ではないです。

p(z) = \prod_{k=1}^K \pi_k^{z_k}\\
\because \pi_k^{z_k=0}=1

䞊蚘は理解に時間をかけたので、少し詳しく(正しい理解か少し自信なし)。

匏 説明
$K=2$ クラスタ数が2
$\pi=(\pi_1,\pi_2)=(0.2, 0.8)$ クラスタ1ぞの所属確率が0.2
クラスタ2ぞの所属確率が0.8
$z=(1,0)$ クラスタ1に属しおいる堎合の隠れ倉数
最終的に事埌確率で最尀掚定する
$p(z_1=1)=\pi_1^{z_1} \times \pi_2^{z_2}=0.2 \times 1$ クラスタ1に所属する確率が0.2

芳枬デヌタの隠れ倉数による条件付き分垃は以䞋の匏。

p(x | z) = \prod_{k = 1}^K (\mathcal{N}(x | \mu_k, \Sigma_k))^{z_k}\\
\because p(x | z_k = 1) = \mathcal{N}(x | \mu_k, \Sigma_k)

p(x)は同時分垃p(x, z)をすべおのzに぀いおの総和ずなるので以䞋の匏。

\begin{eqnarray}
p(x)& = & \sum_{k = 1}^K p(z)\\
& = & \sum_{k = 1}^K \prod_{k = 1}^K \pi_k^{z_k} \prod_{k = 1}^K (\mathcal{N}(x | \mu_k, \Sigma_k))^{z_k}\\
& = & \sum_{k = 1}^K \pi_k \mathcal{N}(x|\mu_k , \Sigma_k)\\
\end{eqnarray}

これで、ようやく求めたかった隠れ倉数の事埌確率$\gamma(z_k)$が蚈算できたす。

\begin{eqnarray}
\gamma(z_k) = p(z_k = 1 | x)& = & \frac{p(z_k = 1) p(x | z_k = 1)}{p(x)}\\
& = & \frac{p(z_k = 1) p(x | z_k = 1)}{\sum_{j = 1}^K p(z_j = 1)p(x | z_j = 1)}\\
& = & \frac{\pi_k \mathcal{N}(x | \mu_k, \Sigma_k)}{\sum_{j = 1}^K \pi_j \mathcal{N}(x | \mu_j, \Sigma_j)}\\
\end{eqnarray}

10.4.3 完党デヌタの察数尀床

芳枬デヌタず隠れ倉数を䜵せお完党デヌタずし、完党デヌタの尀床を最倧にするパラメヌタを求めたす。ただし、最尀掚定倀を盎接求めるこずはできたせん。

10.4.4 Q関数

完党デヌタの察数尀床の隠れ倉数に関する期埅倀をずるず、隠れ倉数の事埌確率になりたす。隠れ倉数の期埅倀を事埌確率で眮き換えた関数をQ関数ず呌びたす。

10.4.5 EMアルゎリズム, 10.4.6 Mステップの導出, 10.4.7 EMアルゎリズムの性質

「党力」ず蚀いながら、省略したす。なぜなら、理解に時間がかかりそうな反面、今埌䜿うのかず感じる郚分もあるため、飛ばしたす。
必芁ずなったらこのあたりのペヌゞを芋お勉匷したいず思いたす。

「はじパタ」勉匷系蚘事リンク

ç«  項目 時間(h) 難易床 孊んだこず
1 はじめに 8.9 :star: 特城の型, 特城空間, 次元の呪い
2 識別芏則ず孊習法の抂芁 12 :star: ホヌルドアりト法,亀差確認法 ,䞀぀抜き法 ,ブヌトストラップ法 ,バむアス・分散トレヌドオフ, 過孊習
3 ベむズの識別芏則 14.8 :star: ベむズ識別芏則, ROC曲線
4 確率モデルず識別関数 18 :star::star: 平均ベクトル, 共分散行列, 暙準化, 無盞関化, 癜色化, 正芏分垃, 最尀掚定
5 k最近傍法(kNN法) 8 :star::star: 最近傍法, ボロノむ境界, kNN
6 線圢識別関数(前半) 30.4 :star::star: 正芏方皋匏
6 線圢識別関数(埌半) 前半に時間は含む :star::star::star: フィッシャヌの線圢刀別関数, 刀別分析法, ロゞスティック回垰
7 パヌセプトロン型孊習芏則 13.5 :star::star: 倚局パヌセプトロン, 誀差逆䌝播法, シグモむド関数
8 サポヌトベクトルマシン 14.7 :star::star: カヌネルトリック, Μ-SVM
9 郚分空間法 15.4 :star::star::star: 䞻成分分析, 特異倀分解, CLAFIC法, カヌネル䞻成分分析, カヌネル郚分空間法
10 クラスタリング 8.4 :star::star: 距離の公理, ミンコフスキヌ距離, K-平均法, 融合法, 混合正芏分垃モデル
11 識別機の組み合わせによる性胜匷化 11.6 :star::star: ノヌフリヌランチ定理, 決定朚, バギング, アダブヌスト, ランダムフォレスト
5
3
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?