دادهٔ با ابعاد بالا و نفرین ابعاد
مقدمه¶
در دادهکاوی و یادگیری ماشین امروز، بارها با داده در فضاهای بسیار ابعاد بالا سروکار داریم (برای مثال تصویرها، تعبیههای متنی، دادهٔ ژنومی). مجموعهداده معمولاً با ماتریس مانند نمایش داده میشود.
شناخت ماهیت فضای با ابعاد بالا، یا فرافضا، بسیار مهم است، چون مانند هندسهٔ آشنای دو یا سه بُعد رفتار نمیکند. این پدیده را اغلب نفرین ابعاد مینامند.
پدیدههای کلیدی که بررسی میکنیم:
تمرکز حجم: حجم ابَرکره نسبت به فرامکعب به صفر میل میکند.
مسئلهٔ همسایگیهای محلی: چرا روشهای «محلی» مانند k-NN شکست میخورند (بر پایهٔ Elements of Statistical Learning).
پوستهٔ نازک: بیشتر حجم نزدیک سطح جمع میشود (اندازهگیری در صفحهٔ نمونهگیری).
تعامد: بردارهای تصادفی در ابعاد بالا تقریباً عمود بر هماند.
رفتار گاوسی: نقطهها در حلقهٔ نازکی گرد شعاع جمع میشوند — این هم در صفحهٔ نمونهگیری اندازهگیری میشود.
هندسهٔ فرافضا: مکعبها و کرهها¶
دو شکل بنیادی در بُعد را تعریف کنیم.
فرامکعب¶
فضای داده را اغلب یک فرامستطیل یا فرامکعب -بُعدی میگیرند. برای فرامکعب با ضلع ، حجم برابر است با:
ابَرکره¶
گوی توپر را و سطح آن را مینویسیم. این تمایز مهم است: حجم زیر از آنِ گوی است و مرز آن لایهای با اندازهٔ صفر است. حجم گوی -بُعدی با شعاع برابر است با:
که در آن تابع گاما است.
شکل ۶.۴. ابَرکرهٔ محاط در فرامکعب: در (الف) دو و (ب) سه بُعد
مرکز خالی (اثر «خارپشت»)¶
فضای درون بزرگترین ابَرکرهای را در نظر بگیرید که در فرامکعبی با ضلع جا میشود. نسبت حجمهایشان چنین است:
پیامد: با افزایش بُعد، حجم ابَرکره در برابر فرامکعب ناچیز میشود. بیشتر حجم فرامکعب در گوشهها است و مرکز عملاً خالی میماند.

نمایی مفهومی از فضای با ابعاد بالا: (الف) دو، (ب) سه، (ج) چهار و (د) بُعدهای بالاتر. در بُعد «گوشه» و قطر داریم. شعاع دایرهٔ محاطی تفاوت حجم فرامکعب و ابَرکرهٔ محاطی را در بُعد بهدرستی نشان میدهد.
Source
import math
import matplotlib.pyplot as plt
import numpy as np
def hypersphere_volume(d, R):
"""Volume of the solid ball of radius R in d dimensions."""
return (math.pi ** (d / 2)) * (R ** d) / math.gamma(d / 2 + 1)
dimensions = list(range(1, 30))
volumes = [hypersphere_volume(d,1) for d in dimensions]
plt.figure(figsize=(10, 6))
plt.plot(dimensions, volumes, marker='o', linestyle='-', color='b', label='volume of the unit ball')
plt.xlabel('dimension d')
plt.ylabel('Volume')
plt.title("Volume of a unit hypersphere in various dimensions")
plt.legend()
plt.grid(True)
plt.show()
مسئلهٔ همسایگیهای محلی (k-NN)¶
یکی از مهمترین جلوههای نفرین ابعاد، روشهای «محلی» مانند k نزدیکترین همسایه (k-NN) را هدف میگیرد.
طول ضلع همسایگیها¶
فرض کنید ورودیها بهطور یکنواخت در فرامکعبی یکه با بُعد توزیع شدهاند. میخواهیم همسایگی محلیای بسازیم که کسری از مشاهدات را در بر گیرد. چون این کسر حجمِ یکه است، امید ریاضی طول ضلع این همسایگی چنین است:

