الگوریتم KNN به زبان ساده

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

با یک مثال شروع میکنم. در مدل ما، کلاس A داده‌ها آبی است و کلاس B داده‌های قرمز، و مقدار k ما ۳ است(در این مثال k=3 انتخاب خوبی است). حالا میخواهیم ببینیم داده جدید ما در کدام کلاس طبقه‌بندی میشود.

چون k=3 در نظر گرفتیم، سه نقطه نزدیک به نقطه سبز را پیدا میکنیم: دو تایشان قرمز و یکی آبی است.حالا سوال پیش میاید که «چطور فاصله‌ها را حساب کردم؟» جواب اینه که: با فاصله اقلیدسی (نرم L2). البته تنها راه ما برای محاسبه فاصله اقلیدسی نیست و فواصل دیگری هم داریم! پس بیایید قبل از ادامه با فواصل مختلف آشنا شویم.

خانواده مینکوفسکی شامل بسیاری از فاصله‌های معروف است. با تغییر مقدار p، فاصله‌های معروف زیر به دست می‌آیند:

زمانی که p=1 شود، فقط حرکت افقی و عمودی در نظر گرفته می‌شود. چون توان ندارد، به داده‌های پرت حساس نیست و گاهی ممکن است بهتر عمل کند (بسته به مدل و داده‌ها).

فاصله اقلیدسی پرکاربردترین فاصله در یادگیری ماشین است. کوتاه‌ترین مسیر بین دو نقطه را محاسبه میکند. به داده‌های پرت حساس است (به دلیل توان دوم).

فاصله چیبشف زمانی که ∞ → p میل کند به دست می‌آید و فقط بزرگترین اختلاف در یک بعد را در نظر می‌گیرد.

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

حالا که فهمیدید چطور فاصله هر نقطه تا نقطه جدید را حساب کردم، بریم ببینیم چطور این فاصله‌ها را نمایش دهیم.

حالا بریم ببینیم چطور سه نقطه نزدیک را به نقطه جدید وصل میکنیم:

کلاس B به عنوان کلاس اکثریت انتخاب شد. (اگر مسئله رگرسیون بود، با میانگین گرفتن از مقادیر همسایه‌ها، خروجی تخمین زده میشد.)

الگوریتم KNN یک الگوریتم Instance Based و Non-parametric هست. یعنی چی؟ خب اول از همه Instanced based یعنی:

Instance‑Based: داده‌های آموزش را ذخیره میکند و تا زمان تست از آنها استفاده نمیکند (Lazy Learning).

Non‑Parametric: تعداد پارامترها با افزایش داده افزایش نمی یابد(برخلاف مدل‌های Parametric مانند رگرسیون خطی).

این ویژگی‌ها باعث میشود KNN هم Lazy باشد (چون داده را ذخیره میکند) و هم در زمان آموزش سریع (چون محاسبه‌ ای انجام نمیدهد)، اما در زمان تست کند است (چون باید فاصله همه نقاط را محاسبه کند).

و چند نکته اخر درمورد KNN:

1.حساسیت به داده پرت: چون بر اساس فاصله کار میکند، داده‌های پرت میتوانند تأثیر زیادی روی نتیجه بگذارند.

2.انتخاب k: مقدار k باید بر اساس مسئله تنظیم شود:

k کوچک: مدل پیچیده، بیش‌برازش (Overfitting)، مرزهای تیز

k بزرگ: مدل ساده، کم‌برازش (Underfitting)، مرزهای نرم

3.نرمالایز کردن داده‌ها: قبل از استفاده از KNN، حتماً ویژگی‌ها را نرمالایز کنید (مقیاس یکسان) تا بعدی با دامنه بزرگتر بر فاصله غالب نشود.

خب اینم از KNN! خوشحال میشم نظراتتون رو درمورد این الگوریتم ببینم! ممنونم که تا اینجا خوندین.