آشنایی با درخت های تصمیم گیری

آشنایی با درخت های تصمیم گیری

اسلاید 1: آشنايي با درخت هاي تصميم گيريارائه دهنده:احمد نيك آبادي8313177استاد:دکتر شيريبهار 84

اسلاید 2: 2فهرست مطالبمقدمهطراحي درخت تصميم گيريپرسش هاي مطرح براي درخت تصميم گيري (CART)الگوريتم يادگيري درخت ID3، C4.5يادگيري افزايشي درخت هاي تصميم گيريکاربرد درخت هاي تصميم گيري

اسلاید 3: 3مقدمه

اسلاید 4: 4مقدمهبردار ويژگي: دوتايي (X,Y) بيانگر بردار ويژگي (الگو) X است و Y برچسب كلاس مربوطه است. اجزاء X همان ويژگي‌هاي مورد نظر هستند.الگوي مرتب: اگر ويژگي‌هاي X داراي مقاديري از يك مجموعه مرتب باشند، X را يك الگوي مرتب (orderd)يا عددي(numerical) مي‌ناميم .الگوي حتمي: اگر ويژگي‌هاي بردار مقاديري اختيار كنند كه داراي ترتيب طبيعي نباشند، آن را يك الگوي حتمي (Categorical) مي‌نامند.ويژگي‌هاي عددي (مرتب) ممكن است داراي مقادير گسسته يا پيوسته باشند.روش هاي دسته بندي:تك مرحله ايچند مرحله ايمقادير ويژگي ها:پيوستهگسسته

اسلاید 5: 5معرفي درخت تصميم گيري و برخي تعاريف مورد نيازنمايي از يك درخت تصميم گيري:

اسلاید 6: 6معرفي درخت تصميم گيري و برخي تعاريف مورد نيازميانگين تعداد لايه‌ها از ريشه تا گره‌هاي پاياني را عمق متوسط مي‌ناميم.ميانگين تعداد گره‌هاي مياني در هر سطح درخت عرض متوسط درخت ناميده مي‌شود.اگر دو گره داخلي حداقل داراي يك كلاس مشترك باشند در اين حالت گفته مي‌شود كه كلاس‌ها داراي روي هم افتادگي (Overlap) هستند.

اسلاید 7: 7معرفي درخت تصميم گيري و برخي تعاريف مورد نيازنحوة انتساب كلاس به يك بردار ورودي در درخت تصميم گيري:بردار ورودي در گره ريشه قرار مي گيريد.بردار ورودي در هر گرهي كه قرار مي گيرد با توجه به ارزيابي انجام شده در يكي از شاخه ها پايين مي رود تا در يك برگ قرار بگيرد.برچسب برگي كه گره در آن قرار مي گيرد به عنوان برچسب بردار برگردانده مي شود.

اسلاید 8: 8معرفي درخت تصميم گيري و برخي تعاريف مورد نيازمزايا:قوانين توليد شده و به كارگرفته شده قابل استخراج و قابل فهم.کار با داده هاي پيوسته و گسسته.استفاده از نواحي تصميم گيري ساده.حذف مقايسه هاي غيرضروري.استفاده از ويژگي هاي متفاوت براي نمونه هاي مختلف. احتياجي به تخمين تابع توزيع نيست.

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

اسلاید 10: 10طراحي درخت تصميم گيري

اسلاید 11: 11طراحي درخت تصميم گيرياهداف اصلي درخت‌هاي تصميم‌گيري دسته‌بندي كننده:داده‌هاي ورودي را تا حد ممكن درست دسته‌بندي كنند.دانش آموخته شده از داده‌هاي آموزشي را به گونه‌اي عموميت ببخشند كه داده‌هاي ديده نشده را با بالاترين دقت ممكن دسته‌بندي كنند.در صورت اضافه شدن داده‌هاي آموزشي جديد بتوان به راحتي درخت تصميم‌گيري را گسترش داد(داراي خاصيت افزايشي باشند).ساختار درخت حاصل به ساده‌ترين شكل ممكن باشد.

