چگونگی اجرای الگوریتم خوشه‌بندی k-means در متلب

من در سری‌های قبلی یک سری مستندات را ترجمه کردم، که البته ناقص هستندُ در این پست و پست‌های بعدی به ترجمه مستندات در این خصوص ادامه می‌دهم.

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

این الگوریتم رویه زیر را دنبال می‌کند:

انتخاب کا مرکز اولیه خوشه. برای مثال انتخاب کا خوشه به صورت تصادفی (با استفاده از ('Start','sample') یا استفاده از الگوریتم کا-مینز پلاس پلاس برای انتخاب مراکز اولیه خوشه

محاسبه فاصله نقطه تا تمامی مراکز

ادامه الگوریتم (مخصوصا در فاز آنلاین)

به روزرسانی دسته – تعیین هر مشاهده به خوشه‌ای که به مرکز خوشه آن نزدیکترین است.

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

به دست آوردن میانگین مشاهدات در هر خوش

محاسبه میانگین مشاهدات در هر خوشه برای به دست آوردن مراکز جدید

تکرار گام ۲ تا ۴ تا زمانی که مقدار ارزیابی تغییر نکند یا ماکزیمم تکرارها حاصل شود.

الگوریتم کا-مینز پلاس پلاس

الگوریتم کا-مینز پلاس پلاس از یک فرایند اکتشاف جهت یافتن مراکز خوشه برای الگوریتم کا-مینز استفاده می‌کند. همان طور که آرتور و واسیلویتسکی گفتند، کا-مینز پلاس پلاس زمان اجرای الگوریتم لیلود را افزایش می‌دهد , کیفیت راه‌حل پایانی بالا می‌رود.

رویه این الگوریتم به شرح زیر است:

  1. انتخاب مشاهدات نایکنواخت به شکل تصادفی از دیتاست. مشاهدهدات انتخاب شده مراکز اولیه هستند و با c۱ نشان داده می‌شوند.
  2. محاسبه فاصله هر مشاهده تا c۱.  فاصله بین c۱ و مشاهدات با m نشان داده می‌شود.
  3. انتخاب مراکز بعدی، به طور تصادفی از ایکس با یک فرمول احتمال
  4. انتخاب مرکز j
    1. محاسبه فاصله هر مشاهده تا مرکز خوشه، و تعیین هر مشاهده به نزدیکترین مرکز
    2. برای m = ۱,…,n و p = ۱,…,j – ۱، جی j را به صورت تصادفی و احتمالی از ماتریس ایکس انتخاب کن

که Cp  مجموعه همه مشاهدات نزدیکتر به مرکز cp  و xm  متعلق به Cp است. انتخاب هر مرکز بعدی با اختیار احتمال تا فاصله تا نزدکترین مرکزی است که اخیرا انتخاب شده است.

 

  1. تکرار گام‌های ۲ تا ۴ تا زمانی که همه مراکز انتخاب شوند.

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


الگوریتم کا-مینز

کا-مینز از الگوریتم تکراری دو فازه برای کمینه کردن مجموعه فواصل نقطه تا مرکز استفاده می‌کند.

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

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

دیدگاه‌تان را بنویسید: