الگوریتم 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

۱۵,۱۵,۱۶,۱۹,۱۹,۲۰,۲۰,۲۱,۲۲,۲۸,۳۵,۴۰,۴۱,۴۲,۴۳,۴۴,۶۰,۶۱,۶۵

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

k = 2

c1 = 16
c2 = 22

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

تکرار ۱

تکرار ۲

تکرار ۳

تکرار ۴

بین تکرارهای ۳ و ۴ تغییری نکرده است. با استفاده از خوشه بندی، دو گروه ۱۵ تا ۲۸ و ۳۵-۶۵ شناسایی شدند. انتخاب اولیه centroids می تواند بر خوشه‌های خروجی تأثیر بگذارد، بنابراین الگوریتم اغلب چند بار با شرایط مختلف شروع می‌شود تا دیدگاه مناسبی از خوشه‌ها داشته باشد.

سخن آخر

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

الگوریتم های یادگیری ماشین

الگوریتم های یادگیری ماشین

کلیک کنید