درخت تصمیم (Decision Tree) چیست؟ معرفی ساده همراه با مثال کاربردی

درخت‌های دسته‌بندی، داده‌های دسته‌ای (Categorical) و کمّی (Quantitative) را برای مدل کردن خروجی‌های دسته‌ای استفاده می‌کنند. درخت‌های رگرسیون نیز از داده‌های دسته‌ای و کمّی استفاده می‌کنند ولی در عوض خروجی کمّی تولید می‌کنند.

درخت‌های تصمیم با یک گره ریشه (Root Node) آغاز می‌شوند که به‌عنوان نقطه شروع عمل می‌کند (در بالا) و با انشعاب‌هایی که شاخه‌ها (Branch) را می‌سازند، ادامه می‌یابد. اصطلاح آماری/ریاضی برای این شاخه‌ها، یال (Edge) است.

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

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

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

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

آموزش درخت تصمیم

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

در نتیجه هدف، انتخاب یک الگوریتم حریصانه (Greedy) است که سطح آنتروپی در هر لایه از درخت را کاهش بدهد. یکی از الگوریتم‌های حریصانه (ID3) (Iterative Dichotomizer) که توسط جی. آر. کوینلن ابداع شده است. این الگوریتم یکی از سه پیاده‌سازی درخت تصمیم، توسط کوینلن است در نتیجه “3” در انتهای نام الگوریتم آمده است.

در ID3 از آنتروپی برای تشخیص سؤال دودویی مناسب در هر سطح از درخت تصمیم استفاده می‌شود. در هر سطح، ID3 یک متغیر را شناسایی می‌کند (تبدیل شده به یک سؤال دودویی) که کمترین آنتروپی را در سطح بعدی تولید خواهد کرد. مثال زیر به درک بهتر نحوه عملکرد ID3 کمک می‌کند.

متغیر 1 (افزایش شاخص‌های کلیدی عملکرد (Key Performance Indicator)) دوشاخه زیر را ایجاد می‌کند:

• شش کارمند ترفیع داده شده‌اند که KPIهای (شاخص کلیدی عملکرد) آن‌ها بالاتر رفته است (بله)
• چهار کارمند که KPIهای آن‌ها بالا نرفته است و ترفیع نگرفته‌اند (نه)

این متغیر، در لایه بعدی درخت تصمیم، دو گروه همگن می‌سازد.

(سیاه = ترفیع گرفته، سفید = ترفیع نگرفته)

متغیر 2 (توانایی رهبری (Leadership)) موارد زیر را ایجاد می‌کند:

• دو کارمند ترفیع گرفته با توانایی رهبری (بله)
• چهار کارمند ترفیع گرفته بدون توانایی رهبری (نه)
• دو کارمند با توانایی رهبری که ترفیع نگرفته‌اند (بله)
• دو کارمند بدون توانایی رهبری که ترفیع نگرفته‌اند (نه)

این متغیر، دو گروه از نقاط داده غیرهمگن ایجاد می‌کند.

(سیاه = ترفیع گرفته، سفید = ترفیع نگرفته)

متغیر 3 (سن زیر 30 سال) موارد زیر را می‌سازد:

• سه کارمند با سن زیر 30 سال که ترفیع گرفته‌اند (بله)
• سه کارمند با سن بالای 30 سال که ترفیع گرفته‌اند (نه)
• چهار کارمند با سن زیر 30 سال که ترفیع نگرفته‌اند (بله)

این متغیر، یک گروه همگن و یک گروه از نقاط داده غیرهمگن می‌سازد.

(سیاه = ترفیع گرفته، سفید = ترفیع نگرفته)

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

در الگوریتم ID3 و دیگر الگوریتم‌ها، فرایند تقسیم داده به دو قسمت دودویی، تا زمان رسیدن به یک شرط توقف تکرار می‌شود. این نقطه توقف، بر اساس طیفی از شرایط است مثل موارد زیر:

• وقتی که تمام برگ‌ها کمتر از 3-5 مورد داشته باشند.
• زمانی که یک شاخه، نتیجه‌ای تولید می‌کند که تمام موارد را در یک برگ دودویی قرار می‌دهد.

شکل زیر مثالی از شرط توقف را نشان می‌دهد.

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

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

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

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

در ادامه توضیحات درخت تصمیم، درخت تصادفی و Boosting را معرفی می کنیم. در جنگل‌های تصادفی از نمونه‌برداری Bootstrap استفاده می شود که یک الگوریتم نظارتی ضعیف است. Boosting با وزن‌‌دهی به تکرارها، “یادگیرنده‌های ضعیف (Weak Learner)” را به “یادگیرنده‌های قوی (Strong Learner)” تبدیل می‌کنند. در ادامه جزییات این روش‌ها را توضیح می‌دهیم.

الگوریتم جنگل تصادفی چیست؟

در فرایند ساخت درخت‌های تصمیم، هدف پیداکردن بهترین تقسیم‌بندی در هر مرحله است ولی یک روش جایگزین ساخت چندین درخت و ترکیب پیش‌بینی آن‌ها، برای انتخاب مسیر بهینه‌ی دسته‌بندی یا پیش‌بینی است. این کار شامل انتخاب تصادفی سؤالات دودویی برای ساخت چندین درخت تصمیم مختلف که به‌عنوان جنگل‌های تصادفی شناخته می‌شوند، است. معمولاً در صنعت به این فرایند “Bootstrap Aggregating” یا “Bagging” می‌گویند. “Bagging” یک مخفف خلاقانه از “Bootstrap Aggregating” است (شکل زیر).

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

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

همچنین گاهی از Bootstrapping به‌عنوان یک الگوریتم نظارتی ضعیف (Weakly- Supervised) یاد می‌شود چون دسته‌بندها را با استفاده از زیرمجموعه‌های تصادفی ویژگی‌ها و متغیرهای کمتر، آموزش می‌دهد.

مزایا و معایب الگوریتم Boosting

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

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

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

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

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

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

. . . .

و در انتها…

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

در ادامه مجموعه مقالات یادگیری ماشین، در قسمت بعد روش های یادگیری جمعی را توضیح می دهیم.

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