* '''k'''-means法 ('''k'''-means method) [#edca1ecc]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

次の目的関数を最小化する分割最適化クラスタリングの代表的手法.
\[\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\|\) はユークリッドノルム.

*** アルゴリズム [#oe5f6cbd]
入力はデータ集合 \(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)\).

*** 正規分布の混合分布との関連 [#t838b378]
全てのクラスタについて共通の標準偏差 σ と単位行列 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]] など,クラスタリングができる統計・機械学習統合ソフトには入っている.

>-- しましま

**関連項目 [#td40dd7d]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[k-means method]]
#br
-[[セントロイド]]
-[[centroid]]
#br
-[[クラスタリング]]
-[[分割最適化クラスタリング]]
-[[k-medoids法]]
-[[EMアルゴリズム]]
-[[混合分布]]
-[[ベクトル量子化]]
-[[カーネルk-means法]]
-[[VFKM]]
-[[ファジィc-means法]]
#br
-[[検索:k-means k平均法]]

**リンク集 [#z2cb7348]

//関連するWWW資源があればリンクしてください.
-[[クラスタリングとは (クラスター分析とは) >http://www.kamishima.net/jp/clustering/]] @ 神嶌敏弘:基本的な手法の説明とクラスタリングを用いた分析での注意点
-[[A Tutorial on Clustering Algorithms>http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/kmeans.html]]
:Javaアプレットのデモがある
#br
-[[Wikipedia:K-means_algorithm]]
-[[MathWorld:K-MeansClusteringAlgorithm]]
-[[Wikipedia.jp:K平均法]]

**関連文献 [#x2cf5e8e]

//この%項目%に関連する書籍や論文を紹介してください.
-基本文献~
J.McQueen "Some methods for classification and analysis of multivariate observations" In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp.281-297 (1967)~
[[GoogleScholarAll:Some methods for classification and analysis of multivariate observations]]
-初期化法の改良~
[[P.S.Bradley and U.M.Fayyad: Refining Initial Points for K-Means Clustering, in Proceedings of the 15th International Conference on Machine Learning, pp.91-99 (1998)>http://research.microsoft.com/research/pubs/view.aspx?type=Technical%20Report&id=200]]~
[[GoogleScholarAll:Refining Initial Points for K-Means Clustering]]
- 混合正規分布の最適化を確定的焼き鈍しで解くとき,k-means法は温度0の状態とみることができることを示す~
S.Zhong and J.Ghosh "A Unified Framework for Model-based Clustering",JMLR, vol.4, pp.1001-1037 (2003)~
[[GoogleScholarAll:A Unified Framework for Model-based Clustering]]
- 距離が三角不等式を満たすことを利用し,冗長な距離の計算を削減することによる高速化.反復数をL として,通常は n k L 回距離を計算するが,それを n回に近づける~
[[Charles Elkan "Using the Triangle Inequality to Accelerate k-Means" 20th ICML, pp.147-153 (2003)>Paper/ICML-2003-p147]]~
[[GoogleScholarAll:Using the Triangle Inequality to Accelerate k-Means]]
-[[Book/Pattern Recognition and Machine Learning]] 9.1章
-[[Book/パターン認識と学習の統計学(統計科学のフロンティア6)]] 第I部 4.2節
-[[Book/データマイニングの基礎]] 3.2.3-3.2.4節
-[[Book/Pattern Classification]] 10.8節
-[[Book/Rで学ぶクラスタ解析]] 5章
-[[Book/パターン認識(Rで学ぶデータサイエンス5)]] 2.2節

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS