k平均法

同義語:k-means法k-means clusteringLloydのアルゴリズムLloyd's algorithm

概要

k平均法(k-means clustering)とは、$\mathbb{R}^d$ の点を $k$ 組に分け、各組の平均からの 2 乗距離の和を小さくする方法で、各点を最も近い中心の組へ移す段と各組の平均を中心にする段を交互に繰り返す Lloyd の反復を指すことが多い。反復は目的関数を単調に下げて有限回で止まるが、止まる先は最小解とは限らず、値の比に上限はない。厳密な最小化は $k=2$ でも $d$ を入力に含めると NP 困難である。データの要約の基本の道具で、主成分分析やスペクトルクラスタリングと跡の形でつながる。

$$\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}} $$

前提知識: 距離空間, 主成分分析

$\mathbb{R}^d$ の $n$ 個の点を $k$ 組に分けるとき、各組の平均からの 2 乗距離の和をできるだけ小さくしたい。これが $k$ 平均の問題である。厳密な最小化は難しいので、実用では「各点を最も近い中心の組へ移す」「各組の平均を新しい中心にする」を交互に繰り返す Lloyd の反復を使い、多くの場合はこの反復そのものを $k$ 平均法と呼ぶ。
反復は目的関数を単調に下げ、有限回で止まる。しかし止まった先が最小とは限らず、値の比はいくらでも悪くなりうる。ここでは目的関数の公式、反復の停止の証明、止まる点の性質、局所最適の例を示し、計算の難しさの位置づけ、主成分分析 および スペクトルクラスタリング との関係を述べる。

定義と使える条件

$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)。距離を替えると平均が最適とは限らない(反例の節)。使える条件は次のとおりである。

  • データが $\mathbb{R}^d$ の点で、座標の尺度に意味がある(尺度を変えると最小解が変わる。ex-kmn-rectangle)。
  • 組の数 $k$ を先に決める。
  • 組の形が凸でよい(各組は超平面で切り分けられる。prop-kmn-opt)。
Lloyd の反復

中心 $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 点の距離の形」と「全平方和の分解」が成り立つ。

1 次の項が消える

$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$ を大きくすることと同じである。

Lloyd の反復は値を下げて有限回で止まる

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 点の移動で改善できない」という基準がある。

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)。

最小解の性質
  1. $\mathrm{OPT}_k$ を与える分割では、各点の組の中心は(空でない組の中心の中で)最も近い。とくに、2 つの組は中心の垂直二等分超平面で切り分けられる。
  2. $\mathrm{OPT}_{k+1}\le\mathrm{OPT}_k$ であり、相異なる点の個数が $k$ より多ければ不等号は真である。相異なる点の個数が $k$ 以下なら $\mathrm{OPT}_k=0$ である。
  3. $d=1$ なら、点を整列して区間に分ける最小解があり、$D_j(i)$ を最初の $i$ 点を高々 $j$ 組に分ける最小値とすると、$D_j(i)=\min_{0\le l\le i}\bigl(D_{j-1}(l)+w(l+1,i)\bigr)$ で求まる。ここで $w(a,b)$ は $a$ 番目から $b$ 番目の点の組の値(空なら $0$)で、累積和により $O(1)$ で計算できる。全体で $O(kn^2)$ である。
交換の議論
  1. ある点により近い中心があれば、その点を移して中心を据え置くと $G(C;c)$ は真に減り、更新でさらに減らないので最小性に反する。$\|x-m_a\|\le\|x-m_b\|$ は半空間の条件である。
  2. 最小解の組を 1 つ増やしてよいので $\le$ である。相異なる点が $k$ より多ければ、最小解のある組は相異なる 2 点を含み、平均と異なる点 $x$ がその組にある。$x$ を新しい組に分けると、prop-kmn-move の除くときの式より値が真に減る。相異なる点が $k$ 以下なら、同じ点ごとに組にすれば $0$ である。
  3. 最小解の中心を小さい順に並べ(重複は 1 つにまとめる)、各点を最も近い中心に、同点なら番号の小さい中心に割り当て直す。中心を据え置くと値は増えず、更新でも増えない。数直線上で各中心に最も近い点の集合は区間なので、分割は区間からなる。漸化式は最後の区間の左端で場合分けしたものである。$\square$

主成分とスペクトルクラスタリングとの関係

点は全体の平均が $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$ では等号)。

定数ベクトルの分だけ次元が 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$ 平均、カーネル法)。とくに次が成り立つ。

RatioCut はカーネル $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$

計算の手順

  1. 尺度をそろえる。単位の異なる変数は標準化するか、尺度の意味を決めてから使う。
  2. $k$ を決める。$\mathrm{OPT}_k$ は $k$ について減るので(prop-kmn-opt (2))、値が最小になる $k$ を選ぶと無意味である。減り方の変化を見るか、別の基準を使う。
  3. 中心を初期化する。データから一様に $k$ 点を選ぶか、$k$-means++ を使う:1 点目を一様に選び、次の点は「既に選んだ中心までの距離の 2 乗」に比例する確率で選ぶ。この種まきの段だけで $E[G]\le8(\ln k+2)\mathrm{OPT}_k$ が成り立つ(AV07 Theorem 1.1、この記事では証明しない)。
  4. def-kmn-lloyd の (a)(b) を、割り当てが変わらなくなるまで繰り返す。大きなデータでは値の減少が相対的に小さくなったところで打ち切ってもよい。
  5. 空の組ができたら、遠い点を新しい中心にするなどの処理をする(ex-kmn-empty)。
  6. 初期値を変えて何度も行い、$G$ の最小のものを採るHTF09。
    図: 3 つの塊の 120 点に Lloyd の反復を当てた結果。左は最小の値に達した分割、中は 1 つの塊を 2 つに割り 2 つの塊をまとめて止まった分割、右は 200 回の初期値での最終値の分布 図: 3 つの塊の 120 点に Lloyd の反復を当てた結果。左は最小の値に達した分割、中は 1 つの塊を 2 つに割り 2 つの塊をまとめて止まった分割、右は 200 回の初期値での最終値の分布
    図は平均 $(0,0)$、$(5,0)$、$(2.5,4)$、標準偏差 $0.7$ の 2 次元正規分布から各 40 点を種 20261107 で生成し、データから一様に選んだ 200 通りの初期値で反復した数値計算の結果である。89% の初期値で最小の値 $115.33$ に達し、最大で $612.73$ に止まった。

例題

反復の表と外れ値

$x=1,2,3,8,9,10,25$、$k=2$、$c^{(0)}=(1,2)$ とする。

  • 使う公式:def-kmn-lloyd、prop-kmn-opt (3)。
  • 答え:反復は分割 $\{1,2,3\},\{8,9,10,25\}$ で止まり、$G=196$ である。最小解は $\{1,2,3,8,9,10\},\{25\}$ で $\mathrm{OPT}_2=77.5$ である。
  • 代表点:第 2 回の更新後の中心は $(2,13)$ で、$8$ は中心 $2$ まで $6$、中心 $13$ まで $5$ なのでとどまる。
    回割り当て中心(更新後)更新前の値更新後の値 $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変わらない停止
    $k$ を変えたときの最小値は $\mathrm{OPT}_1\approx403.43$、$\mathrm{OPT}_2=77.5$、$\mathrm{OPT}_3=4$($\{1,2,3\},\{8,9,10\},\{25\}$)、$\mathrm{OPT}_4=2.5$ である。$k=3$ までは大きく減り、それ以後は少ししか減らない。
同点で止まり局所最小でない例

