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.

مسائل عملی: مقدارهای آغازین و انتخاب K

English · فارسی

مسائل عملی: مقدارهای آغازین و انتخاب KK

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

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

بند ۱۴.۳.۱۱ از hastie2009esl (صص ۵۱۸–۵۲۰) دو پرسشی را جمع می‌کند که K-means و K-medoids خودشان نمی‌توانند پاسخ دهند:

  1. از کجا شروع کنیم، یعنی مجموعهٔ آغازین مرکزها {m1,…,mK}\{m_1,\dots,m_K\} یا اندیس‌های {i1,…,iK}\{i_1,\dots,i_K\}؛

  2. چند خوشه، وقتی مسئله KK را نمی‌دهد.

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

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

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

  • مقدارگذاری آغازین گام‌به‌گام رو به جلو را توصیف کنید و بگویید چه چیزی بیش از شروع‌های تصادفی می‌خرد؛

  • توضیح دهید چرا اعتبارسنجی متقاطع نمی‌تواند KK را برای خوشه‌بندی برگزیند؛

  • آمارهٔ شکاف را از ایدهٔ شکستگی به دست آورید و قاعدهٔ (۱۴.۳۹) را بیان کنید؛

  • نمودار شکاف را بخوانید، با میله‌های خطا.

۱. مقدارهای آغازین

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

آزمایش زیر دو راهبرد را روی داده‌ای مقایسه می‌کند که تفاوت را نشان می‌دهد: سه گروه که آن‌قدر نزدیک‌اند که برخی شروع‌ها به پیکربندی نادرست همگرا می‌شوند.

random starts (50 runs): best    320.8  median    323.7  worst    380.6
runs above the median  : 25 of 50
forward stepwise       :    325.3

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

۲. انتخاب KK: شکستگی، و چرا اعتبارسنجی متقاطع شکست می‌خورد

رویکرد داده‌بنیان این است که نامتشابهی درون‌خوشه‌ای WKW_K را برای K=1,2,…,Kmax⁡K = 1, 2, \dots, K_{\max} حساب کنیم و منحنی را ببینیم. همیشه کاهش می‌یابد. دلیلش این نیست که خوشه‌های بیشتر از نظر آماری بهتر برازش می‌شوند، و کتاب دقیق است: حتی روی مجموعهٔ آزمون مستقل هم معیار کاهش می‌یابد، چون «تعداد زیادی مرکز خوشه گرایش دارند فضای ویژگی را چگال پر کنند و در نتیجه به همهٔ نقطه‌های داده نزدیک باشند». بهایی از بابت مجموعهٔ آزمون پرداخت نمی‌شود، پس درمان معمول یادگیری ماشین — کنار گذاشتن داده — اصلاً KK را برنمی‌گزیند. سلول زیر این را نشان می‌دهد.

 K     W_K on the held-out data
 1                      321.9
 2                      177.6
 3                      124.8
 4                       85.9
 5                       69.9
 6                       61.3
 7                       57.0
 8                       44.9

از بالا به پایین یکنوا کاهش می‌یابد، پس کمینه همیشه K=Kmax⁡K = K_{\max} است. خوشه‌بندی پیش‌بینی نیست: چیزی برای پیش‌بینی و خطای کنارگذاشته‌شده‌ای برای پرداخت بهای بیش‌برازش وجود ندارد.

کتاب در عوض از شکل منحنی بهره می‌برد. اگر داده واقعاً Kˉ\bar K گروه داشته باشد، آن‌گاه برای K<KˉK < \bar K الگوریتم باید گروه‌های دور از هم را در هم بیامیزد و هر خوشهٔ اضافه WW را بسیار کم می‌کند؛ برای K>KˉK > \bar K خوشهٔ اضافه گروهی را که از قبل جمع‌وجور است می‌شکند و کاهش کوچک است. پس تفاوت‌های متوالی WK−WK+1W_K - W_{K+1} در Kˉ\bar K به‌شدت می‌افتند، و همین «شکستگی» است — و روشی ابتکاری. مثال تومور ضدِمثال صادقانه است: منحنی آنجا اصلاً شکستگی ندارد و کتاب فقط برای نمایش K=3K = 3 را برمی‌گزیند.

