スペクトルクラスタリング

同義語:スペクトラルクラスタリングspectral clustering

概要

スペクトルクラスタリング(spectral clustering)とは、データの点を頂点とする非負の重みのグラフの Laplacian の最小 $k$ 個の固有ベクトルを列に並べ、その行を $k$ 平均法で分ける方法である。グラフがちょうど $k$ 個の連結成分を持てば行は直交する $k$ 点に潰れ、分割は連結成分に一致する。一般のグラフでは、固有値問題は RatioCut や Ncut という切断の最小化を、列の直交性だけに緩めた問題にあたり、最小 $k$ 個の固有値の和が切断の下界を与える。緩和なので最良の分割を返すとは限らないが、座標の近さでなくつながりで分けるので凸でない塊も扱える。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Laplacian行列, Rayleigh商, 固有値

スペクトルクラスタリング(spectral clustering)は、データの点を頂点とする重み付きグラフを作り、その Laplacian の小さい固有値に対する固有ベクトルで点を $\mathbb{R}^k$ へ写してから、k平均法で $k$ 組に分ける方法である。座標の近さではなく「辺のつながり」で分けるので、同心円のように凸でない塊も分けられる。その根拠は 2 つある。グラフが $k$ 個の連結成分に分かれていれば写した先が厳密に $k$ 点へ潰れること、一般のグラフでは固有値問題が切断の最小化を緩和した問題になっていることである。ここでは両方を証明し、成分がつながっている場合の誤差も評価する。緩和なので最良の分割を返す保証はなく、その反例も示す。

定義と使える条件

類似度グラフの行列

頂点集合を $V=\{1,\dots,n\}$ とし、$W=(w_{il})$ を対称で $w_{il}\ge0$、$w_{ii}=0$ の行列とする。$w_{il}>0$ のとき $i,l$ を辺で結ぶ。$d_i:=\sum_l w_{il}$ を次数、$D:=\mathrm{diag}(d_1,\dots,d_n)$ として
$$L:=D-W$$
を Laplacian という。すべての $d_i>0$ のとき
$$L_{\mathrm{sym}}:=D^{-1/2}LD^{-1/2},\qquad L_{\mathrm{rw}}:=D^{-1}L$$
を 正規化 Laplacian という。$L_{\mathrm{sym}}$ は対称で、$L_{\mathrm{rw}}$ は $L_{\mathrm{sym}}$ と相似である。固有値を小さい順に、$L$ は $\mu_1\le\dots\le\mu_n$、$L_{\mathrm{sym}}$ は $\nu_1\le\dots\le\nu_n$ と書く。

類似度グラフの作り方には、距離が $\varepsilon$ 以下の点を結ぶもの、近い順に $m$ 個を結ぶもの(どちらかが選べば辺を置いて対称にする)、$w_{il}=\exp(-\|x_i-x_l\|^2/(2s^2))$ とするものがあるvL07。以下の結果はどれにも同じように当てはまり、使うのは $W$ の対称性と非負性だけである。

切断の目的関数

$A,B\subset V$ に対し $W(A,B):=\sum_{i\in A,\,l\in B}w_{il}$、$\mathrm{vol}\,A:=\sum_{i\in A}d_i$ とおく。$V$ の空でない部分集合への分割 $A_1,\dots,A_k$ に対し
$$\mathrm{RatioCut}(A_1,\dots,A_k):=\sum_{j=1}^k\frac{W(A_j,A_j^c)}{|A_j|},\qquad \mathrm{Ncut}(A_1,\dots,A_k):=\sum_{j=1}^k\frac{W(A_j,A_j^c)}{\mathrm{vol}\,A_j}$$
と定める($\mathrm{Ncut}$ はすべての $\mathrm{vol}\,A_j>0$ のとき)。分子が切る辺の重み、分母が組の大きさで、小さい組だけを切り離す分割に罰を与える。分子に $\frac12$ を付ける流儀もあり、その場合は値が半分になる。

k 平均の目的関数

$y_1,\dots,y_n\in\mathbb{R}^k$ と $V$ の分割 $C_1,\dots,C_k$(空の組も許す)に対し、$m_j$ を $C_j$ の点の平均として
$$G(C_1,\dots,C_k):=\sum_{j=1}^k\sum_{i\in C_j}\|y_i-m_j\|^2$$
とする。平均は各組で 2 乗距離の和を最小にする点なので、$m_j$ を別の点に替えても和は $G$ より小さくならない。$G$ の厳密な最小化は NP 困難で、実用の Lloyd 法は値を単調に下げるが、局所最小でもない点で止まりうるSSBD14。

