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

درخت تصمیم آنلاین

معرفی‌شده توسط
Domingos, P. & Hulten, G.
سال
2000
نوع
Incremental supervised classifier
خانواده
Machine learning

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

اندازه قلم

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

درخت تصمیم آنلاین (Online Decision Tree) نوعی درخت تصمیم است که به صورت افزایشی از یک جریان پیوسته داده و بدون نیاز به بازبینی نمونه‌های گذشته، رشد می‌کند. الگوریتم غالب در این زمینه، درخت هوفدینگ (Hoeffding Tree) یا VFDT است که از کران هوفدینگ (Hoeffding bound) برای تصمیم‌گیری در مورد زمان کافی بودن تعداد نمونه‌ها در یک گره برای تقسیم مطمئن آن استفاده می‌کند. این ویژگی امکان طبقه‌بندی مقیاس‌پذیر و بلادرنگ را بر روی جریان‌های داده‌ای بالقوه نامحدود فراهم می‌آورد.

شهود پشت روش

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

تاریخ

الگوریتم بنیادی، درخت تصمیم بسیار سریع (Very Fast Decision Tree) یا درخت هوفدینگ (Hoeffding Tree)، توسط دومینگوس و هولتن در KDD 2000 معرفی شد. این الگوریتم از نابرابری هوفدینگ برای محدود کردن خطا در انتخاب ویژگی‌های تقسیم از یک جریان داده استفاده کرد و امکان استنتاج مجانبی صحیح درخت را بدون ذخیره نمونه‌ها فراهم آورد. هولتن، اسپنسر و دومینگوس این روش را در سال 2001 به جریان‌های دارای رانش مفهوم گسترش دادند. این رویکرد به سنگ بنای چارچوب MOA (Massive Online Analysis) تبدیل شد و بر نسلی از روش‌های گروهی جریانی تأثیر گذاشت.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

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

2

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

3

کران هوفدینگ (یا چرنوف) اپسیلون = sqrt(R^2 * ln(1/delta) / (2n)) حداکثر خطای بین بهترین ویژگی تقسیم مشاهده‌شده و بهترین تقسیم واقعی را با احتمال حداقل 1 - delta کمی‌سازی می‌کند. با افزایش n، اپسیلون به سمت صفر کاهش می‌یابد.

فرمول
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}
4

اگر تفاوت بهره اطلاعاتی (information-gain) بین بهترین و دومین بهترین کاندیدای تقسیم از کران هوفدینگ فعلی فراتر رود، برگ با یک گره تقسیم داخلی بر روی ویژگی برنده جایگزین می‌شود و دو شمارنده برگ جدید مقداردهی اولیه می‌شوند. در غیر این صورت، گره منتظر داده‌های بیشتری می‌ماند.

5

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

دام‌های رایج

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

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

درخت هوفدینگ چه تفاوتی با درخت تصمیم CART استاندارد دارد؟

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

آیا درخت تصمیم آنلاین رانش مفهوم را مدیریت می‌کند؟

درخت هوفدینگ پایه به طور خودکار رانش را تشخیص نمی‌دهد. توسعه‌هایی مانند درخت تصمیم بسیار سریع تطبیق‌پذیر با مفهوم (Concept-adapting Very Fast Decision Tree) یا CVFDT و نسخه‌های ترکیب‌شده با آشکارسازهای رانش ADWIN یا Page-Hinkley می‌توانند زیردرخت‌های منسوخ را هنگام تشخیص رانش جایگزین کنند.

دوره مهلت چیست و چگونه باید آن را تنظیم کنم؟

دوره مهلت تعداد نمونه‌هایی است که بین ارزیابی‌های متوالی تقسیم به یک برگ می‌رسند. یک مقدار بزرگتر محاسبات را کاهش می‌دهد اما تقسیم‌ها را به تأخیر می‌اندازد؛ یک مقدار کوچکتر تقسیم‌ها را با هزینه CPU بالاتر بیشتر ارزیابی می‌کند. مقادیر پیش‌فرض معمول بین 200 تا 1000 نمونه متغیر است.

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

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

دقت در مقایسه با روش‌های دسته‌ای بر روی یک مجموعه داده ثابت چگونه است؟

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

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

منابع

  1. Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.

    باز کردن مرجع انتشار
    کپی شد.
  2. Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.

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