کامپیوتر و IT و اینترنت • علوم مهندسی

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

در نمایش آنلاین فایل، ممکن است بعضی علائم، اعداد و حتی فونت‌ها به خوبی نمایش داده نشود. این مشکل در فایل اصلی وجود ندارد.

در نمایش آنلاین تعداد 42 از 42 صفحه نمایش داده شده است.

صفحه 1:
یادگیری درخت تصمیم ‎Skhiry‏ لججهة) : تسصوو|؟ ‎ ‎0 Mitchell Ch. 3 ‎

صفحه 2:
#در یک مسئله یادگیری با دو جنبه مختلف روبرو هستیم: # نحوه نمایش فرضیه ها * روشی که برای یادگیری برمی گزینیم © در اين فصل براى نمايش فرضیه ها از درخت تصمیم استفاده ميكنيم و براى يادكرفتن اين درخت از روش ‎IDO‏ استفاده

صفحه 3:
© درختها درهوش مصنوعی برای نمایش مفاهیم مختلفی ‎pales‏ ‏ساختار جملات معادلات» حالات بازی» و غیره استفاده میشود. 9 یادگیری درخت تصمیم روشی برای تقریب توابع هدف با مقادیر گسسته است. این روش نسبت به نویز داده هامقاوم بوده وقادر است ترکیب فصلی گزاره های عطفی را یاد بگیرد. * این روش جزو مشهورترین الگوریتمهای یادگیری استقرائی است که بصورت موفقیت آمیزی در کاربردهای مختلف بکار گرفته شده است.

صفحه 4:
نمایش درخت تصمیم © درخت تصمیم درختی است که در آن نمونه ها را به نحوی دسته بندی ميكند كه از ريشه به سمت يائين رشد ميكنند و در نهایت به گره های برگ ميرسد: * هر گره داخلی یاغپر برنگ (ابا مسب) با بک ویژگی (حعهی) مشلخص میشود: این ویژگی سوالی را در رابطه با مثال ورودی مطرح میکند. * درهر گره داخلی به تعداد جوابهای ممکن با این سوال شاخه (مس) وجود دارد که هر یک با مقدار آن جواب مشخص میشوند. * برگهای این درخت با یک کلاس و با یک دسته از جوابها مشخص میشوند. ‎٩‏ علت نامگذاری آن با درخت تصمیم این است. که اين درخت فرایند تصمیم گیری برای تعیین دسته یک مثال ورودی را نشان میدهد.

صفحه 5:
۲ “هر برك اين درخت يك كلاس يا دسته را مشخص ميكند. با یک مثال آموزشی در درخت تصمیم به این صورت دسته بندی مر ‎os‏ میب رو راک اتقو اد نوتطزل: شاخه ها حرکت رو به پائین انجام می این ف یند برای گزه های زیردرختان كر شود.

صفحه 6:
درخت تصمیم در مسایلی کاربرد دارد که بتوان آنها را بصورتی مطرح نمود که پاسخ واحدی بصورت نام یک دسته پا کلاس ارائه دهند. © براى مثال میتوان درخت تصمیمی ساخت که به این سوال پاسخ دهد: بیماری مریض کدام است؟ و یا درختی ساخت که به اين سوال پاسخ دهد: آیا مریض به هپاتیت مبتلاست؟ © برای مسائلی مناسب است که مثالهای آموزشی بصورت زوج (مقدار- ویژگی) مشخص شده باشند. © تابع هدف دارای خروجی با مقادیر گسسته باشد. مثلا هر مثال با بله و خیر تعیین شود. © نياز به توصيف كر فصلی («رهسنصه) باشد.

صفحه 7:
‎ss‏ ویژگی های درخت تصمیم ‏* برای تقریب توابع گیسته بکار می )35 ‎(cheroPiration)‏ ‎٩‏ نسبت به نویز داده های ورودی مقاوم است ‏© براى داده های با حجم بالا کاراست از اين رو درون مهظ) استفاده می شود ‏© می توان درخت را بصورت قوانین ب!<: نمایش داد که قابل فهم برای استفاده است ‏© امکان ترکیب عطفی و فصلی فرضیه ها را می دهد ‏© در مواردی که مثالهای آموزشی که فاقد همه ویژگیها هستند نیز قابل استفاده است

صفحه 8:
نحوه نمایش درخت تصمیم Outlook ‏ارتباط مستقیمی بین درخت‎ Sunny Overcast Rain ‏تصمیم ونمایش توابع منطقی‎ د دارد.درواق خت ‎a2 01‏ در ‎Humidity 1 Wind‏ تصميم تركيب فصلى كزاره هاى مر اد High Normal Strong Weak = Yes No Yes No (Outlook = Sunny \ Humidity = Normal) ۷ (Outlook = Overcast) ‏نا‎ (Outlook = Rain \ Wind = Weak) ‏مسیر از ريشه به برگ ترکیب عطفی (00060))از ویژگی ها را مشخص نموده و‎ ‏خوددرخت ترکیب فصلی((20)) اين ترکیبات را میسازد.‎

صفحه 9:

صفحه 10:

صفحه 11:

