تعریف مسئله

امروزه، با توجه به گسترش روزافزون مطالبات حمل‌ونقل و بروز مشکلات ناشی از افزایش ترافیک شهری، ازجمله آلودگی هوا، آلودگی صوتی، مصرف سوخت، اتلاف وقت و انرژی و هزینه‌های تحمیلی آنها، ارائه راهکار مناسب درجهت روان شدن ترافیک از اهمیت ویژه‌ای برخوردار است. از طرفی باتوجه به محدودیت‌های امکانات شهرسازی در مقابل تقاضای انبوه وسایل نقلیه، لازم است تا تمهیداتی کاربردی و امکان‌پذیر برای حل این معضل درنظر گرفته ‌شود. ازآنجا که تاکنون فناوری اطلاعات^[۱] نقش مؤثری درعرصه‌های مختلف صنعتی ایفا کرده است، ورود این تکنولوژی در زمینه‌ی سیستم‌های حمل‌ونقل نیز بعنوان راهکاری مناسب مورد توجه قرارگرفت و منجر به پدیدآمدن سیستم‌های حمل‌ونقل هوشمند^[۲] شد. در واقع تکنولوژی فناوری اطلاعات به عناصر سیستم حمل‌ونقل این امکان را می‌دهد تا با بکارگیری حسگر^[۳]ها و میکروچیپ‌ها و ارتباط آنها از طریق تکنولوژی بی­سیم^[۴]، تبدیل به یک سیستم هوشمند شوند. امروزه سیستم حمل‌ونقل هوشمند با تشکیل سامانه‌ای متشکل از حسگرهای دریافت داده، سامانه‌های پردازش اطلاعات و سامانه‌های ارائه‌ اطلاعات به استفاده کنندگان، گامی مؤثر در راستای مدیریت سیستم حمل‌ونقل و استفاده هوشمندانه از زیرساختارهای موجود، برداشته است [۱]. بطور مثال این سیستم با بکارگیری فناوری‌های متفاوتی همچون هدایت خودرو و سیستم کنترل چراغ‌های راهنمایی، تابلوهای اعلان ترافیک، دوربین سرعت‌سنج و سیستم خودکار شناسایی شماره‌ی خودرو گرفته تا سیستم‌های پیشرفته و پیچیده‌تری که بطور همزمان اطلاعات متفاوتی مانند وضعیت آب و هوا، وضعیت ترافیک، وضعیت جاده‌ها را از منابع متفاوت یکپارچه می­ کند، کنترل این حوزه را بدست‌ گرفته‌ است. از جمله دستاوردهای مهم بکارگیری سیستم حمل‌ونقل هوشمند می‌توان به کاهش ترافیک، کاهش حوادث و تصادفات، امکان انتخاب مسیرهای بهینه با توجه به وضعیت مسیرها، مدیریت حمل‌ونقل عمومی و وسائل نقلیه‌ی امدادی و همچنین امکان اخذ الکترونیکی مواردی همچون عوارض، هزینه‌ی پارکینگ و خرید بلیط که منجر به صرفه جویی در سوخت وانرژی و کاهش هزینه‌های تحمیلی می­ شود، اشاره کرد. عموماً سیستم‌های حمل ونقل هوشمند را تحت عنوان پنج گروه اصلی بررسی می­ کنند که هرکدام حوزه‌های مختلف از این سامانه را شامل می­شوند؛
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

