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

اصطلاحات و واژگان مرتبط با درخت تصمیم:

ریشه (Root Node):

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

تقسیم‌‌بندی (Splitting) :

فرآیند تقسیم گره‌‌ها به دو یا بیشتر زیرگره‌‌ را گویند.

گره تصمیم(Decision Node) :

زمانی‌‌که یک گره به زیرگره تقسیم می‌‌شود، به آن زیرگره ایجاد شده گره تصمیم گویند.

برگ/ گره نهایی(Leaf/ Terminal Node) :

گره‌‌هایی که دیگر تقسیم به زیرگره نمی‌‌شوند را گره نهایی یا برگ گویند.

هرس‌‌کردن(Pruning) :

زمانی‌‌که زیرگره‌‌های یک گره تصمیم را حذف می‌‌کنیم، اصطلاحا درخت را هرس کرده‌‌ایم.

شاخه/ زیردرخت(Branch):

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

گره والد و گره فرزند(Parent and Child Node) :

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

عملکرد الگوریتم درخت تصمیم:

  1. درخت با استفاده از کل داده‌‌های دیتاست ایجاد می‌‌شود.
  2. بهترین ویژگی با استفاده از یکی از معیارهای انتخاب ویژگی (Attribute Selection Measure-ASM)  انتخاب می‌‌شود.
  3. سپس داده‌‌ها با استفاده از ویژگی انتخاب شده در مرحله‌‌ی قبل تقسیم می‌‌شوند. (بهترین ویژگی)
  4. گره تصمیم ساخته می‌‌شود.
  5. مراحل 3 تا 5 تکرار می‌‌شود. و تاجایی ادامه می‌‌یابد که به شروط توقف برسد.

شروط توقف:

  • همه‌‌ی داده‌‌ها به یک کلاس تعلق دارند.
  • ویژگی دیگری در دیتاست وجود نداشته باشد که نیاز به بررسی داشته باشد. ( زمانی رخ می‌‌دهد که ویژگی‌‌هایمان کافی نیست)
  • داده‌‌ی دیگری وجود نداشته باشد و همه‌‌ی داده‌‌ها چک شده باشد.

انواع روش‌‌های انتخاب ویژگی‌‌ها:

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

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

بهره اطلاعاتی(Information Gain) :

این معیار به مفهومی به نام آنتروپی اطلاعات وابسته است. به همین منظور ابتدا به توضیح مفهوم آنتروپی می‌‌پردازیم.

آنتروپی/ عدم قطعیت (Entropy):

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

که در آن p احتمال رخداد iام است. فرض کنید مجموعه‌‌ای دارید مثل پرتاب سکه سالم (S) که متغیر تصادفی دارد. و دو بار سکه را پرتاب می‌‌نمایید. در آن احتمال شیر یا خط آمدن سکه ½  است.

برمی‌‌گردیم به بحث بهره اطلاعاتی، همان‌‌طور که پیش‌‌تر اشاره شد، انتخاب ویژگی صحیح در زمان ساخت درخت تصمیم بسیار در صحت نتیجه و کارایی درخت تصمیم تاثیرگذار است. لذا معیار بهره اطلاعاتی به دنبال کاهش آنتروپی است. بهره اطلاعاتی اختلاف آنتروپی قبل از تقسیم گره و آنتروپی بعد از تقسیم گره را بر اساس ویژگی خاص(X)  محاسبه می‌‌کند. فرمول آن به صورت زیر است که در آن S معرف مجموعه داده‌‌هاست:

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

ضریب بهره (Gain Ratio):

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

شاخص جینی(Gini Index) :

این شاخص تقریبا شبیه شاخص بهره اطلاعاتی است با این تفاوت که در اینجا به جای آنتروپی از معیار جینی(Gini)  استفاده می‌‌شود.  که در آن مجموعه D شامل نمونه‌‌هایی از 1 تا m کلاس مختلف است.

ویژگی با شاخص جینی کمتر، بر ویژگی با شاخص جینی بیشتر ارجح می‌‌باشد.

انواع درخت تصمیم:

درخت طبقه‌‌بندی (بله/خیر)

درخت رگرسیون ( انواع داده‌‌ی پیوسته)

هرس:

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

هرس کردن به دو روش pre-pruning و post-pruning صورت می‌‌گیرد.

هرس قبل- پیش‌‌هرس (Pre-pruning) :

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

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

 یا به عنوان مثالی دیگر، در زمان ساخت درخت، شرطی را اضافه می‌‌نماییم که رشد درخت را محدود نماید هم‌‌چون شرط توقف رشد درخت، زمانی‌‌که به عمق 6 رسید. و یا از گره‌‌ای با Information Gain کمتر از عددی که تعیین نموده‌‌ایم درخت رشد نکند.

هرس بعد (Post-pruning):

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

روش‌‌های جلوگیری از بیش‌‌پردازش:

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

  • حداکثر عمق(Max_depth) :

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

  • محدودسازی انشعاب(Min_Sample_split) :

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

مزایا:

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

معایب:

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

برنامه‌‌ها و سیستم‌‌هایی که از درخت تصمیم استفاده می‌‌کنند:

سیستم آنالیز مالی (رضایت مشتری از محصول یا سرویس ارائه شده)

سیستم ستاره شناسی (دسته‌‌بندی کهکشان‌‌ها)

دارو ( تشخیص، درمان روان‌‌پزشکی)

فیزیک ( تشخیص ذرات) و…