موضوع مقاله: الگوریتم کی-نزدیک‌ترین همسایه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم کی-نزدیک‌ترین همسایه | مقدمه: این روش را در ابتدا اولین فیکس و جوزف هاجز، در سال ۱۹۵۱ توسعه دادند و بعدتر توماس کاور آن را توسعه داد. | ## بخش 1: الگوریتم کی-نزدیک‌ترین همسایه | در هر دو موضوع طبقه‌بندی آماری و رگرسیون کی شامل نزدیک‌ترین نمونه آموزشی در فضای داده‌ای می‌باشد و خروجی آن بسته به نوع مورد استفاده در طبقه‌بندی و رگرسیون متغیر است. در حالت طبقه‌بندی با توجه به مقدار مشخص شده برای کی، به محاسبه فاصله نقطه ای که می‌خواهیم برچسب آن را مشخص کنیم با نزدیک‌ترین نقاط می‌پردازد و با توجه به تعداد رای حداکثری این نقاط همسایه، در رابطه با برچسب نقطه مورد نظر تصمیم‌گیری می‌کنیم. برای محاسبه این فاصله می‌توان از روش‌های مختلفی استفاده کرد که یکی از مطرح‌ترین این روش‌ها، فاصله اقلیدسی است. از آنجا که محاسبات این الگوریتم بر اساس فاصله است نرمال‌سازی داده‌ها می‌تواند به بهبود عملکرد آن کمک کند. اگر = ۳ (دایره سیاه)، نمونه به دسته دوم اختصاص دارد؛ زیرا درون دایره سیاه درونی، ۲ کره قرمز و ۱ کره آبی وجود دارد. هم چنین اگر = ۵ (دایره نارنجی) به دسته اول اختصاص داده می‌شود؛ زیرا در حلقه بیرونی ۳ کره آبی و ۲ کره قرمز است. داده‌های اولیه، بردارهایی در یک فضای چند بعدی هستند که هر کدام شامل برچسبی به نام دسته می‌باشند. در فاز طبقه‌بندی، k یک ثابت توسط کاربر تعریف می‌شود و بردار بدون برچسب (نقطه تست) از دسته ای است که بیشترین تعداد را در k نزدیک‌ترین همسایه آن نقطه داشته باشد. برای متغیرهای گسسته، مانند دسته‌بندی متون، می‌توان از یک معیار دیگر مانند فاصله همینگ استفاده کرد. به این معنی که تعداد زیادی از نمونه‌های یک دسته در میان نزدیک‌ترین همسایه عضو جدید بوده‌است.D. Massart: نزدیکترین همسایه با استفاده از قوانین رای‌گیری جایگزین یکی از راه‌های غلبه بر این مشکل، وزن دادن به طبقه‌بندی بر مبنای فاصله هر یک از نمونه‌های اولیه، از عضو جدید است. دسته (یا مقدار در مسائل رگرسیون) هرکدام از k نزدیک‌ترین نقاط در وزن خود که متناسب با معکوس فاصله آن‌ها از نقطه تست است، ضرب می‌شود. برای مثال، در یک نقشه‌های خودسازمان‌دهنده (SOM)، هر گره، صرف نظر از تراکم آن‌ها در داده‌های اولیه اصلی، یک نماینده (مرکز) از نقاط مشابه است. | ## بخش 2: الگوریتم کی-نزدیک‌ترین همسایه | برای هر یک از داده‌های اولیه: فاصله بین داده مورد سؤال و هر یک داده‌های اولیه را محاسبه کنید. مورد خاص زمانی است که دسته پیش‌بینی شده برای عضو جدید، همان دسته نزدیکترین نمونه باشد. دقت الگوریتم NN- می‌تواند در نتیجه وجود خطا، یا ویژگی‌های غیر مرتبط یا اگر مقیاس داده‌ها با اهمیت آن‌ها تطابق نداشته باشد، به شدت تضعیف می‌شود. برای بهبود طبقه‌بندی، تلاش‌های زیادی در زمینه انتخاب یا مقیاس بندی داده‌ها شده‌است. یک رویکرد بسیار مشهور، استفاده از الگوریتم‌های تکاملی برای بهینه‌سازی مقیاس بندی داده‌ها است. در دسته‌بندی‌های دو کلاس، بهتر است که k یک عدد فرد انتخاب شود؛ زیرا این امر از گره خوردن آرا جلوگیری می‌کند. نزدیکترین همسایه شهودی‌ترین نوع نزدیکترین همسایه در حالت طبقه‌بندی، تنها نزدیکترین همسایه است که یک نقطه را به کلاس نزدیکترین همسایه خود اختصاص می‌دهد؛ به این معنی که (1)Clnnn(x) = Y. هر چه تعداد داده‌های اولیه به بی‌نهایت نزدیک می‌شود، نزدیکترین همسایه در حالت طبقه‌بندی تضمین می‌کند که میزان خطا بیشتر از دو برابر خطای بایاس (حداقل خطا قابل دستیابی با توجه به توزیع داده‌ها) نخواهد بود. با استفاده از الگوریتم تقریبی جستجوی نزدیکترین همسایه، می‌توان از شدت این محاسبات، حتی برای مجموعه اولیه‌های بزرگ، کاست. در طول سال‌ها، بسیاری از الگوریتم‌های جستجوی نزدیکترین همسایه پیشنهاد شده‌اند که به دنبال کاهش تعداد محاسبه‌های انجام شده بوده‌اند. برای M = ۲ خطای بیزین *R به صفر میل می‌کند؛ این حد، حداکثر به میزان دو برابر خطای بیزین کاهش می‌یابد. یادگیری متریک عملکرد نزدیکترین همسایه، اغلب می‌تواند به‌طور قابل توجهی، از طریق یادگیری متریک بهبود یابد. الگوریتم‌های یادگیری متریک، از اطلاعات نمونه، برای یادگیری متریک جدید یا شبه متریک استفاده می‌کنند. | ## بخش 3: الگوریتم کی-نزدیک‌ترین همسایه | استخراج ویژگی هنگامی که داده‌های ورودی یک الگوریتم برای پردازش بیش از حد بزرگ باشد و داده‌ها مشکوک به بی‌استفاده یا تکراری بودن باشند (به عنوان مثال اندازه‌گیری یکسان یک ویژگی با دو واحد متفاوت) آنگاه داده‌های ورودی به یک مجموعه با ابعاد کاهش یافته از ویژگی‌ها تبدیل می‌شوند (همچنین بردار ویژگی‌ها نامیده می‌شود). اگر ویژگی‌های استخراج‌شده با دقت انتخاب شوند، انتظار می‌رود که مجموعه ویژگی‌ها اطلاعات مربوط را از داده‌های ورودی استخراج کند تا با استفاده از این نمایش کاهش‌یافته به جای ورودی با اندازه بزرگ الگوریتم را اجرا کرد و به نتیجه رسید. استخراج ویژگی بر روی داده‌های خام قبل از اعمال الگوریتم k-NN انجام می‌شود تا الگوریتم بر روی داده‌های تبدیل شده در فضای ویژگی جدید اجرا شود. مرز تصمیم‌گیری قواعد مربوط به نزدیکترین همسایه در عمل به‌طور ضمنی مرز تصمیم را محاسبه می‌کنند. همچنین می‌توان مرز تصمیم را به‌طور صریح محاسبه کرد و این کار را به‌طور کارآمد انجام داد، به طوری که پیچیدگی محاسباتی در مجموع تابعی از پیچیدگی مرزی خواهد بود. کاهش ابعاد برای داده‌های با ابعاد بالا (به عنوان مثال، با تعداد ابعاد بیش از ۱۰)، کاهش ابعاد معمولاً قبل از اعمال الگوریتم k-NN انجام می‌شود تا از اثرات مشقت بعدچندی جلوگیری شود. مشقت بعدچندی در زمینه k-NN اساساً به این معنی است که فاصله اقلیدسی در ابعاد بالا مفید نیست، زیرا همه بردارها تقریباً با بردار پرس‌وجو(query) فاصله دارند (تصور کنید چندین نقطه تقریباً بر روی یک دایره به مرکز نقطه پرس‌وجو قرار دارند. استخراج ویژگی و کاهش ابعاد را می‌توان در یک مرحله با استفاده از تحلیل مؤلفه اصلی (PCA)، تجزیه و تحلیل متمایز خطی (LDA)، یا تجزیه و تحلیل همبستگی متعارف (CCA) به عنوان یک مرحله پیش پردازش، و پس از خوشه بندی توسط k-NN بر روی بردارهای ویژگی‌ها در فضا با بعد کاهش یافته انجام داد. کاهش داده‌ها کاهش داده‌ها یکی از مهم‌ترین مسائل در کار با مجموعه داده‌های عظیم است. این داده‌ها نمونه‌های اولیه نامیده می‌شوند و می‌توان آنها را با استفاده از سه مرحله زیر یافت: پیدا کردن داده‌های پرت: پیدا کردن داده‌هایی که در زمان آموزش به اشتباه توسط k-NN طبقه‌بندی شده‌اند. یک دسته نمونه‌های اولیه که برای تصمیم‌گیری‌های طبقه‌بندی استفاده می‌شوند و دسته دیگر نقاط جذب (نقاطی که می‌توانند به درستی توسط k-NN با استفاده از نمونه‌های اولیه طبقه‌بندی شوند) در انتها نقاط جذب شده را می‌توان از مجموعه داده‌های آموزش حذف کرد. نزدیکترین همسایه در حالت رگرسیون در رگرسیون، الگوریتم NN- برای تخمین زدن متغیرهای پیوسته استفاده می‌شود. یکی از این الگوریتم‌ها از میانگین وزنی k نزدیکترین همسایه به‌دست می‌آید (میانگین وزنی از معکوس فاصله آنها محاسبه می‌شود). | ## جمع‌بندی | اعتبارسنجی نتایج یک ماتریس درهم‌ریختگی یا «ماتریس تطبیق» اغلب به عنوان ابزاری برای تأیید صحت طبقه‌بندی k-NN استفاده می‌شود.