الف) سامانه‌های پیشرفته‌ی اطلاعات مسافرتی^[۵](ATIS) که وظیفه‌ی آن فراهم آوردن اطلاعات وضعیت فعلی ترافیکی و جوّی جاده‌ها، تصادفات و تعمیرات جاده‌ای و همچنین اطلاع رسانی به مسافران و کاربران به منظور استفاده‌ی بهینه از مسیرهای موجود و برقراری تعادل ترافیکی می‌باشد.
ب) سامانه‌های پیشرفته‌ی مدیریت ترافیک^[۶] (ATMS)که اطلاعات ترافیکی جمع­آوری شده از منابع مختلف را بررسی و یکپارچه کرده و از طریق ابزارهای کنترل ترافیک مانند سینگال‌های ترافیکی، کنترل رمپ^[۷] ورودی بزرگراه ها به منظور حفظ تراکم و تابلوهای اطلاع رسانی متغیر موجود در جاده‌ها، کنترل جریان ترافیکی را در دست می‌گیرند.
ج) سامانه‌های پرداخت الکترونیکی^[۸] (EPS) که شامل سیستم جمع‌ آوری الکترونیکی عوارض^[۹](ETC)، سامانه‌های پرداخت عوارض به منظور استفاده از خطوط ویژه‌ی وسایل نقلیه پرسرنشین^[۱۰] توسط وسایل تک سرنشین و همچنین قیمت‌گذاری مسیر^[۱۱] و خطوط پرترافیک می‌باشد.
د) سامانه‌های پیشرفته و هوشمند حمل‌ونقل همگانی^[۱۲] (APTS)اموری در جهت تسهیل ارائه‌ خدمات حمل‌ونقل عمومی همچون تعیین موقعیت خودکار^[۱۳] وسیله نقلیه و اطلاع رسانی به مسافران، خدمات رزرو و تعیین کرایه را نیز شامل می‌شود.
ه) سامانه‌های پیشرفته‌ی کنترل وسائل نقلیه(AVCS)^[14] که شامل سامانه­ی انطباق هوشمند سرعت^[۱۵](ISA)، سامانه‌های هشدار و پیشگیری از تصادفات می‌شوند.
در حوزه‌یAITS وATMS، پیش‌بینی کوتاه مدت ترافیک از عناصر مهم موفقیت سیستم‌های حمل‌ونقل هوشمند محسوب می‌شود، چرا که در راستای کنترل ترافیک نه تنها وضعیت فعلی ترافیک بلکه وضعیت آینده‌ی ترافیک نیز حائز اهمیت است. از این رو الگوریتم‌های پیش‌بینی ترافیک مورد توجه ویژه‌ای در میان محققان این حوزه قرار گرفتند.

چالش‌های مسئله

همانطور که پیشتر بیان شد، مراکز کنترل ترافیک بر اساس جمع­آوری آمار و اطلاعات ترافیکی، پردازش و یکپارچه سازی آنها، تصمیمات لازم جهت مدیریت و کنترل ترافیک را اتخاذ می‌کنند. در راستای بهبود کنترل ترافیک، ATIS و ATMS بعنوان اصلی­ترین اجزاء سیستم حمل­و­نقل هوشمند، علاوه بر وضعیت فعلی ترافیک، به وضعیت آینده ترافیک نیز احتیاج دارند. ازین‌رو پیش ­بینی وضعیت آینده ترافیک از جمله مباحث مهم برای این مراکز به حساب می‌آید تا با بهره گرفتن از آن استراتژی‌های لازم جهت جلوگیری از تراکم و هشدار به رانندگان جهت انتخاب مسیر بهینه، صورت گیرد. تاکنون تحقیقات متعددی در خصوص پیش‌بینی وضعیت ترافیکی آینده انجام شده است که در واقع با بهره گرفتن از داده‌های ثبت شده از وضعیت فعلی ترافیک، ترافیک مربوط به زمان‌های آتی را پیش‌بینی می‌کنند.
بطور معمول داده‌های جمع‌ آوری شده در حوزه‌ی ترافیک، بصورت سری‌های زمانی^[۱۶] در اختیار ما قرار می‌گیرند که در واقع شامل رکوردهای مختلفی هستند که در بازه های زمانی مساوی و در طی اندازه‌گیری‌های متوالی بدست می‌آیند. با بهره گرفتن از داده‌های فعلی و گذشته، مقادیر آن‌ها در آینده پیش‌بینی می‌شوند [۲]. تاکنون تکنیک‌های متفاوتی در زمینه‌ی پیش‌بینی ترافیک بکار گرفته شده است که از جمله‌ی آن‌ها می‌توان به روش‌های کالمن فیلترینگ^[۱۷] [۴,۳]، متدهای آماری غیرپارامتریک [۵,۶] ^[۱۸]، روش‌های یادگیری متوالی[۷] ^[۱۹]، مدل‌های شبکه‌عصبی^[۲۰] [۸-۱۱] و آنالیزهای سری‌های زمانی[۱۳-۱۷] اشاره کرد. از مهمترین چالش‌های اعمال این الگوریتم‌ها، حجم بالای داده‌های ترافیکی است که منجر شده تا اخیراً گرایش تحقیقات به سمت استفاده از الگوریتم‌های داده کاوی^[۲۱] باشد.
همانطور که می‌دانیم تکنیک‌های داده کاوی قابلیت استخراج اطلاعات از داده‌هایی با حجم بسیار بالا همچون داده‌های ترافیکی را دارا هستند. از میان آن‌ها روش‌های مبتنی بر درختهای تصمیم‌گیری^[۲۲] بطور گسترده‌ای در حوزه‌ی ترافیک مورد استفاده قرار گرفته است[۱۸,۱۹]. همچنین متدهای یادگیری تجمعی^[۲۳] همانند بگینگ و بوستینگ با توجه به کارایی بالا، مورد توجه ویژه‌ای واقع شدند. ایده‌ی اصلی آن‌ها ساخت مجموعه‌ای از مدل‌ها و ترکیب نتایج آن‌ها با هدف بهبود دقت^[۲۴] یادگیری می‌باشد[۴۷]. در شکل -۱۱ معماری کلی الگوریتم‌های یادگیری تجمعی را می‌بینیم که از کتاب [۲۰] آورده شده است.

