تعریف K-نزدیکترین همسایه

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

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

kNN یک الگوریتم یادگیری نظارت شده است که در آن 'k' تعداد نزدیکترین همسایگان در نظر گرفته شده در مسئله دسته‌بندی یا رگرسیون را نشان می‌دهد، و 'NN' مخفف نزدیکترین همسایگان به عدد انتخاب شده برای k است.

تاریخچه مختصری از الگوریتم kNN

kNN اولین بار توسط Evelyn Fix و Joseph Hodges در سال 1951 در زمینه تحقیقات انجام شده برای ارتش ایالات متحده توسعه یافت. آنها مقاله‌ای را منتشر کردند که در آن تجزیه و تحلیل تفکیک کننده، که یک روش دسته‌بندی ناپارامتریک است، توضیح می‌داد. در سال 1967، توماس کاور و پیتر هارت روش دسته‌بندی ناپارامتریک را گسترش دادند و مقاله «دسته‌بندی الگوی نزدیکترین همسایه» را منتشر کردند. تقریباً 20 سال بعد، این الگوریتم توسط جیمز کلر، که یک "KNN فازی" ایجاد کرد که نرخ خطای کمتری تولید می‌کند، اصلاح شد.

امروزه الگوریتم kNN به دلیل سازگاری با بیشتر زمینه‌ها - از ژنتیک گرفته تا امور مالی و خدمات مشتری - پرکاربردترین الگوریتم است.

kNN چگونه کار می‌کند؟

الگوریتم kNN به عنوان یک الگوریتم یادگیری نظارت شده کار می‌کند، به این معنی که مجموعه داده‌های آموزشی را که به خاطر می‌سپارد تغذیه می‌کند. برای یادگیری تابعی که با داده‌های بدون برچسب جدید، خروجی مناسبی تولید می‌کند، به این داده‌های ورودی برچسب‌گذاری شده متکی است.

این الگوریتم را قادر می‌سازد تا مسائل طبقه بندی یا رگرسیون را حل کند. در حالی که محاسبات kNN در طول یک پرس و جو و نه در مرحله آموزش رخ می‌دهد، نیازهای ذخیره‌سازی داده مهمی دارد و بنابراین به شدت به حافظه وابسته است.

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

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

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

چهار نوع محاسبه فاصله kNN

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

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

فاصله منهتن نیز یک اندازه‌گیری فاصله محبوب است که قدر مطلق بین دو نقطه را اندازه‌گیری می‌کند. در یک شبکه بازنمایی داده می‌شود و اغلب به عنوان هندسه تاکسی شناخته می‌شود - چگونه از نقطه A (نقطه درخواست شما) به نقطه B (نقطه در حال اندازه‌گیری) سفر می‌کنید؟

فاصله مینکوفسکی تعمیم معیارهای فاصله اقلیدسی و منهتن است که امکان ایجاد سایر معیارهای فاصله را فراهم می‌کند. در یک فضای برداری هنجاری محاسبه می‌شود. در فاصله Minkowski، p پارامتری است که نوع فاصله مورد استفاده در محاسبه را مشخص می‌کند. اگر p=1 باشد، از فاصله منهتن استفاده می‌شود. اگر p=2 باشد، از فاصله اقلیدسی استفاده می‌شود.

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

نحوه انتخاب بهترین مقدار k

برای انتخاب بهترین مقدار k - تعداد نزدیک‌ترین همسایگان در نظر گرفته شده - باید با چند مقدار آزمایش کنید تا مقدار k را پیدا کنید که دقیق‌ترین پیش‌بینی‌ها را با کمترین تعداد خطا ایجاد می‌کند. تعیین بهترین ارزش یک عمل متعادل کننده است:

مقادیر k پایین، پیش‌بینی‌ها را ناپایدار می‌کند.

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

مقادیر بالای k نویز دارند.

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

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

مقدار k مناسب نیز نسبت به مجموعه داده‌های شما است. برای انتخاب آن مقدار، ممکن است سعی کنید ریشه دوم N را پیدا کنید، جایی که N تعداد نقاط داده در مجموعه داده آموزشی است. تاکتیک‌های اعتبارسنجی متقاطع نیز می‌توانند به شما کمک کنند تا مقدار k را که به بهترین وجه برای مجموعه داده شما مناسب است انتخاب کنید.

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

الگوریتم kNN اغلب به عنوان "ساده‌ترین" الگوریتم یادگیری تحت نظارت توصیف می‌شود که به چندین مزیت آن منجر می‌شود:

ساده: پیاده‌سازی kNN به دلیل ساده و دقیق بودن آن آسان است. به این ترتیب، اغلب یکی از اولین طبقه‌بندی‌کننده‌هایی است که یک دانشمند داده می‌آموزد.

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

به راحتی قابل برنامه‌ریزی: kNN تنها به چند فراپارامتر نیاز دارد - یک مقدار k و یک متریک فاصله. این آن را به یک الگوریتم نسبتاً بدون پیچیدگی تبدیل می‌کند.

علاوه بر این، الگوریتم kNN به هیچ زمان آموزشی نیاز ندارد زیرا داده‌های آموزشی را ذخیره می‌کند و قدرت محاسباتی آن تنها در هنگام پیش‌بینی استفاده می‌شود.

چالش‌ها و محدودیت‌های kNN

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

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

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

برازش بیش از حد: مقدار k، همانطور که قبلا نشان داده شد، بر رفتار الگوریتم تأثیر می‌گذارد. این می‌تواند به خصوص زمانی اتفاق بیفتد که مقدار k خیلی کم باشد. مقادیر پایین‌تر k می‌توانند بیش از حد بر داده‌ها برازش داشته باشند، در حالی که مقادیر بالاتر k، مقادیر پیش‌بینی را «هموار» می‌کنند، زیرا الگوریتم مقادیر را در یک منطقه بزرگ‌تر میانگین می‌دهد.

موارد استفاده برتر kNN

الگوریتم kNN که به دلیل سادگی و دقت محبوبیت دارد، کاربردهای متنوعی دارد، به ویژه هنگامی که برای تجزیه و تحلیل دسته‌بندی استفاده می‌شود.

رتبه‌بندی ارتباط: kNN از الگوریتم‌های پردازش زبان طبیعی (NLP) برای تعیین اینکه کدام نتایج مرتبط‌تر با یک پرس و جو هستند، استفاده می‌کند.

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

تشخیص الگو[1]: از kNN می‌توان برای شناسایی الگوها در متن یا دسته‌بندی رقم استفاده کرد.

امور مالی[2]: در بخش مالی، kNN می‌تواند برای پیش‌بینی بازار سهام، نرخ ارز و غیره استفاده شود.

توصیه‌های محصول و موتورهای توصیه[3]: به نتفلیکس فکر کنید! "اگر شما این را دوست داشتید، فکر می کنیم شما نیز دوست خواهید داشت..." هر سایتی که از نسخه‌ای از آن جمله استفاده می‌کند، آشکار یا نه، احتمالاً از یک الگوریتم kNN برای روشن کردن موتور توصیه خود استفاده می‌کند.

مراقبت‌های بهداشتی[4]: در زمینه پزشکی و تحقیقات پزشکی، از الگوریتم kNN می‌توان در ژنتیک برای محاسبه احتمال بیان ژن‌های خاص استفاده کرد. این به پزشکان اجازه می‌دهد تا احتمال سرطان، حملات قلبی یا هر بیماری ارثی دیگری را پیش‌بینی کنند.

پیش‌پردازش داده‌ها[5]: الگوریتم kNN می‌تواند برای تخمین مقادیر از دست رفته در مجموعه داده‌ها استفاده شود.

جستجوی kNN با الاستیک

Elasticsearch شما را قادر می‌سازد تا جستجوی kNN را پیاده‌سازی کنید. دو روش پشتیبانی می‌شود: kNN تقریبی و kNN دقیق، brute-force. می‌توانید از جستجوی kNN در زمینه جستجوی شباهت، رتبه‌بندی ارتباط بر اساس الگوریتم‌های NLP و توصیه‌های محصول و موتورهای توصیه استفاده کنید.

---

[1] Pattern Recognition

[2] Finance

[3] Product Recommendations and Recommendation Engines

[4] Healthcare

[5] Data Preprocessing