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

خوشه‌بندی (بخش ۱)

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

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

خوشه‌بندی، وظیفهٔ افراز نقطه‌های داده به گروه‌های طبیعی به نام خوشه است، به‌گونه‌ای که نقطه‌های درون یک گروه بسیار شبیه و نقطه‌های گروه‌های مختلف تا حد ممکن نامتشابه باشند zaki2020data.

بسته به داده و ویژگی‌های مطلوب خوشه‌ها، الگوهای گوناگونی از خوشه‌بندی داریم مانند نماینده‌بنیان، سلسله‌مراتبی، چگالی‌بنیان، گراف‌بنیان و طیفی. خوشه‌بندی رویکردی یادگیری بدون‌نظارت است، چون برای یادگیری پارامترهای مدل به مجموعه‌دادهٔ آموزشی جداگانه نیاز ندارد.

یک الگوریتم جست‌وجوی فراگیر برای یافتن خوشه‌بندی خوب این است که همهٔ افرازهای ممکن nn نقطه به kk خوشه را بسازیم، برای هر کدام نمرهٔ بهینگی را حساب کنیم و خوشه‌بندی با بهترین نمره را نگه داریم. ولی این کار آشکارا ناممکن است، چون تعداد خوشه‌بندی‌های nn نقطه در kk گروه از مرتبهٔ O(kn/k!)O(k^n/k!) است.

بسیاری از الگوریتم‌های خوشه‌بندی در Scikit-Learn و جاهای دیگر هست، ولی شاید ساده‌ترینشان برای فهم، الگوریتمی به نام خوشه‌بندی k-means است که در sklearn.cluster.KMeans پیاده شده است.

با وارد کردن‌های استاندارد آغاز می‌کنیم:

Source

معرفی k-means

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

  • مرکز خوشه میانگین حسابی همهٔ نقطه‌های آن خوشه است.

  • هر نقطه به مرکز خوشهٔ خودش نزدیک‌تر است تا به مرکزهای دیگر.

این دو فرض پایهٔ مدل k-means است. به‌زودی می‌بینیم الگوریتم دقیقاً چگونه به این جواب می‌رسد؛ فعلاً یک مجموعه‌دادهٔ ساده را ببینیم.

نخست یک مجموعه‌دادهٔ دوبُعدی با چهار تودهٔ جدا می‌سازیم. برای تأکید بر اینکه الگوریتم بدون‌نظارت است، برچسب‌ها را از نمودار بیرون می‌گذاریم (شکل زیر):

<Figure size 640x480 with 1 Axes>

با چشم، جدا کردن چهار خوشه نسبتاً آسان است. الگوریتم k-means این کار را خودکار انجام می‌دهد و در Scikit-Learn با API معمول برآوردگر:

بیایید نتیجه را با رنگ‌کردن داده بر پایهٔ این برچسب‌ها ببینیم (شکل زیر). همچنین مرکزهای خوشه را که برآوردگر k-means یافته است رسم می‌کنیم:

<Figure size 640x480 with 1 Axes>

خبر خوب این است که الگوریتم k-means (دست‌کم در این حالت ساده) نقطه‌ها را تقریباً همان‌گونه به خوشه‌ها می‌دهد که با چشم می‌دادیم. ولی شاید بپرسید این الگوریتم چگونه این خوشه‌ها را این‌قدر سریع می‌یابد: تعداد ترکیب‌های ممکن انتساب خوشه در تعداد نقطه‌ها نمایی است — جست‌وجوی فراگیر بسیار بسیار گران می‌شد. خوشبختانه چنین جست‌وجویی لازم نیست: رویکرد معمول به k-means یک روش تکراری شهودی به نام امید ریاضی–بیشینه‌سازی است.

امید ریاضی–بیشینه‌سازی

امید ریاضی–بیشینه‌سازی (E–M) الگوریتمی نیرومند است که در بافت‌های گوناگون علم داده سر بر می‌آورد. k-means کاربرد خاص ساده و آسان‌فهم این الگوریتم است و اینجا کوتاه مرورش می‌کنیم. خلاصه، رویکرد امید ریاضی–بیشینه‌سازی اینجا از این روند تشکیل می‌شود:

  1. چند مرکز خوشه حدس بزن.

  2. تا همگرایی تکرار کن:

    1. گام E: هر نقطه را به نزدیک‌ترین مرکز خوشه نسبت بده.

    2. گام M: مرکزهای خوشه را میانگین نقطه‌های منتسب به خودشان بگذار.

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

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

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

