初心者データサイエンティストの備忘録

調べたことは全部ここに書いて自分の辞書を作る

クラスタリング結果の評価指標【実装編】

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

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

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

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

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

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

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

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

実装

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

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

※前回記事で書いた近接性の評価に用いる指標のおさらい
クラスタリングをした結果現れたクラスの一つをGとする。また、データii ^ \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)

と定義する。

シミュレーション結果

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

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

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

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

完全連結法では、直径(14.44)が小さいコンパクトなクラスタを生成しやすい。しかし、「近接」性に反するクラスタを生成することがある。

まとめ

今回の記事は、近接性を評価する指標を考案し、その振る舞いをシミュレーションによって確認した。 また、その振る舞いはカステラ本記載の性質(単連結の方が完全連結よりも近接になりやすい)と一致していることも、今回のシミュレーションにおいて確認することができた。

参考文献

  • カステラ本