الگوریتم درخت تصمیم Decision Tree

الگوریتم درخت تصمیم

الگوریتم درخت تصمیم Decision Tree

 

الگوریتم درخت تصمیم یا الگوریتم ID3 یکی از روش های دسته بندی یا classification در زیر شاخه گروه جدول فراوانی Frequency Table در بحث پیش بینی آینده predicting the future در علوم داده یا داده کاوی است. در ادامه به توضیح و تشریح این الگوریتم همراه با یک مثال خواهیم پرداخت.

الگوریتم درخت تصمیم چیست؟

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

دسته بندی درخت تصمیم

الگوریتم درخت تصمیم

الگوریتم اصلی ساختن درختان تصمیم گیری به نام ID3 توسط J. R. Quinlan که از جستجوی حریصانه از بالا به پایین و حریصانه در فضای شاخه های احتمالی و بدون برگشت استفاده می کند. ID3 از Entropy و Information Gain برای ساخت درخت تصمیم استفاده می کند. با توجه به آموزش های قبلی در مدل ZeroR هیچ پیش بینی کننده ای وجود ندارد ، در مدل OneR سعی می کنیم بهترین پیش بینی کننده را به تنهایی پیدا کنیم ، مدل بیزی ساده نیز شامل کلیه پیش بینی کننده ها با استفاده از قانون Bayes و پیش فرض های استقلال بین پیش بینی کننده ها است اما درخت تصمیم شامل کلیه پیش بینی کننده ها با فرضیات وابستگی بین پیش بینی کننده ها است.

آنتروپی

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

دسته بندی درخت تصمیم

برای ساختن یک درخت تصمیم گیری ، باید دو نوع آنتروپی را با استفاده از جداول فرکانس به شرح زیر محاسبه کنیم:

الف) آنتروپی با استفاده از جدول فرکانس یک ویژگی:

فرمول دسته بندی درخت تصمیم با یک ویژگی

ب) آنتروپی با استفاده از جدول فرکانس دو ویژگی:

به دست آوردن اطلاعات یا Information Gain

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

مرحله 1: آنتروپی هدف را محاسبه کنید.

الگوریتم ID3

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

الگوریتم ID3 محاسبه آنتروپی

مرحله 3: ویژگی را با بیشترین سود Gain به عنوان گره تصمیم گیری انتخاب کنید ، مجموعه داده را توسط شاخه های آن تقسیم کنید و همان روند را در هر شاخه تکرار کنید.

Information Gain درخت تصمیم

مرحله 4a: شاخه ای با آنتروپی 0 ، گره برگ است.

الگوریتم درخت تصمیم Decision Tree

مرحله 4b: یک شاخه با آنتروپی بیش از 0 نیاز به تقسیم بیشتر دارد.

الگوریتم درخت تصمیم

مرحله 5: الگوریتم ID3 به طور بازگشتی روی شاخه های بدون برگ اجرا می شود ، تا زمانی که همه داده ها طبقه بندی شوند.

قوانین تصمیم گیری برای درخت تصمیم

با تصمیم گیری از گره ریشه به گره های برگ یک به یک ، درخت تصمیم گیری می تواند به راحتی به مجموعه ای از قوانین تبدیل شود.

قوانین تصمیم گیری برای درخت تصمیم

 

مطالب زیر را حتما بخوانید

دیدگاه ها

  1. رضا گفت:

    ممنون از این توضیحات عالی. دنبال یه متن تخصصی در مورد الگوریتم درخت های تصمیم بودم که این نوشته رو پیدا کردم. بازم ممنون

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.