فضاهای با ابعاد بالا
فضاهای با ابعاد بالا¶

مجموعهداده یک ماتریس است — نقطه، مختصه — و در کار امروز اغلب بزرگ است: یک تصویر خاکستری یک نقطه در است، یک تعبیهٔ سند چند صد مختصه دارد، یک نمونهٔ ژنومی دهها هزار. فاصلهها، همسایگیها و مرکزها با همان فرمولهایی حساب میشوند که در صفحه به کار میبریم، ولی هندسهای که این فرمولها توصیف میکنند هندسهٔ صفحه نیست. تقریباً همهٔ حجم مکعب نزدیک گوشههایش است، تقریباً همهٔ حجم کره در پوستهٔ نازکی نزدیک سطحش، و نزدیکترین همسایهٔ یک نقطه تقریباً بهاندازهٔ دورترین همسایهاش دور است.
این بخش از درس همین شهود را میسازد، عدد رویش میگذارد، نشان میدهد با دو الگوریتمی که پیشتر به کار بردهایم — k نزدیکترین همسایه و k-means — چه میکند، و سپس پاسخ سازنده را میدهد: تصویرسازی تصادفی، که بُعد را کم میکند و فاصلهها را نگه میدارد، با لم جانسون–لیندناشتراوس بهعنوان تضمین. صفحهها به ترتیب فهرست:
| صفحه | چه میکند |
|---|---|
| دادهٔ با ابعاد بالا و نفرین ابعاد | نظریه: مکعب و کره در بُعد، مرکز خالی، همسایگیهای محلی و فاصله تا مرز، و جهتهای تصادفی که تقریباً عمودند. |
| نمونهگیری در فضاهای با ابعاد بالا | آزمایشگاه: آزمایش حجم پوستهٔ نازک، نمونهگیری ردکردنی و نسبت پذیرشش، نقطههای یکنواخت روی ابَرکره (بردارهای گاوسی نرمالشده) و درون گوی (شعاع با تبدیل معکوس)، و حلقهٔ گاوسی. |
| kNN در فضاهای با ابعاد بالا | یک آزمایش: دقت دستهبندی یک دستهبند ۵-همسایه روی دادهٔ ساختگی، وقتی تعداد ویژگیها از ۲ به ۱۰۰ میرسد. |
| k-means در فضاهای با ابعاد بالا | همان آزمایش برای خوشهبندی: شاخص رند تعدیلشدهٔ k-means در برابر برچسبهای واقعی، برحسب . |
| تصویرسازی تصادفی: نظریه و پیادهسازی | پاسخ سازنده: لم جانسون–لیندناشتراوس، ماتریسهای تصویر گاوسی و تُنُک (آچلیوپتاس)، آزمایش مقیاس ، بررسیای با Scikit-Learn که فاصلههای جفتی در تصویر میمانند، و مروری کوتاه بر حسگری فشرده. |
سه واقعیت پشت عنوان¶
۱. مکعب کره را میبلعد. برای نقطهٔ یکنواخت روی ، احتمال اینکه در گوی یکهٔ محاطی بیفتد نسبت این دو حجم است،
و این نسبت به صفر میل میکند. در ابعاد بالا یک مکعب عملاً همهاش گوشه است.
۲. کره یک پوسته است. همان محاسبه برای شعاع میدهد، برای هر ثابت،
برای و این احتمال از قبل 0.994 است: مرکز گوی خالی است و همهٔ نقطهها روی پوستشاند.
۳. نزدیکترین و دورترین همسایه شبیه هماند. با نقطه در مکعب یکه، فاصلهٔ معمول تا نزدیکترین همسایه با رشد میکند در حالی که قطر ثابت میماند، پس نسبت (دورترین فاصله) / (نزدیکترین فاصله) به 1 میل میکند. همسایگی دیگر محلی نیست: دیگر گوی کوچکی گرد نقطهٔ پرسش نیست، صفحهای است که تا سراسر مجموعهداده میرسد.
واقعیتهای ۱ و ۲ چیزی است که صفحهٔ اول اثبات و رسم میکند؛ واقعیت ۳ چیزی است که دو آزمایش اندازه میگیرند، یکبار برای یک دستهبند و یکبار برای یک خوشهبندی. صفحهٔ آخر بعد نشان میدهد همین تمرکز دلیلِ کارکرد تصویرسازی تصادفی است.
ترتیب خواندن و پیشنیازها¶
صفحهها باید به همان ترتیب بالا خوانده شوند. تنها پیشنیازها نرم اقلیدسی و فرمول فاصلهاند، هر دو از نرمها، بهعلاوهٔ این ایده — که در تصویر بهعنوان دادهٔ با ابعاد بالا آمده — که تصویر یک بردار و بنابراین نقطهای در فضای با ابعاد بالاست.
خواندن صفحهٔ نظریه اول مهم است: بی آن، دو آزمایش شبیه «الگوریتمهایی که بدتر میشوند» به نظر میرسند، در حالی که الگوریتمها دقیقاً همان کاری را میکنند که به آنها گفته شده و این فضا است که عوض شده. صفحهٔ نمونهگیری بعد همان گزارهها را به اندازهگیریهایی تبدیل میکند که خودتان میتوانید اجرا کنید. در جهت دیگر، صفحهٔ تصویرسازی تصادفی جایی است که همین واقعیتها به الگوریتم تبدیل میشوند، پس ارزش دارد صفحهٔ نظریه را پیش از آن بخوانید.
جایگاه این بخش در درس¶
دستهبندی و خوشهبندی. صفحهٔ kNN، k نزدیکترین همسایه و سنجههای ارزیابی دستهبندی، و صفحههای خوشهبندی، خوشهبندی، خوشهبندی k-means و خوشهبندی فراگیر، جایی است که این الگوریتمها تعریف میشوند. این بخش توضیح میدهد چرا رفتارشان با رشد بدتر میشود.
تقریب رتبه پایین و PCA. اگر فاصلهها اطلاعاتدهنده نباشند، یک پاسخ این است که در بُعد کمتر کار کنیم با نگه داشتن جهتهای بیشترین واریانس: تحلیل مؤلفهٔ اصلی، بخش ۱ و SVD برای فشردهسازی تصویر. تصویرسازی تصادفی جانشین ارزان و مستقل از دادهٔ همان ایده است، و این دو در پایان صفحهٔ آخر مقایسه میشوند.
تمرینها¶
سه واقعیت این صفحه را با چند خط NumPy عددی بررسی کنید: تمرکز فاصله، نسبت حجم کره و مکعب، و کسر پوستهٔ نازک.
با ترتیب خواندن دادهشده اینجا بگویید کدام صفحه را پیش از PCA لازم دارید، و چرا برای خوانندهای که هنوز مقدار ویژه ندیده این ترتیب مهم است.
از هر یک از سه صفحهٔ این بخش یک گزاره بنویسید که در دو بُعد هم برقرار میماند و یکی که ویژهٔ ابعاد بالاست.
منابع¶
A. Blum, J. Hopcroft, R. Kannan, Foundations of Data Science، فصلهای فضای با ابعاد بالا، تصویرسازی تصادفی و لم جانسون–لیندناشتراوس.
Achlioptas, D. (2003)، Database-friendly random projections: Johnson–Lindenstrauss with binary coins — ماتریسهای تصویر تُنُکِ صفحهٔ آخر.