Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

k نزدیک‌ترین همسایه و سنجه‌های ارزیابی دسته‌بندی

English · فارسی

k نزدیک‌ترین همسایه و سنجه‌های ارزیابی دسته‌بندی

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

این نوت‌بوک پوشش می‌دهد:

  1. مروری بر الگوریتم k نزدیک‌ترین همسایه (kNN)

  2. سنجه‌های ارزیابی دسته‌بندی: دقت، دقت مثبت (precision)، بازیابی (recall) و امتیاز F1

Notebook Cell

مروری بر k نزدیک‌ترین همسایه (kNN)

الگوریتم k نزدیک‌ترین همسایه — که در ابرپارامترها و اعتبارسنجی مدل دیدیم — روشی ناپارامتری و نمونه‌محور برای دسته‌بندی و رگرسیون است. الگوریتم k نمونهٔ آموزشیِ نزدیک‌تر به نمونهٔ تازه را می‌یابد و بر پایهٔ رأی اکثریت برچسب کلاس را پیش‌بینی می‌کند.

ویژگی‌های کلیدی kNN:

  • ناپارامتری: الگوریتم دربارهٔ توزیع زیربنایی داده فرضی نمی‌گذارد.

  • نمونه‌محور (یادگیری تنبل): فاز آموزش صریحی ندارد؛ مدل فقط دادهٔ آموزش را نگه می‌دارد.

  • فاصله‌محور: پیش‌بینی بر پایهٔ فاصلهٔ میان نقطه‌ها انجام می‌شود.

الگوریتم kNN (به روایت دودا و همکاران):

  1. همهٔ نمونه‌های آموزشی را با برچسب کلاسشان ذخیره کن.

  2. برای نمونهٔ تازهٔ x:

    • فاصلهٔ x تا همهٔ نمونه‌های آموزشی را حساب کن.

    • k نمونهٔ آموزشی نزدیک‌تر (k نزدیک‌ترین همسایه) را برگزین.

    • برچسب کلاس را بر پایهٔ رأی اکثریت میان این k همسایه نسبت بده.

سنجه‌های فاصله:

رایج‌ترین سنجه‌های فاصله در kNN:

  1. فاصلهٔ اقلیدسی: d(x,y)=∑i=1n(xi−yi)2d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}

  2. فاصلهٔ منهتن: d(x,y)=∑i=1n∣xi−yi∣d(x, y) = \sum_{i=1}^{n} |x_i - y_i|

  3. فاصلهٔ مینکوفسکی: d(x,y)=(∑i=1n∣xi−yi∣p)1/pd(x, y) = (\sum_{i=1}^{n} |x_i - y_i|^p)^{1/p}

بیایید الگوریتم kNN را پیاده و مصور کنیم:

Source
<Figure size 1000x600 with 2 Axes>
Source
<Figure size 1500x500 with 3 Axes>

مشاهده‌هایی دربارهٔ رفتار kNN:

  1. اثر k:

    • k کوچک: مرزهای تصمیم پیچیده‌ترند و می‌توانند به بیش‌برازش بینجامند

    • k بزرگ: مرزهای تصمیم نرم‌ترند ولی ممکن است الگوهای مهم را از دست بدهند

  2. پیچیدگی محاسباتی:

    • آموزش: O(1) — فقط داده ذخیره می‌شود

    • پیش‌بینی: O(nd) که n تعداد نمونه‌های آموزش و d تعداد ویژگی‌هاست

  3. نفرین ابعاد:

    • با افزایش تعداد بُعدها، سنجهٔ فاصله معناداری‌اش را از دست می‌دهد

    • در ابعاد بالا همهٔ نقطه‌ها گرایش دارند به یک اندازه از هم دور باشند

سنجه‌های ارزیابی دسته‌بندی

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

ماتریس درهم‌ریختگی

ماتریس درهم‌ریختگی جدولی است که کارایی یک مدل دسته‌بندی را توصیف می‌کند. برای مسئلهٔ دسته‌بندی دودویی شامل این‌هاست:

  • مثبت‌های درست (TP): نمونه‌های مثبتی که درست پیش‌بینی شده‌اند

  • مثبت‌های نادرست (FP): نمونه‌های مثبتی که نادرست پیش‌بینی شده‌اند (خطای نوع اول)

  • منفی‌های درست (TN): نمونه‌های منفی که درست پیش‌بینی شده‌اند

  • منفی‌های نادرست (FN): نمونه‌های منفی که نادرست پیش‌بینی شده‌اند (خطای نوع دوم)

بیایید با make_classification یک مسئلهٔ دسته‌بندی دودویی بسازیم و ماتریس درهم‌ریختگی آن را ببینیم:

Source
<Figure size 1000x600 with 2 Axes>
Source
<Figure size 800x400 with 2 Axes>
True Negatives (TN): 141
False Positives (FP): 6
False Negatives (FN): 13
True Positives (TP): 140

دقت

