پیاده سازی درخت تصمیم در نرم افزار

در این آموزش بر روی دیتاست BankLoan مدل سازی داده ها و پیاده سازی درخت تصمیم را در IBM SPSS Modeler انجام خواهیم داد. برای شروع مدلسازی ابتدا فیلد هدف و فیلد های موثر را تعریف می نماییم و سپس دیتاست را به دو قسمت تست و آموزش تقسیم می نماییم.

Pallet Bar 🡺 Field Ops 🡺 Partition

Pallet Bar 🡺 Modeling 🡺 Classification 🡺 C5.0

الگوریتم C5.0 یک نوع درخت تصمیم گیری تک متغیره و بهبود یافته الگوریتم C4.5 می باشد که توسط محقق استرالیایی کوئین لن در سال ۱۹۹۳ طراحی شده است.

الگوریتم درخت تصمیم گیری C5 یا C5.0 Decision Tree Algorithm مثل الگوریتم طبقه بند درخت تصمیم CART در ابتدا درختی کامل پر ایجاد می کند اما استراتژی هرس آن متفاوت می باشد. این الگوریتم کلاسه بندی را با تقسیم داده ها به زیر مجموعه هایی که شامل رکورد های همگن تر از والد خود می باشند انجام می دهد.

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

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

استنتاج قانون به کمک الگوریتم C5.0 براساس درخت تصمیم گیری (Decision Tree) می باشد. احتمالا بیشتر از یک قانون به ازای هر رکورد خاص صدق کند و یا هیچ قانونی مورد استفاده قرار نگیرد.

در صورتی که چندین قانون برای یک رکورد مناسب باشند، آنگاه هر قانون مبتنی بر اطمینان مربوط به هر قانون، وزن vote می گیرد که در این صورت بر اساس ترکیب وزن تمام قوانین مناسب برای رکورد، پیش بینی نهایی تعیین می گردد.

در صورتی که هیچ قانونی مناسبی در کار نباشند، یک پیش گویی پیش فرض به آن رکورد نسبت داده می شود.

Pallet Bar 🡺 Modeling 🡺 Classification 🡺 C&RT

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

در این درس می‌خواهیم بیشتر با نحوه‌ی ساختِ درختِ CART آشنا شویم. این درخت (و البته درخت‌های دیگر) می‌تواند پایه‌ای برای الگوریتم‌های پیچیده‌تر مانند جنگلِ تصادفی (Random Forest) باشد.

الگوریتمِ درختِ تصمیمِ CART برای ساختِ درختِ تصمیم، داده‌ها را به قسمت‌های دو‌تایی تقسیم کرده و بر اساس آن‌ها درخت دو‌دویی (باینری) را می‌سازد. اجازه دهید با همان مثال سگ و گربه یک درختِ تصمیمِ CART ایجاد کنیم.

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

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

حال با این کار یک درخت دودویی ایجاد می شود. مانند تصویر زیر:

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

حال می‌توان هر کدام از این دو قسمت را نیز، به قسمت های کوچکتری تقسیم کرد:

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

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

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

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

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

Pallet Bar 🡺 Output 🡺 Analysis