K平均法

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

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

アルゴリズム

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

1. 各データ$x_i(i=1\cdots n)$に対してランダムにクラスタを割り振る。
2. 割り振ったデータをもとに各クラスタの中心$V_j(j=1\cdots K)$を計算する。計算は通常割り当てられたデータの各要素の平均が使用される。
3. 各 x_i と各 V_j との距離を求め、x_i を最も近い中心のクラスタに割り当て直す。
4. 上記の処理で全ての x_i のクラスタの割り当てが変化しなかった場合は処理を終了する。それ以外の場合は新しく割り振られたクラスタから V_j を再計算して上記の処理を繰り返す。

結果は、最初のクラスタのランダムな割り振りに大きく依存することが知られており、1回の結果で最良のものが得られるとは限らない。

参考文献

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

関連項目

• ベクトル量子化