خوشه بندی ( Clustering ) چیست؟

یکشنبه ۰۴ خرداد ۱۳۹۹سامان

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

خوشه بندی به جای اینکه به دنبال پیش‌بینی در داده‌ها باشد به دنبالِ یافتنِ نظم‌های پنهان و الگوها در داده‌ها جهت گروه‌بندی آن‌ها می‌گردد. در واقع خوشه بندی فرایند تفکیک داده ها یا اشیاء به زیر کلاس هایی به نام خوشه است. هدف از خوشه بندی، فهم(بررسی رکورد های مشابه ) یا خلاصه سازی(کاهش مجموعه های بزرگ است).

خوشه بندی - clustering شامل مجموعه ای از الگوریتم ها می شود که در درس های بعدی به بررسی هر کدام می پردازیم.

چه زمانی از الگوریتم های خوشه بندی استفاده می شود؟

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

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

بنابراین اگر داده های ما هیچ برچسب یا Target نداشته باشند و بخواهیم داده ها را به گروه های مختلفی تقسیم کنیم می توان از الگوریتم های خوشه بندی استفاده کرد.

Label Age BMI Insulin SkinThickness BloodPressure Glucose pregnancies
0 50 33.6 0 35 72 148 6
1 31 26.6 0 29 66 85 1
1 32 23.3 0 25 64 183 8
1 30 25 0 24 63 150 6
0 33 24.3 1 28 58 96 2

خوشه بندی چطور عمل می کند؟

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

  • شباهت درون خوشه ای بیشترین باشد
  • عدم شباهت بین خوشه ای بیشترین باشد

شباهت درون خوشه ای بیشترین باشد یعنی الگوریتم تلاش کند تا شباهت تمام داده های که در یک خوشه قرار می گیرند بیشتر از شباهت داده های دو خوشه متفاوت باشد. همچنین عدم شباهت بین خوشه ای بیشترین باشد یعنی دو خوشه ای که ایجاد می شوند به اندازه کافی با یکدیگر متفاوت باشند که بتوان آنها را به عنوان دو خوشه جدا از هم تعریف کرد.

شاید برای شما سوال شود که چطور می توان شباهت بین داده ها را مشخص کرد؟ ما در یک نوشته دیگر به بررسی کامل معیارهای شباهت و عدم شباهت می پردازیم.

برای درک بهتر خوشه بندی به مثال زیر دقت کنید:

فرض کنید سوار بر یک بالن از ارتفاع بالا به زمین نگاه می کنید دانش آموزان یک مدرسه در حیاط مشغول بازی کردن هستند شما هر دانش آموز را مانند یک نقطه می بینید. فرض کنید چیزی که از حیاط این مدرسه می بینید مثل شکل زیر باشد:

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

مسئله دیگر الگوریتم مورد استفاده و معیارهای مورد استفاده است، الگوریتم ها با توجه به استراتژی که در پیش می گیرند ممکن است برای داده های ما مناسب نباشند لذا انتخاب الگوریتم مناسب اهمیت دارد.

در اینجا در حالت کلی مسئله را بررسی می کنیم و به جزئیات بیشتر را در بخش های بعدی بررسی می کنیم. بنابراین خوشه بندی داده های ما را با توجه به تعداد خوشه ها و الگوریتم خوشه بندی مورد استفاده ممکن است به شکل زیر انجام دهد.

 

در بخش های بعد به بررسی کامل همه الگوریتم های خوشه بندی می پردازیم.