الگوریتم کی-نزدیک‌ترین همسایه
در بازشناخت الگو کی-نزدیکترین همسایه (انگلیسی: k-nearest neighbors algorithm) یک متد آمار ناپارامتری است که برای طبقه‌بندی آماری و رگرسیون استفاده می شود. در هر دو حالت کی شامل نزدیک ترین مثال آموزشی در فضای داده ای می باشد و خروجی آن بسته به نوع مورد استفاده در طبقه بندی و رگرسیون متغیر است. در حالت طبقه بندی با توجه به مقدار مشخص شده برای کی، به محاسبه فاصله نقطه ای که میخواهیم برچسب آن را مشخص کنیم با نزدیک ترین نقاط میپردازد و با توجه به تعداد رای حداکثری این نقاط همسایه، در رابطه با برچسب نقطه مورد نظر تصمیم گیری می‌کنیم. برای محاسبه این فاصله میتوان از روش های مختلفی استفاده کرد که یکی از مطرح ترین این روش ها، فاصله اقلیدسی است. در حالت رگرسیون نیز میانگین مقادیر بدست آمده از کی خروجی آن می باشد. از آنجا که محاسبات این الگوریتم بر اساس فاصله است نرمال‌سازی داده‌ها می‌تواند به بهبود عملکرد آن کمک کند.
فرض کنید زوج مرتب‌های (X,Y)... ,(X,Y),(X,Y) از {۱٬۲} × R مقدار می‌گیرد. (Y نشان دهنده کلاس X است). در نتیجه خواهیم داشت: X|Y = r ~ P برای r = ۱٬۲ که P توزیع احتمال است.
با داشتن تعدادی اندازه (norm) ‖. ‖ در R و نقطه x، زوج مرتب‌های (X,Y) ... , (X,Y),(X,Y) را که ترتیب دیگری از داده‌های اولیه هستند با شرط ǁX ≤ xǁ ... , ǁX ≤ xǁ تعریف می‌کنیم.
داده‌های اولیه، بردارهایی در یک فضای چند بعدی هستند که هر کدام شامل برچسبی به نام دسته می‌باشند.
فاز یادگیری (training phase) الگوریتم، شامل ذخیره‌سازی بردارهای ویژگی و برچسب دسته نمونه‌های اولیه است.
در فاز طبقه‌بندی، k یک ثابت توسط کاربر تعریف می‌شود و بردار بدون برچسب (نقطه تست) از دسته ای است که بیشترین تعداد را در k نزدیک‌ترین همسایه آن نقطه داشته باشد. به این ترتیب برچسب نقطه تست نیز مشخص می‌شود.
معیار فاصله برای متغیرهای پیوسته معمولاً فاصله اقلیدسی است.
برای متغیرهای گسسته، مانند دسته‌بندی متون، می‌توان از یک معیار دیگر مانند فاصله همینگ استفاده کرد.
اگر NN-formula_1 را با استفاده از الگوریتم‌های تخصصی مانند تجزیه و تحلیل اجزای همسایه (Neighbourhood components analysis) یا حاشیه بزرگ نزدیک‌ترین همسایه (Large Margin Nearest Neighbor) پیاده‌سازی کرد، می‌توان دقت اندازه‌گیری را به شدت بهبود داد.
یک اشکال طبقه‌بندی پایه «رای اکثریت» (majority voting) زمانی اتفاق می‌افتد که توزیع دسته درهم شکسته شود. به این معنی که تعداد زیادی از نمونه‌های یک دسته در میان نزدیک‌ترین همسایه عضو جدید بوده‌است. یکی از راه‌های غلبه بر این مشکل، وزن دادن به طبقه‌بندی بر مبنای فاصله هر یک از نمونه‌های اولیه، از عضو جدید است. دسته (یا مقدار در مسائل رگرسیون) هرکدام از k نزدیک‌ترین نقاط در وزن خود که متناسب با معکوس فاصله آن‌ها از نقطه تست است، ضرب می‌شود.
یکی دیگر از راه‌های غلبه بر این مشکل، انتزاع در نمایش داده‌ها است. برای مثال، در یک نقشه‌های خودسازمان‌دهنده (SOM)، هر گره، صرف نظر از تراکم آن‌ها در داده‌های اولیه اصلی، یک نماینده (مرکز) از نقاط مشابه است. سپس NN-formula_1 به SOM اعمال می‌شود.
مراحل الگوریتم knn شامل موارد زیر خواهد بود: به این ترتیب، کد پایتون محاسبه فاصله اقلیدسی و NN-formula_1 را در ادامه می‌بینید:
کد زیر مربوط به الگوریتم knn گفته شده در حالت دسته‌بندی است. داده‌های اولیه، trainingSet و داده مورد سؤال testInstance نامیده شده‌است.
بهترین انتخاب formula_1 بستگی به داده‌ها دارد؛ به‌طور کلی، مقادیر بزرگ formula_1 باعث کاهش خطا در طبقه‌بندی می‌شود، اما وضوح مرز بین کلاس‌ها را کمتر می‌کند. formula_1 مناسب را می‌توان با استفاده از تکنیک‌های مختلف انتخاب کرد. مورد خاص زمانی است که دسته پیش‌بینی شده برای عضو جدید، همان دسته نزدیکترین نمونه باشد. (به ازای k = ۱). در این صورت، الگوریتم نزدیکترین همسایه نامیده می‌شود.
دقت الگوریتم NN-formula_1 می‌تواند در نتیجه وجود خطا، یا ویژگی‌های غیر مرتبط یا اگر مقیاس داده‌ها با اهمیت آن‌ها تطابق نداشته باشد، به شدت تضعیف می‌شود. برای بهبود طبقه‌بندی، تلاش‌های زیادی در زمینه انتخاب یا مقیاس بندی داده‌ها شده‌است. یک رویکرد بسیار مشهور، استفاده از الگوریتم‌های تکاملی برای بهینه‌سازی مقیاس بندی داده‌ها است.
در دسته‌بندی‌های دو کلاس، بهتر است که k یک عدد فرد انتخاب شود؛ زیرا این امر از گره خوردن آرا جلوگیری می‌کند.
شهودی‌ترین نوع نزدیکترین همسایه در حالت طبقه‌بندی، تنها نزدیکترین همسایه است که یک نقطه را به کلاس نزدیکترین همسایه خوداختصاص می‌دهد؛ به این معنی که C(x) = Y.
هر چه تعداد داده‌های اولیه به بی‌نهایت نزدیک می‌شود، نزدیکترین همسایه در حالت طبقه‌بندی تضمین می‌کند که میزان خطا بیشتر از دو برابر خطای بایاس (حداقل خطا قابل دستیابی با توجه به توزیع داده‌ها) نخواهد بود.
kNN یک مورد خاص از پهنای باند متغیر است.
نسخهٔ ساده این الگوریتم از محاسبه فاصلهٔ نمونه مورد سؤال با تمامی نمونه‌های اولیه، بدست می‌آید؛ اما برای مجموعه اولیه‌های بزرگ، این محاسبات بسیار سنگین خواهد بود. با استفاده از الگوریتم تقریبی جستجوی نزدیکترین همسایه، می‌توان از شدت این محاسبات، حتی برای مجموعه اولیه‌های بزرگ، کاست. در طول سال‌ها، بسیاری از الگوریتم‌های جستجوی نزدیکترین همسایه پیشنهاد شده‌اند که به دنبال کاهش تعداد محاسبه‌های انجام شده بوده‌اند.
NN-formula_1 نتایجی با سازگاری(consistency) قوی دارد. هر چه تعدا داده‌ها به بی‌نهایت نزدیک می‌شود، الگوریتم NN-formula_1 با دو دسته، تضمین می‌کند که نرخ خطا بیشتر از دو برابر نرخ خطای Bayes(حداقل خطا قابل دستیابی با توجه به توزیع داده‌ها) نباشد. هم چنین می‌توان با استفاده از گرافهای مجاورت، سرعت kNN را بهبود بخشید.
برای طبقه‌بندی NN-formula_1 چند کلاس، کاور و هارت (۱۹۶۷) ثابت می‌کنند که حد بالای نرخ خطا برابر است با:
R R R (2 -
R نرخ خطای Bayes (حداقل نرخ خطا ممکن)، R نرخ خطای NN-formula_1 و M تعداد دسته‌ها در مسئله است. برای M = ۲ خطای بیزین R به صفر میل می‌کند؛ این حد، حداکثر به میزان دو برابر خطای بیزین کاهش می‌یابد.
عملکرد formula_1 نزدیکترین همسایه، اغلب می‌تواند به‌طور قابل توجهی، از طریق یادگیری متریک بهبود یابد. الگوریتم‌های مشهور، تجزیه و تحلیل اجزای همسایه (Neighbourhood components analysis) یا حاشیه بزرگ نزدیک‌ترین همسایه (Large Margin Nearest Neighbor) هستند. الگوریتم‌های یادگیری متریک، از اطلاعات نمونه، برای یادگیری متریک جدید یا شبه متریک استفاده می‌کنند.
در رگرسیون، الگوریتم NN-formula_1 برای تخمین زدن متغیرهای پیوسته استفاده می‌شود. یکی از این الگوریتم‌ها از میانگین وزنی k نزدیکترین همسایه بدست می‌آید (میانگین وزنی از معکوس فاصله آنها محاسبه می‌شود). این الگوریتم به شرح زیر عمل می‌کند:
مزایا:
مضرات: