خوشه بندی k-Means در ابعاد بالا

یکی از مخاطبین فرادرس سوال زیر را مطرح کرده بودند. در پاسخ به این سوال مدرس عضو هیات علمی فرادرس پاسخی مبسوط ارائه کرده‌اند که با توجه به اهمیت این سوال، به نظر رسید که شاید انتشار عمومی آن نیز خالی از لطف نباشد. در ادامه متن سوال مخاطب و پاسخ به این سوال را می بینیم.

سئوال مخاطب:

در هنگام خوشه بندی با استفاده از الگوریتم k-Means در داده های با ابعاد بالا، الگوریتم پاسخ های مناسبی ندارد و اغلب تعداد خوشه های کمتری ارائه می شوند. راه حل این مشکل چیست؟

پاسخ مدرس عضو هیأت علمی مجموعه:

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

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

برای سایر روش ها نیز، می توانید به این ترتیب عمل کنید. به ویژه، در مورد الگوریتم های تکاملی و هوشمند، می توانید مسأله خوشه بندی را، به مسأله انتخاب تبدیل کنید، که یک مسأله باینری است و به مراتب راحت تر حل می شود.