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 عدد درخت تعیین می‌شود. در مورد کلاسه‌بندی، رای نهایی بر مبنای مُد خروجی‌ها و در مورد رگرسیون بر اساس میانگین‌گیری تعیین می‌شود.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

بکارگیری این استراتژی باعث عملکرد مناسب و کارا در مقایسه با دیگر الگوریتم‌ها همچون آنالیزهای جداسازی، بردارهای پشتیبان کننده^[۶۷] و شبکه‌های عصبی مصنوعی می‌شود. همچنین این تکنیک فقط به تنظیم دو پارامتر (۱) تعداد متغیرهای قرار گرفته در زیرمجموعه‌ی رندوم انتخاب شده و (۲) تعداد درختان مورد استفاده، نیاز دارد و علاوه بر آن، حساسیت شدیدی نسبت به مقادیر این پارامترها ندارد.

مراحل توسعه‌ی رندوم فارست

بطور کلی الگوریتم رندوم فارست یک مجموعه از درخت‌های شبه CART^[68] است . مروری کلی بر این الگوریتم را تحت ۴ مبحث ۱) مرحله رشد درختان^[۶۹]، ۲) مرحله ترکیب درختان^[۷۰]، ۳) مرحله خودآزمایی^[۷۱]و ۴) مرحله پس پردازش^[۷۲] بررسی می‌کنیم که این مباحث از [۳۲] آمده است.

• مرحله رشد درختان:

درختان موجود در رندوم فارست، شاخه‌های دوتایی^[۷۳] دارند، یعنی هر والد، تنها به دو فرزند تقسیم می‌شود. رندوم بودن در دو مرحله به هرکدام از این درختان تزریق می‌شود، (۱) در توسعه هر درخت روی نمونه‌های رندوم انتخاب شده از داده آموزشی و (۲) در مرحله انتخاب بهترین نقطه شکست از میان متغیرهایی که بطور رندوم از میان همه متغیرها انتخاب شده‌اند. اگر m، تعداد کل خصیصه‌ها باشد، مقادیری که Breiman برای تعداد متغیرهای انتخابی R پیشنهاد داد، به ترتیب در فرمول‌های (۲-۱)، (۲-۲) و (۲-۳) بدین ترتیب بود: