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 · فارسی

نقشه‌های خودسازمان‌ده

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

جای این صفحه در درس

بند ۱۴.۴ از hastie2009esl (صص ۵۲۸–۵۳۳) آخرین روش خوشه‌بندی فصل است، و کتاب آن را با جمله‌ای معرفی می‌کند که خودش تعریفش هم هست: نقشهٔ خودسازمان‌ده (SOM) همان K-means است با این قید که پیش‌نمونه‌ها روی خمینه‌ای یک‌ یا دوبعدی در فضای ویژگی بمانند. همین قید است که نتیجه را به یک نقشه بدل می‌کند: پیش‌نمونه‌ها مختصات شبکه‌ای دارند، پس هر مشاهده را می‌توان روی نمایشی دوبعدی نشاند، و سلول‌های همسایهٔ نمایش مشاهده‌های مشابه را در خود دارند.

روش Kohonen از واژگان یادگیری ماشین پیرامونش قدیمی‌تر است، و هنوز ابزار استاندارد تصویرسازی مجموعه‌های سند است؛ WEBSOM، مثالی که بند با آن بسته می‌شود، نقشه‌ای از دوازده هزار مقالهٔ گروه خبری است.

در پایان باید بتوانید

  • یک SOM را شبکه‌ای از پیش‌نمونه‌ها توصیف کنید و به‌روزرسانی برخط (۱۴.۴۶) را بنویسید؛

  • بگویید شعاع همسایگی و نرخ یادگیری چه می‌کنند، و هر دو چگونه برنامه‌ریزی می‌شوند؛

  • به‌روزرسانی دسته‌ای (۱۴.۴۸) را بنویسید و نشان دهید وقتی همسایگی به یک سلول کوچک شود به K-means بدل می‌شود؛

  • با سنجیدن خطای بازسازی در برابر K-means داوری کنید که آیا قید دوبعدی روی مجموعه‌دادهٔ داده‌شده پذیرفتنی است.

۱. مدل

شبکه‌ای را ثابت کنید، مثلاً q1×q2q_1 \times q_2 سلول، و یک پیش‌نمونه mj∈Rpm_j \in \mathbb{R}^p برای هر سلول. هر پیش‌نمونه یک جفت مختصات صحیح j∈Q1×Q2j \in Q_1 \times Q_2 دارد — جایش روی نقشه، نه در فضای ویژگی. نقشه یک دستگاه مختصات دوبعدی است و پیش‌نمونه‌ها نقطه‌های فضای ویژگی‌اند که به سلول‌های آن نسبت داده شده‌اند.

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

۲. الگوریتم برخط

مشاهده‌ها یکی‌یکی پردازش می‌شوند. نزدیک‌ترین پیش‌نمونه به xix_i را در Rp\mathbb{R}^p بیابید، بعد آن و همسایه‌های نقشه‌ای‌اش را به‌سوی xix_i ببرید:

mk←mk+ε (xi−mk),for every mk with ∥j−k∥≤r.(14.46)m_k \leftarrow m_k + \varepsilon\,(x_i - m_k), \qquad \text{for every } m_k \text{ with } \lVert j - k \rVert \le r . \qquad \text{(14.46)}

همسایگی همیشه خود برنده را در بر دارد. شکل کلی گام را با فاصلهٔ نقشه وزن می‌دهد،

mk←mk+h(∥j−k∥) (xi−mk),(14.47)m_k \leftarrow m_k + h(\lVert j - k \rVert)\,(x_i - m_k), \qquad \text{(14.47)}

که hh در فاصلهٔ نقشه کاهش می‌یابد — گاوسی، یا نشانگر یک قرص.

هر دو برنامهٔ کتاب از درشت به ریز می‌روند: نرخ یادگیری ε\varepsilon در چند هزار تکرار از حدود 1.0 به 0 می‌افتد، و شعاع rr خطی از RR آغازین به 1 می‌رسد. همسایگی‌های بزرگ در آغاز نقشه را به‌طور کلی صاف می‌کنند؛ همسایگی‌های کوچک در پایان می‌گذارند ساختار محلی را برازش کند. این همان ایدهٔ بازپخت در LVQ است و همان هشدار هم صادق است: روش با برنامه‌اش تعریف می‌شود، نه با کمینه‌سازی یک معیار.

اگر rr به‌قدری کوچک باشد که هر همسایگی یک سلول شود، پیوند مکانی از دست می‌رود و الگوریتم به K-means برخط بدل می‌شود: به یکی از همان کمینه‌های محلی‌ای همگرا می‌شود که K-means هم می‌یابد. این همان معنایی است که SOM را K-means مقید می‌داند، و همچنین می‌گوید قید را روی یک مسئله چگونه بسنجید:

reconstruction error=∑i∥xi−mj(i)∥2.\text{reconstruction error} = \sum_i \lVert x_i - m_{j(i)} \rVert^2 .