شکل ۱-۱٫ معماری کلی مربوط به متدهای یادگیری تجمعی. در این متدها، مجموعه‌ای از کلاسه‌بندها یا مدل‌های پیش‌بینی کننده M₁, M₂, …, M_k تولید می‌شوند و نهایتاً با ورود نمونه‌ی ناشناخته^[۲۵] ، استراتژی‌های رأی‌گیری برای ترکیب پیش‌بینی‌های مختلف مدل‌ها استفاده می‌شوند.

رندوم فارست^[۲۶] یکی از مشهورترین و کاراترین متدهای مبتنی بر یادگیری تجمعی در زمینه پیش‌بینی است که توسط Leo Brieman در سال ۲۰۰۱ ارائه شد. رندوم فارست در واقع حالتی عمومی از متدهای بگینگ به حساب می‌آید که از مجموعه‌ای از درخت‌هایCART ^[۲۷] غیر هرس شده^[۲۸]، تشکیل شده است [۲۱]. در حالت رگرسیون^[۲۹]، جواب نهایی میانگین جواب‌های درختان و در حالت کلاسه بندی^[۳۰]، کلاس نهایی با توجه به اکثریت آرا تعیین می‌شود. درخت‌های CART در واقع درخت‌های تصمیم‌گیری هستند که در آن‌ها هر گره^[۳۱]ی والد تنها به دو بچه تقسیم می‌شود و همچنین از معیار Gini به منظور ارزیابی ویژگی ها استفاده می‌کند [۲۰].
بطور خلاصه، اغلب روش‌های اعمال شده ، تنها بر روی اعمال الگوریتم‌های مختلف داده کاوی به مدل‌های یادگرفته شده از داده‌های پیشین^[۳۲] هستند، حال آنکه با توجه به ماهیت ناپایداری و وابسته به زمان بودن جریان‌های ترافیکی^[۳۳]، لازم است تا قبل از یادگیری این مدل‌ها، رفتار جریان‌های ترافیکی نیز بررسی شوند. در این راستا، آنالیزهای مختلف کلاسترینگ^[۳۴] نیز با هدف ثبت رفتارها و روند تغیرات جریان‌های ترافیکی انجام شد تا جریان‌های با رفتارهای مشابه قبل از یادگیری، دسته بندی شوند[۲۲, ۲۳]. اکثریت این دسته‌بندی‌ها بر اساس زمان‌های پُرترافیک وکم‌ترافیک صورت می‌گیرد. همانطور که می‌دانیم در طی روزهای مختلف، رفتارهای ویژه‌ای در ساعات معینی از روز دنبال می‌کنند. بنابراین تفکیک و جداسازی و یادگیری مدل‌های متفاوت بر مبنای این رفتارها، نقش مؤثری در دقت الگوریتم‌های پیش‌بینی خواهد داشت. نکته‌ی حائز اهمیت در اینجا این‌است که اغلب روش‌هایی که رفتارهای جریان‌های ترافیکی را بررسی می‌کنند تنها بر روی داده‌های واقعی یا داده‌هایی که زمان رخدادشان مشخص است، قابل اعمالند. هرچند در برخی از داده‌های جمع‌ آوری شده، زمان جمع‌ آوری آنها مشخص نیست. بنابراین، با توجه به اهمیت موضوع، هدف این پایان‌نامه ارائه‌ روشی مبتنی بر الگوریتم رندوم فارست است که بدون در اختیار داشتن زمان واقعی جمع آوری داده، توزیع داده را بررسی، رفتارهای ترافیکی را تشخیص و در مرحله یادگیری از آنها استفاده می‌کند.

نگاهی به فصول پایان نامه

ادامه‌ی مطالب عنوان شده در این پایان نامه در قالب چهار فصل و بصورت زیر سازماندهی شده‌اند؛ فصل دوم با عنوان مبانی نظری تحقیق، ضمن ارائه‌ چهارچوب‌های نظری مورد استفاده، قالب ریاضی مسئله‌ی پیش‌بینی ترافیک را مورد مطالعه قرار می‌دهد و مفاهیم اولیه و متغیرهای مسئله را مطرح می‌کند. فصل سوم نیز با عنوان پیشینه تحقیقات، شامل خلاصه‌ای از نظریات و مطالعات پیشین انجام شده در حوزه‌ی این پایان نامه می‌باشد که در آن متدهایی که تاکنون کاربرد گسترده‌تری داشته‌اند، در قالب سه گروه تقسیم بندی و مطالعه می‌شوند.
فصل چهارم نیز تحت عنوان معرفی تکنیک پیشنهادی، مباحثی همچون آنالیز داده‌ی مورد استفاده، ارائه توصیف کلی از هدف اصلی متد و مراحل اعمال تکنیک ارائه شده را شامل می‌شود. در راستای مطالعه و بررسی عملکرد تکنیک پیشنهادی، آزمایش‌های متعددی صورت گرفته که در فصل پنجم با نام نتایج تجربی، تحلیل ها و نتایج حاصل از اعمال این تکنیک‌ها در مقایسه با دیگر روش‌ها مورد بررسی قرار خواهند گرفت.
در نهایت، نتیجه‌گیری و خلاصه‌ای از تحلیل‌های حاصل از انجام این مطالعات، در فصل ششم ارائه خواهد شد و علاوه بر آن گام‌هایی در راستای گسترش و ادامه این تحقیق در کارهای آینده، پیشنهاد می‌شوند.
فصل دوم

مبانی نظری تحقیق

مقدمه

پیش‌بینی دقیق وضعیت ترافیکی، امری لازم و تأثیرگذار در مدیریت مؤثر سیستم‌های حمل‌ونقل هوشمند به حساب می‌آید. از آنجا که داده‌های ترافیکی معمولاً داده‌هایی با حجم بالا هستند، تکنیک‌های کاربردی و جدیدی را برای پردازش نیاز دارند. داده کاوی بعنوان یک شاخه از علم کامپیوتر اخیراً توجه زیادی را به خود جلب کرده است که در نتیجه‌ی اعمال آن، آنالیز و پردازش پایگاه داده^[۳۵] های بزرگ فراهم می‌شود. در واقع متدهای داده کاوی معمولاً با هدف استخراج دانش^[۳۶] و ساخت مدل از داده‌های حجیم بکار گرفته می‌شوند[۲۴]. از میان روش‌های گوناگون داده کاوی، تمرکز تعداد قابل توجهی از تحقیقات به روی یادگیری یادگیری تجمعی ^[۳۷] ، درخت‌های تصمیم‌گیری و بطور ویژه رندوم فارست^[۳۸] می‌باشد که در ادامه توضیح داده خواهند شد[۲۵].

متدهای یادگیری تجمعی

در سال‌های اخیر گرایش زیادی به سمت تکنیک‌های یادگیری تجمعی مشاهده می‌شود که ایده‌ی اصلی آن‌ها استفاده از ترکیبی از مدل‌ها به جای استفاده از یک مدل است. در واقع این متدها با هدف بهبود کارایی مدل نهایی M، مجموعه‌ای از K مدل (کلاسه‌بند یا پیش‌بینی‌کننده^[۳۹]) شامل را ترکیب می‌کنند[۲۰].

تعاریف مفاهیم اولیه

