دسته بندی کننده ها

دسته بندی کننده ها

اسلاید 1: Popular Ensemble Methods: An Empirical Study گروه مهندسي کامپيوتر و فناوری اطلاعات دانشگاه کردستانPopular Ensemble Methods: An Empirical Studyاستاد راهنما: دکتر کیومرث شیخ اسماعیلیارائه دهنده: شهرام رحمانیرحیم شیخیمصطفی اعظمیبه نام خداG7

اسلاید 2: 2مقدمهاصل ”نهار مجانی وجود ندارد“(No Free Lunch Theorem) بیان میدارد که:هیچ الگوریتمی وجود ندارد که برای تمامی مسائل و در تمامی زمانها بهترین ( دقیق ترین) یادگیر را بوجود آورد.ایده:اگر تعدادی یادگیر پایه داشته باشیم میتوان با ترکیب نتایج آنها به دقت بالاتری رسید.این یادگیرها ممکن است در موارد زیر با هم متفاوت باشند:الگوریتم: که باعث میشود فرضیات مختلفی در مورد داده استفاده شود.پارامترها: مثل تعداد گره های مختلف لایه پنهان شبکه های عصبی و یا K متفاوت در KNNنحوه نمایش: استفاده از تعداد متفاوت ویژگی برای هر یادگیر، استفاده از مجموعه داده متفاوتمجموعه آموزشی: داده های آموزشی یادگیرها اندکی با هم تفاوت داشته باشند.

اسلاید 3: 3ترکیب دسته بندی کننده هاروشهای مختلفی برای ترکیب نتایج دسته بندی کننده ها وجود دارد:متداولترین روشها میانگین گیری و یا استفاده از رای اکثریت هستندانگیزه اصلی این کار در اینجاست که:ما هنگام طراحی یک سیستم یادگیر انتخاب های فراوانی داریم: نحوه نمایش، پارامترهای یادگیر، داده های آموزشی و غیره. این تنوع باعث میشود که نوعی از واریانس در عملکرد سیستم وجود داشته باشد. در نتیجه اگر سیستم های مختلفی داشته و از نتایج آنها استفاده شود این امکان وجود دارد که توزیع خطا حول هدف متمرکز شده و با افزایش نمونه گیری از این توزیع به نتیجه بهتری برسیمd1d2d3d4d5Final outputinput

اسلاید 4: Simple Majority Voting4

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

اسلاید 6: 6انواع ترکیب دسته بندی کننده هاStatic structures پاسخ چندین خبره بدون در نظر گرفتن سیگنال ورودی با هم ترکیب میشوند.ensemble averagingخروجی خبره های مختلف بصورت خطی با هم ترکیب شده و خروجی جمعی را بوجود می آوردboostingیک یادگیر ضعیف طوری تغییر داده میشود تا به دقت بالائی برسد.Dynamic structuresدر این روش سیگنال ورودی در انتخاب مکانیسم ترکیب خبره ها تاثیر میگذارد.mixture of expertsخروجی خبره ها توسط یک شبکه Gating network بصورت غیر خطی با هم ترکیب میشوند.hierarchical mixture of expertsخروجی خبره ها توسط چندین شبکه Gating network که بصورت سلسله مراتبی قرار داده شده اند بصورت غیر خطی با هم ترکیب میشوند.

اسلاید 7: 7Ensemble Methods

اسلاید 8: 8Ensemble Averaging

اسلاید 9: اگر چندین خبره با بایاس و واریانس یکسان، از طریق روش ensemble-averaging با هم ترکیب شوند: بایاس سیستم حاصل مشابه بایاس هر یک از خبره ها خواهد بود.واریانس سیستم حاصل کمتر از واریانس هر یک از خبره ها خواهد بود.خطای میانگین سیستم حاصل کمتر از خطای میانگین هر یک از خبره ها خواهد بود.9نتیجه گیری در موردEnsemble Averaging

اسلاید 10: 10مثال در این مثال خروجی 10 شبکه با هم ترکیب شده اند. میانگین Ensemble توانسته به خطای مورد انتظاری که کمتر از خطای میانگین شبکه های منفرد است (eD) برسد.80.3% درصد صحت دسته بندی کننده ترکیبی در مقابل79.4% میانگین دسته بندی کننده منفرد%1 اختلاف

اسلاید 11: 11روش Baggingاین روش نیز مبتنی بر رای گیری است با این تفاوت که یادگیرهای پایه با داده های آموزشی متفاوتی آموزش داده میشوند تا اندکی با هم تفاوت داشته باشند. در نتیجه در حالی که این یادگیرها بدلیل آموزش از مجموعه اصلی مشابه هم خواهند بود بدلیل انتخاب تصادفی نمونه های آموزشی اندکی با هم اختلاف نیز خواهند داشت.Bagging (Bootstrap Aggregating) - Breiman, 1996take a training set D, of size Nfor each network / tree / k-nn / etc…- build a new training set by sampling N examples, randomly with replacement, from D- train your machine with the new dataset end foroutput is average/vote from all machines trained