شکل ۲.۶. نفرین ابعاد را بهخوبی با یک همسایگی زیرمکعبی برای دادهٔ یکنواخت در مکعب یکه نشان میدهند. شکل سمت راست طول ضلع زیرمکعبی را نشان میدهد که برای در بر گرفتن کسری از حجم داده لازم است، برای بُعدهای مختلف . در ده بُعد باید ۸۰٪ دامنهٔ هر مختصه را بپوشانیم تا ۱۰٪ داده را در بر بگیریم
بیایید این را برای بُعدهای مختلف () و کسرهای مختلف () ببینیم.
Source
import numpy as np
import matplotlib.pyplot as plt
def edge_length(fraction_volume, p):
return fraction_volume ** (1/p)
fractions = np.linspace(0.001, 1.0, 100)
dims_esl = [1, 2, 3, 10]
plt.figure(figsize=(8, 6))
for p in dims_esl:
plt.plot(fractions, edge_length(fractions, p), label=f'p={p}')
# Highlighting the case for p=10, r=0.1
plt.plot(0.1, 0.1**(1/10), 'ro')
plt.xlabel('Fraction of Volume ($r$)')
plt.ylabel('Edge Length of Subcube: $e_p(r)$')
plt.title('Edge Length required to capture fraction of Volume')
plt.legend()
plt.grid(True)
plt.show()
تحلیل: در ده بُعد ()، برای در بر گرفتن تنها ۱۰٪ () داده، باید ۸۰٪ دامنهٔ هر متغیر ورودی را بپوشانیم. چنین همسایگیهایی دیگر «محلی» نیستند. برای یافتن همسایه باید بسیار دور را نگاه کرد.
فاصله تا مرز¶
پیامد دیگر، تُنُکی چگالی نمونهبرداری است. برای نقطهٔ داده در گوی یکهٔ -بُعدی، میانهٔ فاصلهٔ مبدأ تا نزدیکترین نقطهٔ داده برابر است با:
برای و این فاصله حدود است، یعنی بیش از نیمهٔ راه تا مرز. پس بیشتر نقطههای داده به مرز فضای نمونه نزدیکترند تا به هر نقطهٔ دادهٔ دیگر. همین پیشبینی را از یک مسئلهٔ برونیابی به جای درونیابی میکند.
تعامد: جهتهای تصادفی تقریباً عمودند¶
ویژگی دیگرِ خلاف شهود: در ابعاد بالا هر جهت تقریباً بر هر جهت دیگر عمود است. دو بردار که تصادفی کشیده شوند تقریباً همیشه تقریباً عمودند.
قطر مکعب در برابر یک محور¶
بردار قطر فرامکعب را بگیرید. زاویهٔ میان این قطر و هر محور مختصات برابر است با:
با ، ، یعنی . قطر عملاً بر محورها عمود است!
افزون بر این، بردارهای تصادفی در ابعاد بالا تقریباً بر یکدیگر عمودند.
Source
dim = 200
# Generate random vectors
x = np.random.randn(4, dim)
# Normalize
x_norm = x / np.linalg.norm(x, axis=1)[:, np.newaxis]
print(f"Dot products of random pairs in {dim}-D:")
for i in range(len(x_norm)):
for j in range(i+1, len(x_norm)):
dp = np.dot(x_norm[i], x_norm[j])
print(f"Vector {i} . Vector {j} = {dp:.4f}")Dot products of random pairs in 200-D:
Vector 0 . Vector 1 = -0.0227
Vector 0 . Vector 2 = 0.0015
Vector 0 . Vector 3 = 0.0229
Vector 1 . Vector 2 = -0.0327
Vector 1 . Vector 3 = 0.0843
Vector 2 . Vector 3 = 0.0176
خلاصه¶
فضای با ابعاد بالا در مرکز خالی است.
حجم در گوشهها یا پوستهٔ نازکی نزدیک سطح است.
همسایهها دورند (که روشهای محلی مانند k-NN را میشکند).
بردارهای تصادفی عمودند.
محاسبات پشت این گزارهها — حجم پوسته، نمونهبرداری ردکردنی، نقطههای یکنواخت روی کره و درون گوی، و حلقهٔ گاوسی — در نمونهگیری در فضاهای با ابعاد بالا آمده است.
منابع¶
zaki2020data، فصل ۶ (فضای با ابعاد بالا).
Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of Data Science. Cambridge University Press.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning.
تمرینها¶
نسبت حجم گوی یکه به حجم مکعب را برای حساب کنید. در کدام بُعد گوی کمتر از حجم مکعب را میگیرد؟
برای دو بردار یکهٔ تصادفی در نشان دهید و هیستوگرام را برای و رسم کنید. این تمرکز برای معنای «نزدیکترین» و «دورترین» چه پیامی دارد؟
کسر حجم گوی در پوستهٔ را برحسب حساب کنید و پیامدش را برای نمونهبرداری یکنواخت در گوی ابعاد بالا توضیح دهید.
با استدلال همسایگی نوتبوک نشان دهید طول ضلع مکعبی که کسر ثابتی از نقطهها را در بر میگیرد مانند رشد میکند و آن را برای و حساب کنید.
