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

اسم الگوریتم: KNN یا ( K تا ) نزدیک ترین همسایه.

توی این مقاله ، قصد داریم الگوریتم  KNN رو یاد بگیریم. با توجه به اینکه یک مثال عملی ِ خوب و جذاب، میتونه تاثیر بهتری داشته باشه تا پرحرفی و کلی گویی، ما هم راه عملی رو پیش خواهیم گرفت. قبل از شروع ، باید بعضی از مفاهیم ساده رو با هم مرور کنیم.

این الگوریتم به چه دردی خواهد خورد؟

طبقه بندی کردن کلا" برای ما مهم بوده و هست. ما غالبا" در حال طبقه بندی و مقایسه ی پدیده های دور و بر خودمون هستیم. غذای خوب، غذای شرقی، آدم حساس، فیلم تاثیر گذار..

معمولا" هروقت ما نیاز داریم یک چیزی رو طبقه بندی کنیم و ایده ای نداریم، سعی میکنیم ازمقایسه اون موضوع با داده های قبلیمون به نتیجه برسیم. منطقی به نظر میاد نه؟ موسیقی میتونه یک مثال ملموس باشه. شما با شنیدن یک آهنگی که قبلا" نشنیدید، با توجه به داده های قبلی ذهنتون سعی میکنید اونو توی یک گروه بگنجونید. میگید سنتی، یا کلاسیک یا پاپ. این که شما یک چراغ راهنمایی با شکل و شمایل کاملا" جدید رو توی یک کشور دیگه میبینید و میشناسید، دلیلش اینه که شما چراغ راهنما زیاد دیدید. بینشون به یکسری جمع بندی و نتیجه رسیدید که آها، اسمش، شکلش، جایی که معمولا" میشه اونو دید، کاربردش و غیره.

برگردیم به الگوریتم KNN و ببینیم چطور میتونه مارو کمک کنه توی طبقه بندی کردن. فرض کنید یک جعبه داریم پراز فیلم با ژانر و محتوای مختلف و از قبل مشخص شده. من به شما یک نمونه فیلم که تا به حال ندید میدم و از شما میخوام 6 تا از شبیه ترین فیلم های موجود رو برای من رو پیدا کنید. بعد توی اون 6 تا ببینید اکثرا" توی چه ژانری هستند. با این کار،من میتونم بهترین طبقه بندی رو با توجه به طبقه بندی های قبلی برای فیلمم انجام بدم.

توی این مثال، K همون 6 هست و همسایه ها، همون شبیه ترین فیلم ها.

سوال اینجاست که توی این الگوریتم، چطور فیلم جدید من با فیلم های قبلی مقایسه شد؟ روی چه حسابی 6 تا فیلم به عنوان شبیه ترین ها انتخاب شدند؟ سوال خوبیه. برای توضیح به این سوال باید یکمی برگردیم به هندسه اما نگران نباشید اگر چیزی یادتون نمیومد از فرمول ها. من خودم هم چیزی یادم نمیامد اوایل، بعد سعی کردم ازنو یاد بگیرم. طبق تعریفی که توی ویکیپیدیا اومده:

فاصلهٔ دو نقطهٔ p و q اندازهٔ پاره‌خطی‌ست که آنها را به هم متصل می‌کند (). در مختصات دکارتی اگر:

p = (p_۱, p_۲... p_n)
q = (q_۱, q_۲,...q_n)

دو نقطه در فضای اقلیدسی n بعدی باشند، آنگاه فاصلهٔ بین آنها به صورت زیر تعریف می‌شود:

برای توضیح رابطه ی بالا، بهتره برگردیم به مثال فیلم. به نظر شما چه خصوصیاتی از یک فیلم رو میشه با دیگری مقایسه کرد؟

خصوصیت	مثال
زبان	فرانسوی
کارگردان	خانوم x
نویسنده	آقای y
سال تولید	1990
مدت	90 دقیقه
تعداد هنرپیشه ستاره	4
تعداد جایزه بین المللی	7
تعداد صحنه های احساسی	2
تعداد صحنه های اکشن	10
..

حالا ما میتونیم همه خصوصیت های یک فیلم رو کنار هم به شکل یک بردار ببینیم و تعداد اونها فضای n بعدی ما رو تشکیل میده. یک مثال برای فضای دو بعدی میتونه به شکل زیر باشه:

p = (تعداد صحنه های احساسی, تعداد صحنه های اکشن) = (1, 7)
q = (تعداد صحنه های احساسی, تعداد صحنه های اکشن) = (5, 2)

در نتیجه طبق تعریف، اندازه پاره خط  خواهد بود:

((۷-۲)² + (۱-۵)²)^1/2 = ۶.۷ cm

درواقع ما با تبدیل کردن خصوصیات فیلم به بردار، می تونیم ازریاضیات بهره ببریم و فاصله فیلم خودمون رو از فیلم های موجود توی یک دستگاه دکارتی چند بعدی (توی مثال فیلم، 9 بعدی) بدست بیاریم.