クラスタリングを勉強してみる（2） partitioning clustering（k-means）

1. 概要

明確なクラスター構造を持たない集合（a flat set of clusters without any explicit structure）を作成する手法を partitioning clustering あるいは flat clustering と言います。

1-1. 目的

• データ集合：
• 分割するクラスター数：
• 目的関数： の最適化

目的関数は、全射（surjection）である必要があり、類似度（similarity measures）あるいは距離（distance metrics）によって、定義されます。

2. k-means

k-meansとは、partitioning clustering の代表的アルゴリズムです。
クラスターを代表するオブジェクト（represented object）としてクラスターの中心（mean or centroid）を使用します。

クラスターの中心を評価する指標として、クラスター内の点とクラスターの中心との残差平方和を算出します。

k-meansの目的は、すべてのクラスターの残差平方和を算出し、その合計を最小にすることです。

2-1. アルゴリズム

1. k個のクラスターの中心の初期値（seed）をランダムに選択する
2. すべてのオブジェクトに対して、平方ユークリッド距離が最も小さい中心を持つクラスターに割り当てる
3. すべてのクラスターの中心を再計算する
4. すべてのオブジェクトに対して、平方ユークリッド距離が最も小さい中心を持つクラスターに再割当てする
5. 3 ~ 4 を繰り返し、どのオブジェクトも再割当てが発生しなければ終了とする

2-2. Pros.

• 比較的効率的である
• クラスタが小さくまとまっていて、互いに離れたところにあれば、うまく機能する

2-3. Cons.

• 初期値の選択など曖昧（non-determinism）である
• 事前にクラスターの分割数を決める必要がある
• ノイズ（noise）や外れ値（outliers）の影響を受けやすい
• 非凸状（non-convex）な形状のクラスターを見出すには適さない

3. その他の主な partitioning clustering

• k-modes
• k-medoids
  • PAM
  • CLARA
  • CLARANS
• prototype-based

4. 参考文献

Introduction to Information Retrieval