صفحه 12:
22 الگوریتم یادگیری درخت تصمیم ‎٩‏ اغلب الگوریتم های یادگیری درخت تصمیم بر پایه یک عمل جستجوی حریصانه (رلعسسی) بالا به پائین (مرسل-م) در فضای درختهای موجود عمل ميكنند. ‏© این الگوریتم پایه» (8)را0) صاصر 8) بمنسددرا اموصدو2) ناميده مى شود كه در سال (09©)0 معرفى شده است. ‏© این الگوریتم توسط بجای) عع؟) در سال 90) بصورت کاملتری تحت عنوان (109) وا مانسه() بمتص(1 مطرح گردید. ‏۶ بعدها الگوریتم کاملتر دیگری تحت عنوان ©.062 ارائه كرديد كه برخی نقائص 1609 را برطرف میکند.

صفحه 13:
ايده اصلى ©2700 © اين ايده به ۲ عمسمی) مشهور است ومی گوید : ” دنيا ذاتا ساده است* بنابراین از کوچکترین درخت تصمیم که با داده سازگار باشد انتظار می رود که مثالهای نادیده را به درستی دسته بندی کند.

صفحه 14:
:* اباياس درخت تصمیم خت ‎١‏ كوجكتر بر 5 "۳ و ری است که درختها ۳ تصميم بر اين ايده اده شود. ‎foe‏ بزرگتر ترجیح داده ‎a a‏

صفحه 15:
سئوال اگر مسئله ما دارای مب ویژگی باشد» ارتقاع درخت تصمیم چقدر خولهد بودگ جواب: درخت تصمیم دارای یک ریشه است که آن خود یک ویژگی است؛ در سئوال از آن ویژگی به پاسخی می رسیم که آن خود نیز» ویژگی است. پس حداکثر ارتفاع درخت رم خواهد بود. دینگیا ویژگی ‎a‏ ‎ym ones‏ “kins Daa oN

صفحه 16:
الگوریتم 106 ۶ در اين الگوریتم درخت تصميم از بالا به يائين ساخته ميشود. اين الكوريتم با اين سوال شروع ميشود: كدام ويزكّى بايد در ريشه درخت مورد أزمايش قرار كيرد؟ © براى يافتن جواب از يك آزمون آمارى استفاده ميشود تا مشخص كردد هر كدام تا جه حد قادر است به تنهائى مثالهاى آزمايشى را دسته بندى ‎us‏ ۶ با انتخاب این ویژگی» برای هر یک از مقادیر ممکن آن یک شاخه ایجاد شده و مثالهای آموزشی بر اساس ویژگی هر شاخه مرتب ميشوند. سپس عملیات فوف برای مثالهای قرار گرفته در هر شاخه تکرار میشوند تا بهترین ویژگی برای گره بعدی انتخاب شود. ۶ این الگوریتم یک جستجوی حریصانه است که در آن انتخاب های قبلی هرگز مورد بازبینی قرار نمیگیرند.

صفحه 17:
106 ‏الگوریتم‎ ‎ID3(Examples, Target-attribute, Attributes) Examples are the training examples. Target.atribute is the attribute whose value is to be predicted by the tree. Attributes is a list of other attributes that may be tested by the learned decision tree. Returns a decision tree that correctly classifies the given Examples. # Create a Root node for the tree ‘« If all Examples are positive, Retum the single-node tree Root, with label = + ‎If all Examples are negative, Return the single-node tree Root, with label‏ و ‎« If Attributes is empty, Return the single-node tree Root, with label = most common value of ‎Target.attribute in Examples © Otherwise Begin © A < the attribute from Attributes that best* classifies Examples @ The decision attribute for Root — A « For each possible value, vj, of A, @ Add a new tree branch below Root, corresponding to the test A = ‏ره‎ ‎© Let Examples, be the subset of Examples that have value v; for A @ If Examplesy, is empty ‘© Then below this new branch add a leaf node with label = most common value of Target-attribute in Examples ‘¢ Else below this new branch add the subtree ID3Examplesy,, Target-attribute, Attributes —{A})) ‎ ‎۰ ‏فم‎ ‎Return Root

صفحه 18:
* برای ساختن درخت تصمیم از مثالهائی استفاده میشود که علامت گذاری (اسله|) شده باشند. © درواقع ورودی سیستم یادگیر مجموعه ای از مثالهاست که هر مثال توسط مجموعه ای از ویژگی ها بیان شده است» هرویژگی می تواند دارای مجموعه متناهی ازمقادیر مختلف باشد. برای هر مثال علاوه بر ویژگیها مقدار دسته بندی آن نیز لازم می باشد. * در اين فصل با درختهای تصمیمی آشنا خواهیم شد که برای دسته بندی بو ای بکار می روند ولی درحالت کلی می توان یک درخت تصمیم ساخت که برای هر نوع دسته بندی بکار می رود.

صفحه 19:
:؟ اکدام ویژگی طبقه بندی کننده بهتری است؟ 9 در درخت تصمیم (106) از یک مقدار آماری به نام بهره اطلاعات () مسنمس_بسام" استفاده می شود تا اينکه مشخص کنیم که یک ویژگی تا چه مقدار قادر است مثالهای آموزشی را بر حسب دسته بندی آنها جدا کند.

صفحه 20:
* برای یادگیری نحوه دسته بندی مثال ساده ای را بررسی می کنیم. ‎٩‏ در مثال ذیل کدام ویژگی باید در ريشه درخت قرار گیرد؟ اه ات اه اب اه اب و اب 0 1 1 1 J 0 1 xD ‏با توجه به صفحه عبوری از مکعب زیر ,یا 0 می توانند ريشه باشند‎

صفحه 21:
© درخت کامل ما به این صورت است : این درخت کامل و پیچیده است وضمتا خطا هم ندارد. در باياس كردن هم هدف ساده كردن است كه ممكن است ايجاد خطا كند :* احل مثال : xo.

صفحه 22:
معیار کمی اندازه گیری یک ویژگی کدام *: ااست؟ © سنوال را می توان به روش دیگری نیز بیان کرد: ” بهترین ویژگی برای قرار گرفتن در ريشه درخت را چگونه باید انتخاب کنیم؟ * برای حل قعداد ‎Bight‏ 1 مثبت و منفی جدا شده ۰ ‏وواوت‎ a Me NI ‏رادر نظر ميكيريم‎

صفحه 23:
: ‏وپی‎ sil] ¢5 © میزان خلوص (بی نظمی یا عدم خالص بودن) مجموعه ای از مثالها را مشخص مى كند. إكر مجموعه 8 شامل مثالهای مثبت و منفی از یک مفهوم هدف باشد آنتروپی 9) نسبت به این دسته بندی بولی بصورت زیر تعریف می شود. Entropy(S) = — pe logy Pe — Pa logy Pa که 2 نسبت متالهای مثبت به کل مثالها و چم نسبت مثالهای منفی به کل مثالها می باشد. همچنین 0 ۷020 فرض میشود.

صفحه 24:
‎٩‏ آنتروپی و ‎xO gx‏ چقدراست؟ ‎av ‎ll ‏دراه‎ ‎2 2, 6 6 E=- Glen ae Glen 2 ‎٩‏ سئوال: اگر همه اعضاء 8) یکسان باشند آنتروپی چقدر است؟ ار

صفحه 25:
9 اگر اعضای 9) نیمی مثبت و نیمی منفی باشد آنتروپی چقدر است ؟ ¢ یک 00 9

صفحه 26:
:؟ آنتروپی برای دسته بندی های غیر بولی ۶ اگر ویژگی هدف دارای() مقدار مختلف باشد آنتروپی 9) نسبت به این دسته بندی ()گانه بصورت زیر تعریف میشود: Entropy(S) = > —p; logy pi i=l © كه در آن إم نسبتى از ‎ul G‏ که به دسته ز تعلق دارند. توجه شود که پا همچنان در مبنای 0 گرفته ميشود. در اين حالت حداکثر آنتروپی میتواند (),پ‌ط باشد.

صفحه 27:
بهره اطلاعات(<) هب-1 * بهره اطلاعات یک ویژگی عبارت است از مقدار کاهش آنتروپی که بواسطه جداسازی مثالها از طریق این ویژگی حاصل ميشود. 08 ‏بعبارت دیگر بهره اطلاعات (09,)9)-:90) برای یک ویژگی نظیر‎ ٩ ‏نسبت به مجموعه مثالهای 9) بصورت زیر تعریف میشود:‎ همم رمک > - ‎Gain(S, A) = Entropy(S)‏ ‎veValues(A)‏ ‏© که در آن (0))عصاه() مجموعه همه مقدار ویژگی های ) بوده و 5) زیرمجموعه ای از 8) است که برای آن 9) دارای مقدار () است. * در تعریف فوق عبارت اول مقدار آنتروپی داده ها و عبارت دوم مقدار آنتروپی مورد انتظار بعد از جداسازی داده هاست.

صفحه 28:
مثال و و یبد سم © با استفاده از مثا ‎oe‏ ۱۳ melee || a | ‏سم‎ lex | le eee : آموزشتی زیر درخ عن اه با سف یسم مه ane | as | ‏سمه | عه | سه‎ Sie ane بسازید که لذت بخش ‎Veo‏ هه | مهس | سم امه امن ز ها ه إمسوا بس | نه ‎are] Gara‏ ‎oS oS‏ دوهی سنا | نمست | اسم | ‎Coot‏ | سست | مه ‏با ویژگیهای مختلف ‎a‏ ات | ‎‘tik‏ سه | ‎a0] Gow‏ ‎ova | rok i ei‏ | مه | مه امه ‏رین كد شم | اس اه سم همه ‏سمه | سمه | مه | سم امه ‏مه | عه | اه أسمسة فيه ‏ممه | سس | ده امه ‏نه إسمة| سند | یه[ سم میم ‎ ‎ ‎ ‎ ‎ ‎ ‏(5/14)يعه! (5/14) - (9/14)يع0! (9/14)- ع ([-5,+9])«مه2 0.940 = ‎ ‎ ‎

صفحه 29:
OverPittary 33 * برای فرضیه ای مثل :| متعلق به فضای فرضیه را دو نوع خطا تعریف میشود: ‎٩‏ خطا روی داده های آموزشی ‎errortraici(h)‏ ‏۶ خطاروی کل داده های ممکن ‎error D(h)‏ ظ) © ميكوئيم برای فرضیه با" جل روی داده های آموزشی بسن رخ میدهد اگر فرتیه ای متن ‎kD A,‏ وجوه داشته داشد كه (0) سسسب ف ‎error alk)‏ 9 ‎ond‏ © ‎errr O(k) > error O(kO)‏ ©

