Algorithm: Bagging
Input :
Sequence of N examples D <( x₁ ,y₁ ),….., ( x_N, y_N )> with labels y _i€ Y={ 1,…,L }
Distribution D over the N example
Integer K specifying number of iterations
Weak Learning algorithm WeakLearn (tree)
Do k=1,2,.., K
Choose bootstrapped sample Di (n sample) by randomly from D.
Call WeakLearn k with Di and receive the hypothesis (tree) h_t.
Add h_t to the ensemble.
End
Test: Simple Majority Voting – Given unlabeled instance x
Evaluate the ensemble {h₁,….,h_k} on x
Choose the class that receives the highest total vote as the final classification.

شکل ۲-۱٫ معماری کلی الگوریتم بگینگ. با دریافت مجموعه‌ی آموزشی D با سایز N ، به تعداد K مجموعه آموزشی جدید D_i، با سایز n<N، تولید می‌شود)بعنوان Bootstrap sample ). K مدل مختلف با استفاده از K زیر مجموعه، آموزش داده می‌شوند و در نهایت کلاسی که تعداد بیشتری از مدلها به آن رای دادهاند، انتخاب میشود.

از جمله عوامل تأثیرگذار در موفقیّت متدهای یادگیری تجمعی، بحث تنوع^[۶۱] مدل‌های پایه و همچنین دقت هرکدام از مدل‌هاست. همانطور که واضح است اگر مدل‌های پایه متنوع یا به اصطلاح diverse نباشند، ترکیب آن‌ها بی فایده است. در متد بگینگ، استفاده از مجموعه‌های متفاوت از مجموعه داده اولیه، شرط تنوع را تضمین می‌کند. از طرف دیگر، زمانی یک مدل می‌تواند از تغییرات مجموعه داده آموزشی خود استفاده کند که ناپایدار^[۶۲] باشد . ناپایدار بودن به این معناست که تغییرات کوچک در ورودی (مجموعهی آموزشی) منجر به تغییرات بزرگ در خروجی مدل شود. از جمله پیشبینی کننده‌های ناپایدار می‌توان به شبکه‌های عصبی مصنوعی و درختان تصمیم‌گیری اشاره کرد. هرچند مدل نزدیکترین همسایگی^[۶۳] جزء کلاسه بندهای پایدار به حساب می‌آید [۲۹].
با توجه به مباحث مطرح شده، می‌توان نتیجه‌گیری کرد که استفاده از درخت تصمیم‌گیری بعنوان مدل‌های پایه‌ای متدهای یادگیری تجمعی کارایی مؤثری دارد و برهمین اساس تحقیقات زیادی انجام و منجر به تولید الگوریتم‌های بسیار قدرتمندی نظیر رندوم فارست شد. در ادامه نیز به بررسی دو نوع متد مبتنی بر بگینگ خواهیم پرداخت.
از جمله انواع الگوریتم‌هایی که روند بگینگ را دنبال می‌کنند، می‌توان به دو نوع (۱) pasting small votes و(۲) رندوم فارست اشاره کرد.
pasting small votes: که طراحی آن در راستای استفاده بر روی پایگاه داده‌های بزرگ بوده است. در این الگوریتم، یک مجموعه داده به زیرمجموعه کوچکتر به نام بیت^[۶۴] تقسیم شده و روی هرکدام یک کلاسهبند متفاوت آموزش داده می‌شود. اگر انتخاب این مجموعه داده‌ها بر اساس رندوم باشد Rvotes (مشابه بگینگ) نامیده شده و اگر بر اساس اهمیت آن بخش باشد، با نام Ivotes (مشابه بوستینگ) شناخته می‌شوند[۲۹].
رندوم فارست: نوع دیگر روش بگینگ الگوریتم رندوم فارست است که به دلیل گستردگی استفاده از آن در این پایان‌نامه، مفاهیم آن بطور مفصل در بطور مجزا در بخش بعدی توضیح داده شده است.

رندوم فارست

در سال ۲۰۰۱، Breiman الگوریتم رندوم فارست را ارائه داد که یک حالت عمومی‌تر از بگینگ به حساب می‌آید و در واقع یک لایه رندوم به بگینگ اضافه می‌کند. در این الگوریتم علاوه بر اینکه هر درخت با استفاده از سمپل‌های متفاوتی از داده‌ها ساخته می‌شود، روند ساخت درخت‌ها نیز تغییر می‌کند. در واقع در یک درخت استاندارد، هر گره تصمیم با استفاده از بهترین نقطه شکست^[۶۵] انتخاب از میان همه خصیصه‌ها^[۶۶] شکسته می‌شود، اما در رندوم فارست، هر گره تصمیم بر مبنای بهترین نقطه شکست از میان زیرمجموعه‌ای از خصیصه‌هایی که بطور رندوم در سطح آن گره انتخاب شده اند، شکسته می‌شود [۳۰]. معماری کلی مربوط به رندوم فارست برگرفته از [۳۱]در شکل۱-۲ آمده است.

شکل ۲-۲٫ نمایی کلی از الگوریتم رندوم فارست که یک متد یادگیری تجمعی برای کلاسه‌بندی و رگرسیون است. مدل‌های پایه، درختان تصمیم‌گیری CART هستند و خروجی نهایی K، بر اساس رای‌گیری خروجی‌های B عدد درخت تعیین می‌شود. در مورد کلاسه‌بندی، رای نهایی بر مبنای مُد خروجی‌ها و در مورد رگرسیون بر اساس میانگین‌گیری تعیین می‌شود.

برای دانلود متن کامل پایان نامه به سایت  fotka.ir  مراجعه نمایید.