الگوریتم k-means آن‌قدر ساده است که می‌توان در چند خط کد نوشت. پیاده‌سازی بسیار سادهٔ زیر را ببینید (شکل زیر):

<Figure size 640x480 with 1 Axes>

بیشتر پیاده‌سازی‌های آزموده‌شده کمی بیشتر از این کار می‌کنند، ولی تابع بالا جانِ رویکرد امید ریاضی–بیشینه‌سازی را می‌رساند.

چند نکتهٔ هشداردهنده هست که هنگام به‌کارگیری الگوریتم امید ریاضی–بیشینه‌سازی باید در نظر داشت:

ممکن است نتیجهٔ بهینهٔ جهانی به دست نیاید

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

<Figure size 640x480 with 1 Axes>

اینجا رویکرد E–M همگرا شده، ولی به پیکربندی بهینهٔ جهانی نرسیده است. به همین دلیل معمول است که الگوریتم را با چند حدس آغازین اجرا کنند، همان‌گونه که Scikit-Learn به‌طور پیش‌فرض می‌کند (تعداد با پارامتر n_init تعیین می‌شود که پیش‌فرضش ۱۰ است).

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

چالش رایج دیگر در k-means این است که باید بگویید چند خوشه انتظار دارید: نمی‌تواند تعداد خوشه‌ها را از داده بیاموزد. برای نمونه اگر از الگوریتم بخواهیم شش خوشه بیابد، با خوشحالی بهترین شش خوشه را می‌یابد، همان‌گونه که در شکل ۴۷-۶ می‌بینید:

<Figure size 640x480 with 1 Axes>

اینکه نتیجه معنادار هست یا نه پرسشی است که پاسخ قطعی به آن دشوار است؛ یک رویکرد نسبتاً شهودی که اینجا بیشتر درباره‌اش بحث نمی‌کنیم تحلیل سیلوئت نام دارد.

به‌جای آن می‌توانید الگوریتم پیچیده‌تری برگزینید که سنجهٔ کمّی بهتری برای برازندگی برحسب تعداد خوشه دارد (مثلاً مدل‌های مخلوط گاوسی) یا می‌تواند تعداد مناسب خوشه را انتخاب کند (مثلاً DBSCAN، mean-shift یا affinity propagation که همه در زیرماژول sklearn.cluster هستند).

k-means به مرزهای خطی محدود است

فرض‌های بنیادی مدل k-means (نقطه‌ها به مرکز خوشهٔ خودشان نزدیک‌ترند تا به بقیه) یعنی اگر خوشه‌ها هندسهٔ پیچیده داشته باشند، الگوریتم اغلب کارآمد نیست.

به‌ویژه مرزهای میان خوشه‌های k-means همیشه خطی‌اند (مثل حالت ۱ در نظریهٔ تصمیم بیزی)، پس برای مرزهای پیچیده‌تر شکست می‌خورد. دادهٔ زیر را با برچسب‌های خوشه‌ای که رویکرد معمول k-means می‌یابد ببینید (شکل زیر):

<Figure size 640x480 with 1 Axes>

این وضعیت بحث فصل‌های بعد را یاد می‌آورد که با یک تبدیل کرنل داده را به بُعدی بالاتر می‌بردیم که در آن جدایی خطی ممکن بود. می‌توان تصور کرد همان ترفند را به کار ببریم تا k-means مرزهای غیرخطی را کشف کند.

یک نسخه از این k-means کرنل‌شده در Scikit-Learn در برآوردگر SpectralClustering پیاده شده است Fayaz2015SpectralNemati2018Gradient. از گراف نزدیک‌ترین همسایه‌ها برای محاسبهٔ نمایشی ابعاد بالاتر از داده استفاده می‌کند و سپس با الگوریتم k-means برچسب می‌گذارد:

<Figure size 640x480 with 1 Axes>

می‌بینیم که با این رویکرد تبدیل کرنل، k-means کرنل‌شده می‌تواند مرزهای غیرخطی پیچیده‌تر میان خوشه‌ها را بیابد.

