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

الگوریتم k-نزدیکترین همسایگان (KNN) یک الگوریتم یادگیری ماشین نظارت شده است که می‌تواند برای حل مسائل طبقه بندی و رگرسیون استفاده شود. در ادامه به تشریح آن می‌پردازیم.

یادگیری نظارت شده در مقابل یادگیری بدون نظارت

الگوریتم یادگیری ماشین نظارت شده (بر خلاف یک الگوریتم یادگیری ماشین بدون نظارت) به داده های ورودی دارای برچسب متکی است تا بتواند به تابع یاد دهد که در هنگام برخورد با داده‌های جدید بدون برچسب ، خروجی مناسبی را تولید کند.

تصور کنید که کامپیوتر یک کودک است و ما سرپرست آن هستیم (به عنوان مثال والدین ، سرپرست یا معلم) و ما می خواهیم کودک (رایانه) یاد بگیرد که خوک چگونه به نظر می رسد. ما چندین تصویر مختلف را به کودک نشان خواهیم داد که برخی از آنها خوک و بقیه می توانند از هر چیزی (گربه ، سگ و غیره) باشند.

وقتی خوک را می بینیم ، فریاد می زنیم: "خوک!" وقتی خوک نیست ، ما فریاد می زنیم "نه، خوک نیست!" بعد از چندین بار انجام این کار به همراه کودک ، ما از کودک یک عکس نشان می دهیم و از او درباره "خوک می پرسیم؟" (بیشتر اوقات) کودک بسته به نوع تصویر به درستی خواهند گفت "خوک!" یا "نه ، خوک نیست!" این یادگیری ماشین نظارت شده است.

برای حل مسائل طبقه بندی یا رگرسیون از الگوریتم های یادگیری ماشین نظارت شده استفاده می شود.

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

این تصویر یک مثال ساده از داده طبقه بندی را نشان می دهد. ما یک پیش بینی کننده (یا مجموعه از پیش بینی کننده ها) و یک برچسب داریم. با توجه به تصویر ما سعی می کنیم پیش بینی کنیم که آیا کسی آناناس را روی پیتزا خود دوست دارد(1) یا نه (0) این کار را بر اساس سن‌شان(پیش‌بینی‌کننده) انجام می دهیم.

نمایش دادن خروجی(برچسب) در یک الگوریتم طبقه‌بندی می‌تواند به صورت یک عدد صحیح مانند 1، 1- و 0 باشد. این یک روش استاندارد جهت نمایش خروجی است.توجه کنید که این اعداد تنها برای نمایش خروجی هستند و نباید عملیات ریاضی بر روی آنها انجام شود زیرا انجام چنین کاری بی‌معنی است.یک لحظه تصور کنید که جمع عبارات "آناناس را دوست دارد" + "آناناس را دوست ندارد" چه معنی می‌دهد؟ دقیقا. ما نمی‌توانیم آنها را با هم جمع کنیم، بنابراین اعدادی که تنها برای نمایش خروجی (برچسب) استفاده می‌شوند.

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

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

همچنین ، معمولا هر سطر با نام‌ یک نمونه، مشاهده یا نقطه داده خوانده می شود ، در حالی که هر ستون اغلب با نام پیش بینی کننده ، بعد ، متغیر مستقل یا ویژگی نامیده می شود.ستون برچسب شامل متغییرهای مستقل نمی‌شود.

در الگوریتم یادگیری ماشین بدون نظارت داده‌های ورودی بدون هیچ برچسبی استفاده می‌شوند ، به عبارت دیگر، هیچ معلمی (برچسب) به کودک (رایانه) درست یا اشتباه را نمی‌گوید تا بتواند خود را اصلاح کند.

برخلاف یادگیری نظارت شده که سعی در یادگیری تابعی دارد که به ما امکان می دهد با توجه به داده های جدید بدون برچسب، پیش بینی هایی را انجام دهیم ، یادگیری بدون نظارت سعی می کند ساختار اولیه داده ها را یاد بگیرد تا بینش بیشتری از داده ها به ما بدهد.

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

الگوریتم KNN فرض می‌کند که موارد مشابه نزدیک به یکدیگر هستند.

