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

صفحه 1:
۹9 / ‎ee‏ ان \ ‏۸ ‎RC‏ 1 02 يت سحن مصطفی اعظمی ‏1 5 ل سس 

صفحه 2:
مقدمه Poy A Oe nO eed ee © ‏اصل "نهارآمجانی وجود ندارد"‎ ۳ 0 برایمامی مسائل و درتمامی زمانهبهترین ( ‎Sb‏ ۳( [ ايده: * اگر تعدادی یادگیر پایه داشته باشیم میتوان با تر کیب نتایج آنها به دقت بالاتری رسید. ‎oon See‏ 7 با هم متفاوث باشند: ‎00 ‏ا‎ ere pyc ‏ا ا اا ا الما 010 ‎KOO‏ ‏* نحوه نمایش: استفاده از تعداد متفاوت ویژگی برای هر یادگیر. استفاده از مجموعه داده ‎peyton‏ ‏* مجموعه آموزشى: داده هاى آموزشى يادكيرها اندكى با هم تفاوت داشته باشند. ‎ ‎ 

صفحه 3:
10 perk ‏ا‎ ۱ Ror Bate tcl Til 34h agzg/la aus ۱ en ke Las " Serres ry] ae Crom ABE ‏ا‎ ‎ee pen pert eer Cr ‏ف ریم: نحوه نمایش, پارامترهای‎ 501010000 TS RICA RO eed retort seer ie ‏در عملکرد سیستم وجود داشته باشد. در‎ | pees 7 Oey eer oy EEC Saeed et ory ‏افزايش نمونه كيرى از اين توزيع به نتيجه‎ ‏بهترى برسيم‎ 

صفحه 4:
Simple Majority Voting ‘Wiest examples: 

صفحه 5:
, خصوصیت دسته‌آبندی کنندهتقای پایه / \ 4مناستبی از ترکیب دیشته بندی کننده ها گ الها بايد شترايط زير را ذاشته باشند: * هر یک به تنهائی در حد قابل قبولی دقیق 00000 00 ؟ هر کدام مکمل دیگری عمل کنند. به اين معنا که همگی نباید مشابه هم بوده و نتیجه یکسانی تولید کنند. 

صفحه 6:
۱ Cn ea aa 19 TCT ete Se eT een ot a a ۱ ee ‏مره‎ ٩ ‏ی‎ ‎/ 4 1 ‏یک یادگیر شیف طویلا تخیر داده میشگید تایه دق بالثی برسد.‎ ۰ ee ata | ‏وه سس‎ ٩ ۱ 8 

صفحه 7:
Output ‏زمار‎ Input xp) Combiner 

صفحه 8:
Ensémble Averaging ey 

صفحه 9:
نتیجه گیری در مورد 91۳9 ۳56۲۱۵۱۵۷۸۲6۲3 ی ‎oO‏ باياس سيستم حاصللا مشابه اس هر یک از خبره ها خواهد بود. ‎oe ee Tee) BB rei oe erent) OL i‏ ‎See Ree ieee Nt Benn er Coe |‏ خواهد بود. 

