차원의 저주: 데이터 밀도, 거리 집중 현상, KNN 과적합, PCA 실험

요약

 

• 고차원 데이터는 차원의 저주(Curse of Dimensionality)로 인해 데이터 간 거리가 멀어지고 희소해짐
• 거리 기반 알고리즘(KNN 등)은 고차원에서 거리의 의미가 사라지며 성능이 급감함 (거리 집중 현상)
• 모델 복잡도가 증가하고 과적합 위험이 커져 일반화 성능 저하
• 고차원 데이터도 종종 저차원 구조(다양체)를 가짐 → 이를 활용한 차원 축소가 핵심
• PCA, AutoEncoder를 통해 유의미한 저차원 표현으로 압축 가능
• CNN은 이미지 데이터의 구조적 특성을 활용하여 사실상 차원 축소 효과
• Dropout, 정규화(L1/L2) 등은 과적합 방지에 효과적
• Random Forest처럼 서로 다른 feature subset을 사용하는 앙상블도 효과적
• KNN+PCA 조합은 고차원에서도 KNN 성능을 유지하거나 개선 가능

 

 

 

 

차원의 저주(Curse of Dimensionality):

 

데이터의 차원(=변수의 개수)이 높아질수록 공간의 부피(volumn)가 지수적으로 증가하여, 데이터 포인트 간 거리가 상대적으로 멀어지고 데이터가 희소(sparse)해지는 현상

 

- 주요 문제점:

• 데이터 밀도 감소
• 거리 집중 (Distance Concentration)
• 모형 복잡도 증가
• 거리 기반 알고리즘(KNN 등)의 성능 저하
• 과적합(overfitting) 위험 증가

 

 

 

거리 집중(Distance Concentration):

 

차원이 증가함에 따라, 데이터 포인트들 간의 거리가 점점 유사해지고 구별이 어려워짐

• 고차원 공간에서 대부분의 데이터 포인트들은 서로 비슷한 거리를 가지게 되며, 가까움의 의미가 없어짐
• KNN (k-최근접 이웃) 알고리즘과 같은 거리 기반 모델은 이러한 현상에 매우 민감함
  → 이웃을 고르기가 애매해지고, 가까운 이웃과 먼 이웃의 구분이 모호해짐
  → 성능 저하
• 따라서 고차원에서는 KNN 분류기/회귀기의 정확도가 급격히 하락할 수 있음

 

 

 

(예1, 데이터 밀도 감소)

격자점: 공간을 채우기 위해 필요한 데이터 포인트의 개수가 기하급수적으로 증가
- 1차원 공간 $[0, 10]$의 격자점은 $11^1=11$개
- 2차원 공간 $[0, 10] \times [0, 10]$의 격자점은 $11^2=121$개
- 3차원 공간 $[0, 10] \times [0, 10] \times [0, 10]$의 격자점은 $11^3=1331$개
...

→ 동일한 개수의 포인트가 고차원 공간에 있으면 데이터의 밀도가 낮아지며, 클러스터링, 패턴 인식 등이 어려워짐

 

 

 

(예2, 거리 집중)

 

(예2-1, Unit hypercube $[0, 1]^p$에서 정의된 분포)
$\prod_{i=1}^{p} U_i$ , $ \quad U_i \overset{\mathrm{i.i.d.}}{\sim} \text{Uniform}(0,1)$
에서 $2$개의 random sample을 추출하면

• 부피: $1$, 두 점 사이 최대 거리: $\sqrt{p}$
• 두 점 사이 평균 (유클리드) 거리 $D$: 차원이 증가할수록 $D / \sqrt{p}$의 분산 감소 (i.e. 거리 집중)

(0) 풀이 방향

• $D$의 분포 대신 계산이 상대적으로 쉬운 $D^2$의 극한분포를 고려하고 일차근사 진행
• $D^2 = \sum_{k=1}^{p}{W_k}$, $W_k = (U_k - V_k)^2$의 극한분포: 아래 내용에 의해 평균, 분산이 존재하므로 중심극한정리(CLT; Central Limit Theorem) 적용 가능

(1) $U, V \overset{\mathrm{i.i.d.}}{\sim} Uniform[0, 1]$, $W = (U-V)^2$이면, $E[U^p] = E[V^p] = 1/(1+p)$이고 $U, V$가 독립이므로 $W$의 평균 및 분산을 계산할 수 있음

 

• $E[(U-V)^2]$
  = $E[U^2] - 2E[U]E[V] + E[V^2]$
  = $1/3 - 2 \cdot 1/2 \cdot 1/2 + 1/3$
  = $1/6$
