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 است — nn نقطه، dd مختصه — و در کار امروز dd اغلب بزرگ است: یک تصویر خاکستری 200×300200\times300 یک نقطه در R60 000\mathbb{R}^{60\,000} است، یک تعبیهٔ سند چند صد مختصه دارد، یک نمونهٔ ژنومی ده‌ها هزار. فاصله‌ها، همسایگی‌ها و مرکزها با همان فرمول‌هایی حساب می‌شوند که در صفحه به کار می‌بریم، ولی هندسه‌ای که این فرمول‌ها توصیف می‌کنند هندسهٔ صفحه نیست. تقریباً همهٔ حجم مکعب نزدیک گوشه‌هایش است، تقریباً همهٔ حجم کره در پوستهٔ نازکی نزدیک سطحش، و نزدیک‌ترین همسایهٔ یک نقطه تقریباً به‌اندازهٔ دورترین همسایه‌اش دور است.

این بخش از درس همین شهود را می‌سازد، عدد رویش می‌گذارد، نشان می‌دهد با دو الگوریتمی که پیش‌تر به کار برده‌ایم — k نزدیک‌ترین همسایه و k-means — چه می‌کند، و سپس پاسخ سازنده را می‌دهد: تصویرسازی تصادفی، که بُعد را کم می‌کند و فاصله‌ها را نگه می‌دارد، با لم جانسون–لیندن‌اشتراوس به‌عنوان تضمین. صفحه‌ها به ترتیب فهرست:

صفحهچه می‌کند
دادهٔ با ابعاد بالا و نفرین ابعادنظریه: مکعب و کره در dd بُعد، مرکز خالی، همسایگی‌های محلی و فاصله تا مرز، و جهت‌های تصادفی که تقریباً عمودند.
نمونه‌گیری در فضاهای با ابعاد بالاآزمایشگاه: آزمایش حجم پوستهٔ نازک، نمونه‌گیری ردکردنی و نسبت پذیرشش، نقطه‌های یکنواخت روی ابَرکره (بردارهای گاوسی نرمال‌شده) و درون گوی (شعاع با تبدیل معکوس)، و حلقهٔ گاوسی.
kNN در فضاهای با ابعاد بالایک آزمایش: دقت دسته‌بندی یک دسته‌بند ۵-همسایه روی دادهٔ ساختگی، وقتی تعداد ویژگی‌ها از ۲ به ۱۰۰ می‌رسد.
k-means در فضاهای با ابعاد بالاهمان آزمایش برای خوشه‌بندی: شاخص رند تعدیل‌شدهٔ k-means در برابر برچسب‌های واقعی، برحسب dd.
تصویرسازی تصادفی: نظریه و پیاده‌سازیپاسخ سازنده: لم جانسون–لیندن‌اشتراوس، ماتریس‌های تصویر گاوسی و تُنُک (آچلیوپتاس)، آزمایش مقیاس 1/k1/\sqrt{k}، بررسی‌ای با Scikit-Learn که فاصله‌های جفتی در تصویر می‌مانند، و مروری کوتاه بر حس‌گری فشرده.

سه واقعیت پشت عنوان

۱. مکعب کره را می‌بلعد. برای نقطهٔ XX یکنواخت روی [−1,1]d[-1,1]^d، احتمال اینکه در گوی یکهٔ محاطی بیفتد نسبت این دو حجم است،

P(∥X∥≤1)=Vd2d,Vd=πd/2Γ ⁣(d2+1),\mathbb{P}(\|X\|\le 1) = \frac{V_d}{2^d}, \qquad V_d = \frac{\pi^{d/2}}{\Gamma\!\left(\frac{d}{2}+1\right)},

و این نسبت به صفر میل می‌کند. در ابعاد بالا یک مکعب عملاً همه‌اش گوشه است.

۲. کره یک پوسته است. همان محاسبه برای شعاع می‌دهد، برای هر ϵ>0\epsilon>0 ثابت،

P(∥X∥>1−ϵ)=1−(1−ϵ)d→d→∞1.\mathbb{P}(\|X\| > 1-\epsilon) = 1-(1-\epsilon)^d \xrightarrow[d\to\infty]{} 1 .

برای d=100d=100 و ϵ=0.05\epsilon=0.05 این احتمال از قبل 0.994 است: مرکز گوی خالی است و همهٔ نقطه‌ها روی پوستش‌اند.

۳. نزدیک‌ترین و دورترین همسایه شبیه هم‌اند. با nn نقطه در مکعب یکه، فاصلهٔ معمول تا نزدیک‌ترین همسایه با dd رشد می‌کند در حالی که قطر ثابت می‌ماند، پس نسبت (دورترین فاصله) / (نزدیک‌ترین فاصله) به 1 میل می‌کند. همسایگی دیگر محلی نیست: دیگر گوی کوچکی گرد نقطهٔ پرسش نیست، صفحه‌ای است که تا سراسر مجموعه‌داده می‌رسد.

واقعیت‌های ۱ و ۲ چیزی است که صفحهٔ اول اثبات و رسم می‌کند؛ واقعیت ۳ چیزی است که دو آزمایش اندازه می‌گیرند، یک‌بار برای یک دسته‌بند و یک‌بار برای یک خوشه‌بندی. صفحهٔ آخر بعد نشان می‌دهد همین تمرکز دلیلِ کارکرد تصویرسازی تصادفی است.

ترتیب خواندن و پیش‌نیازها

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

خواندن صفحهٔ نظریه اول مهم است: بی آن، دو آزمایش شبیه «الگوریتم‌هایی که بدتر می‌شوند» به نظر می‌رسند، در حالی که الگوریتم‌ها دقیقاً همان کاری را می‌کنند که به آن‌ها گفته شده و این فضا است که عوض شده. صفحهٔ نمونه‌گیری بعد همان گزاره‌ها را به اندازه‌گیری‌هایی تبدیل می‌کند که خودتان می‌توانید اجرا کنید. در جهت دیگر، صفحهٔ تصویرسازی تصادفی جایی است که همین واقعیت‌ها به الگوریتم تبدیل می‌شوند، پس ارزش دارد صفحهٔ نظریه را پیش از آن بخوانید.

جایگاه این بخش در درس

تمرین‌ها

  1. سه واقعیت این صفحه را با چند خط NumPy عددی بررسی کنید: تمرکز فاصله، نسبت حجم کره و مکعب، و کسر پوستهٔ نازک.

  2. با ترتیب خواندن داده‌شده اینجا بگویید کدام صفحه را پیش از PCA لازم دارید، و چرا برای خواننده‌ای که هنوز مقدار ویژه ندیده این ترتیب مهم است.

  3. از هر یک از سه صفحهٔ این بخش یک گزاره بنویسید که در دو بُعد هم برقرار می‌ماند و یکی که ویژهٔ ابعاد بالاست.

منابع