معرفی روش خوشه بندی K-means

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

روش k-mean جزء روش های یادگیری بدون نظارت هست که هدف آن خوشه بندی کردن داده ها بر اساس ویژگی های آن هاست.

سری مباحث خوشه بندی

در ابتدا و قبل از شروع مبحث باید بگم سعی کردم که مباحث خوشه‌بندی رو به صورت یک سلسه و سری که از دیدگاه کل به جزء بررسی می‌شه رو باهاتون به اشتراک بگذارم. این سلسله مباحث به ترتیب اولویت زیر لیست شده اند و پیشنهاد من برای بهتر درک کردن این مباحث اینه که به ترتیب بخونید و البته اگه مطلبی رو بلدید می‌تونید برید سراغ بعدی :)

1- یادگیری ماشین و مدل سازی آماری(شباهت ها و تفاوت ها)

2- یادگیری تحت نظارت و بدون نظارت در یادگیری ماشین در سه دقیقه

3- خوشه بندی چیست و چگونه عمل می‌کند؟

4- معرفی روش خوشه بندی K-means

5- الگوریتم های خوشه بندی لوید و فورجی(K-means)

6- الگوریتم های خوشه بندی هارتیگان-ونگ و مک‌کوئین (K-means)

7- پیاده سازی الگوریتم های لوید و فورجی - قسمت اول (مجموعه داده Iris)

8- پیاده سازی الگوریتم های لوید و فورجی - قسمت دوم(مجموعه داده Diamond)

کاربرد ها و هدف روش خوشه بندی k-means

خب قبل ازین که بحث تخصصی بشه؛ خوبه که به چند تا کاربرد از روش k-means و همین‌طور هدف این روش پرداخته بشه. همونطور که قبل تر در مطلب «خوشه بندی چیست؟» گفته شد، هدف از خوشه بندی کردن داده ها، قرار گرقتن داده های مشابه‌تر در یک خوشه است. برای مثال اگر یک مجموعه داده خرید مشتریان از یک فروشگاه اینترنتی با متغیر های قیمت محصول، نوع محصول، دسته بندی محصول، تعداد سفارش هر محصول، تعداد محصول در هر سبد خرید مشتری وجود داشته باشد؛ می‌توان با روش های خوشه‌بندی هر مشتری را بر اساس رفتار خرید آنالیز کرد و در خوشه مربوط به خود قرار داد. شاید براتون سوال پیش بیاد خب که چی؟ چرا باید مشتریان رو با آنالیز رفتار خرید خوشه بندی کنیم؟ خب باید بگم این فیلد کاربرد خیلی کلیدی ای داره که می‌تونه فروش یک فروشگاه رو تا چندین برابر افزایش بده. ساده ترین مثالش این هست که میشه بر اساس این رفتار خرید استراتژی فروش چید. مثلا اگر در سبد یک خوشه از مشتریان کالای A و B و C مکررا با هم خریداری شده، می‌توان یک پیشنهاد ویژه برای خرید پک کامل این کالا ها برای مشتریان تدارک دید.

البته راه های دیگه‌ای مثل تحلیل مولفه های اصلی(Principal Component Analysis) هم وجود داره برای این دسته کار ها؛ اما با توجه به نوع دیتاست باید دید کدوم روش بهتره.

چون روش k-means هم جزء روش های خوشه بندی محسوب میشه، کاربرد و هدف مشابهی داره.

هدف الگوریتم های این روش یافتن خوشه هایی در مجموعه داده ها با تعداد خوشه های متغیر K هست.

برای مثال اگه بخوایم مشتری ها رو به k گروه خوشه بندی کنیم تا رفتار خرید اون ها رو آنالیز کنیم؛ از الگوریتم های k-means می‌تونیم استفاده کنیم. توی این روش مهمه که k چه عددی باشه و این رو باید خودمون تعیین کنیم. مثلا روی دیتاست iris که هدفش تشخیص سه نوع گل از یک دیگه هست(با فرض ندانستن نوع گل ها)، k برابر با 3 در نظر گرفته میشه. خب سوال جدی این بخش اینه که چطور مقدار k رو تعیین کنیم؟ بسته به نوع دیتاست این مقدار متغیره. حتی بعضی اوقات با دیتاست هایی سر و کار داریم که برای k مقادیر مختلف در نظر می‌گیریم و بعد از خوشه بندی، بهینه ترین خوشه بندی رو انتخاب می‌کنیم. این نکته که چطور میشه بهینه ترین رو انتخاب کرد رو بعدا توضیح میدم.

روش خوشه بندی k-means

همونطور که گفتیم روش k-means جزء روش های یادگیری بدون نظارت هست که هدف آن خوشه بندی کردن داده ها بر اساس ویژگی های آن هاست. در این روش نیاز به یک تابع امتیاز برای ارزیابی میزان کیفیت خوشه بندی داریم. بنابراین نیاز به یک تابع هدف داریم که بتونیم نسبت به اون کیفیت خوشه بندی رو بسنجیم؛ پس تابع توان دوم خطا رو به شکل زیر تعریف می‌کنیم:

تابع هدف برای ارزیابی میزان کیفیت خوشه بندی

هدف نهایی کمینه کردن تابع توان دوم خطا برای هر خوشه هست.

مراحل الگوریتم های روش k-means

اینجا می‌خوام از مراحل الگوریتم های این روش بگم که این مراحل تا زمانی مشخص تکرار میشه:

انتخاب k نقطه به صورت تصادفی؛ در این مرحله به صورت رندوم k نقطه انتخاب میشه و به عنوان مرکز خوشه شناخته میشه.
شکل دادن k خوشه بر اساس میزان فاصله هر نقطه تا مراکز انتخابی، به گونه‌ای که برای هر نقطه(داده) فاصله تا تمام مراکز محاسبه می‌شود و نهایتا نقطه(داده) متعلق به خوشه با کمترین فاصله است.

تابع محاسبه کمترین فاصله نقطه x از مراکز خوشه C. نقطه(داده) i ام متعلق به خوشه j ام است.

بعد از تخصیص نقطه(داده) ها به خوشه، میانگین جدید هر خوشه محاسبه میشه و اون میانگین به عنوان مرکز خوشه قرار میگیره.

الگوریتم بالا تا جایی تکرار میشه که فاصله میانگین های دو مرحله پیاپی کمتر از سطح حساسیت مورد نظر بشه:

پلات دو بعدی داده ها بعد از خوشه بندی؛ c1، c2 و c3 مراکز خوشه ها هستند.

مزیت ها و معایب روش k-means

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

الگوریتم های روش k-means

چون نمیخوام این مطلب بیشتر ازین ادامه داشته باشه در اینجا فقط نام الگوریتم های این روش رو می‌گم و بعدا به چگونگی کارکرد اون ها جزئی تر می‌پردازیم. این روش 4 الگوریتم داره که عبارتند از:

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

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