Isomap

最終更新 2020-04-08 読了時間 2 分

まとめ

Isomap は、点同士の距離を直線距離ではなく「データの面に沿って歩いた距離」（測地距離）で測り、その距離をできるだけ保つように低次元へ並べ直す次元削減です。計算は 3 段階で、まず各点を n_neighbors 個の近い点とつないだグラフを作り、次にグラフ上の最短経路の長さを全ペアについて求め、最後にその距離行列を多次元尺度法（MDS）に渡して座標を得ます。巻いた紙のような Swiss roll データでは、直線距離で近い「紙の表と裏」が測地距離では遠くなるので、PCA では潰れてしまう巻きがきれいに広げられます。結果を左右するのは n_neighbors で、小さすぎるとグラフが分断され、大きすぎると測地距離が直線距離に近づいて PCA と同じ図になります。

主成分分析（PCA）の概念を先に学ぶと理解がスムーズです

直感 #

くるくる巻いた 1 枚の紙（Swiss roll）を思い浮かべてください。紙の上の 2 点は、巻きの内側と外側で重なっていれば直線距離は 1 cm でも、紙に沿って歩くと 20 cm 離れています。PCA は直線距離しか見ないので、巻いた紙を真上から潰した図になり、本来遠い点が重なります。Isomap は「紙に沿って歩いた距離」を使います。各点を n_neighbors=10 個の近所の点とだけ線でつなぐと、線は紙の面に沿って張られるので、グラフ上の最短経路の長さが紙に沿った距離の近似になります。その距離を保つように 2 次元の平面に並べ直すと、巻いた紙を広げたような図が得られます。

詳細な解説 #

Isomap はデータをグラフで結び、測地線距離を近似した上で多次元尺度法（MDS）を適用することで、非線形多様体を低次元に展開する手法です。

1. 手順 #

Isomap の計算は 3 段階です。まず、各点を近い n_neighbors 個の点とつなぐ k 近傍グラフ（または距離 \(\varepsilon\) 以内の点をつなぐ \(\varepsilon\) 近傍グラフ）を構築します。次に、グラフ上で全ペアの最短経路距離（測地距離）を Dijkstra 法などで計算します。最後に、その距離行列を MDS に渡し、距離をできるだけ保つ 2 次元の座標を得ます。これで巻いた Swiss roll が平面に広がります。

高次元データ n_neighbors 個の近傍をつないだグラフを作るグラフ上の最短経路で全ペアの測地距離を計算距離行列を MDS に渡す測地距離を保つ 2 次元座標

2. Python 実装 #

次のコードは make_swiss_roll で巻いた 3 次元データ 1500 点を作り、Isomap(n_neighbors=10, n_components=2) で平面に広げます。左に元の巻き（\(x\) と \(z\) の断面）、右に埋め込み結果を、巻きに沿った位置を色にして並べます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_swiss_roll
from sklearn.manifold import Isomap

X, color = make_swiss_roll(n_samples=1500, noise=0.05, random_state=0)
iso = Isomap(n_neighbors=10, n_components=2)
emb = iso.fit_transform(X)

fig, axes = plt.subplots(1, 2, figsize=(12, 5))
axes[0].scatter(X[:, 0], X[:, 2], c=color, cmap="Spectral", s=5)
axes[0].set_title("元の Swiss roll")
axes[1].scatter(emb[:, 0], emb[:, 1], c=color, cmap="Spectral", s=5)
axes[1].set_title("Isomap 埋め込み")
for ax in axes:
    ax.set_xticks([])
    ax.set_yticks([])
plt.tight_layout()
plt.show()

コードの解説番号をクリックすると、コード内の該当行がハイライトされます。

