K平均法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年8月7日 (水) 09:08時点におけるEsploro (トーク)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

K平均法(Kへいきんほう、k-means clustering)は、MacQueen、Anderberg、Forgyらにより提案された非階層型クラスタリング手法の1つ。クラスタの平均を用い、与えられたクラスタ数K個に分類することから、MacQueenによりこう呼ばれた。K-平均法(K-means)、c-平均法(c-means)とも呼ばれる。

単純なアルゴリズムで計算することができるため、現在広く用いられている。分類をファジィ化したファジィc-平均法エントロピー法をはじめ、データ構造を発見するさまざまな応用手法が提案されている。

アルゴリズム

K-平均法は、一般には以下のような流れで実装される[1][2]。データの数を n 、クラスタの数を K としておく。

  1. 各データ <math>x_i(i=1\cdots n)</math> に対してランダムにクラスタを割り振る。
  2. 割り振ったデータをもとに各クラスタの中心 <math>V_j(j=1\cdots K)</math> を計算する。計算は通常割り当てられたデータの各要素の算術平均が使用される。
  3. 各 <math>x_i</math> と各 <math>V_j</math> との距離を求め、<math>x_i</math> を最も近い中心のクラスタに割り当て直す。
  4. 上記の処理で全ての <math>x_i</math> のクラスタの割り当てが変化しなかった場合、あるいは変化量が事前に設定した一定の閾値を下回った場合に、収束したと判断して処理を終了する。そうでない場合は新しく割り振られたクラスタから <math>V_j</math> を再計算して上記の処理を繰り返す。

結果は、最初のクラスタのランダムな割り振りに大きく依存することが知られており、1回の結果で最良のものが得られるとは限らない。そのため、何度か繰り返して行って最良の結果を選択する手法や、k-means++法のように最初のクラスタ中心点の振り方を工夫する手法などが使用されることがある。

なお、このアルゴリズムではクラスタ数 K は最初に所与のものとして定めるため、最適なクラスタ数を選ぶには他の計算等による考察を用いる必要がある。

脚注

テンプレート:脚注ヘルプ テンプレート:Reflist

参考文献

  • 宮本定明 『クラスター分析入門 ファジィクラスタリングの理論と応用』 森北出版株式会社、1999年、ISBN 4-627-91651-5

関連項目

  • テンプレート:Cite web
  • テンプレート:Cite web