次の目的関数を最小化する分割最適化クラスタリングの代表的手法. \[\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.
目的関数 \(\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法では,一つのデータはいずれか一つのクラスタの要素にしかならない点が異なる.
このことから,k-means法では,クラスタが全て超球状になり,また,そのクラスタの半径はほぼ等しくなることが暗黙的に仮定されている. よってこの仮定に合わないクラスタは抽出されないことに注意.
R や Weka など,クラスタリングができる統計・機械学習統合ソフトには入っている.
-- しましま