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]。本アルゴリズムでは最小値ではなく初期値依存の極小値に収束する。

*
⁡
a
r
g
m
i
n
V
1
,
⋯
,
V
k
∑
i
=
1
n
min
j
∥
x
i
−
V
j
∥
2
operatorname*{arg,min}_{V_1 ,, cdots ,, V_k} sum_{i=1}^n min_j left| x_i - V_j ight|^2
単純なアルゴリズムであり、広く用いられている。分類をファジィ化したファジィc-平均法やエントロピー法をはじめ、データ構造を発見するさまざまな応用手法が提案されている。

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

各データ
x
i
(
i
=
1
⋯
n
)
x_i(i=1cdots n) に対してランダムにクラスタを割り振る。
割り振ったデータをもとに各クラスタの中心
V
j
(
j
=
1
⋯
k
)
V_j(j=1cdots 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 は最初に所与のものとして定めるため、最適なクラスタ数を選ぶには他の計算等による考察を用いる必要がある。

^ 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”. 1. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. pp. 281–297 2009年4月7日閲覧。
^ Hastie, Trevor、Robert, Tibshirani、Jerome, Friedman 『統計的学習の基礎 ―データマイニング・推論・予測―』 共立出版、2014年6月25日。ISBN 978-4320123625。
^ “クラスタリング (クラスター分析)”. 2013年8月7日閲覧。
^ “クラスタ生成の統計アルゴリズム　～　階層的手法、k-means法”. 2013年8月7日閲覧。

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

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

人と人あるいは人とAIの間において、より質の高い意思疎通を可能とする情報通信技術の実現に示唆を与えるもの。理系が我々の色彩だ。認識のカテゴリーを分割していく。もちろんモノトーンな文字列へと変えることも必要なのだ。

ロット
同じ条件のもとに製造する製品の、生産・出荷の最小単位。

とりあえずリリースすることで、学習データが大量に集まってくる。そして性能を向上させる。アプリには副作用なさげだしね。

不思議に感じる瞬間が時々ある
僕が今ここにいるというこの事実が
僕に特別な力があるとはとても思えないし
ひとりきりではできなかったことだよ

突然世界が真っ暗闇になったように見えた
でも少しずつ目が慣れて明るくなってきた
今まであまりに強すぎる光に照らされてたから
目がくらんで気付けなかっただけだった

大切な「イマ」はどんどん変わっていく
忘れてく思い出もたくさんあるけど
終わりの時間は確かに近づいて来てる
だけど今夜だけは「イマ」が愛しく思えそうなんだ

自分はなんにもできないと思っていた
でもそれはなんでもできるって事みたいで
望んだ人にはなれないのかもしれないけれども
僕は僕になることだけはできるんだ

大切な「イマ」はどんどん変わっていく
忘れてく思い出もたくさんあるけど
終わりの時間は確かに近づいて来てる
だけど今夜だけは「イマ」が愛しく思えそうなんだ

今の自分がどうしよもなくキライで
ここまでの道が灰色に見えてたとしても
この長い道が君へと続いていたなら
また一歩前に進む事ができそうな気がするんだ