اسلاید 12: 12طراحي درخت تصميم گيريگام‌هاي لازم براي طراحي يك درخت تصميم‌گيري:انتخاب مناسبي براي ساختار درخت.انتخاب ويژگي‌هايي مورد نظر براي تصميم‌گيري در هر يك از گره‌هاي مياني.انتخاب قانون تصميم‌گيري يا استراتژي مورد استفاده در هر يك از گره‌هاي مياني.

اسلاید 13: 13طراحي درخت تصميم گيريروش‌هاي هيوريستيك ساخت درخت تصميم‌گيري:روش‌هاي پايين به بالاروش‌هاي بالا به پايينروش تركيبيروش‌هاي رشد دهنده-هرس كننده

اسلاید 14: 14طراحي درخت تصميم گيريروش‌هاي پايين به بالا:درخت تصميم گيري از پايين به بالا با حركت از برگ ها به سمت ريشه ساخته مي شود.در هر مرحه دو يا چند كلاس بر اساس معياري با يكديگر تركيب مي شوند.فرآيند تركيب كلاس ها تا زماني كه تنها يك كلاس باقي بماند ادامه مي يابد.

اسلاید 15: 15طراحي درخت تصميم گيريروش‌هاي بالا به پايين :در روش‌هاي بالا به پايين براي طراحي درخت تصميم‌گيري سه كار زير انجام مي گيرد:انتخاب يك قانون براي تقسيم گره‌ها.تصميم‌گيري در مورد اينكه چه گره‌هايي گره پاياني هستند.انتساب برچسب كلاس به گره‌هاي پاياني.اكثر كارهاي انجام شده در زمينه درخت هاي تصميم گيري روش هاي بالا به پايين هستند.نمونه الگوريتم هاي بالا به پايين:ID3، ID4، ID5R، C4.5، CART

اسلاید 16: 16طراحي درخت تصميم گيريروش هاي رشد دهنده-هرس كننده:در اين روش ابتدا درخت تصميم گيري با استفاده از روشي همچون يك روش بالا به پايين ساخته مي شود.در مرحله بعد با استفاده از يك الگوريتم هرس شاخه هاي اضافي درخت حذف مي شوند.الگوريتم CART از جمله اين الگوريتم هاست.الگوريتم C4.5 نيز داراي يك الگوريتم هرس مي باشد.

اسلاید 17: 17طراحي درخت تصميم گيريروش هاي تركيبي:در اين روش ها از هر دو روش بالا به پايين و پايين به بالا استفاده مي شود.

اسلاید 18: 18پرسش هاي مطرح براي درخت تصميم گيري (CART)

اسلاید 19: 19پرسش هاي مطرح براي درخت تصميم گيري CARTالگوريتم ساخت درخت CART:Classification And Regression Trees (CART)Bereiman(1983)ارائه نرم افزاري با همين نام كه اين الگوريتم را پياده سازي مي كند توسط Salford Systems الگوريتم هاي ديگري مشابه الگوريتم CART پياده سازي شده و نشان داده شده كه از CART بهتر عمل مي كنند.

اسلاید 20: 20پرسش هاي مطرح براي درخت تصميم گيري CARTبراي ساخت درخت تصميم گيري با استفاده از الگوريتم CART و بسياري از الگوريتم هاي ديگر ساخت درخت بايد به پرسش هاي زير پاسخ داد:ويژگي‌ها به مقادير دوتايي محدود مي‌شوند يا مي‌توانند چند مقدار داشته باشند؟ تعداد مقادير ويژگي‌ها تعداد خروجي‌هاي هر گره را مشخص مي‌كند.در هر گره چه ويژگي بايد ارزيابي شود؟چه موقع يك گره را به عنوان گره پاياني اعلام كنيم؟اگر درخت تصميم‌گيري خيلي بزرگ شد چگونه مي‌توان آن را كوچكتر (ساده‌تر) كرد؟ پاسخ اين پرسش الگوريتم هرس را مشخص مي‌كند.اگر يك برگ درخت داراي ناخالصي بود چه برچسب كلاسي به آن نسبت داده مي‌شود؟با نمونه‌هايي كه مقدار برخي ويژگي‌هاي آنان معلوم نيست چگونه برخورد شود؟

