از جمله معایب این روشها، مناسب نبودن آنها برای پیش‌بینی سری‌های زمانی غیرخطی است. در سال ۲۰۰۳ محققان به بررسی این موضوع پرداختند و تحقیقات گسترده‌ای را به منظور ارزیابی سیستم پیاده‌سازی شده‌ی در خصوص پیش‌بینی سری‌های زمانی غیرخطی با در نظرگرفتن پارامترها و شرایط متفاوت ترافیکی، انجام دادند [۱۷]. همچنین یک مدل خطی برای امتحان تاثیرات سطح تراکم ترافیکی، prediction horizon و تعاملات آنها روی خطای نسبی پیش‌بینی سرعت ترافیکی، ارائه دادند. نتایج حاصل، بیانگر افت کارایی مدل در مقابل رشد تراکم بود. همچنین نشان داده شد که همه پارامترها تاثیر بسزایی درمیزان خطای نسبی دارند. علاوه بر این تعاملات مهم بین پارامترهای مهم با اندیس تراکم، نشان‌داد که پیش‌بینی کوتاهمدت و rolling horizon در شرایط تراکم، مطلوب‌ترند[۲۲] .
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
بطور کلی، تکنیک‌های مبتنی بر آنالیزهای سری زمانی برای تشخیص رفتار فصلی[۱۱۷] داده‌های ترافیکی گسترش یافتند. هرچند، واضح است که رفتار فصلی در خصوص پریودهای طولانی مدت رخ میدهد. همان طور که پیش‌تر بیان شد، هدف این پایان نامه پیش بینی کوتاه مدت ترافیک است. بنابراین واضح است که در این بازه‌های زمانی کوتاه، روند stochastic و نه فصلی، دیده می‌شود. پس به منظور اعمال روشهای تخمین مبتنی بر آنالیزهای سری زمانی، نیاز به انجام پیش پردازش‌هایی شامل stationarity، نویز سفیدو غیره میباشد [۲۲].
از طرف دیگر، اعمال روشهای کلاسیک مبتنی بر آنالیزهای سری زمانی، نیازمند در اختیار داشتن یک روند صاف‌تر[۱۱۸]، با از حذف نوسانات زمانی از داده‌های حجیم ترافیکی میباشد. در سال ۲۰۰۳، Washington این هدف را در پیش گرفت. هرچند این روش برای پیش بینی کوتاه مدت، بدلیل از دست دادن اطلاعات مفید با شکست مواجه شد [۳۸].
روشهای مبتنی بر مدلهای شبکه عصبی مصنوعی
بر خلاف آنالیزهای سری زمانی که غالباً بر روی ساختارهای داخلی داده، مانند همبستگی و تغییرات فصلی تکیه دارند، روشهای شبکه عصبی قابلیت تطبیق با هر پایگاه داده و با بکارگیری توابع سیگمُید مختلف و لایه‌های مخفی کافی، دارند.
در سال ۱۹۹۸، برای پیش‌بینی سری‌های زمانی، شبکه‌های عصبی RBF [۱۱۹] بکار گرفته شدند[۹]. RBFN در واقع یک شبکه عصبی‌ایست که از توابع radial basis بعنوان تابع‌های activation استفاده می‌کند و خروجی آن یک ترکیب خطی از توابع radial basis اعمال شده به روی ورودی‌ها و پارامترهای نرون‌هاست. بطور معمول این شبکه‌ها در جهت تخمین تابع، پیش‌بینی سری‌های زمانی و کنترل سیستم‌ها استفاده میشوند. داده‌ی مورد استفاده در آن مطالعه، مشاهدات واقعی متعلق به نرخ ترافیکی آزاد راه‌ها بود که به بازه های ۵-دقیقهای در آمده بودند. این روش با متد [۱۲۰]ESM و سری‌های تیلور[۱۲۱] ، متد double exponential moothing BPN[122] مقایسه شد که از میان آنها RBFN با صرف زمان محاسباتی[۱۲۳] کمتری نسبت به BPN، بهترین کارآیی را نتیجه داد[۲۲] .
در [۱۰] یک سیستم مبتنی بر شبکه عصبی تأخیر زمانی[۱۲۴] (TDNN) ارائه شد تا بر اساس پروفایل‌های گذشته مسیرها و همسایه‌های آنها، پیش بینی را انجام دهد. این مطالعه بر روی داده‌های واقعی و مصنوعی، اعمال شد تا جریانهای ترافیکی را پیش‌بینی کند. نتایج بیانگر آن بود که بکارگیری ۳ حلقه در دو جهت یک مسیر برای پیش‌بینی کافی است. از دیگر نتایج مهم این مطالعه این بود که برای رسیدن به دقت بالا، باید سطح دامنه‌ی داده‌ها در حد Horizon Prediction باشد.
به منظور بهبود استفاده از شبکه‌های TDNN، یک مدل غیر پارامتریک و داینامیک time-delay recurrent wavelet برای تخمین جریان ترافیکی توسط [۸] ارائه شد. این تکنیک رفتارهای موجود در جریانهای ترافیکی همانند منحصربفرد[۱۲۵]، خود مشابهی[۱۲۶] و و فرکتال[۱۲۷] را در روند مدلسازی دخیل می‌کند. همچنین برای تخمین بُعد بهینه ورودی سری‌های زمانی ترافیک از توابع آماری همبستگی[۱۲۸] استفاده کردند. این روش با دخیل کردن زمان، شامل زمان رخداد در چه هنگام از روز و چه روز از هفته، توانست برای پیش بینی طولانی- مدت و کوتاه مدت کاربرد مناسبی داشته باشد.
علاوه بر روشهای ذکر شده، روشهای ترکیبی دیگری از شبکه‌های عصبی و دیگر الگوریتم‌ها نیز ارائه شدند. بطور مثال، در سال ۲۰۰۵ ترکیبی از یک مدل شبکه عصبی و الگوریتم ژنتیک[۱۲۹] در نظر گرفته شد تا با بهره گرفتن از GA، ساختار شبکه و قوانین یادگیری را بهینه کند. این روش با مدلهای ARIMA و state-space مقایسه و بر روی داده‌های یک خیابان اصلی در بازه‌ی ماه‌های ژانویه تا مِی سال۲۰۰۰، از شهر یونان ارزیابی شد. نتایج این مقایسات کارآیی روش را بخوبی نشان داد [۱۱].
در سال ۲۰۱۰ نیز، متدی مبتنی بر شبکه های عصبی بر روی داده‌های مورد استفاده در این پایان نامه ارائه شد. این روش RBM [۱۳۰] را به همراه دو الگوریتم دیگر؛ فاکتورگیری شبه تجزیه‌ی مقدارهای منفرد[۱۳۱] (SVD-like) و حداقل مربعات خطی[۱۳۲] (LLS) را به کار گرفت تا تراکم ترافیک در ۱۰ دقیقه بعدی را پیش بینی کند. در نظر گرفتن انواع پارامترها با این سه روش منجر به تشکیل یک ترکیب خطی از ۲۰ پیش بینیکننده شد. همچنین واحدهای مخفی[۱۳۳] در این مدل توزیع شرطی برنولی[۱۳۴] در نظر گرفته شدند. علاوه بر این، آموزش فاکتورگیری SVD-like، با گام‌های Gradiant descent و LLS نیز بر اساس رگرسیون خطی وزن‌دار[۱۳۵] انجام شدند. این تحقیق که در راستای مسابقهی ICDM (2010) ارائه شد، در بخش پیش‌بینی ترافیک مقام اول را کسب کرد و کارآیی قابل توجهی در مقایسه با دیگر روشها نشان داد.
علیرغم دقت بالای مدلهای شبکه عصبی مصنوعی و تطابق آن با انواع داده ها، مشکل عمده‌ی آنها، هزینه تخمین تعداد زیادی پارامتر میباشد.
روشهای مبتنی بر الگوریتمهای داده کاوی
در سالهای اخیر تمایل بسیاری از محققان به سمت استفاده از روشهای داده کاوی بوده است که در این زیر فصل به اشاره‌ی برخی از آنها میپردازیم. در واقع با توجه به اینکه داده های ترافیکی معمولاً سایز بالایی دارند، الگوریتمهای داده‌کاوی از جمله روشهای مناسب در مواجهه با این نوع پایگاه داده ها به حساب میآیند.
بطور مثال در سال ۲۰۰۶، Zhong و همکارانش، از متد ماشین بردار پشتیبانی[۱۳۶] (SVM) که یک روش یادگیری ماشین[۱۳۷] (ML)بحساب می‌آید، استفاده کرد[۳۹]. این الگوریتم از جمله روشهای یادگیری با نظارت محسوب می‌شود و مبنای آن بر اساس دسته بندی خطی داده ها میباشد. این متد هنگام پیدا کردن خط مناسب برای جداسازی داده های متعلق به کلاسهای مختلف، خطی را انتخاب می‌کند که حاشیه اطمینان بیشتری داشته باشد و برای حل معادله این خط، از روش برنامه نویسی درجه دوم[۱۳۸](QP) استفاده می‌کند. Zhang با بکارگیری این روش سعی در غلبه به مشکل مناسب سازی بیش از حد[۱۳۹] و مینیمم محلی[۱۴۰] مربوط به شبکه عصبی رو به جلو چندلایه[۱۴۱](MLFNN) داشت. این روش به روی پایگاه پایگاه‌های دادهای نرخ ترافیک که از ۴ مسیر جمع آوری شده بود، اعمال شد. داده ها به بازه های ۵-دقیقهای متراکم[۱۴۲] شدند. کارآیی روش در خصوص پیش بینی یک و دو گام بعدی با معیارهای درصد خطای مطلق میانگین[۱۴۳] (MAPE) و خطای مجموع مجذور مربعات[۱۴۴] (RMSE) مورد ارزیابی قرار گرفت.
از جمله الگوریتمهای مشهور در حوزه داده کاوی که در سالهای اخیر بطور گسترده‌ای بر روی داده های ترافیکی و با هدف پیش بینی ترافیکی استفاده شد، الگوریتمهای مبتنی بر درختهای تصمیم‌گیری و متدهای Ensembling است [۱۸,۱۹,۲۵]. همانطور که پیش‌تر بیان شد، متدهای Ensembling از جمله روش‌هایی است که با ترکیب مدلهای پایه، سعی در بهبود کارآیی خود دارد.
رندوم فارست از جمله الگوریتمهای Ensembling به شمار می‌آید که از درختهای تصمیم‌گیری CART بعنوان مدلهای پایه استفاده می‌کند . این الگوریتم در سال ۲۰۱۰ به منظور پیش بینی کوتاهمدت ترافیک توسط Carlos بکار گرفته شد. پایگاه داده مورد استفاده، همانند داده‌ی مورد استفاده در این پایان نامه (داده‌ی بخش ترافیک مربوط به مسابقه ICDM سال ۲۰۱۰) بود که هدف آن پیش بینی ترافیک۱۰-دقیق آینده، با داشتن نرخ ترافیک مربوط به نیم ساعت اول هر ساعت است . در این الگورتیم از یک ترکیب محدب، متشکل از چند مدل استفاده شده که هر کدام از مدلها از دیدهای متفاوتی، اطلاعات درون داده را کاوش می‌کنند. به بیانی دقیق‌تر، انواع مختلفی از اطلاعات همانند اطلاعات محلی[۱۴۵]، اطلاعات سراسری[۱۴۶] و اطلاعات موجود در ساختار همبستگی[۱۴۷]، فضا[۱۴۸] و زمان در داده وجود دارد که هرکدام از مدلها قابلیت متفاوتی در خصوص کاوش این اطلاعات دارند. بنابراین با ترکیب این مدلها میتوان از انواع این اطلاعات استفاده کرد و دقت مدل نهایی را افزایش داد. مدل نهایی این الگوریتم از ترکیب وزن دار الگوریتمهای رندوم فارست و دو نوع متد نزدیکترین همسایگی[۱۴۹] حاصل شد که دقت قابل مقایسه‌ای نسبت به دیگر الگوریتم‌ها داشت. شایان ذکر است که این روش در مسابقه ICDM سال ۲۰۱۰ مقام دوم را کسب کرد [۱۹].
یک روش دیگر که شباهت بسیاری به روش پیشنهادی ما دارد، روشی است که توسط Hamner در سال۲۰۱۰ ارائه شده است. این روش نیز از الگوریتم رندوم فارست استفاده می‌کند و بر روی داده‌ی نرخ ترافیکی مربوط به ۲۰ مسیر اعمال شده است. پایگاه داده‌ی مورد استفاده نیز پایگاه داده‌ی ارائه شده در مسابقه ICDM سال ۲۰۱۰ میباشد که هدف آن پیش‌بینی مجموع تعداد ماشین های عبوری در بازه‌ی ۵۰- ۴۱ دقیقه‌ی یک ساعت، با داشتن اطلاعات نیم ساعت اول آن است. الگوریتم این روش بدین صورت است که با اعمال مراحل down sampling وresampling ، بترتیب، ابتدا بُعد را کاهش داده و سپس نمونهبرداریهای مختلفی را روی مجموعه آموزشی انجام میدهد که منجر به ساخت مجموعههای متفاوت با سایز متفاوت می‌شود. در گام بعد، از الگوریتم رگرسیون رندوم فارست برای آموزش این مجموعهها استفاده می‌کند و نهایتاً با در نظر گرفتن مجموعههای متفاوت، یک مدل Ensemble of RF می‌سازد. بهترین دقت بدست آمده با این روش مربوط به اعمال بزرگترین مجموعه نمونه برداری با سایز ۵۵۰۰۰ نمونه است که البته یکی از مشکلات این روش به حساب می‌آید. در واقع اگر تعداد مسیرهای مورد بررسی افزایش یابد، ممکنست این الگوریتم دچار مشکل شود. بنابراین اعمال روشهای انتخاب ویژگی بعنوان راه‌حل این روش، پیشنهاد شد[۱۸].
یکی از مشکلاتی که به روشهای مشابه به دو روش اخیر وارد است، این است که تنها اساسِ این روشها، اعمال الگوریتمهای یادگیری متفاوت روی داده های پیشین[۱۵۰] و پیدا کردن بهترین الگوریتم است. در حالی که با توجه به ماهیت وابسته به زمان داده‌های ترافیکی، لازم است تا رفتارهای جریانهای ترافیکی نیز قبل از مدلسازی یا در روند آن منعکس شود. در این راستا مدلهایی بکار گرفته شدند که آنالیزهای کلاستربندی را با هدف ثبت روند تغییرات جریانهای ترافیکی اعمال کردند [۲۲ , ۲۳]. بطور نمونه، در سال ۲۰۱۰، از یک مدل پنهان مارکوف[۱۵۱] و مدل اتفاقی یک-گامی[۱۵۲] برای پیش بینی ترافیک استفاده کرد. این روش بر روی داده واقعی ۶ سال مربوط به شهر Orlando از فلوریدا اعمال شد [۲۲].
مدل پنهان مارکوف در واقع مدلی است آماری که به صورت یک فرایند مارکوف با حالت های مشاهده نشده (پنهان) فرض می شود. انجام کلاسهبندی با مدل مارکوف بدین صورت است که یک مدل و تعدادی از مشاهدات را داریم و هدف محاسبه احتمال کل تولید شدن یک توالی توسط آن مدل است[۴۰]. به بیانی دقیق تر، جمع احتمالات همه مسیرهایی که منجر به تولید این توالی میشوند، محاسبه می شود. بنابراین هردوی این مدلها تکیه بر محاسبه احتمال تغییرحالت ترافیک از یک وضعیت به وضعیتی دیگر، دارند. علاوه بر این، در این روش پس از مرحله انتخاب ویژگی، یک مرحله جداسازی[۱۵۳] بر مبنای آنالیز کلاسترینگ صورت گرفت. با انجام مرحله کلاسترینگ، پترن های ترافیکی بررسی شده و رنج مربوط به مقادیر ویژگی ها نیز تقریب و بر مبنای آن گروه های مختلف تشکیل میشوند. نتایج بدست آمده توسط این الگوریتم نشان داد که آموزش تنها یک مدل منحصر به فرد برای پریودهای اوج ترافیک، کافی نیست چرا که داده‌ی ترافیکی علاوه بر خصوصیات پیکی، رفتار غیرپیکی نیز دارد. همچنین نشان داده شد که چون تغییرات ترافیکی مربوط به پریودهای اوج ترافیک از یک روند پیروی نمیکنند، روش های احتمالی[۱۵۴] از جمله روش های مناسب برای پیش بینی آنها به شمار میآیند.
فصل چهارم
تکنیک پیشنهادی
مقدمه
ارائه راهکارهای مؤثر در جهت برقراری تعادل ترافیکی و کاهش نرخ ترافیک[۱۵۵]، علاوه بر در دسترس بودن داده های real-time ، تکیه زیادی به وضعیت ترافیکی آینده دارند. بدین سبب، روشهای پیش بینی ترافیک، اهمیت ویژه‌ای برای مراکز کنترل ترافیک دارند تا بتوانند با استفاد از آنها، برنامه‌ریزی ترافیکی مناسبی اعمال کنند. تاکنون، تکنیک‌های زیادی در راستای بهبود پیش بینی کوتاهمدت ترافیک انجام گرفته است، هرچند اکثریت این روشها مبتنی بر ساخت مدل بهینه از روی داده های قدیمی هستند. از جمله نکات مهم این پایان نامه دخیل کردن رفتار داده‌ی مورد بررسی قبل از انجام مدلسازی است.
همان طور که میدانیم جریانهای ترافیکی در زمانهای مختلف، رفتارهای متفاوت ارائه می دهند، یعنی، داده های ترافیکی ماهیت پویای وابسته به زمان دارند. در همین راستا، در این پایان نامه سعی بر آنست تا این رفتارها تشخیص داده شده و در جهت افزایش دقت پیش بینی بکارگرفته شوند. از طرف دیگر، از آنجا که داده‌ی تحت بررسی در این پایان نامه، مربوط به مسابقه پیش بینی ترافیک IEEE ICDM در سال ۲۰۱۰ میباشد و جزء داده های مصنوعی محسوب می شود، زمان واقعی مربوط به جمعآوری داده ها مشخص نیست. بنابراین در تکنیک پیشنهادی، آنالیزهایی بر روی توزیع این داده‌ها انجام شده تا بتوان رفتارها و روندهای حاوی اطلاعات را در آنها تشخیص داد. در نهایت روش پیشنهادی قادر است تا با بهره گرفتن از استخراج این رفتارها، دقت مدلهای پیش‌بینی ترافیک را در حد قابل ملاحظه‌ای افزایش دهد. در ادامه به توضیح خصوصیات داده‌ی مورد استفاده و چندین مفهوم که تکنیک پیشنهادی از آنها استفاده می کند، میپردازیم.
خصوصیات داده
بطور معمول جمع آوری داده های ترافیکی از طریق شبکه‌ای از حسگرها[۱۵۶] انجام می شود که قابلیت فراهم آوردن پارامترهای استاندارد ترافیکی، از قبیل نرخ ترافیک، سرعت[۱۵۷] جابجایی و ظرفیت اشغال شده[۱۵۸] را دارند. در حال حاضر تکنولوژی غالب، که در خصوص جمع آوری داده های ترافیکی بکار گرفته شده، رکوردهای ثبت ترافیک اتوماتیک[۱۵۹] یا ATR ها هستند. ATR ها حلقههای مغناطیسی تعبیه شده در زیر زمین هستند، که قابلیت شمارش وسائل نقلیه‌هایی که از روی آنها رد میشوند را دارند. دادهجمع آوری شده از طریق ATR ها می تواند به منظور پیش بینی کوتاهمدت و طولانیمدت و با هدف برنامه ریزی حمل و نقل شهری استفاده شوند. این موضوع به طور خاص در مسابقه پیش بینی ترافیک مربوط به IEEE ICDM در سال ۲۰۱۰ مطرح شد. این مسابقه در سه بخش متفاوت با عناوین Traffic, JAM , GPS برگزار شد. تمرکز این پایان نامه به روی بخش Traffic است که هدف آن پیش بینی کوتاهمدت نرخ ترافیک در خیابانهای مختلف است. داده در اختیار گذاشته شده در این بخش حاصل یک شبیه ساز وضعیت ترافیکی[۱۶۰] بسیار قدرتمند با نام اختصاری [۱۶۱]TSF است [۴۱]. این ابزار پیچیده با هدف شبیه سازی و بررسی ترافیک شهری، در دانشگاه Warsaw ارائه شد. این شبیه ساز از نقشههای واقعی شهرWarsaw(Poland) استفاده میکرد که از پروژه OpenStreetMap آورده شده بود. در شکل ۴-۱ صفحه نمایش شبیه ساز TSF نشان داده شده است. لازم به ذکر است که این شبیهساز در آینده قابل اعمال به نقشه هر شهری خواهد بود. در این ابزار قوانین مختلفی در جهت مدلسازی چراغهای راهنما، چهارراه‌ها و خیابانهای چند باندی در نظر گرفته شد، تا ترافیک واقعی به طور دقیقی باز تولید شود [۴۲].
| |
| شکل ۴-۱٫ صفحه‌ی نمایشTraffic Simulation Framework(TSF) ، ابزاری قدرتمند برای شبیه‌سازی ترافیک شهری، توسعه یافته در دانشگاه Warsaw. این ابزار از نقشههای واقعی شبکه‌ی جاده‌ای شهر استفاده می‌کند که در این شکل به روی نقشه شهر warsaw(Poland) اعمال شده است. |
مجموعه داده‌های مورد استفاده
به منظور فراهم کردن داده‌ی ترافیک، شبیه ساز ترافیک TSF، نرخ ترافیکی مربوط به دو جهت از ۱۰ خیابان شهر Warsaw را تولید کرده است. موقعیت این ۲۰ مسیر در شکل ۴-۲ با رنگ قرمز نشان داده شده است.
این داده‌ها در بازه‌های یک دقیقهای از نرخ ترافیکی مربوط به این خیابان‌ها جمع آوری شده است. به بیانی دقیق‌تر، هر رکورد شامل یک بردار۲۰ مقداری (دو جهتِ ۱۰ خیابان) مربوط به تعداد ماشینهای عبوری از این ۲۰ مسیر میباشد که بصورت فرمول ۴-۱ قابل نمایش است:
