موضوع مقاله: یادگیری درخت تصمیم | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # یادگیری درخت تصمیم | مقدمه: درخت‌های تصمیم به گروه الگوریتم‌های یادگیری تحت نظارت تعلق دارند و بیشتر آنها بر اساس حداقل‌سازی کمیتی به نام آنتروپی ساخته می‌شوند. | ## بخش 1: یادگیری درخت تصمیم | نمونه‌های قدیمی درخت تصمیم تنها قادر به استفاده از متغیرهای گسسته بودند، اما الگوریتم‌های جدیدتر هردو نوع متغیر گسسته و پیوسته را در یادگیری به کار می‌برند. یکی از مزایای مهم الگوریتم درخت تصمیم قابلیت فهم و تفسیر آسان است که محبوبیت این الگوریتم را بالا برده‌است. مقدمه یادگیری درخت تصمیم روشی است که به‌طور معمول در داده کاوی از آن استفاده می‌شود. هدف این مدل این است که بتواند مقدار یک متغیر هدف را براساس مقادیر متغیرهای ورودی پیش‌بینی کند. درخت تصمیم یا درخت طبقه‌بندی درختی است که به هر گره داخلی (گره‌ای که برگ نیست) یکی از ویژگی‌های ورودی‌ها برچسب زده شده‌است. یال‌های خارج شده از گره داخلی به یک گره برگ برای دسته‌بندی داده‌ها یا یک گره داخلی برای دسته‌بندی داده‌ها برحسب یک ویژگی دیگر هدایت می‌شوند. درنهایت، هر گره برگ برحسب یکی از مقادیر در دامنه طبقه‌بند برچسب زده می‌شوند و همه داده‌هایی که در آن گره قرار بگیرند، به عنوان عضو آن کلاس پیش‌بینی خواهند شد. روند ایجاد درخت تصمیم از تقسیم کردن مجموعه تمام داده‌های در دسترس (که در واقع ریشه درخت را تشکیل می‌دهند)، به زیر مجموعه‌هایی (که به هر گره فرزند تبدیل می‌شوند) است. شرایط تقسیم کردن داده‌های هر گره به گره‌های فرزند آن براساس یک شرط تقسیم‌بندی در هر گره داخلی خواهد بود. تقسیم کردن هر گره بدست آمده به گره‌های فرزند آن در یک روند بازگشتی انجام خواهد گرفت که به آن تقسیم‌بندی بازگشتی نیز گفته خواهد شد. این تقسیم‌بندی تا زمانی ادامه پیدا خواهد کرد که داده‌های در هر گره برگ متعلق به یک کلاس باشند یا زمانی که دیگر ویژگی‌ای برای تقسیم گردن داده‌های در یک گره وجود نداشته باشد. به این فرایند القای درخت تصمیم از بالا به پایین گفته می‌شود که یک مثال از الگوریتمی حریصانه است. داده‌های در درخت تصمیم به‌طور معمول به شکل زیر هستند: که متغیر مستقل و همان متغیر هدف است و بردار یک بردار بعدی است که شامل مقدار ویژگی‌های است. | ## بخش 2: یادگیری درخت تصمیم | درختان تصمیم علاوه بر دسته‌بندی داده‌ها، همچنین می‌توانند در مسئله رگرسیون نیز استفاده شوند، به این صورت که خروجی درخت تصمیم به جای شماره کلاس داده، یک مقدار عددی پیوسته برای پیش‌بینی کردن مقدار متغیر هدف براساس مقادیر ویژگی داده‌های ورودی باشد. از رایج‌ترین این متریک‌ها می‌توان به آنتروپی (یا افزایش اطلاعات) و شاخص جینی اشاره کرد. ناخالصی جینی شاخص تنوع جینی در الگوریتم CART (درخت طبقه‌بندی و رگرسیون) برای ایجاد درخت تصمیم استفاده می‌شود. ناخالصی جینی (نام‌گذاری شده بعد از ریاضی‌دان ایتالیایی کورادو جینی) اندازه‌گیری می‌کند که با چه احتمالی یک عنصر از یک مجموعه می‌تواند به اشتباه برچسب‌گذاری (دسته‌بندی) شود اگر که دسته‌بندی عناصر در مجموعه به‌طور تصادفی براساس یک توزیع احتمال انجام شده باشد. ناخالصی جینی را می‌توان با جمع کردن احتمال‌های برای یک عنصر که برچسب برای آن انتخاب شده در احتمال دسته‌بندی اشتباه آن که برابر است با کمترین مقدار ممکن برای این متریک برابر صفر است که در این حالت تمام المان‌های در یک مجموعه به یک کلاس تعلق دارند. برای اینکه مقدار ناخالصی جینی را برای یک مجموعه از المان‌ها با کلاس که که و نسبتی از داده‌ها باشد که با برچسب i در این مجموعه برچسب زده شده‌اند: افزایش اطلاعات افزایش اطلاعات یکی از متریک‌های یادگیری درخت تصمیم است که بر اساس آنتروپی بوده و به شکل زیر فرموله می‌شود: که در آن کسرهایی هستند که مجموعشان برابر با ۱ است و نشانگر درصدهای هر کلاس در گره فرزند پس از تقسیم هستند. بدین ترتیب افزایش اطلاعات حاصل در سیستم از تقسیم یک گره به صورت تفریق آنتروپی سیستم پیش و پس از تقسیم (یعنی آنتروپی والد منهای آنتروپی فرزند) به شکل زیر محاسبه می‌شود: یادگیری درخت یادگیری درخت به این شکلست که ابتدا متغیری که بیشترین تغییر در آنتروپی را ایجاد می‌کند (یا بیشترین افزایش اطلاعات را دارد) انتخاب می‌شود و مجموعه داده بر اساس این متغیر تقسیم می‌شود. سپس همین عمل برای هرکدام از زیرمجموعه‌های ایجاد شده تکرار می‌شود و تا جایی ادامه پیدا می‌کند که زیرمجموعه‌های بدست آمده از حداقلی از خلوص برخوردار باشند. بنابراین ترتیب متغیرها در ساختار یک درخت تصمیم نشانگر میزان اطلاعات نهفته در آنهاست. درختان همچنین می‌توانند به صورت گرافیکی به گونه ای نمایش داده شوند که تفسیر آنها برای افراد غیر متخصص آسان باشد. سایر تکنیک‌ها معمولاً در تجزیه و تحلیل مجموعه داده‌هایی که فقط یک نوع متغیر دارند، تخصصی می‌شوند. (به عنوان مثال، قوانین رابطه را می‌توان فقط با متغیرهای اسمی استفاده کرد، در حالی که شبکه‌های عصبی را می‌توان فقط با متغیرهای عددی یا مقوله‌هایی که به مقادیر ۰–۱ تبدیل شده‌اند استفاده کرد) درختان تصمیم اولیه فقط قادر به مدیریت متغیرهای طبقه‌بندی بودند، اما نسخه‌های جدیدتر، مانند به عنوان C4.5، این محدودیت را ندارند. از آنجایی که درختان می‌توانند پیش‌بینی کننده‌های کیفی را اداره کنند، نیازی به ایجاد متغیرهای ساختگی نیست. | ## بخش 3: یادگیری درخت تصمیم | اگر یک موقعیت معین در یک مدل قابل مشاهده باشد، توضیح این شرط به راحتی با منطق بولی توضیح داده می‌شود. در مقابل، در مدل جعبه سیاه، توضیح نتایج معمولاً به سختی قابل درک است، برای مثال با یک شبکه عصبی مصنوعی. رویکرد ناپارامتریک که هیچ فرضی در مورد داده‌های آموزشی یا باقیمانده‌های پیش‌بینی نمی‌کند. از ویژگی‌های نامربوط اضافی کمتر استفاده می‌شود تا بتوان آنها را در اجراهای بعدی حذف کرد. یک تغییر کوچک در داده‌های آموزشی می‌تواند منجر به تغییر بزرگ در درخت و در نتیجه پیش‌بینی‌های نهایی شود. مشکل یادگیری یک درخت تصمیم بهینه به عنوان ان‌پی کامل تحت چندین جنبه از بهینه بودن و حتی برای مفاهیم ساده شناخته شده‌است. در نتیجه، الگوریتم‌های یادگیری درخت تصمیم عملی مبتنی بر اکتشافی مانند الگوریتم حریصانه هستند که در آن تصمیمات بهینه محلی در هر گره گرفته می‌شود. چنین الگوریتم‌هایی نمی‌توانند تضمین کنند که درخت تصمیم‌گیری بهینه سراسری را بازگرداند. برای کاهش اثر حریصانه بهینه‌سازی محلی، روش‌هایی مانند درخت فاصله اطلاعات دوگانه پیشنهاد شد. یادگیرندگان درخت تصمیم می‌توانند درختان بیش از حد پیچیده ایجاد کنند که به خوبی از داده‌های آموزشی تعمیم نمی‌یابد. (این به عنوان بیش‌برازش شناخته می‌شود) مکانیسم‌هایی مانند هرس برای جلوگیری از این مشکل ضروری است (به استثنای برخی از الگوریتم‌ها مانند رویکرد استنتاج شرطی که نیازی به هرس ندارد). | ## جمع‌بندی | عمق متوسط درخت که با تعداد گره‌ها یا آزمایش‌ها تا زمان طبقه‌بندی تعریف می‌شود، تحت معیارهای مختلف تقسیم تضمین نمی‌شود که حداقل یا کوچک باشد.