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

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

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

هرس کردن باید اندازه درخت یادگیرنده را بدون کاهش دقت پیش‌بینی بر روی مجموعه cross-validation انجام شود. تکنیک‌های زیادی برای هرس کردن درخت‌ها وجود دارد که از شاخص‌های متفاوتی برای افزایش کارایی استفاده می‌کنند.

تکنیک‌ها

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

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

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

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

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

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

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

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

الگوریتم‌های هرس کردن

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

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

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

هرس پیچیدگی هزینه مجموعه‌ای از درختان $T_{m}...T_{0}$ را ایجاد می‌کند که $T_{0}$ درخت اولیه و $T_{m}$ ریشه درخت است. در قدم $i$ یک درخت جدید با حذف یک زیردرخت از $T_{i-1}$ و جایگزین‌کردن آن با یک گره برگ که مقدار انتخاب شده آن از الگوریتم ساخت درخت بدست آمده است، ایجاد می‌شود. زیر درختی که حذف شده است به صورت زیر انتخاب می‌شود:

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

تابع $prune(T,t)$ درختی را نمایش می‌دهد که از هرس زیر درخت $t$ در درخت $T$ به وجود آمده است. به محض اینکه تمام درختان ایجاد شوند، بهترین درخت با اندازه‌گیری میزان دقت بر روی مجموعه‌آموزشی یا cross-validation انتخاب می‌شود.

برای مطالعهٔ بیشتر

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

پیوند به بیرون

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