k平均法

k平均法の収束

k平均法︵kへいきんほう、英: k-means clustering︶は、非階層型クラスタリングのアルゴリズム。クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。k-平均法︵k-means︶、c-平均法︵c-means︶とも呼ばれる。

何度か再発見されており、まず、Hugo Steinhusが1957年に発表し、Stuart Lloydが1957年に考案し、E.W.Forgyが1965年に発表し、James MacQueenが1967年に発表しk-meansと命名した。

数式で表現すると、下記最適化問題を解くアルゴリズム。本アルゴリズムでは最小値ではなく初期値依存の極小値に収束する。

$\operatorname {arg\,min} _{V_{1},\dotsc ,V_{k}}\sum _{i=1}^{n}\min _{j}\left\|x_{i}-V_{j}\right\|^{2}$$\operatorname {arg\,min} _{V_{1},\dotsc ,V_{k}}\sum _{i=1}^{n}\min _{j}\left\|x_{i}-V_{j}\right\|^{2}$
単純なアルゴリズムであり、広く用いられている。分類をファジィ化したファジィc-平均法やエントロピー法をはじめ、データ構造を発見するさまざまな応用手法が提案されている。上記の最適化問題はNP困難であるが、k-平均法は局所解を求める効率的なヒューリスティックである。k-平均法は混合正規分布に対するEMアルゴリズムの特殊な場合である。

アルゴリズム

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

(一)各データ $x_{i}(i=1,\dotsc ,n)$$x_{i}(i=1,\dotsc ,n)$に対してランダムにクラスタを割り振る。

(二)割り振ったデータをもとに各クラスタの中心 $V_{j}(j=1,\dotsc ,k)$$V_{j}(j=1,\dotsc ,k)$を計算する。計算は通常割り当てられたデータの各要素の算術平均が使用されるが、必須ではない。

(三)各 $x_{i}$$x_{i}$と各 $V_{j}$$V_{j}$との距離を求め、$x_{i}$$x_{i}$ を最も近い中心のクラスタに割り当て直す。

(四)上記の処理で全ての $x_{i}$$x_{i}$のクラスタの割り当てが変化しなかった場合、あるいは変化量が事前に設定した一定の閾値を下回った場合に、収束したと判断して処理を終了する。そうでない場合は新しく割り振られたクラスタから $V_{j}$$V_{j}$を再計算して上記の処理を繰り返す。

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

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

参考文献

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

関連項目

• ベクトル量子化
• 自己組織化写像
• データ・クラスタリング
• k-means++法
• 階層型クラスタリング
• ウォード法