الگوریتم KNN (k نزدیکترین همسایه – K-nearest neighbors) نوعی از الگوریتم های یادگیری ماشین تحت نظارت است که هم در مسائل طبقه بندی و هم در مسائل رگرسیون پیشگویانه مورد استفاده قرار می گیرد. اگرچه، غالبا در مسائل طبقه بندی پیشگویانه، در صنعت از آن استفاده می شود.

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

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

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

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

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

عملکرد الگوریتم KNN :

الگوریتم KNN (k نزدیکترین همسایه – K-nearest neighbors) از “تشابه ویژگی” برای پیش بینی مقادیر نقاط داده جدید استفاده می کند؛ که به این معنی است که به نقطه داده جدید بر اساس میزان مطابقت آن با نقاط مجموعه آموزشی، یک مقدار تخصیص می دهد. با کمک مراحل زیر میتوان نحوه عملکرد آن را درک کرد.

مرحله 1- ‌

– برای پیاده سازی هر الگوریتمی، به مجموعه داده نیاز داریم. بنابراین، در طول مرحله اول از KNN، باید داده آموزشی را به همراه داده تست بارگیری کنیم.

مرحله 2- ‌

سپس، باید مقدار k را انتخاب کنیم مانند نزدیک ترین نقاط داده. K می تواند هر عدد صحیحی باشد.

مرحله 3- ‌

برای هر نقطه داده در مجموعه داده تست، مراحل زیر را انجام دهید.

مرحله 3.1 : ‌

با کمک هر یک از متد های اقلیدسی (Euclidean) ، فاصله همینگ (Hamming distance) یا منهتن (Manhattan distance) ، فاصله بین داده تست و هر سطر از داده آموزشی را محاسبه کنید. متداول ترین روش برای محاسبه فاصله، روش اقلیدسی است.

مرحله 3.2 : ‌

حال، بر اساس مقدار فاصله، آنها را به صورت صعودی مرتب کنید.

مرحله 3.3 : ‌

سپس، الگوریتم، k سطر بالاتر از آرایه مرتب شده را انتخاب میکند.

مرحله 3.4 : ‌

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

مرحله 4- ‌

پایان.

مثال: ‌

در ادامه مثالی برای درک مفهوم k و نحوه عملکرد الگوریتم KNN ارائه شده است.

فرض کنید یک مجموعه داده داریم که می توان آن را به صورت زیر رسم کرد.

حال، باید نقطه داده جدید به رنگ مشکی (در مختصات 60.60 ) را در کلاس آبی یا قرمز طبقه بندی کنیم. فرض می کنیم k=3 است در نتیجه سه تا از نزدیک ترین نقاط داده را پیدا میکند که در شکل زیر نشان داده شده است.

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