الگوریتم k نزدیک‌ترین همسایه (KNN)

KNN یکی از ساده‌ترین الگوریتم‌های طبقه‌بندی است و برای شروع یادگیری ماشین عالی است: ایده‌اش را در یک جمله می‌شود گفت و پیاده‌سازی‌اش چند خط بیشتر نیست.

یک مسئله‌ی ساده

فرض کنید قد و وزن چند نفر را داریم و می‌دانیم کدام زن و کدام مرد است. حالا قد و وزن یک نفر جدید را می‌دهیم: زن است یا مرد؟ (مسئله عمداً ساده است؛ با قد و وزن نمی‌شود دقیق جواب داد، ولی تقریب خوبی می‌دهد.)

دایره‌ها زن و مربع‌ها مرد هستند. لوزی سبز فرد جدید است و دایره‌ی خط‌چین نزدیک‌ترین همسایه‌اش را نشان می‌دهد.

اگر این سؤال را در کلاس بپرسید، جواب‌ها متفاوت است و هر کدام به یک خانواده از الگوریتم‌ها می‌رسد:

• «چون آن طرف همه مرد بودند»: یعنی در ذهنتان مرزی کشیده‌اید. الگوریتم‌هایی مثل SVM دنبال همین مرز هستند؛ خط، منحنی یا شکلی پیچیده‌تر.
• «چون به مردها نزدیک‌تر است»: یعنی با فاصله فکر کرده‌اید. این ایده‌ی KNN است.
• «چون در محدوده‌ی میانگین قد و وزن مردهاست»: یعنی با توزیع آماری فکر کرده‌اید. روش‌های آماری این‌طور کار می‌کنند.

نزدیک‌ترین همسایه

ما با چشم می‌بینیم کدام نقطه نزدیک‌تر است؛ کامپیوتر باید حساب کند:

1. فاصله‌ی نقطه‌ی جدید را تا همه‌ی نقطه‌های آموزشی حساب کن؛
2. فاصله‌ها را مرتب کن و نزدیک‌ترین را پیدا کن؛
3. برچسب نزدیک‌ترین نقطه را به نقطه‌ی جدید بده.

فاصله را معمولاً اقلیدسی حساب می‌کنیم؛ همان خط‌کش معمولی:

$$d(a, b) = \sqrt{\sum_{j} (a_j - b_j)^2}$$

مشکل: داده‌ی پرت

نزدیک‌ترین همسایه یک ضعف جدی دارد: فقط به یک نقطه نگاه می‌کند. اگر آن نقطه استثنا یا اشتباه برچسب‌خورده باشد، جواب غلط می‌شود. در دنیا خانمی با قد ۱۸۴ و وزن ۹۰ هم پیدا می‌شود. حالا اگر فردی با قد ۱۸۳ و وزن ۸۸ بیاید که نمی‌دانیم کیست، و نزدیک‌ترین نقطه به او همان خانم باشد، الگوریتم می‌گوید «زن»؛ در حالی که همه‌ی نقطه‌های دیگر اطرافش مرد هستند.

این مشکل فقط در مثال‌های ساختگی نیست. فرض کنید داده‌ی سنسورهایی را دارید که فردایش خراب شدند یا سالم ماندند. یک سنسور رفتار عجیبی داشته ولی تصادفاً خراب نشده و برچسب «سالم» خورده. سنسور جدیدی که دقیقاً شبیه آن رفتار می‌کند هم برچسب «سالم» می‌گیرد، با اینکه ده سنسور مشابه دیگر همه خراب شده‌اند. الگوریتم فقط به همسایگی خیلی محلی نگاه می‌کند و نمی‌تواند تعمیم دهد.

راه‌حل: k همسایه و رأی‌گیری

به جای یک همسایه، k همسایه‌ی نزدیک را پیدا می‌کنیم و برچسبی را انتخاب می‌کنیم که بیشترین تکرار را بینشان دارد. اگر k=3 باشد و دو تا از سه همسایه مرد باشند، جواب «مرد» است.

با k=1 (دایره‌ی کوچک) فقط داده‌ی پرت دیده می‌شود و جواب «زن» است. با k=3 (دایره‌ی بزرگ) دو همسایه از سه همسایه مرد هستند.

k یک ابرپارامتر است

چرا ۳؟ چرا ۵ یا ۷ نه؟ الگوریتم این عدد را پیدا نمی‌کند؛ ما به‌عنوان کاربر الگوریتم انتخابش می‌کنیم. به این مقدارها ابرپارامتر (hyperparameter) می‌گوییم. راهش آزمایش است: k را عوض کنید، دقت را بسنجید و بهترین را بردارید. در تکلیف این جلسه همین کار را با رسم نمودار انجام می‌دهید.

KNN با scikit-learn

