رایگان: همین الان رتبه‌ ارشدت رو تخمین بزن! کافیه عضو این بات تلگرامی رایگان بشین و دقیق‌ترین تخمین از رتبه‌تون رو دریافت کنین.
عضویت در بات تخمین رتبه
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

الگوریتم knn چیست؟ آموزش الگوریتم K نزدیک ترین همسایه

این مقاله الگوریتم knn یا همان الگوریتم K نزدیک ترین همسایه را بصورت کامل بررسی و مثالی علمی از الگوریتم KNN آورده و کاربردهای الگوریتم KNN را گفته است

K نزدیک ترین همسایه یا K-Nearest Neighbors که به‌اختصار به آن KNN می‌گویند، جزو ساده‌ترین الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد‌ها در بحث طبقه‌بندی است. این الگوریتم در واقع یک الگوریتم یادگیری است که در حل مسائل رگرسیون (Regression) و طبقه‌بندی (Classification) مورد استفاده قرار می‌گیرد. ابتدا با یک مثال ساده به توضیح کلی در مورد کارکرد این الگوریتم می‌پردازیم و سپس با مثال علمی‌تر به جزئیات این الگوریتم خواهیم پرداخت.

این تصویر مفهوم الگوریتم K نزدیک ترین همسایه را می رساند

فرض کنید داده‌های دانش‌آموزان یک کلاس در دستان شما قرار دارد و شما این دانش‌آموزان را به 2 دسته تقسیم‌بندی می‌کنید. دسته اول دانش‌آموزانی که معدل سال قبل آنها بالای 17.5 بوده است و روزانه بیشتر از 3 ساعت درس می‌خوانند و دسته دوم دانش آموزانی که معدل آنها کمتر از 17.5 است و روزانه کمتر از 3 ساعت درس می‌خوانند؛ حال نتایج کنکور آمده است و شما این نتایج را با دسته‌بندی خود مقایسه می‌کنید و می‌بینید که 90 درصد دانش‌آموزان دسته اول در کنکور رتبه خوبی کسب کرده‌اند و اما از دسته دوم تنها 25 درصد دانش‌آموزان موفق به کسب رتبه خوب در کنکور شده‌اند. حالا فرض کنید دانش‌آموز جدیدی قصد ثبت نام در کنکور را دارد و شما می‌خواهید پیش‌بینی کنید آیا این دانش‌آموز موفق به کسب رتبه خوب در کنکور خواهد شد یا خیر. این دانش‌آموز روزانه 4 ساعت درس می‌خواند و معدل آن 18 است. قطعا شما این دانش‌آموز را بدون هیچ‌گونه تردیدی در دسته اول قرار می‌دهید. دلیل این کار هم بسیار ساده است، این دانش‌آموز به دانش‌آموزان دسته اول نزدیک‌تر است تا دانش‌آموزان دسته دوم و از آنجایی که 90 درصد دانش‌آموزان دسته اول در کنکور رتبه خوبی کسب کرده‌اند، شانس این دانش‌آموز را برای قبولی در کنکور بالا می‌دانید.

مثالی علمی از الگوریتم KNN

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

پرداخت به موقع قسطویژگی دوم: میزان حقوقویژگی اول: سابقه کارشماره
خیر 7 میلیون 5 سال #1
بله 17 میلیون 13 سال #2
خیر 11 میلیون 9 سال #3
خیر 6 میلیون 13.5 سال #4
بله 12 میلیون 16 سال #5
بله 18 میلیون 21 سال #6
بله 6.5 میلیون 23.5 سال #7
خیر 14 میلیون 20 سال #8

اکنون که اطلاعات مشتریان و وضعیت پرداخت قسط آنها را در جدول داریم، نمودار مربوط به این مشتریان را رسم می‌کنیم. با توجه به اینکه تنها 2 ویژگی در اینجا ذکر شده است، ما یک نمودار 2 بعدی خواهیم داشت. به‌طور دلخواه محور افقی این نمودار را میزان سابقه کاری در نظر گرفته و محور عمودی را برابر میزان حقوق در نظر می‌گیریم. سپس 8 مشتری را در جای مناسب قرار می‌دهیم. مشتریانی که قسط‌های خود را به‌موقع پرداخت کرده‌اند با رنگ سبز و آنهایی که قسط‌های خود را به موقع پرداخت نکرده‌اند با رنگ قرمز مشخص شده‌اند:

تصویر نمودار اطلاعات مشتریان است که مشتریانی که قسط های خود را به موقع پرداخت کرده اند با رنگ سبز و آنهایی که قسط های خود را به موقع پرداخت نکرده اند با رنگ قرمز مشخص شده اند

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

