درخت تصمیم: وقتی ماشین مانند انسان تصمیم‌گیری می‌کند قسمت اول

مقدمه

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

درخت تصمیم یک تکنیک محبوب و کاملا مفید است که هم در مسائل رگرسیونی و هم در مسائل دسته‌بندی قابل استفاده است. در پست‌های قبلی در مورد مسائل رگرسیونی صحبت کردیم اما منظورمان از مسائل دسته‌بندی چیست؟ 

هرگاه متغیر پاسخی که به دنبال پیش‌بینی آن هستیم، از جنس گسسته باشد می‌گوییم که با یک مساله‌ی دسته‌بندی مواجه هستیم. به طور مثال فرض کنید که می‌خواهیم مدلی داشته باشیم که از روی تصویر تشخیص دهد که تصویر ورودی مربوط به یک مرغ است یا یک خروس. اینجا متغیر پاسخی که مدل باید آن را یاد بگیرد گسسته است و تنها دو مقدار «مرغ» و «خروس» را اختیار می‌کند. یا فرض کنید می‌خواهیم مدلی داشته باشیم که ایمیل‌های اسپم و مزاحم را از ایمیل‌های معتبر و مفید جدا کند. اینجا نیز به طور مشابه متغیر پاسخ تنها دو مقدار می‌گیرد. به چنین مسائلی که متغیر پاسخ تنها دو مقدار را اختیار می‌کند، مسائل دسته‌بندی دودویی می‌گوییم اما تعداد کلاس‌ها (مقادیر متنوع متغیر پاسخ) می‌تواند بیشتر از دو باشد؛ مثلا مدلی را در نظر بگیرید که قرار است دستخط 10 نفر را از همدیگر تشخیص و یا مدلی که باید ارقام 0 تا 9 را براساس تصویر ورودی از همدیگر تشخیص دهد. 

مسائل دسته‌بندی جزو مسائل مهم و بسیار پرکاربرد دنیای واقعی هستند و در پست‌های مجزا به الگوریتم‌های مفید این حوزه خواهیم پرداخت. 

یکی از مزیت‌های الگوریتم درخت تصمیم، تفسیرپذیری مناسب آن است. همان‌طور که در شکل 1 مشاهده می‌کنید، می‌توانیم به صورت بصری نحوه‌ی تصمیم‌گیری مدل را درک کنیم و توضیح دهیم. این موضوع مخصوصا در محیط کار که کارفرمایان معمولا به سختی حاضرند چشم‌بسته به توصیه‌ی دیگران عمل کنند بسیار کارآمد است زیرا می‌توانید نحوه‌ی تفکر و تصمیم‌گیری مدل را به سادگی برای کارفرمای خود توضیح دهید تا اعتماد او به کارایی مدل جلب شود.

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

        شکل 1: نمونه‌ای از یک درخت تصمیم

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

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

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

1. درخت تصمیم چیست: گره ریشه، گره‌های فرعی، گره پایانی(برگ) 
2. معیارهای تقسیم: آنتروپی، شاخص جینی، معیار کسب اطلاعات
3. چگونگی تقسیم گره‌های فرعی 
4. بررسی دلایل ایجاد بیش‌برازش مدل و راه‌های جلوگیری از آن
5. چگونگی پیش‌بینی با استفاده از مدل درخت تصمیم 

پس بیایید به این سوال‌ها پاسخ بدهیم.

درخت تصمیم چگونه کار می‌کند؟

 ابتدا با یک مثال شروع می‌کنیم. می‌خواهیم ابتلای شخص به دیابت را بر اساس متغیرهای پیش‌بینی‌کننده‌ی مستقل مختلف مانند قند خون ناشتا، BMI ،BP  و غیره، تشخیص دهیم.

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

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

به عنوان مثال اگر متغیر پاسخ، دودویی و با دسته‌های 0 و 1 باشد که در شکل 2 با نقاط قرمز و سبز نشان داده شده‌ است، درخت تصمیم برای تقسیم فضای متغیرهای مستقل به نحوی عمل می‌کند که نمونه‌های موجود به زیرگروه‌هایی تقسیم شوند که از نظر مقدار متغیر پاسخ همگن‌تر هستند؛ یعنی نمونه‌های قرمز در یک زیرگروه و نمونه‌های سبز در یک زیرگروه دیگر قرار بگیرند.

در شکل 2 مثالی از تقسیم نمونه‌ها با هدف تشکیل گره‌هایی همگن از نظر متغیر هدف را مشاهده می‌کنید.

     شکل 2: تقسیم نمونه‌های آموزشی با هدف ایجاد گره‌هایی همگن از نظر متغیر هدف

شکل 2 ساختار کلی مدل درخت تصمیم را نشان می‌دهد. حال بیایید با درک عناصر مختلف درخت تصمیم کار را ادامه دهیم.

اجزای یک درخت تصمیم

 درخت تصمیم یک نمودار از انشعابات متوالی یا یک نمودار درختی است که از اجزای زیر تشکیل شده است:

• متغیر هدف: مانند دیابتی یا غیردیابتی بودن افراد و نحوه‌ی توزیع آن در نمونه‌های آموزشی.
• گره ریشه: گره‌ای است که مدل، فرآیند تقسیم را از آنجا آغاز کرده و متغیر مستقلی را می‌یابد که می‌تواند متغیر هدف را به بهترین نحو تقسیم کند.
• خلوص یک گره: گره‌های تصمیم معمولاً از نظر متغیر پاسخ، ناخالص هستند یعنی مخلوطی از هر دو کلاس متغیر هدف(0 و 1 یا نقاط سبز و قرمز در شکل 2) هستند. 

گره‌های خالص آنهایی هستند که فقط نمونه‌هایی از یک کلاس دارند. مانند زیرگروه‌هایی که در شکل 2 فقط دارای نقاط سبز یا قرمز هستند.

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

می‌توانید در شکل 3 این اجزا را به صورت بصری مشاهده کنید.

شکل 3: اجزای یک درخت تصمیم

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

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

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

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

یک متغیر عددی می تواند چندین بار در داده ها با برش‌ها یا آستانه‌های متفاوت ظاهر شود. مقادیر آستانه‌ای را ما و براساس تجربه و دانشی که از ساختار مجموعه داده داریم مشخص می‌کنیم. مقادیر آستانه‌ای باید به نحوی انتخاب شوند که یک افراز مناسب و مفید روی متغیر ایجاد کنند.

موارد مهمی که از دیدگاه علم داده در مدل درخت تصمیم باید مورد توجه قرار بگیرند عبارتند از:

1. نحوه‌ی جریان اطلاعات در درخت تصمیم

2. چگونگی انتخاب متغیر معیار در گره‌های تصمیم درخت تصمیم

3. چگونگی تعیین اندازه‌ی درخت و زمان مناسب توقف رشد درخت تصمیم

مثال

فرض کنید ما مجموعه داده‌ای از 15 دانشجو در مورد قبولی یا عدم موفقیت آن‌ها در امتحان آنلاین یادگیری ماشین داریم. مجموعه داده شامل یک متغیر پاسخ است که دودویی است (Pass/Fail) و متغیرهای مستقل دودویی یا چندسطحی(چندکلاسه) مختلفی مانند موارد زیر در مجموعه داده موجود است:

• آیا دانشجو در دوره‌های آنلاین دیگری نیز ثبت‌نام کرده است؟ 
• آیا دانشجو از رشته‌ی ریاضیات، علوم کامپیوتر یا سایر زمینه‌ها است؟ 
• آیا دانشجو شاغل است یا خیر؟

مجموعه داده را در شکل 4 می‌توانید مشاهده کنید.

توجه داشته باشید که تنها متغیر «پیشینه‌ی دانشجو» بیش از دو سطح یا رده دارد. همان‌طور که می‌دانید در هنگام کار با متغیرهای گسسته معمولا آن‌ها را کدگذاری کرده و متغیرهای مجازی جدیدی را براساس آن‌‌ها می‌سازیم؛ مثلا ممکن در متغیر جنسیت، «مرد» را با 1 و «زن» را با 0 نشان بدهیم. یکی از مزایای درخت‌های تصمیم در مقایسه با سایر مدل‌های دسته‌بندی مانند رگرسیون لجستیک یا ماشین بردار پشتیبان این است که برای استفاده از متغیرهای گسسته نیازی به ساخت متغیرهای مجازی نداریم و می‌توانیم به طور مستقیم از خود آن‌ها در مدل استفاده کنیم.

شکل 4: مجموعه داده‌ی قبولی دانشجویان در آزمون یادگیری ماشین

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

جریان اطلاعات در درخت تصمیم 

درخت تصمیم با متغیر پاسخ شروع می‌شود. این معمولاً گره والد نامیده می‌شود. سپس درخت تصمیم دنباله‌ای از تقسیم‌ها را بر اساس ترتیب سلسله مراتبی تأثیر بر متغیر هدف ایجاد می‌کند. 

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

