چکیده مقاله
یادگیری درخت تصمیم یکی از رایج ترین تکنیک های یادگیری ماشین می باشد که به دلیل سادگی و کارامدی باعث شده است علی رغم مشکلاتی که در استفاده از آن همچون صفات دارای نویز و یا صفات فاقد مقدار یا … وجود دارد به شکل گسترده ای در مسائل مربوط به یادگیری ماشین استفاده شود. در این تحقیق سعی شده است به مسائل اصلی مطرح در زمینهء درخت طراحی مانند بازنمایی، طراحی، عام سازی و مشکلات و راه کارهای برخورد با آنها که توسعه یافته اند پرداخته شود و همچنین از برخی مسائل غیراصلی مانند درختان رگراسیون، نرم افزارهای آزمایشگاهی و تست آماری χ۲ نیز ذکری به میان آید.
یادگیری درخت تصمیم
۱- مقدمه
ساختار درخت تصمیم در یادگیری ماشین، یک مدل پیش بینی کننده می باشد که حقایق مشاهده شده در مورد یک پدیده را به استنتاج هایی در مورد مقدار هدف آن پدیده نقش می کند. تکنیک یادگیری ماشین برای استنتاج یک درخت تصمیم از داده ها، یادگیری درخت تصمیم نامیده می شود که یکی از رایج ترین روش های داده کاوی است.
هر گرهء داخلی متناظر یک متغیر و هر کمان به یک فرزند، نمایانگر یک مقدار ممکن برای آن متغیر است. یک گرهء برگ، با داشتن مقادیر متغیرها که با مسیری از ریشهء درخت تا آن گرهء برگ بازنمایی می شود، مقدار پیش بینی شدهء متغیر هدف را نشان می دهد..یک درخت تصمیم ساختاری را نشان می دهد که برگ ها نشان دهندهء دسته بندی و شاخه ها ترکیبات فصلی صفاتی که منتج به این دسته بندی ها را بازنمایی می کنند. یادگیری یک درخت می تواند با تفکیک کردن یک مجموعهء منبع به زیرمجموعه هایی براساس یک تست مقدار صفت انجام شود. این فرآیند به شکل بازگشتی در هر زیرمجموعهء حاصل از تفکیک تکرار می شود. عمل بازگشت زمانی کامل می شود که تفکیک بیشتر سودمند نباشد یا بتوان یک دسته بندی را به همهء نمونه های موجود در زیرمجموعهء بدست آمده اعمال کرد.
درختان تصمیم قادر به تولید توصیفات قابل درک برای انسان، از روابط موجود در یک مجموعهء داده ای هستند و می توانند برای وظایف دسته بندی و پیش بینی بکار روند. این تکنیک به شکل گسترده ای در زمینه های مختلف همچون تشخیص بیماری دسته بندی گیاهان و استراتژی های بازاریابی مشتری بکار رفته است.
این ساختار تصمیم گیری می تواند به شکل تکنیک های ریاضی و محاسباتی که به توصیف، دسته بندی و عام سازی یک مجموعه از داده ها کمک می کنند نیز معرفی شوند. داده ها در رکوردهایی به شکل (x, y) = (x1, x2, x3…, xk, y) داده می شوند. با استفاده از متغیرهای x1,x2,..,xk سعی در درک، دسته بندی یا عام سازی متغیر وابستهء Y داریم.
انواع صفات در درخت تصمیم به دو نوع صفات دسته ای و صفات حقیقی بوده که صفات دسته ای، صفاتی هستند که دو یا چند مقدار گسسته می پذیرند (یا صفات سمبلیک) درحالی که صفات حقیقی مقادیر خود را از مجموعهء اعداد حقیقی می گیرند.
۱-۱- اهداف اصلی درخت‌های تصمیم‌گیری دسته‌بندی کننده
۱٫ داده‌های ورودی را تا حد ممکن درست دسته‌بندی کنند.
۲٫ دانش یادگیری شده از داده‌های آموزشی را به گونه‌ای عام سازی کنند که داده‌های دیده نشده را با بالاترین دقت ممکن دسته‌بندی کنند.
۳٫ در صورت اضافه شدن داده‌های آموزشی جدید، بتوان به راحتی درخت تصمیم‌گیری را گسترش داد(دارای خاصیت افزایشی باشند).
۴٫ ساختار درخت حاصل به ساده‌ترین شکل ممکن باشد.
۱-۲- جذابیت درختان تصمیم
۱٫ نواحی تصمیم پیچیدهء سراسری (خصوصاً در فضاهای با ابعاد زیاد) می توانند با اجتماع نواحی تصمیم محلی ساده تر در سطوح مختلف درخت تقریب زده شوند.
۲٫ برخلاف دسته بندی کننده های تک مرحله ای رایج که هر نمونهء داده ای روی تمام دسته ها امتحان می شود، در یک دسته بندی کنندهء درخت، یک نمونه فقط روی زیرمجموعه های خاصی از دسته ها امتحان شده و محاسبات غیرلازم حذف می شود.
۳٫ در دسته بندی کننده های تک مرحله ای، فقط از زیرمجموعه ای از صفات، برای تفکیک بین دسته ها استفاده می شود که معمولاً با یک معیار بهینهء سراسری انتخاب می شوند. در دسته بندی کنندهء درخت، انعطاف پذیری انتخاب زیرمجموعه های مختلفی از صفات در گره های داخلی مختلف درخت وجود دارد؛ به شکلی که زیرمجموعهء انتخاب شده به شکل بهینه بین دسته های این گره را تفکیک می کند. این انعطاف پذیری ممکن است بهبودی در کارایی را نسبت به دسته بندی کننده های تک مرحله ای ایجاد کند.
۴٫ در تحلیل چندگونگی با تعداد صفات و دسته های زیاد، معمولاً نیاز به تخمین توزیع های ابعاد-زیاد یا پارامترهای خاصی از توزیع های دسته همانند احتمالات اولیه از یک مجموعهء داده های آموزشی کوچک می باشد. در این حالت مشکل ابعاد-بالا وجود دارد که امکان دارد در درخت دسته بندی کننده، با بکاربردن تعداد کمتری از صفات در هر گرهء داخلی بدون افت شدید کارایی، این مسئله حل شود.
۱-۳- انواع درختان تصمیم
• هنگامی که خروجی یک درخت، یک مجموعهء گسسته از یک مجموعه مقادیر ممکن است؛ به آن درخت دسته بندی ، می گوییم (مثلاً مونث یا مذکر، برنده یا بازنده). این درخت ها تابع X→C را بازنمایی می کنند که در آن C مقادیر گسسته می پذیرد.
• هنگامی که بتوان خروجی درخت را یک عدد حقیقی درنظر گرفت آن را، درخت برگشت می نامیم (مثلاً قیمت خانه یا طول مدت اقامت یک بیمار در یک بیمارستان). این درختان اعداد را در گره های برگ پیش بینی می کنند و می توانند از مدل رگراسیون خطی یا ثابت (یعنی میانگین) یا مدل های دیگر استفاده کنند.
• درخت CART (Classification And Regression Tree) نامی است که به هر دو روال بالا اطلاق می شود. نام CART سرنام کلمات درختان برگشت و دسته بندی است.
• درختان خوشه ای فقط نمونه ها را در گره های برگ گروه بندی می کنند.
بیشتر تحقیقات در یادگیری ماشین روی درختان دسته بندی متمرکز است.
۱-۳-۱- درختان رگراسیون
وظیفهء یادگیری در درختان رگراسیون، شامل پیش بینی اعداد حقیقی بجای مقادیر دسته ای گسسته است. که این عمل را با داشتن مقادیر حقیقی در گره های برگ خود نشان می دهند. بدین صورت که میانگین مقادیر هدف نمونه های آموزشی را در این گرهء برگ بدست می آورند. این نوع از درختان، تفسیر آسان داشته و می توانند توابع ثابت تکه ای را تقریب بزنند.
نسخهء پیچیده تر درختان رگراسیون، درختان مدل هستند که عمل رگراسیون را با داشتن مدل خطی در گره های داخلی یا پایانی نشان می دهند (در هر گره، توابع رگراسیون خطی دارند). بعداز اینکه درخت رگراسیون کامل ساخته شد، عمل رگراسیون خطی، به نمونه هایی که به این گره رسیده اند اعمال می شود و فقط از یک زیرمجموعه از صفات (صفاتی که در زیردرخت دیده خواهند شد) برای این کار استفاده می شوند. بدلیل استفاده از زیرمجموعه ای از صفات در هر گره، سربار عمل رگراسیون خطی زیاد نخواهد شد.
تفاوت درخت رگراسیون و درخت دسته بندی:
• معیار تقسیم و شاخه زدن در درختان رگراسیون براساس حداقل کردن گوناگونی زیرمجموعهء داخلی است.
• معیار هرس در درختان رگراسیون براساس معیار خطای عددی می باشد.
• گره های برگ، میانگین مقادیر دسته برای مثال های آموزشی افراز شده به این گره را پیش بینی می کنند.
فهرست
– چکیده ۲
مقدمه ۵
۱-۱- اهداف اصلی درخت‌های تصمیم‌گیری دسته‌بندی کننده ۶
۱-۲- جذابیت درختان تصمیم ۶
۱-۳- انواع درختان تصمیم ۶
۱-۳-۱- درختان رگراسیون ۷
۲- بازنمایی درخت تصمیم ۸
۲-۱- توسعهء درختان تصمیم با گراف های تصمیم ۹
۳- مسائل مناسب برای یادگیری درخت تصمیم ۱۰
۴- چه صفتی بهترین طبقه بندی کننده است؟ ۱۱
۴-۱-۱- بی نظمی همگونی مثال ها را اندازه گیری می کند. ۱۱
۴-۱-۲- نفع اطلاعات، کاهش مورد انتظار در بی نظمی را اندازه گیری می کند. ۱۳
۴-۲- یک مثال تشریحی ۱۴
۴-۳- حالت خاصی از ساخت درخت تصمیم ۱۵
۵- جستجوی فضای فرضیه در یادگیری درخت تصمیم ۱۶
۵-۱- قابلیت ها و محدودیت های الگوریتم ID3 16
۶- بایاس قیاسی (استنتاجی) در یادگیری درخت تصمیم ۱۷
۶-۱- بایاس های محدودیت و بایاس های ارجحیت ۱۸
۶-۲- چرا فرضیات کوتاهتر را ترجیح می دهیم؟ ۱۹
۷- مسائل در یادگیری درخت تصمیم ۲۰
۷-۱- اورفیتینگ داده ها ۲۰
۷-۲- روشهای موجود برای ممانعت از اورفیتینگ ۲۶
۷-۲-۱- انواع روش های هرس کردن ۲۷
۷-۲-۱-۱- تست chi-Square 29
۷-۲-۲- هرس خطای کاهش یافته ۳۰
۷-۲-۳- هرس بعدی قانون ۳۱
۷-۳- بکاربردن صفات با مقادیر پیوسته ۳۴
۷-۴- معیارهای دیگر برای انتخاب صفات ۳۵
۷-۵- بکاربردن مثال های آموزشی با صفات فاقد مقدار ۳۶
۷-۶- بکاربردن صفات با هزینه های متفاوت ۳۷
۸- عام سازی درخت ۳۸
۸-۱- طراحی یک دسته بندی کنندهء درخت تصمیم ۳۸
۸-۲- روشهای اصلی برای طراحی دسته بندی کنندهء درخت تصمیم ۳۹
۹- انواع یادگیری در درخت تصمیم گیری ۴۰
۱۰- مزایا و معایب درخت تصمیم ۴۰
۱۰-۱- مزایای درختان تصمیم نسبت به روش های دیگر داده کاوی ۴۰
۱۰-۲- معایب درختان تصمیم ۴۱
۱۱- نرم افزارهای مفید برای درخت تصمیم ۴۲
۱۲- الگوریتم یادگیری درخت تصمیم پایه ۴۳
۱۳- جمع بندی ۴۵
۱۴- لغت نامه ۴۶
۱۵- مراجع ۴۸