منابع مقالات علمی : ارائه‌ چارچوبی در راستای بهبود پیش‌بینی وضعیت ترافیک- قسمت ۳

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

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

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

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

(۲-۱)
(۲-۲)
(۲-۳)

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

این مطلب را هم بخوانید :
تحقیق دانشگاهی - بررسی رابطه آگاهی و اعتماد سرمایه گذاران با بهره وری ...

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

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

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

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