الگوریتم طبقه بندی KNN

مقدمه

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

الگوریتم KNN نوعی از الگوریتم های یادگیری ماشین تحت نظارت است که هم در مسائل طبقه بندی و هم در مسائل رگرسیون پیشگویانه مورد استفاده قرار می گیرد. اگرچه، غالبا در مسائل طبقه بندی پیشگویانه، در صنعت از آن استفاده می شود.

دو خصیصه زیر KNN را به خوبی تعریف می کند:

الگوریتم یادگیری تنبل (Lazy learning algorithm) :‌

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

الگوریتم یادگیری بدون پارامتر (Non-parametric learning algorithm) :

همچنین KNN یک الگوریتم یادگیری بدون پارامتر است زیرا درباره داده اصلی هیچ فرضی در نظر نمی گیرد.

چه زمانی از الگوریتم KNN استفاده می کنیم ؟

از الگوریتم KNN می توان برای مسائل پیش بینی طبقه بندی و رگرسیون استفاده کرد. با این حال ، بیشتر در مسائل طبقه بندی(Classification) مورد استفاده قرار می‌گیرد. ما هر الگوریتم را از سه جنبه مورد بررسی قرار می‌دهیم:

1- سهولت در تفسیر خروجی
2- زمان محاسبه
3- قدرت پیش بینی
در زیر چند الگوریتم را براساس معیارهایی که در بالا بیان شد بررسی کرده ایم . الگوریتم Knn در بین این الگوریتم‌ها بهترین عملکرد را ارائه می‌دهد:

الگوریتم KNN چگونه کار می کند؟

با یک مثال ساده روش کار این الگوریتم را به شما آموزش خواهیم داد. در زیر محدوده ی دایره های قرمز (RC) و مربع های سبز (GS) مشخص است:

الگوریتم KNN چگونه کار می کند؟

ستاره ی آبی به داده‌های ما اضافه شده است. ما می‌خواهیم از کلاس مربوط به ستاره آبی(BS) مطلع شویم. ستاره‌ی آبی می‌تواند به دو کلاس دایره های قرمز و یا مربع های سبز تعلق داشته باشد. ستاره آبی براساس الگوریتم KNN به نزدیکترین کلاس تعلق خواهد داشت. اگر k=3 باشد.ما دایره‌‌ای به دور ستاره آبی می‌کشیم که سه نقطه را پوشش دهد. دایره ی رسم شده را در شکل زیر مشاهده می‌کنید:

الگوریتم K نزدیک ترین همسایه

همه ی سه نقطه ی نزدیک به ستاره‌ی آبی ،نقطه های قرمز رنگ می‌باشند. از این رو ، با سطح اطمینان خوب ، می توان گفت که BS(ستاره آبی) باید به کلاس RC(دایره قرمز) تعلق داشته باشد. در اینجا ، انتخاب بسیار ساده است. زیرا هر سه نقطه‌‍ی نزدیکترین همسایه به RC تعلق دارد. انتخاب پارامتر K در این الگوریتم بسیار مهم است. در مرحله بعدی ، خواهیم فهمید که چه عواملی بر انتخاب بهترین K موثر خواهند بود.

مزایا و معایب KNN

مزایا الگوریتم KNN :

  • سادگی الگوریتم
  • تفسیر بسیار ساده
  • دقت بالا
  • چند منظوره بودن
  • قابلیت استفاده در طیف وسیعی از مسایل

معایب الگوریتم KNN:

  • زمان متوسط
  • محاسبه کمی گران است
  • نیازمند حافظه زیاد چون باید تمامی داده های قبلی را ذخیره کند
  • حساس به مقیاس داده
  • اگر K عدد بزرگی شود پیش بینی کند و زمان افزایش پیدا می کند

نتیجه گیری

الگوریتم k-نزدیک‌ترین همسایگی یکی از ساده‌ترین الگوریتم‌های طبقه‌بندی است. اما با وجود سادگی، نتایج آن به وضوح قابل رقابت با دیگر الگوریتم‌ها است. این الگوریتم برای حل مسائل رگرسیون نیز قابل استفاده است. در این راستا، تنها تفاوت آن با روشی که در این نوشتار ارائه شده، استفاده از میانگین نزدیک‌ترین همسایه‌ها به جای رأی‌گیری از نزدیک‌ترین همسایه‌ها است.

1138 بازدید