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

صفحه 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 ‏سل‎ ©