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

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

معرفی‌شده توسط
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
سال
2002 (semi-supervised extension); 1967 (KNN base)
نوع
Semi-supervised classifier / label propagation
خانواده
Machine learning

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

اندازه قلم

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

K-نزدیک‌ترین همسایگی نیمه‌نظارت‌شده (Semi-supervised KNN) الگوریتم کلاسیک K-نزدیک‌ترین همسایگی را گسترش می‌دهد تا از مجموعه‌های بزرگ داده بدون برچسب در کنار مجموعه‌ای کوچک از داده‌های برچسب‌دار بهره‌برداری کند. با ساختن یک گراف KNN بر روی تمام مشاهدات و انتشار برچسب‌های شناخته‌شده از طریق یال‌های گراف، این روش برچسب‌ها را برای نقاط بدون برچسب استنتاج می‌کند بدون اینکه نیاز به حاشیه‌نویسی دستی پرهزینه برای هر نمونه باشد.

شهود پشت روش

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

تاریخ

انتشار برچسب بر روی گراف‌های KNN توسط Zhu و Ghahramani در سال ۲۰۰۲، با تکیه بر ماشین‌های بردار پشتیبان استقرایی (transductive SVM) Vapnik و ایده‌های اولیه انتشار مبتنی بر گراف، سیستم‌بندی شد. این چارچوب در جلد انتشارات MIT به نام Semi-Supervised Learning (Chapelle et al., 2006) که مرجع استاندارد باقی مانده است، تثبیت شد. کتابخانه‌های مقیاس‌پذیر KNN تقریبی (FAISS, Annoy) بعداً این رویکرد را در مقیاس میلیون‌ها نقطه عملی کردند و همچنان به عنوان یک خط پایه قوی برای طبقه‌بندی نیمه‌نظارت‌شده تصویر و متن استفاده می‌شود.

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

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

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

  • ساخت گراف با اندازه مجموعه داده به صورت درجه دوم مقیاس‌پذیر است مگر اینکه از روش‌های تقریبی نزدیک‌ترین همسایه استفاده شود.
  • عملکرد در فضاهای پربعد که معیارهای فاصله قدرت تمایز خود را از دست می‌دهند، به شدت کاهش می‌یابد.
  • فرض می‌کند داده‌های برچسب‌دار و بدون برچسب از یک توزیع استخراج شده‌اند؛ تغییر کوواریانس روش را مختل می‌کند.
  • نیاز به تنظیم دقیق k، پهنای باند هسته یال و پارامتر اختلاط انتشار دارد.
  • انتشار برچسب می‌تواند خطاهای برچسب‌گذاری اولیه را در بخش‌های بزرگی از گراف تقویت کند.

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

نقاط قوت

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

کاربردها

  • طبقه‌بندی تصویر با مجموعه‌ای کوچک از تصاویر برچسب‌دار و مجموعه‌ای بزرگ از داده‌های بدون برچسب.
  • دسته‌بندی متن و اسناد که در آن برچسب‌گذاری دستی پرهزینه است.
  • طبقه‌بندی سوابق پزشکی یا اسلایدهای پاتولوژی با حاشیه‌نویسی‌های محدود توسط متخصص.
  • تشخیص تقلب زمانی که تنها تعداد کمی از موارد تقلب تأیید شده در دسترس است.
  • برچسب‌گذاری داده‌های حسگر در محیط‌های اینترنت اشیاء صنعتی با رویدادهای حقیقت زمینی پراکنده.

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

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

1

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

2

وزن‌های یال، قدرت شباهت بین گره‌های متصل را ثبت می‌کنند، معمولاً از طریق یک هسته گوسی (RBF) که بر روی فاصله اقلیدسی بین بردارهای ویژگی اعمال می‌شود. یک پارامتر پهنای باند سیگما (sigma) کنترل می‌کند که شباهت با فاصله با چه سرعتی کاهش می‌یابد. یال‌های قوی‌تر برچسب‌ها را در طول انتشار راحت‌تر منتقل می‌کنند.

فرمول
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

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

فرمول
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

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

فرمول
\hat{y}_i = \arg\max_c F_{ic}

دام‌های رایج

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

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

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

با k در محدوده ۵-۱۵ شروع کنید و با دقت اعتبارسنجی داده‌های برچسب‌دار نگهداری شده، آن را تنظیم کنید. k کوچک‌تر مرزهای تیزتر و محلی‌تری می‌دهد؛ k بزرگ‌تر اجازه می‌دهد برچسب‌ها بیشتر منتشر شوند اما خطر عبور از مرزهای واقعی کلاس را دارد.

آیا می‌توانم روش را صادقانه ارزیابی کنم در حالی که بیشتر داده‌ها بدون برچسب هستند؟

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

اگر مجموعه داده من برای ساخت گراف کامل KNN خیلی بزرگ باشد چه؟

از کتابخانه‌های تقریبی نزدیک‌ترین همسایه مانند FAISS یا Annoy برای ساخت گراف در زمان O(n log n) به جای O(n^2) استفاده کنید، سپس انتشار برچسب را بر روی گراف تقریبی پراکنده اعمال کنید.

آیا KNN نیمه‌نظارت‌شده همیشه بهتر از KNN نظارت‌شده عمل می‌کند؟

لزوماً نه. اگر داده‌های بدون برچسب خارج از توزیع باشند یا فضای ویژگی بسیار پربعد باشد، گراف نویزی است و انتشار می‌تواند عملکرد را مختل کند. همیشه قبل از ادعای سودمندی داده‌های بدون برچسب، با یک خط پایه KNN نظارت‌شده مقایسه کنید.

آیا این همان انتشار برچسب یا پخش برچسب در scikit-learn است؟

ارتباط نزدیکی دارد. LabelPropagation و LabelSpreading در scikit-learn چارچوب Zhu و Ghahramani را با استفاده از گراف هسته KNN یا RBF پیاده‌سازی می‌کنند، بنابراین آنها پیاده‌سازی‌های مستقیمی از روش شرح داده شده در اینجا هستند.

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

منابع

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    باز کردن مرجع انتشار
    کپی شد.
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    شابک: 978-0-262-03358-9
    کپی شد.