پیاده‌سازی KNN ساده است، ولی کتابخانه‌ی scikit-learn آن را به همراه ده‌ها الگوریتم دیگر آماده دارد. scikit-learn متن‌باز است، جامعه‌ی بزرگی دارد و شرکت‌های بزرگ هم در توسعه‌اش سهیم‌اند. نصب:

pip install scikit-learn

داده‌ی ما ارقام دست‌نویس فارسی از دیتاست هدی است. تابع load_hoda (که در آن درس ساختیم) هزار تصویر برای آموزش و دویست تصویر برای آزمون برمی‌گرداند؛ هر تصویر به ۵×۵ کوچک شده و به یک بردار ۲۵تایی تبدیل شده است.

from sklearn.neighbors import KNeighborsClassifier
from dataset import load_hoda

X_train, y_train, X_test, y_test = load_hoda()
print(X_train.shape, X_test.shape)   # (1000, 25) (200, 25)

model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_train, y_train)

در scikit-learn همه‌ی الگوریتم‌ها متد fit برای آموزش و predict برای پیش‌بینی دارند. KNN در واقع «آموزش» به معنای دقیق ندارد؛ fit فقط داده‌ها را نگه می‌دارد (و برای سرعت، فهرستی از آن‌ها می‌سازد) تا موقع پیش‌بینی همسایه‌ها را پیدا کند. ولی رابط همه‌ی الگوریتم‌ها یکسان مانده است.

ورودی باید دوبعدی باشد

model.predict(X_test[12])       # خطا: Expected 2D array, got 1D array
model.predict([X_test[12]])     # درست: یک نمونه با ۲۵ ویژگی
model.predict(X_test)           # پیش‌بینی هر ۲۰۰ نمونه با هم

کتابخانه همیشه ماتریسی به شکل $n \times m$ می‌خواهد: $n$ نمونه، هر کدام با $m$ ویژگی. اگر فقط یک نمونه دارید، آن را در یک لیست بگذارید یا با reshape(1, -1) دوبعدی کنید.

ارزیابی: مدل چند درصد درست می‌گوید؟

import numpy as np

pred = model.predict(X_test)
correct = pred == y_test          # آرایه‌ای از True و False

print(np.sum(correct))            # 192
print(np.sum(correct) / len(y_test))   # 0.96
print(np.mean(correct))           # 0.96
print(model.score(X_test, y_test))     # 0.96

هر سه روش یک چیز را حساب می‌کنند: چند تا از چند تا را درست گفته. وقتی میانگین آرایه‌ای از True و False را می‌گیرید، True یک و False صفر حساب می‌شود؛ پس میانگین همان نسبت پاسخ‌های درست است. متد score هم خودش پیش‌بینی می‌کند و با برچسب‌ها مقایسه می‌کند.

کجاها اشتباه کرده؟

با همین ماسک True و False می‌شود اشتباه‌ها را پیدا کرد:

wrong = pred != y_test
print(y_test[wrong])   # برچسب واقعی:  [2 7 6 3 6 3 5 3]
print(pred[wrong])     # پیش‌بینی مدل: [3 2 7 1 7 2 1 5]

با یک نگاه معلوم است مدل روی رقم ۳ بیشترین مشکل را دارد: آن را یک بار ۱، یک بار ۲ و یک بار ۵ دیده و یک ۲ را هم ۳ دیده. در مقابل رقم ۹ را هیچ‌وقت اشتباه نکرده.

با اندازه‌ی تصویر بازی کنید

اندازه‌ی تصویرها هم یک ابرپارامتر است. با load_hoda(size=...) اندازه را عوض کنید:

اندازه	دقت
۵×۵	۹۶٪
۸×۸	۹۴٫۵٪
۱۰×۱۰	۹۵٪

بزرگ‌تر کردن تصویر لزوماً بهتر نیست: پیکسل‌های بیشتر یعنی جزئیات بیشتری از دست‌خط هر نفر، که برای KNN بیشتر شبیه نویز است. ولی از یک آزمایش نمی‌شود نتیجه‌ی قطعی گرفت؛ باید با داده‌ی بیشتر و به‌طور منظم امتحان کرد.

امتحان با دست‌خط خودتان

می‌توانید در Paint یک رقم بنویسید و از مدل بپرسید. فقط باید شرایط داده‌ی آموزشی را رعایت کنید: پس‌زمینه سیاه، رقم سفید، و برش تنگ (بدون حاشیه).

import cv2

img = cv2.imread("sample.jpg", 0)          # آرگومان 0 یعنی خاکستری بخوان
x = cv2.resize(img, (5, 5)).reshape(1, 25)
print(model.predict(x)[0])

