الگوریتم درخت تصمیم Decision Tree — آموزش مفاهیم به همراه ۱ مثال کاربردی

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

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

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

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

الگوریتم اصلی ساختن درختان تصمیم گیری به نام ID3 توسط J. R. Quinlan که از جستجوی حریصانه از بالا به پایین و حریصانه در فضای شاخه‌های احتمالی و بدون برگشت استفاده می‌کند. ID3 از Entropy و Information Gain برای ساخت درخت تصمیم استفاده می‌کند.

با توجه به آموزش‌های قبلی در مدل ZeroR هیچ پیش بینی کننده‌ای وجود ندارد ، در مدل OneR سعی می‌کنیم بهترین پیش بینی کننده را به تنهایی پیدا کنیم ، مدل بیزی ساده نیز شامل کلیه پیش بینی کننده‌ها با استفاده از قانون Bayes و پیش فرض‌های استقلال بین پیش بینی کننده‌ها است اما درخت تصمیم شامل کلیه پیش بینی کننده‌ها با فرضیات وابستگی بین پیش بینی کننده‌ها است.

آنتروپی

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

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

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

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

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

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

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

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

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

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

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

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

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

سخن پایانی در مورد الگوریتم DT

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