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

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

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

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

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

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

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

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

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

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

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

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

تفاوت شاخص Gini و Entropy را میتوان در این دانست که معمولا شاخص Gini برای داده هایی که دارای قسمت بزرگتر هستند به درد می خورد این در حالی است که Entropy به درد داده هایی میخورد که قسمت های کوچک زیادی دارند که مقادیر یکتا در آن ها بیشتر است.

2380 بازدید