K平均法のソースを表示

{{小文字}}
{{Expand English|k-means clustering|date=2024年5月}}
[[File:K-means_convergence.gif|right|thumb|k平均法の収束]]
{{Machine learning bar}}
'''k平均法'''（kへいきんほう、{{lang-en-short|k-means clustering}}）は、非階層型[[データ・クラスタリング|クラスタリング]]の[[アルゴリズム]]。クラスタの平均を用い、与えられたクラスタ数k個に分類することから、MacQueen がこのように命名した。'''k-平均法'''（k-means）、'''c-平均法'''（c-means）とも呼ばれる。

何度か再発見されており、まず、[[フーゴ・シュタインハウス|Hugo Steinhus]]が[[1957年]]に発表し<ref>{{cite journal
 |first=H. 
 |last=Steinhaus 
 |authorlink=Hugo Steinhaus
 |title=Sur la division des corps matériels en parties
 |journal=Bull. Acad. Polon. Sci.
 |volume=4 
 |issue=12 
 |pages=801&ndash;804
 |year=1957
 |mr=0090073
 |zbl=0079.16403
 |language=French
}}</ref>、Stuart Lloydが1957年に考案し、E.W.Forgyが1965年に発表し<ref>{{Cite journal
 |author=E.W. Forgy
 |title=Cluster analysis of multivariate data: efficiency versus interpretability of classifications
 |journal=Biometrics
 |volume=21
 |pages=768–769
 |year=1965}}</ref>、James MacQueenが[[1967年]]に発表しk-meansと命名した<ref>{{cite conference
 |first=J. B. 
 |last=MacQueen
 |year=1967
 |title=Some Methods for classification and Analysis of Multivariate Observations
 |url=http://projecteuclid.org/euclid.bsmsp/1200512992 
 |accessdate=2009-04-07
 |conference=Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability
 |publisher=University of California Press
 |volume=1 
 |pages=281&ndash;297
 |mr=0214227
 |zbl=0214.46201
}}</ref>。

数式で表現すると、下記[[最適化問題]]を解くアルゴリズム<ref>{{Cite book
|和書 
|last1= Hastie
|first1= Trevor
|last2= Robert
|first2= Tibshirani
|last3= Jerome
|first3= Friedman
|date= 2014-06-25
|title= 統計的学習の基礎 ―データマイニング・推論・予測―
|publisher= 共立出版
|isbn= 978-4320123625
}}
</ref>。本アルゴリズムでは最小値ではなく初期値依存の極小値に収束する。
:<math>\operatorname{arg\,min}_{V_1, \dotsc, V_k} \sum_{i=1}^n \min_j \left\| x_i - V_j \right\|^2</math>

単純なアルゴリズムであり、広く用いられている。分類を[[ファジィ]]化した[[ファジィc-平均法]]や[[エントロピー法]]をはじめ、[[データ構造]]を発見するさまざまな応用手法が提案されている。上記の最適化問題は[[NP困難]]であるが、k-平均法は局所解を求める効率的な[[ヒューリスティック]]である。k-平均法は混合正規分布に対するEMアルゴリズムの特殊な場合である。

== アルゴリズム ==
k-平均法は、一般には以下のような流れで実装される<ref>{{Cite web|和書|url=http://www.kamishima.net/jp/clustering/ |title=クラスタリング (クラスター分析) |accessdate=2013-08-07}}</ref><ref>{{Cite web|和書|url=http://www.antecanis.com/texts/group_04/ |title=クラスタ生成の統計アルゴリズム　～　階層的手法、k-means法 |accessdate=2013-08-07}}</ref>。データの数を <math>n</math>、クラスタの数を <math>k</math> としておく。

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

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

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

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

== 関連項目 ==
* [[ベクトル量子化]]
* [[自己組織化写像]]
* [[データ・クラスタリング]]
* [[k-means++法]]
* [[階層型クラスタリング]]
* [[ウォード法]]

{{DEFAULTSORT:けいへいきんほう}}
[[Category:クラスター分析アルゴリズム]]
[[Category:統計学]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事|Kけいへいきんほう]]