در بازشناخت الگو کی - نزدیکترین همسایه ( انگلیسی: k - nearest neighbors algorithm ) یک متد آمار ناپارامتری است که برای طبقه بندی آماری و رگرسیون استفاده می شود. در هر دو حالت کی شامل نزدیک ترین مثال آموزشی در فضای داده ای می باشد و خروجی آن بسته به نوع مورد استفاده در طبقه بندی و رگرسیون متغیر است. در حالت طبقه بندی با توجه به مقدار مشخص شده برای کی، به محاسبه فاصله نقطه ای که می خواهیم برچسب آن را مشخص کنیم با نزدیک ترین نقاط می پردازد و با توجه به تعداد رای حداکثری این نقاط همسایه، در رابطه با برچسب نقطه مورد نظر تصمیم گیری می کنیم. برای محاسبه این فاصله می توان از روش های مختلفی استفاده کرد که یکی از مطرح ترین این روش ها، فاصله اقلیدسی است. در حالت رگرسیون نیز میانگین مقادیر به دست آمده از کی خروجی آن می باشد. از آنجا که محاسبات این الگوریتم بر اساس فاصله است نرمال سازی داده ها می تواند به بهبود عملکرد آن کمک کند. [ ۱] [ ۲]
فرض کنید زوج مرتب های ( Xn, Yn ) , . . . , ( X2, Y2 ) , ( X1, Y1 ) از {۱٬۲} × Rd مقدار می گیرد. ( Y نشان دهنده کلاس X است ) . در نتیجه خواهیم داشت: X|Y = r ~ Pr برای r = ۱٬۲ که Pr توزیع احتمال است.
با داشتن تعدادی اندازه ( norm ) ‖. ‖ در Rd و نقطه x، زوج مرتب های ( X ( n ) , Y ( n ) ) , . . . , ( X ( 2 ) , Y ( 2 ) ) , ( X ( 1 ) , Y ( 1 ) را که ترتیب دیگری از داده های اولیه هستند با شرط ǁX ( n ) ≤ xǁ , . . . , ǁX ( 1 ) ≤ xǁ تعریف می کنیم.
داده های اولیه، بردارهایی در یک فضای چند بعدی هستند که هر کدام شامل برچسبی به نام دسته می باشند.
فاز یادگیری ( training phase ) الگوریتم، شامل ذخیره سازی بردارهای ویژگی و برچسب دسته نمونه های اولیه است.
در فاز طبقه بندی، k یک ثابت توسط کاربر تعریف می شود و بردار بدون برچسب ( نقطه تست ) از دسته ای است که بیشترین تعداد را در k نزدیک ترین همسایه آن نقطه داشته باشد. به این ترتیب برچسب نقطه تست نیز مشخص می شود.
معیار فاصله برای متغیرهای پیوسته معمولاً فاصله اقلیدسی است.
برای متغیرهای گسسته، مانند دسته بندی متون، می توان از یک معیار دیگر مانند فاصله همینگ استفاده کرد.
اگر NN - را با استفاده از الگوریتم های تخصصی مانند تجزیه و تحلیل اجزای همسایه ( Neighbourhood components analysis ) یا حاشیه بزرگ نزدیک ترین همسایه ( Large Margin Nearest Neighbor ) پیاده سازی کرد، می توان دقت اندازه گیری را به شدت بهبود داد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلففرض کنید زوج مرتب های ( Xn, Yn ) , . . . , ( X2, Y2 ) , ( X1, Y1 ) از {۱٬۲} × Rd مقدار می گیرد. ( Y نشان دهنده کلاس X است ) . در نتیجه خواهیم داشت: X|Y = r ~ Pr برای r = ۱٬۲ که Pr توزیع احتمال است.
با داشتن تعدادی اندازه ( norm ) ‖. ‖ در Rd و نقطه x، زوج مرتب های ( X ( n ) , Y ( n ) ) , . . . , ( X ( 2 ) , Y ( 2 ) ) , ( X ( 1 ) , Y ( 1 ) را که ترتیب دیگری از داده های اولیه هستند با شرط ǁX ( n ) ≤ xǁ , . . . , ǁX ( 1 ) ≤ xǁ تعریف می کنیم.
داده های اولیه، بردارهایی در یک فضای چند بعدی هستند که هر کدام شامل برچسبی به نام دسته می باشند.
فاز یادگیری ( training phase ) الگوریتم، شامل ذخیره سازی بردارهای ویژگی و برچسب دسته نمونه های اولیه است.
در فاز طبقه بندی، k یک ثابت توسط کاربر تعریف می شود و بردار بدون برچسب ( نقطه تست ) از دسته ای است که بیشترین تعداد را در k نزدیک ترین همسایه آن نقطه داشته باشد. به این ترتیب برچسب نقطه تست نیز مشخص می شود.
معیار فاصله برای متغیرهای پیوسته معمولاً فاصله اقلیدسی است.
برای متغیرهای گسسته، مانند دسته بندی متون، می توان از یک معیار دیگر مانند فاصله همینگ استفاده کرد.
اگر NN - را با استفاده از الگوریتم های تخصصی مانند تجزیه و تحلیل اجزای همسایه ( Neighbourhood components analysis ) یا حاشیه بزرگ نزدیک ترین همسایه ( Large Margin Nearest Neighbor ) پیاده سازی کرد، می توان دقت اندازه گیری را به شدت بهبود داد.
