درختها کاربردِ فراوانی در علومِ کامپیوتر و مهندسی نرمافزار دارند. از ساختمان داده و طراحیِ الگوریتم تا سیستمهای عامل و سیستمهای توزیع شده، همه به نوعی و در قسمتهای مختلف از درختهای تصمیم استفاده کردهاند. در دادهکاوی و طبقهبندی نیز این درختها جایگاهِ ویژهای دارند و بسیاری از الگوریتمهای طبقهبندی بر پایهی این درختها ساخته شدهاند. به آنها درختهای تصمیم میگویند زیرا میتوانند یک تصمیمِ خاص (مثلاً اینکه به یک شخص وام بدهیم یا نه) را بر اساسِ اطلاعاتِ گذشته اتخاذ کنند. اجازه بدهید مانند دروس قبلی، با یک مثال بحث را آغاز کنیم.
فرض کنید شما مدیر یک دانشکده هستید و میخواهید یک طبقه بند (classifier) بسازید تا با کمک این طبقهبند مشخص کنید کدام یک از دانشجوهای این دانشکده میتوانند در آزمون دکتری، قبول شوند (در واقع میخواهید یک پیشبینی انجام دهید). این پیشبینی میتواند باعثِ این شود که شما از این به بعد دانشجویان با پتاسیلِ بالا را پیدا کرده و روی آنها سرمایهگذاری کنید. مثلاً به آنها وامهایی دهید تا بتوانند مقالات بهتری را در نشریات معتبرتر صادر کنند. در واقع میخواهید یک مدلِ طبقهبندی ایجاد کنید تا بتواند توسط دادههای گذشته، یک مدل ساخته و از این به بعد، هر بار که یک دانشجوی جدید را به مدلِ یادگرفته شده دادیم، این مدل بتواند بفهمد که این دانشجو با چه احتمالی میتواند در آزمونِ دکتری قبول شود. همان طور که از دروس گذشته به یاد دارید، باید یک مجموعه داده (dataset) از دانشجویانِ گذشته که در آزمونِ دکتری قبول شدند یا نشدند ایجاد کنیم تا بتوانیم آن را به الگوریتمِ دادهکاوی بدهیم و این الگوریتم یاد بگیرد. فرض کنید مجموعه داده را به این صورت میسازیم:
همان طور که میبیند در اینجا دانشجویان قبلیِ ما که مورد بررسی قرار گرفتهاند، ۷دانشجو هستند که هر کدام ۴ ویژگی دارند. ۱. معدل کل (عدد) ۲. تعداد مقالات (عدد) ۳. مدرک IELTS زبان دارند (۰ یا ۱)؟ ۴. سنوات تحصیلی (عدد). و همچنین یک ستونِ برچسب که اگر دانشجو در در مقطع دکتری قبول شده بود، بلی و اگر قبول نشده بود، خیر است. در واقع این دادهها مربوط به دادههای مختلفِ دانشجوهای قبلی هستند که قبلاً در آزمون دکتری شرکت کردهاند.
جدول بالا نوعی دادههای آموزشی است که الگوریتم میتواند از روی آن یاد بگیرد. مثلاً موردِ شمارهی ۱# را نگاه کنید. این دانشجو معدل ۱۹/۵ دارد، تعداد ۳ مقاله ارائه کرده است و مدرک زبان IELTS دارد، همچنین سنوات تحصیلی او ۳ سال بوده است. این دانشجو در مقطع دکتری قبول شده است.
درخت های تصمیم با توجه به دادهها مبادرت به ایجادِ یک ساختارِ درختی میکنند که مانندِ قانونهای IF و ELSE عمل کرده و در نهایت به برچسبهای دلخواهِ ما که از دادههای آموزشی یاد گرفته شدند، میرسند. فرض کنیدمیخواهیم دادههای بالا را به صورت یک درخت بسازیم. شکلِ زیر در واقع یک نمونه درخت تصمیم از روی دادههای بالا است:
تفسیر شکلِ بالا بسیار ساده است، این شکل میتواند در یک زبان برنامهنویسی به وسیلهی دستورات IF و Else پیادهسازی شود. ریشه این درخت (سطح اول)، این است که آیا شخص مدرک IELTS زبان دارد یا خیر؟ اگر مدرک IELTS داشته باشد به زیر درختِ سمت چپ میرویم و اگر مدرک IELTS زبان نداشته باشد به زیر درختِ سمت راست میرویم. فرض کنید به زیر درخت سمت چپ رفتهایم، حال باید بررسی کنیم که آیا شخص تعداد مقالاتی که ارائه کرده است بیشتر یا مساوی ۲ بوده یا خیر؟ اگر بیشتر یا مساوی ۲ بوده، این شخص احتمالاً میتواند در آزمون دکتری قبول شود. در واقع درخت تصمیم به این نتیجه رسیده است که اگر یک شخص، مدرکِ IELTS زبان داشته باشد و تعداد مقالاتش بیشتر یا مساوی ۲ باشد، این شخص میتواند در آزمون دکتری قبول شود. برای مثالِ دیگر، اگر شخصی، مدرک IELTS زبان داشته باشد (سطح اول درخت) و تعداد کمتر از ۲ مقاله ارائه کرده باشد (سطح دوم در زیر درخت چپ)، الگوریتم تشخیص میدهد که این شخص نمیتواند آزمون دکتری قبول شود. پس وظیفه اصلی یک درخت تصمیم که الگوریتمهای آن را در درس های بعدی خواهیم دید، ساخت این درخت به صورت پویا (بدون کد نویسیِ صریح) است به گونهای که خودِ درخت بتواند از روی دادههای آموزشیِ موجود، شاخهها و برگهای خود را پیدا کند. همان طور که میبینید، برگهای این درخت، همان برچسبهای دادههای آموزشی هستند (مثلاً اینجا دکتری قبول شده است یا خیر).
حال فرض کنید این درخت توسط یکی از الگوریتمهای درختهای تصمیم (decision trees) ساخته شده است. در واقع عملیاتِ یادگیری در درختِ تصمیم، همان ساخت عناصر و برگهای یک درخت است. شما به عنوان رئیسِ دانشکده میخواهید یک دانشجو با مشخصات زیر را بررسی کنید که با توجه به دادههای موجود و درختِ یادگرفته شده، میتواند دکتری قبول شود یا خیر. این کار را به مدل درخت تصمیم که از دادههای گذشته یاد گرفته است، واگذار میکنیم:
این دانشجوی جدید معدل ۱۵.۵ دارد، تعداد ۵ مقاله ارائه کرده است ولی مدرک IELTS زبان ندارد. همچنین ۳ سال سنوات تحصیلی دارد. میخواهیم بدانیم آیا این شخص در آزمون دکتری قبول میشود یا خیر؟
اگر بخواهیم با توجه به درخت ساخته شده در شکل بالا، این دانشجو را ارزیابی کنیم مانند شکل زیر مسیر را ادامه میدهیم تا به یکی از برگها برسیم (مسیر حاشور خورده قرمز):
درخت تصمیمِ ساخته شده به ما میگوید که این دانشجو احتمالاً نمیتواند در آزمون دکتری قبول شود. این طبقهبندی با استفاده از درختی که توسط دادههای گذشته ساخته بود، انجام شد.
این یک مثال ساده برای فهمِ نحوهی کارکردِ یک درخت تصمیم بود. در دنیای واقعی، ابعاد (یعنی همان ویژگی ها) و تعداد نمونهها – در اینجا تعداد دانشجویان در مجموعه دادهی آموزشی – معمولاً خیلی بیشتر از اینها است و کارِ ساختِ درختِ تصمیم بر عهدهی الگوریتم و کامپیوتر است. در دروس بعدی به نحوه ساخت و چینش شاخهها و برگها در الگوریتمهای مختلفِ درخت تصمیم خواهیم پرداخت.
- ۱ » الگوریتم K نزدیک ترین همسایه (KNN)
- ۲ » درخت های تصمیم جهت طبقهبندی (Decision Trees)
- ۳ » الگوریتم درخت تصمیم ID3 و ساختار Entropy و Gain
- ۴ » آشنایی با مفهوم Overfitting و Underfitting در طبقهبندی
- ۵ » آشنایی با مفهوم Bias و Variance در طبقهبندی
- ۶ » الگوریتم طبقهبندی درخت تصمیم C4.5
- ۷ » الگوریتم طبقه بند درخت تصمیم CART
- ۸ » طبقه بند ترکیبی (Ensemble Classifier) و مبحث Bagging و Boosting
- ۹ » الگوریتم جنگل تصادفی (Random Forest)
- ۱۰ » رگرسیون لجستیک (Logistic Regression)
- ۱۱ » مسائل طبقهبندی دودویی (binary)، چند کلاسه (Multi Class)، چند برچسبه (Multi Label) و تفاوت آنها
- ۱۲ » روش «یک در مقابل همه (One vs. All)» برای طبقهبندی دادههای چند کلاسه
- ۱۳ » روش «یک در مقابل یک (One vs. One)» در طبقهبندی
- ۱۴ » مدلهای احتمالی در مقابل مدلهای قطعی در طبقهبندی دادهها
- ۱۵ » ماتریس اغتشاش (Confusion Matrix) و معیار دقت (Accuracy)
- ۱۶ » معیار صحت (Precision)، پوشش (Recall) و معیار F
- ۱۷ » معیار کاپا (Kappa) برای ارزیابی طبقهبندیهای چندکلاسه
با سلام
دوست عزیز واقعا مطالب سایتتون عالی و مفیده.
موفق باشید
با سلام فوق العاده خوب درس دادید واقعا بی نظیره سپاسگزارم
با سلام، ممنون خیلی عالی بود
امیدوارم که همین گونه به مباحث خوبتون ادامه بدید.
مثالهاتون بی نظیره من کلی سایتا رو گشتم فقط با توضیحات و مثال های شما فهمیدم موضوع از چه قراره . مرسی
باسلام .خیلی عالی بود.
سلام خیلی ممنونم از مطلب مفیدتون خیلیییییی به دردم خورد
سلام خیلی روان توضیح دادین جناب مهندس. من سه روز دگ جلسه دفاع دارم الگوریتمم جنگل تصادفیه ولی به صورت کدنویسی بلدم و اگه بخوام برای کسی توضیح بدم نمیفهمه اصلا. ولی برای اطلاعات بیشتر اومدم مطالب شمارو از اول میخونم چقداطلاعاتم رفت بالا واقعا ممنونم ازتون.
با سلام و احترام
مطالب بسیار ساده فهم و روان ارائه شده، البته موضوع پایان نامه من در مورد “مدل سازی بیماری آنفلوآنزای فوق حاد پرندگان در استان گیلان با استفاده از GIS” است و در این خصوص برای تعیین وزن متغیر های مورد نظر از روش مدل سازی Boosted Regresion Tree استفاده میشه. اگر لطف کنید در این خصوص هم مطالبی به اشتراک بگذارید بسیار سپاس گزار خواهم شد.
سلام خسته نباشید
برای رسم درخت از کجا میفهمیم که از کجا شروع کنیم؟و ترتیبش رو چطور متوجه میشیم؟
سلام
دروس بعدی رو بخونید، اونجا توضیح دادم به چه ترتیبی میتونه شروع بشه
بسیار بسیار عالی
واقعا ممنون
با سلام
الگوریتم Decision Tree که در نرم افزار رپیدماینر وجود دارد از چه نوعی هستش؟
مثلا نوع های id3 و cart و c4.5 داریم ولی تو رپیدماینر مشخص نکردن چه نوعی هستش.
اگر شما می دانید لطفا پاسخ دهید
با تشکر
عالی بود ،ممنون
مرسی عالی بود
عالی بود. مرسی
سلام
ممنون از مطالب مفیدتون
سلام مطالبتون واقعا عالیه
امکانش هست درمورد الگوریتم های درختان تصمیم ارتقای گرادیانی (XGBoost) هم مطلب بزارید
اگر فایل پی دی اف هر درس رو هم قرار بدید خیلی خوب میشه
سپاس از تدریس خوبتون
سلام
میشه بفرمایید منظور از کد نویسی صریح چیست؟
یعنی صراحتا در کد بگوییم که در سطح اول درخت براساس کدام صفت (تعداد مقلات و…) دیتاست را تقسیم کنیم و همینطور در سطح دوم و الی آخر در صورتی که میتوان الگوریتمی داینامیک داشت باشیم که خود الگوریتم این صفات را مشخص کند و هر سطح درخت تصمیم را بر اساس صفتی که بیشتر برای ما gain دارد تشکیل دهد.
خیلی عالی بود
واقعا همین که ساده توضیح میدید باعث مفهومی یادگرفتن میشه