الگوریتم طبقه بند درخت تصمیم CART

مدرس: مسعود کاویانی

یکی از محبوب‌ترین و در عین حال ساده‌ترین الگوریتم‌های درخت‌های تصمیم، درخت تصمیمِ CART است که کاربردهای زیادی در طبقه‌بندی و رگرسیون دارد. CART که خود مخفف Classification and Regression Tree است بر اساس درخت های دودویی (باینری) بنا نهاده شده است. در این درس می‌خواهیم بیشتر با نحوه‌ی ساختِ درختِ CART آشنا شویم. این درخت (و البته درخت‌های دیگر) می‌تواند پایه‌ای برای الگوریتم‌های پیچیده‌تر مانند جنگلِ تصادفی (Random Forest) باشد.

الگوریتمِ درختِ تصمیمِ CART برای ساختِ درختِ تصمیم، داده‌ها را به قسمت‌های دو‌تایی تقسیم کرده و بر اساس آن‌ها درخت دو‌دویی (باینری) را می‌سازد. اجازه دهید با همان مثال سگ و گربه یک درختِ تصمیمِ CART ایجاد کنیم. فرض کنید تعدادی حیوان داریم (سگ و گربه) که هر کدام دو ویژگیِ طولِ حیوان و ارتفاعِ حیوان را دارند. بر اساس این دو ویژگی می‌خواهیم سگ‌ها و گربه‌ها را از هم دیگر جدا کنیم. ۱۶ حیوان داریم که هر کدام ۲ویژگی دارند. اگر بخواهیم این نمونه‌ها را بر روی محور مختصات نمایش دهیم به صورت زیر است (مثالی که در درس شبکه عصبی MLP در مورد آن بحث کردیم):

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

الگوریتمِ CART به این صورت عمل می‌کند: در تصویر بالا مشاهده می‌کنید که داده‌ها را به دو قسمت تصمیم کردیم. این کار با یک خط آبی در محورِ طول حیوان انجام شده است و حیوانات را به دو قسمت (که طول آن ها بزرگتر یا کوچکتر از  X1) است تقسیم می‌کنیم. حال با این کار یک درخت دودویی ایجاد می شود. مانند تصویر زیر:

درخت تصمیم

این درختِ دودویی که بر اساس خط X1 کشیده شده است دو قسمت دارد. اگر طول حیوان بزرگتر از X1 بود، سمت راست X1 مورد نظر است که در آن قسمت ۶ سگ و ۴ گربه داریم. اگر طولِ حیوان کوچکتر از X1 بود سمت چپ این خط مورد نظر است که ۳ سگ و ۳ گربه داریم. حال می‌توان هر کدام از این دو قسمت را نیز، به قسمت های کوچکتری تقسیم کرد:

الگوریتم CART

همان طور که می‌بینید، قسمت سمت چپ خط X1 را با یک خطِ دیگر جدا کردیم. این خط که همان خط Y1 است توانست گربه‌ها و سگ‌ها را در قسمت سمت چپِ X1 از همدیگر جدا کند. درخت CART مناسب تا به اینجا به این صورت است:

درخت تصمیم cart

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

داده‌کاوی درخت تصمیم

و در آخر خطی مانند زیر می‌تواند طبقه‌بند را با دقت بالایی مدل‌سازی کند:

داده‌کاوی درخت تصمیم کارت

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

درختِ تصمیمِ CART برای اینکه تصمیم بگیرد چگونه گره‌های درخت را انتخاب کند از معیاری به نام معیار شاخص جینی (gini) استفاده می‌کند. همان طور که درخت های ID3 و C4.5 از entropy و gain استفاده می‌کرند. در واقع برای اینکه درخت CART تشخیص دهد که کدام ویژگی‌ها می‌تواند اطلاعات بیشتری را ارائه دهد از شاخص جینی استفاده کرده و برای هر ویژگی (بُعد) هر چقدر شاخص جینی کمتر باشد، یعنی آن ویژگی اطلاعات بیشتری را به ما می.دهد. (مثال ID3 را نگاه کنید). هر چقدر یک ویژگی (بُعد) شاخصِ جینی کمتری داشته باشد آن ویژگی اطلاعات بیشتری را دارد و می‌تواند در درخت ساخته شده، بالاتر (یعنی نزدیک به ریشه) قرار بگیرد. این درخت از آزمون و خطا برای تعیینِ مقدارِ بهینه جهتِ نقطه‌ی جداساز (مثلاق خط X1 در مثالِ بالا) در هر ویژگی (بُعد) استفاده می‌کند. برای مثال در تصاویرِ بالا اگر بخواهد X1 را برای طولِ حیوان انتخاب کند، بایستی نقاطِ مختلف را در این ویژگی مورد آزمایش قرار دهد تا بتواند بهترین نقطه (که شاخص جینیِ کمتری داشته باشد) را مکان‌یابی کند.

