想定読者：

kNN距離など「距離ベース」で外挿/OOD/異常検知をやってみた人
あるいはクラスタリング・近傍探索・類似検索を触った人
「次元が高いと距離が効かない」と聞いたことがあるが、腹落ちしていない人

この記事のゴール：

高次元で距離が効かなくなる現象（距離集中）を用語から理解する
ダミーデータで「本当に距離が死ぬ」を図で体験する
そして「データが低次元構造を持つなら」PCAで距離を蘇らせられることを、最小実装で確認する

TL;DR（結論）

高次元では、点と点の距離が 平均付近に集中していき、「近い/遠い」の差が小さくなります（距離集中）。
その結果、kNN・距離ベース異常検知・クラスタリングなどが急に不安定になります（＝「距離が死ぬ」）。
ただし、現実のデータが「低次元の構造（低い内在次元）」を持ち、そこに意味があるなら、
PCAで次元を落としてノイズ次元を捨てることで距離が蘇ることがあります。
この記事のコード（seed固定）では、OOD検知（kNN距離スコア）のAUROCが
- raw（高次元そのまま）：次元が増えるほど低下（例：D=20で≈0.91 → D=1000で≈0.78）
- Standardize → PCA(2) → kNN：高次元でもほぼ維持（≈0.92〜0.93）
  という挙動になります。

1. 用語：距離集中 / 次元の呪い / PCA

距離集中（distance concentration）

高次元になるほど、点同士の距離が似た値に集まり、

「近い点」と「遠い点」の差が相対的に小さくなる

現象です。

次元の呪い（curse of dimensionality）

距離集中も含めて、高次元が原因で

必要データ数が爆増
近傍が意味を失う
密度推定が難しい
などが起きることの総称として使われます。

PCA（Principal Component Analysis：主成分分析）

データの分散（ばらつき）をなるべく保ちながら、
直交座標系（主成分）に写して次元を圧縮する方法です。

たくさんの特徴量の中に「実は2〜3次元の構造」があるとき、そこを抽出しやすい
ノイズ次元を落とせると、距離ベースが復活することがある

2. なぜ高次元で距離が死ぬのか？（直感＋超ざっくり式）

直感：

次元が増えるほど、差分（ノイズ）を足し合わせる回数が増える
すると距離は「大きくなる」だけでなく「平均との差が相対的に小さくなる」

ざっくり式（雰囲気だけ）：

もし x, y ~ N(0, I_D) なら、x-y ~ N(0, 2I_D) なので
||x-y||^2 はだいたい 平均が 2D、分散が 8D みたいなスケールになります
すると距離（||x-y||）の 相対的なばらつき（std/mean） は
~ 1/sqrt(D) くらいで小さくなる
→ Dが大きいほど“みんな同じ距離”に見える。

3. 最小実験①：距離集中を「図で」体験する

実験内容

各次元Dで、ランダムな点を生成
点同士の距離の分布を見て、
- 相対的ばらつき（CV=std/mean）
- 「遠い/近い」比（q95/q05）
  がDとともにどう変わるかを確認します

4. 最小実験②：距離集中が“検知”を壊す → PCAで蘇らせる

実験の設計（ここが大事）

現実っぽく、こういう状況をダミーで作ります：

データには本当は 低次元（2次元）の意味ある構造がある（=内在次元が低い）
でも同時に、無関係な特徴量（ノイズ次元）が大量に混ざっている
OOD（分布外）は「低次元の意味ある方向」だけズレる（＝本質的に見抜きたい）

このとき、

高次元そのままの距離（kNN）はノイズ次元に支配され、性能が落ちる
PCAで低次元構造だけ取り出すと、距離が復活する（ことがある）

5. Google Colab 実行コード（コピペでOK）

5.1 import

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from sklearn.metrics import pairwise_distances, roc_auc_score
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import NearestNeighbors
from sklearn.decomposition import PCA

5.2 距離集中の統計を取る関数

