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

خونه‌ی تازه

فرض کنید یه خونه توی محله‌تون می‌خواد فروش بره و می‌خواید حدس بزنید چند می‌ارزه. چی کار می‌کنید؟

خیلی ساده: می‌رید می‌بینید خونه‌های نزدیکش چند فروش رفتن. اگه سه تا خونه‌ی بغلی متری ۹۰ و ۱۰۰ و ۱۱۰ رفتن، این یکی هم حدودا ۱۰۰ می‌ارزه. خونه‌های اون سر محله رو هم اصلا حساب نمی‌کنید.

یکی از ساده‌ترین الگوریتم‌های یادگیری ماشین دقیقا همین کار رو می‌کنه. اسمش KNN هست، یعنی «k تا نزدیک‌ترین همسایه». اینجا k سه بود.

رأی همسایه‌ها

قیمت خونه یه عدد بود، پس میانگین گرفتیم. ولی اگه سوال دسته‌بندی باشه چی؟ مثلا هر نقطه یا توپره یا توخالی، و یه نقطه‌ی تازه داریم.

اینجا جای میانگین، رأی می‌گیریم. سه تا نزدیک‌ترین رو پیدا می‌کنیم و هر دسته‌ای که بینشون بیشتره، جواب می‌شه. دو تا توپر، یکی توخالی؛ پس نقطه‌ی تازه توپره.

پس KNN دو جور جواب می‌ده:

• جواب عدد (مثل قیمت): میانگین k همسایه.
• جواب دسته (مثل توپر یا توخالی): رأی بیشتر بین k همسایه.

k چند باشه؟

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

جواب عوض شد! با k برابر ۱، فقط نزدیک‌ترین نقطه مهمه. اگه همون یه نقطه شانسی غلط برچسب خورده باشه، جواب ما هم غلط می‌شه. k بزرگ‌تر این شانس رو کم می‌کنه، ولی اگه زیادی بزرگ بشه، همسایه‌های دور هم رأی می‌دن و مرز بین دسته‌ها کم‌رنگ می‌شه.

پس k یه ابرپارامتره و باید با اعتبارسنجی متقابل انتخابش کرد. یه نکته‌ی کوچیک هم: وقتی فقط دو تا دسته داریم، k رو فرد بذارید تا رأی‌ها هیچ‌وقت مساوی نشن.

نزدیک یعنی چی؟

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

۴ قدم این‌ور، ۳ قدم اون‌ور؛ خط راست بینشون ۵ قدمه. با دو تا ویژگی همینه؛ با ده تا ویژگی هم همین حساب انجام می‌شه، فقط نمی‌شه کشیدش.

هم‌اندازه کردن

اینجا یه دام هست. فرض کنید خونه‌ها رو با دو تا ویژگی مقایسه می‌کنیم: متراژ و تعداد اتاق.

فرق متراژ می‌شه ۴۰ و فرق اتاق می‌شه ۱. توی حساب فاصله، اون ۴۰ همه‌چی رو می‌بره و تعداد اتاق تقریبا هیچ اثری نداره؛ نه چون مهم نیست، فقط چون عددش کوچیکه.

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

بی‌آموزش، ولی کند

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

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

چند نکته

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

درس بعد یه الگوریتم دیگه‌ی ساده ولی خیلی سریعه که جای فاصله، با احتمال کار می‌کنه: بیز ساده.