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

هرس یک روش فشرده سازی در یادگیری ماشین و جستجوی درخت است که با حذف قسمت های غیرضروری و غیرمرتبط با طبقه بندی، اندازه درخت تصمیم را کاهش می دهد. هرس، پیچیدگی طبقه بندی نهایی را کاهش می دهد که در نتیجه با جلوگیری از بیش برازشی، دقت پیش بینی را افزایش می دهد.
یکی از پرسش هایی که در مورد یک درخت تصمیم گیری مطرح می شود اندازه بهینه درخت نهایی است. یک درخت خیلی بزرگ، ریسک زیادی را در پیداکردن بیش برازشی بر روی داده های آموزشی متحمل می شود و همچنین قدرت کمی در تعمیم دادن به نمونه های جدیدتر دارد. در مقابل، یک درخت خیلی کوچک ممکن است ساختارهای اطلاعاتی مهم را فضای حالت کشف نکند. با این حال بسیار سخت می توان تشخیص داد که یک الگوریتم درخت چه زمانی باید متوقف شود زیرا صحبت درباره کاهش خطا با اضافه کردن یک گره جدید به درخت غیرممکن است. این مشکل تحت عنوان «اثر افقی» ( به انگلیسی: horizon effect ) شناخته شده است. یک استراتژی مرسوم این است که به رشد درخت تا زمانی که هر گره حاوی تعداد کمی از نمونه ها باشد ادامه داده شود و سپس با هرس کردن، گره هایی که اطلاعات مفیدی ندارند را حذف شوند. [ ۱]
هرس کردن باید اندازه درخت یادگیرنده را بدون کاهش دقت پیش بینی بر روی مجموعه cross - validation انجام شود. تکنیک های زیادی برای هرس کردن درخت ها وجود دارد که از شاخص های متفاوتی برای افزایش کارایی استفاده می کنند.
فرایند هرس کردن میتواند به دو نوع تقسیم می شود ( پیش هرس و پس هرس ) .
پیش هرس با جایگزین کردن یک معیار توقف از القای الگوریتم بر روی تمام مجموعه آموزشی جلوگیری می کند ( برای مثال عمق درخت ) . روش های پیش هرس کارآمدتر در نظر گرفته می شوند زیرا آنها کل مجموعه را القا نمی کنند و درخت از ابتدا کوچک می مانند. روش های پیش هرس همگی دارای مشکل «تاثیر افقی» می باشند و این را می توان به عنوان خاتمه زودرس و ناخواسته توسط معیار توقف در نظر گرفت.
پس هرسی ( یا به اختصار هرس ) مرسوم ترین روش خلاصه سازی درخت ها می باشد. در این روش نودها و زیردرخت ها با برگ ها جایگزین می شوند تا پیچیدگی را کاهش دهند. هرس کردن نه تنها می تواند اندازه درخت را کاهش دهد بلکه می تواند دقت طبقه بندی را بر روی داده های دیده نشده افزایش دهد. ممکن است دقت انتساب در مجموعه آموزشی افت پیدا کند، اما دقت ویژگی های طبقه بندی درخت به طور کلی افزایش می یابد.