(۲-۱)

(۲-۲)

(۲-۳)

انتخاب زیرمجموعه‌ای از خصیصه‌ها و توسعه‌ی درختان براساس آن‌ها منجر به افزایش سرعت رشد درختان و همچنین عدم نیاز به اعمال الگوریتم‌های انتخاب خصیصه^[۷۴] می‌شود.

• انتخاب نقطه شکست در رندوم فارست:

هرچند انتخاب بهترین نقطه شکست از زیرمجموعه رندوم، ممکن است لزوماً بهترین نتیجه را در بر نداشته باشد، اما تکرار این انتخاب‌ها در مورد هرگره، تصمیم‌گیری متفاوتی را در طی ساخت درخت فراهم می‌کند و نهایتاً متغیرهای مهم نیز در ساخت درخت دخیل خواهند شد. این موضوع دلیلی است در راستای تأکید بر استفاده از درخت‌های با سایز کامل، که هَرَس نشده باشند. نتایج تحقیقات نیز نشان داده‌اند که هَرس کردن این درختان منجر به کاهش کارآیی الگوریتم می‌شود.

• مرحله خودآزمایی در رندوم فارست:

در طی اعمال الگوریتم رندوم فارست با توجه به مرحله نمونه برداری bootstrap، هر درخت تقریبا بر روی ۶۳% از داده‌ها، رشد پیدا می‌کند. بنابراین ۳۷% از داده‌ها، در مورد هر درخت استفاده نمی‌شود که به این داده‌ها “Out Of Bag” یا به اختصار OOB می‌گویند. از داده‌های OOB که در مورد هر درخت داده‌های مجزایی هستند ، می‌توان برای ارزیابی درختان توسعه یافته استفاده کرد. در واقع با بهره گرفتن از این مجموعه داده‌های OOB، الگوریتم رندوم فارست می‌تواند آمارهایی مربوط به کارآیی الگوریتم خود ارائه دهد. همچنین مسئله RF Self-testing، شبیه مسئله وارسی اعتبار^[۷۵] می‌باشد که هر بار روی قسمت بندی‌های متفاوتی از داده اولیه محاسبه می‌شوند. بنابراین با بهره گرفتن از این قابلیت رندوم فارست، حتی اگر کل داده آموزشی بعنوان ورودی الگوریتم استفاده شود، امکان Self-testing در طی یادگیری فراهم است. علاوه برآن، این قابلیت در مورد داده‌های کوچک حائز اهمیت زیادی است، چرا که نیازی به کنار گذاشتن قسمتی از داده برای تست، لازم نیست. بنابراین از جمله الگوریتم‌های پرکاربرد در خصوص اعمال بر روی داده‌های کم سایز محسوب می‌شود. از دیگر نتایج وجود داده‌هایOOB در هنگام ساخت درخت، مقاومت در برابر مسئله بیش برازش^[۷۶] و عمومیت‌بخشی^[۷۷] در برابر داده‌های جدید، می‌باشد. همچنین با انتخاب زیرمجموعه­ای از خصیصه‌ها، نیازی به اعمال الگوریتم‌های انتخاب ویژگی^[۷۸] نیز نخواهد بود[۲۱].

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

• مرحله پس پردازش در رندوم فارست:

در واقع پس از ساخت درختان، با دقت در آنها، دید بهتری در مورد داده می‌توان بدست آورد. با در نظر گرفتن هر رکورد، می‌توان تعداد دفعاتی که هر دو رکورد در برگ‌های یکسان درختان قرار گرفته‌اند، را محاسبه کرد و میزان شباهت آن‌ها را بدست آورد. معیار فاصله^[۷۹] بدست آمده از این طریق می‌تواند برای ساخت ماتریس عدم شباهت^[۸۰] نیز استفاده شود که بعنوان ورودی الگوریتم‌های خوشه یابی سلسله مراتبی^[۸۱] بسیار پرکاربردند. همچنین با حرکت روی مسیر درختان، عملاً مکانیزم الگوریتم نزدیکترین همسایگی انجام می‌شود. در نظر بگیرید که برای رسیدن به یک گره در درخت، یک رکورد باید تمام شرایط در همه والدها را ارضا کند، بنابراین رسیدن دو رکورد به یک گره نشان دهنده شباهت آن‌هاست. پس همانند تکنیک نزدیکترین همسایگی که با توجه به شبیه‌ترین همسایه‌ها، بر چسب آن داده جدید را پیش ­بینی می‌کند، درختان موجود در رندوم فارست نیز همانند این روند را می‌توانند دنبال کنند.

• مرحله ترکیب درختان در رندوم فارست:

از آنجا که در متدهای یادگیری تجمعی نهایتاً یک مدل نهایی ارائه می‌شود، پس در اینجا نیز درخت‌های آموزش دیده، باید ترکیب شوند. همانطور که پیشتر بیان شد، در مورد مسائل کلاسه بندی، بین نتایج مدل‌ها رأی‌گیری و در مورد مسائل رگرسیون از نتایج مدل‌ها میانگین‌گیری می‌شود. همچنین ترکیب مدل‌ها می‌تواند بر اساس نوعی وزن‌دهی صورت گیرد، یعنی همه مدل‌ها به یک اندازه در مدل نهایی مشارکت نداشته باشند. از جمله تلاش‌هایی که در این زمینه صورت گرفته می‌توان به موارد [۳۳] و [۳۴] اشاره کرد. در اکثریت این تحقیقات، وزن‌دهی و میزان مشارکت یک مدل، بر اساس دقت آن تعیین می‌شود.

تئوری‌های مرتبط با رندوم فارست

در این بخش به بیان تعاریف ریاضی موجود از رندوم فارست می‌پردازیم که در مقاله اصلی [۲۱] در مورد رندوم فارست آمده است. همچنین تئوری‌های مرتبط با این الگوریتم همچون مسئله همگرایی، دقت و خطای عمومی آن را بررسی می‌کنیم. علاوه بر آن به معرفی مجموعه OOB پرداخته و چگونگی کاربرد آن را برای محاسبه قدرت، وابستگی و مشاهده خطا در روند ساخت الگوریتم توضیح می‌دهیم. همچنین، از آنجا که تمرکز اصلی این پایان نامه با توجه به داده‌های ترافیکی، انجام رگرسیون است، بنابراین مسئله رگرسیون رندوم فارست را نیز بررسی کرده و در انتها، مزایا و کاربردهای الگوریتم رندوم فارست را توضیح می‌دهیم.

تعریف ریاضی رندوم فارست: “یک رندوم فارست یک کلاسه بند است که از مجموعه ای (k عدد) از کلاسه بندی‌های با ساختار درختی تشکیل شدهکه  بردارهای رندوم مستقل و یکنواخت توزیع شده هستند و هرکدام از درخت‌ها یک رأی واحد را برای مشهورترین کلاس با ورودی x تعیین می‌کنند” [۲۱].

“بعبارتی برای kاُمین درخت یک بردار رندوم  تولید شده که مستقل از بردارهای رندوم قبلی یعنی  است، اما توزیع یکسانی دارد و هر درخت با بهره گرفتن از مجموعه آموزشی و  رشد پیدا می‌کند. نهایتاً هر درخت، یک کلاسه بند  را نتیجه خواهد داد که X یک بردار ورودی است"[۲۱]. الگوریتم رندوم فارست بصورت شبه کُد^[۸۲] در شکل ۲-۳ (برگرفته از [۳۲]) آورده شده است.

Algorithm Random Forest (k)
Input : Sequence of N examples <( 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
p = # of variables
Do For t=1,2,.., K(# trees)

• • Choose bootstrap sample Di from D to construct tree Ti

• Select m input variables at random from p