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.

خوشه‌بندی، بخش 1

محمود امین‌طوسی، پاییز ۱۴۰۵

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

English · فارسی
English · فارسی

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

خوشه‌بندی وظیفهٔ افراز نقطه‌های داده به گروه‌های طبیعیِ خوشه است، چنان که نقطه‌های درون یک گروه بسیار شبیه و نقطه‌های گروه‌های مختلف تا حد ممکن نامشابه باشند Zaki & Meira (2020).

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

یک الگوریتم جست‌وجوی کامل یا تمام‌شماری برای یافتن خوشه‌بندی خوب این است که همهٔ افرازهای ممکن 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 هستند. به‌زودی می‌بینیم الگوریتم چگونه به این جواب می‌رسد، ولی فعلاً یک مجموعه‌دادهٔ ساده را ببینیم و نتیجهٔ 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 تعیین می‌شود که پیش‌فرضش 10 است).

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

چالش رایج دیگر k-means این است که باید بگویید چند خوشه انتظار دارید: نمی‌تواند تعداد خوشه‌ها را از داده یاد بگیرد. مثلاً اگر از الگوریتم بخواهیم شش خوشه پیدا کند، بی‌درنگ پیش می‌رود و بهترین شش خوشه را می‌یابد، همان‌طور که در شکل 47-6 آمده است:

<Figure size 640x480 with 1 Axes>

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

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

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

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

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

<Figure size 640x480 with 1 Axes>

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

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

<Figure size 640x480 with 1 Axes>

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

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

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

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

مثال‌ها

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

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

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

با بارگذاری مجموعه‌داده شروع می‌کنیم و بعد خوشه‌ها را می‌یابیم. یادآوری می‌کنیم مجموعه‌دادهٔ ارقام از 1797 نمونه با 64 ویژگی تشکیل شده که هر یک از 64 ویژگی روشنایی یک پیکسل در تصویری 8×8 است:

(1797, 64)

خوشه‌بندی مانند قبل انجام می‌شود:

(10, 64)

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

<Figure size 800x300 with 10 Axes>

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

چون k-means هیچ چیزی از هویت خوشه‌ها نمی‌داند، برچسب‌های 0 تا 9 ممکن است جای هم باشند. می‌توانیم این را با تناظر دادن هر برچسب خوشهٔ یادگرفته با برچسب‌های واقعیِ یافت‌شده در خوشه‌ها اصلاح کنیم:

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

0.7440178074568725

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

<Figure size 640x480 with 1 Axes>

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

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

0.9415692821368948

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

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

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

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

<Figure size 640x480 with 1 Axes>

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

(427, 640, 3)

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

(273280, 3)

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

<Figure size 1600x600 with 2 Axes>

اکنون این 16 میلیون رنگ را به فقط 16 رنگ کاهش دهیم و از خوشه‌بندی k-means روی فضای پیکسل استفاده کنیم. چون با مجموعه‌دادهٔ بسیار بزرگی سر و کار داریم، از k-means کوچک‌دسته‌ای استفاده می‌کنیم که روی زیرمجموعه‌هایی از داده کار می‌کند و نتیجه را (شکل زیر) بسیار سریع‌تر از الگوریتم استاندارد 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: Comparing different clustering algorithms on toy datasets

References
  1. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367
  2. Fayaz, T. (2015). Spectral clustering for image segmentation [Mathesis, Hakim Sabzevari University, Faculty of Mathematics]. https://hcloud.hsu.ac.ir/index.php/s/Y4BedGEY7OjXVgK
  3. Nemati, M. (2018). A Gradient Based Method for the Spectral Graph Partitioning [Mathesis, Hakim Sabzevari University, Faculty of Mathematics]. https://hcloud.hsu.ac.ir/index.php/s/tR53d9306yZSAc7