Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

دادهٔ با ابعاد بالا و نفرین ابعاد

English · فارسی

دادهٔ با ابعاد بالا و نفرین ابعاد

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

مقدمه

در داده‌کاوی و یادگیری ماشین امروز، بارها با داده در فضاهای بسیار ابعاد بالا سروکار داریم (برای مثال تصویرها، تعبیه‌های متنی، دادهٔ ژنومی). مجموعه‌داده معمولاً با ماتریس n×dn \times d مانند D\mathbf{D} نمایش داده می‌شود.

شناخت ماهیت فضای با ابعاد بالا، یا فرافضا، بسیار مهم است، چون مانند هندسهٔ آشنای دو یا سه بُعد رفتار نمی‌کند. این پدیده را اغلب نفرین ابعاد می‌نامند.

پدیده‌های کلیدی که بررسی می‌کنیم:

  1. تمرکز حجم: حجم ابَرکره نسبت به فرامکعب به صفر میل می‌کند.

  2. مسئلهٔ همسایگی‌های محلی: چرا روش‌های «محلی» مانند k-NN شکست می‌خورند (بر پایهٔ Elements of Statistical Learning).

  3. پوستهٔ نازک: بیشتر حجم نزدیک سطح جمع می‌شود (اندازه‌گیری در صفحهٔ نمونه‌گیری).

  4. تعامد: بردارهای تصادفی در ابعاد بالا تقریباً عمود بر هم‌اند.

  5. رفتار گاوسی: نقطه‌ها در حلقهٔ نازکی گرد شعاع d\sqrt{d} جمع می‌شوند — این هم در صفحهٔ نمونه‌گیری اندازه‌گیری می‌شود.


هندسهٔ فرافضا: مکعب‌ها و کره‌ها

دو شکل بنیادی در dd بُعد را تعریف کنیم.

فرامکعب

فضای داده را اغلب یک فرامستطیل یا فرامکعب dd-بُعدی می‌گیرند. برای فرامکعب Hd(l)H_d(l) با ضلع ll، حجم برابر است با:

Vol(Hd(l))=ld\text{Vol}(H_d(l)) = l^d

ابَرکره

گوی توپر را Bd(r)B_d(r) و سطح آن را Sd(r)S_d(r) می‌نویسیم. این تمایز مهم است: حجم زیر از آنِ گوی است و مرز آن لایه‌ای با اندازهٔ صفر است. حجم گوی dd-بُعدی با شعاع rr برابر است با:

Vol(Sd(r))=Kdrd=πd/2Γ(d2+1)rd\text{Vol}(S_d(r)) = K_d r^d = \frac{\pi^{d/2}}{\Gamma(\frac{d}{2}+1)} r^d

که در آن Γ\Gamma تابع گاما است.

شکل ۶.۴. ابَرکرهٔ محاط در فرامکعب: در (الف) دو و (ب) سه بُعد

مرکز خالی (اثر «خارپشت»)

فضای درون بزرگ‌ترین ابَرکره‌ای را در نظر بگیرید که در فرامکعبی با ضلع l=2rl=2r جا می‌شود. نسبت حجم‌هایشان چنین است:

lim⁡d→∞Vol(Sd(r))Vol(Hd(2r))=lim⁡d→∞πd/22dΓ(d2+1)→0\lim_{d \to \infty} \frac{\text{Vol}(S_d(r))}{\text{Vol}(H_d(2r))} = \lim_{d \to \infty} \frac{\pi^{d/2}}{2^d \Gamma(\frac{d}{2}+1)} \to 0

پیامد: با افزایش بُعد، حجم ابَرکره در برابر فرامکعب ناچیز می‌شود. بیشتر حجم فرامکعب در گوشه‌ها است و مرکز عملاً خالی می‌ماند.

گوشه‌ها در ابعاد بالا

نمایی مفهومی از فضای با ابعاد بالا: (الف) دو، (ب) سه، (ج) چهار و (د) بُعدهای بالاتر. در dd بُعد 2d2^d «گوشه» و 2d−12^{d−1} قطر داریم. شعاع دایرهٔ محاطی تفاوت حجم فرامکعب و ابَرکرهٔ محاطی را در dd بُعد به‌درستی نشان می‌دهد.


Source
<Figure size 1000x600 with 1 Axes>

مسئلهٔ همسایگی‌های محلی (k-NN)

یکی از مهم‌ترین جلوه‌های نفرین ابعاد، روش‌های «محلی» مانند k نزدیک‌ترین همسایه (k-NN) را هدف می‌گیرد.

طول ضلع همسایگی‌ها

فرض کنید ورودی‌ها به‌طور یکنواخت در فرامکعبی یکه با pp بُعد توزیع شده‌اند. می‌خواهیم همسایگی محلی‌ای بسازیم که کسری rr از مشاهدات را در بر گیرد. چون این کسر حجمِ یکه است، امید ریاضی طول ضلع ep(r)e_p(r) این همسایگی چنین است:

ep(r)=r1/pe_p(r) = r^{1/p}

