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

الگوریتم ID3

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

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

الگوریتم C4.5

این الگوریتم یکی از تعمیم‌های الگوریتم ID3 است که از معیار نسبت بهره Gain ratio استفاده می‌کند. الگوریتم هنگامی متوقف می‌شود که تعداد نمونه‌ها کمتر از مقدار مشخص‌شده‌ای باشد. این الگوریتم از تکنیک پس هرس استفاده می‌کند و همانند الگوریتم قبلی داده‌های عددی را نیز می‌پذیرد.

از نقاطِ ضعف الگوریتم ID3  که در C4.5  رفع شده است می‌توان به موارد زیر اشاره کرد:

الگوریتم C4.5    می‌تواند مقادیر گسسته یا پیوسته را در ویژگی‌ها درک کند و الگوریتم C4.5   قادر است باوجود مقادیر گمشده نیز درخت تصمیم خود را بسازد، درحالی‌که الگوریتمی مانند ID3 و بسیاری دیگر از الگوریتم‌های طبقه‌بندی نمی‌توانند باوجود مقادیر گمشده، مدلِ خود را بسازند. سومین موردی که باعث بهینه شدن الگوریتم  C4.5  نسبت به ID3  می‌شود، عملیاتِ هرس کردن جهت جلوگیری از بیش برازش هست. الگوریتم‌هایی مانند ID3  به خاطر اینکه سعی دارند تا حد امکان شاخه و برگ داشته باشند (تا به نتیجه موردنظر برسند) با احتمال بالاتری دارای پیچیدگی در ساخت مدل و این پیچیدگی در بسیاری از موارد الگوریتم را دچار بیش برازش و خطای بالا می‌کند؛ اما با عملیات هرس کردن درخت که در الگوریتم 5  انجام می‌شود، می‌توان مدل را به یک نقطه بهینه رساند که زیاد پیچیده نباشد (و البته زیاد هم ساده نباشد) و  بیش برازش یا کم برازش Underfitting رخ ندهد. الگوریتم C4.5 این قابلیت را دارد که وزن‌های مختلف و غیر یکسانی را به برخی از ویژگی‌ها بدهد.

الگوریتم CHAID

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

نرم‌افزارهای مورداستفاده برای انجام الگوریتم درخت تصمیم

در حوزه داده‌کاوی، با استفاده از نرم‌افزارهای SPSS Modeler, SAS JMP, Clementine, MATLAB, R, Python, … می‌توانید الگوریتم درخت تصمیم را برای دسته‌بندی نمونه‌های خود استفاده کنید.