اگر حاشیه‌ی دور رقم را نبرید، مدل تقریباً همیشه اشتباه می‌کند. KNN پیکسل به پیکسل مقایسه می‌کند: پیکسل اول با پیکسل اول، دوم با دوم. اگر رقم کمی جابه‌جا شود یا حاشیه داشته باشد، همه‌ی پیکسل‌ها جابه‌جا می‌شوند. در عوض به چند نقطه‌ی نویز کوچک حساسیت زیادی ندارد، چون با کوچک شدن تصویر به ۵×۵ محو می‌شوند. برای پیدا کردن و بریدن خودکار رقم‌ها در یک عکس واقعی، درس مؤلفه‌های همبند را ببینید.

محدودیت‌های KNN روی تصویر

ارقام دست‌نویس مثال خیلی ساده‌شده‌ای است: هفت را هر طور بنویسید، باز شبیه هفت است. ولی روی تصویرهای واقعی، KNN تقریباً هیچ‌وقت استفاده نمی‌شود:

• جابه‌جایی: اگر چهره‌ی یک نفر چند پیکسل جابه‌جا شود، فاصله‌ی پیکسلی با عکس قبلی‌اش زیاد می‌شود.
• تغییرهای ظاهری: عینک آفتابی، شال‌گردن، آرایش، ریش، نور داخل یا بیرون از خانه، گذر سن.
• فاصله‌ی گمراه‌کننده: تصویری که چند پیکسلش جابه‌جا شده، تصویری که بخشی از آن پوشانده شده و تصویری که کمی رنگش عوض شده می‌توانند دقیقاً یک فاصله با تصویر اصلی داشته باشند، در حالی که برای ما خیلی فرق دارند.
• کندی در زمان پیش‌بینی: برای هر پیش‌بینی باید با همه‌ی داده‌های آموزشی مقایسه کرد.

برای تصویرهای واقعی به مدل‌هایی نیاز داریم که خودشان ویژگی‌های مفید را یاد بگیرند؛ یعنی شبکه‌های عصبی و بعدتر شبکه‌های کانولوشنی. البته ایده‌ی «نزدیک‌ترین همسایه» هنوز زنده است: پایگاه‌داده‌های برداری که در جست‌وجوی متن و سیستم‌های RAG استفاده می‌شوند، در میلیاردها سند تقریباً نزدیک‌ترین همسایه‌ها را پیدا می‌کنند.

تکلیف

در تکلیف این جلسه با رسم نمودار دقت به ازای k از ۱ تا ۱۵ بهترین k را پیدا می‌کنید و بعد رقم‌های روی یک عکس واقعی را با مؤلفه‌های همبند پیدا و تشخیص می‌دهید.

تکلیف نوت‌بوک از ۱۰ نمره

انتخاب k و پیدا کردن رقم‌ها در عکس

این تکلیف دو بخش دارد:

1. انتخاب k (۴ نمره): مدل KNN را روی دیتاست هدی با k از ۱ تا ۱۵ آموزش دهید، دقت هر k را روی داده‌ی آزمون حساب کنید، نمودار «دقت بر حسب k» را رسم کنید و kای را که بیشترین دقت را دارد گزارش کنید.
2. پیدا کردن رقم‌ها در عکس (۴ نمره): عکسی از یک برگه داریم که چهار رقم دست‌نویس رویش نوشته شده. عکس را دودویی و معکوس کنید، با مؤلفه‌های همبند رقم‌ها را جدا کنید و با همان مدل KNN تشخیص دهید.

دو نمره‌ی دیگر برای این است که همه‌ی سلول‌ها به ترتیب و بدون خطا اجرا شده باشند. نوت‌بوک آماده است و فقط باید جاهای خالی را پر کنید؛ دیتاست و عکس هنگام اجرا خودکار دانلود می‌شوند.

1. دانلود نوت‌بوک تمرین
2. نوت‌بوک را در Jupyter، VS Code یا Colab باز کنید و جاهای خالی را کامل کنید. در آخر همه‌ی سلول‌ها را از اول اجرا کنید (Restart & Run All) و فایل را با خروجی‌ها ذخیره کنید؛ نوت‌بوک روی سرور اجرا نمی‌شود و همین خروجی‌ها بررسی می‌شوند.کتابخانه‌های لازم: numpy, scipy, opencv-python, scikit-learn, matplotlib
3. فایل حل‌شده (.ipynb) را انتخاب کنیدارسال برای تصحیح

خلاصه

• KNN برای هر نمونه‌ی جدید، k نمونه‌ی نزدیک را پیدا می‌کند و برچسب اکثریت را برمی‌گرداند.
• k=1 به داده‌ی پرت حساس است؛ k بزرگ‌تر اثر نویز را کم می‌کند. k ابرپارامتر است و با آزمایش انتخاب می‌شود.
• در scikit-learn: fit برای آموزش، predict برای پیش‌بینی و score برای دقت. ورودی همیشه دوبعدی است.
• روی ارقام هدی با تصویرهای ۵×۵ به دقت ۹۶٪ رسیدیم، ولی KNN برای تصویرهای واقعی مناسب نیست.