k-means برای تعداد زیاد نمونه می‌تواند کند باشد

چون هر تکرار k-means باید به همهٔ نقطه‌های مجموعه‌داده دسترسی یابد، الگوریتم با رشد تعداد نمونه‌ها نسبتاً کند می‌شود. شاید بپرسید آیا می‌توان این الزام به استفاده از همهٔ داده در هر تکرار را شل کرد؛ مثلاً فقط زیرمجموعه‌ای از داده برای به‌روزرسانی مرکزها در هر گام به کار رود. این ایدهٔ الگوریتم‌های k-means دسته‌ای است که یک شکلش در sklearn.cluster.MiniBatchKMeans پیاده شده است. رابط آن همان KMeans استاندارد است؛ در ادامه نمونه‌ای از کاربردش را می‌بینیم.

مثال‌ها

با در نظر داشتن این محدودیت‌های الگوریتم، می‌توانیم از k-means در موقعیت‌های گوناگون به سود خود بهره بگیریم. حالا چند مثال را می‌بینیم.

مثال ۱: k-means روی ارقام

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

با بارگذاری مجموعه‌داده آغاز می‌کنیم و سپس خوشه‌ها را می‌یابیم. یادآوری: مجموعه‌دادهٔ ارقام ۱٬۷۹۷ نمونه با ۶۴ ویژگی دارد که هر یک از این ۶۴ ویژگی روشنایی یک پیکسل در تصویر ۸×۸ است:

(1797, 64)

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

(10, 64)

نتیجه ۱۰ خوشه در ۶۴ بُعد است. دقت کنید که خود مرکزهای خوشه نقطه‌هایی ۶۴-بُعدی‌اند و می‌توان آن‌ها را نمایندهٔ رقم «معمول» درون خوشه دانست. بیایید ببینیم این مرکزها چه شکلی‌اند (شکل زیر):

<Figure size 800x300 with 10 Axes>

می‌بینیم که حتی بدون برچسب‌ها هم KMeans می‌تواند خوشه‌هایی بیابد که مرکزهایشان ارقام قابل‌شناسایی‌اند، شاید به‌جز ۱ و ۸.

چون k-means هیچ از هویت خوشه‌ها نمی‌داند، برچسب‌های ۰–۹ ممکن است جابه‌جا شوند. این را با تطبیق دادن هر برچسب خوشهٔ آموخته‌شده با برچسب‌های واقعی یافته‌شده در خوشه‌ها اصلاح می‌کنیم:

اکنون می‌توانیم ببینیم خوشه‌بندی بدون‌نظارتمان در یافتن ارقام مشابه چقدر دقیق بوده است:

0.7440178074568725

با یک الگوریتم k-means ساده، گروه‌بندی درست را برای ۸۰٪ ارقام ورودی کشف کردیم! ماتریس درهم‌ریختگی این کار را در شکل زیر ببینید:

<Figure size 640x480 with 1 Axes>

همان‌گونه که از مرکزهای خوشهٔ پیشین انتظار می‌رفت، نقطهٔ اصلی درهم‌ریختگی میان هشت‌ها و یک‌هاست. ولی این هم نشان می‌دهد با k-means می‌توانیم در اساس یک دسته‌بند رقم بسازیم بدون هیچ ارجاعی به برچسب‌های معلوم!

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

0.9415692821368948

این دقت دسته‌بندی 94%94\% است بدون استفاده از برچسب‌ها. این توان یادگیری بدون‌نظارت است وقتی با احتیاط به کار رود: می‌تواند اطلاعاتی را از مجموعه‌داده بیرون بکشد که استخراجش با دست یا چشم دشوار است.

مثال ۲: k-means برای فشرده‌سازی رنگ

