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 نزدیک‌ترین همسایه و سنجه‌های ارزیابی دسته‌بندی

این نوتبوک شامل این‌ها است:

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

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

English · فارسی
English · فارسی
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: وقتی به توازنی میان دقتِ مثبت و بازآوری نیاز دارید

آیا «نقطهٔ بهینه» روی منحنی دقتِ مثبت–بازآوری وجود دارد؟

پاسخ کوتاه: نه، یک نقطهٔ بهینهٔ یکتا و جهانی روی منحنی دقتِ مثبت–بازآوری وجود ندارد. ولی مفهوم «نقطهٔ بهینه» را می‌توان به چند معنای معنادار و وابسته به زمینهٔ مسئله تعریف کرد.

چرا نقطهٔ بهینهٔ مطلق وجود ندارد

1. ماهیت مبادله

هر نقطه روی منحنی دقتِ مثبت–بازآوری به یک آستانهٔ تصمیم متفاوت متناظر است. با حرکت روی منحنی:

  • بالا بردن آستانه دقتِ مثبت را زیاد و بازآوری را کم می‌کند.

  • پایین آوردن آستانه بازآوری را زیاد و دقتِ مثبت را کم می‌کند.

پس هر نقطه توازنی متفاوت میان این دو سنجه است و هیچ نقطه‌ای هم‌زمان هر دو را بیشینه نمی‌کند (مگر حالت آرمانی که منحنی به گوشهٔ بالا-راست می‌رسد).

2. وابستگی به هزینهٔ خطا

«بهینه» با هزینهٔ نسبی مثبت‌های نادرست در برابر منفی‌های نادرست در کاربرد داده‌شده تعریف می‌شود:

  • اگر FP گران‌تر باشد (مثلاً تشخیص هرزنامه)، نقطه‌ای با دقتِ مثبت بالا بهینه است.

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

  • اگر هزینه‌ها متوازن باشند، نقطه‌ای که امتیاز F1 را بیشینه می‌کند انتخاب معقولی است.

چه چیزی را می‌توان «بهینه» دانست؟

1. نقطه‌ای با بالاترین امتیاز F1

این رایج‌ترین معیار انتخاب نقطه روی منحنی است. امتیاز F1 میانگین هارمونیک دقتِ مثبت و بازآوری است و نقطه‌ای که آن را بیشینه می‌کند توازن معقولی میان این دو می‌دهد.

با نگاه به نمودار سمت چپ بالا (دقتِ مثبت، بازآوری و F1 در برابر آستانه)، امتیاز F1 (خط سبز) در آستانهٔ مشخصی به قله می‌رسد. توجه کنید این قله ممکن است در 0.5 نباشد — به‌ویژه برای مجموعه‌داده‌های نامتوازن، آستانهٔ بهینهٔ F1 اغلب کمتر از 0.5 است (در این مثال حدود 0.29 تا 0.32).

2. نقطه‌ای نزدیک‌ترین به گوشهٔ بالا-راست

در برخی تحلیل‌ها نقطه‌ای با کمترین فاصلهٔ اقلیدسی تا (Precision=1, Recall=1) بهینه انتخاب می‌شود. این معیار ساده است ولی هزینهٔ واقعی مسئله را نادیده می‌گیرد.

یافتن آستانهٔ بهینه با یک شبکهٔ متراکم

این کد 100 آستانهٔ یکنواخت میان 0 و 1 را ارزیابی می‌کند تا آستانه‌ای را بیابد که امتیاز F1 را بیشینه می‌کند؛ تقریبی ریزدانه از مرز تصمیم بهینه.

Best threshold: 0.29, Best F1: 0.8757

یافتن آستانهٔ بهینه با precision_recall_curve در Scikit-learn

این کد از تابع آمادهٔ precision_recall_curve در Scikit-learn استفاده می‌کند که دقتِ مثبت و بازآوری را در هر مقدار احتمال متمایزی که مدل تولید می‌کند حساب می‌کند و برآورد دقیق‌تر و اصولی‌تری از آستانهٔ بهینه می‌دهد.