صفحه 30:
100 90 On taining data (On test data ---- o 0 20 30 4 50 6 7 80 Size of tree (number of nodes) Accuracy

صفحه 31:
* الگوریتم 109 هر شاخه از درخت را آنقدر به عمق میبرد که بتواند بطور کامل مثالهای آموزشی را دسته بندی کند. این امر ‎per Pitty 5992 Jes 24 Over Pitty 42 pate at sive‏ عبارتند از: © وجود نویز در داده های آموزشی ‎٩‏ تعداد کم مثالهای آموزشی ‏* برای مثال اگر فقط دو بار پرتاب سکه داشته باشیم و هر دو بار شیر ‏آمده باشد چه نتیجه ای در مورد اين آزمایش میتوان گرفت؟

صفحه 32:
4 جلوگیری از رشد درخت قبل از رسیدن به مرحله ای که بطور کامل داده های آموزشی را دسته بندی نماید. و اجازه به رشد کامل درخت و سيس حرس كردن شاخه هانی در عمل روش دوم بیشتر استفاده شده است زیرا تخمین اندازه صحیح درخت کار ساده ای نیست.

صفحه 33:
حرس كردن درخت به روش ‎Reduced‏ ‎@rnicry‏ 0 ‎o She} SS ja 4g Nat) cual 08 441) Quicterer Jour si Gg Cul ©‏ داده میشود تا به اندازه کافی رشد کند. سپس گره هانی را که باعث افزایش دقت دسته بندی نمیشوند حرس میگردند: © داده ها به دو مجموعه تست و آموزشی نقسیم ميشوند. * درخت با داده های آموزشی مطابق روش قبل یاد گرفته میشود. ۶ سپس برای یک گره داخلی (غیر برگ » ) * زیرشاخه م حذف ميكردد شاخه با یک برگ جایگزین ميشود. به این برگ دسته مثالهای اکثریت یعنی دسته بندی اکثر مثالهای قرار گرفته تحت این شاخه نسبت داده میشود. * عملکرد درخت برروی مثالهای تست بررسی میشود: اگر درخت حرس شده عملکرد بهتر و یا مساوی با درخت فعلی داشت از درخت حرس شده استفاده ميشود. * حرس كردن آنقدر ادامه مى يابد تا حرس بيشترء سودى نداشته باشد. ‎ ‎

صفحه 34:
‎Over Pitty‏ یکپدیدم عمومی‌لست ‏پدیده ‎te ng‏ ود و تكد ل ی یادگیری ماشینی نیز با آن مواجه هستند. این پدیده غالبا وقتی اتفاق می افتد که ‎ ‎° the hypothesis space is very large ‎©» the hypothesis search is not biased toward simple models ‎° there is little training data ° there is a lot of noise in the training data ‏در عمل با دیدن شرایط زیر میتوانیم بگونیم که 0۷6۲/09 رخ داده است: ‏اختلاف زیاد بین دقت دسته بندی داده های آموزشی و داده های تست ‏۶ رسیدن به فرضیه و یا مدلهای خیلی پیچیده ( مثلا رسیدن به یک درخت تصمیم خیلی بزر:

صفحه 35:
در نظر گرفتن ویژگی های با مقادیر پیوسته * درخت یادگرفته شده توسط 160 محدود به توابع و ویژگی های با مقدار گسسته است. * برای اينکه اين الگوریتم ویژگی های با مقدار پیوسته را نیز شامل شود؛ میتوان برای یک ویژگی پیوسته مثل 0) یک ویژگی بولی مثل 92) تعریف گرد که 02) درست است اگر (9>0) باشد و در غیر اینصورت نادرست است. ‎٩‏ <) باید طورولنتخاب‌شود که بسهرم لطلاعاتوا حدلکثر کند. لینکار میتولند با مرتبک ردن‌مقادیر ویژگی9) ولنتخاب: قاطیکه مقادیر مثالهای مجاور تسغییر مپکنند لنجام شود. در چنین‌حا.لی‌میانگین‌دومثا لهجاور میتولند بعنوان‌لستانه لنتخابشود. ‎ ‎Temperaure: 40 48 | 60 72 80| 0 PlayTennis: No No /Yes. Yes Yes} No ‎ ‎ ‎(48 + 60)/2 (80 + 2 ‎ ‎

صفحه 36:
© اكر به مثال قبل يك ويؤكى به نام تاريخ اضافه شودء اين ويزكى به تنهائى قادر خواهد بود تا كليه مثالهاى آموزشى را دسته بندی کند. در واقع بعلت اينکه اين ویژگی دارای بهره اطلاعات زیادی است بعنوان ريشه درخت انتخاب خواهد شد و درخت حاصله دارای عمق بسیار کمی خواهد بود. * با وجود اينکه این درخت مثالهای آموزشی را بخوبی دسته بندی خواهد کرد اما در مورد مثالهای نادیده بسیار ضعیف عمل خواهد نمود. زیرا این درخت در عمل مثالهای آموزشی را حفظ کرده و قادر به تعمیم نیست.

صفحه 37:
معيار نسبت بهره يا صل ماكب ۶ برای پرهیز از ویژگی هائی مثل تاریخ میتوان از معيار ديكرى بانام نسبت بوره و يا ده :4 امتتقااه تموذ اكه خاصيت إن حسابسيت داشت به ابن است که یک ویژگی با چه گنترنگی و كاحت هر * برای اینکار عبارتی بصورت زیر تعریف میشود: ‎Splitinformation(S, A) = - = ie I 1‏ با استفاده از عبارت فوق نسبت بهره بصورت زير تعریف میشود: ‎Gain(S, A)‏ ‎Re (S$, A) = ‏للخخنب‎ ‎Gain Ravio(S, A) = Sita Formation(S, A)

صفحه 38:
:: امعیار نسبت بهره یا طه۲ مس © باعنمیشود تا ویژگی‌هنیکه مقادیر زیادویا توزیم. یکنولخندارند حذفگردند. ‎٩‏ برای متال یک ویژگی نظیر تاریخ برای تک تک مثالها توزیع یکسانی دارد از اینرو ,<901) خواهد شد در حالیکه اگر یک ویژگی مثالها را به دو دسته تقسیم کند 91<0) خواهد شد. ‏یک مشکل عملی استفاده ازمعیار نسبت بهره این است که ممکن است مخرج این عبارت صفر و یا خیلی کوچک شود. در اين حالت از روشهای هیوریستیک استفاده میشود.