اسلاید 21: 21پرسش هاي مطرح براي درخت تصميم گيري CARTتعداد انشعابانتساب برچسب كلاس به برگ‌هانمونه‌هايي كه مقادير برخي ويژگي‌هاي آنان مشخص نيست

اسلاید 22: 22پرسش هاي مطرح براي درخت تصميم گيري CARTانتخاب ارزيابي و ناخالصي گره:معيارهاي اندازه گيري ناخالصي بايد داراي ويژگي هاي زير باشند:در صورتي كه كليه داده‌هاي يك گره به يك كلاس تعلق داشته باشند بايد مقدار آن صفر شود.در صورتي كه داده‌ها به صورت مساوي بين تمام كلاس‌هاي موجود تقسيم شده باشند بايد بيشترين مقدار خود را داشته باشد. برخي روش هاي اندازه گيري ناخالصي:ناخالصي انتروپي ناخالصي Gini ناخالصي دسته‌بندي اشتباه

اسلاید 23: 23پرسش هاي مطرح براي درخت تصميم گيري CARTنمودار مقادير معيارهاي مختلف ناخالصي براي حالت دو كلاسه

اسلاید 24: 24پرسش هاي مطرح براي درخت تصميم گيري CARTدر هر گره از چه ارزيابي براي تقسيم داده‌ها استفاده كنيم؟با داشتن رابطه‌اي كه با استفاد از آن بتوان ناخالصي داده‌ها را اندازه‌گيري كرد به دنبال ارزيابي مي‌گرديم كه ناخالصي داده‌ها را تا حد ممكن كاهش دهد. براي اندازه‌گيري ميزان كاهش ناخالصي در موراد دو كلاسه از رابطه استفاده مي‌كنيم. در اين رابطه NL و NR به ترتيب بيانگر گره‌هاي چپ و راست ايجاد شده در نتيجه ارزيابي در گره فعلي و PL احتمال قرار گرفتن نمونه در گره چپ است.

اسلاید 25: 25پرسش هاي مطرح براي درخت تصميم گيري CARTچه موقع تقسيم گره‌ها را خاتمه دهيم؟برازش بيش از حد (overfitting)برخي روش هاي مورد استفاده براي پايان دادن به تقسيم ها:وارسي اعتبار : هر زمان كه خطاي دسته‌بندي براي داده‌هاي ارزيابي از يك حد از پيش تعيين شده كمتر شد آموزش (تقسيم گره‌ها) را خاتمه مي‌دهيم. حد آستانه براي تغييرات ناخالصي: اگر بهترين انتخابي كه براي ارزيابي وجود دارد، ناخالصي را از يك حد آستانه كمتر كاهش ‌دهد، تقسيم در آن گره را خاتمه مي‌دهيم.

اسلاید 26: 26پرسش هاي مطرح براي درخت تصميم گيري CARTهرس كردن درخت تصميم‌گيري:پديده horizon effect : گاهي اوقات متوقف شدن تقسيم نمونه‌ها در يك گره و اعلام گره به عنوان برگ به دليل فقدان پيش‌بيني در مورد ميزان مطلوبيت تقسيم‌هاي گره‌هاي بعدي است. رويه ديگري كه در مقابل روش متوقف ساختن تقسيم به كار گرفته مي‌شود، هرس كردن درخت است. در اين روش ابتدا درخت تصميم‌گيري را تا حد ممكن گسترش مي‌دهيم تا به كمترين مقادير ناخالصي در برگ‌ها برسيم. سپس به بررسي دو برگ مجاور (داراي پدر يكسان) مي‌پردازيم كه آيا مي‌توان اين دو برگ را با يكديگر تركيب كرد يا خير.

