学習・調査で出くわしたクラスタリング手法を一覧にしたく、まとめた。
ここにまとめてある手法が全てではないし、自身の理解のアウトプットのため正確でない部分もあるかと思う。そのため、記事末尾にある参考サイトを別途確認していただいたほうが良いです。
ご指摘あればぜひ。
クラスタリング手法（一部）
| 手法カテゴリ | 手法の型 | データ対象 | 分割の種類 | 手法名 |
|---|---|---|---|---|
| 階層的 | 分割型（分岐型，分枝型） | データ集合 | ハード | Diana法 |
| ソフト | - | |||
| 凝集型 | ハード | ウォード法 | ||
| 群平均法 | ||||
| 最短距離法（単リンク法，単連結法） | ||||
| 再長距離法（完全リンク法，完全連結法） | ||||
| 重心法 | ||||
| 重み付き平均法 | ||||
| メジアン法 | ||||
| ソフト | ||||
| 非階層的(分割最適化) | - | データ集合 | ハード | k-means |
| k-means++ | ||||
| x-means | ||||
| k-medoids | ||||
| 隠れマルコフモデル（復号化問題） | ||||
| スペクトラルクラスタリング | ||||
| DBSCAN | ||||
| ソフト | ソフトk-means | |||
| ファジィC平均法 | ||||
| 自己組織化写像（マップ） | ||||
| pLSI（トピックモデル） | ||||
| NMF | ||||
| - | データストリーム | ハード | BIRCH | |
| CluStream | ||||
| HPStream | ||||
| VFKM(Very Fast K-Means) | ||||
| ソフト | - |
クラスタリング手法の用語
階層的クラスタリング
似ているデータのグループを階層的に構築していく手法の総称。
階層的に構築する方法には2つの方式があって、 分割型（分岐型，分枝型） と 凝集型 と呼ばれる。これらの呼び名も具体的な手法を指しているわけではなく、構築方式を端的に説明しているだけ。
分割型（分岐型，分枝型）
最初にデータ集合全体を1つのクラスタとして、そこから徐々に小さなクラスタへ分割していく方式の総称。TopDown方式のクラスタリングともいえる。あまり使われていない方式。
主な手法としてDiana法がある。
凝集型
最初にデータ1つ1つを1クラスタとして、そこから徐々にクラスタの統合を行って大きなクラスタを構築していく方式の総称。BottomUp方式のクラスタリングともいえる。階層的クラスタリングではこちらの方式の手法がよく使われている。
凝集型に属するクラスタリングの手法は、アルゴリズムがすべて同じで次のようなロジックになる。
- データ数を$ N $としたとき、まず1個のデータだけを含むクラスタを$ N $個つくる
- クラスタを$ C_1, C_2 $とするとき、$ C_1 $と$ C_2 $の似ている具合を$ d(C_1, C_2) $
- $ d(C_1, C_2) $が最も小さい（最も似ている）2つのクラスタを併合する
手法による違いは、データやクラスタの似ている具合の表現方法のみ。
凝集型の主な手法として最短距離法やウォード法などがある。なお、一部手法で外乱に弱い。
- 最短距離法：空間濃縮（一度併合されたクラスタはその後も併合されやすくなる）が起きる
- 最長距離法：空間拡散（一度併合されたクラスタはその後併合されにくくなる）が起きる
非階層的クラスタリング（分割最適化クラスタリング）
データの集合をグループに分割したとき、同じグループに属するデータ同士の似ている具合が最適になるようにデータ分割を行う手法の総称。
クラスタリング対象としてデータ集合をとる手法のほか、データストリームをとる手法もある。データストリームを対象としてとる場合、省資源かつ高速化と忘却特性が必要とされる（らしい）。
データ集合
何らかの事象を計測して記録し、関連のある単位でまとめた情報の集合。
例えば、健康診断の結果一覧とか生徒の成績一覧とか1か月の日次売り上げ記録とか。
このうち、数値を対象にクラスタリングする手法としてk-meansがよく使われる。
データストリーム
データ集合のうち、次のような性質を持つものを指す
- 連続的に与えられ、時間順に整列されている
- その更新頻度や間隔は一定ではない（時系列データとの相違）
- データの性質が急激に変化することがある
- 大量で、潜在的に無限に高速でデータが与えられる
このような性質をもつデータを対象にクラスタリングするには、 いかに資源を効率的に使用しつつ高速に処理か と データの性質の変化に対応すること が必要になるらしい。
勉強し始めたばかりなのでこれ以上はよく知らない。
データ分割の種類：ハード・ソフト
データとクラスタの関係のこと。
ハードクラスタリング
1データはかならず1クラスタにのみ属するようなクラスタリング手法の総称。
例）互いに受け入れることがない場合の「きのこの山」派と「たけのこの里」派。
ソフトクラスタリング
1データが複数のクラスタに属することを許すクラスタリング手法の総称。
”属する／属さない”の判定ではなく、”クラスタがもつ性質への一致度”を割合で表現する。
例）「きのこの山もたけのこの里も好きだけど、どっちかというと４：６でたけのこの里」派
各クラスタリング手法の説明（一部）
神嶌先生のクラスタリング (クラスター分析)で勉強したため、数式をそのまま引用しています。
階層的クラスタリング手法
最短距離法
単リンク法，単連結法とも呼ばれる。
d(C_1, C_2) = \min_{x_1 \in C_1, x_2 \in C_2}d(x_1, x_2)
最長距離法
完全リンク法，完全連結法とも呼ばれる。
d(C_1, C_2) = \max_{x_1 \in C_1, x_2 \in C_2}d(x_1, x_2)
群平均法
2つのクラスタの要素間の距離の総和をクラスタの要素数で割った値（＝距離の平均）をクラスタ間の距離とする。
d(C_1, C_2) = \frac{1}{|C_1||C_2|} \sum_{x_1 \in C_1} \sum_{x_2 \in C_2} d(x_1, x_2)
ウォード法
- 2つのクラスタ$ C_1, C_2 $を併合した$ C_1 \cup C_2 $のバラツキ具合から、$ C_1, C_2 $それぞれのバラツキ具合を減算した値
- 併合後のバラツキが併合前のバラツキと近いほどクラスタとしても近い、という考え
d(C_1, C_2) = E(C_1, C_2) - E(C_1) - E(C_2) \\
E(C_i) = \sum_{x \in C_i}(d(x, c_i))^{2} \\
c_iはクラスタC_iの重心で\sum_{x \in C_i} \frac{x}{|C_i|}
非階層的クラスタリング手法
k-means
- $ k $個の代表点$ c_1, ...... , c_k $をランダムに選択
- $ X $中の全ての対象$ x $を$ c^* = argmin_{c_i}d(x, c_i) $なる代表点をもつクラスタ$ C^* $に割り当て
- もし代表点への割り当てが変化しないならばし終了、そうでなければ各クラスタのセントロイドを代表点にしてステップ2へ
解き方としては評価関数$ \sum_{i=1}^{k} \sum_{x \in c_i} (d(x, c_i))^2 $の最小化問題になる。
k-means++
- k-meansの改良版
- 代表点の選び方を修正している
- $ X $の中からランダムに1つデータを選び、それを代表点$ \mu_1 $とする
- 代表点以外のデータすべてに対して、一番近い代表点との距離$ d(X, \mu) $を計算する
- ステップ2で求めた距離$ d(x, \mu) $から確率分布を用意し、それを使って新しい代表点$ \mu_n $を選択する
- 確率分布$ \frac{d(\mu^{(p)}, M)^2}{\sum_{i}d(x^{(i)}, M)^2} $、$ M $は一番近い代表点
- 代表点の合計数が$ k $個集まればk-meansを実行する、そうでなければステップ2へ戻る
- k-meansに代表点の選び方を追加した手法がk-means++ということ
- ただし、クラスタ数を選ぶのは依然として分析者
参考：k-meansよりもちょっとイケてるk-means++ - Qiita
x-means
- k-means++の改良版
- クラスタ数も自動で推定してくれる手法
- k-means++では、なおもクラスタ数を事前に指定する必要があった
- 手順
- k-means++でクラスタ数=2として、代表点を決める
- ステップ1で決めた代表点を使ってk-meansでクラスタを分割する
- 分割したクラスタに対して、さらにk-meansを適用して分割前と後のBICを計算する
- 分割前のBICよりも分割後のBICの方が大きければ分割を適用する、そうでなければ分割しない
- クラスタサイズが一定より小さくなるか、分割するクラスタが無くなったら終了、そうでなければステップ3へ戻る
- 「再帰的に2-meansを繰り返して、実際に分割するかどうかは情報量で決める」という方法
参考：クラスタ数を自動推定するX-means法を調べてみた - Qiita
k-medoids
- クラスタ内のデータで、その点以外のクラスタ内の点までの距離の総和が最小になる点を代表点として用いるk-means
- k-meansは代表点として重心（セントロイド）を使っていた
- 解き方としては評価関数$ \sum_{i=1}^{k} \sum_{x \in c_i} d(x, m_i) $の最小化問題となる
- 平方和ではない(k-meansは平方和で計算している)
DBSCAN
- 「密集していれば同じクラスタで、そうでなければ違うクラスタか外れ値である」という手法
- 手順
- 点を次の3つのカテゴリに分ける
- コア点：半径$ \epsilon $以内に少なくとも$ minPts $個の隣接点がある
- ボーダー点：半径$ \epsilon $以内に$ minPts $個の隣接点はないけれど、半径$ \epsilon $以内にコア点がある
- 外れ点：コア点でもボーダー点でもない
- 隣接するコア点を同じクラスタとする
- コア点$ C_i $に隣接するボーダー点$ B_i $を$ C_i $と同じクラスタにする
- 点を次の3つのカテゴリに分ける
- 半径$ \epsilon $と隣接点の個数$ minPts $がパラメータで、試行錯誤が必要
- データに精通している人ならわりと決めやすい、らしい…
参考：scikit-learnでDBSCAN(クラスタリング)
参考
- クラスタリング（クラスター分析）
- クラスタリング(k-medoids) ※pdf
- 隠れマルコフモデル入門
-
EMアルゴリズム徹底解説 - Qiita
- ソフトk-means(混合ガウスモデルに対するEMアルゴリズム)
- 子供でもわかる「自己組織化マップ」
-
Somの分かり易い解説
- わかりやすいというより曖昧にわかった気にする表現な感じ
-
減法クラスタリング(Subtractive Clustering)
- ここのSUBTRACTIVE CLUSTERINGという項目
- ググり力が低くて日本語情報が見つけられない
-
subclust#Algorithm - MathWorks
- Algorithmsの項目になんか書いてある
- クラスタリング ※pdf
- ファジィc-means法 - 朱鷺の社Wiki
- Mahout で fuzzy k-means やってみた - ALBERT Engineer Blog
- k-meansよりもちょっとイケてるk-means++ - Qiita
- クラスタ数を自動推定するX-means法を調べてみた - Qiita
- scikit-learnでDBSCAN(クラスタリング)
- サクッと類似度指標のまとめ
- データストリーム
- スペクトラルクラスタリング
- NMF(非負値行列因子分解)
- クラスタリング入門 ※pdf