ویژگی دوم: میزان حقوقویژگی اول: سابقه کار
16 میلیون 17 سال

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

در اینجا ما از فاصله منهتن استفاده می‌کنیم. یعنی عدد مربوط به هر ویژگی مشتری جدید را از ویژگی مشتری‌های سابق کم می‌کنیم و مجموع قدر مطلق آن را به‌عنوان خروجی در نظر می‌گیریم. تمامی این مراحل در جدول زیر انجام شده است:

فاصله مشتری جدید به مشتری‌هاپرداخت به موقع قسطویژگی دوم: میزان حقوقویژگی اول: سابقه کارشماره
|17-5|+|16-7|=21 خیر 7 میلیون 5 سال #1
|17-13|+|16-17|=5 بله 17 میلیون 13 سال #2
|17-9|+|16-11|=13 خیر 11 میلیون 9 سال #3
|17-13.5|+|16-6|=13.5 خیر 6 میلیون 13.5 سال #4
|17-16|+|16-12|=5 بله 12 میلیون 16 سال #5
|17-21|+|16-18|=6 بله 18 میلیون 21 سال #6
|17-23.5|+|16-6.5|=16 بله 6.5 میلیون 23.5 سال #7
|17-20|+|16-14|=5 خیر 14 میلیون 20 سال #8

همانطور که مشاهده می‌کنید فاصله مشتری جدید برای تمامی 8 مشتری محاسبه شده است. حال اگر بخواهیم 4 مشتری نزدیک‌تر به مشتری جدید را حساب کنیم، یعنی در واقع K را برابر 4 در نظر بگیریم، مشتری‌های شماره 2، 5، 6 و 8 نزدیک‌ترین مشتری‌ها به مشتری جدید هستند. از این 4 مشتری، 3 تای آنها برچسب بله دارند یعنی قسط‌هایشان را به‌موقع پرداخت کرده‌اند و یکی از آنها (شماره 8) برچسب خیر دارد بنابراین با توجه به اینکه اکثریت (75 درصد) قسط‌های خود را به‌موقع پرداخت کرده‌اند، می‌توانیم برچسب بله را به این مشتری نسبت دهیم. در تصویر زیر این موضوع را به‌صورت دقیق‌تر نمایش داده‌ایم:

تصویر نمودار اطلاعات مشتریان است که 4 مشتری نزدیک و مشتری جدید با درج دایره ای دور آنها در یک دسته قرار گرفته اند

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

کاربردهای الگوریتم KNN

الگوریتم KNN، کاربردهای زیادی در مسائل مربوط به طبقه‌بندی در صنعت دارد. این الگوریتم علاوه بر طبقه‌بندی در مسائل پیش‌بینی رگرسیون نیز مورد استفاده قرار می‌گیرد. در لیست زیر چند نمونه از مهم‌ترین کاربردهای استفاده از الگوریتم K نزدیک ترین همسایه آورده شده است:

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

الگوریتم KNN دارای مزایا و معایب مختلفی می‌باشد که در اینجا به برخی از مهم‌ترین آنها می‌پردازیم.

مزایای الگوریتم KNN

از مزایای الگوریتم KNN می‌توان به موارد زیر اشاره کرد:

معایب الگوریتم KNN

در کنار مزایای زیادی که الگوریتم K نزدیک‌ترین همسایه دارد، این الگوریتم دارای معایبی نیز می‌باشد که در لیست زیر مهم‌ترین آنها عنوان شده است:

جمع‌‌بندی

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

چه زمانی از الگوریتم KNN استفاده می‌شود؟

الگوریتم K نزدیک‌ترین همسایه که در واقع یک نوع الگوریتم یادگیری ماشین است، برای حل مسائل طبقه‌بندی و رگرسیون مورد استفاده قرار می‌گیرد. در این الگوریتم ما فاصله بین ویژگی‌های داده مورد آزمایش را با داده‌های تحت آموزش محاسبه می‌کنیم و سپس طبق آنها یک مقدار پیش‌بینی برای داده مورد آزمایش در نظر می‌گیریم.

مقدار فاصله بین داده‌ها به چه صورت انجام می‌شود؟

برای محاسبه فاصله بین داده‌ها، فرمول‌ها و تکنیک‌های مختلفی وجود دارد. از مهم‌ترین آنها می‌توان به موارد زیر اشاره کرد:
فاصله منهتن (Manhattan Distance)
فاصله اقلیدسی (Euclidean Distance)
فاصله مینوکوفسکی (Minkowski Distance)

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (3 رای)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200