دقت نسبت نمونه‌های درست‌پیش‌بینی‌شده به کل نمونه‌هاست.

Accuracy=TP+TNTP+TN+FP+FN\text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN}

مزایا:

  • ساده و شهودی

  • برای مجموعه‌دادهٔ متوازن خوب کار می‌کند

معایب:

  • برای مجموعه‌دادهٔ نامتوازن گمراه‌کننده است

  • میان انواع خطا تمایز نمی‌گذارد

Accuracy: 0.9367
Manually calculated accuracy: 0.9367

دقت مثبت و بازیابی

دقت مثبت (Precision)

دقت مثبت نسبت نمونه‌های مثبت درست‌پیش‌بینی‌شده به کل نمونه‌های مثبتِ پیش‌بینی‌شده است. به این پرسش پاسخ می‌دهد: «از همهٔ نمونه‌هایی که مثبت پیش‌بینی شدند، چند تا واقعاً مثبت‌اند؟»

Precision=TPTP+FP\text{Precision} = \frac{TP}{TP + FP}

کاربردها و مثال‌های کلیدی:

  • تشخیص هرزنامه — علامت‌زدن نادرست ایمیل مهم گران است

  • آزمایش پزشکی — پرهیز از تشخیص نادرست که به درمان بی‌مورد می‌انجامد

  • خودروهای خودگردان — تشخیص نادرست مانع می‌تواند واکنش خطرناکی بسازد

مزایا:

  • وقتی مثبت‌های نادرست (FP) پیامد سنگین دارند حیاتی است

  • برای کاربردهایی که در آن‌ها پیش‌بینی مثبتِ نادرست گران است ضروری است

  • در سامانه‌های بازیابی اطلاعات که مرتبط بودن مهم است بسیار ارزشمند است

معایب:

  • منفی‌های نادرست را نادیده می‌گیرد (ممکن است موارد مهم را از دست بدهد)

  • اگر مدل در پیش‌بینی بیش از اندازه محافظه‌کار باشد می‌تواند به‌طور گمراه‌کننده بالا باشد

  • برای مجموعه‌دادهٔ نامتوازن که منفی‌ها غالب‌اند به‌تنهایی کافی نیست

Precision: 0.9589
Manually calculated precision: 0.9589

بازیابی (حساسیت)

بازیابی نسبت نمونه‌های مثبت درست‌پیش‌بینی‌شده به همهٔ مثبت‌های واقعی است. به این پرسش پاسخ می‌دهد: «از همهٔ نمونه‌های مثبتِ واقعی، چند تا را درست پیش‌بینی کردیم؟»

Recall=TPTP+FN\text{Recall} = \frac{TP}{TP + FN}

کاربردها و مثال‌های کلیدی:

  • تشخیص پزشکی

  • کشف تقلب

  • کشف مین

  • پایش امنیتی

  • سامانه‌های هشدار زودهنگام زلزله

  • کشف تهدید در امنیت سایبری

  • عملیات جست‌وجو و نجات

مزایا:

  • وقتی هزینهٔ منفی‌های نادرست (FN) بالا است حیاتی می‌شود (مثلاً سناریوهای تهدیدکنندهٔ جان).

  • برای غربالگری پزشکی و کاربردهای ایمنی عمومی ضروری است.

معایب:

  • مثبت‌های نادرست (FP) را در نظر نمی‌گیرد (می‌تواند به هشدارهای بی‌مورد بینجامد).

  • اگر مدل همه‌چیز را مثبت برچسب بزند می‌تواند مصنوعی بالا برود.

نکتهٔ بده‌بستان: در بسیاری از سامانه‌های واقعی میان دقت مثبت و بازیابی رابطهٔ معکوس هست — بهبود یکی معمولاً دیگری را بدتر می‌کند. توازن درست به این بستگی دارد که کدام نوع خطا (FP یا FN) برای کاربرد شما گران‌تر است.

Recall: 0.9150
Manually calculated recall: 0.9150

امتیاز F1

امتیاز F1 میانگین هارمونیک دقت مثبت و بازیابی است. توازنی میان این دو برقرار می‌کند.

F1-Score=2×Precision×RecallPrecision+Recall\text{F1-Score} = 2 \times \frac{\text{Precision} \times \text{Recall}}{\text{Precision} + \text{Recall}}

مزایا:

  • دقت مثبت و بازیابی را متوازن می‌کند

  • برای مجموعه‌دادهٔ نامتوازن خوب کار می‌کند

معایب:

  • اگر یکی از دو سنجه مهم‌تر از دیگری باشد ممکن است مناسب نباشد

  • منفی‌های درست را در نظر نمی‌گیرد

F1-Score: 0.9365
Manually calculated F1-Score: 0.9365

بده‌بستان دقت مثبت و بازیابی

اغلب میان دقت مثبت و بازیابی بده‌بستان هست: افزایش یکی معمولاً دیگری را کم می‌کند.