تفاوتِ شاخص جینی و entropy (آنتروپی) را می‌توان در این دانست که معمولاً شاخصِ جینی برای داده‌هایی که دارای قسمتِ بزرگتر هستند به درد می‌خورد این در حالی است که entropy به درد داده‌هایی می‌‌خورد که قسمت های کوچک زیادی دارند که مقادیر یکتا در آن ها بیشتر است.

اگر درس overfitting و underfitting را خوانده باشید متوجه می‌شوید که درخت های تصمیم احتمال overfit شدن را دارند. درخت تصمیم CART نیز چنین است. جهت جلوگیری از overfit شدن درخت تصمیم CART، می‌توان از یک شرطِ توقف استفاده کرد. این شرطِ توقف به الگوریتم می‌گوید که ادامه‌ی درخت را متوقف کند. این کار باعث می‌شود که درخت CART دیگر شاخه‌سازی و برگ‌سازی را متوقف کند و درخت را بیش از یک حدِ آستانه‌ بزرگ و پیچیده نکند (همان طور که می‌دانید پیچیدگی یکی از دلایل overfit شدن مدل در طبقه‌بندی بود). یکی از این روش‌ها استفاده از تعداد مشخص نمونه در زیر درخت خاص است به گونه‌ای که اگر تعداد نمونه‌ها در یک زیر درخت از یک حد آستانه کمتر شد، دیگر درخت ریشه‌سازی را ادامه نمی‌دهد. مثلا اگر در مثالِ بالا حدآستانه را ۴ قرار دهیم آن وقت اگر زیر درختی مجموعِ سگ و گربه‌های آن بیشتر از ۴ بود، می‌تواند ادامه پیدا کند ولی اگر کمتر از ۴ بود، دیگر ساخت شاخه و برگ برای آن درخت در آن قسمت، ادامه پیدا نمی‌کند و برای مثال آن دسته‌ای که اکثریت نمونه‌ها را دارند به عنوان گره برگ (برچسب) استفاده می‌شود. مثلاً اگر در شرایطی در یک زیر درخت، ۲ سگ و ۱ گربه داشتیم، دیگر ریشه‌سازی ادامه پیدا نمی‌کند (مجموع ۳ می‌شود که کمتر از ۴ است) و این گره به عنوان گره‌ی برگ (آخرین گره درخت را گره‌ی برگ می‌گویند) شناخته شده، برچسب سگ (که اکثریت است) برای این گره در نظر گرفته می‌شود.

ترتیب پیشنهادی خواندن درس‌های این مجموعه به صورت زیر است:
منابع این بحث و اطلاعات بیشتر

» وب سایت MachineLearningMastery » وب سایت learnbymarketing

در صورت تمایل به یادگیری بیشتر، منابع بالا در نظر گرفته شده است. می توانید با خواندن این منابع، به یادگیری خود در این زمینه عمق ببخشید

13 دیدگاه دربارهٔ «الگوریتم طبقه بند درخت تصمیم CART»

  1. سلام

    لطفا بگید تفاوت درخت تصمیم cart با درخت تضمیم c.5 در چیست ؟ مزایا و تفاوتهاشون در چیه ؟

    تفاوت شبکه عصبی با درخت تصمیم چیست ؟ ( من دارم پایان نامه مینویسم و وقتی داده هامون وارد نرم افزار کلمنتاین کردم الویت بندی متغییرهامو برا هردو مدل یکسان رتبه بندی کرده(یعنی متلا متغیر اول را برای هردومدلم عدد ۰.۶۵ داده و …) ، من میخوام نتیجه بگیرم شبکه عصبی بهتره چه ویژگیو میتونم بیان کنم که نشون بده شبکه عصبی بهتر کار کرده ) ؟

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

  2. من تمام درساتونو مطالعه کردم خیلی مفید بودن ولی به طور واضح متوجه نشدم که بتونم به جواب سوالم برسم که بالا براتون مطرح کردم 🙁

  3. سلام، برای انتخاب ویژگی انشعاب، با استفاده از شاخص جینی میشه دو بار پشت سرهم یه ویژگی یکسان انتخاب بشه؟

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

    1. سلام
      منم همین مشکل رو دارم. میشه این تفاوت رو بیشتر توضیح بدید
      یعنی چی داده هایی که دارای قسمت بزرگتر هستند یا داده هایی که قسمت های کوچک زیادی دارند.

  5. سلام
    منم همین سوال رو دارم. میشه این تفاوت رو بیشتر توضیح بدید
    منظور از داده هایی که دارای قسمت بزرگتر هستند یا داده هایی که قسمت های کوچک زیادی دارند چیست؟

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *