クラスタリング結果の評価指標【実装編】 - 初心者データサイエンティストの備忘録

クラスタリング結果を評価する方法を、過去２回の記事に残してきた。また、近接性を評価する指標については、過去文献から欲しいものを見つけることができなかったので、自分自身で考えてみた。
今回の記事では、考案した指標で実際のクラスタリング結果を評価してみようと思う。

過去の記事はこちら。 aisinkakura-datascientist.hatenablog.com aisinkakura-datascientist.hatenablog.com

４種類の凝集型クラスタリングとその実装

ここでは、評価対象のクラスタリング手法について説明する。

凝集型クラスタリングとは、カステラ本によると

凝集型クラスタリング法は、各観測がそれぞれ一つのクラスタを構成するところから始める。N-1回の各ステップにおいて、最も近い（最も非類似度が小さい）二つのクラスタを一つのクラスタに併合し、一つ上の階層ではクラスタが一つ少なくなる。

である。要するに、各観測を併合していって最終的には一つのクラスタにしますよーというのが凝集型クラスタリングである。
この併合する際にポイントなってくるのが、非類似度である。各クラスタを併合して、一階層上のクラスタを作る基準を何にするかで、クラスタリング結果が変わってくる。この基準に応じて、単連結法、群平均法、完全連結法、ウォード法といった手法が存在する。

各手法の詳細については、下記のQiitaの記事が参考になった。（単連結法は単純連結法、群平均法は重心法に読みかえていただきたい） qiita.com

実装

単連結法、群平均法、完全連結法、ウォード法を実装し、かつそれを評価する指標を実装した。 github.com

上記git内の「評価」章内の「近接性の評価」が今回考案した指標を実装した箇所である。前回記事で書いた指標が実装されている。

※前回記事で書いた近接性の評価に用いる指標のおさらい
クラスタリングをした結果現れたクラスの一つを $G$ とする。また、データ $i$ と $i ^ \prime$ 間の距離を $d _ {ii^ \prime}$ とする。このとき、 $d$ を閾値として、

$N_{G(i)} = \#\{i^\prime \in G \ | d_{ii^\prime} \leq d \} \\ N_{\bar{G}(i)} = \#\{i^\prime \notin G \ | d_{ii^\prime} \leq d \}$

とする。また、

$\varepsilon (i) = \frac{N_{\bar{G}(i)}}{N_{G(i)}+N_{\bar{G}(i)}}$

と定義する。このとき、近接性を表す指標を

$\frac{1}{N}\sum _ {i \in G}\varepsilon (i)$

と定義する。

シミュレーション結果

下記の条件でシミュレーションを行った。

目的：考案した指標の振る舞いを調べること
データ：SchoolScore, 'https://raw.githubusercontent.com/maskot1977/ipython_notebook/master/toydata/SchoolScore.txt'からDLした
シミュレーション内容：単連結法、群平均法、完全連結法、ウォード法を用いた階層的クラスタリングを行い、考案指標の振る舞いを調べる

図１は、シミュレーションの結果を表したものである。図１は、横軸を併合の回数、縦軸を考案した指標の値としたものである。ここで、併合の回数とは、デンドログラムにおける下からの階層の数と言い換えることもできる。つまり、クラスタを併合するたびに現れるクラスタリング結果に対して、考案した指標を計算してプロットしたものが図１である。

f:id:aisinkakura_datascientist:20220410105122j:plain:w300 — 図１：近接性指標の振る舞い

図１において、単連結、群平均、完全連結の折れ線を見ると、指標の大きさについて、おおむね単連結＜群平均＜完全連結となっていることが分かる。
考案した指標は、値が小さいと近接、値が大きいと近接ではないクラスタリング結果であることを表す。したがって、図１は単連結の方が完全連結よりも近接なクラスタを生成しやすいことを表している。このことは、カステラ本p603にも記載がある。