اسلاید 12: 12مثال روش Bagging برای الگوریتمهای یادگیر ناپایدار یعنی الگوریتمهائی که با تغییر داده دچار تغییر در نتیجه میشوند عملکرد خوبی خواهد داشت. ( شبکه عصبی و درخت تصمیم نمونه ای از این الگوریتمها هستند. در حالیکه KNN پایدار است.)

اسلاید 13: Bagging13

اسلاید 14: Bagging14

اسلاید 15: Boostingاگر یادگیرهای پایه مشابه هم باشند ترکیب آنها نتیجه متفاوت محسوسی نخواهد داشت. بهتر است که یادگیرها تصمیم گیری متفاوتی داشته و مکمل یکدیگر باشند.در Boosting سعی میشود تا تعدادی یادگیر پایه ضعیف که مکمل هم باشند تولید شده و آنها را با اشتباه یادگیر قبلی آموزش داد.منظور از یادگیر ضعیف این است که یادگیر فقط کافی است که یک کمی از حالت تصادفی بهتر عمل کند. (e < ½)در مقابل به یادگیری که با احتمال بالائی به دقت دلخواه برسد یادگیر قوی گفته میشود.منظور از Boosting این است که یک یادگیر ضعیف را به یک یادگیر قوی تبدیل کنیم.15

اسلاید 16: 16Boostingبه هر یک از دسته بندی کننده های مورد استفاده یک خبره (expert) گفته میشود. هر خبره با مجموعه داده ای با توزیع متفاوت آموزش داده میشود. برای پیاده سازی Boosting سه روش مختلف وجود دارد:Filteringدر این روش فرض میشود مجموعه داده خیلی بزرگ است و مثالهائی که از آن انتخاب میشوند، یا حذف شده و یا به مجموعه داده برگردانده می شوند.Subsamplingاین روش با مجموعه داده های با اندازه ثابت بکار برده میشود. داده ها با استفاده از یک توزیع احتمال مشخص مجدا نمونه برداری میشوند.Reweightingاین روش نیز با مجموعه داده های با اندازه ثابت بکار برده میشود. ولی داده ها توسط یک یادگیر ضعیف ارزش گذاری شده و به آنها وزن داده میشود.

اسلاید 17: Boosting17

اسلاید 18: Boosting accuracy Training18

اسلاید 19: Boosting19

اسلاید 20: AdaBoost (ADAptive BOOSTing)20در این روش احتمال انتخاب یک نمونه xt برای قرار گرفتن در مجموعه داده های آموزشی دسته بندی کننده j+1 بر مبنای احتمال خطای دسته بندی کننده cj تعیین میشود:اگر نمونه xt بدرستی دسته بندی شده باشد، احتمال انتخاب شدن آن برای دسته بندی کننده بعدی کاهش داده می شود. اگر نمونه xt بدرستی دسته بندی نشود، احتمال انتخاب شدن آن برای دسته بندی کننده بعدی افزایش داده می شود.تمامی یادگیرها ضعیف و ساده بوده و باید خطائی کمتر از ½ داشته باشند در غیر اینصورت آموزش متوقف میشود زیرا ادامه آن باعث خواهد شد تا یادگیری برای دسته بندی کننده بعدی مشکلتر شود.

اسلاید 21: یک نمونه از پیاده سازی الگوریتم AdaBoost21

اسلاید 22: AdaBoost training22

اسلاید 23: مثال23

اسلاید 24: Arcing-x4این روش از رای گیری وزن دار استفاده نمی کند.اما وزن مثال ها با توجه به K دسته بندی کننده ی قبلی با فرمول زیر محاسبه می شود:24

اسلاید 25: مثال25

اسلاید 26: مثال26

اسلاید 27: مثال27

اسلاید 28: مثال28

اسلاید 29: مثال29

اسلاید 30: Methodology30

اسلاید 31: Data Set Error Rates31

اسلاید 32: Percent Reduction in Error32

اسلاید 33: 33درصد کاهش خطا در شبکه عصبی

اسلاید 34: 34درصد کاهش خطا در درخت تصمیم

اسلاید 35: Ensemble Size35

اسلاید 36: Noise36

اسلاید 37: Error rates by the size of ensemble & Noise37

اسلاید 38: نتیجه گیرینتیجه بهترBoosting نسبت به BaggingوsingleهاحساسیتBoosting نسبت به نویز وپایین آمدن کارائیبیشترین کاهش خطا با شبکه عصبی با سایز10-15بیشترین کاهش خطا با درخت تصمیم با سایز25مناسب بودن Bagging روی اکثر مسائلبالا بودن دقتBoosting در شرایط مناسب38

اسلاید 39: پیشنهاداتاستفاده ازالگوریتم ژنتیک درانتخاب طبقه بندی کننده هاانتخاب مناسب مقدارپارامترها ازقبیل لایه های مخفی و نرخ یادگیری و....راهکاری برای ممانعت Overfitشدن Boostingدر دیتاهای حاوی نویز39

اسلاید 40: 40