درخت تصمیم چیست؟

درخت تصمیم (Decision Tree) جز الگوریتم های یادگیری ماشین با ناظر محسوب می شود که برای هر دو مساله رگرسیون و طبقه‌­ ای مورد استفاده قرار می گیرد. زمانی که درخت برای کارهای طبقه‌­بندی استفاده می‌­شود، به عنوان درخت طبقه­‌بندی شناخته می‌­شود و در حوزه رگرسیون به عنوان درخت رگرسیون شناخته می­ شود.

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

هر درخت تصمیم شامل سه گره زیر می باشد:

• برگ (Leaf Nodes): هر گره­ ای که نتیجه نهایی بعد از تقسیمات متوالی را مشخص می کند. گره نهایی برگ مشخص کننده کلاس داده است.
• ریشه (Root Node): منظور از ریشه، پر اهمیت ترین گره که تقسیمات درخت از این گره شروع می شود.
• شاخه (Branches): هر گره داخلی به تعداد جواب‌­های ممکن شاخه بخش بخش می‌­شود.

معیار های انتخاب ریشه

در هر مرحله باید گره انشعابی مشخص شود این به معنای انتخاب بهترین گزینه (ویژگی) برای تفکیک داده ها می باشد. سه معیار انتخاب مشخصه شناخته شده عبارتند از:

• Information gain
• Gain ratio
• Gini index

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

1. آماده‌سازی داده‌ها (پیش‌پردازش):

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

• پاک‌سازی داده‌ها: حذف یا اصلاح داده‌های پرت (Outliers) و مقادیر گمشده.
• نرمال‌سازی یا استانداردسازی: برای مسائل رگرسیون، ممکن است ویژگی‌های عددی نیاز به مقیاس‌بندی داشته باشند (مثلاً با Min-Max Scaling یا Standard Scaling).
• رمزگذاری داده‌های دسته‌ای: برای مسائل طبقه‌بندی، ویژگی‌های دسته‌ای (مانند “بله/خیر”) باید به مقادیر عددی تبدیل شوند (مثلاً با One-Hot Encoding یا Label Encoding).
• انتخاب ویژگی: حذف ویژگی‌های غیرمرتبط یا کم‌اهمیت برای کاهش پیچیدگی.

2. انتخاب گره ریشه:

• در ابتدا، کل مجموعه داده به عنوان گره ریشه در نظر گرفته می‌شود.
• برای انتخاب ویژگی مناسب به عنوان گره ریشه، از معیارهای آماری مانند انتروپی (Entropy)، بهره اطلاعات (Information Gain)، یا اندیس جینی (Gini Index) برای مسائل طبقه‌بندی و واریانس (Variance) برای مسائل رگرسیون استفاده می‌شود.
• این محاسبات برای تمام ویژگی‌ها انجام می‌شود و ویژگی‌ای که بهترین معیار (مثلاً بالاترین بهره اطلاعات یا پایین‌ترین اندیس جینی یا برای مسائل رگرسیون، ویژگی‌ای که بیشترین کاهش را در واریانس داده‌ها ایجاد کند، انتخاب می‌شود.) را داشته باشد، به عنوان گره ریشه انتخاب می‌شود.

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

بهره اطلاعات IG: فاوت انتروپی قبل و بعد از تقسیم داده‌ها بر اساس یک ویژگی. ویژگی با بالاترین بهره اطلاعات (یا پایین‌ترین انتروپی بعد از تقسیم) به عنوان گره ریشه انتخاب می‌شود. هدف انتخاب ویژگی با بیشینه IG به عنوان گره می باشد.

اندیس Gini : این نام تابع هزینه (cost function) ای است که معیاری برای سنجش ناپاکی (Impurity) در داده‌هاست. ویژگی با پایین‌ترین اندیس جینی انتخاب می‌شود.. که مقدار بهینه ان معادل صفر می باشد.

 شاخص جینی وقتی زمان محاسبات مد نظر است از سایر معیار ها سریع تر می باشد.

3. تقسیم داده‌ها و ساخت شاخه‌ها:

• پس از انتخاب گره ریشه، داده‌ها بر اساس مقادیر آن ویژگی به زیرمجموعه‌هایی تقسیم می‌شوند. مثلاً، اگر ویژگی ریشه “سن” باشد، داده‌ها ممکن است به زیرمجموعه‌های “سن < 30” و “سن ≥ 30” تقسیم شوند.
• برای هر زیرمجموعه، فرآیند انتخاب ویژگی (مشابه مرحله قبل) تکرار می‌شود تا ویژگی مناسب برای گره شاخه انتخاب شود. این کار شامل محاسبه مجدد معیارهای آماری (انتروپی، جینی، یا واریانس) برای ویژگی‌های باقی‌مانده است.

4.تکرار فرآیند تا رسیدن به گره‌های برگ:

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

5. تعیین خروجی گره‌های برگ:

• برای مسائل طبقه‌بندی: گره برگ نشان‌دهنده یک برچسب کلاس است. این برچسب معمولاً کلاسی است که بیشترین تعداد نمونه‌ها را در آن گره دارد (رأی‌گیری اکثریت). مثلاً در تشخیص دیابت، گره برگ ممکن است “دیابت دارد” یا “دیابت ندارد” باشد.
• برای مسائل رگرسیون: گره برگ نشان‌دهنده یک مقدار عددی است که معمولاً میانگین (یا میانه) مقادیر نمونه‌های موجود در آن گره است. مثلاً در پیش‌بینی قیمت خانه، گره برگ ممکن است میانگین قیمت خانه‌ها در آن زیرمجموعه باشد.

پیش‌بینی برای داده‌های جدید:

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

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

محبوب ترین الگوریتم ها برای ساخت درخت های تصمیم ID3، C5.0 و CART هستند که از معیار های ارزیابی متفاتی بهره می برند در جدول زیر می توانید چندین الگورتیم معرفی شده برای ساخت درخت تصمیم را ببینید و با هم مقایسه کنید.

جلوگیری از overfitting درخت تصمیم

کاهی در روند ساخت درخت تصمیم با شاخه های بیشماری مواجه می شویم که منجر به بیش برازش درخت تصمیم می شود برای از بین بردن این مش از مفهوم هرس درخت به معنای حذف شاخه های اضافه بهره می بریم . به طور کلی دو تکنیک هرس درخت وجود دارد :

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

برای حل مشکل Overfitting می توانیم به سراغ تکنیک های Ensemble برویم. درخت‌های تصمیم اغلب به عنوان مدل پایه در روش‌های یادگیری گروهی مانند بگینگ (Random Forest) و بوستینگ (XGBoost) استفاده می‌شوند تا معایب آن‌ها (مانند بیش‌برازش و حساسیت به نویز) کاهش یابد.

مثال ساده برای طبقه‌بندی و رگرسیون

• طبقه‌بندی (تشخیص دیابت):
  • فرض کنید داده‌ها شامل ویژگی‌هایی مانند “گلوکز خون”، “BMI” و “سن” هستند.
  • گره ریشه: “گلوکز خون < 140”. داده‌ها به دو زیرمجموعه تقسیم می‌شوند.
  • گره‌های شاخه: برای زیرمجموعه “گلوکز خون < 140″، ویژگی بعدی (مثلاً “BMI < 30”) انتخاب می‌شود.
  • گره برگ: اگر تمام نمونه‌ها در یک گره به “دیابت ندارد” تعلق داشته باشند، برچسب “دیابت ندارد” خروجی است.
• رگرسیون (پیش‌بینی قیمت خانه):
  • فرض کنید داده‌ها شامل ویژگی‌هایی مانند “متراژ”، “تعداد اتاق” و “سن ساختمان” هستند.
  • گره ریشه: “متراژ < 100 متر”. داده‌ها به دو زیرمجموعه تقسیم می‌شوند.
  • گره‌های شاخه: برای زیرمجموعه “متراژ < 100 متر”، ویژگی بعدی (مثلاً “تعداد اتاق < 3”) انتخاب می‌شود.
  • گره برگ: میانگین قیمت خانه‌ها در آن زیرمجموعه (مثلاً 200,000 دلار) به عنوان خروجی ارائه می‌شود.

مزایا و معایب درخت تصمیم

در میان ابزارهای پشتیبانی تصمیم، درخت تصمیم و دیاگرام تصمیم دارای مزایای زیر هستند:

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

در مورد معایب این الگوریتم می توان به موراد زیر اشاره نمود:

• هزینه محاسباتی درخت‌های تصمیم به صورت نمایی با بزرگ شدن مسئله بزرگ می‌شوند.
• اکثر درخت‌های تصمیم تنها از یک ویژگی برای شاخه زدن در گره‌ها استفاده می‌کنند در صورتی که ممکن است ویژگی‌ها دارای توزیع توأم باشند.
• برای داده های پیوسته عملکرد مناسبی نخواهد داشت.
• هزینه هرس بالایی دارد.
• ساخت درخت تصمیم در برنامه‌های داده کاوی حافظه زیادی لازم دارد چون برای هر گره باید معیار کارایی برای ویژگی‌های مختلف ذخیره شده و انتخاب بهترین ویژگی بر اساس آن انجام شودرا انتخاب کند.

درخت تصمیم در متلب

برای دسته بندی داده در متلب می توانید از تابع fitctree استفاده کنید در مثال زیر یک مثال از متلب که کاربرد این تابع را در دسته بندی داده های iris نشان می دهد.

load fisheriris
t = fitctree(meas(:,1:2), species,'PredictorNames',{'SL' 'SW' });
[x,y] = meshgrid(4:.1:8,2:.1:4.5);
x = x(:);
y = y(:);
[grpname,node] = predict(t,[x y]);
view(t,'Mode','graph');

به عنوان نتیجه می توانید گراف از ریشه تا برگ های درخت تصمیم را به صورت زیر ببینید :