6 行目巻いた多様体を人工的に作る
make_swiss_roll は 2 次元の長方形を 3 次元空間で渦巻き状に巻いたデータを返し、color には巻きに沿った位置（展開したときの横座標）が入ります。正解の「広げ方」が分かっているので、埋め込み後に色が左から右へ順に並べば Isomap が巻きを正しくほどいた証拠になります。noise=0.05 は紙の厚み程度の揺らぎで、これを 0.5 にすると内側と外側の巻きがつながってしまい、測地距離が壊れます。
7 行目近傍数 10 で面に沿ったグラフを張る
n_neighbors=10 は各点を近い 10 点とつなぐ指定です。巻きの層の間隔より近い点だけがつながるので、グラフの辺は紙の面に沿って張られます。この値を 40 にすると隣の層の点ともつながって近道ができ、測地距離が直線距離に近づいて PCA と同じ潰れた図になります。3 まで下げるとグラフが複数の島に分断され、島の間の距離が無限大になって埋め込みが壊れます。n_components=2 は展開先の次元で、紙は本来 2 次元なので 2 で十分です。
8 行目fit_transform の中で最短経路と MDS が走る
この 1 行で、近傍グラフの構築、全ペアの最短経路計算、MDS による座標の決定がすべて実行されます。1500 点の最短経路計算は数秒で済みますが、計算量は点の数の 2 乗以上で増えるので、数万点では n_neighbors を小さくするか点を間引きます。
11-14 行目巻き位置の色で展開の正しさを読む
左右どちらも c=color で巻きに沿った位置を色にしています。左の元データでは色が渦巻き状に並び、右の埋め込みで色が左から右へ虹のように一方向に並べば、巻きがほどけて紙の長方形に戻ったと読めます。色が途中で折り返していれば n_neighbors が大きすぎて層の間に近道ができた合図です。

Python 実装の図

実行結果の読み方 #

左の図では色が渦を巻いていますが、右の Isomap 埋め込みでは横に長い長方形の上に色が一方向に並びます。これが「巻いた紙を広げた」状態です。同じデータを PCA にかけると渦を真上から潰した円盤になり、紙の反対側の色が重なります。

3. パラメータ選び #

いちばん効くのは n_neighbors です。小さすぎると近傍グラフが分断されて距離が定義できない点の組ができ、大きすぎると層をまたぐ近道ができて測地距離がユークリッド距離に近づきます。n_components は可視化なら 2 か 3、下流モデルの前処理なら必要な次元まで増やします。近傍グラフはノイズに弱いので、外れ値が 1 点あるだけで本来離れた層をつなぐ橋になることがあり、事前の外れ値除去や StandardScaler による列のスケール合わせが埋め込みの品質を左右します。

4. 長所と短所 #

長所	短所
非線形構造を保ちつつ展開	グラフ最短経路の計算コストが高い
埋め込み座標が安定	近傍グラフの選び方に敏感
可視化に向く	高次元・大規模データでは重い

5. まとめ #

Isomap は「近傍グラフの最短経路で測地距離を測り、それを MDS で保つ」という 3 段階の構成で、Swiss roll のように巻いた多様体を平面に広げます。直線距離しか見ない PCA が巻きを潰してしまうのに対し、n_neighbors=10 の Isomap では色が一方向に並んだ長方形が得られました。結果は近傍グラフの品質で決まります。n_neighbors を 3〜40 の範囲で動かして分断と近道の両方を避け、外れ値を先に取り除きます。局所構造だけを重視する t-SNE や高速な UMAP と並べて見ると、同じデータの多様体構造を別の角度から確認できます。

t-SNE — 近傍の確率分布を保つ可視化向けの多様体学習
Kernel-PCA — カーネルベースの非線形PCA
主成分分析（PCA） — 線形な基本手法
UMAP — 近傍グラフを使う点は同じで、数十万点に対応する高速な多様体学習手法

近傍数と Isomap #

スライダーで n_neighbors を 3, 5, 10, 20, 40 と変えると、3 クラスのデータの埋め込みがどう変わるかを確認できます。3 では近傍グラフが細切れになって点が帯状に伸び、10 前後で 3 つの塊が最もはっきり分かれ、40 では測地距離が直線距離に近づいて PCA に似た配置になります。