یکی از کاربردهای جالب خوشه‌بندی، فشرده‌سازی رنگ در تصویرهاست (این مثال از «کوانتیزه‌سازی رنگ با K-Means» در Scikit-Learn گرفته شده است. برای نمونه تصور کنید تصویری با میلیون‌ها رنگ دارید. در بیشتر تصویرها تعداد زیادی از رنگ‌ها به کار نرفته‌اند و بسیاری از پیکسل‌ها رنگ‌های مشابه یا حتی یکسان دارند.

برای نمونه تصویر شکل زیر را در نظر بگیرید که از ماژول datasets در Scikit-Learn است (برای این کار باید بستهٔ PIL نصب باشد): (برای نسخهٔ رنگی این تصویر و تصویرهای بعد، نسخهٔ آنلاین کتاب را ببینید).

<Figure size 640x480 with 1 Axes>

خود تصویر در آرایه‌ای سه‌بُعدی با اندازهٔ (height, width, RGB) ذخیره شده است که سهم قرمز/آبی/سبز را به‌صورت عدد صحیح از ۰ تا ۲۵۵ در بر دارد:

(427, 640, 3)

یک راه دیدن این مجموعه پیکسل، ابری از نقطه‌ها در فضای رنگ سه‌بُعدی است. داده را به [n_samples, n_features] بازشکل می‌دهیم و رنگ‌ها را به بازهٔ ۰ تا ۱ می‌بریم:

(273280, 3)

می‌توانیم این پیکسل‌ها را در این فضای رنگ ببینیم و برای کارایی از زیرمجموعه‌ای ۱۰٬۰۰۰ پیکسلی بهره ببریم (شکل زیر):

<Figure size 1600x600 with 2 Axes>

حالا با خوشه‌بندی k-means در فضای پیکسل، این ۱۶ میلیون رنگ را به ۱۶ رنگ کم می‌کنیم. چون با مجموعه‌دادهٔ بسیار بزرگی سروکار داریم، از k-means دسته‌ای کوچک (mini-batch) بهره می‌بریم که روی زیرمجموعه‌هایی از داده کار می‌کند و نتیجه (شکل زیر) را بسیار سریع‌تر از k-means استاندارد می‌دهد:

<Figure size 1600x600 with 2 Axes>

نتیجه بازرنگ‌کردن پیکسل‌های اصلی است که هر پیکسل رنگ نزدیک‌ترین مرکز خوشه‌اش را می‌گیرد. رسم این رنگ‌های تازه در فضای تصویر (نه فضای پیکسل) اثر این کار را نشان می‌دهد (شکل زیر):

<Figure size 1600x600 with 2 Axes>

قطعاً پار بعضی جزئیات در پنل سمت راست از دست می‌رود، ولی تصویر کلی هنوز آسان‌قابل‌تشخیص است. از نظر بایت لازم برای ذخیرهٔ دادهٔ خام، تصویر سمت راست ضریب فشرده‌سازی حدود یک میلیون را به‌دست می‌آورد! البته این رویکرد به وفاداری روش‌های فشرده‌سازی تصویرِ ویژهٔ همین کار مانند JPEG نمی‌رسد، ولی مثال قدرت اندیشیدن بیرون از چارچوب با روش‌های بدون‌نظارتی مانند k-means را نشان می‌دهد.

تمرین‌ها

  1. اتحاد ∑x,x′∈C∥x−x′∥2=2∣C∣∑x∈C∥x−μC∥2\sum_{x,x'\in C}\|x-x'\|^2 = 2|C|\sum_{x\in C}\|x-\mu_C\|^2 را اثبات کنید و با آن نشان دهید نسبت دادن هر نقطه به نزدیک‌ترین مرکز نمی‌تواند SSE را افزایش دهد.

  2. نشان دهید برای یک افراز ثابت، SSE با مرکز (میانگین) کمینه می‌شود؛ با مشتق گرفتن نسبت به μk\mu_k و صفر گذاشتن گرادیان. چرا این کار جواب بستهٔ کل مسئله را نمی‌دهد؟

  3. k-means نوت‌بوک را روی ارقام با K=10K=10 و پنج مقدار آغازین اجرا کنید؛ پراکندگی SSE نهایی و شاخص رند تعدیل‌شده را گزارش دهید. کدام بیشتر تغییر می‌کند و چرا؟

  4. یک گام E و یک گام M را برای یک مخلوط گاوسی دوبؤلفه‌ای یک‌بُعدی روی نقطه‌های {0,1,9,10}\{0,1,9,10\} دستی انجام دهید. مسئولیت‌ها را با انتساب سختِ k-means مقایسه کنید.

مطالعهٔ بیشتر

Scikit-learn: مقایسهٔ الگوریتم‌های مختلف خوشه‌بندی روی مجموعه‌داده‌های اسباب‌بازی