def distance_concentration_stats(d_list, n=350, seed=0):
    """
    For each dimension D:
      - sample n points from N(0, I_D)
      - compute pairwise distances
      - summarize distance spread
    """
    rng = np.random.default_rng(seed)
    stats=[]
    for d in d_list:
        X = rng.normal(size=(n, d))
        Dm = pairwise_distances(X, metric="euclidean")
        iu = np.triu_indices(n, k=1)
        dist = Dm[iu]

        mean = dist.mean()
        std = dist.std()
        cv = std / mean
        q05, q50, q95 = np.quantile(dist, [0.05, 0.5, 0.95])
        ratio = q95 / q05
        stats.append({"D": d, "mean": mean, "std": std, "cv": cv, "q05": q05, "q50": q50, "q95": q95, "q95/q05": ratio})
    return pd.DataFrame(stats)

5.3 実験①：距離集中を描く（図1）

d_list = [2, 5, 10, 20, 50, 100, 200, 500, 1000]
dc = distance_concentration_stats(d_list, n=350, seed=0)
display(dc)

fig, axes = plt.subplots(1,2, figsize=(10.5,4.0))

axes[0].plot(dc["D"], dc["cv"], marker="o")
axes[0].set_xscale("log")
axes[0].set_xlabel("dimension D (log)")
axes[0].set_ylabel("CV = std(dist)/mean(dist)")
axes[0].set_title("Relative spread shrinks")

axes[1].plot(dc["D"], dc["q95/q05"], marker="o")
axes[1].set_xscale("log")
axes[1].set_xlabel("dimension D (log)")
axes[1].set_ylabel("q95 / q05")
axes[1].set_title("'Near' and 'far' become similar")

fig.suptitle("Distance concentration in high-dimensional space", y=1.05)
fig.tight_layout()
fig.savefig("fig1_distance_concentration.png", dpi=200, bbox_inches="tight")
plt.show()

print("saved: fig1_distance_concentration.png")

CV（相対的ばらつき）がDとともにどんどん小さくなる
q95/q05 が 1 に近づいていく（=「遠い」と「近い」が似てくる）

6. 実験②：高次元でkNN検知が落ち、PCAで戻るのを確認

6.1 ダミーデータ生成（低次元の構造＋大量ノイズ）

def generate_dataset(n, d_total, W_signal, z_shift=None, signal_noise=0.3, seed=0):
    """
    intrinsic dim = 2 latent z
    - m_signal features are correlated via z @ W_signal^T + small noise
    - remaining (d_total - m_signal) features are pure noise
    """
    rng = np.random.default_rng(seed)
    z = rng.normal(size=(n, 2))
    if z_shift is not None:
        z = z + np.array(z_shift).reshape(1,2)

    X_signal = z @ W_signal.T + rng.normal(scale=signal_noise, size=(n, W_signal.shape[0]))
    d_noise = d_total - W_signal.shape[0]
    X_noise = rng.normal(size=(n, d_noise))
    return np.concatenate([X_signal, X_noise], axis=1)

6.2 kNN距離スコア（Standardize →（任意でPCA）→ kNN）

def knn_distance_score(X_train, X_test, k=5, n_components=None, random_state=0):
    # 1) scale
    scaler = StandardScaler().fit(X_train)
    Xtr = scaler.transform(X_train)
    Xte = scaler.transform(X_test)

    # 2) optional PCA
    explained = None
    if n_components is not None:
        pca = PCA(n_components=n_components, random_state=random_state).fit(Xtr)
        Xtr = pca.transform(Xtr)
        Xte = pca.transform(Xte)
        explained = pca.explained_variance_ratio_.sum()

    # 3) kNN distance
    nn = NearestNeighbors(n_neighbors=k).fit(Xtr)
    d, _ = nn.kneighbors(Xte)
    return d.mean(axis=1), explained

6.3 Dを増やしてAUROCを比較（図2）

# Settings (seed固定)
rng = np.random.default_rng(0)

m_signal = 20                 # 低次元構造が載る「相関した特徴量」の数
W_signal = rng.normal(size=(m_signal, 2))

z_shift = (2.0, 2.0)          # OODは低次元方向にずらす
signal_noise = 0.3

n_train = 800
n_test = 2000

D_list = [20, 50, 100, 200, 500, 1000]