برای شناسایی گره ریشه، تأثیر همه‌ی متغیرهای مستقل را بر روی متغیر پاسخ می‌سنجیم تا متغیری را که کلاس‌های قبولی و شکست در امتحان را به همگن‌ترین گروه‌ها تقسیم می‌کند، شناسایی کنیم. نامزدهای ما برای تقسیم این عبارتند از: پیش‌زمینه‌ی تحصیلی دانشجویان، وضعیت اشتغال، و وضعیت شرکت در سایر دوره‌های آنلاین.

می‌خواهیم با ایجاد ین انشعاب‌ها به چه چیزی برسیم؟ فرض کنید با وضعیت اشتغال به عنوان گره ریشه شروع می‌کنیم. بنابراین نمونه‌ها به دو گره فرعی تقسیم می‌شوند که یکی برای شاغلین است و دیگری برای غیرشاغلان. سپس وضعیت موفقیت و شکست نمونه‌ها در امتحان مانند شکل 5 در هر گره فرعی به‌روزرسانی می‌شود.

شکل 5: تقسیم دانشجویان براساس وضعیت اشتغال

این ساختار اصلی مدل درخت تصمیم است. تا زمانی که ترکیبی از موفقیت و شکست در یک گره فرعی وجود دارد، امکان تقسیم بیشتر آن وجود دارد. می‌توانیم این فرایند را تا جایی ادامه دهیم که به گره‌هایی برسیم که تمام نمونه‌هایشان از یک کلاس هستند. این همان خلوص گره است که پیشتر در رابطه با آن صحبت کردیم. به عنوان مثال، گره غیرشاغلان دارای 5 موفقیت و 1 شکست است؛ بنابراین از گره شاغلان که دارای 5 موفقیت و 4 شکست است، خالص‌تر است. یک گره برگ، گرهی است که فقط (حتی‌الامکان) شامل کلاس موفقیت یا شکست باشد.

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

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

سوال کلیدی:

درخت چگونه تصمیم می‌گیرد که کدام متغیر در هر سطح برای ایجاد انشعاب مناسب است؟

رویکرد حریصانه‌ی بالا به پایین

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

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

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

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

معیار انتخاب متغیر در افرازبندی 

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

1. آنتروپی و معیار کسب اطلاعات
2. شاخص جینی

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

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

بیایید با معیار آنتروپی و معیار کسب اطلاعات شروع کنیم.

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

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

در نظریه‌ی اطلاعات، آنتروپی یک متغیر تصادفی، میانگین سطح «اطلاعات»، «غافل‌گیری» یا «عدم قطعیتی» است که ممکن است در برآمدهای احتمالی متغیر تصادفی مشاهده کنیم.

در زمینه‌ی درخت تصمیم، آنتروپی معیاری از بی‌نظمی یا ناخالصی در یک گره است. بنابراین یک گره با تنوع متغیر پاسخ بیشتر، مانند 2 موفقیت و 2 شکست، دارای سطح آنتروپی بالاتری نسبت به گرهی است که فقط موفقیت یا فقط شکست دارد. حداکثر سطح آنتروپی یا بی‌نظمی با 1 و حداقل آنتروپی با مقدار 0 بیان می‌شود.

گره‌های برگی که همه نمونه‌های متعلق به آن‌ها از لحاظ متغیر پاسخ در یک کلاس قرار دارند، دارای آنتروپی 0 خواهند بود؛ در حالی که آنتروپی برای گره‌ای که در آن کلاس‌های متغیر پاسخ به طور مساوی تقسیم شده‌اند، برابر 1 خواهد بود.

آنتروپی با فرمول زیر اندازه‌گیری می‌شود:

در رابطه‌ی بالا  احتمال انتخاب یک نمونه از کلاس در مجموعه داده‌ی آموزشی است. بیایید این رابطه را در چارچوب مثال خود کمی بهتر درک کنیم.  

در مثال ما آنتروپی اولیه در گره والد براساس احتمال مشاهده‌ی یک موفقیت در مقابل یک شکست محاسبه می‌شود. در مجموعه داده‌ی ما، متغیر پاسخ دارای 9 موفقیت و 6 شکست است. بنابراین احتمالات برای فرمول آنتروپی عبارتند از:

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

