وبلاگ شخصی -احمد سوری

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

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

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

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

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

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

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

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

درخت تصمیم ساخته شده به ما میگوید که این دانشجو احتمالا نمیتواند در آزمون دکتری قبول شود. (از روی درختی که خودْ از روی داده‌های گذشته ساخته شده بود)

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