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

درخت تصمیم نیمه‌نظارت‌شده

معرفی‌شده توسط
Various (Levin & Shapiro; Zhu & Goldberg lineage)
سال
2000s
نوع
Semi-supervised classifier / regressor
خانواده
Machine learning

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

اندازه قلم

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

درخت تصمیم نیمه‌نظارت‌شده، القای درخت تصمیم استاندارد - مانند CART یا C4.5 - را برای بهره‌برداری از مشاهدات بدون برچسب در کنار مجموعه آموزشی برچسب‌دار گسترش می‌دهد. با تخصیص تکراری برچسب‌های موقت به داده‌های بدون برچسب و گنجاندن آن‌ها در فرآیند رشد یا تقسیم، الگوریتم می‌تواند به دقت بهتری نسبت به یک درخت کاملاً نظارت‌شده که تنها بر روی زیرمجموعه برچسب‌دار آموزش دیده است، دست یابد؛ این امر به‌ویژه زمانی ارزشمند است که برچسب‌گذاری پرهزینه یا زمان‌بر باشد.

شهود پشت روش

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

تاریخ

یادگیری نیمه‌نظارت‌شده در اواخر دهه 1990 ظهور کرد زیرا محققان به دنبال بهره‌برداری از فراوانی داده‌های بدون برچسب موجود در حوزه‌هایی مانند طبقه‌بندی وب و زیست‌شناسی محاسباتی بودند. انواع خودآموزی درختان تصمیم، که در آن یک درخت به‌طور تکراری داده‌های بدون برچسب خود را برچسب‌گذاری می‌کند، از اولین نمونه‌های اولیه بودند. درمان رسمی در بررسی Zhu & Goldberg (2009) ظاهر شد، که خودآموزی مبتنی بر درخت را در طبقه‌بندی گسترده‌تر یادگیری نیمه‌نظارت‌شده قرار می‌دهد. از آن زمان، رویکردها به تنظیمات گروهی گسترش یافته‌اند و جنگل‌های تصادفی نیمه‌نظارت‌شده و درختان تقویت‌شده گرادیان را تولید کرده‌اند.

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

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

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

  • خطاهای شبه‌برچسب از یک درخت اولیه غیرقابل اعتماد می‌تواند در طول تکرارها تقویت شود و عملکرد را نسبت به یک پایه کاملاً نظارت‌شده کاهش دهد.
  • این روش فرض می‌کند که داده‌های بدون برچسب از توزیع مشابهی با داده‌های برچسب‌دار پیروی می‌کنند؛ تغییر توزیع این فرض را نقض می‌کند.
  • هزینه محاسباتی با هر تکرار افزایش می‌یابد زیرا درختان بر روی مجموعه داده‌های مؤثر فزاینده‌ای بازآموزی می‌شوند.
  • انتخاب آستانه اطمینان برای گنجاندن شبه‌برچسب نیاز به تنظیم دقیق و اعتبارسنجی متقابل دارد.

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

نقاط قوت

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

کاربردها

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

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

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

1

یک درخت تصمیم استاندارد (مانند CART یا C4.5) تنها با استفاده از بخش برچسب‌دار مجموعه داده، برازش داده می‌شود. این مدل اولیه، تقریب اولیه‌ای از مرزهای تصمیم‌گیری ارائه می‌دهد و به عنوان بذری برای تکرارهای نیمه‌نظارت‌شده بعدی عمل می‌کند.

2

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

3

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

4

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

5

تکرار تا زمانی ادامه می‌یابد که برچسب‌های موقت در دورهای متوالی تثبیت شوند یا به حداکثر حد تکرار برسیم. سپس استراتژی‌های هرس پس از آن (هرس هزینه-پیچیدگی، حداقل اندازه برگ) برای کنترل بیش‌برازش بر روی داده‌های شبه‌برچسب‌گذاری شده بر روی درخت نهایی اعمال می‌شوند.

دام‌های رایج

  • استفاده از تمام شبه‌برچسب‌ها بدون توجه به اطمینان، که اجازه می‌دهد تخصیص‌های با کیفیت پایین بر تکرارهای بعدی غلبه کنند.
  • عدم تأیید اینکه داده‌های بدون برچسب قبل از آموزش از همان توزیع مجموعه برچسب‌دار گرفته شده‌اند.
  • رفتار با آماره‌های برگ درخت نهایی به عنوان کاملاً نظارت‌شده هنگام گزارش معیارهای عملکرد - ارزیابی خارج از نمونه (out-of-bag) یا برچسب‌دار نگه‌داشته‌شده (held-out) لازم است.
  • نادیده گرفتن هرس پس از افزایش شبه‌برچسب، که منجر به بیش‌برازش شدید بر روی برچسب‌های موقت پر نویز می‌شود.
  • مقایسه مستقیم با یک درخت کاملاً نظارت‌شده که بر روی همان زیرمجموعه برچسب‌دار آموزش دیده است، بدون در نظر گرفتن داده‌های بدون برچسب اضافی استفاده شده.

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

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

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

به چند مثال برچسب‌دار برای شروع نیاز دارم؟

حداقل جهانی وجود ندارد، اما درخت نظارت‌شده اولیه باید به اندازه کافی قابل اعتماد باشد تا شبه‌برچسب‌های مفیدی تولید کند. در عمل، اغلب حداقل 20-50 مثال برچسب‌دار در هر کلاس توصیه می‌شود؛ با تعداد کمتر، خطر انتشار خطا بالا است و رویکردهای جایگزین مانند انتشار برچسب ممکن است بهتر عمل کنند.

آیا باید از تمام داده‌های بدون برچسب استفاده کنم یا زیرمجموعه‌ای را انتخاب کنم؟

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

آیا این جایگزین اعتبارسنجی متقابل استاندارد می‌شود؟

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

آیا می‌توانم این را با روش‌های گروهی ترکیب کنم؟

بله. جنگل‌های تصادفی نیمه‌نظارت‌شده و رویکردهای هم‌جنگل (co-forest) این ایده را به گروه‌ها گسترش می‌دهند، که می‌تواند واریانس خطاهای شبه‌برچسب را کاهش دهد و معمولاً بهتر از یک درخت نیمه‌نظارت‌شده منفرد عمل می‌کند.

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

منابع

  1. Levin, E. & Shapiro, E. (2000). Learning Decision Trees from Semi-labeled Examples. Proceedings of the ICML Workshop on Attribute-Value and Relational Learning.

    باز کردن مرجع انتشار
    کپی شد.
  2. Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.

    شابک: 978-1-598-29548-9
    کپی شد.