اسلاید 27: 27پرسش هاي مطرح براي درخت تصميم گيري CARTالگوريتم هرس CART: فرض كنيد مقدار را از رابطهبدست مي‌آوريم. كه در آن نرخ دسته‌بندي اشتباه در گره t است كه با استفاده از رابطه محاسبه مي‌شود.فرض كنيد زيردرختي با ريشه t باشد و از رابطه محاسبه شود. كه در آن ثابتي است كه پيچيدگي درخت تصميم‌گيري را به ازاء هر گره پاياني بيان مي‌كند و مجموعه گره‌هاي پاياني زير درخت است. تخميني از نرخ دسته‌بندي اشتباه و پيچيدگي درخت ارائه مي‌كند.

اسلاید 28: 28اگر آنگاه پيچيدگي هزينه زير درخت كمتر از گره t خواهد بود. اين امر براي مقادير كم رخ مي‌دهد. با افزايش اين رابطه تا زماني درست خواهد بود كه كه در آن تعداد گره‌هاي پاياني زيردرخت است. در نهايت مقدار را به شكل زير محاسبه مي کنيم.براي هرس كردن درخت در هر مرحله مقدار g(t) را براي تمام گره‌هاي غير برگ محاسبه مي‌كنيم. تا زماني كه حداقل اين مقدار براي گره‌ها از مقدار آستانه‌اي كمتر است، گره مياني با كمترين مقدار g(t) را به عنوان برگ اعلام مي‌كنيم و مقدار g(t) تمام گره‌هاي پدر آن تا ريشه را مجدداً محاسبه مي‌كنيم.

اسلاید 29: 29پرسش هاي مطرح براي درخت تصميم گيري CARTالگوريتم يادگيري درخت ID3، C4.5

اسلاید 30: 30الگوريتم يادگيري درخت ID3، C4.5الگوريتم ID3:1986 – Quinlanبالا به پايينپايه بسياري از الگوريتم هاي يادگيري درختجستجوي حريصانه اي را براي درخت تصميم گيري بهينه انجام مي دهد.الگوريتم C4.5:1993 – Quinlanحاصل اعمال برخي بهبودها در الگوريتم ID3 (كار با داده هاي پيوسته، كار با ويژگي هاي بدون مقدار و ... )الگوريتم C5:

اسلاید 31: 31الگوريتم يادگيري درخت ID3، C4.5الگوريتم ID3:كار كردن با مثال‌هاي آموزشي داراي صفات بدون مقداركار با صفات داراي مقادير پيوستهكدام صفت بهترين دسته‌بندي كننده است؟مشكل معيارِ اندازه‌گيري بهره اطلاعاتيمقياس‌‌ ديگر براي انتخاب صفاتنسبت بهره (Quinlan 1986, C4.5):

اسلاید 32: 32الگوريتم يادگيري درخت ID3، C4.5كار با صفات داراي هزينه‌هاي متفاوت:گاهي اوقات ويژگي هاي مختلف داراي هزينه‌ محاسبه متفاوتي هستند.مي‌توان با اضافه كردن عبارت هزينه در مقياس انتخاب صفات ID3 را به گونه‌اي تغيير داد كه هزينه صفات را نيز در نظر بگيرد.پيشنهادي ارائه شده (جريمه كردن ويژگي با هزينه آن):Tan و Schlimmer (1990) و Tan (1993) :Nunez (1988)

اسلاید 33: 33الگوريتم يادگيري درخت ID3، C4.5ايجاد پنجره در ID3روشي براي برخورد با داده‌هاي آموزشي بسيار زياد بدون استفاده از تكنيك ايجاد پنجره الگوريتم‌هاي فوق بسيار كند عمل خواهند كرد نمونه‌اي از يك الگوريتم يادگيري به شكل زير است:زيرمجموعه‌اي از نمونه‌هاي آموزشي را به تصادف انتخاب كنيد.الگوريتم ID3 را بر روي نمونه‌هاي آموزشي انتخاب شده اجرا و درخت تصميم‌گيري حاصل را بدست آوريد.كليه نمونه‌هاي آموزشي را با استفاده از درخت به دست آمده دسته‌بندي كنيد. نمونه‌هاي آموزشي را كه اشتباه دسته‌بندي شده‌اند در مجموعه‌اي همانند E قرار دهيد.در صورتي كه E تهي بود الگوريتم خاتمه مي‌يابد.زير مجموعه نمونه‌هاي آموزشي (S) را برابر با اجتماع S و E قرار بده.به گام 2 برو و الگوريتم ID3 را براي زيرمجموعه نمونه‌هاي آموزشي جديد اجرا كن.