صفحه 10:
a ۳ ۱ ۱ ۳ ( ۰ 4 دراین ال خروجی ۱۰شیکهباهم ‎Individual Experts Used‏ ترکیب شده اند. میانگین 00 / 5616 توانسته به خطلى مورد انتظارى كه كمتر از خطاى/ ‎hee‏ 060 برسد. ‎On wa!‏ ا 0 0 7 ‎Se oe Rene dd‏ © (/اختلاف co 

صفحه 11:
Bagging Vs) 1 اين روش نیز مبتنی بر رای گیْری است با اين تفاوت که یاد گیرهای پایه با داده ‎ep Cone sr Altay‏ لو ده میشوند تا اندکی با هم تفاوت داشته باشند. Cee ec eee SS STON N Eel See he Page) tes Pete eC ev UNC eee 5 ۰ ‏مس وم ای مب تا‎ eiodes | Cee eee Se Rae ee KOR ‏راو راو‎ )( ‏اس رنه ان نی سر جوا‎ مسر ‎aca‏ ۱ 1 

صفحه 12:
breast cancer glass diabetes Error rates on ۲ 1 روش ۳:۸۱( برایالگوریتمهاییادگیر اپادار یعنیالگوریتمهثی که با تغیر دده خرن عملکرد خونى شواهد يت در 

صفحه 13:
6 

صفحه 14:
ae »+—Bagging 

صفحه 15:
Boosting اا ا متفاوت محسوسى ‎waa 500‏ ی را م یکدیگر باشند. \ PCD TOTS NY ANIL EES. WO er ۱ Le ESC EO 3 منظور از یادگیر ضعیف این است که یاد گیر فقط کافی است که یک کمی از حالت تصادفى بهتر عمل كند. (ج < و/ة) 000 ‏ا ل ال‎ FRC a AP ‏ميشود.‎ ا ا ا | 06 

صفحه 16:
۱۱ | | ‏رب‎ meer ewe ree * له 1 Mer Sen enoM ES LT NESE eee od eT erento Se eee ‏ل ا ا‎ eid PIE ‏ا‎ eS Pe ree a ene Soe te ‏ها توسط يك يادكير ضعيف ارزش كذارى شده و به آنها وزن داده ميشود.‎ 6 

صفحه 17:
a -~< Boosting “Onigmal Training set 3 Training set 4 

صفحه 18:
Boosting accuracy Training ۳ ples assification differently © 

صفحه 19:
Boosting 06 

صفحه 20:
AdaBoost (ADAptive #99 ل وض احتمال انتخاب,یک نمُونه * برای قرار گرفتن در مجموعه داده های ‎Pu cnen ete sie‏ موی ‎ean ie)‏ ا ‎[eC‏ ‏میشود: ۱ 0 ‎Cat SC Seat at)‏ 19 ‎Reve ats ene ore tl ia‏ ا ا ‎Pen‏ ‎eMC Ies‏ 0[ | تمامی یادگیرها ضعیف و ساده بوده و باید خطائی کمتر از 22 داشته باشند در غیر اینصورت آموزش متوقف میشود زیرا ادامه آن باعث خواهد شد ‎COT poe‏ ا ل 0 er 

صفحه 21:
Training For all {2° For all ba Randomly draw 4 Train d, using For each (zt,r‘), calculate yt — dj Calculate error rate: «, — >, pf - (yf Ar*) 1/2, then ‏لد‎ > For each If ut Normalize probabilitie: ی یس Testing Given «, calculate d,(x),j =1 Calculate class outpu vem Dy (low) ‏ب‎ 9 

صفحه 22:
eo ‎Te‏ ول ای ‎Learn) ‎ 

صفحه 23:
ه06 

صفحه 24:
۱ eit ۸ 0006 ۳۳ 5 00 ne sre 9 

صفحه 25:
es. 

صفحه 26:


صفحه 27:


صفحه 28:


صفحه 29:


صفحه 30:
Methodology Features Neural Network Class | Cont Dise Hiddens _ Epochs TO 0 690 : 10 35 000 4 0 10 5 9 5 3 10 10 heart-cleveland hepatitis house-votes-84 hy ionosphere krvs-kp labe letter 20000 prom 136 | 936 ribosome-bind | 1877 satellite 

صفحه 31:
90 hepatitis honse-votes-84 ionospher iis kr-vekp Tabor letter promot ribosome-bind satellite ‏مهست‎ 

صفحه 32:


صفحه 33:


صفحه 34:


صفحه 35:
1 & 3 & 5 

صفحه 36:


صفحه 37:


صفحه 38:
و ‎eee |‏ 0070 وپایین آمدن کارائی @ ن كاهش خِظًا با شبكه عصكّى با سايز ‎١8-١ ٠‏ © بيشترين كاهشخطا با درخت تصميّم با سايزه! © مناسب بودن 200 0) روى اكثر مسائل Ree ‏ا‎ AL | 30. 

صفحه 39:
۲ پيشنهادات 4 | استفاده ازالگوریتم سس ۳ / fy ae TSE STE CTCL DN I Sep Seren ree | PT ‏اا‎ ear para لحك 

صفحه 40:


‏Popular Ensemble Methods: An Empirical Study استاد راهنما :دکتر کیومرث شیخ اسماعیلی ارائه دهنده: شهرام رحمانی رحیم شیخی مصطفی اعظمی گروه Popular Ensemble Methods: An Empirical Study مهندسي کامپيوتر و فناوری اطالعات دانشگاه کردستان مقدمه اصل ”نهار مجانی وجود ندارد“( )No Free Lunch Theoremبیان میدارد که: ‏ هیچ الگوریتمی وجود ندارد که برای تمامی مسائل و در تمامی زمانها بهترین ( دقیق ترین) یادگیر را بوجود آورد. ‏ اگر تعدادی یادگیر پایه داشته باشیم میتوان با ترکیب نتایج آنها به دقت باالتری رسید. ایده: این یادگیرها ممکن است در موارد زیر با هم متفاوت باشند: الگوریتم :که باعث میشود فرضیات مختلفی در مورد داده استفاده شود. پارامترها :مثل تعداد گره های مختلف الیه پنهان شبکه های عصبی و یا Kمتفاوت در ‏KNN نحوه نمایش :استفاده از تعداد متفاوت ویژگی برای هر یادگیر ،استفاده از مجموعه داده متفاوت مجموعه آموزشی :داده های آموزشی یادگیرها اندکی با هم تفاوت داشته باشند. 2 ترکیب دسته بندی کننده ها روشهای مختلفی برای ترکیب نتایج دسته بندی کننده ها وجود دارد: متداولترین روشها میانگین گیری و یا استفاده از رای اکثریت هستند ‏Final انگیزه اصلی این کار در اینجاست که: ‏outpu ما هنگام طراحی یک سیستم یادگیر انتخاب ‏t های فراوانی داریم :نحوه نمایش ،پارامترهای یادگیر ،داده های آموزشی و غیره. این تنوع باعث میشود که نوعی از واریانس در عملکرد سیستم وجود داشته باشد .در نتیجه اگر سیستم های مختلفی داشته و از نتایج آنها استفاده شود این امکان وجود دارد که توزیع خطا حول هدف متمرکز شده و با افزایش نمونه گیری از این توزیع به نتیجه بهتری برسیم 3 ‏d ‏d1 ‏d2 ‏d3 ‏d4 5 ‏input Simple Majority Voting 4 خصوصیت دسته بندی کننده های پایه برای اینکه بتوان نتیجه مناسبی از ترکیب دسته بندی کننده ها گرفت ،این دسته بندی کنن__ده ها باید شرایط زیر را داشته باشند: ‏ ‏ 5 هر یک به تنهائی در حد قابل قبولی دقیق باشند .البته نیازی به بسیار دقیق بودن آنها نیست. هر کدام مکمل دیگری عمل کنند .به این معنا که همگی نباید مشابه هم بوده و نتیجه یکسانی تولید کنند. انواع ترکیب دسته بندی کننده ها ‏Static structures پاسخ چندین خبره بدون در نظر گرفتن سیگنال ورودی با هم ترکیب میشوند. ‏ ‏ ‏ ‏ ‏ensemble averaging خروجی خبره های مختلف بصورت خطی با هم ترکیب شده و خروجی جمعی را بوج___ود می آورد ‏boosting یک یادگیر ضعیف طوری تغییر داده میشود تا به دقت باالئی برسد. ‏Dynamic structures در این روش سیگنال ورودی در انتخاب مکانیسم ترکیب خبره ها تاثیر میگذارد. ‏ ‏ ‏ ‏ 6 ‏mixture of experts خروجی خبره ها توس___ط ی___ک شبکه Gating networkبص___ورت غ___یر خطی با هم ترکیب میشوند. ‏hierarchical mixture of experts خروجی خبره ها توسط چندین شبکه Gating networkک__ه بص__ورت سلس__له مراتبی قرار داده شده اند بصورت غیر خطی با هم ترکیب میشوند. Ensemble Methods 7 Ensemble Averaging 8 نتیجه گیری در موردEnsemble Averaging اگر چندین خبره با بایاس و واریانس یکسان ،از طریق روش ensemble-averagingبا هم ترکیب شوند: ‏ ‏ بایاس سیستم حاصل مشابه بایاس هر یک از خبره ها خواهد بود. واریانس سیستم حاصل کمتر از واریانس هر یک از خبره ها خواهد بود. خطای میانگین سیستم حاصل کمتر از خطای میانگین هر یک از خبره ها خواهد بود. 9 مثال در این مثال خروجی 10شبکه با هم ترکیب شده اند .میانگین Ensembleتوانسته به خطای مورد انتظاری که کمتر از خطای میانگین شبکه های منفرد است ()D برسد. 80.3%درصد صحت دسته بندی کننده ترکیبی در مقابل%79.4 میانگین دسته بندی کننده منفرد %1اختالف 10 Bagging روش این روش نیز مبتنی بر رای گیری است با این تفاوت که یادگیرهای پایه با داده .های آموزشی متفاوتی آموزش داده میشوند تا اندکی با هم تفاوت داشته باشند در نتیجه در حالی که این یادگیرها بدلیل آموزش از مجموعه اصلی مشابه هم خواهند بود بدلیل انتخاب تصادفی نمونه های آموزشی اندکی با هم اختالف نیز .خواهند داشت  Bagging (Bootstrap Aggregating) - Breiman, 1996   take a training set D, of size N for 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 for output is average/vote from all machines trained 11 مثال روش Baggingبرای الگوریتمهای یادگیر ناپایدار یعنی الگوریتمهائی که با تغییر داده دچار تغییر در نتیجه میشوند عملکرد خوبی خواهد داشت ( .شبکه عصبی و درخت تصمیم نمونه ای از این الگوریتمها هستند .در حالیکه KNNپایدار است). 12 Bagging 13 Bagging 14 Boosting اگر یادگیرهای پایه مشابه هم باشند ترکیب آنها نتیجه متفاوت محسوسی نخواهد داشت .بهتر است که یادگیرها تصمیم گیری متفاوتی داشته و مکمل یکدیگر باشند. در Boostingسعی میشود تا تعدادی یادگیر پایه ضعیف که مکمل هم باشند تولید شده و آنها را با اشتباه یادگیر قبلی آموزش داد. منظور از یادگیر ضعیف این است که یادگیر فقط کافی است که یک کمی از حالت تصادفی بهتر عمل کند)½ < e( . در مقابل به یادگیری که با احتمال باالئی به دقت دلخواه برسد یادگیر قوی گفته میشود. منظور از Boostingاین است که یک یادگیر ضعیف را به یک یادگیر قوی تبدیل کنیم. 15 Boosting به هر یک از دسته بندی کننده های مورد استفاده یک خبره ( )expertگفته میشود .هر خبره با مجموعه داده ای با توزیع متفاوت آموزش داده میشود. برای پیاده سازی Boostingسه روش مختلف وجود دارد: ‏ ‏ ‏ 16 ‏Filtering در این روش فرض میشود مجموعه داده خیلی بزرگ است و مثالهائی که از آن انتخاب میشوند ،یا حذف شده و یا به مجموعه داده برگردانده می شوند. ‏Subsampling این روش با مجموعه داده های با اندازه ثابت بکار برده میشود .داده ها با استفاده از یک توزیع احتمال مشخص مجدا نمونه برداری میشوند. ‏Reweighting این روش نیز با مجموعه داده های با اندازه ثابت بکار برده میشود .ولی داده ها توسط یک یادگیر ضعیف ارزش گذاری شده و به آنها وزن داده میشود. Boosting 17 Boosting accuracy Training 18 Boosting 19 )AdaBoost (ADAptive BOOSTing در این روش احتمال انتخاب یک نمونه xtبرای قرار گرفتن در مجموعه داده های آموزشی دسته بندی کننده j+1بر مبنای احتمال خطای دسته بندی کننده cjتعیین میشود: اگر نمونه xtبدرستی دسته بندی شده باشد ،احتمال انتخاب شدن آن برای دسته بندی کننده بعدی کاهش داده می شود. اگر نمونه xtبدرستی دسته بندی نشود ،احتمال انتخاب شدن آن برای دسته بندی کننده بعدی افزایش داده می شود. تمامی یادگیرها ضعیف و ساده بوده و باید خطائی کمتر از ½ داشته باشند در غیر اینصورت آموزش متوقف میشود زیرا ادامه آن باعث خواهد شد تا یادگیری برای دسته بندی کننده بعدی مشکلتر شود. 20 یک نمونه از پیاده سازی الگوریتم AdaBoost 21 AdaBoost training 22 مثال 23 Arcing-x4 این روش از رای گیری وزن دار استفاده نمی کند. اما وزن مثال ها با توجه به Kدسته بندی کننده ی قبلی با فرمول زیر محاسبه می شود: 24 مثال 25 مثال 26 مثال 27 مثال 28 مثال 29 Methodology 30 Data Set Error Rates 31 Percent Reduction in Error 32 33 درصد کاهش خطا در شبکه عصبی 34 درصد کاهش خطا در درخت تصمیم Ensemble Size 35 Noise 36 Error rates by the size of ensemble & Noise 37 نتیجه گیری نتیجه بهتر Boostingنسبت به Baggingوsingleها حساسیت Boostingنسبت به نویز وپایین آمدن کارائی بیشترین کاهش خطا با شبکه عصبی با سایز15-10 بیشترین کاهش خطا با درخت تصمیم با سایز25 مناسب بودن Baggingروی اکثر مسائل باال بودن دقت Boostingدر شرایط مناسب 38 پیشنهادات استفاده ازالگوریتم ژنتیک درانتخاب طبقه بندی کننده ها انتخاب مناسب مقدارپارامترها ازقبیل الیه های مخفی و نرخ یادگیری و.... راهکاری برای ممانعت Overfitشدن Boostingدر دیتاهای حاوی نویز 39 40