• $E[(U-V)^4]$
  = $E[U^4] - 4E[U^3]E[V] + 6E[U^2]E[V^2] - 4E[U]E[V^3] + E[V^4]$
  = $1/5 - 4 \cdot 1/4 \cdot 1/2 + 6 \cdot 1/3 \cdot 1/3 - 4 \cdot 1/2 \cdot 1/4 + 1/5$
  = $1/15$
• $E[W] = 1/6$
• $Var[W] = 1/15 - (1/6)^2 = 7/180$

(2) 중심극한정리에 의해 $ \sqrt{p} (D^2 / p - E[W]) \overset{d}{\longrightarrow} N(0, Var[W])$

$f(x) = \sqrt{x}$를 이용한 일차근사(Delta method)를 적용하면

$ \sqrt{p} (D / \sqrt{p} - \sqrt{E[W]})$ $ \overset{d}{\longrightarrow} $ $\dfrac{1}{2 \sqrt{E[W]}} \cdot N(0, Var[W])$

→ 고차원 공간에서 거리 계산의 의미가 퇴색됨

import numpy as np
import matplotlib.pyplot as plt
import sys

# Print versions
print(f"Python version: {sys.version}")
print(f"NumPy version: {np.__version__}")
print(f"Matplotlib version: {plt.matplotlib.__version__}")

# Parameters
n_samples = 10000
dimensions = [3, 10, 50, 100, 200, 500]

# Theoretical values
E_W = 1/6
Var_W = 7/180
theoretical_mean = np.sqrt(E_W)

# Collect all normalized distances
all_D_normalized = []

for p in dimensions:
    A = np.random.rand(n_samples, p)
    B = np.random.rand(n_samples, p)
    D = np.linalg.norm(A - B, axis=1)
    D_normalized = D / np.sqrt(p)
    all_D_normalized.append(D_normalized)

# Determine global x/y axis ranges
all_values = np.concatenate(all_D_normalized)
x_min = np.min(all_values)
x_max = np.max(all_values)

y_max = 0
for D_norm in all_D_normalized:
    counts, _ = np.histogram(D_norm, bins=50, density=True)
    y_max = max(y_max, counts.max())
y_max *= 1.1

# Plotting
plt.figure(figsize=(15, 10))

for i, (p, D_norm) in enumerate(zip(dimensions, all_D_normalized), 1):
    mean_emp = np.mean(D_norm)
    std_emp = np.std(D_norm)

    std_theory = (1 / (2 * np.sqrt(E_W))) * np.sqrt(Var_W / p)

    # Plot
    plt.subplot(2, 3, i)
    plt.hist(D_norm, bins=50, density=True, color='skyblue', alpha=0.7, label='Empirical')
    plt.axvline(mean_emp, color='red', linestyle='--', label=f'Emp. μ={mean_emp:.4f}\nEmp. σ={std_emp:.4f}')
    plt.axvline(theoretical_mean, color='green', linestyle='--', label=f'Theo. μ={theoretical_mean:.4f}\nTheo. σ={std_theory:.4f}')

    plt.title(f'p = {p}')
    plt.xlabel(r'$D / \sqrt{p}$')
    plt.ylabel('Density')
    plt.xlim(x_min, x_max)
    plt.ylim(0, y_max)
    plt.legend(fontsize=8, loc='upper right')

plt.suptitle('Empirical vs Theoretical Distribution of $D/\\sqrt{p}$', fontsize=16)
plt.tight_layout(rect=[0, 0, 1, 0.96])
plt.show()

 

 

(예2-2, 참고 링크) Mathematical demonstration of the distance concentration in high dimensions

https://stats.stackexchange.com/questions/451027/mathematical-demonstration-of-the-distance-concentration-in-high-dimensions

Mathematical demonstration of the distance concentration in high dimensions

 

 

 

차원의 저주를 해결하기 위한 공통 가정:

 

고차원 데이터에도 내재된 단순한 구조가 있다!

• 대부분의 경우, 고차원 데이터는 저차원 다양체(manifold) 위에 분포해 있다.
• 따라서, 데이터를 의미 있는 저차원 표현으로 압축하거나, 고차원 구조의 제약을 활용해야 한다.

(참고) 위 (예1, 데이터 밀도 감소), (예2, 거리 집중)의 경우는 가정을 만족하지 않는 극단적인 예시임

 

 

 

해결 방법

 

1. 데이터의 특성과 구조 이해:

 

(예) CNN (Convolutional Neural Network): 이미지 데이터 등