کلاسه بند: فرایند پیدا کردن یک مدل (یا یک تابع) که قابلیت توصیف داده‌ای که توسط آن آموزش دیده را دارد، می‌باشد. در نهایت از این مدل می‌توان برای پیش‌بینی کلاس مربوط به نمونه‌هایی که برچسب^[۴۰] کلاس آنها مشخص نیست، استفاده کرد. مدل بدست آمده می‌تواند با فرم‌های متفاوتی از جمله قوانین کلاسه بندی (IF-THEN)^[41] ، درخت های تصمیم‌گیری، فرمول‌های ریاضی^[۴۲]، شبکه های عصبی و … ارائه شود [۲۰].
درخت تصمیم‌گیری: در واقع یک ساختار درختی شبه فلوچارت^[۴۳] می‌باشد که هر گره^[۴۴]ی تصمیم، نمایانگر یک تصمیم‌گیری روی مقادیر یک ویژگی است و هر شاخه^[۴۵] بیانگر نتیجه آن تصمیم‌گیری است. همچنین برگ^[۴۶]های یک درخت، برچسب کلاس‌ها یا توزیع‌های کلاسی^[۴۷] را نشان می‌دهند .[۲۰]
شبکه عصبی مصنوعی: یک مدل ریاضی الهام گرفته از شبکه عصبی انسان است که از گروه‌هایی از نِرون‌های^[۴۸] مصنوعی تشکیل شده است. اساس محاسبات در این روش بر مبنای اتصال بهم پیوسته^[۴۹] چندین واحد پردازشی می‌باشد و می‌تواند ساختار خود را در طی مرحله یادگیری تغییر دهد که این موضوع را با تنظیم وزن^[۵۰] اتصال‌ها انجام می‌دهد [۲۶].
پیش‌بینی کننده: بر خلاف کلاسه‌بند که برچسب‌های گسسته^[۵۱] را پیش‌بینی می‌کند، پیش‌بینی‌کننده، توابع با مقادیر پیوسته^[۵۲] را مدل می‌کند، یعنی به جای برچسب کلاس، مقادیر عددی^[۵۳] را پیش‌بینی می‌کند. هرچند بطور عمومی اصطلاح پیش‌بینی‌کننده هم برای پیش ­بینی برچسب‌های گسسته و هم برچسب‌های پیوسته بکار می‌رود، اما در کتاب های مختلف از جمله کتاب [۲۰]، این واژه مختص پیش ­بینی ‌مقادیر عددی است.
آنالیز رگرسیون^[۵۴] نیز یک متدولوژی آماری است که غالباَ برای پیش ­بینی مقادیر عددی استفاده می‌شود. در طول این پایان نامه نیز، اصطلاح رگرسیون معادل پیش ­بینی کننده عددی استفاده شده است. در واقع از آنجا که داده‌های در اختیار گذاشته شده در این پایان نامه، داده‌های ترافیکی و به بیانی دقیق‌تر تعداد وسایل نقلیه عبوری از خیابان‌هاست، هدف اصلی در این‌جا نیز اعمال روشی بهینه مبتنی بر رگرسیون می‌باشد.
دو دسته از مهم ترین و شناخته شده ترین متدها در زمینه‌ی یادگیری تجمعی ، درخت‌های بوستینگ^[۵۵] ارائه شده توسط [۲۷] و درخت بگینگ^[۵۶] توسط [۲۸] می باشد که در ادامه به توضیح آن‌ها می‌پردازیم.

درخت بوستینگ

در این روش نیز مدل نهایی از مجموعه ­ای از مدل‌ها تشکیل شده است که در آن مدل‌های پایه­ای مبتنی بر درخت‌های تصمیم‌گیری هستند. در طی اعمال این الگوریتم، درخت‌ها به نمونه‌هایی که توسط درخت‌های قبلی نادرست پیش ­بینی شده اند، وزن بیشتری می‌دهند. در نهایت مدل نهایی بر مبنای رأی‌گیری^[۵۷] وزن‌دار بین درخت‌ها انجام می‌گیرد که این وزن‌ها بر اساس میزان دقت^[۵۸] درخت‌ها تنظیم می‌شوند [۲۷].

درخت بگینگ

درخت بگینگ مخفف Bootstrap AggregatlNG (Bagging) می باشد که در این قسمت توضیح داده شده است. الگوریتم بگینگ از مجموعه ­ای از مدل‌های پایه‌ای تشکیل شده و به ترتیب زیر عمل می‌کند. با دریافت مجموعه‌ی آموزشی D با سایز N (تعداد نمونه های داده آموزشی)، به تعداد K مجموعه آموزشی جدید D_i، با سایز n<N، تولید می‌شود که حاصل سمپل‌گیری یکنواخت^[۵۹] و با جایگزینی^[۶۰] از مجموعه اولیه D می‌باشد. همان‌طور که می‌دانیم این نوع سمپل‌گیری بعنوان Bootstrap sample شناخته می‌شود. K مدل مختلف با بهره گرفتن از K زیر مجموعه، آموزش داده می‌شوند و در نهایت یک مدل نهایی را تشکیل می‌دهند. این مدل نهایی در رگرسیون از میانگین‌گیری نتایج مدل‌ها و در کلاسه‌بندی از رأی‌گیری بین مدل‌ها حاصل می‌شود [۲۹]. درخت بگینگ در واقع همان الگوریتم بگینگ است که مدل‌های پایه‌ای آن مبتنی بر درخت‌های تصمیم‌گیری هستند. همانطور که مشخص است، بر خلاف بوستینگ در بحث بگینگ، مدل‌های پایه مستقل از هم ساخته می‌شوند و به دقت مدل‌های قبلی وابسته نیستند. در شکل ۲-۱ الگوریتم مربوط به بگینگ را می­بینیم.

Algorithm: Bagging
Input :