K平均クラスタリング

K平均クラスタリングは、クラスター中心までの二乗距離の合計を最小化することにより、観測値を固定数のクラスターに分割する手法である。

Definition

K平均クラスタリングは、所定の数のクラスター中心を配置し、各観測値を最も近い中心点に割り当てることにより、観測値から割り当てられた中心点までの総二乗ユークリッド距離を最小化する分割手法である。

Scope

このトピックでは、クラスター内平方和の目的、最も近い中心点への点の割り当てと中心点の再計算を交互に行う反復的な割り当てと更新のアルゴリズム、初期化への依存性とそれに伴う局所最適解、クラスター数の選択、およびこの手法の仮定と限界について説明する。

Core questions

• クラスター内の分散を最小化するために、観測値をどのように分割できるか？
• なぜアルゴリズムは局所最適解にしか収束せず、これはどのように緩和されるのか？
• クラスター数はどのように選択されるのか？
• この手法は暗黙的にどのようなクラスター形状とスケールを仮定しているのか？

Key theories

クラスター内平方和の最小化

K平均法は、点からクラスター中心までの総二乗距離を最小化する分割と中心点の集合を探索する。これは、交互の割り当てと更新の反復によって基準が単調に減少する目的である。

局所最適解への感度

目的関数が非凸であるため、アルゴリズムは初期中心点に依存する局所最小値に収束する。このため、複数回の再実行と慎重なシード設定が推奨される。

Clinical relevance

K平均法は、大規模データセットを分割するための高速でスケーラブルなデフォルト手法であり、ベクトル量子化、画像の色数削減、顧客セグメンテーション、およびより複雑なモデルの初期化に利用されている。

History

中心点に基づく分割のアイデアは、Lloydの以前の量子化アルゴリズムに基づいて、1967年にMacQueenによって形式化され、k-meansと名付けられた。その簡潔さと速度により、最も広く使用されるクラスタリング手法の1つとなった。

Debates

k-meansの暗黙の仮定

二乗ユークリッド距離の最小化は、ほぼ球形で同程度のサイズのクラスターを好むため、クラスターが細長い、サイズが不均一、または非凸である場合、k-meansは誤解を招く可能性があり、モデルベースまたは密度ベースの代替手法が推奨される。

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

k-meansは実行ごとに異なる結果を出すのはなぜですか？

その目的関数は非凸であるため、アルゴリズムはランダムな初期中心点に依存する局所最適解に収束する。複数回実行し、最良の結果を保持することが一般的な慣行である。

クラスター数kはどのように選択すればよいですか？

一般的なヒューリスティックには、クラスター内平方和のエルボー法、ギャップ統計量、平均シルエット幅などがあるが、決定的なものはなく、多くの場合、ドメイン知識が選択を導く。