بیایید این بده‌بستان را با تغییر آستانهٔ تصمیم یک دسته‌بند احتمالاتی ببینیم:

<Figure size 1000x600 with 2 Axes>
Source

نمونهٔ این مثال sklearn دربارهٔ weights در kNN را ببینید

Source
<Figure size 1000x500 with 6 Axes>
Source
<Figure size 1200x600 with 2 Axes>

انتخاب سنجهٔ درست

انتخاب سنجهٔ ارزیابی به مسئلهٔ مشخص و هزینهٔ نسبی انواع خطا بستگی دارد:

  • دقت: وقتی کلاس‌ها متوازن‌اند و همهٔ انواع خطا هزینهٔ مشابه دارند

  • دقت مثبت: وقتی مثبت‌های نادرست گران‌ترند (مثلاً تشخیص هرزنامه)

  • بازیابی: وقتی منفی‌های نادرست گران‌ترند (مثلاً تشخیص بیماری)

  • امتیاز F1: وقتی به توازنی میان دقت مثبت و بازیابی نیاز دارید

مطالعهٔ بیشتر

سنجه‌ها برای دسته‌بندی چندکلاسه

برای مسائل چندکلاسه این سنجه‌ها را با راهبردهای میانگین‌گیری گوناگون می‌توان گسترد:

  • میانگین ماکرو: سنجه را برای هر کلاس حساب کن و میانگین بگیر (همهٔ کلاس‌ها برابر)

  • میانگین میکرو: سنجه را با مجموع مثبت‌های درست، مثبت‌های نادرست و… حساب کن (سوگرفته به کلاس‌های بزرگ‌تر)

  • میانگین وزنی: سنجه را برای هر کلاس حساب کن و بر پایهٔ فراوانی کلاس وزن بده

Source
Multi-class Classification Metrics:
            Macro   Micro  Weighted
Precision  0.9652  0.9667    0.9677
Recall     0.9648  0.9667    0.9667
F1-Score   0.9645  0.9667    0.9666

خلاصه

در این نوت‌بوک پوشش دادیم:

  1. k نزدیک‌ترین همسایه (kNN):

    • الگوریتمی ناپارامتری و نمونه‌محور

    • از سنجه‌های فاصله برای یافتن k نمونهٔ آموزشی نزدیک‌تر بهره می‌برد

    • پیش‌بینی را بر پایهٔ رأی اکثریت انجام می‌دهد

    • انتخاب k پیچیدگی مرزهای تصمیم را تعیین می‌کند

  2. سنجه‌های ارزیابی دسته‌بندی:

    • ماتریس درهم‌ریختگی: جدولی از شمار مثبت/منفی‌های درست و نادرست

    • دقت: نسبت پیش‌بینی‌های درست

    • دقت مثبت: نسبت مثبت‌های درست میان مثبت‌های پیش‌بینی‌شده

    • بازیابی: نسبت مثبت‌های درست میان مثبت‌های واقعی

    • امتیاز F1: میانگین هارمونیک دقت مثبت و بازیابی

    • بده‌بستان دقت مثبت و بازیابی: تغییر آستانهٔ تصمیم هر دو را عوض می‌کند

این مفاهیم پایهٔ فهم الگوریتم‌های دسته‌بندی و ارزیابی کارایی‌شان را می‌سازند. در نوت‌بوک بعد نمودارهای ورونوی و پیوندشان با kNN و نظریهٔ تصمیم بیزی را می‌بینیم.

تمرین‌ها

  1. از ماتریس درهم‌ریختگی نوت‌بوک، دقت مثبت، بازیابی و F1F_1 را برای هر کلاس، هم دستی و هم با sklearn حساب کنید و هر تفاوت میان میانگین میکرو و ماکرو را توضیح دهید.

  2. دسته‌بندی که روی یک تقسیم ۹۵/۵ همیشه کلاس اکثریت را پیش‌بینی می‌کند به دقت 95%95\% می‌رسد. دقت مثبت، بازیابی و F1F_1 آن را برای کلاس اقلیت حساب کنید و بگویید یک سنجهٔ سودمند باید چه چیزی گزارش کند.

  3. kNN را با فاصلهٔ L1L_1 و L2L_2 پیاده کنید و هر دو را روی مجموعه‌داده‌ای با چند داده‌پرته مقایسه کنید. کدام سنجه اینجا استوارتر است و چرا؟

  4. نشان دهید چرا kNN هزینهٔ آموزش ندارد ولی هزینهٔ پیش‌بینی‌اش در nn خطی است، و تعداد محاسبهٔ فاصله را برای n=104n=10^4، d=10d=10 و k=5k=5 برآورد کنید.

منابع

  1. Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern Classification (2nd ed.). Wiley-Interscience.

  2. دقت مثبت و بازیابی — ویکی‌پدیا

  3. ماتریس درهم‌ریختگی — ویکی‌پدیا

  4. مستندات Scikit-learn — ارزیابی مدل