شکل ۲.۶. نفرین ابعاد را به‌خوبی با یک همسایگی زیرمکعبی برای دادهٔ یکنواخت در مکعب یکه نشان می‌دهند. شکل سمت راست طول ضلع زیرمکعبی را نشان می‌دهد که برای در بر گرفتن کسری rr از حجم داده لازم است، برای بُعدهای مختلف pp. در ده بُعد باید ۸۰٪ دامنهٔ هر مختصه را بپوشانیم تا ۱۰٪ داده را در بر بگیریم

بیایید این را برای بُعدهای مختلف (pp) و کسرهای مختلف (rr) ببینیم.

Source
<Figure size 800x600 with 1 Axes>

تحلیل: در ده بُعد (p=10p=10)، برای در بر گرفتن تنها ۱۰٪ (r=0.1r=0.1) داده، باید ۸۰٪ دامنهٔ هر متغیر ورودی را بپوشانیم. چنین همسایگی‌هایی دیگر «محلی» نیستند. برای یافتن همسایه باید بسیار دور را نگاه کرد.

فاصله تا مرز

پیامد دیگر، تُنُکی چگالی نمونه‌برداری است. برای NN نقطهٔ داده در گوی یکهٔ pp-بُعدی، میانهٔ فاصلهٔ مبدأ تا نزدیک‌ترین نقطهٔ داده برابر است با:

d(p,N)=(1−(12)1/N)1/pd(p,N) = \left(1 - \left(\tfrac{1}{2}\right)^{1/N}\right)^{1/p}

برای N=500N=500 و p=10p=10 این فاصله حدود ≈0.52\approx 0.52 است، یعنی بیش از نیمهٔ راه تا مرز. پس بیشتر نقطه‌های داده به مرز فضای نمونه نزدیک‌ترند تا به هر نقطهٔ دادهٔ دیگر. همین پیش‌بینی را از یک مسئلهٔ برون‌یابی به جای درون‌یابی می‌کند.



تعامد: جهت‌های تصادفی تقریباً عمودند

ویژگی دیگرِ خلاف شهود: در ابعاد بالا هر جهت تقریباً بر هر جهت دیگر عمود است. دو بردار که تصادفی کشیده شوند تقریباً همیشه تقریباً عمودند.

قطر مکعب در برابر یک محور

بردار قطر فرامکعب را 1=(1,1,…,1)T\mathbf{1} = (1, 1, \dots, 1)^T بگیرید. زاویهٔ θd\theta_d میان این قطر و هر محور مختصات e1=(1,0,…,0)T\mathbf{e}_1 = (1, 0, \dots, 0)^T برابر است با:

cos⁡θd=e1T1∣∣e1∣∣⋅∣∣1∣∣=11⋅d=1d\cos \theta_d = \frac{\mathbf{e}_1^T \mathbf{1}}{||\mathbf{e}_1|| \cdot ||\mathbf{1}||} = \frac{1}{1 \cdot \sqrt{d}} = \frac{1}{\sqrt{d}}

با d→∞d \to \infty، cos⁡θd→0\cos \theta_d \to 0، یعنی θd→90∘\theta_d \to 90^\circ. قطر عملاً بر محورها عمود است!

افزون بر این، بردارهای تصادفی در ابعاد بالا تقریباً بر یکدیگر عمودند.

Source
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 را می‌شکند).

  • بردارهای تصادفی عمودند.

محاسبات پشت این گزاره‌ها — حجم پوسته، نمونه‌برداری ردکردنی، نقطه‌های یکنواخت روی کره و درون گوی، و حلقهٔ گاوسی — در نمونه‌گیری در فضاهای با ابعاد بالا آمده است.

منابع

  1. zaki2020data، فصل ۶ (فضای با ابعاد بالا).

  2. Blum, A., Hopcroft, J., & Kannan, R. (2020). Foundations of Data Science. Cambridge University Press.

  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning.

تمرین‌ها

  1. نسبت حجم گوی یکه به حجم مکعب [−1,1]d[-1,1]^d را برای d=2,10,100d=2,10,100 حساب کنید. در کدام بُعد گوی کمتر از 1%1\% حجم مکعب را می‌گیرد؟

  2. برای دو بردار یکهٔ تصادفی در Rd\mathbb{R}^d نشان دهید E[cos⁡2θ]=1/d\mathbb{E}[\cos^2\theta]=1/d و هیستوگرام cos⁡θ\cos\theta را برای d=2d=2 و d=100d=100 رسم کنید. این تمرکز برای معنای «نزدیک‌ترین» و «دورترین» چه پیامی دارد؟

  3. کسر حجم گوی در پوستهٔ 0.9≤r≤10.9\le r\le 1 را برحسب dd حساب کنید و پیامدش را برای نمونه‌برداری یکنواخت در گوی ابعاد بالا توضیح دهید.

  4. با استدلال همسایگی نوت‌بوک نشان دهید طول ضلع مکعبی که کسر ثابتی pp از نقطه‌ها را در بر می‌گیرد مانند p1/dp^{1/d} رشد می‌کند و آن را برای p=0.01p=0.01 و d=100d=100 حساب کنید.