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

Online Random Forest

معرفی‌شده توسط
Saffari, A. et al.
سال
2009
نوع
Incremental ensemble (streaming decision trees)
خانواده
Machine learning

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

اندازه قلم

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

Online Random Forest (ORF) the Random Forest کلاسیک را به محیط‌های جریانی تعمیم می‌دهد و هر درخت را به صورت افزایشی با ورود مشاهدات جدید به‌روزرسانی می‌کند، بدون اینکه مجموعه داده آموزشی کامل را ذخیره یا مجدداً پخش کند. الگوریتم‌هایی مانند Adaptive Random Forests (ARF) تشخیص رانش را اضافه می‌کنند تا مجموعه زمانی که توزیع داده‌ها در طول زمان تغییر می‌کند، سازگار شود.

شهود پشت روش

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

تاریخ

کیسه پارچه‌ای آنلاین توسط Oza & Russell (2001) به عنوان تقریب وزن‌دار پواسون برای تجمیع بوت‌استرپ فرموله شد. Saffari و همکاران (2009) On-line Random Forests را معرفی کردند که کیسه پارچه‌ای آنلاین را با انتخاب تصادفی ویژگی و معیارهای شکاف مبتنی بر هوفدینگ برای جریان‌های بینایی کامپیوتر ترکیب می‌کند. Gomes و همکاران (2017) Adaptive Random Forests (ARF) را معرفی کردند که تشخیص رانش در هر درخت را از طریق ADWIN اضافه می‌کند و دقت پیشرفته‌ای را در وظایف طبقه‌بندی جریان داده معیار نشان داد. ARF به یک خط پایه استاندارد در چارچوب MOA (Massive Online Analysis) تبدیل شد.

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

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

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

  • تصمیمات شکاف که در اوایل با داده‌های پراکنده گرفته می‌شوند می‌توانند نامناسب باشند و بازنگری آنها دشوار است.
  • تخمین‌های اهمیت ویژگی نسبت به Random Forest دسته‌ای کمتر پایدار هستند.
  • تنظیم ابرپارامترها (تعداد درختان، آستانه‌های تشخیص رانش) در یک زمینه جریانی پیچیده‌تر است.
  • ارزیابی نیازمند پروتکل‌های اختصاصی مبتنی بر جریان (پیش‌بینی‌کننده/تست-قبل-آموزش) است که با اعتبارسنجی متقابل استاندارد متفاوت است.

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

برای هر مشاهده ورودی، هر درخت به طور مستقل k را از توزیع Poisson(1) می‌کشد و مشاهده را به عنوان k تکرار مجازی از خود در نظر می‌گیرد. هنگامی که k = 0 درخت نقطه را نادیده می‌گیرد (به عنوان نمونه خارج از کیسه خود عمل می‌کند). این امر نمونه‌گیری بوت‌استرپ را بدون نیاز به مجموعه داده کامل تقریب می‌زند.

فرمول
k \sim \text{Poisson}(\lambda),\; \lambda=1
3

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

4

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

5

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

فرمول
\hat{y} = \text{mode/mean of active trees}

دام‌های رایج

  • ارزیابی با اعتبارسنجی متقابل k-fold استاندارد، که داده‌های i.i.d را فرض می‌کند و ترتیب زمانی را نادیده می‌گیرد.
  • نادیده گرفتن رانش مفهوم: عدم گنجاندن جزء تشخیص رانش زمانی که توزیع داده‌ها در طول زمان تغییر می‌کند.
  • مقایسه مستقیم دقت جنگل آنلاین با یک Random Forest دسته‌ای که بر روی کل مجموعه داده تاریخی آموزش دیده است - دومی دارای مزیت اطلاعاتی ذاتی است.
  • استفاده از درختان بسیار کم در اوایل جریان قبل از اینکه هر درخت داده‌های کافی برای ایجاد شکاف‌های قابل اعتماد را ببیند.
  • فراموش کردن اینکه کیسه پارچه‌ای وزن‌دار پواسون بوت‌استرپ را تقریب می‌زند - آن خواص آماری بوت‌استرپ دسته‌ای را دقیقاً بازتولید نمی‌کند.

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

Online Random Forest چگونه با Random Forest استاندارد تفاوت دارد؟

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

ترفند وزن‌دهی پواسون چیست؟

هر نمونه ورودی k بار به هر درخت نشان داده می‌شود، که در آن k از Poisson(1) کشیده شده است. از آنجایی که مقدار مورد انتظار k برابر 1 است، و k با احتمال ~37% برابر 0 است، این فرآیند بوت‌استرپ (نمونه‌گیری با جایگزینی) را بدون نیاز به کل مجموعه داده در حافظه، از نظر آماری تقریب می‌زند.

چگونه باید یک جنگل تصادفی آنلاین را ارزیابی کنم؟

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

چه زمانی باید تشخیص رانش را اضافه کنم؟

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

آیا Adaptive Random Forest همان است؟

ARF پرکاربردترین نوع Online Random Forest است. این الگوریتم کیسه پارچه‌ای آنلاین، انتخاب تصادفی ویژگی و تشخیص رانش ADWIN در هر درخت را ترکیب می‌کند و در کتابخانه‌های MOA و scikit-multiflow/River موجود است. اصطلاح 'Online Random Forest' اغلب به طور کلی به خانواده اشاره دارد؛ ARF یک پیاده‌سازی خاص و بسیار توصیه شده است.

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

منابع

  1. Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.

    باز کردن مرجع انتشار
    کپی شد.
  2. Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.

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