الگوریتم KNN

الگوریتم KNN یا K نزدیک ترین همسایه یکی از ساده‌ترین و تنبل‌ترین الگوریتم‌ها در یادگیری ماشین هست! ایده الگوریتم KNN بسیار ساده هست: برای پیش بینی خروجی یک نمونه داده، به همسایه‌های آن نمونه نگاه کن! من و هوسم با یکی دیگر از جلسات آموزش یادگیری ماشین رایگان در خدمت شما هستیم…

آشنایی با الگوریتم KNN

به تصویر زیر نگاه کنید؛ به نظر شما نمونه سبز متعلق به کدام کلاس (قرمز یا آبی) است؟ به هیچ الگوریتم یا مدلی در یادگیری ماشین فکر نکنید و تنها با منطق و استدلال خود جواب دهید؛ احتمالا شما هم مثل من می‌گویید آبی! البته، می‌دونم آبی نیست! فکر کنم سرمه‌ای باشه! 😅 فکر کنم اون یکی هم قرمز نباشه، بهش میخوره ارغوانی باشه! شکل رو خودم کشیدم و رنگ‌ها رو خودم تعیین کردم، ولی اسمشو نمی‌دونم! اینجاست که استاد شهریار میگه: شعر میگم، نمی‌تونم بنویسم! 😀 

اما با چه منطقی، آن نمونه سبز را به عنوان کلاس آبی دسته‌بندی کردید؟ احتمالا گفتید، باتوجه به اینکه همه نمونه‌های نزدیکش آبی هستند، پس این نمونه هم به کلاس آبی تعلق دارد. الگوریتم KNN هم دقیقا مبتنی بر همین منطق کار می‌کند! اگر تا اینجا توضیحاتم را متوجه شدید، دیگر نیازی به مطالعه ادامه آموزش ندارید! 😀

الگوریتم KNN می‌تواند هم برای طبقه بندی و هم برای رگرسیون استفاده شود. البته، اولین بار در سال 1951 برای طبقه بندی معرفی شده بود. ما هم اینجا ادامه آموزش را مبتنی بر طبقه بندی جلو می‌بریم. حالا وقتش رسیده که جزئیات بیشتری از الگوریتم KNN بدانید…

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

الگوریتم KNN برای طبقه بندی شامل تنها سه مرحله است:

1. محاسبه فاصله اقلیدسی بین نمونه تست (x_t) و نمونه‌های آموزش (X)
2. انتخاب K همسایه نزدیک به نمونه تست براساس فاصله
3. تعیین کلاس نمونه تست براساس اکثریت آرا در K همسایه نزدیک

در ادامه، در مورد سه مرحله بالا مبتنی بر داده‌های زیر توضیح می‌دهم…

محاسبه فاصله اقلیدسی بین نمونه تست (x_t) و نمونه‌های آموزش (X)

در اولین مرحله، باید فاصله اقلیدسی بین نمونه تست (x_t) با تک‌تک نمونه‌های آموزش (X) محاسبه شود. فرض کنید، n نمونه داده آموزشی داشته باشیم. از طریق فرمول زیر به راحتی می‌توان فاصله بین نمونه‌های مختلف را حساب کرد. خروجی این رابطه، بردار d به طول n هست که درایه i-ام آن نشان دهنده میزان فاصله نمونه x_t با نمونه X_i است.

انتخاب K همسایه نزدیک به نمونه تست براساس فاصله

نتیجه مرحله قبلی این بود که یک بردار فاصله (d) به طول n بدست آوردیم. طبیعتا، نمونه‌هایی که مقدار فاصله آنها به نمونه تست کم باشد، همسایه‌های نزدیک محسوب می‌شوند. در این مرحله ما باید تعیین کنیم که چه تعداد از همسایه‌‌های نزدیک را می‌خواهیم. مثلا ما سه همسایه نزدیک‌تر را انتخاب می‌کنیم. در شکل زیر، سه همسایه نزدیک تر به نمونه تست را مشاهده می‌کنید.

توجه همان‌طور که گفته شد، الگوریتم KNN مخفف K Nearest Neighbor هست. مفهوم Nearest Neighbor که تاکنون متوجه شدید. اما K به چه اشاره می‌کند؟ به همان تعداد همسایه نزدیک‌تر!

تعیین کلاس نمونه تست براساس اکثریت آرا در K همسایه نزدیک

حالا باید نگاه کنیم که K همسایه نزدیک، به کدام کلاس‌ها تعلق دارند. در اینجا، هر سه همسایه نزدیک، به کلاس آبی تعلق دارند. بنابراین، الگوریتم KNN می‌گوید که نمونه تست به کلاس آبی تعلق دارد و تمام!

این سه مرحله‌ای که به شما توضیح دادم، باید برای تک تک نمونه‌های تست به‌صورت جداگانه انجام شود.

ادامه دارد…