K-Nearest Neighbors یا به اختصار KNN یکی از الگوریتمهای ساده و در عین حال مهم در یادگیری ماشین است. ایده اصلی آن بسیار طبیعی است: اگر بخواهیم درباره یک نمونه جدید تصمیم بگیریم، میتوانیم ببینیم نزدیکترین نمونههای شناختهشده به آن چه برچسبی دارند.
KNN در شکل رایج خود یک الگوریتم یادگیری نظارتشده (Supervised Learning) است؛ یعنی دادههای آموزشی دارای برچسب هستند و الگوریتم از این نمونهها برای پیشبینی نمونه جدید استفاده میکند.
ایده اصلی KNN
فرض کنید اطلاعات چند مشتری را داریم و هر مشتری در یکی از دو گروه «احتمال خرید بالا» یا «احتمال خرید پایین» قرار گرفته است. برای یک مشتری جدید، میتوانیم ویژگیهایی مانند تعداد بازدید از محصول، تعداد تماسها و میزان تعامل را با مشتریان قبلی مقایسه کنیم.
اگر از میان 5 مشتری نزدیک، 4 نفر در گروه «احتمال خرید بالا» باشند، KNN میتواند نمونه جدید را نیز در همان گروه قرار دهد.
منطق کلی الگوریتم به صورت زیر است:
- دادههای آموزشی و برچسبهای آنها را دریافت میکنیم.
- فاصله نمونه جدید تا تمام نمونههای آموزشی محاسبه میشود.
- نمونهها بر اساس فاصله مرتب میشوند.
- نزدیکترین
Kنمونه انتخاب میشوند. - در مسئله طبقهبندی، رایجترین کلاس میان همسایهها به عنوان پاسخ انتخاب میشود.
K در KNN چه معنایی دارد؟
K تعداد همسایههایی است که در تصمیمگیری شرکت میکنند.
اگر K = 1 باشد، تنها نزدیکترین نمونه تعیینکننده پاسخ است. این حالت میتواند نسبت به نویز بسیار حساس باشد.
اگر K = 3 باشد، سه همسایه نزدیک بررسی میشوند و کلاسی که بیشترین تکرار را دارد انتخاب میشود.
در مسائل طبقهبندی دودویی معمولاً استفاده از مقادیر فرد مانند 3، 5 یا 7 میتواند احتمال مساوی شدن رأیها را کاهش دهد؛ با این حال مقدار مناسب K باید بر اساس داده و اعتبارسنجی انتخاب شود.
فاصله اقلیدسی
یکی از رایجترین معیارهای فاصله در KNN، Euclidean Distance است.
برای دو نقطه دوبعدی:
A = (x1, y1)
B = (x2, y2)
فاصله برابر است با:
d = sqrt((x2 - x1)^2 + (y2 - y1)^2)
هرچه این مقدار کوچکتر باشد، دو نمونه از نظر ویژگیهای استفادهشده به یکدیگر نزدیکتر هستند.
یک مثال ساده
فرض کنید دادههای آموزشی ما چنین باشند:
(1, 2)→ کلاس A(2, 2)→ کلاس A(3, 3)→ کلاس A(7, 7)→ کلاس B(8, 7)→ کلاس B(8, 9)→ کلاس B
اکنون میخواهیم نقطه (2.5, 2.5) را با K = 3 طبقهبندی کنیم.
سه نقطه نزدیک به آن عمدتاً از کلاس A هستند؛ بنابراین خروجی الگوریتم کلاس A خواهد بود.
چرا نرمالسازی دادهها مهم است؟
فرض کنید دو ویژگی داریم:
- سن: بین 18 تا 70
- درآمد سالانه: بین 20,000 تا 500,000
اگر بدون مقیاسبندی از فاصله اقلیدسی استفاده کنیم، ویژگی درآمد به دلیل دامنه عددی بزرگتر تأثیر بسیار بیشتری بر فاصله خواهد داشت.
به همین دلیل در بسیاری از پروژهها قبل از KNN از روشهایی مانند Standardization یا Min-Max Scaling استفاده میشود.
KNN در Classification و Regression
KNN فقط برای طبقهبندی نیست.
Classification
در طبقهبندی، کلاس پرتکرار میان K همسایه انتخاب میشود.
Regression
در رگرسیون، میتوان میانگین یا میانگین وزندار مقدار K همسایه نزدیک را به عنوان پیشبینی در نظر گرفت.
مزایای KNN
- مفهوم بسیار ساده و قابل فهم
- نیاز نداشتن به مدلسازی پیچیده
- مناسب برای دادههای کوچک و متوسط
- قابل استفاده برای Classification و Regression
- عملکرد مناسب زمانی که نمونههای مشابه واقعاً خروجیهای مشابه دارند
محدودیتهای KNN
هزینه پیشبینی
KNN معمولاً در مرحله آموزش کار زیادی انجام نمیدهد، اما هنگام پیشبینی باید فاصله نمونه جدید تا تعداد زیادی از نمونههای آموزشی محاسبه شود.
حساسیت به مقیاس
ویژگیهایی با دامنه عددی بزرگ میتوانند فاصله را تحت تأثیر قرار دهند.
حساسیت به ویژگیهای غیرضروری
اگر تعداد زیادی ویژگی بیربط داشته باشیم، مفهوم «نزدیکی» ضعیفتر میشود.
Curse of Dimensionality
در ابعاد بسیار بالا، فاصله بین نقاط رفتار متفاوتی پیدا میکند و KNN ممکن است کارایی خود را از دست بدهد.
انتخاب K مناسب
K بسیار کوچک میتواند مدل را نسبت به نویز حساس کند و K بسیار بزرگ ممکن است مرزهای واقعی بین کلاسها را بیش از حد هموار کند.
روش مناسب این است که چند مقدار مختلف K را روی داده اعتبارسنجی آزمایش کنیم و مقداری را انتخاب کنیم که بهترین عملکرد تعمیمپذیر را ارائه میدهد.
KNN در دنیای واقعی کجا استفاده میشود؟
KNN میتواند در مسئلههایی مانند اینها مفید باشد:
- دستهبندی مشتریان بر اساس رفتار مشابه
- تشخیص ساده الگوهای غیرعادی
- سیستمهای پیشنهاددهنده مبتنی بر شباهت
- طبقهبندی نمونههای پزشکی یا آزمایشگاهی
- تشخیص نوع نمونه بر اساس ویژگیهای اندازهگیریشده
- ساخت Baseline سریع برای مسائل طبقهبندی
پیادهسازی الگوریتم
یک پیادهسازی ساده KNN معمولاً همین مراحل را دارد:
for each training point:
calculate distance to target
sort all points by distance
take the first K points
count their labels
return the most frequent label
در پیادهسازی JavaScript موجود در نمونه این پروژه نیز فاصله نمونه جدید تا تمام دادهها محاسبه میشود، فاصلهها مرتب میشوند، K نمونه اول انتخاب میشوند و کلاس پرتکرار به عنوان نتیجه بازگردانده میشود.
جمعبندی
KNN نشان میدهد که یک ایده بسیار ساده میتواند به یک الگوریتم واقعی یادگیری ماشین تبدیل شود: نمونههای مشابه معمولاً رفتار یا خروجی مشابهی دارند.
برای استفاده درست از KNN باید به انتخاب K، معیار فاصله، مقیاس ویژگیها، حجم داده و تعداد ابعاد توجه کرد. KNN برای یادگیری مفاهیم Machine Learning و همچنین ساخت مدلهای پایه بسیار ارزشمند است، اما در دادههای بسیار بزرگ یا بسیار پُربعد معمولاً باید با دقت بیشتری از آن استفاده کرد.