rows = []
for D in D_list:
    X_train = generate_dataset(n_train, D, W_signal, z_shift=None, signal_noise=signal_noise, seed=1)
    X_in    = generate_dataset(n_test,  D, W_signal, z_shift=None, signal_noise=signal_noise, seed=2)
    X_ood   = generate_dataset(n_test,  D, W_signal, z_shift=z_shift, signal_noise=signal_noise, seed=3)

    s_in_raw, _ = knn_distance_score(X_train, X_in,  k=5, n_components=None)
    s_ood_raw, _ = knn_distance_score(X_train, X_ood, k=5, n_components=None)

    y = np.concatenate([np.zeros_like(s_in_raw), np.ones_like(s_ood_raw)])
    auc_raw = roc_auc_score(y, np.concatenate([s_in_raw, s_ood_raw]))

    s_in_pca, explained = knn_distance_score(X_train, X_in,  k=5, n_components=2)
    s_ood_pca, _        = knn_distance_score(X_train, X_ood, k=5, n_components=2)
    auc_pca = roc_auc_score(y, np.concatenate([s_in_pca, s_ood_pca]))

    rows.append({"D": D, "AUROC_raw": auc_raw, "AUROC_PCA2": auc_pca, "explained_var_PCA2": explained})

perf = pd.DataFrame(rows)
display(perf)

plt.figure(figsize=(6.8,4.4))
plt.plot(perf["D"], perf["AUROC_raw"], marker="o", label="raw space (Std→kNN)")
plt.plot(perf["D"], perf["AUROC_PCA2"], marker="o", label="Std→PCA(2)→kNN")
plt.xscale("log")
plt.ylim(0.45, 1.02)
plt.xlabel("total dimension D (log)")
plt.ylabel("AUROC (In vs OOD)")
plt.title("Distance-based detection degrades in high dimension\nPCA can recover when data has low intrinsic dim")
plt.legend()
plt.tight_layout()
plt.savefig("fig2_auroc_vs_dim.png", dpi=200)
plt.show()

print("saved: fig2_auroc_vs_dim.png")

raw（高次元のまま）AUROCが、Dが増えるほど下がる
PCA(2)を挟むと、AUROCが高次元でも比較的維持される

なお explained_var_PCA2（寄与率）はDが増えるほど小さく見えます。
これは「ノイズ次元が増えて総分散が増える」ためで、小さいからダメとは限りません（ここは誤解ポイント）。

7. 実験③：高次元（D=1000）でスコア分布を比較（図3）

D_example = 1000
n_inout = 4000

X_train = generate_dataset(n_train, D_example, W_signal, z_shift=None, signal_noise=signal_noise, seed=1)
X_in    = generate_dataset(n_inout, D_example, W_signal, z_shift=None, signal_noise=signal_noise, seed=2)
X_ood   = generate_dataset(n_inout, D_example, W_signal, z_shift=z_shift, signal_noise=signal_noise, seed=3)

s_in_raw, _ = knn_distance_score(X_train, X_in,  k=5, n_components=None)
s_ood_raw, _ = knn_distance_score(X_train, X_ood, k=5, n_components=None)

y = np.concatenate([np.zeros_like(s_in_raw), np.ones_like(s_ood_raw)])
auc_raw = roc_auc_score(y, np.concatenate([s_in_raw, s_ood_raw]))

s_in_pca, explained = knn_distance_score(X_train, X_in,  k=5, n_components=2)
s_ood_pca, _        = knn_distance_score(X_train, X_ood, k=5, n_components=2)
auc_pca = roc_auc_score(y, np.concatenate([s_in_pca, s_ood_pca]))

print(f"D={D_example} raw AUROC  = {auc_raw:.3f}")
print(f"D={D_example} PCA AUROC  = {auc_pca:.3f}")
print(f"PCA(2) explained variance ratio (sum) = {explained*100:.2f}%")

# 図3：raw vs PCA のスコア分布（2枚を1枚にまとめて保存）
fig, axes = plt.subplots(1,2, figsize=(11.5,4.2))

