階層型クラスタリングについてわかりやすい解説を聞いたので頭の中にあるものを書き出してみます。
(せっかく聞いたシャープな解説が台無しになってしまっているかと思いますが…)
本当はもっとアクティブなアウトプット方法があれば良いのですが、今のところはブログしかないのと、
WordPressのエントリという単位が、アウトプットの量として個人的に丁度良いなと思いますので。
初学なので解釈の誤りとか検討不足があるかと思いますが、本日も書いていきます！
試しに実行してみるためのデータを作る面倒さの洗礼を受けまして、
実際に試すのは別記事になります。
階層型クラスタリング
小さいクラスタを大きいクラスタで内包する様が木構造(階層構造)になることから、
階層型クラスタリング、という名前が付いているんでしょうかね。
最初にk個のクラスタに分割する！ みたいな問題であればk-means法、
何個のクラスタに分割すべきかはやってみて考えるのであれば、階層型クラスタリング。
木の深さとクラスタ数を対応させるところに見事な美しさを感じます。
クラスタ間距離として以下のWard距離を使うことで空間拡張性と非単調性に優れた結果を得られやすく、
よく傾向が分かっていないデータに対して一発目に適用すべき方法の様子。
\begin{eqnarray}
d_{ward} (C,C’) = \sum_{i\in C\cup C’} || x_i – \bar{x}_{C\cup C’}||^2 – \left( \sum_{i \in C} ||x_i-\bar{x}_C||^2 + \sum_{i\in C’}||x_i – \bar{x}_{C’}||^2 \right)
\end{eqnarray}
階層型クラスタリングのアルゴリズム
以下の通り。最初、全てのデータポイントをクラスタとみなすところからスタートする。
クラスタとクラスタを併合してより大きいクラスタを作る処理であって、
繰り返しを止めなければ最終的に一つのクラスタまで成長する。
つまり、どこかで止めることで、その時点のクラスタ分割を得ることができる。
- 全データポイントそれぞれをクラスタとする
- 全てのデータポイントが初期クラスタ以外に含まれるまで以下の計算を繰り返す
- 各クラスタ間の距離を計算する。
- 最もクラスタ間距離が小さいクラスタを併合する。
クラスタを成長させる際に、うまい具合に併合相手を選ばないとよくない。
全体としてクラスタがバラけて欲しいのだけれども、クラスタが隣のクラスタを併合した結果、
次の併合先としてその隣のクラスタが対象となってしまうかもしれない。
そうすると、単調に端っこから順番に成長することになり、
「大きなクラスタ」と「その他の小さなクラスタ」みたいになる。
何らかの距離に基づいてクラスタとクラスタを併合するのだけれども、
クラスタを併合した結果、併合後のクラスタと別のクラスタの距離が、
より短くなってしまう、というケースも起こってしまう。
クラスタ内のデータポイント間の距離、とか、クラスタの重心間の距離とかでは
上記の問題が起こりやすい。
先に距離があって次に併合を考えるのではなく、併合前後の条件を使って距離を作ることで、
上記の問題が起こりにくくなる。その一つがWard距離。
Ward距離
データポイント間の距離はユークリッド距離を使うとして、クラスタ間の距離をどう決めるのか？
データポイントをクラスタ\(C\)とクラスタ\(C’\)に分けるとする。分ける前は\(C\cup C’\)。
(逆? クラスタ\(C\)とクラスタ\(C’\)を併合してクラスタ\(C\cup C’\)を作る)。
クラスタ\(C\)とクラスタ\(C’\)の距離\(d_{ward}(C,C’)\)を以下のように定義する。
\begin{eqnarray}
d_{ward} (C,C’) = \sum_{i\in C\cup C’} || x_i – \bar{x}_{C\cup C’}||^2 – \left( \sum_{i \in C} ||x_i-\bar{x}_C||^2 + \sum_{i\in C’}||x_i – \bar{x}_{C’}||^2 \right)
\end{eqnarray}
併合後のクラスタ\(C\cup C’\)における重心との距離の2乗和\( \sum_{i\in C\cup C’} || x_i – \bar{x}_{C\cup C’}||^2\)から、
併合前のクラスタ\(C\)における重心との距離の2乗和\(\sum_{i \in C} ||x_i-\bar{x}_C||^2\)、
\(C’\)における重心との距離の2乗和\(\sum_{i\in C’}||x_i – \bar{x}_{C’}||^2\)を引いたもの。
当たり前だけれども、大きいクラスタよりも小さいクラスタの方が凝集度が小さい。
つまり、併合前のクラスタ\(C\)、\(C’\)を併合してクラスタ\(C\cup C’\)を作るとなると、
\(C\cup C’\)の凝集度よりも、\(C\)、\(C’\)の凝集度の方が必ず小さい。
\(C\)の凝集度と\(C’\)の凝集度の和よりも、\(C\cup C’\)の凝集度の方が大きくなることがポイント。
要するに\(C\cup C’\)を\(C\)、\(C’\)に分割することは、全体の凝集度が小さくなるような操作を行うということ。
無数にある分割の仕方の中から、凝集度の総和が小さくなるような「マシな分割」を決めたい！
\(\sum_{i \in C} ||x_i-\bar{x}_C||^2+\sum_{i\in C’}||x_i – \bar{x}_{C’}||^2\)よりも\( \sum_{i\in C\cup C’} || x_i – \bar{x}_{C\cup C’}||^2\)の方が大きいから、
\(d_{ward}\)は正の値となる。\(d_{ward}\)が大きければそれはマシな分割。
そもそも、データ達が何をもってクラスタを形成しているのかって考えるとかなり微妙で、
人間が解釈するための合理的な根拠を作り出す手段でしかないことがわかった。
データポイント間の”距離”を何らかの方法で定義し、”距離が近しい塊をクラスタと言う”
という話であるとすれば、確かに合理的なのだろうけども。
モヤモヤしているのは、k個のクラスタ集合とk+1個のクラスタ集合を比較したときに、
前者と後者で異なるクラスタに属するデータポイントが発生するところ。
クラスタリングとは単に境界を引く処理なのであって、
それにどういう意味を付けるかは目的次第なのだろうと改めて認識した次第。
そもそも、これらは単なる道具でしかないので、他の手段も同じく
出力結果にどう意味付けするのかは目的次第なんだろうなと。
最初から何個のクラスタに分割すべきか分かっているときはk-means法を使えば良さそう。
今回は、そもそも何個に分割すべきか分かっていないときに使う手法。