اسلاید 34: 34يادگيري افزايشي درخت هاي تصميم گيري

اسلاید 35: 35يادگيري افزايشي درخت هاي تصميم گيرييادگيري درخت تصميم گيري:غير افزايشي: الگوريتم درخت تصميم گيري مورد نظر را در يك بار آموزش با داده‌هاي آموزشي ياد مي‌گيرد. افزايشي: با دريافت هر نمونه آموزشي جديد در صورتي كه لازم باشد، الگوريتم، درخت يادگرفته شده را بازبيني مي‌كند و ممكن است آنچه را كه ياد گرفته است بهبود بخشد. ويژگي هاي الگوريتم افزايشي خوب:حافظه مورد نياز كم.سرعت بازسازي بالاي درخت.توليد درختي مناسب نسبت به روش هاي غيرافزايشي.الگوريتم هاي CART و ID3 كه تا اينجا ديديم همگي الگوريتم هاي غير افزايشي بودند.برخي الگوريتم هاي افزايشي ساخت درخت:ID3’ID4ID5R

اسلاید 36: 36يادگيري افزايشي درخت هاي تصميم گيريالگوريتم ID3’:ساده ترين ساخت درخت تصميم گيري به صورت افزايشي است.كليه نمونه هاي آموزشي را نگهداري مي كند و با دريافت هر نمونه جديد الگورتيم ساخت درخت را از ابتدا اجرا مي كند.ويژگي ها:حافظه مورد نياز زياد.سرعت كم.درختي مشابه درخت ID3 ايجاد مي كند!

اسلاید 37: 37يادگيري افزايشي درخت هاي تصميم گيريالگوريتم ID4:اساس کار اين الگوريتم دسته بندي ورودي جديد و خراب کردن زيردرختي است که بهترين صفت برا ي ارزيابي در آن انتخاب نشده باشد.ويژگي ها:اين الگوريتم ساخت درختي مشايه درخت ID3 را تضمين نمي كند.در برخي موارد قادر به يافتن درخت مناسب نيست.

اسلاید 38: 38يادگيري افزايشي درخت هاي تصميم گيريالگوريتم ID5R:تضمين مي‌كند كه با استفاده از داده‌هاي آموزشي يكسان درخت حاصل از آن مشابه درخت توليدي الگوريتم ID3 خواهد بود. تفاوت اين الگوريتم با ID4 در روش تغيير ويژگي ارزيابي در يك گره است. به جاي آنكه زير درخت مربوط به گرهي كه قرار است ويژگي مورد ارزيابي آن تغيير كند كلاً خراب شود، اين زير درخت را به گونه‌اي بازسازي مي‌كند كه ويژگي مورد نظر در ريشه قرار بگيرد. شامل دو الگوريتم به روز رساني درخت و بازسازي است.براي بازسازي درخت، اين الگوريتم در هر گره تعداد نمونه هاي هر يك از كلاس ها را براي هر يك از مقادير ويژگي ها نگهداري مي كند. به متغيرهاي نگهدارنده هر يك از اين مقادير «شمارنده مورد» گفته مي شود.

