非階層的クラスタリング

クラスタ分析

クラスタ分析（clustering analysis; クラスタリング）とは、データをいくつかのグループ（クラスタ）に分ける手法の総称である。クラスタ分析は教師なし学習の一種であり、データにラベルが付与されていない場合でもデータを分類できる。つまり、分類問題とは違い、あらかじめデータがどのグループに属するかが分かっていなくても、データをグループに分けることができる。

各事例を のベクトルとしたデータセット を考えられる。このデータセットをクラス に分割することを考える。ここで、 はクラス数で各 は事例の添え字（インデックス）の集合であり以下の条件を満たす。

• （すべての事例がいずれかのクラスに属する）
• （異なるクラスは共通の事例を持たない）

k-means法

クラスタリングの基本的な考え方は、「似たベクトルは同じクラスに、異なるクラスに属するベクトルは遠くに」である。k-means法では各クラス の重心/中心ベクトル（centroid） をもってそのクラス を代表させる。

そして、そのクラスに属しているベクトルと との距離の二乗和を考えると

これは事例の偏差平方和に相当する。したがって、全クラスにわたるこの値の総和 を考える。

この を歪み尺度（distortion measure）やクラスタ内平方和（within-cluster sum of squares; WCSS）と呼ぶ。k-means法では、この を最小化するようにクラス を決定する。

Lloydのアルゴリズム

k-means法で を最小化するクラス分けを見つけるために、Lloydのアルゴリズム（Lloyd's algorithm）がよく用いられる。このアルゴリズムは以下の手順で行われる。

Lloydのアルゴリズムは局所最適解に収束するが、必ずしも大域最適解に収束するとは限らない。そのため、異なる初期化を用いて複数回実行し、最も良い結果を採用することが一般的である。

また の値は事前に決定する必要があるが、適切な の選択は難しい問題である。基本的に を大きくすると は小さくなるが、過学習のリスクも高まる。

ボロノイ図

Lloydのアルゴリズムにおける各事例のクラス割り当ては、各中心ベクトルに基づいてボロノイ図（Voronoi diagram）を形成する。ボロノイ図は、 空間において、ある点が最も近い中心ベクトルに属するような領域を示す図である。各中心ベクトル に対して、その点から最も近い点の集合は以下のように定義される。

この をボロノイ領域（Voronoi region）と呼ぶ。Lloydのアルゴリズムにおいて、各事例 は、その点が属するボロノイ領域に対応するクラスに割り当てられる。

k-means法の性質

k-means法はシンプルで計算効率が高いため、広く利用されている。しかし、いくつかの制約や欠点も存在する。例えば、k-means法は各クラスが球状で同じ大きさを持つことを前提としているため、非球状や異なる大きさのクラスタには適していない。また、外れ値に敏感であり、外れ値がクラスタの中心に大きな影響を与える可能性がある。さらに、k-means法は初期化に依存するため、異なる初期化により異なる結果、つまり、 の最小化が異なる特殊解に収束する可能性がある。