公式の表

$H$ は $j$ 列目が $h_j:=\mathbf{1}_{A_j}/\sqrt{|A_j|}$ の行列、$T$ は $j$ 列目が $t_j:=D^{1/2}\mathbf{1}_{A_j}/\sqrt{\mathrm{vol}\,A_j}$ の行列である。

量式根拠条件
2 次形式$x^{\top}Lx=\frac12\sum_{i,l}w_{il}(x_i-x_l)^2$展開$W$ が対称
核の次元$\dim\ker L=$ 連結成分の個数thm-spc-ideal$w_{il}\ge0$
行の位置$i\in A_j$ の行は $q_j/\sqrt{\lvert A_j\rvert}$thm-spc-ideal成分がちょうど $k$ 個
RatioCut と跡$\mathrm{RatioCut}=\mathrm{tr}(H^{\top}LH)$thm-spc-relax$A_j$ が分割
Ncut と跡$\mathrm{Ncut}=\mathrm{tr}(T^{\top}L_{\mathrm{sym}}T)$thm-spc-relax$d_i>0$
下界$\mathrm{RatioCut}\ge\mu_1+\dots+\mu_k$、$\mathrm{Ncut}\ge\nu_1+\dots+\nu_k$thm-spc-relax$w_{il}\ge0$
行の誤差$\Vert U-HQ\Vert_F^2\le2\rho/\gamma$thm-spc-perturb各 $A_j$ が連結
誤分類の個数高々 $16\rho\,n_{\max}/\gamma$thm-spc-perturb$16\rho\,n_{\max}/\gamma< n_{\min}$
2 分割の比$\nu_2/2\le h\le\sqrt{2\nu_2}$prop-spc-cheeger連結、$d_i>0$

主定理と証明

まず切断がなければ固有ベクトルの行が組をそのまま表すことを示す。

連結成分と固有ベクトルの行

グラフがちょうど $k$ 個の連結成分 $A_1,\dots,A_k$ を持つとする。$\ker L$ は $k$ 次元で、その正規直交基底を列とする $n\times k$ 行列 $U$ を任意に取り、$y_i$ を $U$ の第 $i$ 行とする。

  1. ある $k$ 次直交行列 $Q$ があり $U=HQ$ である。$Q$ の第 $j$ 行を $q_j$ とすれば、$i\in A_j$ のとき $y_i=q_j/\sqrt{|A_j|}$ となる。特に異なる成分の行は直交する。
  2. $y_1,\dots,y_n$ についての $G$ の最小値は $0$ で、最小を与える分割は(組の番号を除いて)$A_1,\dots,A_k$ だけである。
  3. すべての $d_i>0$ とする。$\ker L_{\mathrm{rw}}=\ker L$ であり、$\ker L_{\mathrm{sym}}$ の正規直交基底を列とする行列の第 $i$ 行($i\in A_j$)は $\sqrt{d_i/\mathrm{vol}\,A_j}\,q_j$($q_j$ は正規直交)の形で、各行を長さ $1$ に正規化すると $q_j$ になる。
成分の上で定数になることから

