این نتیجه در واقع نشان دهندهی دلیل بیش برازش نشدن الگوریتم رندوم فارست (حتی با در برداشتن درختان زیاد) به حساب میآید. در واقع این رابطه نشان میدهد که خطای عمومی مقداری محدود و کوچکتر از صفر است و همین مسئله باعث بیش برازش نشدن الگوریتم میشود.
استفاده از OOB برای مشاهده خطا، قدرت [۸۶]و وابستگی[۸۷]: همانطور که پیشتر توضیح دادیم، برای ساخت هر درخت، یک مجموعه دادهی آموزشی جدید از مجموعه دادهی اصلی انتخاب شده و با انتخاب رندوم ویژگیها، یک درخت ساخته میشود. بدین ترتیب، استفاده از بگینگ میتواند در راستای پیش بینی خطای عمومی (PE*) ترکیب درختها و همچنین قدرت و وابستگی آنها بکار گرفته شود. فرض کنید با داشتن مجموعه آموزشی T، یک مجموعه bootstrap ، Tk داریم که کلاسهبندهای روی آن ساخته شدهاند. برای هر x,y موجود در داده آموزشی، فقط رأیهای کلاسه بندهایی استفاده میشود که در آن TK شامل y نشده باشند. به این کلاسه بندها، کلاسه بند OOB گفته میشود. پیش بینی OOB برای خطای عمومی نیز نسبت خطای کلاسه بند OOB روی مجموعه آموزشی است. در واقع در هر مجموعه آموزشی Bootstrap، تقریبا ۳/۱ نمونهها کنار گذاشته میشوند. بنابراین، خطای OOB بر مبنای ترکیب ۳/۱ از کلاسه بندها در ترکیب نهایی، محاسبه میشود. از آنجا که نسبت خطا با افزایش کلاسه بندها، کاهش مییابد، بنابراین خطای OOB خطای فعلی را Overestimate میکند. برای رسیدن به خطای OOB بدون سوگیری[۸۸]، باید در نقطه قبل از همگرایی خطای تست، آن را اجرا کرد. هرچند بر خلاف وارسی اعتبار، خطای OOB، بدون سوگیری است.
رندوم فارست برای رگرسیون
در انتها با توجه به استفاده از رگرسیون رندوم فارست در این پایان نامه، به بیان مختصری از مباحث کلی آن میپردازیم. همانند قبل، رگرسیون رندوم فارست از درختان مبتنی بر بردار رندوم Ө شکل میگیرد که درخت پیش بینی کننده ، به جای برچسب کلاسها، روی مقادیر عددی اعمال میشوند. در انتها مدل نهایی بر اساس میانگین گیری روی k عدد درخت بدست میآید. در مورد محاسبه خطای عمومی رگرسیون رندوم فارست میتوان به تئوری زیر اشاره کرد [۲۱].
تئوری ۲-۲ : با افزایش تعداد درختان، خطای عمومی در مورد رگرسیون نیز تحت تئوری زیر بیان شده است:
(۲-۸)
که میانگین مجذور خطای عمومی برای هر پیش بینی کننده عددیh(x) بصورت زیر محاسبه میشود.
(۲-۹)
مزایا و کاربردهای رندوم فارست
مباحث مطرح شده در این بخش و دیگر تحقیقات میتوان نتیجه گرفت که الگوریتم رندوم فارست از جمله تکنیکهای قوی در زمینهی کلاسهبندی و رگرسیون به شمار میآید. از دیگر فواید حاصل از بکارگیری این الگوریتم میتوان به موارد زیر نیز اشاره کرد:
- امکان مشاهده داده[۸۹] در مورد دادههای با بُعد بالا[۹۰]
- تشخیص ناهنجاری[۹۱]، دورافتادگی[۹۲] و خطا
- امکان آنالیز مجموعه دادههای با سایز کوچک (بدلیل امکان انجام محاسبات OOB)
- تشخیص ویژگیهای با اهمیت تر
- حل مسئله مقادیر از دست رفته[۹۳]
- ارائه متد جدید چرخشی کلاسترینگ[۹۴] با بهره گرفتن از معیارهای سنجش فاصله بین رکوردها، مبتنی بر درختها
- آموزش سریع در مورد دادههای با سایز بالا به دلیل عدم نیاز به مسئلهی انتخاب ویژگی
- مقاوم بودن در مورد مسئله بیش برازشی و عمومیت به دادههای جدید
- سهولت استفاده به دلیل نیاز محدود به تنظیم پارامترها
- و نهایتاً ارائه مدل با کارآیی و دقت بسیار بالا
نتیجه گیری
همان طور نشان داده شد، الگوریتم رندوم فارست یک ابزار قدرتمند در خصوص مسئله پیشبینی به حساب میآید. نتایجی که در دیگر تحقیقات بر روی مجموعههای دادههای مختلف انجام شده نیز بیانگر کارایی قابل مقایسهی این الگوریتم با دیگر تکنیکهای قوی در این زمینه از جمله بوستینگ و دیگر انواع بگینگ، میباشد. همچنین در فصل پیشینه تحقیق خواهیم دید که در تحقیقات اخیر و در حوزههای مختلف، گرایش قابل توجهی به سمت استفاده از این الگوریتم میباشد. در این پایان نامه نیز به بررسی کارآیی و استفاده از الگوریتم رندوم فارست در خصوص دادههای ترافیکی پرداختهایم.
فصل سوم
پیشینه تحقیق
مقدمه
در این فصل، ابتدا به بیان تعریف مسئلهی پیشبینی کوتاه مدت ترافیک یا به عبارتی پیشبینی سریهای زمانی میپردازیم. در واقع از آنجا که دادههای ترافیکی معمولاً در غالب بازههای زمانی یکسان جمع آوری میشوند، عموماً بعنوان سریهای زمانی در نظر گرفته میشوند. پس از ارائه مفاهیم و نشانه گذاریها، مطالعهی روشهای مرسوم برای حل این مسئله را در سه گروه و تحت سه بخش بعدی بررسی میکنیم. از میان این متدها، با توجه به پرکاربرد بودن روشهای مبتنی بر مدلهای شبکه عصبی مصنوعی و همچنین روشهای مبتنی بر آنالیزهای سریهای زمانی، ابتدا به بررسی پیشینه مطالعات انجام شده در این دو گروه میپردازیم. در انتها نیز به مطالعهی روشهای مبتنی بر متدهای داده کاوی پرداخته میشود که گرایش قابل ملاحظهای از تحقیقات اخیر به سمت استفاده از آنها میباشد.
تعریف مسئله
همانطور که پیشتر بیان شد، مسئلهی پیش بینی ترافیک از جمله نیازهای اساسی مراکز کنترل ترافیک در راستای ایجاد تعادل ترافیکی میباشد. غالباً این مسئله میتواند به دو گروه کلی پیش بینی طولانیمدت[۹۵] و کوتاهمدت تقسیمبندی شود. در مقابل الگوریتمهای پیش بینی طولانیمدت که تخمین ترافیک در زمانهای آینده دور را شامل میشوند، الگوریتمهای پیش بینی کوتاهمدت، به روی تخمین ترافیک در چند دقیقه تا ساعات آینده متمرکز میشوند که در این پایاننامه نیز بتمرکز اصلی بر روی بررسی این نوع الگوریتمها میباشد.
از طرف دیگر، دادههای جمع آوری شده از وضعیت ترافیکی، داده حجیمی هستند که غالباً در بازههای زمانی یکسانی ثبت شدهاند، از اینرو، این دادهها معمولاً بصورت سریهای زمانی در نظر گرفته میشوند. در واقع، دادههای سری زمانی شامل دنبالههایی از مقادیرند که در طی اندازهگیری های متناوب در زمانهای مختلف بدست آمده اند. معمولاً این مقادیر در بازههای زمانی مساوی (ساعتی، روزانه، هفتگی و…) ثبت شدهاند. از این رو میتوان آنها را در غالب بردارهای وابسته به زمان در نظر گرفت و بصورت زیر نمایش داد.