K نزدیک ترین همسایه یا K-Nearest Neighbors که به‌اختصار به آن KNN می‌گویند، جزو ساده‌ترین الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوان
در این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد‌ها در بحث طبقهبندی است. این الگوریتم در واقع یک الگوریتم یادگیری است که در حل مسائل رگرسیون (Regression) و طبقهبندی (Classification) مورد استفاده قرار میگیرد. ابتدا با یک مثال ساده به توضیح کلی در مورد کارکرد این الگوریتم می‌پردازیم و سپس با مثال علمی‌تر به جزئیات این الگوریتم خواهیم پرداخت.
فرض کنید دادههای دانش‌آموزان یک کلاس در دستان شما قرار دارد و شما این دانش‌آموزان را به 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 ابتدا می‌بایست فاصله هر نمونه جدید را با تمامی دادههای پیشین مقایسه کنیم. در روش محاسبه فاصله، تکنیکهای گوناگونی وجود دارد؛ به‌عنوان مثال:
- فاصله منهتن (Manhattan Distance)
- فاصله اقلیدسی (Euclidean Distance)
- فاصله مینوکوفسکی (Minkowski Distance)
در اینجا ما از فاصله منهتن استفاده میکنیم. یعنی عدد مربوط به هر ویژگی مشتری جدید را از ویژگی مشتری‌های سابق کم میکنیم و مجموع قدر مطلق آن را به‌عنوان خروجی در نظر میگیریم. تمامی این مراحل در جدول زیر انجام شده است:
| فاصله مشتری جدید به مشتری‌ها | پرداخت به موقع قسط | ویژگی دوم: میزان حقوق | ویژگی اول: سابقه کار | شماره |
|---|---|---|---|---|
| |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 درصد) قسط‌های خود را به‌موقع پرداخت کرده‌اند، می‌توانیم برچسب بله را به این مشتری نسبت دهیم. در تصویر زیر این موضوع را به‌صورت دقیق‌تر نمایش داده‌ایم:
این مثال در واقع یک مثال بسیار ساده با تنها 2 ویژگی بود. مسائل دنیای واقعی دارای ویژگیهای بسیار بیشتر و در نتیجه شامل ابعاد گسترده‌تری می‌شوند؛ به‌عنوان مثال فرض کنید می‌خواهیم احتمال پیروز شدن یک تیم در بازی فوتبال را پیشبینی کنیم، ویژگیهای متعددی در این پیشبینی دخیل هستند؛ از جمله تعداد دفعات برد و باخت تیم‌ها در بازی‌های گذشته، تعداد بازیکن‌های حذف شده، تعداد بازیکن‌های مسدوم، داور بازی، زمین بازی و عوامل متعدد دیگر.
کاربردهای الگوریتم KNN
الگوریتم KNN، کاربردهای زیادی در مسائل مربوط به طبقهبندی در صنعت دارد. این الگوریتم علاوه بر طبقهبندی در مسائل پیشبینی رگرسیون نیز مورد استفاده قرار میگیرد. در لیست زیر چند نمونه از مهمترین کاربردهای استفاده از الگوریتم K نزدیک ترین همسایه آورده شده است:
- دسته‌بندی مشتریان: یکی از مهمترین کاربرد استفاده از الگوریتم KNN، دسته‌بندی مشتریان است. فروشگاه‌های اینترنتی به‌وسیله این الگوریتم، مشتریان خود را دسته‌بندی می‌کنند و محصولات متناسب با سبد خرید را به آنها پیشنهاد می‌دهند.
- استخراج متون: از الگوریتم KNN در استخراج متن و یافتن الگوهای مشابه متنی استفاده میشود؛ به‌عنوان مثال تشخیص اینکه آیا درون متنی سرقت ادبی وجود دارد یا خیر را به‌وسیله این الگوریتم میتوان تشخیص داد.
- بازارهای سرمایه: یکی از موارد مهم استفاده از الگوریتم KNN استفاده آنها در بازارهای سرمایه و پیشبینی قیمت‌ها است.
- تشخیص چهره: از دیگر موارد استفاده از الگوریتم K نزدیکترین همسایه میتوان به استفاده از آن در سیستم‌های تشخیص چهره اشاره کرد.
مزایا و معایب الگوریتم K نزدیکترین همسایه
الگوریتم KNN دارای مزایا و معایب مختلفی می‌باشد که در اینجا به برخی از مهمترین آنها می‌پردازیم.
مزایای الگوریتم KNN
از مزایای الگوریتم KNN میتوان به موارد زیر اشاره کرد:
- الگوریتم KNN جزو ساده‌ترین الگوریتم‌های طبقهبندی و یادگیری ماشینیادگیری ماشین چیست و چرا مهم است؟ - Machine learning (ML)
تعریف یادگیری ماشین : ماشین لرنینگ (Machine Learning یا به اختصار ML) باعث میشود که خود ماشین‌ها با آنالیز داده ها امکان یادگیری و پیشرفت داشته باشند، این مقاله فوق العاده یادگیری ماشین را بصورت کامل بررسی کرده است است و پیاده‌سازی آن کار آسانی است. - این الگوریتم از دقت نسبتا بالایی برخوردار است بنابراین نتایج حاصل از خروجی الگوریتم KNN قابل اطمینان است.
- از الگوریتم KNN در مسائل مختلفی از جمله حل مسائل رگرسیون و مسائل طبقهبندی میتوان استفاده کرد.
- نتایج حاصل از خروجی این الگوریتم به‌راحتی قابل تفسیر است و نیاز به تحلیل خاصی ندارد.
معایب الگوریتم KNN
در کنار مزایای زیادی که الگوریتم K نزدیکترین همسایه دارد، این الگوریتم دارای معایبی نیز می‌باشد که در لیست زیر مهمترین آنها عنوان شده است:
- زمان محاسبه این الگوریتم بالاست و نیازمند حافظه زیادی نیز می‌باشد. اگر n را تعداد نقاط دادهها و d را تعداد ویژگیهای هر داده در نظر بگیریم، پیچیدگی زمانی و پیچیدگی حافظه این الگوریتم برابر O(n*d) می‌باشد.
- در الگوریتم KNN اگر مقیاس‌بندی به‌درستی انجام نشود، نتایج حاصل از خروجی الگوریتم ممکن است جواب دلخواه ما نباشد، بنابراین این الگوریتم به مقیاس داده حساس است.
- هرچه مقدار K در این الگوریتم بزرگتر باشد، پیشبینی کندتر صورت می‌پذیرد.
جمع‌‌بندی
در این مقاله به‌طور خلاصه الگوریتم K نزدیکترین همسایه (KNN) را با ذکر یک مثال توضیح دادیم. از آن جا که این الگوریتم، الگوریتم زیاد پیچیده‌ای نیست و پیچیدگی زمانی و حافظه‌ای بالایی دارد، بهتر است که برای دادههای نسبتا کوچک که دارای دسته‌بندی مناسب و نویز پایین هستند استفاده شود.
چه زمانی از الگوریتم KNN استفاده میشود؟
الگوریتم K نزدیکترین همسایه که در واقع یک نوع الگوریتم یادگیری ماشین است، برای حل مسائل طبقهبندی و رگرسیون مورد استفاده قرار میگیرد. در این الگوریتم ما فاصله بین ویژگیهای داده مورد آزمایش را با دادههای تحت آموزش محاسبه میکنیم و سپس طبق آنها یک مقدار پیشبینی برای داده مورد آزمایش در نظر میگیریم.
مقدار فاصله بین دادهها به چه صورت انجام میشود؟
برای محاسبه فاصله بین دادهها، فرمولها و تکنیکهای مختلفی وجود دارد. از مهمترین آنها میتوان به موارد زیر اشاره کرد:
فاصله منهتن (Manhattan Distance)
فاصله اقلیدسی (Euclidean Distance)
فاصله مینوکوفسکی (Minkowski Distance)
