هرس کردن درخت جستجو

فرایند هرس کردن میتواند به دو نوع تقسیم می‌شود(پیش هرس و پس هرس).

پیش‌هرس با جایگزین‌کردن یک معیار توقف از القای الگوریتم بر روی تمام مجموعه‌آموزشی جلوگیری می‌کند(برای مثال عمق درخت). روش‌های پیش‌هرس کارآمدتر در نظر گرفته می‌شوند زیرا آنها کل مجموعه را القا نمی‌کنند و درخت از ابتدا کوچک می‌مانند. روش‌های پیش‌هرس همگی دارای مشکل «تاثیر افقی» می‌باشند و این را می‌توان به عنوان خاتمه زودرس و ناخواسته توسط معیار توقف در نظر گرفت.

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

رویه‌ها براساس رویکرد آنها بر روی درخت از یکدیگر متمایز میشوند(بالا به پایین و پایین به بالا)

هرس پایین به بالا

این رویه از آخرین گره در درخت شروع می‌کند(پایین‌ترین عمق) و به صورت بازگشتی و رو به بالا ارتباط هر گره را جداگانه بررسی می‌کند. اگر ارتباطی زیادی برای طبقه بندی نداشته باشد، گره مورد نظر حذف و یا با یک برگ جایگزین می‌شود. مزیت این است که هیچ کدوم از زیردرخت‌های مرتبط از بین نمی‌روند. این روش شامل هرس خطای کاهش‌یافته (به انگلیسی: Reduced Error Pruning or REP)، هرس پیچیدگی هزینه مینیمم (ب انگلیسی: Minimum Cost Complexity Pruning or MCCP) و هرس خطای مینیمم (به انگلیسی: Minimum Error Pruning or MEP) می‌باشد.

هرس بالا به پایین

این روش برخلاف روش پایین به بالا، از ریشه درخت آغاز می‌کند. و با حرکت به سمت پایین ساختار، یک «بررسی ارتباط» انجام می‌دهد تا در مورد مرتبط بودن یک گره با طبقه‌بندی تصمیم‌گیری کند. با هرس کردن نودهای میانی یک درخت، ممکن است تمامی زیردرخت‌های آن گره را (بدون درنظر گرفتن ارتباط آن‌ها) حذف کند. یک نمونه از این روش هرس بدبینانه خطا(به انگلیسی: Pessimistic Error Pruning or PEP) است.

هرس خطای کاهش یافته

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

هرس پیچیدگی هزینه

هرس پیچیدگی هزینه مجموعه‌ای از درختان ${\displaystyle T_m...T_0}$

1. میزان نرخ خطای درخت ${\displaystyle T}$
   روی مجموعه‌داده ${\displaystyle S}$
   به صورت ${\displaystyle err(T,S)}$
   مشخص کن.
2. زیردرختی که کمترین مقدار${\displaystyle \frac{\mathrm{err}(\mathrm{prune}(T,t),S)-\mathrm{err}(T,S)}{\left|\mathrm{leaves}(T)\right|-\left|\mathrm{leaves}(\mathrm{prune}(T,t))\right|}}$
   را دارد، برای حذف کردن انتخاب کن.

تابع ${\displaystyle prune(T,t)}$

1. ↑ Trevor Hastie, Robert Tibshirani, and Jerome Friedman.

• MDL بر اساس هرس درخت تصمیم
• هرس درخت تصمیم با استفاده از شبکه‌های عصبی مصنوعی backpropagation

• الگوریتم سریع و بالا به پائین هرس درخت تصمیم
• آشنایی با هرس درخت تصمیم