Entropy_parent آنتروپی گره والد است و Entropy_children میانگین آنتروپی گره‌های فرزند را نشان می‌دهد که از این گره پیروی می‌کنند. در حالت فعلی از آنجایی که در مثال ما 3 متغیر وجود دارد (وضعیت اشتغال، وضعیت شرکت در دوره‌های آنلاین، و زمینه‌ی تحصیلی دانشجو)، در تقسیم‌بندی‌ها باید هر 3 متغیر مورد توجه قرار بگیرند.

برای محاسبه‌ی آنتروپی، ابتدا بیایید فرمول‌های آنتروپی و کسب اطلاعات را بر حسب متغیرهای موجود در مجموعه داده‌ی خودمان بازنویسی کنیم:

• احتمال موفقیت و شکست در هر گره، یعنی :

• آنتروپی

• متوسط آنتروپی در گره‌های فرزند

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

• معیار کسب اطلاعات

محاسبات گره والد

ابتدا آنتروپی گره والد را با استفاده از فرمول بالا محاسبه می‌کنیم. در مثال ما محاسبات به صورت زیر است:

)نکته‌ی ریاضی: وقتی عدد کم‌تر از 1 را به عنوان ورودی به لگاریتم با پایه‌ی 2 می‌دهیم، خروجی منفی خواهد بود، بنابراین خروجی را در یک علامت منفی ضرب می‌کنیم تا یک عدد مثبت به دست آید.)

    حالا آنتروپی گره والد را به دست آورده‌ایم. اکنون باید تصمیم بگیریم که از کدام ویژگی یا متغیر برای افراز کردن آن برای به دست آوردن گره ریشه استفاده کنیم.

محاسبات گره ریشه

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

    بیایید با متغیر وضعیت کار شروع کنیم و آنتروپی تقسیم را محاسبه کنیم.

    سپس آنتروپی متوسط ​​را برای تقسیم وضعیت اشتغال به عنوان یک میانگین وزنی با وزن‌های سهم مشاهدات از تعداد کل مشاهداتی که در هر گره فرعی قرار می‌گیرند محاسبه می‌کنیم.

پس معیار کسب اطلاعات به صورت زیر خواهد بود:

به طور مشابه، می‌توانیم آنتروپی و معیار کسب اطلاعات را بر اساس متغیرهای زمینه‌ی تحصیلات دانشجو و وضعیت شرکت درر دوره‌های آنلاین محاسبه کنیم. نتایج در جدول زیر ارائه شده است:

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

بنابراین بر اساس محاسبات فوق، ما تعیین کرده‌ایم که گره ریشه به چه صورت خواهد بود. درخت اکنون به صورت شکل 6 است:

شکل 6: ریشه‌ی درخت تصمیم

زمینه‌ی تحصیلی دانشجو متغیر هدف را به 3 گروه تقسیم می‌کند. همه افراد از پس زمینه علوم کامپیوتر در امتحان موفق شده‌اند از این رو به یک گره برگ خالص می‌رسیم. همه افراد از زمینه‌های مطالعاتی متفرقه شکست می‌خورند پس این نیز یک گره برگ خالص است. زمینه‌ی ریاضی به 3 موفقیت و 4 شکست تقسیم می‌شود و از این رو هنوز ناخالص است و همچنان امکان تقسیم بیشتر برای دستیابی به خلوص بیشتر وجود دارد.

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

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

توجه: محاسبه‌ی log(0) ایجاد خطا می‌کند. با این حال از نظر ریاضی می‌توانیم از حد آن استفاده کنیم. به طور معمول ما مورد  را در محاسبات لحاظ نمی‌کنیم زیرا حد حاصل‌ضرب احتمال 0 در لگاریتم 0 برابر 0 خواهد بود. با این حال، ما برای نشان دادن محاسبات کامل، آن را نیز ذکر کرده‌ایم.

همانطور که در جدول مشاهده می‌کنید معیار کسب اطلاعات برای متغیر وضعیت اشتغال بالاتر است. بنابراین این متغیری است که برای ادامه‌ی ایجاد انشعاب مورد استفاده قرار می‌گیرد.        

شکل 7: انشعاب گره دانشجویان با سابقع‌ی تحصیلی ریاضی

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

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

اکثر پیاده‌سازی‌‌های درخت تصمیم در نرم‌افزار‌ها دارای معیار توقف‌هایی هستند که در ادامه به آن‌ها خواهیم پرداخت.  

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

منبع

https://towardsdatascience.com/decision-trees-explained-entropy-information-gain-gini-index-ccp-pruning-4d78070db36c