• (가정 1) 공간적 국소성(spatial locality): 인접한 입력값(픽셀)이 서로 연관된 정보(색상, 패턴 등)를 가지고 있다.
• (가정 2) 패턴의 위치 불변성(stationarity): 한 위치에서 학습한 패턴(예: 엣지)은 다른 위치에서도 유효하다.
• 합성곱(Convolution) 연산을 통해 이미지 내에서 인접한 지역 간의 관계를 캡처
• Vanilla NN 대비 parameter 수 감소 (fully connected vs parameter 공유) -> 사실상 차원 수를 간접적으로 줄임

(참고 링크) Why do Convolutional Neural Networks work so well?

https://youtu.be/8iIdWHjleIs?si=T9DIftCR8eCMLroC

 

 

 

2. 차원 축소 (데이터 압축):

 

(가정) 데이터의 의미 있는 분산 대부분은 소수의 차원으로 설명할 수 있다(특징 간에 상관관계가 있다).

 

(예) PCA (Principal Component Analysis)

• 직교 선형 변환을 통해 데이터 분산이 큰 방향으로 축을 재정렬
• 처음 몇 개의 주성분만 유지하고 나머지는 제거 → 효율적 차원 축소
• KNN + PCA 조합: 고차원 데이터에서 먼저 PCA로 차원을 줄인 뒤, KNN을 적용하면 성능이 개선될 수 있음
  → 특히 고차원 이미지/텍스트 벡터 데이터에서 효과적

(예) AutoEncoder

• 비선형 차원 축소를 수행하는 신경망 기반 방법
• 중간에 저차원 잠재 공간(latent space)을 통해 중요한 특징만 추출
• 노이즈 제거 및 일반화 성능 향상

 

 

 

3. 정규화 및 모델 간소화:

 

고차원일수록 모델이 과적합(overfit)되기 쉬움
→ 차원이 많으면 훈련 데이터에 과하게 맞춘 복잡한 모델이 만들어질 가능성 증가
→ 일반화 성능 저하

 

(예) 정규화 방법

• L1/L2 정규화 (ElasticNet): 불필요한 feature의 가중치를 0으로 만들거나 줄임
• Dropout (신경망): 일부 뉴런을 학습 시 랜덤하게 제거하여 과적합 방지
• Sparse coding: 적은 수의 활성화된 feature로 정보를 표현하여 모델 단순화

 

 

 

4. Random Subspace (부분공간 학습)

• 특징 공간을 무작위로 나눠서 여러 모델에 학습시킴
• 서로 다른 feature subset에 대해 학습된 모델을 앙상블 → 과적합 억제 + 성능 향상
• (예) Random Forest: Bagging + Random Subspace 조합
  → 고차원에서도 안정적인 성능

 

 

 

예시 코드: KNN + PCA 실험

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification
from sklearn.decomposition import PCA
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Set random seed for reproducibility
np.random.seed(42)

# Parameters
n_samples = 2000
n_features_list = [10, 50, 100, 200]
n_informative = 5
test_size = 0.3
n_neighbors = 5

# Store results
knn_acc = []
pca_knn_acc = []

for n_features in n_features_list:
    # Generate classification data
    X, y = make_classification(n_samples=n_samples, n_features=n_features,
                               n_informative=n_informative, n_redundant=0,
                               n_repeated=0, n_classes=2, random_state=42)

    # Split data
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=test_size, random_state=42)

    # 1. KNN on raw high-dimensional data
    knn = KNeighborsClassifier(n_neighbors=n_neighbors)
    knn.fit(X_train, y_train)
    y_pred_knn = knn.predict(X_test)
    acc_knn = accuracy_score(y_test, y_pred_knn)
    knn_acc.append(acc_knn)

    # 2. PCA + KNN
    pca = PCA(n_components=n_informative)
    X_train_pca = pca.fit_transform(X_train)
    X_test_pca = pca.transform(X_test)

    knn_pca = KNeighborsClassifier(n_neighbors=n_neighbors)
    knn_pca.fit(X_train_pca, y_train)
    y_pred_pca = knn_pca.predict(X_test_pca)
    acc_pca = accuracy_score(y_test, y_pred_pca)
    pca_knn_acc.append(acc_pca)

# Plot
plt.figure(figsize=(10, 6))
plt.plot(n_features_list, knn_acc, marker='o', label='KNN (Raw)', color='red')
plt.plot(n_features_list, pca_knn_acc, marker='o', label='PCA + KNN', color='green')
plt.xlabel('Number of Features (Dimension)')
plt.ylabel('Test Accuracy')
plt.title('KNN vs PCA+KNN across Dimensions')
plt.grid(True)
plt.legend()
plt.tight_layout()
plt.show()