درخت های تصمیم جهت طبقه‌بندی (Decision Trees)

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

MasoudKaviani.ir

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

فرض کنید شما مدیر یک دانشکده هستید و میخواهید یک طبقه بند (classifier) بسازید تا با کمک این طبقه‌بند مشخص کنید کدام یک از دانشجوهای این دانشکده می‌توانند در آزمون دکتری، قبول شوند (در واقع می‌خواهید یک پیش‌بینی انجام دهید). این پیش‌بینی می‌تواند باعثِ این شود که شما از این به بعد دانشجویان با پتاسیلِ بالا را پیدا کرده و روی آن‌ها سرمایه‌گذاری کنید. مثلاً به آن‌ها وام‌هایی دهید تا بتوانند مقالات بهتری را در نشریات معتبرتر صادر کنند. در واقع می‌خواهید یک مدلِ طبقه‌بندی ایجاد کنید تا بتواند توسط داده‌های گذشته، یک مدل ساخته و از این به بعد، هر بار که یک دانشجوی جدید را به مدلِ یادگرفته شده دادیم، این مدل بتواند بفهمد که این دانشجو با چه احتمالی می‌تواند در آزمونِ دکتری قبول شود. همان طور که از دروس گذشته به یاد دارید، باید یک مجموعه داده (dataset) از دانشجویانِ گذشته که در آزمونِ دکتری قبول شدند یا نشدند ایجاد کنیم تا بتوانیم آن را به الگوریتمِ داده‌کاوی بدهیم و این الگوریتم یاد بگیرد. فرض کنید مجموعه داده را به این صورت می‌سازیم:

همان طور که میبیند در این‌جا دانشجویان قبلیِ ما که مورد بررسی قرار گرفته‌اند، ۷دانشجو هستند که هر کدام ۴ ویژگی دارند. ۱. معدل کل (عدد) ۲. تعداد مقالات (عدد) ۳. مدرک IELTS زبان دارند (۰ یا ۱)؟ ۴. سنوات تحصیلی (عدد). و همچنین یک ستونِ برچسب که اگر دانشجو در در مقطع دکتری قبول شده بود، بلی و اگر قبول نشده بود، خیر است. در واقع این داده‌ها مربوط به داده‌های مختلفِ دانشجوهای قبلی هستند که قبلاً در آزمون دکتری شرکت کرده‌اند.

جدول بالا نوعی داده‌های آموزشی است که الگوریتم می‌تواند از روی آن یاد بگیرد. مثلاً موردِ شماره‌ی ۱# را نگاه کنید. این دانشجو معدل ۱۹/۵ دارد، تعداد ۳ مقاله ارائه کرده است و مدرک زبان IELTS دارد، همچنین  سنوات تحصیلی او ۳ سال بوده است. این دانشجو در مقطع دکتری قبول شده است.

درخت های تصمیم با توجه به داده‌ها مبادرت به ایجادِ یک ساختارِ درختی می‌کنند که مانندِ قانون‌های IF و ELSE عمل کرده و در نهایت به برچسب‌های دلخواهِ ما که از داده‌های آموزشی یاد گرفته شدند، می‌رسند. فرض کنیدمی‌خواهیم داده‌های بالا را به صورت یک درخت بسازیم. شکلِ زیر در واقع یک نمونه درخت تصمیم از روی داده‌های بالا است:

تفسیر شکلِ بالا بسیار ساده است، این شکل می‌تواند در یک زبان برنامه‌نویسی به وسیله‌ی دستورات IF و Else پیاده‌سازی شود. ریشه این درخت (سطح اول)، این است که آیا شخص مدرک IELTS زبان دارد یا خیر؟ اگر مدرک IELTS داشته باشد به زیر درختِ سمت چپ می‌رویم و اگر مدرک IELTS زبان نداشته باشد به زیر درختِ سمت راست می‌رویم. فرض کنید به زیر درخت سمت چپ رفته‌ایم، حال باید بررسی کنیم که آیا شخص تعداد مقالاتی که ارائه کرده است بیشتر یا مساوی ۲ بوده یا خیر؟ اگر بیشتر یا مساوی ۲ بوده، این شخص احتمالاً می‌تواند در آزمون دکتری قبول شود. در واقع درخت تصمیم به این نتیجه رسیده است که اگر یک شخص، مدرکِ IELTS زبان داشته باشد و تعداد مقالاتش بیشتر یا مساوی ۲ باشد، این شخص می‌تواند در آزمون دکتری قبول شود. برای مثالِ دیگر، اگر شخصی، مدرک IELTS زبان داشته باشد (سطح اول درخت) و تعداد کمتر از ۲ مقاله ارائه کرده باشد (سطح دوم در زیر درخت چپ)، الگوریتم تشخیص می‌دهد که این شخص نمی‌تواند آزمون دکتری قبول شود. پس وظیفه اصلی یک درخت تصمیم که الگوریتم‌های آن را در درس های بعدی خواهیم دید، ساخت این درخت به صورت پویا (بدون کد نویسیِ صریح) است به گونه‌ای که خودِ درخت بتواند از روی داده‌های آموزشیِ موجود، شاخه‌ها و برگ‌های خود را پیدا کند. همان طور که می‌بینید، برگ‌های این درخت، همان برچسب‌های داده‌های آموزشی هستند (مثلاً اینجا دکتری قبول شده است یا خیر).

حال فرض کنید این درخت توسط یکی از الگوریتم‌های درخت‌های تصمیم (decision trees) ساخته شده است. در واقع عملیاتِ یادگیری در درختِ تصمیم، همان ساخت عناصر و برگ‌های یک درخت است. شما به عنوان رئیسِ دانشکده می‌خواهید یک دانشجو با مشخصات زیر را بررسی کنید که با توجه به داده‌های موجود و درختِ یادگرفته شده، می‌تواند دکتری قبول شود یا خیر. این کار را به مدل درخت تصمیم که از داده‌های گذشته یاد گرفته است، واگذار می‌کنیم:

این دانشجوی جدید معدل ۱۵.۵ دارد، تعداد ۵ مقاله ارائه کرده است ولی مدرک IELTS زبان ندارد. همچنین ۳ سال سنوات تحصیلی دارد. می‌خواهیم بدانیم آیا این شخص در آزمون دکتری قبول می‌شود یا خیر؟

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

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

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