Skip to content
بازگشت به نتایج جست‌وجو

کی-نزدیک‌ترین همسایگان

معرفی‌شده توسط
Cover, T.M. & Hart, P.E.
سال
1967
نوع
Instance-based (non-parametric) learning

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

کی-نزدیک‌ترین همسایگان (KNN)، که توسط کاور و هارت در سال ۱۹۶۷ رسمی شد، یک روش غیرپارامتری و مبتنی بر نمونه است که با نگاه کردن به k نزدیک‌ترین مثال‌ها در داده‌های آموزشی، یک مشاهده جدید را طبقه‌بندی یا پیش‌بینی می‌کند. برای طبقه‌بندی، رأی اکثریت را در میان آن همسایگان می‌گیرد؛ برای رگرسیون، مقادیر آن‌ها را میانگین می‌گیرد.

شهود پشت روش

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

تاریخ

طبقه‌بندی الگوی نزدیک‌ترین همسایه توسط توماس کاور و پیتر هارت در مقاله سال ۱۹۶۷ آن‌ها در IEEE Transactions on Information Theory، که نرخ خطا را قانون نزدیک‌ترین همسایه تجزیه و تحلیل کرد، پایه آماری رسمی خود را دریافت کرد. KNN به یکی از اولین و پایدارترین روش‌های یادگیری مبتنی بر نمونه تبدیل شد و همچنان یک طبقه‌بند پایه استاندارد باقی مانده است.

چه زمانی استفاده شود

از KNN برای طبقه‌بندی یا پیش‌بینی روی داده‌های جدولی با ویژگی‌های پیوسته، دودویی یا ترتیبی و حداقل حدود ۳۰ مشاهده استفاده کنید. این روش هیچ توزیع خاصی را فرض نمی‌کند، اما نیاز دارد که ویژگی‌ها نرمال‌سازی شوند و تعداد ویژگی‌ها نسبت به اندازه نمونه کوچک باقی بماند (p بسیار کمتر از n ترجیح داده می‌شود). در نمونه‌های کوچک یا با ابعاد بالا، نفرین ابعاد غالب می‌شود — فواصل همسایگی بی‌اطلاع می‌شوند — و یک مدل پارامتری مانند رگرسیون لجستیک یا بیز ساده‌تر انتخاب بهتری است.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • مفهوماً ساده و آسان برای توضیح: هیچ معادله‌ای در زمان آموزش وجود ندارد، داده‌ها مدل هستند.
  • غیرپارامتری — هیچ فرضی در مورد توزیع زیربنایی نمی‌کند.
  • به طور طبیعی مسائل چندکلاسه و مرزهای تصمیم‌گیری پیچیده و غیرخطی را مدیریت می‌کند.
  • برای طبقه‌بندی و رگرسیون با همان ایده اساسی کار می‌کند.

کاربردها

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

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

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

1

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

فرمول
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}
2

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

3

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

فرمول
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}

دام‌های رایج

  • نادیده گرفتن استانداردسازی ویژگی، بنابراین یک متغیر در مقیاس بزرگ به طور خاموش فاصله را کنترل می‌کند.
  • انتخاب k به صورت دستی به جای انتخاب آن با اعتبارسنجی متقابل.
  • اعمال KNN با بسیاری از ویژگی‌ها و مشاهدات کم، که در آن نسبت ابعاد/نمونه آن را می‌شکند.
  • گزارش فقط دقت به جای دقت، بازیابی، F1 و ماتریس درهم‌ریختگی.

پرسش‌های متداول

چگونه مقدار k را انتخاب کنم؟

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

چرا باید ویژگی‌ها را استاندارد کنم؟

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

چرا KNN با بسیاری از ویژگی‌ها مشکل دارد؟

در فضاهای با ابعاد بالا، همه نقاط تقریباً هم‌فاصله می‌شوند — نفرین ابعاد — بنابراین همسایگان «نزدیک» دیگر به طور معناداری نزدیک نیستند. عملکرد KNN به سرعت کاهش می‌یابد و یک مدل پارامتری مانند بیز ساده یا رگرسیون لجستیک معمولاً ترجیح داده می‌شود. نگه داشتن p بسیار کوچکتر از n کمک می‌کند.

آیا مرحله آموزشی وجود دارد؟

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

روش‌های مرتبط

منابع

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    باز کردن مرجع DOI
    کپی شد.