k-means法

これらのキーワードがハイライトされています：最適化 optimization

k-means法 (k-means method)†

次の目的関数を最小化する分割最適化クラスタリングの代表的手法． $\mathrm{Err}(\{X_i\})=\sum_i^k\;\sum_{\mathbf{x}\in X_i}\;{\|\mathbf{x} - \bar{\mathbf{x}}_i\|}^2$ ただし，データ集合 $X$ は，ベクトルで表現されたデータ $\mathbf{x}$ の集合．クラスタ $X_i$ は，データ集合の網羅的で互いに素な部分集合． $\bar{\mathbf{x}}_i$ は $X_i$ 中の重心(セントロイドともいう)． $\|\cdot\|$ はユークリッドノルム．

↑

アルゴリズム †

入力はデータ集合 $X$ とクラスタ数 $k$ ，および最大反復数 maxIter．

初期化：データ集合をランダムに $k$ 個のクラスタ分割し，初期クラスタを得る
各クラスタについてセントロイド $\mathbf{x}_i=\frac{1}{|X_i|}\sum_{\mathbf{x}\in X_i} \mathbf{x}$ を計算
全てのデータ $\mathbf{x}\in X$ を，各クラスタのセントロイド $\mathbf{x}_i$ との距離 $\|\mathbf{x}-\mathbf{x}_i\|$ を最小にするクラスタ $X_i$ へ割り当てる
前の反復とクラスタに変化がないか反復数が maxIter を超えたら終了しクラスタ $\{X_i\}$ を出力．そうでなければ，ステップ2に戻る．

目的関数 $\mathrm{Err}(\{X_i\})$ の値は単調非増加になり，局所最適解が必ず見つかる．通常は，異なる初期クラスタで上記アルゴリズムを何回か適用し，目的関数を最小化する分割を選んで，より大域最適に近い解を探す．計算量はデータ数を $N$ として，反復回数を定数とみなせば $O(Nk)$ ．

↑

正規分布の混合分布との関連†

全てのクラスタについて共通の標準偏差 σ と単位行列 I で表される共分散行列 $\sigma^2 I$ と，各クラスタごとに異なる中心点 $\bar{\mathbf{x}}_i$ の多変量正規分布 $f(\mathbf{x};\bar{\mathbf{x}}_i,\sigma^2 I)$ を考える．これらの混合分布は次式： $f(\mathbf{x})=\sum_i^k \alpha_i f(\mathbf{x};\bar{\mathbf{x}}_i,\sigma^2 I)$ この混合分布のデータ集合 $X$ に対する最尤推定をEMアルゴリズムで求める．この過程はk-means法と関連がある．相違点は，データのクラスタへの割り当てを [0,1] の範囲の実数が混合分布+EMアルゴリズムでは許されるが，k-means法では，一つのデータはいずれか一つのクラスタの要素にしかならない点が異なる．