スペクトルクラスタリング(spectral clustering)とは、データの点を頂点とする非負の重みのグラフの Laplacian の最小 $k$ 個の固有ベクトルを列に並べ、その行を $k$ 平均法で分ける方法である。グラフがちょうど $k$ 個の連結成分を持てば行は直交する $k$ 点に潰れ、分割は連結成分に一致する。一般のグラフでは、固有値問題は RatioCut や Ncut という切断の最小化を、列の直交性だけに緩めた問題にあたり、最小 $k$ 個の固有値の和が切断の下界を与える。緩和なので最良の分割を返すとは限らないが、座標の近さでなくつながりで分けるので凸でない塊も扱える。
前提知識: 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$ を付ける流儀もあり、その場合は値が半分になる。
$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$ 行とする。
$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.$$
$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) $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 以上とする。$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$ である。
図: 同心円の 2 組の 300 点を、生の座標で k 平均にかけたもの、10 近傍グラフの Laplacian の小さい固有値、最小 2 個の固有ベクトルの行とその k 平均。内外をまたぐ辺がないので固有値 0 が 2 個あり、行は 2 点に潰れる
頂点 $1,2,3$ の三角形と頂点 $4,5,6$ の三角形を辺 $34$ で結ぶ。重みはすべて $1$ とする。
特性多項式は $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 つを辺で結ばずに置く。$\mu=0,0,3,3,3,3$ である。
完全グラフ $K_4$ を 2 つ(頂点 $0$〜$3$ と $4$〜$7$)辺 $04$、$15$ で結び、頂点 $0$ に頂点 $8$ をぶら下げる。
| 分割 | 切る重み | RatioCut | Ncut |
|---|---|---|---|
| $\{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$ である。
| $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$ 平均は組を凸な領域に限る。スペクトルクラスタリングの組に形の制限はないが、類似度グラフの作り方に結果が左右される。局所的なつながりをデータの形の情報に変えるという見方は、多次元尺度法 を最短路の距離に当てる方法と共通する。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する