"کبوتر با کبوتر، باز با باز"

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

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

روش های دیگری نیز برای محاسبه فاصله وجود دارد و بسته به مسئله‌ایی که ما حل می کنیم ، یک راه ممکن است ارجح باشد. با این حال ، فاصله مستقیم (که به آن فاصله اقلیدسی نیز گفته می شود) یک انتخاب محبوب و آشناست.

الگوریتم KNN

1. بارگذاری داده ها
2. مقداردهی اولیه K برای انتخاب تعداد همسایگان
3. برای هر نمونه از داده ها
4. فاصله بین نمونه پرس‌وجو و نمونه فعلی از داده ها را محاسبه کنید
5. فاصله و اندیس داده نمونه را به مجموعه مرتب شده اضافه كنيد
6. مجموعه فاصله ها و شاخص های مرتب شده را از کوچکترین تا بزرگترین (به ترتیب صعودی) بر اساس فاصله‌ها مرتب کنید
7. اولین ورودی های K را از مجموعه مرتب شده انتخاب کنید
8. برچسب های ورودی K انتخاب شده را دریافت کنید
9. در صورت رگرسیون ، میانگین برچسب های K را برگردانید
10. در صورت طبقه بندی ، حالت برچسب های K را برگردانید

اجرای KNN

انتخاب مقدار مناسب برای K

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

نکاتی که باید به خاطر داشته باشید:

1. هرچه مقدار K را کاهش می‌دهیم و به 1 نزدیک می‌شود ، پیش‌بینی های ما از پایداری کمتری برخوردار می‌شود. برای مثال: مقدار K = 1 را تصور کنید و ما یک نقطه پرس و جو داریم که توسط چندین قرمز و یک رنگ سبز احاطه شده است، منطقی است که ما فکر کنیم که نقطه پرس و جو به احتمال زیاد قرمز است ولی به‌خاطر اینکه نزدیک‌ترین همسایه به نقطه پرس‌وجو رنگ سبز است و همچنین مقدار k=1 است به طور اشتباه نقطه پرس و جو را سبز پیش بینی می کند.
2. برعکس ، با افزایش مقدار K ، پیش بینی های ما به دلیل رای اکثریت / میانگین‌گیری ​​، پایدارتر می‌شوند. بنابراین ، به احتمال زیاد پیش بینی های دقیق تری انجام می دهیم.البته تا یک مقدار خاصی از K و بعد از آن مقدار ما شاهد افزایش فزاینده خطاها هستیم. در این مرحله است که می دانیم مقدار K را خیلی دور کرده ایم.
3. در مواردی که در بین برچسب ها اکثریت آراء را کسب می کنیم (مثلاً انتخاب حالت در یک مسئله طبقه بندی) ، ما معمولاً K را یک عدد فرد اتخاب می‌کنیم رای حداکثری داشته باشیم.

مزایا

1. یکی از ساده‌ترین و آسان‌ترین الگوریتم جهت پیاده‌سازی است.
2. نیازی به ساختن مدل ، تنظیم چندین پارامتر یا پیش فرض های اضافی نیست.
3. الگوریتم همه کاره است. این می تواند برای طبقه بندی ، رگرسیون و جستجو استفاده شود (همانطور که در بخش بعدی خواهیم دید).

معایب

1. با افزایش تعداد نمونه ها و یا متغیرهای پیش بینی کننده / مستقل ، الگوریتم بطور قابل توجهی کندتر می‌شود.

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

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

با این حال، به شرط آنكه از منابع محاسباتی كافی برخوردار باشید، KNN می تواند در حل مسائلی كه با استفاده از معیار مشابهت اشیاء انجام می‌شود، مفید باشد. نمونه‌ای از استفاده از الگوریتم KNN در سیستم های توصیه‌کننده ( KNN-search) است.

خلاصه

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

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

در مورد طبقه بندی و رگرسیون ، دیدیم که انتخاب درست K برای داده های ما با امتحان کردن چندین K و انتخاب یکی از مواردی که بهترین عملکرد را دارد ، انجام می شود.

برداشتی آزاد از مقاله :

https://towardsdatascience.com/machine-learning-basics-with-the-k-nearest-neighbors-algorithm-6a6e71d01761