۳. آمارهٔ شکاف

آمارهٔ شکاف شکستگی چشمی را با یک منحنی مرجع جانشین می‌کند. برای هر KK مقدار مشاهده‌شدهٔ log⁡WK\log W_K را با مقدار مورد انتظار در حالتی مقایسه کنید که داده هیچ خوشه‌ای نداشته باشد، که از نمونه‌گیری یکنواخت در جعبه‌ای که داده را در بر دارد به دست می‌آید:

G(K)=1B∑b=1Blog⁡WK(b)−log⁡WK,G(K) = \frac{1}{B}\sum_{b=1}^{B} \log W_K^{(b)} - \log W_K ,

که در آن WK(b)W_K^{(b)} روی نمونهٔ یکنواخت bbام حساب می‌شود. اگر داده یک تودهٔ واحد باشد، دو منحنی نزدیک‌اند و G(K)G(K) نزدیک صفر می‌ماند. اگر Kˉ\bar K گروه باشد، منحنی مشاهده‌شده تا Kˉ\bar K سریع‌تر از مرجع می‌افتد و بعد موازی با آن پیش می‌رود، پس شکاف اوج می‌گیرد و سپس صاف می‌شود.

میلهٔ خطا شبیه‌سازی را در نظر می‌گیرد، با sKs_K انحراف معیار log⁡WK\log W_K روی BB نمونه:

sK′=sK1+1/B,K^=arg⁡min⁡{K:G(K)≥G(K+1)−sK+1′}.(14.39)s'_K = s_K \sqrt{1 + 1/B}, \qquad \hat K = \arg\min \left\{ K : G(K) \ge G(K+1) - s'_{K+1} \right\}. \qquad \text{(14.39)}

قاعده «بیشینه را بگیر» نیست: کوچک‌ترین KKای را می‌گیرد که شکافش در فاصلهٔ یک میله خطا از شکاف بعدی است، که همان نسخهٔ رسمی «وقتی منحنی صاف شد بایست» است. و وقتی داده یک خوشه داشته باشد هم کار می‌کند — آن‌گاه K^=1\hat K = 1 — که همان حالتی است که روش شکستگی چیزی برای اشاره ندارد.

K = 1:  gap = -0.506   error bar = 0.083
K = 2:  gap = -0.385   error bar = 0.083
K = 3:  gap =  3.028   error bar = 0.078
K = 4:  gap =  2.865   error bar = 0.053
K = 5:  gap =  2.795   error bar = 0.069
K = 6:  gap =  2.782   error bar = 0.079
K = 7:  gap =  2.802   error bar = 0.073
K = 8:  gap =  2.833   error bar = 0.058

Gap estimate of K: 3

برآورد چاپ‌شده کوچک‌ترین KKای است که شکافش در فاصلهٔ یک میله خطا از شکاف بعدی است، و اینجا همان تعداد گروه‌هایی است که داده از آن‌ها ساخته شده. به شکل آن توجه کنید. برای K=1K = 1 و K=2K = 2 شکاف منفی است: دادهٔ مشاهده‌شده سه گروه جمع‌وجور پخش‌شده در جعبه‌ای بزرگ است، در حالی که مرجع یک تودهٔ پخش است، پس یک یا دو مرکز مرجع را بهتر از دادهٔ اصلی توصیف می‌کنند. در K=3K = 3 منحنی مشاهده‌شده فرو می‌ریزد و شکاف بیش از سه واحد می‌جهد — همان شکستگی، ولی سنجیده در برابر یک مرجع نه حدس‌زده با چشم. پس از آن دو منحنی موازی می‌روند و شکاف صاف است.

<Figure size 1100x400 with 2 Axes>

