درخت تصمیم
درخت تصمیم‌گیری (Decision Tree) یک ابزار برای پشتیبانی از تصمیم است که از درخت‌ها برای مدل کردن استفاده می‌کند. درخت تصمیم به‌طور معمول در تحقیق‌ها و عملیات مختلف استفاده می‌شود. به‌طور خاص در آنالیز تصمیم، برای مشخص کردن استراتژی که با بیشترین احتمال به هدف برسد بکار می‌رود. استفاده دیگر درختان تصمیم، توصیف محاسبات احتمال شرطی است.
درخت‌ها کاربرد فراوانی در علوم کامپیوتر و مهندسی نرم‌افزار دارند. از ساختمان داده و طراحی الگوریتم تا سیستم‌های عامل و سیستم‌های توزیع شده، همه به نوعی و در قسمت‌های مختلف از درخت‌های تصمیم استفاده کرده‌اند.
در داده‌کاوی و طبقه‌بندی نیز این درخت‌ها جایگاه ویژه‌ای دارند و بسیاری از الگوریتم‌های طبقه‌بندی بر پایه‌ی این درخت‌ها ساخته شده‌اند.
الگوریتم ID3 و ساختار Entropy و Gain
این الگوریتم، درختانِ تصمیمِ از بالا به پایین می‌سازد و با طرح این سوال که چه صفتی باید در ریشه‌ی درخت آزمایش شود آغاز می‌کند. برای پاسخ به این سوال، با استفاده از یکی از انواع آزمایش‌های آماری برای تعیین مناسب‌ترین صفت برای دسته‌بندی مثال‌های آموزشی، تصمیم براساس هر صفت نمونه را ارزیابی می‌کند.
سپس بهترین صفت را انتخاب کرده و به عنوان تست در گره‌ی ریشه‌ی درخت استفاده می‌کند. برای هر مقدار ممکن صفت تست شده در ریشه، یک گره‌ی متناظر ایجاد شده و مثال‌های آموزشی براساس مقادیر صفت تست، بین این گره‌ها افراز می‌شوند.
تمام فرآیند ذکر شده، با استفاده از مثال‌های آموزشی نسبت داده شده به هر گره، برای انتخاب بهترین صفت برای آزمایشی در آن گره‌ی درخت تکرار می‌شود. این روش جستجویی حریصانه را برای یک درخت تصمیم قابل قبول ارائه می‌دهد که در این الگوریتم، هیچ‌گاه برای در نظر گرفتن دوباره‌ی انتخاب‌های قبلی، به عقب برگشت نمی‌شود.
این الگوریتم در یادگیری نمونه‌هایی با صفات فاقد مقدار مشکل داشته و غیرافزایشی و ارزان می‌باشد.
پیاده‌سازی الگوریتم درخت تصمیم ID3
جدول فرضیه خود را در این قسمت درج کنید، سطر اول برای عنوان صفت‌ها استفاده کنید، سطرهای بعدی مربوط به مقادیر می‌باشند، توجه داشته باشید کلمات با ویرگول از هم جدا می‌شوند.
مراجع
- https://www.xoriant.com/blog/product-engineering/decision-trees-machine-learning-algorithm.html
