K平均法

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

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

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

\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-平均法は、一般には以下のような流れで実装される^[5]^[6]。データの数を $n$ 、クラスタの数を $k$ としておく。

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

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

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

脚注

[脚注の使い方]

^ Steinhaus, H. (1957). “Sur la division des corps matériels en parties” (French). Bull. Acad. Polon. Sci. 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
^ E.W. Forgy (1965). “Cluster analysis of multivariate data: efficiency versus interpretability of classifications”. Biometrics 21: 768–769.
^ MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Vol. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. 2009年4月7日閲覧。
^ Hastie, Trevor、Robert, Tibshirani、Jerome, Friedman『統計的学習の基礎 ―データマイニング・推論・予測―』共立出版、2014年6月25日。ISBN 978-4320123625。
^ “クラスタリング (クラスター分析)”. 2013年8月7日閲覧。
^ “クラスタ生成の統計アルゴリズム　～　階層的手法、k-means法”. 2013年8月7日閲覧。