این خطا برای SOM ناگزیر بزرگ‌تر از K-means با همان تعداد پیش‌نمونه است. اگر بسیار بزرگ‌تر باشد، نقشهٔ دوبعدی توصیف بدی از داده است.

۳. یک مثال حل‌شده: سه خوشه روی نیم‌کره

مثال کتاب ۹۰ نقطه در R3\mathbb{R}^3 نزدیک سطح نیم‌کره‌ای به شعاع ۱ است، در سه خوشه نزدیک (0,1,0)(0,1,0)، (0,0,1)(0,0,1) و (1,0,0)(1,0,0). خوشهٔ سرخ عامدانه بسیار جمع‌وجورتر از دو خوشهٔ دیگر است، و همین است که نقشهٔ برازش‌شده را روی خودش تا می‌زند.

<Figure size 550x500 with 1 Axes>

پیش‌نمونه‌ها روی دو مؤلفهٔ اصلی نخستین مقداردهی می‌شوند و در گسترهٔ داده پخش می‌شوند — همان «دکمه‌های دوخته روی صفحهٔ» این بند.

prototypes: (25, 3)  map coordinates: (25, 2)

حلقهٔ آموزش عیناً (۱۴.۴۶) است: ۴۰ گذر روی ۹۰ مشاهده، یعنی ۳۶۰۰ تکرار، با ε\varepsilon و rr که در این تکرارها خطی کاهش می‌یابند.

reconstruction error after training: 0.636
K-means with the same 25 prototypes : 0.124

این دو عدد همان سنجشی است که کتاب می‌خواهد، و اینجا بسیار از هم دورند: برازش مقید حدوداً پنج برابر هزینه دارد. این بهای پخش یکنواخت ۲۵ دکمه روی سطحی است که داده‌اش در سه تودهٔ تنگ نشسته — شبکه نمی‌تواند همهٔ سلول‌هایش را روی توده‌ها خرج کند. دادهٔ خود کتاب پخش‌تر است و SOM آن در حدود یک‌چهارم K-means تمام می‌شود (شکل ۱۴.۱۸)؛ این نسبت خاصیت داده است، نه پیاده‌سازی، و خواندنش همان راهی است که تصمیم می‌گیرید نقشهٔ دوبعدی توصیف منصفانه‌ای از دادهٔ شما هست یا نه.

۴. خواندن نقشه

نمایش همان شبکه است. هر سلول مشاهده‌های نزدیک‌ترین به پیش‌نمونه‌اش را در خود دارد، که در جایگاه‌های تصادفی درون سلول کشیده می‌شوند — چیدمان شکل ۱۴.۱۶. پنل چپ نقشهٔ آغازین و پنل راست نقشهٔ آموزش‌دیده است.

<Figure size 900x420 with 2 Axes>

نقشهٔ آموزش‌دیده سه رنگ را در نواحی همسایه جدا کرده، و این کار را با مرزی صاف کرده است: سلول‌های مجاور مشاهده‌های مشابه دارند. همین خاصیتی است که K-means ندارد — برچسب‌هایش هیچ مجاورتی حمل نمی‌کنند، پس همان ۲۵ مرکز می‌توانستند دلبخواه جابه‌جا شوند و معنایشان عوض نشود.

چیزی که نقشه نشان نمی‌دهد چگالی یا اندازه است. خوشهٔ سرخ بسیار جمع‌وجورتر از دو خوشهٔ دیگر است و هیچ چیز در نمایش این را نمی‌گوید، چون فاصله‌های به‌کاررفته در چیدمان، فاصله‌های نقشه‌اند. کتاب همین نکته را دربارهٔ شکل ۱۴.۱۶ می‌گوید.

۵. شبکه در فضای ویژگی

کشیدن پیش‌نمونه‌ها و یال‌های شبکه در R3\mathbb{R}^3 نشان می‌دهد «خم‌کردن صفحه» هندسی چه معنایی دارد. جایی که سطح باید روی خودش تا بخورد تا به خوشهٔ تنگ سرخ برسد، یال‌ها روی هم می‌افتند — همان تای شکل ۱۴.۱۷.

<Figure size 600x550 with 1 Axes>

۶. خطای بازسازی در مسیر

منحنی‌ای که قید را توجیه می‌کند خطای بازسازی برحسب شمارهٔ تکرار است، با مقدار K-means به‌صورت خطی افقی (شکل ۱۴.۱۸).

<Figure size 650x400 with 1 Axes>

خطا تا وقتی همسایگی پهن است سریع می‌افتد — نقشه دارد باز می‌شود — و به سطح K-means نزدیک می‌شود بی‌آنکه به آن برسد. خواندن بخش آخر منحنی راه صادقانهٔ پاسخ به «آیا نقشهٔ دوبعدی برای این داده مناسب است؟» است، و این پرسشی دربارهٔ داده است، نه دربارهٔ الگوریتم.

۷. نسخهٔ دسته‌ای، و نسبتش با K-means

