クラスタリング

似たデータをまとめる。 正解ラベルは使わない。

k-means#

最も基本的な手法。

1. $k$ 個の中心を初期化する
2. 各点を最も近い中心に割り当てる
3. 各クラスタの重心を新しい中心にする
4. 収束するまで 2〜3 を繰り返す

目的関数は明確。

$$\min \sum _i\Vert x_i-{\mu }_{c_i}{\Vert }^2$$

ただしこれは非凸で、初期値によって結果が変わる。 k-means++ は初期中心を離れて選ぶことでこれを緩和する。

前提#

k-means は暗黙に次を仮定している。

• クラスタが球状（等方的）
• クラスタの大きさが同程度
• ユークリッド距離が意味を持つ

細長いクラスタや密度の違うクラスタでは破綻する。 そのときは混合ガウス（共分散を持つ）、 DBSCAN（密度ベース）、スペクトラルクラスタリングを検討する。

$k$ の決め方#

クラスタ数は事前に決める必要があるが、正解は無い。

• エルボー法 — 損失の減り方が緩やかになる点
• シルエット係数 — クラスタ内の凝集とクラスタ間の分離
• ギャップ統計量

いずれも目安にすぎず、 最終的には解釈可能性で判断することになる。

参考文献#

• Trevor Hastie, Robert Tibshirani, Jerome Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009.（全文公開） https://hastie.su.domains/ElemStatLearn/
• Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. https://www.microsoft.com/en-us/research/publication/pattern-recognition-machine-learning/
• David Arthur, Sergei Vassilvitskii. k-means++: the advantages of careful seeding. SODA, 2007. https://theory.stanford.edu/~sergei/papers/kMeansPP-soda.pdf