اسلاید 39: 39يادگيري افزايشي درخت هاي تصميم گيريالگوريتم به روزرساني درخت ID5Rاگر درخت خالي است، درخت را به عنوان يك گره تنها تعريف كن. برچسب گره را برچسب داده آموزشي جديد قرار بده و مجموعه موارد را نيز مجموعه‌اي شامل تنها داده آموزشي ارائه شده قرار بده.در غير اين صورت اگر درخت گسترش داده نشده است و برچسب داده آموزشي جديد با برچسب گره يكي است، داده آموزشي جديد را به مجموعه داده‌هاي گره اضافه كن.در غير اين صورتاگر درخت گسترش داده نشده است، آن را با انتخاب يك صفت دلخواه براي ريشه، يك سطح گسترش بده.تعداد موارد مثبت و منفي را به ازاء مقادير ويژگي‌هاي داده آموزشي جديد براي صفت ارزيابي و كليه صفات ديگر در گره فعلي به روز رساني كن.اگر در گره فعلي بهترين ويژگي براي ارزيابي انتخاب نشده است،درخت را به گونه‌اي بازسازي كن كه ويژگي مورد نظر در ريشه مورد ارزيابي قرار بگيرد.به صورت بازگشتي بهترين ويژگي براي ارزيابي در هر يك از زير درخت‌ها –بجز زير درختي كه در گام d به روزرساني مي‌شود- را انتخاب كن.زير درختي از گره جاري كه داده آموزشي در آن قرار مي‌گيرد را به صورت بازگشتي به روزرساني كن و در صورت لزوم آن را گسترش بده.

اسلاید 40: 40يادگيري افزايشي درخت هاي تصميم گيريالگوريتم بازسازي ID5R :اگر ويژگي مورد نظر هم اكنون در ريشه باشد، آنگاه الگورتيم خاتمه مي‌يابد.در غير اين صورت:به صورت بازگشتي هر يك از زير درخت‌هاي گره فعلي را با انتخاب ويژگي مورد نظر به عنوان ويژگي ارزيابي بازسازي كن. در مواردي كه لازم است، درخت را گسترش بده.ويژگي انتخاب شده را در ريشه و ويژگي قبلي را در ريشه هر يك از زيردرخت‌هاي قبلي قرار بده.

اسلاید 41: 41يادگيري افزايشي درخت هاي تصميم گيريمثالي از به كارگيري الگوريتم ID5R :مجموعه داده هاي مورد استفاده براي ساخت درخت:

اسلاید 42: 42يادگيري افزايشي درخت هاي تصميم گيرينمونه جديد:درخت حاصل:

اسلاید 43: 43يادگيري افزايشي درخت هاي تصميم گيرينمونه جديد:درخت حاصل:

اسلاید 44: 44يادگيري افزايشي درخت هاي تصميم گيرينمونه جديد:درخت حاصل:

اسلاید 45: 45يادگيري افزايشي درخت هاي تصميم گيرينمونه جديد:درخت حاصل:

اسلاید 46: 46يادگيري افزايشي درخت هاي تصميم گيرينمونه جديد:درخت حاصل:

اسلاید 47: 47يادگيري افزايشي درخت هاي تصميم گيرينمونه جديد:درخت حاصل:

اسلاید 48: 48يادگيري افزايشي درخت هاي تصميم گيريدرخت حاصل را مي توان به شكل فشرده زير نيز ارائه كرد اما اين كار در الگوريتم ID5R انجام نمي شود.

اسلاید 49: 49يادگيري افزايشي درخت هاي تصميم گيريبرررسي پيچيدگي الگوريتم هاي معرفي شده:پيچيدگي الگوريتم ها بر اساس تعداد نمونه هاي آموزشي (n) است.دو معيار ارزيابي تعداد افزايش هاي شمانده هاي مورد و محاسبه ارزش تقسيم هستند.

اسلاید 50: 50کاربرد درخت هاي تصميم گيريمسائل دسته بندیUsing Decision Tree Confidence Factors for Multi agent Control

اسلاید 51: 51مراجع[1] S. R. Safavian, and D. Landgrebe, “A Survey of Decision Tree Classifier Methodology,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 3, pp 660-674, May 1991.[2] R. Duda, and P.E. Hart, Pattern Classification and Scene Analysis, Wiley, 1978.[3] A. Webb, Statistical Pattern Recognition, Second Edition, Wiley, 2002.[4] T. M. Mitchel, Machine Learning, McGraw-Hill, 1997.[5] P. E. Utgoff, “Incremental induction of decision tress,” Machine Learning vol. vol. 4, pp.161-186, 1989.[6] P. Stone, M. Veloso, “Using Decision Tree Confidence Factors for Multi agent Control”, 1998.