در قسمت قبل با الگوریتم Naive Bayes به عنوان الگوریتمی جهت شروع امر داده کاوی آشنا شدیم. در این قسمت به الگوریتم‌های Decision trees و Linear Regression می‌پردازیم.

خودتان را جای یک متصدی اعطای وام بانکی درنظر بگیرید. یک زوج جوان برای دریافت وام به بانک مراجعه می‌کنند. برای اعطای وام، ممکن است جوان بودن آن‌ها یک علامت مثبت نباشد. حال شما شروع به مصاحبه با آن‌ها می‌کنید و متوجه می‌شوید که ازدواج کرده‌اند. متاهل بودن آن‌ها یک نکته مثبت است. همچنین متوجه می‌شوید که هر دو یک شغل دارند و به مدت سه سال است که مشغول همان کار هستند. درست حدس زدید، پایداری شغل می‌تواند یک نکته مثبت باشد. پس از بررسی حساب بانکی آن‌ها متوجه می‌شوید که در یکسال اخیر سه چک برگشتی دارند. این موضوع، یک منفی بزرگ را سر راه قرار می‌دهد. درنهایت، شما جهت تصمیم گیری برای اعطای وام، براساس تجربه کاری خود در ذهنتان یک درخت ایجاد می‌کنید که رتبه بندی امتیاز برای اعطای وام را تسهیل می‌کند. کاری که الگوریتم Decision Trees انجام می‌دهد شبیه به همین کار است.

چرا الگوریتم درخت تصمیم؟

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

تفسیر الگوریتم

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

شرح نوار ابزار

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

آموزش بیش از اندازه

این الگوریتم، درخت را به صورت بازگشتی رشد می‌دهد. درنتیجه گاهی اوقات ممکن است که با یک درخت بزرگ مواجه شوید. این درخت می‌تواند شامل سطح‌ها و شاخه‌های زیادی باشد. بنابراین شامل قوانین زیادی هم خواهد بود. اما در نظر داشته باشید که ارتباط مستقیمی بین کیفیت پیش بینی و اندازه درخت وجود ندارد. حقیقت امر این است، هرگاه که درخت بیش از اندازه عمیق شود، بجای اینکه تعمیم قوانین صورت گیرد، آموزش حالات مختلف نشان داده می‌شود و این خوب نیست. الگوریتم درخت تصمیم مایکروسافت ویژگی دارد به نام forward pruning که رشد درخت را با استفاده از امتیاز بایزین کنترل می‌کند. به عبارتی زمانیکه اطلاعات کافی برای بخش کردن یک نود وجود نداشته باشد، از این امر جلوگیری می‌کند. این کار توسط پارامتر Complexity_Penalty انجام می‌گردد که مقداری اعشاری بین 0 و 1 را می‌گیرد. هرچه مقدار بالاتری به این پارامتر اختصاص داده شود، محدودیت بیشتری برای تقسیم درخت درنظر گرفته می‌شود و بنابراین سایز درخت کوچکتر می‌گردد.

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

Complexity_Penalty : که توضیح آن در بخش "آموزش بیش از اندازه" آورده شد.

Minimum_Support : جهت تعیین مینیمم اندازه هر نود به کار می‌رود. برای مثال اگر مقدار 20 را به آن بدهیم، آنگاه هر تقسیم بندی که منجر به تولید نودهای فرزندی با اندازه کمتر از 20 شود، انجام نمی‌گردد. اغلب در مواردی که مجموعه داده دارای حالات گوناگون زیادی است، می‌توان مقدار این متغیر را بالا برد تا از آموزش بیش از اندازه جلوگیری کرد. پیش فرض این پارامتر 10 می‌باشد.

Score_Method : این پارامتر مشخص می‌کند که از کدام روش برای محاسبه امتیاز جهت بخش بندی درخت استفاده کنیم. سه مقدار 1، 3 و 4 را می‌گیرد. 1 از امتیاز انتروپی استفاده می‌کند، 3 از بایزین k2 و 4 از بایزین Dirichlet equivalent .

Split_Method : سه مقدار 1 تا 3 را می‌گیرد. فرض کنید که وضعیت تحصیل در یک مجموعه داده سه حالت را دارد: دیپلم، لیسانس، فوق لیسانس. اگر مقدار 1 را برای این پارامتر تعیین نماییم آنگاه حالت دودویی برای تقسیم نودها درخت درنظر گرفته می‌شود. یعنی دو حالت دیپلم و غیر دیپلم. حال اگر مقدار 2 را نظر بگیریم آنگاه تقسیم نودها براساس تمامی حالات درنظر گرفته می‌شود؛ در اینجا سه تا. مقدار 3 که مقدار پیش فرض نیز می‌باشد، انتخاب حالت 1 یا 2 را به عهده الگوریتم می‌گذارد.

Maximum_Input_Attributes : ماکزیمم ورودی را می‌توان از این طریق تعیین کرد. اگر تعداد ورودی‌ها بیشتر از این مقدار باشد، آنگاه فقط ورودی‌های مهم درنظر گرفته شده و مابقی نادیده گرفته می‌شوند.

Linear Regression:

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