صفحه 39:
22 اویژگی هائی با هزینه متفاوت # در بررسی پرونده یک بیمار ممکن است هزينه تست كردن برخی ‎Shes‏ ها بسیار بالا باشد و یا اينکه علیرغم موثربودن ویژگی تست آن خطرناک باشد. * در اين حالت بايد درخت را طوری بایاس کرد که ویژگی های با هزینه کم را ترجیح دهد. برای مثال ممکن است بهره را بر هزینه تقسیم نمود.

صفحه 40:
:؟ امثالهائی با ویژگی های نامعلوم ‎٩‏ در برخی از کاربردها نظیر مدارک پزشکی جمع آوری شده در بیمارستانهای مختلف ممکن است مقدار برخی از ویژگی ها درست ثبت نشده باشد. در این صورت یک انتخاب میتواند این باشد که به آن مقدار متداولترین مقدار مثالها در گره ب نسبت داده شود.

صفحه 41:
igasl Cancer Wisconsin (isanostc ۳ | eater ane 8 5 عدص دع ۳7 عتمفممتسيية بسع ‎[UCI]‏ 52171751711 سك ۳ سس 221851 25010 2524 000 نا 17 16516: Ulan characte version ‘Bond Tanstision Senice Center معا عون one Level Detection Currey wruictcics IPP dota ses us o service ty the ‏مها منطو‎ ۳7 بحاص /:صط 4 O01 Ouwhe Leorcica Ri

صفحه 42:
موضوع ارائه Puzzy devo trees ° Prontay to devisiva tree ‏سل‎ ©

یادگیری درخت تصمیم Instructor : Saeed Shiry Mitchell Ch. 3 Amirkabir University of Technology Computer Engineering & Information Technology Department مقدمه در یک مسئله یادگیری 3با دو جنبه مختلف روبرو هستیم: نحوه نمایش فرضیه ها روشی که برای یادگیری برمی گزینیم در این فصل برای نمایش فرضیه ها از درخت تصمیم استفاده میکنیم و برای یادگرفتن این درخت از روش ID3استفاده میکنیم. درخت تصمیم درختها درهوش مصنوعی برای نمایش مفاهیم مختلفی نظیر ساختار جمالت ،معادالت ،حاالت بازی ،و غیره استفاده میشود. یادگیری درخت تصمیم روشی برای تقریب توابع هدف با مقادیر گسسته است .این روش نسبت به نویز داده هامقاوم بوده وقادر است ترکیب فصلی گزاره های عطفی را یاد بگیرد. این روش جزو مشهورترین الگوریتمهای یادگیری استقرائی است که بصورت موفقیت آمیزی در کاربردهای مختلف بکار گرفته شده است. نمایش درخت تصمیم ‏ درخت تصمیم درختی است ک3ه در آن نمونه ها را به نحوی دسته بندی میکند که از ریشه به سمت پائین رشد میکنند و در نهایت به گره های برگ میرسد: ‏ ‏ ‏ ‏ هر گره داخلی یاغیر برگ ( )non leafبا یک ویژگی ( )attributeمشخص میشود. این ویژگی سوالی را در رابطه با مثال ورودی مطرح میکند. درهر گره داخلی به تعداد جوابهای ممکن با این سوال شاخه ( )branchوجود دارد که هر یک با مقدار آن جواب مشخص میشوند. برگهای این درخت با یک کالس و یا یک دسته از جوابها مشخص میشوند. علت نامگذاری آن با درخت تصمیم این است 3که این درخت فرایند تصمیم گیری برای تعیین دسته یک مثال ورودی را نشان میدهد. مثالی از یک درخت تصمیم محل درد سینه هیچکدام گلو سکته سرفه خیر بله هیچکدام تب ویروسی خیر سرماخوردگی آنفوالنزا آپاندیس تب خیر بله شکم بله باکتری •هر برگ این درخت یک کالس یا دسته را مشخص میکند. • یک مثال آموزشی در درخت تصمیم به این صورت دسته بندی میشود: •از ریشه درخت شروع میشود. •ویژگی معین شده توسط این گره تست می گردد. • و سپس منطبق با ارزش ویژگی در مثال داده شده در طول شاخه ها حرکت رو به پائین انجام می دهد. • این فرآیند برای گره های زیردرختان گره جدید تکرار می شود. کاربردها ‏ ‏ ‏ ‏ ‏ درخت تصمیم در مسایلی کاربرد دارد که بتوان آنه3ا را بصورتی م3طرح نمود که پاسخ واحدی بصورت نام یک دسته یا کالس ارائه دهند. برای م3ثال میتوان درخت تصم3یمی ساخت که به این سوال پاسخ دهد: بیماری مریض ک3دام است؟ و یا درختی ساخت که به این سوال پاسخ دهد: آیا مریض به هپاتیت مبتالست؟ برای م3سائلی مناسب است که مثالهای آموزشی بصورت زوج (م3قدار- ویژگی) مشخص شده باشند. تابع هدف دارای خروجی با مقادیر گسسته باشد .مثال هر مثال با بله و خیر تعیین شود. نیاز به توصیف گر فصلی ( )disjunctiveباشد. ویژگی های درخت تصمیم برای تقریب توابع گسسته بکار می رود ()classification نسبت به نویز داده های ورودی مقاوم است برای داده های با حجم باال کاراست از این رو درData mining استفاده می شود می توان درخت را بصورت قوانین if-thenنمایش داد که قابل فهم برای استفاده است امکان ترکیب عطفی و فصلی فرضیه ها را می دهد در مواردی که مثالهای آموزشی که فاقد همه ویژگیها هستند نیز قابل استفاده است نحوه نمایش درخت تصمیم ارتباط مستقیمی بین درخت تصمیم ونمایش توابع منطقی وجود دارد.درواقع هردرخت تصمیم ترکیب فصلی گزاره های عطفی است مسیر از ریشه به برگ ترکیب عطفی ()ANDاز ویژگی ها را مشخص نموده و خوددرخت ترکیب فصلی( )ORاین ترکیبات را میسازد. مثال ترکیب عطفی No No Outlook=Sunny AND Wind=Normal مثال ترکیب فصلی ‏OR مثال تابع XOR ‏XOR الگوریتم یادگیری درخت تصمیم ‏ ‏ ‏ ‏ اغلب الگوریتم های یادگیری درخت تصمیم بر پایه یک عم3ل جستجوی حریصانه ( )greedyباال به پائین ( )top-downدر فضای درختهای موجود عمل میکنند. این الگوریتم پایه Concept Learning System (CLS) ،نامیده می شود که در سال 1950معرفی شده است. این الگوریتم توسط Ross Quilanدر سال 1986بصورت کاملتری تحت عنوان ) Inducing Decisition trees (ID3مطرح گردید. بع3دها الگوریتم کاملتر دیگری تحت عنوان C4.5ارائه گردید که برخی نقائص ID3را برطرف میکند. ایده اصلی ID3 این ایده به Ocuum’s Razorمشهور است ومی گوید : ” دنیا ذاتا ساده است“ بنابراین از کوچکترین درخت تصمیم که با داده سازگار باشد انتظار می رود که مثالهای نادیده را به درستی دسته بندی کند. بایاس درخت تصمیم انتخاب درختهای کوچکتر بایاس درخت تصمیم بر این ایده است که درختهای کوچکتر بر درختهای بزرگتر ترجیح داده شود. سئوال اگر مسئله ما دارای mویژگی ب3اشد ،ارتفاع درخت تصمیم چقدر خ3وا3هد بو3د؟3 جواب: درخت تصمی3م دارای یک ریشه است که آن خود یک وی3ژگی 3است، در سئوال از آن ویژگی به پاسخی می رسیم که آن خود نی3ز ،وی3ژگی 3است. پس حداکثر ارتفاع درخت mخواهد بود. ویژگی1 ویژگی2 ویژگیm دستهA دستهB الگوریتم ID3 ‏ ‏ ‏ ‏ در این الگوریتم درخت 3تصمیم از باال به پائین ساخته میشود .این الگوریتم با این سوال شروع میشود :کدام ویژگی باید در ریشه درخت مورد آزمایش قرار گ3یرد؟ برای یافتن جواب از یک آزمون آم3اری استفاده م3یشود تا مشخص گردد هر کدام تا چه حد قادر است به تنهائی مثالهای آزمایشی را دسته بندی کند. با انتخاب این ویژگ3ی ،برای هر یک از مقادیر ممکن آن یک شاخه ایجاد شده و مثالهای آموزشی بر اساس ویژگ3ی هر شاخه م3رتب میشوند .سپس عملیات فوق برای مثاله3ای قرار گرفته در هر شاخه تکرار میشوند تا بهترین ویژگی برای گره بع3دی انتخاب شود. این الگوریتم یک جستجوی حریصانه است که در آن انتخاب های قبلی هرگز م3ورد بازبینی قرار نمیگیرند. الگوریتم ID3 نحوه ساختن درخت ‏ ‏ ‏ برای ساختن درخت تصمیم از م3ثالهائی استفاده میشود که عالمت گذاری ( )labelشده باشند. درواقع ورودی سیستم یادگ3یر م3جموعه ای از م3ثالهاست که هر مثال توسط مجموعه ای از ویژگ3ی ها بیان شده است ،هرویژگی می تواند دارای مجم3وعه متناهی ازمقادیر مختلف باشد .برای هر مثال عالوه بر ویژگیه3ا م3قدار دسته بندی آن نیز الزم م3ی باشد. در این فصل با درختهای تصمیمی آشنا خواهیم شد که برای دسته بندی بولی بکار می روند ولی درحالت کلی می توان یک درخت تصمیم ساخت 3که برای هر نوع دسته بندی بکار می رود. کدام ویژگی طبقه بندی کننده بهتری است؟ در درخت تصمیم ( )ID3از یک مقدار آماری به نام بهره اطالعات Information Gainاستفاده می شود تا اینکه مشخص کنیم که یک ویژگی تا چه مقدار قادر است مثالهای آموزشی را بر حسب دسته بندی آنها جدا کند. مثال ‏ ‏ برای یادگیری نحوه دسته بندی مثال ساده ای را بررسی می کنیم. در مثال ذیل کدام ویژگی باید در ریشه درخت قرار گیرد؟ ‏x2 ‏x1 ‏x0 با توجه به صفحه عبوری از مکعب زیر x0یا x2می توانند ریشه باشند حل مثال : درخت کامل ما به این صورت است : این درخت کامل و پیچیده است وضمنا خطا هم ندارد. در بایاس کردن هم هدف ساده کردن است که ممکن است ایجاد خطا کند. معیار کمی اندازه گیری یک ویژگی کدام است؟ سئوال را می توان به روش دیگری نیز بیان کرد: ” بهترین ویژگی برای قرار گرفتن در ریشه درخت را چگونه باید انتخاب کنیم؟ “ برای حل تعداد مثالهای مثبت و منفی جدا شده را در نظر میگیریم آنتروپی : میزان خلوص (بی نظمی یا عدم خالص بودن) مجموعه ای از مثالها را مشخص می کند .اگر مجموعه Sشامل مثالهای مثبت و منفی از یک مفهوم هدف باشد آنتروپی Sنسبت به این دسته بندی بولی بصورت زیر تعریف می شود. نسبت مثالهای نسبت مثالهای مثبت به کل مثالها و که منفی به کل مثالها می باشد .همچنین log0=0 0فرض میشود. مثال : ‏ آنتروپی x0و x1و x2چقدراست؟ 2 6 6 ) )  ( log2 8 8 8 2 8 ‏E  ( log2 2 8 ‏P  6 8 ‏P  سئوال :اگر همه اعضاء Sیکسان باشند آنتروپی چقدر است؟ صفر سئوال اگر اعضای S 3نیمی مثبت و نیمی منفی باشد آنتروپی چقدر است ؟ یک آنتروپی برای دسته بندی های غیر بولی اگر ویژگی هدف دارای Cمقدار مختلف باشد آنتروپی Sنسبت به این دسته بندیC 3گانه بصورت زیر تعریف میشود: که در آن piنسبتی از Sاست که به دسته iتعلق دارند .توجه شود که logهمچنان در مبنای 2گرفته میشود .در این حالت حداکثر آنتروپی میتواند log2Cباشد. بهره اطالعات()Information Gain ‏ بهره اطالعات یک ویژگی عبارت است 3از مقدار کاهش آنتروپی که بواسطه جداسازی مثالها از طریق این ویژگی حاصل میشود. بعبارت دیگر بهره اطالعات ) Gain(S,Aبرای یک ویژگی نظیر A نسبت به مجموعه مثالهای Sبصورت زیر تعریف م3یشود: ‏ ک3ه در آن ) Values(Aمجموعه همه مقدار ویژگی های Aبوده و SV زیرمجموعه ای از Sاست که برای آن Aدارای م3قدار Vاست. در تعریف فوق عبارت اول مقدار آنتروپی داده ها و عبارت دوم مقدار آنتروپی مورد انتظار بعد از جداسازی داده هاست. ‏ ‏ Day Out lo ok Temperat ure Humidit y W ind Pla y Tennis Day1 Da y2 Su nny Su nny Hot Hot High High W eak St ro ng No No Day3 Overcast Hot High W eak Yes Day4 Ra in Mild High W eak Yes Day5 Ra in Coo l No rmal W eak Yes Day6 Ra in Coo l No rmal St ro ng No Day7 Overcast Cool No rmal St ro ng Yes Day8 Su nny Mild High W eak No Day9 Su nny Coo l No rmal W eak Yes Day10 Ra in Mild No rmal W eak Yes Day11 Su nny Mild No rmal St ro ng Yes Day12 Overcast Mild High St ro ng Yes Day13 Overcast Hot No rmal W eak Yes Day14 Mild High St ro ng No Ra in مثال با استفاده از مثالهای آموزشی زیر درختی بسازید که لذت بخش بودن بازی در روزهایی با ویژگیهای مختلف .راتعیین کند Overfitting برای فرضیه ای مثل hمتعلق به فضای فرضیه Hدو نوع خطا تعریف میشود: خطا روی داده های آموزشی )errortrain(h خطا روی کل داده های ممکن )D errorD(h میگوئیم برای فرضیه h Hروی داده های آموزشی Overfitting رخ میدهد اگر فرضیه ای مثل h0 Hوجود داشته باشد که: )errortrain(h) < errortrain(h0 ‏and )errorD(h) > errorD(h0 ‏ ‏ ‏ Overfitting دالیل بروز Overfitting الگوریتم ID3هر شاخه از درخت را آنقدر به عمق میبرد که بتواند بطور کامل مثالهای آموزشی را دسته بندی کند .این امر میتواند منجر به Overfittingشود .دالیل بروز overfitting عبارتند از: وجود نویز در داده های آموزشی تعداد کم مثالهای آموزشی ‏ برای مثال اگر فقط دو بار پرتاب سکه داشته باشیم و هر دو بار شیر آمده باشد چه نتیجه ای در م3ورد این آزمایش میتوان گرفت؟ پرهیز ازOverfitting .1 .2 جلوگیری از رشد درخت قبل از رسیدن به مرحله ای که بطور کامل داده های آموزشی را دسته بندی 3نماید. اجازه به رشد کامل درخت و سپس حرس کردن شاخه هائی که مفید نیستند)post pruning( . در عمل روش دوم بیشتر استفاده شده است زیرا تخمین اندازه صحیح درخت کار ساده ای نیست. حرس کردن درخت به روش Reduced ‏Error Pruning این روش توسط Quinlanارائه شده است .ابتدا به درخت اجازه داده میشود تا به اندازه کافی رشد کند .سپس گره هائی را که باعث افزایش دقت دسته بندی نمیشوند حرس میگردند: ‏ ‏ ‏ داده ها به دو مجموعه تست و آموزشی تقسیم میشوند. درخت با داده های آموزشی مطابق روش قبل یاد گرفته میشود. سپس برای یک گره داخلی (غیر برگ ) n ‏ ‏ ‏ زیرشاخه nحذف میگردد .این زیر شاخه با یک برگ جایگزین میشود .به این برگ دسته مثالهای اکثریت یعنی دسته بندی اکثر مثالهای قرار گرفته تحت این شاخه نسبت داده میشود. عملکرد درخت برروی مثالهای تست بررسی میشود :اگر درخت حرس شده عملکرد بهتر و یا مساوی با درخت فعلی داشت از درخت حرس شده استفاده میشود. حرس کردن آنقدر ادامه می یابد تا حرس بیشتر ،سودی نداشته باشد. Overfittingی33کپ333دیده 3عمومیا3ست پدیده overfittingمنحصر به درخت های تصمیم نیست و سایر روشهای یادگیری ماشینی نیز با آن مواجه هستند .این پدیده غالبا وقتی اتفاق می افتد که: ‏the hypothesis space is very large ‏the hypothesis search is not biased toward simple ‏models ‏there is little training data ‏there is a lot of noise in the training data ‏ ‏ ‏ ‏ در عمل با دیدن شرایط زیر میتوانیم بگوئیم که overfittingرخ داده است: اختالف زیاد بین دقت دسته بندی داده های آموزشی و داده های تست رسیدن به فرضیه و یا مدلهای خیلی پیچید3ه ( مثال رسیدن به یک درخت تصمیم خیلی بزرگ) در نظر گرفتن ویژگی های با مقادیر پیوسته ‏ ‏ ‏ درخت یادگرفته شده توسط ID3محدود به توابع و ویژگی های با مقدار گسسته است. برای اینکه این الگوریتم ویژگی های با مقدار پیوسته را نیز شامل شود، میتوان برای یک ویژگی پیوسته مثل Aیک ویژگ3ی بولی مثل Ac تعریف گرد که Acدرست است اگر A<Cباشد و در غیر اینصورت نادرست است. Cب333اید طوریا3نتخابش33ود ک333ه 3ب333ه3ره 3ا3طالعاترا ح3دا3ک3ثر ک333ند .ا3ینکار میتوا3ند ب333ا مرتبک333ردنمقادیر ویژگ3ی Aوا3نتخابن 3ق3اطیک333ه 3مق3ادیر مثا33له3ای مجاور ت333غییر میکنند ا3نجام 3ش33ود .در چنینح3ا33لتیمیانگیندوم3ثا33لمجاور میتوا3ند ب333عنوا3نآ3ستانه 3ا3نتخابش33ود. سایر معیارهای انتخاب ویژگی برای درخت اگر به مثال قبل یک ویژگی به نام تاریخ اضافه شود ،این ویژگی به تنهائی قادر خواهد بود تا کلیه مثالهای آموزشی را دسته بندی کند .در واقع بعلت اینکه این ویژگی دارای بهره اطالعات زیادی است بعنوان ریشه درخت انتخاب خواهد شد و درخت حاصله دارای عمق بسیار کمی خواهد بود. با وجود اینکه این درخت مثالهای آموزشی را بخوبی دسته بندی خواهد کرد اما در مورد مثالهای نادیده بسیار ضعیف عمل خواهد نمود .زیرا این درخت در عمل مثالهای آموزشی را حفظ کرده و قادر به تعمیم نیست. معیار نسبت بهره یا gain ratio برای پرهیز از ویژگی هائی مثل تاریخ میتوان از معیار دیگری با نام نسبت بهره و یا gain ratioاستفاده نمود که خاصیت آن حساسیت داشتن به این است که یک ویژگی با چه گستردگی و یکنواختی داده ها را جدا میکند. برای اینکار عبارتی بصورت زیر تعریف میشود: با استفاده از عبارت فوق نسبت بهره بصورت زیر تعریف میشود: معیار نسبت بهره یا gain ratio SI ب333اعثمیشود ت333ا ویژگ3یهائیک333ه 3مق3ادیر زیادیب333ا ت333وزیع3 ی33کنوا3ختدارند ح3ذفگ333ردند. برای مثال یک ویژگی نظیر تاریخ برای تک تک مثالها توزیع یکسانی دارد از اینرو SI=logn2خواهد شد در حالیکه اگر یک ویژگی مثالها را به دو دسته تقسیم کند SI=1خواهد شد. یک مشکل عملی استفاده ازمعیار نسبت بهره این است که ممکن است مخرج این عبارت صفر و یا خیلی کوچک شود. در این حالت از روشهای هیوریستیک استفاده میشود. ویژگی هائی با هزینه متفاوت در بررسی پرونده یک بیمار ممکن است هزینه تست کردن برخی ویژگی ها بسیار باال باشد و یا اینکه علیرغم موثربودن ویژگی تست آن خطرناک باشد. در این حالت باید درخت را طوری بایاس کرد که ویژگی های با هزینه کم را ترجیح دهد .برای 3مثال ممک3ن است بهره را بر هزینه تقسیم نمود. مثالهائی با ویژگی های نامعلوم در برخی از کاربردها نظیر مدارک پزشکی جمع آوری شده در بیمارستانهای مختلف ممکن است مقدار برخی از ویژگی ها درست ثبت نشده باشد .در این صورت یک انتخاب میتواند این باشد که به آن مقدار متداولترین مقدار مثالها در گره nنسبت داده شود. UCI Machine Learning Repository  Currently maintains 177 data sets as a service to the machine learning community.  http://archive.ics.u ci.edu/ml/ موضوع ارائه fuzzy decision trees  pruning in decision tree induction 

39,000 تومان

خرید فایل توسط کلیه کارت‌های شتاب امکان‌پذیر است و بلافاصله پس از خرید، لینک دانلود فایل در اختیار شما قرار خواهد گرفت.

در صورت عدم رضایت سفارش برگشت و وجه به حساب شما برگشت داده خواهد شد.

در صورت نیاز به شماره 09353405883 در ایتا و واتساپ پیام دهید.

39,000 تومان