axes[0].hist(s_in_raw, bins=60, alpha=0.6, label="In")
axes[0].hist(s_ood_raw, bins=60, alpha=0.6, label="OOD")
axes[0].set_xlabel("kNN distance (raw space)")
axes[0].set_ylabel("count")
axes[0].set_title(f"Raw space\nAUROC={auc_raw:.3f}")
axes[0].legend(fontsize=8)

axes[1].hist(s_in_pca, bins=60, alpha=0.6, label="In")
axes[1].hist(s_ood_pca, bins=60, alpha=0.6, label="OOD")
axes[1].set_xlabel("kNN distance (Std→PCA(2))")
axes[1].set_ylabel("count")
axes[1].set_title(f"After PCA (2 comps)\nAUROC={auc_pca:.3f}")
axes[1].legend(fontsize=8)

fig.suptitle(f"Score distributions (D={D_example})", y=1.05)
fig.tight_layout()
fig.savefig("fig3_score_hist_compare.png", dpi=200, bbox_inches="tight")
plt.show()

print("saved: fig3_score_hist_compare.png")

raw空間は In と OOD のヒストグラムがかなり重なりやすい
PCA後は分離がよくなり、スコアで判定しやすくなる

図4：PCA空間（2D）の散布図

# PCA空間で可視化
scaler = StandardScaler().fit(X_train)
Xtr_s = scaler.transform(X_train)
pca = PCA(n_components=2, random_state=0).fit(Xtr_s)

Z_in  = pca.transform(scaler.transform(X_in))
Z_ood = pca.transform(scaler.transform(X_ood))

# 表示が重いのでサンプル
rng2 = np.random.default_rng(0)
idx_in  = rng2.choice(len(Z_in),  size=800, replace=False)
idx_ood = rng2.choice(len(Z_ood), size=800, replace=False)

plt.figure(figsize=(6,6))
plt.scatter(Z_in[idx_in,0],  Z_in[idx_in,1],  s=10, alpha=0.6, label="In")
plt.scatter(Z_ood[idx_ood,0], Z_ood[idx_ood,1], s=10, alpha=0.6, label="OOD")
plt.xlabel("PC1")
plt.ylabel("PC2")
plt.title(f"PCA space (2D) reveals structure (D={D_example} → 2)")
plt.legend()
plt.tight_layout()
plt.savefig("fig4_pca_scatter.png", dpi=200)
plt.show()

print("saved: fig4_pca_scatter.png")

8. 実務で「PCAで蘇らせる」が効く条件 / 効かない条件

効きやすい（PCAが強い）パターン

特徴量が多いが、実際には 相関が強い（センサー配列、計測特徴、埋め込みなど）
ノイズ次元が多く、距離がノイズに埋もれている
データが（だいたい）線形な低次元構造に乗っている（PCAは線形）

効きにくい / 注意が必要

意味のある差が 低分散方向にある（PCAが捨てる可能性）
データ構造が非線形（曲がった多様体）で、PCA(線形)では表現しにくい
特徴量がワンホットなど疎で、ユークリッド距離自体が不適切なことがある
→ その場合は距離（コサイン等）やモデルを見直す

9. 「何次元まで落とす？」の決め方（初心者向け）

よくある決め方：

寄与率（explained variance）が 90% などになる最小次元を選ぶ

ただしこの記事のように「ノイズ次元が大量にある」状況だと、

寄与率は小さく見えても、検知には十分な場合がある

おすすめの決め方（運用寄り）：

検証データ（Inと想定OOD）で、AUROCやアラート率を見ながら n_components を選ぶ
具体例：n_components ∈ {2, 5, 10, 20, 50} を試す

大事：PCAは必ず 学習データだけでfit し、推論時はtransformする
（リーク防止。Pipeline化推奨）

まとめ

高次元では距離が集中し、「近い/遠い」が曖昧になりやすい（距離が死ぬ）
距離ベースの検知（kNNなど）は、その影響を強く受ける
ただしデータに低次元の構造があるなら、
Standardize → PCA → 距離 で距離が蘇ることがある
実務では「寄与率だけ」ではなく、検証性能と運用（誤警報/見逃し）で次元数を決めるのが安全