絡まった2つのリングは、k-meansには永遠に分けられない。「近さ」ではなく「つながり」で見る
鎖のように絡まった2つのリング。人間がこの3Dデータを見たら、0.1秒で「輪っかが2つ」と答える。では、クラスタリングアルゴリズムにはそれが分かるのだろうか。
このデータが意地悪なのは、2つのリングの重心がほぼ同じ場所にあることだ。リングAのある点にとって、一番近い点は自分のリングの隣人だが、「クラスタの中心」で考え始めた瞬間、2つのリングは区別できなくなる。距離で見るか、つながりで見るか——クラスタリングの2大流派が真っ二つに分かれるはずのデータで、4手法を競わせてみた。
結果: 流派がそのまま結果に出た
k-means・GMM(混合ガウス)・スペクトラルクラスタリング・DBSCANに、それぞれ「2クラスタに分けて」と頼んだ(DBSCANだけはクラスタ数を指定できないので密度パラメータで調整)。正解のリング所属との一致度をARI(調整ランド指数、1が完璧・0がでたらめ)で測る。
- k-means: ARI 0.08。 予想通りの惨敗だが、壊れ方が面白い。空間を真っ二つに切る平面で分けるので、両方のリングが半分ずつ赤と青に塗られる。k-meansにとってクラスタとは「中心からの距離が近い点の集合」であり、リングという形は原理的に表現できない
- GMM: ARI 0.89。 意外な健闘。2つのリングは別々の平面に乗っているので、それぞれを薄く潰れた楕円ガウスで近似すると案外当たる。間違えるのはリングが交差するあたりだけ
- スペクトラル: ARI 1.00。DBSCAN: ARI 1.00。 どちらも完璧
「近さ」派のk-meansが原理的に敗北し、「つながり」派の2つが満点。教科書通りの結果が、教科書より鮮明に出た。
なぜスペクトラルには「輪っか」が見えるのか
スペクトラルクラスタリングの中身は、(1) 各点を近傍k点とつないだグラフを作る、(2) そのグラフラプラシアンの固有ベクトルで点を並べ直す、(3) その空間でk-meansする——という3段構えだ。魔法の部分は(2)にある。ラプラシアンを自分で組んで固有分解してみた。
ノイズが小さいとき、2つのリングのグラフは完全に分断されていて(リング間エッジ0本)、第2固有ベクトル(Fiedlerベクトル)は所属表そのものになる(上段)。面白いのはノイズを上げてリング間に42本の「誤配線」ができた場合で(下段)、固有ベクトルは連続値になりながらも、符号を見ればほぼ完璧にリングを分けている。42本の弱いつながりと、リング内部の何千本もの強いつながりを、固有ベクトルはちゃんと重み付けして「切るならここ」を見つけてくる。λ₂=0.0337という小さな固有値が「ほぼ切れているが、完全には切れていない」というグラフの状態をそのまま数値で語っているのも美しい。
壊し方を変えると、壊れ方の性格が出る
ではノイズをさらに増やしていくと、どの手法がいつ壊れるのか。ノイズの標準偏差を0.02から0.30まで動かして測った(3シード平均)。
壊れ方に、はっきり性格が出た。
- つながり派(スペクトラル・DBSCAN)は「完璧 → 崖」。 リング同士が触れるまでは満点を守り続け、触れた瞬間に崩落する。DBSCANは0.14→0.16の間でARIが0.97から0.31へ落ち、0.20以降はすべてが1つの塊に融合してほぼ0
- 距離派(GMM)は「最初からじわじわ」。 0.96から0.39まで、崖のない一定ペースの右肩下がり
- k-meansは「常に底辺で安定」。 ある意味一番ロバストだが、そもそも一度も正解していない
もう1つ、正直に書いておくと、スペクトラルはノイズ0.04という低ノイズ帯で一度ARI 0.67に落ちている(3シード中1つで失敗)。まばらな部分でグラフが偶発的に分断・誤接続されると、条件が簡単でも壊れることがある。「つながり」で見る手法は、つながりの検出そのもの(kNNグラフの引き方)が急所なのだ。
手を動かして意外だったこと
一番の収穫は、「壊れるかどうか」より**「どう壊れるか」に手法の性格が出る**と分かったことだ。つながり派は全か無か。前提が守られている限り完璧で、破られた瞬間に一気に崩れる。距離派は最初から粗いが、条件が悪化しても急変はしない。どちらが良いかは、静かに劣化してほしいか、壊れたら派手に壊れて気づかせてほしいかという、運用の好みの問題でもある。
GMMの健闘(0.89)も予想外だった。「距離ベースはリングを分けられない」と一括りにしていたが、共分散を持つGMMは「潰れた楕円」を表現できるぶん、k-meansとは別物の柔軟さがある。流派のレッテルで手法をまとめて評価するのは雑すぎた、という反省でもある。
人間関係でも、「物理的に近くにいる人たち」と「つながっている人たち」は別のグループ分けだ。オフィスの席が隣なのは同じクラスタに見えるが、実際のつながりのグラフを辿れば別の輪に属していたりする。そして、輪と輪が触れるほど密になったとき、どこからが自分の輪なのかは、急に分からなくなる。
まとめ
- 鎖状に絡まった2つのリング(重心がほぼ同じ)を4手法でクラスタリング: k-means 0.08 / GMM 0.89 / スペクトラル 1.00 / DBSCAN 1.00 (ARI)
- k-meansは空間を平面で切るため、リングという形を原理的に表現できず、両リングを半分ずつに塗り分けた
- スペクトラルの中身をグラフラプラシアンの固有分解で確認: グラフ分断時はFiedlerベクトルが所属表そのものになり、リング間に42本の誤配線があっても符号でほぼ完璧に分離する
- ノイズ耐性は壊れ方に性格が出る: つながり派は「完璧→崖」(スペクトラル0.16まで満点→0.20で0.55、DBSCANは0.16で崖)、距離派GMMは「なだらかに劣化」(0.96→0.39)
- スペクトラルは低ノイズでも偶発的なグラフ誤接続で稀に失敗する(0.04で3シード中1回)——「つながり」手法の急所はつながりの検出自体にある
