درخت بگینگ مخفف Bootstrap aggregating (Bagging) می باشد که در این قسمت توضیح داده شده است. الگوریتم بگینگ از مجموعه ای از مدل‌های پایه‌ای تشکیل شده و به ترتیب زیر عمل می‌کند. با دریافت مجموعه‌ی آموزشی D با سایز N (تعداد نمونه های داده آموزشی)، به تعداد K مجموعه آموزشی جدید Di، با سایز n<N، تولید می‌شود که حاصل سمپل‌گیری یکنواخت و با جایگزینی از مجموعه اولیه D می‌باشد. همانطور که می‌دانیم این نوع سمپل‌گیری بعنوان Bootstrap sample شناخته می‌شود. K مدل مختلف با استفاده از K زیر مجموعه، آموزش داده می‌شوند و در نهایت یک مدل نهایی را تشکیل می‌دهند. این مدل نهایی در رگرسیون از میانگین‌گیری نتایج مدل‌ها و در کلاسه‌بندی از رأی‌گیری بین مدل‌ها حاصل می‌شود [29]. درخت بگینگ در واقع همان الگوریتم بگینگ است که مدل‌های پایه‌ای آن مبتنی بر درخت‌های تصمیم‌گیری هستند. همانطور که مشخص است، بر خلاف بوستینگ در بحث بگینگ، مدل‌های پایه مستقل از هم ساخته می‌شوند و به دقت مدل‌های قبلی وابسته نیستند. در شکل 2-1 الگوریتم مربوط به بگینگ را می بینیم.
Algorithm: Bagging
Input :
Sequence of N examples D <( x1 ,y1 ),….., ( xN, yN )> 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) ht.
• Add ht to the ensemble.
End
Test: Simple Majority Voting – Given unlabeled instance x
• Evaluate the ensemble {h1,….,hk} on x
• Choose the class that receives the highest total vote as the final classification.
شکل 2-1. معماری کلی الگوریتم بگینگ. با دریافت مجموعه‌ی آموزشی D با سایز N ، به تعداد K مجموعه آموزشی جدید Di، با سایز n<N، تولید می‌شود)بعنوان Bootstrap sample ). K مدل مختلف با استفاده از K زیر مجموعه، آموزش داده می‌شوند و در نهایت کلاسی که تعداد بیشتری از مدل ها به آن رای داده اند، انتخاب می شود.
از جمله عوامل تأثیرگذار در موفقیّت متدهای یادگیری تجمعی، بحث تنوع مدل‌های پایه و همچنین دقت هرکدام از مدل‌هاست. همانطور که واضح است اگر مدل‌های پایه متنوع یا به اصطلاح diverse نباشند، ترکیب آن‌ها بی فایده است. در متد بگینگ، استفاده از مجموعه‌های متفاوت از مجموعه داده اولیه، شرط تنوع را تضمین می‌کند. از طرف دیگر، زمانی یک مدل می‌تواند از تغییرات مجموعه داده آموزشی خود استفاده کند که ناپایدار باشد . ناپایدار بودن به این معناست که تغییرات کوچک در ورودی (مجموعه ی آموزشی) منجر به تغییرات بزرگ در خروجی مدل شود. از جمله پیش بینی کننده‌های ناپایدار می‌توان به شبکه‌های عصبی مصنوعی و درختان تصمیم‌گیری اشاره کرد. هرچند مدل نزدیکترین همسایگی جزء کلاسه بندهای پایدار به حساب می‌آید [29].
با توجه به مباحث مطرح شده، می‌توان نتیجه‌گیری کرد که استفاده از درخت تصمیم‌گیری بعنوان مدل‌های پایه‌ای متدهای یادگیری تجمعی کارایی مؤثری دارد و برهمین اساس تحقیقات زیادی انجام و منجر به تولید الگوریتم‌های بسیار قدرتمندی نظیر رندوم فارست شد. در ادامه نیز به بررسی دو نوع متد مبتنی بر بگینگ خواهیم پرداخت.
از جمله انواع الگوریتم‌هایی که روند بگینگ را دنبال می‌کنند، می‌توان به دو نوع (1) pasting small votes و(2) رندوم فارست اشاره کرد.
• pasting small votes: که طراحی آن در راستای استفاده بر روی پایگاه داده‌های بزرگ بوده است. در این الگوریتم، یک مجموعه داده به زیرمجموعه کوچکتر به نام بیت تقسیم شده و روی هرکدام یک کلاسه بند متفاوت آموزش داده می‌شود. اگر انتخاب این مجموعه داده‌ها بر اساس رندوم باشد Rvotes (مشابه بگینگ) نامیده شده و اگر بر اساس اهمیت آن بخش باشد، با نام Ivotes (مشابه بوستینگ) شناخته می‌شوند[29].
• رندوم فارست: نوع دیگر روش بگینگ الگوریتم رندوم فارست است که به دلیل گستردگی استفاده از آن در این پایان‌نامه، مفاهیم آن بطور مفصل در بطور مجزا در بخش بعدی توضیح داده شده است.