الگوریتم‌ خوشه‌بندی 7

الگوریتم KNN

ساده‌ترین روش خوشه‌ بندی در یادگیری ماشین، الگوریتم KNN یا k نزدیک‌ترین همسایه (k-NN: k-nearest neighbors) است؛ یک روش یادگیری بانظارت که برای دسته‌بندی نقاط داده جدید بر اساس نزدیکی با نقاط داده فعلی، استفاده می‌شود.  الگوریتم KNN شبیه به یک سیستم رأی‌گیری است. این الگوریتم را شبیه به یک بچه تازه‌وارد به مدرسه در حال انتخاب یک گروه از هم‌کلاسی‌ها برای داشتن روابط اجتماعی بر اساس پنج هم‌کلاسی که در نزدیک‌ترین محل می‌نشینند، فرض کنید. در بین این پنج هم‌کلاسی، سه نفر درس‌خوان (Geek)، یک نفر اسکیت‌باز و یک نفر ورزشکار است. بر اساس الگوریتم KNN، وقت‌گذرانی با درس‌خوان‌ها را به علت مزایای بالای آن انتخاب می‌کند. بگذارید یک مثال دیگر را بررسی کنیم.

همان‌طور که در شکل بالا دیده می‌شود، نمودار پراکندگی، امکان محاسبه فاصله بین هر دو نقطه داده‌ای را فراهم می‌کند. قبلاً نقاط داده بر روی نمودار پراکندگی به دو خوشه تقسیم شده‌اند. در ادامه، یک نقطه داده جدید که برچسب (Class) آن را نمی‌دانیم به نمودار اضافه می‌شود. حال برچسب نقطه داده جدید را بر اساس رابطه‌اش با نقاط داده موجود، پیش‌بینی می‌کنیم.

ولی ابتدا، باید “k” را انتخاب کنیم تا تعداد نقاط داده کاندید برای دسته‌بندی نقطه داده جدید را مشخص کنیم. اگر مقدار k را 3 قرار بدهیم، الگوریتم KNN تنها رابطه نقطه داده جدید را با سه‌ نقطه داده در نزدیک‌ترین فاصله (همسایه‌ها) را تحلیل می‌کند. با انتخاب سه تا نزدیک‌ترین همسایه، دو نقطه داده دسته B و یک نقطه داده دسته A را خواهیم داشت. در این شرایط پیش‌بینی مدل برای نقطه داده جدید دسته B است چون دو همسایه از سه همسایه نزدیک را شامل می‌شود.

تعداد همسایه‌ها در تشخیص و تعیین نتیجه نهایی، تعریف شده توسط k، نقش مهمی ایفا می‌کند. در شکل بالا، بسته به اینکه مقدار k، برابر 3 یا 7 باشد، دسته‌بندی تغییر می‌کند. پس پیشنهاد می‌شود که تعداد زیادی از ترکیبات k را مورد آزمایش قرار بدهید تا بهترین k را پیدا کنید. همچنین از مقادیر خیلی کم یا خیلی زیاد برای k اجتناب کنید. انتخاب مقادیر فرد برای k همچنین کمک می‌کند تا امکان رسیدن به یک بن‌بست آماری و نتیجه نامعتبر از بین برود. تعداد پیش‌فرض همسایه‌ها در استفاده از Scikit-learn، پنج است.

با اینکه معمولاً الگوریتم KNN تکنیکی بادقت بالا و ساده است ولی ذخیره کل یک مجموعه‌داده و محاسبه فاصله بین هر نقطه داده جدید و تمام نقاط داده موجود، بار سنگین محاسباتی دارد. در نتیجه، KNN برای استفاده بر روی مجموعه‌داده‌های بزرگ پیشنهاد نمی‌شود.

نکته منفی احتمالی دیگر این است که اعمال KNN برای داده‌های با بعد بالا (سه‌بعدی یا چهاربُعدی) با چندین ویژگی می‌تواند چالش‌برانگیز باشد. اندازه‌گیری چندین فاصله بین نقاط داده در یک فضای سه یا چهاربعدی، فشار مضاعفی بر روی منابع محاسباتی می‌آورد و همچنین دسته‌بندی صحیح را پیچیده می‌کند. کاهش تعداد کل بُعدها، به‌وسیله یک الگوریتم کاهش بُعد مثل تحلیل مؤلفه‌های اصلی (PCA: Principle Component Analysis) یا ادغام متغیرها، یک استراتژی معمول برای ساده‌سازی و آماده‌سازی یک مجموعه‌داده برای تحلیل الگوریتم KNN است.