درخت تصمیم چیست؟
درخت تصمیم (Decision Tree) جز الگوریتم های یادگیری ماشین با ناظر محسوب می شود که برای هر دو مساله رگرسیون و طبقه ای مورد استفاده قرار می گیرد. زمانی که درخت برای کارهای طبقه‌بندی استفاده می‌شود، به عنوان درخت طبقه‌بندی شناخته می‌شود و در حوزه رگرسیون به عنوان درخت رگرسیون شناخته می شود.
اجزای درخت تصمیم
هر درخت تصمیم شامل سه گره زیر می باشد:
- برگ (Leaf Nodes): هر گره ای که نتیجه نهایی بعد از تقسیمات متوالی را مشخص می کند. گره نهایی برگ مشخص کننده کلاس داده است.
- ریشه (Root Node): منظور از ریشه، پر اهمیت ترین گره که تقسیمات درخت از این گره شروع می شود.
- شاخه (Branches): هر گره داخلی به تعداد جواب‌های ممکن شاخه بخش بخش می‌شود.
معیار های انتخاب ریشه
در هر مرحله باید گره انشعابی مشخص شود این به معنای انتخاب بهترین گزینه (ویژگی) برای تفکیک داده ها می باشد. سه معیار انتخاب مشخصه شناخته شده عبارتند از:
- Information gain
- Gain ratio
- Gini index
الگوریتم تولید درخت تصمیم:
- در ابتدا کل مجموعه آموزشی به عنوان ریشه در نظر گرفته می شود
- توصیه می شود که پیش پردازش داده ها را انجام دهید اگرچه اجباری نیست
- روش های انتخاب ویژگی های ریشه، شاخه و گره برگ درخت با استفاده از رویکرد آماری انجام می شود.
- برای ساختن درخت، اولین عامل موثر انتخاب گره ریشه است و مشخص کنید کدام ویژگی را به عنوان گره ریشه در هر سطح انتخاب کنید، برای پیدا کردن آن، آنتروپی، اندیس جینی داریم.
آنتروپی: آنتروپی نشان دهنده عدم قطعیت متغیرهای تصادفی است
بهره اطلاعات IG: بهره اطلاعات مقدار کاهش آنتروپی که به واسطه جداسازی نمونه ها ازطریق این ویژگی را نشان می دهد هدف انتخاب ویژگی با بیشینه IG به عنوان گره می باشد.
اندیس Gini : این نام تابع هزینه (cost function) ای است که برای ارزیابی تفکیک دودویی مجموعه داده از آن استفاده می شود، و با متغیر های هدف قطعی "موفقیت" و "شکست" کار می کند. که مقدار بهینه ان معادل صفر می باشد.
- پس از اینکه با معیارهای نامبرده محاسبات برای تمام ویژگی ها انجام شد با توجه به جدول بالا ویژگی مناسب برای ریشه انتخاب می شود.به عنوان مثال بالاترین بهره اطلاعات یا پایین ترین اندیس جینی، نشان دهنده بهترین گزینه برای انتخاب یک ویژگی به عنوان گره ریشه است
- پس از انتخاب گره ریشه، مجموعه داده دوباره تقسیم می شود و محاسبات مجدد انجام شده تا ویژگی که به عنوان گره شاخه مناسب است هم مشخص شود و این روند را تکرار کنید تا زمانی که امکان تقسیم بیشتر وجود نداشته باشد.
- در نهایت، گره برگ برای مساله طبقه بندی معادل برچسب کلاس ها و برای مساله رگرسیون معادل میانگین مقادیر است را به عنوان خروجی می دهد.
شاخص جینی وقتی زمان محاسبات مد نظر است از سایر معیار ها سریع تر می باشد.
الگوریتم های ساخت درخت تصمیم
محبوب ترین الگوریتم ها برای ساخت درخت های تصمیم ID3، C5.0 و CART هستند که از معیار های ارزیابی متفاتی بهره می برند در جدول زیر می توانید چندین الگورتیم معرفی شده برای ساخت درخت تصمیم را ببینید و با هم مقایسه کنید.
جلوگیری از overfitting درخت تصمیم
کاهی در روند ساخت درخت تصمیم با شاخه های بیشماری مواجه می شویم که منجر به بیش برازش درخت تصمیم می شود برای از بین بردن این مش از مفهوم هرس درخت به معنای حذف شاخه های اضافه بهره می بریم . به طور کلی دو تکنیک هرس درخت وجود دارد :
- هرس قبل ساخت درخت : برای انجام پیش هرس می توانیم از پارامترهای min نمونه، حداکثر عمق، حداقل برگ و غیره در حین ساخت خود مدل استفاده کنیم.
- هرس بعد ساخت درخت : اول درخت را ساخته و پس از آن می توان شاخه های اضافی را حذف کرد.
برای حل مشکل Overfitting می توانیم به سراغ تکنیک های Ensemble برویم. تکنیکی است که از چندین الگوریتم برای افزایش عملکرد مدل استفاده می کند.
مزایا و معایب درخت تصمیم
در میان ابزارهای پشتیبانی تصمیم، درخت تصمیم و دیاگرام تصمیم دارای مزایای زیر هستند:
- فهم ساده و قابلیت تفسیر پذیری درخت تصمیم
- کار کردن با داده‌های بزرگ و پیچیده
- استفاده مجدد آسان بعد از ساخت یک درخت تصمیم برای داده های تست
- قابلیت ترکیب با روش‌های دیگر و تقویت تصمیم گیری
در مورد معایب این الگوریتم می توان به موراد زیر اشاره نمود:
- هزینه محاسباتی درخت‌های تصمیم به صورت نمایی با بزرگ شدن مسئله بزرگ می‌شوند.
- اکثر درخت‌های تصمیم تنها از یک ویژگی برای شاخه زدن در گره‌ها استفاده می‌کنند در صورتی که ممکن است ویژگی‌ها دارای توزیع توأم باشند.
- برای داده های پیوسته عملکرد مناسبی نخواهد داشت.
- هزینه هرس بالایی دارد.
- ساخت درخت تصمیم در برنامه‌های داده کاوی حافظه زیادی لازم دارد چون برای هر گره باید معیار کارایی برای ویژگی‌های مختلف ذخیره شده و انتخاب بهترین ویژگی بر اساس آن انجام شودرا انتخاب کند.
درخت تصمیم در متلب
برای دسته بندی داده در متلب می توانید از تابع 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');
به عنوان نتیجه می توانید گراف از ریشه تا برگ های درخت تصمیم را به صورت زیر ببینید :
