در آمار kNN یا k-nearest neighbors algorithm یکی از روش های یادگیری ماشین غیر پارامتریک محسوب میشه که اولین بار توسط Evelyn Fix و Joseph Hodges دو آماردان و استاد دانشگاه برکلی کالیفرنیا در سال 1951 ایجاد و ارایه شد. و بعد ها توسط Thomas Cover متخصص نئوری اطلاعات و آمار توسعه پیدا کرد. از این الگوریتم به منظور طبقه بندی و همچنین در رگرسیون مورد استفادست. (ویکی پدیا) ویکی پدیا فارسی رو هم نگاه کنید اطلاعات خوبی داره!
k-Nearest Neighbors از جمله آسون ترین الگوریتم های موجود برای طبقه بندی (calssification) به حساب میاد. دو کاربرد مهم kNN که به عقیده برخی جز الگوریتم های machine learning به حساب نمیاد چون training نداره! استفاده در classification و imputation هستش.
دو مزیت اصلی این روش عبارتند از دقت بالا به خصوص در دیتا های کم و همچنین عدم حساسیت به outliers. و اما از عیب های اصلی این روش میشه به هزینه بالا در استفاده از منابع سیستمی (مثل ram و cpu) اشاره کرد.
نحوه محاسبات در این الگوریتم به این صورته که فاصله نقطه مورد نظر رو نسبت به نقاط دیگه محاسبه می کنه و براساس طبقه ای که نقاط دیگه دارن و کوتاه ترین فاصله به اون دسته دسته مورد نظر اختصاص پیدا میکنه (k دسته اول سورت شده براساس فاصله).
به بیان دیگه منطق روش به این صورته که فاصله نقطه مورد نظر رو نسبت به نقاط دیگه اندازه گیری میکنه و در مجموع اگر به طبقه ای فاصله کمتر داشته باشه به همون دسته تعلق می گیره.فقط برای تعیین این نزدیکی میزان فاصله به k نقطه رو که دارای کمترین مقدار باشند انتخاب می کنیم یعنی مقادیر فاصله بدست آمده رو به صورت نزولی مرتب می کنیم و از k مقدار اول طبقه مورد نظر رو انتخاب می کنیم.
به طور مثال برای طبقه بندی ژانر فیلم ها (البته با نگاهی ساده) به دو گروه رمانتیک و اکشن تعداد ماچو بوسه ها و مشت و لگد ها رو می شماریم. (در پست های بعدی طبقه بندی اعداد با دست خط های متفاوت و افراد متفاوت رو با هم بررسی میکنیم که یک مثال کاملا کاربردی به حساب میاد)
اگر مقدار مشت و لگدها و ماچو بوسه ها به صورت جدول زیر باشه فیلمی با n تعداد ماچ و m تعداد لگد در کدوم دسته قرار میگیره؟ اکشن یا رمانتیک؟
البته مثال بالا بیشتر یه مثال آموزشی و شوخی طوره! ولی دقیقا نحوه عملکرد رو نشون میده. جدول بالا نشون میده که فاصله ها اقلیدسی نسبت به هر کدوم از فیلم ها در ستون آخر قرار گرفته و نتیجه این میشه که فیلم جدید رمانتیک هستش! برای این که با کد ها پایتون هم این مطلب رو چک کنیم به کدهای زیر دقت کنید :
