高次元空間に出現するハブという現象がおもしろい
高次元では球面集中現象などと呼ばれる面白い現象が知られている。 この帰結のひとつとして、高次元空間においてデータ間の距離分布の分散が小さくなるという現象が次元の呪いとして知られている。
で、比較的最近、次元の呪いの一種として新しい現象が示された。オリジナル論文はこれ。
これがめちゃくちゃ面白い。
一言で言うと、ユークリッドな高次元空間において、他の多くのデータ近傍に現れるデータが出現するという現象。
なのでkNNなどのクラスタリングの性能悪化につながる。
詳しいサイトはこちら。
欲しい情報を見つけるための障害(ハブ)の克服 - Kazuo Hara (原 一夫)
簡単に疑似データ(500個のランダムベクトル)で数値実験してみた。 データの次元は{5,10,50,100}とした。
グラフの見方であるが、横軸は他のデータの10近傍(10でなくてもいい)にカウントされた回数で、縦軸はそういうデータ点がいくつあるかという意味である。距離はコサイン距離である。 ようするに、右に尾を引いていればそれがハブの存在を示唆する。 これは上記のRadovanović+2010の論文で提案されているハブの存在の指標である。
これをみると、5次元ではハブはまったくなく、50次元では明らかにハブが存在していることがわかる。
私からは以上です。