الگوریتم K نزدیک ترین همسایگی یا KNN – الگوریتمی قدرتمند برای یادگیری ماشین

از الگوریتم های یادگیری ماشین نظارت شده (Supervised machine learning) برای حل مسائل طبقه بندی یا رگرسیون استفاده می شود. در این مقاله ، ما در مورد یکی دیگر از تکنیک های طبقه بندی یادگیری ماشین به نام K نزدیک ترین همسایگی (KNN) که بسیار مورد استفاده قرار می‌گیرد، صحبت خواهیم کرد. تمرکز ما در درجه اول بر روی نحوه کار الگوریتم Knn و تأثیر پارامتر ورودی بر خروجی / پیش بینی خواهد بود.

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

از الگوریتم KNN می توان برای مسائل پیش بینی طبقه بندی و رگرسیون استفاده کرد. با این حال ، بیشتر در مسائل طبقه بندی(Classification) مورد استفاده قرار می‌گیرد. ما هر الگوریتم را از سه جنبه مورد بررسی قرار می‌دهیم:

1. سهولت در تفسیر خروجی
2. زمان محاسبه
3. قدرت پیش بینی

در زیر چند الگوریتم را براساس معیارهایی که در بالا بیان شد بررسی کرده ایم . الگوریتم Knn در بین این الگوریتم‌ها بهترین عملکرد را ارائه می‌دهد:

الگوریتم KNN چگونه کار می کند؟

با یک مثال ساده روش کار این الگوریتم  را به شما آموزش خواهیم داد. در زیر محدوده ی دایره های قرمز (RC) و مربع های سبز (GS) مشخص است:

ستاره ی آبی به داده‌های ما اضافه شده است.  ما می‌خواهیم از کلاس مربوط به ستاره آبی(BS) مطلع شویم. ستاره‌ی آبی می‌تواند به دو کلاس دایره های قرمز و یا مربع های سبز تعلق داشته باشد. ستاره آبی براساس الگوریتم KNN به نزدیکترین کلاس تعلق خواهد داشت. اگر k=3 باشد.ما دایره‌‌ای به دور ستاره آبی می‌کشیم که سه نقطه را پوشش دهد. دایره ی رسم شده را در شکل زیر مشاهده می‌کنید:

همه ی سه نقطه ی نزدیک به ستاره‌ی آبی ،نقطه های قرمز رنگ می‌باشند. از این رو ، با سطح اطمینان خوب ، می توان گفت که BS(ستاره آبی) باید به کلاس RC(دایره قرمز) تعلق داشته باشد. در اینجا ، انتخاب بسیار ساده است. زیرا هر سه نقطه‌‍ی نزدیکترین همسایه به RC تعلق دارد. انتخاب پارامتر K در این الگوریتم بسیار مهم است. در مرحله بعدی ، خواهیم فهمید که چه عواملی بر انتخاب بهترین K موثر خواهند بود.

چگونه K را انتخاب کنیم؟

ابتدا باید درک کنیم که K دقیقاً در الگوریتم چه تاثیری دارد. اگر به آخرین مثال نگاهی بیندازیم ، با توجه به اینکه هر ۶ داده‌ی آموزشی ثابت می‌باشد ، با یک مقدار K مشخص می توانیم مرزهای هر کلاس را مشخص کنیم. این مرزها RC(دایره‌های قرمز) را از GS(مربع‌های سبز) تفکیک می کنند.به همین ترتیب ، تنها عامل تأثیرگذار مقدار “K” می‌باشد. در زیر مشاهده خواهید کرد که با تغییر K مرز کلاس ها تغییر می کند.

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

همانطور که مشاهده می کنید ، میزان خطا در K = 1 برای نمونه آموزش همیشه صفر است. این به این دلیل است که نزدیکترین نقطه به هر نقطه ی داده آموزش ، خود آن است. از این رو پیش بینی همیشه با K = 1 دقیق است. اگر K برابر با ۱باشد ،منحنی خطای اعتبارسنجی روند مشابهی خواهد داشت. در زیر منحنی خطای اعتبار سنجی با مقدار متغیر K وجود دارد:

این موضوع ماجرا را بیشتر روشن می کند. در K = 1 ، ما بیش از حد از مرزها استفاده کرده ایم و به همین خاطر خطای اعتبارسنجی بسیار زیاد است.از این رو ، میزان خطا در ابتدا کاهش می یابد و به حداقل می رسد. بعد از نقطه حداقل ، سپس با افزایش K، خطای اعتبارسنجی افزایش می یابد. برای به دست آوردن مقدار بهینه K ، می توانید آموزش و اعتبارسنجی را از مجموعه داده های اولیه جدا کنید. حالا منحنی خطای اعتبارسنجی را رسم کنید تا مقدار بهینه‌ی K را بدست آورید. این مقدار K باید برای همه پیش بینی ها استفاده شود.

سخن پایانی

الگوریتم k-نزدیک‌ترین همسایگی یکی از ساده‌ترین الگوریتم‌های طبقه‌بندی است. اما با وجود سادگی، نتایج آن به وضوح قابل رقابت با دیگر الگوریتم‌ها است. این الگوریتم برای حل مسائل رگرسیون نیز قابل استفاده است. در این راستا، تنها تفاوت آن با روشی که در این نوشتار ارائه شده، استفاده از میانگین نزدیک‌ترین همسایه‌ها به جای رأی‌گیری از نزدیک‌ترین همسایه‌ها است.

منبع : analyticsvidhya