K平均法

k平均法（kへいきんほう、）は、非階層型クラスタリングのアルゴリズム。クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。k-平均法（k-means）、c-平均法（c-means）とも呼ばれる。
何度か再発見されており、まず、Hugo Steinhusが1957年に発表し、Stuart Lloydが1957年に考案し、E.W.Forgyが1965年に発表し、James MacQueenが1967年に発表しk-meansと命名した。
数式で表現すると、下記最適化問題を解くアルゴリズム。本アルゴリズムでは最小値ではなく初期値依存の極小値に収束する。
単純なアルゴリズムであり、広く用いられている。分類をファジィ化したファジィc-平均法やエントロピー法をはじめ、データ構造を発見するさまざまな応用手法が提案されている。上記の最適化問題はNP困難であるが、k-平均法は局所解を求める効率的なヒューリスティックである。k-平均法は混合正規分布に対するEMアルゴリズムの特殊な場合である。
アルゴリズム.
k-平均法は、一般には以下のような流れで実装される。データの数を formula_2、クラスタの数を formula_3 としておく。
結果は、最初のクラスタのランダムな割り振りに大きく依存することが知られており、1回の結果で最良のものが得られるとは限らない。そのため、何度か繰り返して行って最良の結果を選択する手法や、k-means++法のように最初のクラスタ中心点の振り方を工夫する手法などが使用されることがある。
なお、このアルゴリズムではクラスタ数 k は最初に所与のものとして定めるため、最適なクラスタ数を選ぶには他の計算等による考察を用いる必要がある。