![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
次の目的関数を最小化する分割最適化クラスタリングの代表的手法． \mathrm{Err}(\{X_i\})=\sum_i^k\;\sum_{\mathbf{x}\in X_i}\;{\|\mathbf{x} - \bar{\mathbf{x}}_i\|}^2
入力はデータ集合 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)
このことから，k-means法では，クラスタが全て超球状になり，また，そのクラスタの半径はほぼ等しくなることが暗黙的に仮定されている． よってこの仮定に合わないクラスタは抽出されないことに注意．
R や Weka など，クラスタリングができる統計・機械学習統合ソフトには入っている．
-- しましま
