الگوریتم K-means – الگوریتم یادگیری ماشین

خوشه بندی یکی از روش های یادگیری بدون نظارت است و هدف آن تقسیم بندی داده ها به خوشه های مختلف است به طوری که داده های درون یک خوشه بیشترین شباهت به یکدیگر را داشته باشند و از طرف دیگر داده های قرار گرفته در خوشه های مختلف بیشترین تفاوت را داشته باشند. خوشه بندی روشی است که هم در داده کاوی و هم در بینایی ماشین کاربرد دارد. از روش های رایج خوشه بندی می توان به خوشه بندی با الگوریتم K-means اشاره کرد.

الگوریتم خوشه بندی K-means

الگوریتم K-means یکی از روش های خوشه بندی ساده و سریع است. این الگوریتم دارای یک پارامتر به نام k است که تعداد خوشه هایی که باید به دست آید را مشخص می کند. الگوریتم K-means پایه به صورت زیر است:

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

• ورودی: خصوصیات n داده و k تعداد دسته ها
• خروجی: k دسته که داده های هر دسته از نظر شباهت به هم نزدیک و از دسته های دیگر دورند.

1. k داده را به عنوان مرکز خوشه انتخاب می کنیم.
2. مرحله سوم تا پنجم را تا رسیدن به عدم تغییر در خوشه ها تکرار می کنیم.
3. فواصل بقیه داده ها با مرکز خوشه ها را تعیین می کنیم.
4. داده هایی که به مرکز هر خوشه نزدیکترند در آن خوشه قرار می گیرند.
5. میانگین هر خوشه را به عنوان مرکز جدید خوشه در نظر می گیریم.

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

اگر یک ماتریس را به عنوان ورودی به K-means بدهیم، K-means این ماتریس را  داده با  خصوصیت در نظر می گیرد و اگر k را دو در نظر بگیریم داده ها را به دو دسته تقسیم می کند با این شرط که اعضایی در یک دسته قرار می گیرند که خصوصیات آنها به یکدیگر نزدیک تر باشد یعنی سطر متناظر با آنها در ماتریس ورودی شباهت بیشتری به یکدیگر داشته باشد.

جزئیات الگوریتم خوشه بندی K-means

خوشه بندی K-Means قصد دارد پارامتر n اشیا را به خوشه های k که هر شیء آن را با نزدیکترین میانگین متعلق به خوشه قرار دهد. این روش دقیقا خوشه های مختلفی از بزرگترین تفاوت ممکن را تولید می کند. بهترین تعداد خوشه های k که منجر به بزرگترین جدایی (فاصله) می شود به عنوان یک پیش فرض شناخته نمی شود و باید از داده ها محاسبه شود. هدف از خوشه بندی K-Means این است که به حداقل رساندن واریانس کل درونی خوشه یا تابع خطای مربع:

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

مثال روش خوشه بندی K-Means

فرض کنید ما می خواهیم بازدید کنندگان را به یک وب سایت با استفاده از سن خود (فضای یک بعدی) به صورت زیر دسته بندی کنیم:

n = 19

15,15,16,19,19,20,20,21,22,28,35,40,41,42,43,44,60,61,65

خوشه اولیه (centroid یا میانگین تصادفی):

k = 2

c1 = 16
c2 = 22

روش خوشه بندی در 4 تکرار بصورت زیر خواهد بود.

تکرار 1

تکرار 2

تکرار 3

تکرار 4

بین تکرارهای 3 و 4 تغییری نکرده است. با استفاده از خوشه بندی، دو گروه 15 تا 28 و 35-65 شناسایی شدند. انتخاب اولیه centroids می تواند بر خوشه های خروجی تأثیر بگذارد، بنابراین الگوریتم اغلب چند بار با شرایط مختلف شروع می شود تا دیدگاه مناسبی از خوشه ها داشته باشد.