یکی از محبوبترین و در عین حال سادهترین الگوریتمهای درختهای تصمیم، درخت تصمیمِ CART است که کاربردهای زیادی در طبقهبندی و رگرسیون دارد. CART که خود مخفف Classification and Regression Tree است بر اساس درخت های دودویی (باینری) بنا نهاده شده است. در این درس میخواهیم بیشتر با نحوهی ساختِ درختِ CART آشنا شویم. این درخت (و البته درختهای دیگر) میتواند پایهای برای الگوریتمهای پیچیدهتر مانند جنگلِ تصادفی (Random Forest) باشد.
الگوریتم طبقهبندی درخت تصمیم C4.5
آقای راس کوینلند (پیشنهاد دهندهی الگوریتمِ ID3)، بعد از اینکه به نقاط ضعفِ این الگوریتم پیبرد، در مدتِ کوتاهی الگوریتمِ بعدی خود یعنی C4.5 را طراحی کرد. از نقاطِ ضعف الگوریتم ID3 که در C4.5 رفع شده است میتوان به موارد زیر اشاره کرد:
آشنایی با مفهوم Bias و Variance در طبقهبندی
مسائلِ حوزهی طبقهبندی (که پایهی آن آمار و ریاضیات هستند) یک خروجیِ موردِ انتظار دارند و آن این است که بتوانیم برچسبها را با دقت بالا شناسایی و از همدیگر تفکیک کنیم. احتمالاً در درس شبکههای عصبی با مفهومِ خطِ جداساز برای سگ و گربه آشنا شدهاید. اجازه بدهید یک بارِ دیگر این تصویر را با هم مرورِ کوتاهی داشته باشیم (برای درک اولیه این تصویر درس شبکه عصبی MLP را از اینجا بخوانید):
آشنایی با مفهوم Overfitting و Underfitting در طبقهبندی
این دو مفهوم از مفاهیمِ اساسی است که در بحثِ طبقهبندیِ دادهها مورد بحث قرار میگیرند. هدف از درسِ جاری این است که با مفهوم Overfitting و Underfitting آشنا شده تا بتوانیم الگوریتمهایی ارائه کنیم تا از این دو پدیده در امان باشند.
ادامه خواندن “آشنایی با مفهوم Overfitting و Underfitting در طبقهبندی”
الگوریتم درخت تصمیم ID3 و ساختار Entropy و Gain
با درختهای تصمیم در درس گذشته آشنا شدید. الگوریتم ID3 یکی از الگوریتمهای پایه برای ساختِ درختهای تصمیم است. همانطور که در درس گذشته گفتیم، در یک درخت تصمیم، مهم است که کدام یک از ویژگیها (یا همان ابعاد) را در سطوح بالاتری از درخت انتخاب کنیم تا به طبقهبندی کمک کند.
ادامه خواندن “الگوریتم درخت تصمیم ID3 و ساختار Entropy و Gain”
درخت های تصمیم جهت طبقهبندی (Decision Trees)
درختها کاربردِ فراوانی در علومِ کامپیوتر و مهندسی نرمافزار دارند. از ساختمان داده و طراحیِ الگوریتم تا سیستمهای عامل و سیستمهای توزیع شده، همه به نوعی و در قسمتهای مختلف از درختهای تصمیم استفاده کردهاند. در دادهکاوی و طبقهبندی نیز این درختها جایگاهِ ویژهای دارند و بسیاری از الگوریتمهای طبقهبندی بر پایهی این درختها ساخته شدهاند. به آنها درختهای تصمیم میگویند زیرا میتوانند یک تصمیمِ خاص (مثلاً اینکه به یک شخص وام بدهیم یا نه) را بر اساسِ اطلاعاتِ گذشته اتخاذ کنند. اجازه بدهید مانند دروس قبلی، با یک مثال بحث را آغاز کنیم.
ادامه خواندن “درخت های تصمیم جهت طبقهبندی (Decision Trees)”
الگوریتم K نزدیک ترین همسایه (KNN)
KNN شاید سادهترین الگوریتم در بحثِ طبقهبندی باشد. میخواهیم با یک مثال بسیار ساده شروع کنیم. فرض کنید شما یک فروشگاهِ مواد غذایی و دو دسته مشتری دارید، مشتریانِ دسته اول، کسانی هستند که بیشتر از ۱۰۰ هزار تومان در هر بار مراجعه از شما خریداری میکنند و دستهی دوم مشتریانی هستند که در هر مراجعه معمولاً کمتر از ۱۰ هزار تومان خرید میکنند. شما که فروشندهی با تجربهای هستید، به سبب چند سالی که در این مغازه فعالیت دارید میدانید که مشتریان دستهی اول خانمهایی هستند که سن بالای ۴۰ سال دارند و با اتومبیل به فروشگاه شما میآیند (مثلاً در مراجعهی آنها به این الگو دقت کردهاید). و دستهی دوم، یعنی همان مشتریانی که کمتر از ۱۰ هزار تومان از شما خریداری می کنند. معمولاً آقایانی هستند که سن زیر ۲۵ سال دارند و بدون اتومبیل به فروشگاه میآیند. حال فرض کنید، یک مشتری جدید به فروشگاه آمده است. این شخص یک خانم ۴۵ ساله است که با اتومبیلِ خود به فروشگاه آمده. شما این مشتری جدید را در کدام دسته (با توجه به مشتریان قبلی) قرار میدهید؟ انتظار دارید که این شخص چقدر از شما خرید کند؟