k平均法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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 ,\, \cdots ,\, V_k} \sum_{i=1}^n \min_j \left\| x_i - V_j \right\|^2

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

アルゴリズム[編集]

k-平均法は、一般には以下のような流れで実装される[5][6]。データの数を 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回の結果で最良のものが得られるとは限らない。そのため、何度か繰り返して行って最良の結果を選択する手法や、k-means++法のように最初のクラスタ中心点の振り方を工夫する手法などが使用されることがある。

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

脚注[編集]

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

参考文献[編集]

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

関連項目[編集]