$x=1,2,3,4$、$k=2$、$c^{(0)}=(2,4)$ とする(SSBD14 Exercise 2 の設定)。

  • 使う公式:def-kmn-lloyd、def-kmn-center-function。
  • 答え:$3$ は 2 つの中心から等距離で、番号の小さい組に入る。分割 $\{1,2,3\},\{4\}$ の中心は $(2,4)$ のままなので止まり、$G=2$ である。最小解は $\{1,2\},\{3,4\}$ で $\mathrm{OPT}_2=1$ である。
  • 代表点:小さい $\delta>0$ で $F(2,4-\delta)=2-2\delta+2\delta^2< 2$ であり、$(2,4)$ は $F$ の局所最小点でない。$\delta=0.1$ で $F=1.82$ である。
    $F$ の計算を開く

    中心を $(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$ で分ける。

  • 使う公式:lem-kmn-centroid、prop-kmn-move。
  • 答え:左右に分ける $\{(0,0),(0,b)\},\{(a,0),(a,b)\}$ は $G=b^2$ で最小である。上下に分ける $\{(0,0),(a,0)\},\{(0,b),(a,b)\}$ は $G=a^2$ で、Lloyd の反復の停止状態である。比 $(a/b)^2$ に上限はない。
  • 代表点:$a=3$、$b=1$ で $9$ と $1$ である。
    確かめを開く

    上下の分け方の中心は $(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$ 方向に $b/a$ 倍、$y$ 方向に $a/b$ 倍にすると縦横が入れ替わり、最小解も入れ替わる。最小解は尺度の取り方に依存する。
反復は止まるが 1 点の移動で改善できる例

$x=0,\ 2,\ 3.5$、$k=2$ とする。

  • 使う公式:prop-kmn-move。
  • 答え:分割 $\{0,2\},\{3.5\}$ の中心は $(1,3.5)$ で、同点はないので停止状態($F$ の狭義の局所最小)であり、$G=2$ である。$2$ を移すと $\Delta=\frac12(1.5)^2-2\cdot1^2=-0.875$ で、$\{0\},\{2,3.5\}$ の $G=1.125$ になる。
  • 代表点:$\{0\},\{2,3.5\}$ の中心 $(0,2.75)$ でも止まる。これが $\mathrm{OPT}_2=1.125$ である。
同心円は分けられない

$\mathbb{R}^2$ の原点中心の半径 $1$ と半径 $2$ の円周上の点の組で、外の円の点の凸包の内部に内の円の点がすべて入るデータ(たとえば外の円に等間隔に 4 点以上)を考える。

  • 使う公式:prop-kmn-opt (1)。
  • 答え:$k=2$ の最小解は超平面で切り分けられる。外の円の点を片側の閉半平面に入れると内の円の点は開半平面の中に入るので、内の組と外の組は直線で切り分けられず、最小解は内外の分割ではない。
  • 代表点:スペクトルクラスタリング の図の例では、生の座標の $k$ 平均と内外の区別の一致率が $56\%$ である。
空の組ができる例

$\mathbb{R}^2$ の 6 点 $(6,4),(0,5),(0,0),(2,0),(6,6),(5,5)$、$k=3$、初期の中心を点 $(0,5),(2,0),(0,0)$ とする。

  • 使う公式:def-kmn-lloyd。
  • 答え:第 1 回の割り当ては $\{(0,5),(6,6),(5,5)\},\{(6,4),(2,0)\},\{(0,0)\}$ で、中心は $(\frac{11}3,\frac{16}3),(4,2),(0,0)$ である。第 2 回には $(6,4)$ が組 1 へ、$(2,0)$ が組 3 へ移り、組 2 が空になる。
  • 代表点:反復は 2 組 $\{(6,4),(0,5),(6,6),(5,5)\},\{(0,0),(2,0)\}$ のまま止まり、$G=28.75$ である。データの点から初期化しても組の数は減りうる。

使える条件と反例

外す条件反例成り立たなくなること
同点の規則下の 4 点の例thm-kmn-lloyd の有限回の停止
2 乗距離($\ell^1$ 距離に平均を組み合わせる)$\{0,0,3\}$更新で値が下がること
初期値によらないという期待ex-kmn-rectangle、ex-kmn-table最小解に達すること
同点がないことex-kmn-tiethm-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 が扱っている。

関連項目

参考文献

[1]
Shai Shalev-Shwartz, Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, §22.2(pp. 311–314、k-Means Algorithm と Lemma 22.1)、§22.8 の Exercises 1, 2(pp. 320–321)
[2]
Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006, §9.1(pp. 424–428)、§9.3.2(pp. 443–444)
[4]
S. Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory, 1982, pp. 129–137
[5]
J. A. Hartigan, M. A. Wong, Algorithm AS 136: A K-means clustering algorithm, Applied Statistics, 1979, pp. 100–108
[6]
David Arthur, Sergei Vassilvitskii, k-means++: The advantages of careful seeding, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 2007, pp. 1027–1035、§1 と Theorem 1.1
[7]
Andrea Vattani, k-means requires exponentially many iterations even in the plane, Discrete & Computational Geometry, 2011, pp. 596–616
[9]
Daniel Aloise, Amit Deshpande, Pierre Hansen, Preyas Popat, NP-hardness of Euclidean sum-of-squares clustering, Machine Learning, 2009, pp. 245–248
[10]
Meena Mahajan, Prajakta Nimbhorkar, Kasturi Varadarajan, The planar k-means problem is NP-hard, Theoretical Computer Science, 2012, pp. 13–21
[11]
Chris Ding, Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the Twenty-First International Conference on Machine Learning (ICML 2004), 2004, Theorem 3.1
[12]
Inderjit S. Dhillon, Yuqiang Guan, Brian Kulis, Kernel k-means: spectral clustering and normalized cuts, Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004, pp. 551–556

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