پاورپوینت یادگیری درخت تصمیم

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

مقدمه:

در یک مسئله یادگیری با دو جنبه مختلف روبرو هستیم:

نحوه نمایش فرضیه ها روشی که برای یادگیری برمی گزینیم در این فصل برای نمایش فرضیه ها از درخت تصمیم استفاده میکنیم و برای یادگرفتن این درخت از روش ID3 استفاده میکنیم.

اسلاید ۲ :

lدرختها درهوش مصنوعی برای نمایش مفاهیم مختلفی نظیر ساختار جملات، معادلات، حالات بازی، و غیره استفاده میشود.

lیادگیری درخت تصمیم روشی برای تقریب توابع هدف با مقادیر گسسته است. این روش نسبت به نویز داده هامقاوم بوده وقادر است ترکیب فصلی گزاره های عطفی  را یاد بگیرد.

lاین روش جزو مشهورترین الگوریتمهای یادگیری استقرائی است که بصورت موفقیت آمیزی در کاربردهای مختلف بکار گرفته شده است.

اسلاید ۳ :

نمایش درخت تصمیم

 درخت تصمیم درختی است که در آن نمونه ها  را به نحوی دسته بندی میکند که از ریشه به سمت پائین رشد میکنند و در نهایت به گره های برگ میرسد:

هر گره داخلی یاغیر برگ (non leaf) با یک ویژگی (attribute) مشخص میشود.  این ویژگی سوالی را در رابطه با مثال ورودی مطرح میکند.

درهر گره داخلی به تعداد جوابهای ممکن با این سوال شاخه (branch) وجود دارد که هر یک با مقدار آن جواب مشخص میشوند.

برگهای این درخت با یک کلاس و یا یک دسته از جوابها مشخص میشوند.

علت نامگذاری آن با درخت تصمیم این است که این درخت فرایند تصمیم گیری برای تعیین دسته یک مثال ورودی را نشان میدهد.

اسلاید ۴ :

کاربردها

درخت تصمیم در مسایلی کاربرد دارد که بتوان آنها را بصورتی مطرح نمود که پاسخ واحدی بصورت نام یک دسته یا کلاس ارائه دهند.

برای مثال میتوان درخت تصمیمی ساخت که به این سوال پاسخ دهد: بیماری مریض کدام است؟ و یا درختی ساخت که به این سوال پاسخ دهد: آیا مریض به هپاتیت مبتلاست؟

برای مسائلی مناسب است که مثالهای آموزشی بصورت زوج (مقدار-ویژگی) مشخص شده باشند.

تابع هدف دارای خروجی با مقادیر گسسته باشد. مثلا هر مثال با بله و خیر تعیین شود.

نیاز به توصیف گر فصلی (disjunctive) باشد.

اسلاید ۵ :

 ویژگی های درخت تصمیم

برای تقریب توابع گسسته بکار می رود (classification)

نسبت به نویز داده های ورودی مقاوم است

برای داده های با حجم بالا کاراست از این رو درData mining  استفاده می شود

می توان درخت را بصورت قوانین if-then نمایش داد که قابل فهم برای استفاده است

امکان ترکیب عطفی و فصلی فرضیه ها را می دهد

در مواردی که مثالهای آموزشی که فاقد همه ویژگیها هستند نیز قابل استفاده است

اسلاید ۶ :

نحوه نمایش درخت تصمیم

 ارتباط مستقیمی بین درخت   تصمیم ونمایش توابع منطقی  وجود دارد.درواقع هردرخت  تصمیم ترکیب فصلی گزاره های  عطفی است

 مسیر از ریشه به برگ ترکیب عطفی (AND)از ویژگی ها را مشخص نموده و خوددرخت ترکیب فصلی(OR) این ترکیبات را میسازد.

اسلاید ۷ :

الگوریتم یادگیری درخت تصمیم

اغلب الگوریتم های یادگیری درخت تصمیم بر پایه یک عمل جستجوی حریصانه (greedy) بالا به پائین (top-down) در فضای درختهای موجود عمل میکنند.

 این الگوریتم پایه، Concept Learning System (CLS) نامیده می شود که در سال ۱۹۵۰ معرفی شده است.

 این الگوریتم توسط Ross Quilan در سال ۱۹۸۶ بصورت کاملتری تحت عنوان  Inducing Decisition trees (ID3) مطرح گردید.

بعدها الگوریتم کاملتر دیگری تحت عنوان C4.5 ارائه گردید که برخی نقائص ID3 را برطرف میکند.

اسلاید ۸ :

ایده اصلی ID3

lاین ایده به Ocuum’s Razor  مشهور است ومی گوید :

     ” دنیا ذاتا ساده است“

  بنابراین از کوچکترین درخت تصمیم که با داده سازگار باشد انتظار می رود که مثالهای نادیده را به درستی دسته بندی کند.

اسلاید ۹ :

بایاس درخت تصمیم

انتخاب درختهای کوچکتر بایاس درخت تصمیم بر این ایده است که درختهای کوچکتر بر درختهای بزرگتر ترجیح داده شود.

اسلاید ۱۰ :

 سئوال

اگر مسئله ما دارای m ویژگی باشد، ارتفاع درخت تصمیم چقدر خواهد بود؟

جواب:

درخت تصمیم دارای یک ریشه است که آن خود یک ویژگی است،

در سئوال از آن ویژگی به پاسخی می رسیم که آن خود نیز، ویژگی است.

پس حداکثر ارتفاع درخت m خواهد بود.