الگوریتم درخت تصمیم Decision Tree — آموزش مفاهیم به همراه 1 مثال کاربردی
الگوریتم درخت تصمیم یا الگوریتم ID3 یکی از روش های دسته بندی یا classification در زیر شاخه گروه جدول فراوانی Frequency Table در بحث پیش بینی آینده predicting the future در علوم داده یا داده کاوی است. در ادامه به توضیح و تشریح این الگوریتم همراه با یک مثال خواهیم پرداخت.
الگوریتم درخت تصمیم چیست؟
الگوریتم درخت تصمیم مدل های طبقه بندی یا رگرسیون را به شکل ساختار درخت می سازد. درخت تصمیم ، مجموعه داده را به زیر مجموعه های کوچکتر و کوچکتر تجزیه می کند و یک درخت تصمیم مرتبط به صورت تدریجی توسعه می یابد. نتیجه نهایی یک درخت با گره های تصمیم گیری و گره های برگ است.
یک گره تصمیم (به عنوان مثال ، Outlook) دارای دو یا چند شاخه (به عنوان مثال ، آفتابی ، ابر و بارانی) است. گره برگ (به عنوان مثال ، بازی) یک طبقه بندی یا تصمیم را نشان می دهد. بالاترین گره تصمیم گیری در یک درخت که مطابق با بهترین پیش بینی کننده به نام گره ریشه است. درختان تصمیم گیری می توانند داده های دسته ای و عددی را کنترل کنند.
الگوریتم درخت تصمیم
الگوریتم اصلی ساختن درختان تصمیم گیری به نام ID3 توسط J. R. Quinlan که از جستجوی حریصانه از بالا به پایین و حریصانه در فضای شاخه های احتمالی و بدون برگشت استفاده می کند. ID3 از Entropy و Information Gain برای ساخت درخت تصمیم استفاده می کند.
با توجه به آموزش های قبلی در مدل ZeroR هیچ پیش بینی کننده ای وجود ندارد ، در مدل OneR سعی می کنیم بهترین پیش بینی کننده را به تنهایی پیدا کنیم ، مدل بیزی ساده نیز شامل کلیه پیش بینی کننده ها با استفاده از قانون Bayes و پیش فرض های استقلال بین پیش بینی کننده ها است اما درخت تصمیم شامل کلیه پیش بینی کننده ها با فرضیات وابستگی بین پیش بینی کننده ها است.
تشخیص نفوذ در شبکه با الگوریتم درخت تصمیم DT در متلب
در این سورس کد از مجموعه های KDDTrain+ ، KDDTest+ و KDDTest-21 که کلاً شامل 22544 نمونه است استفاده می شود. در کل 42 ویژگی برای دیتاست در نظر گرفته شده که 41 ویژگی مربوط به داده های جمع آوری شده و ویژگی آخر نیز به عنوان برچسب هدف با عنوان نرمال یا حمله می باشد. برای اطلاعات بیشتر می توانید بر روی لینک زیر کلیک کنید.
آنتروپی
یک درخت تصمیم گیری از بالا به پایین از یک گره ریشه ساخته شده است و شامل تقسیم داده ها به زیر مجموعه هایی است که حاوی نمونه هایی با مقادیر مشابه (همگن) هستند. الگوریتم ID3 از آنتروپی برای محاسبه همگن یک نمونه استفاده می کند. اگر نمونه کاملاً همگن باشد ، آنتروپی صفر است و اگر نمونه تقسیم به همان اندازه باشد ، آنتروپی یک دارد.
برای ساختن یک درخت تصمیم گیری ، باید دو نوع آنتروپی را با استفاده از جداول فرکانس به شرح زیر محاسبه کنیم:
الف) آنتروپی با استفاده از جدول فرکانس یک ویژگی:
ب) آنتروپی با استفاده از جدول فرکانس دو ویژگی:
به دست آوردن اطلاعات یا Information Gain
پس از تقسیم مجموعه داده ها روی یک ویژگی ، سود یا Gain حاصل از آن بر اساس کاهش آنتروپی است. در الگوریتم درخت تصمیم ساختن یک درخت تصمیم گیری درمورد یافتن صفتی است که بالاترین سود Gain اطلاعات را به دست می آورد (یعنی همگن ترین شاخه ها). مراحل الگوریتم بصورت زیر خواد بود:
مرحله 1: آنتروپی هدف را محاسبه کنید.
مرحله 2: مجموعه داده ها بر روی ویژگی های مختلف تقسیم می شوند. آنتروپی برای هر شاخه محاسبه می شود. سپس به طور متناسب اضافه می شود ، برای بدست آوردن آنتروپی کل برای قسمت آنتروپی حاصل از آنتروپی قبل از انشعاب جدا می شود. نتیجه آن ، افزایش اطلاعات یا کاهش آنتروپی است.
مرحله 3: ویژگی را با بیشترین سود Gain به عنوان گره تصمیم گیری انتخاب کنید ، مجموعه داده را توسط شاخه های آن تقسیم کنید و همان روند را در هر شاخه تکرار کنید.
مرحله 4a: شاخه ای با آنتروپی 0 ، گره برگ است.
مرحله 4b: یک شاخه با آنتروپی بیش از 0 نیاز به تقسیم بیشتر دارد.
مرحله 5: الگوریتم ID3 به طور بازگشتی روی شاخه های بدون برگ اجرا می شود ، تا زمانی که همه داده ها طبقه بندی شوند.
انتخاب ویژگی با ترکیب الگوریتم کلونی مورچکان و درخت تصمیم
سورس انتخاب ویژگی با ACO برای DT دارای دو بخش است بخش اول توسط فایل DT.m اجرا می شود که این قسمت فقط الگوریتم DT یا درخت تصمیم را اجرا می کند و بدون در نظر گرفتن انتخاب ویژگی است. بخش دوم توسط فایل DT_with_selection_ACO.m اجرا می شود که توسط الگوریتم کلونی مورچگان برای انتخاب ویژگی (فیوچر) می پردازد.برای اطلاعات بیشتر روی لینک زیر کلیک کنید.
قوانین تصمیم گیری برای درخت تصمیم
با تصمیم گیری از گره ریشه به گره های برگ یک به یک ، درخت تصمیم گیری می تواند به راحتی به مجموعه ای از قوانین تبدیل شود.
سخن پایانی در مورد الگوریتم DT
خوب همانطور که مشاهده کردید با درخت تصمیم می توان یک مدل برای پیش بینی وقایع آینده با استفاده از اتفاقات گذشته طراحی کرد. این الگوریتم بیشتر بر روی مسائل خطی و رگرسیون جواب قابل قبول می دهد و برای مسائل غیر خطی هم با کمی تغییرات در قوانین تصمیم گیری می توان نتایج خوبی را دریافت کرد. امیدواریم مطالب فوق برای شما مفید بوده باشد. منتظر نظرات و پیشنهادهای شما سروران گرامی هستیم.
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.
مثال خیلی خوبی از کاربرد الگوریتم درخت تصمیم بود.
دستتون درد نکنه خیلی خوب بود.
ممنون از این توضیحات عالی. دنبال یه متن تخصصی در مورد الگوریتم درخت های تصمیم بودم که این نوشته رو پیدا کردم. بازم ممنون