Best threshold: 0.32

چرا نقطهٔ «بهینه»ی دیداری در 0.5 با نتیجهٔ محاسباتی فرق دارد

در نوتبوک اصلی فقط پنج آستانه (0، 0.1، 0.5، 0.9، 1) ارزیابی شده بود. پس نمودار حاصل تقریب بسیار زبری است — فقط پنج نقطه که با خط به هم وصل شده‌اند. به‌طور دیداری F1 در 0.5 قله می‌زند فقط چون هیچ آستانهٔ ریزتری میان 0.1 و 0.5 آزموده نشده بود.

وقتی از شبکهٔ متراکمی از آستانه‌ها (مثلاً 100 نقطه با np.linspace) یا از precision_recall_curve استفاده شود، بیشینهٔ واقعی امتیاز F1 در آستانهٔ پایین‌تری (حدود 0.29 تا 0.32 در این مثال) پیدا می‌شود. این برای مجموعه‌داده‌های نامتوازن انتظار می‌رود:

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

  • در آستانهٔ پایین‌تر (مثلاً 0.3) مدل بیشتر دستهٔ مثبت را پیش‌بینی می‌کند و بازآوری را بالا می‌برد با هزینهٔ کوچکی در دقتِ مثبت. چون F1 میانگین هارمونیک است، این توازن معمولاً امتیاز F1 بالاتری می‌دهد.

تفاوت کوچک دو روش (0.29 در برابر 0.32)

دو رویکرد آستانه‌های بهینهٔ کمی متفاوت می‌یابند:

  • روش np.linspace 100 آستانهٔ یکنواخت را ارزیابی می‌کند و نزدیک‌ترین را برمی‌گرداند (0.29).

  • روش precision_recall_curve آستانه‌ها را در هر مقدار احتمال متمایز تولیدشده توسط مدل ارزیابی می‌کند و برآورد اصولی‌تری می‌دهد (0.32).

تفاوت حدود 0.03 ناچیز است و هر دو روش به همان ناحیهٔ بهینه اشاره می‌کنند. برای گزارش نهایی، precision_recall_curve عموماً ترجیح دارد چون بر توزیع واقعی احتمال‌های پیش‌بینی‌شده استوار است و نه بر یک شبکهٔ دلبخواه.

معیارنقطهٔ بهینه
بیشینه کردن امتیاز F1نقطه‌ای با بالاترین F1 (در این مثال ≈ 0.29–0.32)
کمینه کردن هزینهٔ کلبه هزینه‌های نسبی FP و FN بستگی دارد
نزدیک‌ترین به (1, 1)کمترین فاصلهٔ اقلیدسی تا گوشهٔ بالا-راست
بیشترین بازآوری با دقتِ مثبت قابل قبولآستانه‌ای که دقتِ مثبت را بالای سطح مطلوب نگه می‌دارد

به کوتاهی، «نقطهٔ بهینه» مفهومی نسبی است که به معیار انتخاب و هزینهٔ خطاهای مسئلهٔ مشخص بستگی دارد. در این نوتبوک معقول‌ترین انتخاب نقطه‌ای است که امتیاز F1 را بیشینه می‌کند، یعنی آستانه‌ای حدود 0.3، نه پیش‌فرض 0.5.

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

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

برای مسائل چنددسته‌ای، این سنجه‌ها را می‌توان با راهبردهای میانگین‌گیری مختلف بسط داد:

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

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

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

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

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

برای مسائل چنددسته‌ای، این سنجه‌ها را می‌توان با راهبردهای میانگین‌گیری مختلف بسط داد:

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

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

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

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. Duda, R. O., Hart, P. E., & Stork, D. G. (2001). Pattern Classification (2nd ed.). Wiley-Interscience.

  2. Precision and Recall - Wikipedia

  3. Confusion Matrix - Wikipedia

  4. Scikit-learn Documentation - Model Evaluation