$x^{\top}Lx=\frac12\sum_{i,l}w_{il}(x_i-x_l)^2$ は $w_{il}\ge0$ より非負である。$L$ は半正定値なので $Lx=0\iff x^{\top}Lx=0$ であり、これは辺で結ばれた頂点で $x$ の値が等しいこと、つまり $x$ が各連結成分で定数であることと同値である。よって $\ker L$ は $h_1,\dots,h_k$ を正規直交基底に持つ。
(1) $U$ の列も同じ空間の正規直交基底だから $U=HQ$ と書け、$Q=H^{\top}U$ は直交行列である。$H$ の第 $i$ 行($i\in A_j$)は $e_j^{\top}/\sqrt{|A_j|}$ なので主張を得る。
(2) $q_j$ は零でなく互いに直交するので、$y_i=y_{i'}$ は $i,i'$ が同じ成分にあることと同値である。成分の分割なら $G=0$ である。逆に $G=0$ なら各組の点は 1 点に集まるから各組は 1 つの成分に含まれる。$k$ 個の組で $k$ 個の成分を覆うので、各組はちょうど 1 つの成分に一致する。
(3) $L_{\mathrm{rw}}x=0\iff Lx=0$ は $D$ が可逆なことから従う。$L_{\mathrm{sym}}t=0\iff L(D^{-1/2}t)=0$ より $t_1,\dots,t_k$ が $\ker L_{\mathrm{sym}}$ の正規直交基底で、(1) と同じ議論で基底は $TQ$ と書ける。$T$ の第 $i$ 行は $\sqrt{d_i/\mathrm{vol}\,A_j}\,e_j^{\top}$ である。$\square$

次に、成分がつながっているときに固有値問題が何を解いているかを示す。

切断の最小化の緩和

$S$ を $n$ 次実対称行列、固有値を $\lambda_1\le\dots\le\lambda_n$ とする。$H'^{\top}H'=I_k$ となる任意の $n\times k$ 実行列 $H'$ に対し
$$\mathrm{tr}(H'^{\top}SH')\ge\lambda_1+\dots+\lambda_k$$
であり、最小 $k$ 個の固有値に対する正規直交な固有ベクトルを列とする $H'$ で等号が成り立つ。$V$ の分割 $A_1,\dots,A_k$ に対しては $H^{\top}H=I_k$、$\mathrm{tr}(H^{\top}LH)=\mathrm{RatioCut}(A_1,\dots,A_k)$ であり、$d_i>0$ なら $T^{\top}T=I_k$、$\mathrm{tr}(T^{\top}L_{\mathrm{sym}}T)=\mathrm{Ncut}(A_1,\dots,A_k)$ である。したがって
$$\mathrm{RatioCut}(A_1,\dots,A_k)\ge\mu_1+\dots+\mu_k,\qquad \mathrm{Ncut}(A_1,\dots,A_k)\ge\nu_1+\dots+\nu_k.$$

跡の下界と 2 次形式の計算

$S$ の正規直交な固有ベクトルを $u_1,\dots,u_n$ とし、$a_i:=\|H'^{\top}u_i\|^2$ とおく。$H'H'^{\top}$ は直交射影だから $0\le a_i\le1$ で、$\sum_ia_i=\mathrm{tr}(H'^{\top}H')=k$ である。$\mathrm{tr}(H'^{\top}SH')=\sum_i\lambda_ia_i$ だから
$$\sum_i\lambda_ia_i-\sum_{i\le k}\lambda_i=\sum_{i\le k}(\lambda_k-\lambda_i)(1-a_i)+\sum_{i>k}(\lambda_i-\lambda_k)a_i\ge0$$
となる。等式は $\sum_i a_i=k$ を使って右辺を展開すれば分かる。
分割の列は台が交わらないので $h_j$ は正規直交である。$x^{\top}Lx$ の式に $h_j$ を入れると、値が変わるのは $A_j$ と $A_j^c$ を結ぶ対だけで、順序対が 2 通りあるから
$$h_j^{\top}Lh_j=\frac12\cdot2\sum_{i\in A_j,\,l\notin A_j}w_{il}\frac{1}{|A_j|}=\frac{W(A_j,A_j^c)}{|A_j|}$$
である。$j$ で足して RatioCut を得る。$t_j^{\top}t_j=\mathbf{1}_{A_j}^{\top}D\mathbf{1}_{A_j}/\mathrm{vol}\,A_j=1$ と $t_j^{\top}L_{\mathrm{sym}}t_j=\mathbf{1}_{A_j}^{\top}L\mathbf{1}_{A_j}/\mathrm{vol}\,A_j=W(A_j,A_j^c)/\mathrm{vol}\,A_j$ から Ncut の式も得る。$\square$

列を分割の形に限ると NP 困難な最小化になり、その制約を $H'^{\top}H'=I_k$ だけに緩めると固有値問題になる。$k$ 平均は、緩めた解から分割へ戻す丸めの段階にあたる。この視点は Hagen–KahngHK92 と Shi–MalikSM00 にさかのぼり、見通しよくまとめた解説に vL07 がある。$k=2$ では $\mu_1=0$ より $\mathrm{RatioCut}\ge\mu_2$ となり、Cheegerの不等式(グラフ) の補題「1 つの分け方についての評価」と同じ内容である。
緩和だけでは丸めの質は分からない。次の定理は、切る辺が内部のつながりに比べて少なければ、丸めでほぼ正しい分割に戻ることを示す。

切断が小さいときの誤差の評価

$A_1,\dots,A_k$ を $V$ の分割とし、各 $A_j$ の誘導部分グラフは連結で、$|A_j|\ge2$ の組が少なくとも 1 つあるとする。組をまたぐ辺を除いたグラフの Laplacian を $L_0$、その最小の正の固有値を $\gamma$、$\rho:=\mathrm{RatioCut}(A_1,\dots,A_k)$、$n_{\max}:=\max_j|A_j|$、$n_{\min}:=\min_j|A_j|$ とする。$L$ の最小 $k$ 個の固有値に対する正規直交な固有ベクトルを列とする $U$ を任意に取る。

  1. ある $k$ 次直交行列 $Q$ があり $\|U-HQ\|_F^2\le2\rho/\gamma$ である。
  2. $16\rho\,n_{\max}/\gamma< n_{\min}$ なら、$U$ の行についての $G$ の任意の最小解は、組の番号を付け替えると $A_1,\dots,A_k$ と高々 $16\rho\,n_{\max}/\gamma$ 個の頂点でしか違わない。
射影の誤差から頂点の数え上げへ

(1) $L-L_0$ はまたぐ辺だけのグラフの Laplacian なので半正定値である。thm-spc-relax より
$$\mathrm{tr}(U^{\top}L_0U)\le\mathrm{tr}(U^{\top}LU)=\mu_1+\dots+\mu_k\le\rho.$$
各 $A_j$ が連結だから $\ker L_0$ は $H$ の列で張られ、$P:=HH^{\top}$ はその上への直交射影である。よって $x^{\top}L_0x\ge\gamma\|(I-P)x\|^2$ で、$U$ の列について足すと $\|(I-P)U\|_F^2\le\rho/\gamma$ となる。
$H^{\top}U=X\Sigma Y^{\top}$ を特異値分解し、特異値を $\sigma_i\in[0,1]$、$Q:=XY^{\top}$ とおくと
$$\|U-HQ\|_F^2=2k-2\,\mathrm{tr}(Q^{\top}H^{\top}U)=2\sum_i(1-\sigma_i)\le2\sum_i(1-\sigma_i^2)=2\|(I-P)U\|_F^2\le\frac{2\rho}{\gamma}$$
である。最後の等号は $\|PU\|_F^2=\|H^{\top}U\|_F^2=\sum_i\sigma_i^2$ による。
(2) $\tau:=2\rho/\gamma$ とし、$y_i$ を $U$ の第 $i$ 行、$z_i$ を $HQ$ の第 $i$ 行とする。$i\in A_j$ なら $z_i=q_j/\sqrt{|A_j|}$ である。平均は 2 乗距離の和を最小にするので、分割 $A_1,\dots,A_k$ の $G$ の値は、中心を $z_i$ の値に置いた和 $\sum_i\|y_i-z_i\|^2\le\tau$ 以下である。$G$ の最小解を $C_1,\dots,C_k$、中心を $m_\ell$、$i$ の属する組の番号を $c(i)$ とすると、最小性から $\sum_i\|y_i-m_{c(i)}\|^2\le\tau$ で、
$$\sum_i\|z_i-m_{c(i)}\|^2\le2\sum_i\|z_i-y_i\|^2+2\sum_i\|y_i-m_{c(i)}\|^2\le4\tau$$
となる。異なる $A_j,A_l$ の $z$ は $q_j$ の直交性より距離の 2 乗が $1/|A_j|+1/|A_l|\ge2/n_{\max}=:\delta^2$ だけ離れている。
$\|z_i-m_{c(i)}\|\ge\delta/2$ となる頂点を「悪い」と呼ぶ。その 2 乗は $1/(2n_{\max})$ 以上だから、悪い頂点は高々 $8\tau n_{\max}=16\rho\,n_{\max}/\gamma$ 個で、仮定よりこれは $n_{\min}$ 未満である。よって各 $A_j$ に悪くない頂点がある。異なる $A_j,A_l$ の悪くない頂点が同じ組に入ると、三角不等式で $z$ の距離が $\delta$ 未満になり矛盾する。したがって $A_j$ の悪くない頂点の入る組は $j$ ごとに異なり、組は $k$ 個なので全単射が定まる。悪くない頂点はすべて対応する組に入るから、$A_j$ と組の違いは悪い頂点だけである。$\square$

上の定理は固有値の間隔を仮定しない。$U$ の取り方に任意性があっても成り立つのは、結論が $Q$ による回転の分だけ自由だからである。$\gamma$ が内部のつながり、$\rho$ が切る量を表し、比 $\rho/\gamma$ が丸めの難しさを測る。定数 $16$ は証明から出た値で、最良ではない。
2 分割については、正規化 Laplacian の $\nu_2$ が切断の比の最小値を両側から抑える。単純グラフで頂点数を分母にした形は Cheegerの不等式(グラフ) の定理「グラフの Cheeger の不等式」にあり、次は重み付きで体積を分母にした形である。

体積で測る 2 分割の比の評価

グラフが連結で頂点数が 2 以上とする。$h:=\min\{W(A,A^c)/\mathrm{vol}\,A:\emptyset\ne A\subset V,\ \mathrm{vol}\,A\le\frac12\mathrm{vol}\,V\}$ とおくと
$$\frac{\nu_2}{2}\le h\le\sqrt{2\nu_2}.$$

下側は緩和、上側は水準集合

下側:$A$ が $h$ を与えるとき、thm-spc-relax と $\nu_1=0$ より $\nu_2\le\mathrm{Ncut}(A,A^c)\le2W(A,A^c)/\mathrm{vol}\,A=2h$ である。
上側は固有ベクトルの水準集合を調べる。

上側の評価の計算

$\nu_2$ の固有ベクトル $t$ から $f:=D^{-1/2}t$ を作ると $Lf=\nu_2Df$、$\sum_id_if_i=0$ である。符号を選んで $\mathrm{vol}\{f>0\}\le\frac12\mathrm{vol}\,V$ とし、$g:=\max(f,0)$ とおく。$g_v>0$ のとき $g_u\ge f_u$ より $(Lg)_v\le(Lf)_v=\nu_2d_vg_v$ なので、$g^{\top}Lg\le\nu_2g^{\top}Dg$ である。辺(順序なしの対)についての和で、Cauchy–Schwarz と $(a+b)^2\le2(a^2+b^2)$ から $\sum_ew_e|g_u^2-g_v^2|\le\sqrt{\sum_ew_e(g_u-g_v)^2}\sqrt{\sum_ew_e(g_u+g_v)^2}\le\sqrt{\nu_2g^{\top}Dg}\sqrt{2g^{\top}Dg}=\sqrt{2\nu_2}\,g^{\top}Dg$ を得る。$S_s:=\{v:g_v^2>s\}$($s>0$)とすると $\int_0^\infty W(S_s,S_s^c)\,ds=\sum_ew_e|g_u^2-g_v^2|$、$\int_0^\infty\mathrm{vol}\,S_s\,ds=g^{\top}Dg$ だから、ある $s$ で $S_s\ne\emptyset$ かつ $W(S_s,S_s^c)\le\sqrt{2\nu_2}\,\mathrm{vol}\,S_s$ となる。$S_s\subset\{f>0\}$ より $h\le\sqrt{2\nu_2}$ である。$\square$

上側の証明は、$f$ の値で頂点を並べて切り口を掃き出せば比 $\sqrt{2\nu_2}$ 以下の 2 分割が見つかることを示している。

計算の手順

入力は点 $x_1,\dots,x_n$ と組の数 $k$ である。

  1. 類似度を決めて $W$ を作る。局所的なつながりだけを残す(近傍で切る、または Gauss 類似度の幅 $s$ を小さめにする)。
  2. $L$ を作る。次数のばらつきが大きいときは $L_{\mathrm{rw}}$ か $L_{\mathrm{sym}}$ を使う。
  3. 最小 $k$ 個の固有値に対する固有ベクトルを求め、列に並べて $U$ とする。$L$ と $L_{\mathrm{sym}}$ では正規直交に取り、$L_{\mathrm{rw}}$ では $Lu=\mu Du$ の解を $u^{\top}Dv$ について正規直交に取る。$W$ が疎なら Lanczos 法などで少数の固有ベクトルだけを求めればよい。
  4. $L_{\mathrm{sym}}$ を使ったときは各行を長さ $1$ に正規化する(Ng–Jordan–Weiss の方法)。
  5. $U$ の行 $y_1,\dots,y_n\in\mathbb{R}^k$ を $k$ 平均法で $k$ 組に分け、組をそのまま頂点の分割として返す。
  6. $k$ が未知なら $\mu_1,\mu_2,\dots$ を見て、$\mu_{k+1}-\mu_k$ が目立って開くところを候補にする。これは目安であり、組がはっきりしないデータでは開きが見えないvL07。
    $k=2$ なら手順 5 の代わりに $\mu_2$ の固有ベクトルの符号で分けてもよい。基本の算法は教科書にも同じ形で載っているSSBD14HTF09。
    図: 同心円の 2 組の 300 点を、生の座標で k 平均にかけたもの、10 近傍グラフの Laplacian の小さい固有値、最小 2 個の固有ベクトルの行とその k 平均。内外をまたぐ辺がないので固有値 0 が 2 個あり、行は 2 点に潰れる 図: 同心円の 2 組の 300 点を、生の座標で k 平均にかけたもの、10 近傍グラフの Laplacian の小さい固有値、最小 2 個の固有ベクトルの行とその k 平均。内外をまたぐ辺がないので固有値 0 が 2 個あり、行は 2 点に潰れる
    この図の例では、生の座標の $k$ 平均と内外の区別の一致率は $56\%$、固有ベクトルの行の $k$ 平均では $100\%$ である(数値計算による値)。

例題

三角形 2 つを橋で結ぶ

頂点 $1,2,3$ の三角形と頂点 $4,5,6$ の三角形を辺 $34$ で結ぶ。重みはすべて $1$ とする。

  • 使う公式:thm-spc-relax の下界。
  • 答え:$\mu_2=(5-\sqrt{17})/2\approx0.4384$ で、Fiedler ベクトルの符号から $\{1,2,3\}\mid\{4,5,6\}$ に分かれる。この分割の $\mathrm{RatioCut}=2/3\approx0.6667\ge\mu_2$、$\mathrm{Ncut}=2/7\approx0.2857\ge\nu_2=(11-\sqrt{73})/12\approx0.2047$ である。
  • 代表点:正規化した固有ベクトルは $(0.4647,0.4647,0.2610,-0.2610,-0.4647,-0.4647)$(数値計算による値)。prop-spc-cheeger は $h=1/7\approx0.1429$ で $0.1023\le0.1429\le0.6398$ となる。
    固有値の求め方

    特性多項式は $x(x-3)^3(x^2-5x+2)$ である。$(1,1,b,-b,-1,-1)$ の形を仮定すると、頂点 $1$ の式から $(2-\mu)-1-b=0$、頂点 $3$ の式から $3b-2-(-b)=\mu b$ となる。$b=1-\mu$ を入れて $\mu^2-5\mu+2=0$ を得るので $\mu=(5-\sqrt{17})/2$、$b=1-\mu\approx0.5616$ である。

連結成分が 2 個のとき、行が 2 点に潰れる

三角形 2 つを辺で結ばずに置く。$\mu=0,0,3,3,3,3$ である。

  • 使う公式:thm-spc-ideal。
  • 答え:核の基底に回転 $Q$ を掛けても、行は 2 点に潰れて互いに直交し、長さの 2 乗は $1/3$ である。
  • 代表点:$0.7$ ラジアンの回転では、行は $(0.4416,-0.3719)$(前半の 3 頂点)と $(0.3719,0.4416)$(後半の 3 頂点)である。内積は $0$、長さの 2 乗は $0.3333$ となる。
最小カットと RatioCut の違い

完全グラフ $K_4$ を 2 つ(頂点 $0$〜$3$ と $4$〜$7$)辺 $04$、$15$ で結び、頂点 $0$ に頂点 $8$ をぶら下げる。

  • 使う公式:RatioCut と Ncut の定義、thm-spc-relax。
  • 答え:最小カットは頂点 $8$ だけを切り離す重み $1$ の切断である。比で測ると最小は $\{0,1,2,3,8\}\mid\{4,5,6,7\}$ に移り、固有ベクトルの符号もこれを返す。
  • 代表点:下の表のとおり。$\mu_2\approx0.6404$、$\nu_2\approx0.2209$(数値計算による値)。
    分割切る重みRatioCutNcut
    $\{8\}$ と残り$1$$1+\frac18=1.125$$1+\frac1{29}\approx1.0345$
    $\{0,1,2,3,8\}$ と $\{4,5,6,7\}$$2$$\frac25+\frac24=0.9$$\frac2{16}+\frac2{14}\approx0.2679$
誤差の評価と実際の値

$K_m$ を 2 つ、辺 1 本で結ぶ。$A_1,A_2$ を 2 つの $K_m$ とすれば $\rho=2/m$、$\gamma=m$ である。

  • 使う公式:thm-spc-perturb。
  • 答え:$\|U-HQ\|_F^2\le4/m^2$ で、$m$ が大きいほど行は 2 点に集まる。$m=20$ で $16\rho\,n_{\max}/\gamma=1.6< 20$ なので、$k$ 平均の最小解の誤分類は高々 $1$ 個である。
  • 代表点:下の表のとおり。
    $m$$\mu_2$ の近似$\Vert U-HQ\Vert_F^2$(数値計算による値)上界 $2\rho/\gamma$
    $3$$0.4384$$0.0561$$0.4444$
    $5$$0.2984$$0.0159$$0.16$
    $20$$0.0913$$0.0004$$0.01$

使える条件と反例

外す条件反例成り立たなくなること
$w_{il}\ge0$三角形で $w_{12}=w_{13}=1$、$w_{23}=-\frac12$$\dim\ker L$ が連結成分の個数に等しいこと
成分がちょうど $k$ 個$K_2$ を 3 つ置いて $k=2$ とする行が $k$ 点に潰れて分割が定まること
$\mu_k< \mu_{k+1}$4 頂点の閉路 $C_4$ で $k=2$$U$ の張る空間と得られる分割の一意性
$d_i>0$孤立点のあるグラフ$L_{\mathrm{sym}}$ が定義されること
丸めを $k$ 平均の最小解とすることゴキブリグラフ符号で丸めた分割が比の小さい分割に近いこと(thm-spc-perturb の結論は $k$ 平均の最小解についてのもので、この例でも成り立つ)
反例の確かめ

負の重み。 $L=\begin{pmatrix}2&-1&-1\\-1&\frac12&\frac12\\-1&\frac12&\frac12\end{pmatrix}$ の固有値は $0,0,3$ で、$\mathbf{1}$ と $(0,1,-1)$ が核に入る。グラフは連結なのに核は 2 次元である。
成分の個数が合わない。 $K_2$ を 3 つ置くと固有値は $0,0,0,2,2,2$ で、核は 3 次元である。$k=2$ で 2 本の固有ベクトルを選ぶ自由度があり、選び方で行の配置が変わる。
固有値が縮退する。 $C_4$(頂点を巡回順に $1,2,3,4$)の固有値は $0,2,2,4$ である。$\mu_2=\mu_3$ で、$(1,1,-1,-1)$ と $(1,-1,-1,1)$ はどちらも $\mu_2$ の固有ベクトルだが、符号の分割はそれぞれ $\{1,2\}\mid\{3,4\}$ と $\{1,4\}\mid\{2,3\}$ となる。どちらも $\mathrm{RatioCut}=2$ で、対称性から一方を選ぶ理由がない。
孤立点。 $d_i=0$ の頂点では $D^{-1/2}$ が定義できない。$L$ なら孤立点は 1 つの連結成分として扱える。
丸めの失敗。 上下に長さ $2m$ の道($v_1,\dots,v_{2m}$ と $w_1,\dots,w_{2m}$)を置き、右半分 $i>m$ で $v_iw_i$ を結ぶ(ゴキブリグラフGM98)。$m=10$ で Fiedler ベクトルの符号は上下の分割を返し、その $\mathrm{RatioCut}=\frac{m}{2m}+\frac{m}{2m}=1$ である。ところが尾の辺 $v_mv_{m+1}$ を 1 本切ると $\frac1m+\frac1{3m}=\frac{4}{3m}\approx0.1333$ で、左右に切っても $\frac2m=0.2$ である。$\mu_2\approx0.0209$(数値計算による値)で、thm-spc-relax の下界はどの分割でも成り立つが、符号による丸めは比の小さい分割を返していない。一方、行の $k$ 平均の最小解は符号の分割とは異なり、上か下の道の端の $9$ 頂点を切り離す分割で、$\mathrm{RatioCut}=\frac19+\frac1{31}\approx0.1434$ である(数値計算による値)。ただし、実用の反復解がこの最小解に達するとは限らない。尾を切る分割では $\rho=\frac4{3m}$、$n_{\max}=3m$ だから $16\rho\,n_{\max}/\gamma=64/\gamma$ で、道の Laplacian の固有値は $4$ 未満なので $\gamma< 4$ より $64/\gamma>16>10=m=n_{\min}$ となり、thm-spc-perturb の仮定を満たさない。

よくある誤り

誤り正しくは
$L$ の大きい固有値の固有ベクトルを取る小さい方を取る。大きい方を取るのは $W$ や $D^{-1/2}WD^{-1/2}$ の固有ベクトルを使う場合である
$k$ 平均を固有ベクトルの列にかける分類するのは頂点なので行にかける
行の座標の値そのものを解釈する基底の取り方で変わる。意味があるのは回転 $Q$ を除いた配置(距離)だけである
緩和の最小値が RatioCut の最小値に等しいと思う一般には下界にすぎない。ex-spc-bridge でも $\mu_2\approx0.4384$ に対し $2/3$ である
最小カットを求めれば同じだと思う分母がないと小さい組を切り離す。ex-spc-pendant を見よ
正規化の違いを無視する$L$ は RatioCut、$L_{\mathrm{sym}}$ と $L_{\mathrm{rw}}$ は Ncut の緩和である

補足

ランダムウォークとの関係。 $W$ から遷移確率 $P_{il}:=w_{il}/d_i$ を定めると $L_{\mathrm{rw}}=I-P$ であり、定常分布は $\pi_i=d_i/\mathrm{vol}\,V$ である。定常な歩きで $X_0\sim\pi$ とすれば $\mathbb{P}(X_1\in A^c\mid X_0\in A)=W(A,A^c)/\mathrm{vol}\,A$ なので、
$$\mathrm{Ncut}(A,A^c)=\mathbb{P}(X_1\in A^c\mid X_0\in A)+\mathbb{P}(X_1\in A\mid X_0\in A^c)$$
となる。Ncut の小さい分割は、歩きが組の間をめったに移らない分割である(Markov連鎖)。
固有ベクトルの摂動。 $L$ を $L_0$ の摂動と見れば、固有空間の傾きは固有値の間隔で割った量で抑えられる(Davis–Kahan の定理、vL07 に紹介がある)。thm-spc-perturb は間隔の代わりに $\rho/\gamma$ を使う評価である。
多分割の Cheeger 不等式。 Lee–Oveis Gharan–Trevisan は $d$-正則グラフで $L=I-A/d$($A$ は隣接行列)の $k$ 番目の固有値 $\lambda_k$ と、互いに交わらない $k$ 個の集合の展開率の最大の最小値 $\rho(k)$ に対し $\lambda_k/2\le\rho(k)\le O(k^2)\sqrt{\lambda_k}$ を示したLOT11。prop-spc-cheeger の $k$ 組版にあたる。
$k$ 平均との違い。 $k$ 平均は組を凸な領域に限る。スペクトルクラスタリングの組に形の制限はないが、類似度グラフの作り方に結果が左右される。局所的なつながりをデータの形の情報に変えるという見方は、多次元尺度法 を最短路の距離に当てる方法と共通する。

関連項目

参考文献

[1]
Ulrike von Luxburg, A tutorial on spectral clustering, Statistics and Computing, 2007, pp. 395–416(§3 グラフ Laplacian、§4 3 種の算法、§5 切断の緩和、§7 摂動、§8 実用上の注意)
[2]
Shai Shalev-Shwartz, Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, §22.2(pp. 311–314、k 平均の目的関数と Lemma 22.1)、§22.3(pp. 315–317、Lemma 22.3 と Unnormalized Spectral Clustering)
[3]
James R. Lee, Shayan Oveis Gharan, Luca Trevisan, Multi-way spectral partitioning and higher-order Cheeger inequalities, arXiv preprint, 2011, Theorem 1.1
[4]
Lars Hagen, Andrew B. Kahng, New spectral methods for ratio cut partitioning and clustering, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992, pp. 1074–1085
[5]
Jianbo Shi, Jitendra Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, pp. 888–905
[6]
Stephen Guattery, Gary L. Miller, On the quality of spectral separators, SIAM Journal on Matrix Analysis and Applications, 1998, pp. 701–719

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する