階層型クラスタリング（高校生向け）

こんな場面を想像してみよう #

部活の合宿で、30 人を住んでいる場所が近い人同士の班に分けたいとします。ただし「何班にするか」はまだ決まっていません。あなたならどうしますか。

自然なやり方はこうでしょう。まずいちばん家が近い 2 人をペアにする。次に近い 2 人（またはペアと 1 人）をくっつける。これを繰り返すと小さなかたまりが大きなかたまりに育ち、最後は全員が 1 つになります。くっつけた順番を木の枝のように描いておけば、「3 班にしたい」と言われたとき枝を 3 本に切るだけで済みます。

k-means が最初にグループ数 \(k\) を決めるのに対して、こちらはくっつける過程そのものを記録しておくのが特徴です。

上の図がデンドログラムです。横軸に 50 個の点（サンプル）が並び、縦軸は「くっついたときの距離」です。下のほうでは高さ 5 以下で細かくつながり、近い点同士が早い段階でまとまったことが分かります。右側の 2 つのかたまりは高さ約 40 で 1 つになり、最後に左のかたまりと高さ約 70 でつながっています。

樹形図はどう育つ？ #

図は下から上へ育ちます。まず、全員を 1 人ずつのグループにします。横軸に並んだ 50 個の点が、それぞれ独立したグループで、図の最下段にあたります。次に、全ペアの距離を計算します。いちばん近い 2 つを見つけてくっつけます。図では、その 2 本の縦線が低い位置の横棒で結ばれ、横棒の高さがそのときの距離です。

ここで、かたまり同士の距離を決めるルールが要ります。いちばん近い点同士で測る（単連結）、いちばん遠い点同士（完全連結）、全ペアの平均（平均連結）、くっつけたときにグループ内のばらつきがどれだけ増えるか（ウォード法）などがあり、上の図はウォード法です。ルールを決めたら、1 つになるまで「近い 2 つをくっつける」を繰り返します。距離が小さい順にくっつくので横棒は下から上へ積み上がり、似たもの同士は低い位置で、遠いもの同士は高い位置でつながって、最後は 1 本の木になります。

最後に、樹形図を横に切ってグループを読みます。好きな高さで水平線を引き、その線と交わる縦線の本数がグループ数です。上の図なら、高さ 50 で切れば 2 グループ、高さ 20 で切れば 3 グループになります。

動かして見てみよう #

下の図で「再生」を押すと、説明した手順が 1 つずつ進みます。手順ごとの説明は図の下に出ます。

気をつけたいこと #

最初の注意点は、切る高さで答えが変わることです（高さ 50 なら 2 班、20 なら 3 班）。「どこで切るか」は人に任されており、高さが大きく跳ぶところ（上の図なら 5 から 40 への跳び）で切るのが目安ですが、目的によって正解は変わります。二つ目は、4 つの測り方のうち単連結は鎖になりやすいことです。いちばん近い点同士で距離を測ると、数珠つなぎに並んだ点は端から端まで 1 グループにつながってしまうので、丸いかたまりを見つけたいならウォード法や完全連結が向いています。三つ目は、一度くっつけたら戻れないことです（k-means は繰り返しの中で所属を変えられます）。階層型は 1 回目の合体を後から取り消しません。データが何万件もあると、全ペアの距離の計算時間も問題になります。

やってみよう #

最初の課題は、方眼紙に点を 8 個描き、定規で全ペアの距離を測って表にすることです。いちばん近いペアから順にくっつけ、横棒の高さを距離にしてデンドログラムを手で描いてみましょう。二つ目は、1 つ目で描いた図を高さ 2 か所で切り、それぞれ何グループになるか、どの点が同じグループになるかを確かめることです。三つ目は、点を一直線に等間隔で 10 個並べたデータを単連結でくっつけるとどうなるか予想することです。どの高さで切っても「自然なグループ」が見つからない理由を考えてみましょう。

つぎに読む #

リンケージ（グループ間距離）の数式と、scipy / AgglomerativeClustering でデンドログラムを描くコードは 標準版の階層型クラスタリング で扱っています。グループ数を先に決めるもう一つの代表的な方法は k-means（高校生向け） へ。「距離」を角度で測る別の考え方は コサイン類似度（高校生向け） で紹介しています。