۴. چه چیزی گزارش کنیم

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

  • تمام منحنی WKW_K را گزارش کنید، نه فقط KK برگزیده را؛

  • بگویید کدام قاعده KK را برگزید — خود مسئله (شرکتی با KK فروشنده)، شکستگی، آمارهٔ شکاف، یا یک سنجهٔ اعتبارسنجی؛

  • پایداری را بسنجید: روی نمونه‌های بوت‌استرپ دوباره خوشه‌بندی کنید و ببینید همان گروه‌ها بازمی‌گردند؛

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

خلاصه

  • مقدارگذاری آغازین یک انتخاب است: شروع‌های تصادفی تکرار می‌خواهند، گام‌به‌گام رو به جلو مرکزها را یکی‌یکی و چنان برمی‌گزیند که معیار کمینه شود و معمولاً نزدیک بهترین جوابی می‌افتد که شروع‌های تصادفی متعدد می‌یابند.

  • WKW_K حتی روی دادهٔ کنارگذاشته‌شده یکنوا کاهش می‌یابد، چون مرکزها فضای ویژگی را پر می‌کنند؛ پس اعتبارسنجی متقاطع نمی‌تواند KK را برگزیند.

  • شکستگی در WKW_K یا در log⁡WK\log W_K پاسخ ابتکاری است، و می‌تواند غایب باشد — مانند مثال تومور.

  • آمارهٔ شکاف log⁡WK\log W_K را با یک مرجع یکنواخت مقایسه می‌کند و (۱۴.۳۹) کوچک‌ترین KK را در فاصلهٔ یک میله خطا از بعدی برمی‌گزیند؛ وقتی جواب درست یک خوشه باشد هم یک خوشه برمی‌گرداند.

  • هر قاعده‌ای به کار می‌برید، منحنی و قاعده را گزارش کنید.

تمرین‌ها

  1. دویست شروع تصادفی روی دادهٔ بخش ۱ اجرا کنید و هیستوگرام مقدارهای نهایی را رسم کنید. چند کمینهٔ محلی متمایز هست؟

  2. قاعدهٔ شکستگی را کد کنید: نخستین KKای که WK−WK+1W_K - W_{K+1} زیر کسری از تفاوت قبلی بیفتد. پاسخ چقدر به آن کسر حساس است؟

  3. آمارهٔ شکاف را روی دادهٔ مثال تومور (یا ۶۴ نقطه از سه گاوسی هم‌پوشان) به کار ببرید و ببینید شکستگی‌ای می‌یابد که منحنی نشان نمی‌دهد.

  4. محاسبهٔ شکاف را با B=5B = 5 و B=100B = 100 تکرار کنید. بر میله‌های خطا و بر K^\hat K چه می‌آید؟

  5. با شبیه‌سازی نشان دهید آمارهٔ شکاف برای دادهٔ یک گاوسی K^=1\hat K = 1 برمی‌گرداند و قاعدهٔ شکستگی نه.

  6. گام‌به‌گام رو به جلو مرکزها را برای کمینه‌کردن WW برمی‌گزیند؛ K-means++ آن‌ها را با احتمالی متناسب با مجذور فاصله تا نزدیک‌ترین مرکز برگزیده نمونه‌گیری می‌کند. این دو را با ۱۰۰ شروع مقایسه کنید.

منابع

  • مقدارگذاری آغازین گام‌به‌گام رو به جلو، استدلال علیه اعتبارسنجی متقاطع، شکستگی، آمارهٔ شکاف، (۱۴.۳۹) و شکل ۱۴.۱۱: بند ۱۴.۳.۱۱ از hastie2009esl، صص ۵۱۸–۵۲۰؛ آمارهٔ شکاف از Tibshirani, Walther and Hastie (2001) است که همان‌جا ارجاع داده شده.

  • غیبت شکستگی روی دادهٔ واقعی: مثال تومور و شکل ۱۴.۸ کتاب.

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