k平均法(k-means clustering)とは、$\mathbb{R}^d$ の点を $k$ 組に分け、各組の平均からの 2 乗距離の和を小さくする方法で、各点を最も近い中心の組へ移す段と各組の平均を中心にする段を交互に繰り返す Lloyd の反復を指すことが多い。反復は目的関数を単調に下げて有限回で止まるが、止まる先は最小解とは限らず、値の比に上限はない。厳密な最小化は $k=2$ でも $d$ を入力に含めると NP 困難である。データの要約の基本の道具で、主成分分析やスペクトルクラスタリングと跡の形でつながる。
$\mathbb{R}^d$ の $n$ 個の点を $k$ 組に分けるとき、各組の平均からの 2 乗距離の和をできるだけ小さくしたい。これが $k$ 平均の問題である。厳密な最小化は難しいので、実用では「各点を最も近い中心の組へ移す」「各組の平均を新しい中心にする」を交互に繰り返す Lloyd の反復を使い、多くの場合はこの反復そのものを $k$ 平均法と呼ぶ。
反復は目的関数を単調に下げ、有限回で止まる。しかし止まった先が最小とは限らず、値の比はいくらでも悪くなりうる。ここでは目的関数の公式、反復の停止の証明、止まる点の性質、局所最適の例を示し、計算の難しさの位置づけ、主成分分析 および スペクトルクラスタリング との関係を述べる。
$x_1,\dots,x_n\in\mathbb{R}^d$(重複を許す)と $k\ge1$ を与える。添字の集合 $\{1,\dots,n\}$ を $k$ 個の組 $C=(C_1,\dots,C_k)$ に分け(空の組を許す)、$c=(c_1,\dots,c_k)\in(\mathbb{R}^d)^k$ に対し
$$G(C;c):=\sum_{j=1}^k\sum_{i\in C_j}\|x_i-c_j\|^2$$
とする。空でない組の平均を $m_j:=\frac1{|C_j|}\sum_{i\in C_j}x_i$ と書き、$m_j$ を中心に使った値を
$$G(C):=\sum_{j:\,C_j\ne\emptyset}\sum_{i\in C_j}\|x_i-m_j\|^2$$
とする。$\mathrm{OPT}_k:=\min_CG(C)$ を求める問題を $k$ 平均の問題 という。
$G(C)$ は スペクトルクラスタリング の定義「k 平均の目的関数」と同じ量である。距離は Euclid 距離の 2 乗で、そのために平均が最適な中心になる(lem-kmn-centroid)。距離を替えると平均が最適とは限らない(反例の節)。使える条件は次のとおりである。
中心 $c^{(0)}$ から始め、$t=1,2,\dots$ について次を繰り返す。
(a) 割り当て:各 $i$ を $\|x_i-c^{(t-1)}_j\|$ が最小の $j$ の組に入れて $C^{(t)}$ を作る。同点のときは、前の回の組がその最小を与えるならそこにとどめ、それ以外は番号の小さい組に入れる。
(b) 更新:$C^{(t)}_j\ne\emptyset$ なら $c^{(t)}_j:=m_j$ とし、空なら $c^{(t)}_j:=c^{(t-1)}_j$ とする。
(c) $C^{(t)}=C^{(t-1)}$ なら止まる。
反復は LloydLlo82 による(量子化の問題として提案された)。SSBD14 §22.2.1 は同点を任意に分けるとしているが、停止の証明には同点の規則が要る(ex-kmn-counter)。
| 量 | 式 | 根拠 | 条件 |
|---|---|---|---|
| 中心の取り替え | $\sum_{i\in C}\|x_i-c\|^2=\sum_{i\in C}\|x_i-m\|^2+\lvert C\rvert\|c-m\|^2$ | lem-kmn-centroid | $C\ne\emptyset$ |
| 2 点の距離の形 | $\sum_{i\in C}\|x_i-m\|^2=\frac1{2\lvert C\rvert}\sum_{i,l\in C}\|x_i-x_l\|^2$ | lem-kmn-centroid | $C\ne\emptyset$ |
| 全平方和の分解 | $\sum_i\|x_i-\bar x\|^2=G(C)+\sum_j\lvert C_j\rvert\|m_j-\bar x\|^2$ | lem-kmn-centroid | $\bar x$ は全体の平均 |
| 1 点を除く | 組の値の減少は $\frac{\lvert C\rvert}{\lvert C\rvert-1}\|x-m\|^2$ | prop-kmn-move | $\lvert C\rvert\ge2$ |
| 1 点を足す | 組の値の増加は $\frac{\lvert C\rvert}{\lvert C\rvert+1}\|x-m\|^2$ | prop-kmn-move | $C\ne\emptyset$ |
| 跡の形 | $G(C)=\mathrm{tr}K-\mathrm{tr}(H^{\top}KH)$ | thm-kmn-trace | 空の組なし |
| 主成分による下界 | $\mathrm{OPT}_k\ge\sum_{j\ge k}\lambda_j$ | thm-kmn-trace | $K$ は中心化した Gram 行列 |
| 1 次元の最小解 | 区間に分ける動的計画法、$O(kn^2)$ | prop-kmn-opt | $d=1$ |
空でない $C$ の平均を $m$ とする。任意の $c\in\mathbb{R}^d$ で
$$\sum_{i\in C}\|x_i-c\|^2=\sum_{i\in C}\|x_i-m\|^2+|C|\,\|c-m\|^2$$
である。したがって $m$ は左辺のただ 1 つの最小点であり、公式の表の「2 点の距離の形」と「全平方和の分解」が成り立つ。
$x_i-c=(x_i-m)+(m-c)$ として展開すると、交差項は $2\langle\sum_{i\in C}(x_i-m),\,m-c\rangle=0$ である。$c=x_l$ として $l\in C$ で足すと
$$\sum_{i,l\in C}\|x_i-x_l\|^2=|C|\sum_{i\in C}\|x_i-m\|^2+|C|\sum_{l\in C}\|x_l-m\|^2$$
で、これが 2 点の距離の形である。$c=\bar x$ として $j$ で足すと全平方和の分解を得る。$\square$
全平方和は $C$ によらないので、$G(C)$ を小さくすることは、組の間の平方和 $\sum_j|C_j|\|m_j-\bar x\|^2$ を大きくすることと同じである。
def-kmn-lloyd の反復について、$J_t:=G(C^{(t)};c^{(t)})$($t\ge1$)とおくと、$J_t=G(C^{(t)})$ であり、
$$J_{t+1}\le G(C^{(t+1)};c^{(t)})\le J_t$$
である。さらに $C^{(t+1)}\ne C^{(t)}$ なら $J_{t+1}< J_t$ である。したがって同じ割り当ては二度と現れず、反復は高々 $k^n+1$ 回の割り当てのあとで止まる。
$J_t=G(C^{(t)})$ は、空の組が和に寄与しないことと、更新の定義から分かる。
割り当ての段では、各 $i$ の項 $\|x_i-c^{(t)}_j\|^2$ を $j$ について最小にしているので、$G(C^{(t+1)};c^{(t)})\le G(C^{(t)};c^{(t)})=J_t$ である。更新の段では、空でない組ごとに lem-kmn-centroid を使い、$J_{t+1}\le G(C^{(t+1)};c^{(t)})$ を得る。
$C^{(t+1)}\ne C^{(t)}$ とする。ある $i$ の組が変わる。同点の規則により、$i$ は前の組が最小を与えないときだけ移るので、$i$ の項は真に減る。他の項は増えないので $G(C^{(t+1)};c^{(t)})< J_t$ となり、$J_{t+1}< J_t$ である。
$J_t=G(C^{(t)})$ は割り当て $C^{(t)}$ だけで決まり、止まるまでは真に減るので、同じ割り当ては繰り返されない。番号つきの割り当ては $k^n$ 個しかないから、反復は止まる。$\square$
単調性は SSBD14 Lemma 22.1(pp. 313–314)にある。有限回での停止の論法は AV07 §1 にも述べられている。反復の回数については、$k,d$ を固定すると $n$ の多項式になる上界 $O(n^{kd})$ が知られている一方、平面でも指数回 $2^{\Omega(n)}$ かかる入力がある(VattaniVat11)。実際のデータでは少ない回数で止まることが多い。
$F(c):=\sum_{i=1}^n\min_j\|x_i-c_j\|^2$ を 中心の関数 という。$F(c)=\min_CG(C;c)$ であり、lem-kmn-centroid より $\min_cF=\mathrm{OPT}_k$ である。
$F$ は連続で区分的に 2 次式だが、凸ではない。Lloyd の反復が止まった点は、$F$ の局所最小とは限らない。次がその正確な条件である。
$(C,c)$ を、組がすべて空でない Lloyd の反復の停止状態とする($c_j$ は $C_j$ の平均で、各 $i$ の組の中心が最も近い中心の一つ)。どの $x_i$ についても最も近い中心が 1 つだけなら、$c$ は $F$ の狭義の局所最小点である。同点があるときは局所最小とは限らない。
同点がないとする。不等式 $\|x_i-c_j\|< \|x_i-c_l\|$($i\in C_j$、$l\ne j$)は有限個で、$c$ の近くの $c'$ でも保たれる。よってその範囲で $F(c')=G(C;c')$ であり、lem-kmn-centroid より
$$F(c')=G(C;c)+\sum_j|C_j|\,\|c'_j-c_j\|^2$$
となる。組は空でないので、$c'\ne c$ で $F(c')>F(c)$ である。同点があるときの例は ex-kmn-tie で示す。$\square$
$F$ の局所最小より強い「1 点の移動で改善できない」という基準がある。
$C_a$($|C_a|=n_a\ge2$)の点 $x$ を、空でない $C_b$($|C_b|=n_b$)へ移すと、$G$ の変化は
$$\Delta=\frac{n_b}{n_b+1}\|x-m_b\|^2-\frac{n_a}{n_a-1}\|x-m_a\|^2$$
である。空の組のない分割ですべての移動で $\Delta\ge0$ なら、その分割は Lloyd の反復の停止状態である。逆は成り立たない。
$C$ の平均を $m$ とし、$C':=C\setminus\{x\}$($n:=|C|\ge2$)の平均を $m'$ とする。$nm=(n-1)m'+x$ から $m'-m=(m-x)/(n-1)$ である。lem-kmn-centroid を $C'$ と $c=m$ に当てて
$$\sum_{y\in C}\|y-m\|^2=\|x-m\|^2+\sum_{y\in C'}\|y-m'\|^2+(n-1)\frac{\|x-m\|^2}{(n-1)^2}=\sum_{y\in C'}\|y-m'\|^2+\frac n{n-1}\|x-m\|^2$$
を得る。これが除くときの式である。足すときは、$C_b\cup\{x\}$ にこの式を当てる。新しい平均を $m''$ とすると $x-m''=\frac{n_b}{n_b+1}(x-m_b)$ なので、増加は $\frac{n_b+1}{n_b}\cdot\frac{n_b^2}{(n_b+1)^2}\|x-m_b\|^2$ である。
すべての移動で $\Delta\ge0$ とする。$\|x-m_a\|^2\le\frac{n_b(n_a-1)}{(n_b+1)n_a}\|x-m_b\|^2\le\|x-m_b\|^2$ だから、各点の組の中心は最も近い。$|C_a|=1$ の点は $x=m_a$ で距離が $0$ なのでこれも正しい。逆が成り立たないことは ex-kmn-exchange で示す。$\square$
この基準を保証する改良が Hartigan–Wong の算法HW79 である(HTF09 §14.3.6)。
点は全体の平均が $0$ になるよう平行移動してあるとする($G$ は変わらない)。$X$ を $x_i$ を行とする $n\times d$ 行列、$K:=XX^{\top}$ を Gram 行列、$\lambda_1\ge\dots\ge\lambda_n\ge0$ をその固有値とする。空でない組からなる分割に対し、$H$ を第 $j$ 列が $h_j:=\mathbf{1}_{C_j}/\sqrt{|C_j|}$ である $n\times k$ 行列とする。
空でない $k$ 組の分割について $G(C)=\mathrm{tr}K-\mathrm{tr}(H^{\top}KH)$ である。したがって
$$\mathrm{OPT}_k\ge\sum_{j\ge k}\lambda_j$$
である($\lambda_k+\dots+\lambda_n$。$k=1$ では等号)。
$\sum_{i\in C}\|x_i-m\|^2=\sum_{i\in C}\|x_i\|^2-\frac1{|C|}\sum_{i,l\in C}\langle x_i,x_l\rangle$ である。第 2 項は $h_j^{\top}Kh_j$ に等しいので跡の形を得る。
$\mathbf{1}=\sum_j\sqrt{|C_j|}\,h_j$ は $H$ の列の張る空間 $W$ に入る。$\sum_ix_i=0$ より $K\mathbf{1}=0$ である。$W$ の正規直交基底を $\mathbf{1}/\sqrt n$ と、$\mathbf{1}$ に直交する $k-1$ 個のベクトルに取り直し、後者を列とする行列を $Q$ とする。跡は基底の取り方によらず、$\mathbf{1}/\sqrt n$ の項は $0$ なので $\mathrm{tr}(H^{\top}KH)=\mathrm{tr}(Q^{\top}KQ)$ である。スペクトルクラスタリング の定理「切断の最小化の緩和」の跡の下界を $-K$ に当てると、$\mathrm{tr}(Q^{\top}KQ)\le\lambda_1+\dots+\lambda_{k-1}$ となる。$\mathrm{tr}K=\sum_j\lambda_j$ と合わせて、空の組のない分割で下界を得る。空でない組が $k'< k$ 個の分割では、同じ議論で $G\ge\sum_{j\ge k'}\lambda_j\ge\sum_{j\ge k}\lambda_j$ である。$\square$
下界は Ding–HeDH04 Theorem 3.1 にある。右辺は、$x_i$ を上位 $k-1$ 個の主方向で近似したときの残差の平方和である(主成分分析)。$k$ 平均は $k$ 個の点で近似し、主成分は $k-1$ 次元の部分空間で近似する。$k$ 個の点は $k-1$ 次元の(アフィン)部分空間に入るので、制約の強い前者の値の方が大きい。長方形の例(ex-kmn-rectangle)では $a=3$、$b=1$、$k=2$ で下界も最小値も $1$ であり、等号が成り立つ。
跡の形は内積だけで書けるので、$K$ を一般の半正定値行列に替えても意味を持つ(カーネル $k$ 平均、カーネル法)。とくに次が成り立つ。
重み付きグラフの Laplacian を $L$ とし、$\mu_{\max}$ をその最大固有値、$\gamma\ge\mu_{\max}$ とする。$K:=\gamma I-L$ は半正定値で、空でない $k$ 組の分割に対し
$$\mathrm{tr}K-\mathrm{tr}(H^{\top}KH)=\gamma(n-k)-\mathrm{tr}L+\mathrm{RatioCut}(C_1,\dots,C_k)$$
である。右辺の RatioCut 以外の項は分割によらないので、空でない $k$ 組に限れば、RatioCut の最小化は $K$ についての跡の形の最小化と同値である。$K=YY^{\top}$ と分解して $Y$ の行を点とみれば、左辺は def-kmn-objective の $G(C)$ に等しい。
$L$ の固有値は $\mu_{\max}$ 以下なので $K$ は半正定値である。$H^{\top}H=I_k$ より $\mathrm{tr}(H^{\top}KH)=\gamma k-\mathrm{tr}(H^{\top}LH)$ であり、$\mathrm{tr}K=\gamma n-\mathrm{tr}L$ である。スペクトルクラスタリング の定理「切断の最小化の緩和」の等式 $\mathrm{tr}(H^{\top}LH)=\mathrm{RatioCut}$ を代入すれば等式を得る。左辺と $G(C)$ が等しいことは、thm-kmn-trace の証明の最初の計算(中心化を使わない)による。$\square$
図: 3 つの塊の 120 点に Lloyd の反復を当てた結果。左は最小の値に達した分割、中は 1 つの塊を 2 つに割り 2 つの塊をまとめて止まった分割、右は 200 回の初期値での最終値の分布
$x=1,2,3,8,9,10,25$、$k=2$、$c^{(0)}=(1,2)$ とする。
| 回 | 割り当て | 中心(更新後) | 更新前の値 | 更新後の値 $J_t$ |
|---|---|---|---|---|
| 1 | $\{1\},\{2,3,8,9,10,25\}$ | $1,\ 9.5$ | $679$ | $341.5$ |
| 2 | $\{1,2,3\},\{8,9,10,25\}$ | $2,\ 13$ | $248$ | $196$ |
| 3 | 変わらない | 停止 |
$x=1,2,3,4$、$k=2$、$c^{(0)}=(2,4)$ とする(SSBD14 Exercise 2 の設定)。
中心を $(2,4-\delta)$ とすると、$1,2$ は左の中心に、$3,4$ は右の中心に最も近い。値は $1+0+(1-\delta)^2+\delta^2$ である。
$a>b>0$ とし、長方形の 4 頂点 $(0,0),(0,b),(a,0),(a,b)$ を $k=2$ で分ける。
上下の分け方の中心は $(a/2,0)$、$(a/2,b)$ で、頂点から自分の中心まで $a/2$、もう一方まで $\sqrt{a^2/4+b^2}$ なので同点はなく、thm-kmn-local より $F$ の狭義の局所最小点である。1 点を移す変化は $\Delta=\frac23(\frac{a^2}4+b^2)-\frac{a^2}2=\frac{2b^2-a^2}3$ で、$a> \sqrt2b$ なら負(移すと改善する)、$a< \sqrt2b$ なら正である。$a=1.2$、$b=1$ では $\Delta\approx0.187$ で、1 点の移動でも抜け出せない。最小であることは、分け方を順に調べれば分かる($1$ 点と $3$ 点の分け方の値は $\frac23(a^2+b^2)$、対角の分け方と全部を 1 組にする分け方の値は $a^2+b^2$ である)。
$x=0,\ 2,\ 3.5$、$k=2$ とする。
$\mathbb{R}^2$ の原点中心の半径 $1$ と半径 $2$ の円周上の点の組で、外の円の点の凸包の内部に内の円の点がすべて入るデータ(たとえば外の円に等間隔に 4 点以上)を考える。
$\mathbb{R}^2$ の 6 点 $(6,4),(0,5),(0,0),(2,0),(6,6),(5,5)$、$k=3$、初期の中心を点 $(0,5),(2,0),(0,0)$ とする。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 同点の規則 | 下の 4 点の例 | thm-kmn-lloyd の有限回の停止 |
| 2 乗距離($\ell^1$ 距離に平均を組み合わせる) | $\{0,0,3\}$ | 更新で値が下がること |
| 初期値によらないという期待 | ex-kmn-rectangle、ex-kmn-table | 最小解に達すること |
| 同点がないこと | ex-kmn-tie | thm-kmn-local の局所最小性 |
| 凸な組で分けられること | ex-kmn-rings | 内外の分割を最小解として得ること |
同点の規則。 $x=-1,-1,1,1$、$k=2$ で組を $\{x_1,x_3\},\{x_2,x_4\}$ とすると、中心はどちらも $0$ で全点が同点である。同点を任意に分ける規則では、次の回に $x_1,x_3$ と $x_2,x_4$ の番号を入れ替えた割り当てを選べて、それを繰り返すと割り当てが永久に変わり続ける。値は $4$ のままである。単調性は保たれるが、停止しなくなる。
$\ell^1$ 距離。 目的関数を $\sum|x_i-c|$ に替えると、組 $\{0,0,3\}$ の中心 $0$(中央値)での値は $3$、平均 $1$ での値は $1+1+2=4$ で増える。距離を替えたら更新も替える必要があり、$\ell^1$ なら中央値である。
初期値。 長方形の上下の分割は、中心 $(a/2,0)$、$(a/2,b)$ から始めると動かない。
同点。 ex-kmn-tie の $F$ の計算が示すように、同点の点を片方に寄せる動きで $F$ が下がる。
凸性。 ex-kmn-rings では、最小解がどの分割であっても内外の分割にはならない。
| 誤り | 正しくは |
|---|---|
| $k$ 平均法は最小解を求める | Lloyd の反復は停止状態を求める。値の比に上限はない(ex-kmn-rectangle) |
| 止まった点は常に局所最小である | 同点があると違う(ex-kmn-tie) |
| $G$ が小さい $k$ を選べばよい | $\mathrm{OPT}_k$ は $k$ とともに減り、$k=n$ で $0$ である |
| 座標の単位は結果に関係ない | 最小解は回転・平行移動・一様な拡大では変わらないが、軸ごとの拡大では変わる |
| 組は同じ大きさになる | 外れ値 1 点が 1 組になることがある(ex-kmn-table) |
| 距離を替えても平均を中心に使える | 距離を替えると平均が最良とは限らない($\ell^1$ なら中央値) |
計算量。 $k$ 平均の問題は、$d$ を入力に含めると $k=2$ でも NP 困難であり(DasguptaDas08、Aloise ほかADHP09)、$d=2$ でも $k$ を入力に含めると NP 困難である(Mahajan ほかMNV12)。一方、$d=1$ は prop-kmn-opt (3) のとおり多項式時間で解ける。定数倍の近似についても難しさが知られているSSBD14。
量子化と混合分布。 $k$ 平均は $n$ 点の経験分布の $k$ 点量子化であり、$\mathrm{OPT}_k/n$ は レート歪み理論 の平均 2 乗歪みにあたるPW25。また、共通の球状の共分散 $\varepsilon I$ を持つ正規混合の EMアルゴリズム で $\varepsilon\to0$ とすると、E ステップの責任度が最も近い中心への割り当てになり、M ステップが平均の更新になる。Lloyd の反復はこの極限である(Bis06 §9.3.2)。
スペクトルクラスタリング での役割。 同記事の手順では、固有ベクトルの行を $k$ 平均法で丸める。prop-kmn-ratiocut は逆向きの関係で、RatioCut の最小化そのものがカーネルを選んだ $k$ 平均の問題である。カーネル $k$ 平均と切断の目的関数の対応は Dhillon–Guan–KulisDGK04 が扱っている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する