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

درختان اضافی (Extra Trees)

معرفی‌شده توسط
Geurts, P.; Ernst, D.; Wehenkel, L.
سال
2006
نوع
Ensemble (extremely randomized decision trees)
خانواده
Machine learning

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

اندازه قلم

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

Extra Trees (درختان فوق‌العاده تصادفی)، که در سال ۲۰۰۶ توسط Geurts، Ernst و Wehenkel معرفی شد، مجموعه‌ای از درختان تصمیم است که تصادفی‌سازی را بیش از جنگل تصادفی (Random Forest) پیش می‌برد. هم ویژگی‌های نامزد و هم آستانه‌های تقسیم به طور کاملاً تصادفی در هر گره انتخاب می‌شوند و جستجوی حریصانه برای آستانه‌ها را حذف می‌کنند. این تصادفی‌سازی اضافی واریانس را کاهش می‌دهد، اغلب دقت جنگل تصادفی را مطابقت می‌دهد یا از آن فراتر می‌رود و در زمان آموزش به طور قابل توجهی سریع‌تر اجرا می‌شود.

شهود پشت روش

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

تاریخ

Extra Trees توسط Pierre Geurts، Damien Ernst و Louis Wehenkel در مقاله‌ای در سال ۲۰۰۶ در مجله Machine Learning پیشنهاد شد. نویسندگان نشان دادند که معرفی تصادفی‌سازی کامل آستانه‌های تقسیم — به جای جستجوی برش‌های بهینه — واریانس را به طور قابل توجهی کاهش می‌دهد در حالی که افزایش جزئی در سوگیری را مبادله می‌کند. از آن زمان، این روش به یک جایگزین استاندارد برای جنگل تصادفی در اکوسیستم scikit-learn تبدیل شده است و به طور گسترده به عنوان یک خط پایه سریع و با دقت بالا برای معیارهای داده‌های جدولی استفاده می‌شود.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

برخلاف جنگل تصادفی، Extra Trees به طور پیش‌فرض هر درخت را بر روی کل مجموعه آموزشی آموزش می‌دهد به جای یک نمونه بوت استرپ. این امر سوگیری معرفی شده توسط نمونه‌برداری را کاهش می‌دهد اما به این معنی است که مجموعه خارج از کیسه (out-of-bag) داخلی وجود ندارد؛ بنابراین، اعتبارسنجی متقابل برای تخمین صادقانه خطا لازم است.

2

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

3

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

4

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

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

دام‌های رایج

  • نادیده گرفتن اعتبارسنجی متقابل و تکیه بر دقت درون نمونه، از آنجایی که به طور پیش‌فرض هیچ تخمین OOB تولید نمی‌شود.
  • نادیده گرفتن عدم تعادل کلاس — قبل از برازش از `class_weight='balanced'` یا نمونه‌برداری مجدد استفاده کنید.
  • گزارش فقط دقت بدون معیارهای مکمل مانند F1، AUC یا RMSE.
  • در نظر گرفتن رتبه‌بندی اهمیت ویژگی به عنوان پایدار بدون بررسی قابلیت تکرار در میان بذرها.

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

Extra Trees چگونه با جنگل تصادفی تفاوت دارد؟

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

کدام را ترجیح دهم — Extra Trees یا جنگل تصادفی؟

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

به چند درخت نیاز دارم؟

با ۱۰۰ درخت شروع کنید و تا زمانی که عملکرد در یک مجموعه اعتبارسنجی یا در اعتبارسنجی متقابل پایدار شود، افزایش دهید. درختان بیشتر پایداری را بهبود می‌بخشند اما حافظه و تأخیر پیش‌بینی را افزایش می‌دهند.

آیا Extra Trees بیش‌برازش (overfit) می‌کند؟

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

چگونه عملکرد مدل را بدون مجموعه OOB ارزیابی کنم؟

از اعتبارسنجی متقابل k-fold استفاده کنید — معمولاً ۵ یا ۱۰ برابر. وظایف طبقه‌بندی را با دقت، F1 و AUC ارزیابی کنید؛ وظایف رگرسیون را با RMSE و R-squared ارزیابی کنید.

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

منابع

  1. Geurts, P., Ernst, D. & Wehenkel, L. (2006). Extremely randomized trees. Machine Learning, 63(1), 3–42.

    باز کردن مرجع DOI
    کپی شد.
  2. Extra-Trees. Wikipedia.

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