تحقیقات متعددی در خصوص پیشبینی وضعیت ترافیکی آینده انجام شده است که در واقع با استفاده از دادههای ثبت شده از وضعیت فعلی ترافیک، ترافیک مربوط به زمانهای آتی را پیشبینی میکنند.
بطور معمول دادههای جمعآوری شده در حوزهی ترافیک، بصورت سریهای زمانی[۱۶] در اختیار ما قرار میگیرند که در واقع شامل رکوردهای مختلفی هستند که در بازه های زمانی مساوی و در طی اندازهگیریهای متوالی بدست میآیند. با استفاده از دادههای فعلی و گذشته، مقادیر آنها در آینده پیشبینی میشوند [۲]. تاکنون تکنیکهای متفاوتی در زمینهی پیشبینی ترافیک بکار گرفته شده است که از جملهی آنها میتوان به روشهای کالمن فیلترینگ[۱۷] [۴,۳]، متدهای آماری غیرپارامتریک [۵,۶] [۱۸]، روشهای یادگیری متوالی[۷] [۱۹]، مدلهای شبکهعصبی[۲۰] [۸-۱۱] و آنالیزهای سریهای زمانی[۱۳-۱۷] اشاره کرد. از مهمترین چالشهای اعمال این الگوریتمها، حجم بالای دادههای ترافیکی است که منجر شده تا اخیراً گرایش تحقیقات به سمت استفاده از الگوریتمهای داده کاوی[۲۱] باشد.
همانطور که میدانیم تکنیکهای داده کاوی قابلیت استخراج اطلاعات از دادههایی با حجم بسیار بالا همچون دادههای ترافیکی را دارا هستند. از میان آنها روشهای مبتنی بر درختهای تصمیمگیری[۲۲] بطور گستردهای در حوزهی ترافیک مورد استفاده قرار گرفته است[۱۸,۱۹]. همچنین متدهای یادگیری تجمعی[۲۳] همانند بگینگ و بوستینگ با توجه به کارایی بالا، مورد توجه ویژهای واقع شدند. ایدهی اصلی آنها ساخت مجموعهای از مدلها و ترکیب نتایج آنها با هدف بهبود دقت[۲۴] یادگیری میباشد[۴۷]. در شکل -۱۱ معماری کلی الگوریتمهای یادگیری تجمعی را میبینیم که از کتاب [۲۰] آورده شده است.
شکل ۱-۱٫ معماری کلی مربوط به متدهای یادگیری تجمعی. در این متدها، مجموعهای از کلاسهبندها یا مدلهای پیشبینی کننده M1, M2, …, Mk تولید میشوند و نهایتاً با ورود نمونهی ناشناخته[۲۵] ، استراتژیهای رأیگیری برای ترکیب پیشبینیهای مختلف مدلها استفاده میشوند. |
دانلود کامل پایان نامه در سایت pifo.ir موجود است. |
رندوم فارست[۲۶] یکی از مشهورترین و کاراترین متدهای مبتنی بر یادگیری تجمعی در زمینه پیشبینی است که توسط Leo Brieman در سال ۲۰۰۱ ارائه شد. رندوم فارست در واقع حالتی عمومی از متدهای بگینگ به حساب میآید که از مجموعهای از درختهایCART [۲۷] غیر هرس شده[۲۸]، تشکیل شده است [۲۱]. در حالت رگرسیون[۲۹]، جواب نهایی میانگین جوابهای درختان و در حالت کلاسه بندی[۳۰]، کلاس نهایی با توجه به اکثریت آرا تعیین میشود. درختهای CART در واقع درختهای تصمیمگیری هستند که در آنها هر گره[۳۱]ی والد تنها به دو بچه تقسیم میشود و همچنین از معیار Gini به منظور ارزیابی ویژگی ها استفاده میکند [۲۰].
بطور خلاصه، اغلب روشهای اعمال شده ، تنها بر روی اعمال الگوریتمهای مختلف داده کاوی به مدلهای یادگرفته شده از دادههای پیشین[۳۲] هستند، حال آنکه با توجه به ماهیت ناپایداری و وابسته به زمان بودن جریانهای ترافیکی[۳۳]، لازم است تا قبل از یادگیری این مدلها، رفتار جریانهای ترافیکی نیز بررسی شوند. در این راستا، آنالیزهای مختلف کلاسترینگ[۳۴] نیز با هدف ثبت رفتارها و روند تغیرات جریانهای ترافیکی انجام شد تا جریانهای با رفتارهای مشابه قبل از یادگیری، دسته بندی شوند[۲۲, ۲۳]. اکثریت این دستهبندیها بر اساس زمانهای پُرترافیک وکمترافیک صورت میگیرد. همانطور که میدانیم در طی روزهای مختلف، رفتارهای ویژهای در ساعات معینی از روز دنبال میکنند. بنابراین تفکیک و جداسازی و یادگیری مدلهای متفاوت بر مبنای این رفتارها، نقش مؤثری در دقت الگوریتمهای پیشبینی خواهد داشت. نکتهی حائز اهمیت در اینجا ایناست که اغلب روشهایی که رفتارهای جریانهای ترافیکی را بررسی میکنند تنها بر روی دادههای واقعی یا دادههایی که زمان رخدادشان مشخص است، قابل اعمالند. هرچند در برخی از دادههای جمعآوری شده، زمان جمعآوری آنها مشخص نیست. بنابراین، با توجه به اهمیت موضوع، هدف این پایاننامه ارائهی روشی مبتنی بر الگوریتم رندوم فارست است که بدون در اختیار داشتن زمان واقعی جمع آوری داده، توزیع داده را بررسی، رفتارهای ترافیکی را تشخیص و در مرحله یادگیری از آنها استفاده میکند.
نگاهی به فصول پایان نامه
ادامهی مطالب عنوان شده در این پایان نامه در قالب چهار فصل و بصورت زیر سازماندهی شدهاند؛ فصل دوم با عنوان مبانی نظری تحقیق، ضمن ارائهی چهارچوبهای نظری مورد استفاده، قالب ریاضی مسئلهی پیشبینی ترافیک را مورد مطالعه قرار میدهد و مفاهیم اولیه و متغیرهای مسئله را مطرح میکند. فصل سوم نیز با عنوان پیشینه تحقیقات، شامل خلاصهای از نظریات و مطالعات پیشین انجام شده در حوزهی این پایان نامه میباشد که در آن متدهایی که تاکنون کاربرد گستردهتری داشتهاند، در قالب سه گروه تقسیم بندی و مطالعه میشوند.
فصل چهارم نیز تحت عنوان معرفی تکنیک پیشنهادی، مباحثی همچون آنالیز دادهی مورد استفاده، ارائه توصیف کلی از هدف اصلی متد و مراحل اعمال تکنیک ارائه شده را شامل میشود. در راستای مطالعه و بررسی عملکرد تکنیک پیشنهادی، آزمایشهای متعددی صورت گرفته که در فصل پنجم با نام نتایج تجربی، تحلیل ها و نتایج حاصل از اعمال این تکنیکها در مقایسه با دیگر روشها مورد بررسی قرار خواهند گرفت.
در نهایت، نتیجهگیری و خلاصهای از تحلیلهای حاصل از انجام این مطالعات، در فصل ششم ارائه خواهد شد و علاوه بر آن گامهایی در راستای گسترش و ادامه این تحقیق در کارهای آینده، پیشنهاد میشوند.
فصل دوم
مبانی نظری تحقیق
مقدمه
پیشبینی دقیق وضعیت ترافیکی، امری لازم و تأثیرگذار در مدیریت مؤثر سیستمهای حملونقل هوشمند به حساب میآید. از آنجا که دادههای ترافیکی معمولاً دادههایی با حجم بالا هستند، تکنیکهای کاربردی و جدیدی را برای پردازش نیاز دارند. داده کاوی بعنوان یک شاخه از علم کامپیوتر اخیراً توجه زیادی را به خود جلب کرده است که در نتیجهی اعمال آن، آنالیز و پردازش پایگاه داده[۳۵] های بزرگ فراهم میشود. در واقع متدهای داده کاوی معمولاً با هدف استخراج دانش[۳۶] و ساخت مدل از دادههای حجیم بکار گرفته میشوند[۲۴]. از میان روشهای گوناگون داده کاوی، تمرکز تعداد قابل توجهی از تحقیقات به روی یادگیری یادگیری تجمعی [۳۷] ، درختهای تصمیمگیری و بطور ویژه رندوم فارست[۳۸] میباشد که در ادامه توضیح داده خواهند شد[۲۵].
متدهای یادگیری تجمعی
در سالهای اخیر گرایش زیادی به سمت تکنیکهای یادگیری تجمعی مشاهده میشود که ایدهی اصلی آنها استفاده از ترکیبی از مدلها به جای استفاده از یک مدل است. در واقع این متدها با هدف بهبود کارایی مدل نهایی M، مجموعهای از K مدل (کلاسهبند یا پیشبینیکننده[۳۹]) شامل را ترکیب میکنند[۲۰].
تعاریف مفاهیم اولیه
کلاسه بند: فرآیند پیدا کردن یک مدل (یا یک تابع) که قابلیت توصیف دادهای که توسط آن آموزش دیده را دارد، میباشد. در نهایت از این مدل میتوان برای پیشبینی کلاس مربوط به نمونههایی که برچسب[۴۰] کلاس آنها مشخص نیست، استفاده کرد. مدل بدست آمده میتواند با فرمهای متفاوتی از جمله قوانین کلاسه بندی (IF-THEN)[41] ، درخت های تصمیمگیری، فرمولهای ریاضی[۴۲]، شبکه های عصبی و … ارائه شود [۲۰].
درخت تصمیمگیری: در واقع یک ساختار درختی شبه فلوچارت[۴۳] میباشد که هر گره[۴۴]ی تصمیم، نمایانگر یک تصمیمگیری روی مقادیر یک ویژگی است و هر شاخه[۴۵] بیانگر نتیجه آن تصمیمگیری است. همچنین برگ[۴۶]های یک درخت، برچسب کلاسها یا توزیعهای کلاسی[۴۷] را نشان میدهند .[۲۰]
شبکه عصبی مصنوعی: یک مدل ریاضی الهام گرفته از شبکه عصبی انسان است که از گروههایی از نِرونهای[۴۸] مصنوعی تشکیل شده است. اساس محاسبات در این روش بر مبنای اتصال بهم پیوسته[۴۹] چندین واحد پردازشی میباشد و میتواند ساختار خود را در طی مرحله یادگیری تغییر دهد که این موضوع را با تنظیم وزن[۵۰] اتصالها انجام میدهد [۲۶].
پیشبینی کننده: بر خلاف کلاسهبند که برچسبهای گسسته[۵۱] را پیشبینی میکند، پیشبینیکننده، توابع با مقادیر پیوسته[۵۲] را مدل میکند، یعنی به جای برچسب کلاس، مقادیر عددی[۵۳] را پیشبینی میکند. هرچند بطور عمومی اصطلاح پیشبینیکننده هم برای پیشبینی برچسبهای گسسته و هم برچسبهای پیوسته بکار میرود، اما در کتاب های مختلف از جمله کتاب [۲۰]، این واژه مختص پیشبینی مقادیر عددی است.
آنالیز رگرسیون[۵۴] نیز یک متدولوژی آماری است که غالباَ برای پیشبینی مقادیر عددی استفاده میشود. در طول این پایان نامه نیز، اصطلاح رگرسیون معادل پیشبینی کننده عددی استفاده شده است. در واقع از آنجا که دادههای در اختیار گذاشته شده در این پایان نامه، دادههای ترافیکی و به بیانی دقیقتر تعداد وسایل نقلیه عبوری از خیابانهاست، هدف اصلی در اینجا نیز اعمال روشی بهینه مبتنی بر رگرسیون میباشد.
دو دسته از مهم ترین و شناخته شده ترین متدها در زمینهی یادگیری تجمعی ، درختهای بوستینگ[۵۵] ارائه شده توسط [۲۷] و درخت بگینگ[۵۶] توسط [۲۸] می باشد که در ادامه به توضیح آنها میپردازیم.
درخت بوستینگ
در این روش نیز مدل نهایی از مجموعهای از مدلها تشکیل شده است که در آن مدلهای پایهای مبتنی بر درختهای تصمیمگیری هستند. در طی اعمال این الگوریتم، درختها به نمونههایی که توسط درختهای قبلی نادرست پیشبینی شده اند، وزن بیشتری میدهند. در نهایت مدل نهایی بر مبنای رأیگیری[۵۷] وزندار بین درختها انجام میگیرد که این وزنها بر اساس میزان دقت[۵۸] درختها تنظیم میشوند [۲۷].
درخت بگینگ
درخت بگینگ مخفف Bootstrap AggregatlNG (Bagging) می باشد که در این قسمت توضیح داده شده است. الگوریتم بگینگ از مجموعهای از مدلهای پایهای تشکیل شده و به ترتیب زیر عمل میکند. با دریافت مجموعهی آموزشی D با سایز N (تعداد نمونه های داده آموزشی)، به تعداد K مجموعه آموزشی جدید Di، با سایز n<N، تولید میشود که حاصل سمپلگیری یکنواخت[۵۹] و با جایگزینی[۶۰] از مجموعه اولیه D میباشد. همانطور که میدانیم این نوع سمپلگیری بعنوان Bootstrap sample شناخته میشود. K مدل مختلف با استفاده از K زیر مجموعه، آموزش داده میشوند و در نهایت یک مدل نهایی را تشکیل میدهند. این مدل نهایی در رگرسیون از میانگینگیری نتایج مدلها و در کلاسهبندی از رأیگیری بین مدلها حاصل میشود [۲۹]. درخت بگینگ در واقع همان الگوریتم بگینگ است که مدلهای پایهای آن مبتنی بر درختهای تصمیمگیری هستند. همانطور که مشخص است، بر خلاف بوستینگ در بحث بگینگ، مدلهای پایه مستقل از هم ساخته میشوند و به دقت مدلهای قبلی وابسته نیستند. در شکل ۲-۱ الگوریتم مربوط به بگینگ را میبینیم.