بازمحاسبهٔ پیش‌نمونه به‌صورت میانگین وزنی مشاهده‌هایی که به همسایه‌هایش نگاشت شده‌اند SOM دسته‌ای را می‌دهد:

mj=∑kwkxk∑kwk,(14.48)m_j = \frac{\sum_k w_k x_k}{\sum_k w_k}, \qquad \text{(14.48)}

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

  • همسایگی مستطیلی با شعاع ۰ به‌روزرسانی را به «هر پیش‌نمونه را با میانگین مشاهده‌های خودش جانشین کن» بدل می‌کند، که همان K-means است؛

  • ww صاف و شعاع کوچک‌شونده SOM دسته‌ای را به نسخه‌ای گسسته از خم‌های اصلی بدل می‌کند، که موضوع بعدی کتاب پس از این بند است.

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

۸. کجا به کار می‌رود

مثال پایانی بند WEBSOM است: ۱۲ ۰۸۸ مقاله از comp.ai.neural-nets، هر یک به برداری تُنُک از بسامد نسبی واژه‌ها بر واژه‌نامه‌ای با ده‌ها هزار واژه (یا جفت واژه) بدل می‌شود، به‌اختیار با SVD تصادفی کاهش می‌یابد، و بعد روی شبکه‌ای نگاشت می‌شود که سلول‌هایش از محتوایشان خودکار برچسب می‌گیرند. نقشه نمایه‌ای مرورشدنی است — نزدیک‌شدن روی یک سلول مقاله‌هایش را نشان می‌دهد — و همان کاربردی است که روش برایش ساخته شد: نه افراز کردن برای خودش، بلکه چیدن مجموعه‌ای بزرگ چنان که چیزهای مشابه در یک صفحه نزدیک هم باشند.

خلاصه

  • SOM شبکه‌ای از پیش‌نمونه‌ها با مختصات نقشه است؛ به‌روزرسانی پیش‌نمونهٔ برنده و همسایه‌های نقشه‌ای‌اش را به‌سوی مشاهده می‌برد (۱۴.۴۶).

  • نرخ یادگیری و شعاع همسایگی هر دو کاهش می‌یابند؛ برنامه بخشی از تعریف است، و همین دلیل این است که روش معیاری برای بهینه‌کردن ندارد.

  • با همسایگی تک‌سلولی الگوریتم K-means برخط است؛ شکل دسته‌ای (۱۴.۴۸) با شعاع ۰ دقیقاً K-means است.

  • خطای اضافه بر K-means بهای قید دوبعدی را می‌سنجد، و خواندنش راه تصمیم دربارهٔ مناسب بودن نقشه است.

  • خروجی نمایشی است که سلول‌های همسایه‌اش مشابه‌اند — همان خاصیتی که روش را برای مرور مجموعه‌های بزرگ سودمند می‌کند.

تمرین‌ها

  1. از آغاز با R0=0R_0 = 0 آموزش دهید. منحنی خطا و نقشه را با برچسب‌های K-means که روی شبکه بازچیده شده‌اند بسنجید. چه چیزی از دست رفته است؟

  2. همسایگی سخت (۱۴.۴۶) را با گاوسی h(d)=exp⁡(−d2/2r2)h(d) = \exp(-d^2/2r^2) از (۱۴.۴۷) جانشین کنید و خطاهای بازسازی نهایی را بسنجید.

  3. اندازهٔ شبکه را (3×33\times3، 5×55\times5، 8×88\times8) با دادهٔ ثابت تغییر دهید. خطا چگونه به خط K-means نزدیک می‌شود، و نقشه در 3×33\times3 چه شکلی است؟

  4. از شبکهٔ شش‌گوش استفاده کنید (شش همسایه در هر سلول به‌جای چهار). آیا نمایش بهتر می‌شود، و خطا فرق می‌کند؟

  5. SOM را روی دادهٔ ۱۰۰-بعدی (مثلاً ارقام) اجرا کنید و بسنجید جواب مقید چه‌قدر بدتر است. آیا نقشهٔ دوبعدی هنوز قابل دفاع است؟

  6. نسخهٔ دسته‌ای (۱۴.۴۸) را با شعاع ۱ پیاده کنید و شمار تکرارهای لازم برای رسیدن به همان خطای نسخهٔ برخط را بسنجید.

منابع

  • تعریف، (۱۴.۴۶)–(۱۴.۴۸)، مثال نیم‌کره با شکل‌های ۱۴.۱۵–۱۴.۱۸، و کاربرد WEBSOM: بند ۱۴.۴ از hastie2009esl، صص ۵۲۸–۵۳۳.

  • نسبتش با K-means همان است که در Clustering-Part2 به کار رفت؛ مبادلهٔ برخط و دسته‌ای همان است که در پرسپترون و یادگیری برخط بحث شد.

  • شرح خود Kohonen از روش، و مقاله‌های WEBSOM، همان ارجاع‌هایی هستند که در بند داده شده‌اند.