پژوهش user6-713

یکشنبه 7 آبان 1396 ساعت 18:08
3-4- روش‌های مبتنی بر مدل‌های شبکه عصبی323-5- روش‌های مبتنی بر الگوریتم‌های دادهکاوی34فصل چهارم. معرفی تکنیک پیشنهادی4-1- مقدمه404-2- خصوصیات کلی پایگاه داده414-3- پایگاه دادهی مورد استفاده424-3-1- داده‌ی آموزشی444-3-2- داده‌ی آزمایشی444-4- تکنیک پیشنهادی454-4-1- بررسی توزیع جریان‌های ترافیکی474-4-2- مرحله پیش پردازش و استخراج […]

  

سایت دانلود پژوهش ها و منابع علمی

سایت دانلود پژوهش ها و منابع علمی دانشگاهی فنی تخصصی همه رشته ها – این سایت صرفا جهت کمک به گردآوری داده ها برای نگارش پژوهش های علمی و صرفه جویی در وقت پژوهشگران راه اندازی شده است

پژوهش user6-713

پژوهش user6-713

پژوهش user6-713

فهرست منابع و مآخذ78

فهرست جدول‌ها
عنوان صفحه
جدول شماره 4-1: شرح مفاهیم و معادل ترم‌های مورد استفاده 45
جدول شماره 5-1: مقایسه میانگین خطای الکوریتمهای مختلف weka64
جدول شماره 5-2: مقایسه خطای الگوریتم بگینگ و رندوم فارست66
فهرست شکل‌ها
عنوان صفحه
شکل 1-1: معماری کلی مربوط به متدهای یادگیری تجمعی6
شکل 2-1: معماری کلی الگوریتم بگینگ14
شکل 2-2: نمایی کلی از الگوریتم رندوم فارست16
شکل 2-3: معماری کلی مربوط به الگوریتم رندوم فارست20
شکل 4-1: صفحه‌ی نمایش شبیه ساز ترافیک TSF42
شکل 4-2: نقشه‌ی شهر Warsaw، اعمال شده بهTSF43
شکل 4-3: نمایش نمادین اعمال تکنیک پیشنهادی46
شکل 4-4: توزیع جریان‌های ترافیکی مسیرها47
شکل 4-5: ارائه‌ی دید دقیق‌تر در خصوص رفتار جریان‌های ترافیکی48
شکل 4-6: نمایش نمادین روند انجام مرحله گردآمدگی50
شکل 4-7: نمودار الزامات معیار شباهت مناسب53
شکل 4-8: جریانهای ترافیکی مسیرها مربوط به دو context 55
شکل 5-1: مثالی از چگونگی اعمال مراحل گردآمدگی68
شکل 5-2: مقایسهی خطا روشها با اعمال سایزهای مختلف گردآمدگی 69
شکل 5-3: مراحل نمادین استخراج مجموعه نمونه آموزشی71
شکل 5-4: مقایسه خطای تکنیک پیشنهادی و روش Ensemble RF72
فصل اول
مقدمهتعریف مسئلهامروزه، با توجه به گسترش روزافزون مطالبات حمل‌ونقل و بروز مشکلات ناشی از افزایش ترافیک شهری، ازجمله آلودگی هوا، آلودگی صوتی، مصرف سوخت، اتلاف وقت و انرژی و هزینه‌های تحمیلی آنها، ارائه راهکار مناسب درجهت روان شدن ترافیک از اهمیت ویژه‌ای برخوردار است. از طرفی باتوجه به محدودیت‌های امکانات شهرسازی در مقابل تقاضای انبوه وسایل نقلیه، لازم است تا تمهیداتی کاربردی و امکان‌پذیر برای حل این معضل درنظر گرفته ‌شود. ازآنجا که تاکنون فناوری اطلاعات نقش مؤثری درعرصه‌های مختلف صنعتی ایفا کرده است، ورود این تکنولوژی در زمینه‌ی سیستم‌های حمل‌ونقل نیز بعنوان راهکاری مناسب مورد توجه قرارگرفت و منجر به پدیدآمدن سیستم‌های حمل‌ونقل هوشمند شد. در واقع تکنولوژی فناوری اطلاعات به عناصر سیستم حمل‌ونقل این امکان را می‌دهد تا با بکارگیری حسگرها و میکروچیپ‌ها و ارتباط آنها از طریق تکنولوژی بیسیم، تبدیل به یک سیستم هوشمند شوند. امروزه سیستم حمل‌ونقل هوشمند با تشکیل سامانه‌ای متشکل از حسگرهای دریافت داده، سامانه‌های پردازش اطلاعات و سامانه‌های ارائه‌ی اطلاعات به استفاده کنندگان، گامی مؤثر در راستای مدیریت سیستم حمل‌ونقل و استفاده هوشمندانه از زیرساختارهای موجود، برداشته است [1]. بطور مثال این سیستم با بکارگیری فناوری‌های متفاوتی همچون هدایت خودرو و سیستم کنترل چراغ‌های راهنمایی، تابلوهای اعلان ترافیک، دوربین سرعت‌سنج و سیستم خودکار شناسایی شماره‌ی خودرو گرفته تا سیستم‌های پیشرفته و پیچیده‌تری که بطور همزمان اطلاعات متفاوتی مانند وضعیت آب و هوا، وضعیت ترافیک، وضعیت جاده‌ها را از منابع متفاوت یکپارچه میکند، کنترل این حوزه را بدست‌ گرفته‌ است. از جمله دستاوردهای مهم بکارگیری سیستم حمل‌ونقل هوشمند می‌توان به کاهش ترافیک، کاهش حوادث و تصادفات، امکان انتخاب مسیرهای بهینه با توجه به وضعیت مسیرها، مدیریت حمل‌ونقل عمومی و وسائل نقلیه‌ی امدادی و همچنین امکان اخذ الکترونیکی مواردی همچون عوارض، هزینه‌ی پارکینگ و خرید بلیط که منجر به صرفه جویی در سوخت وانرژی و کاهش هزینه‌های تحمیلی میشود، اشاره کرد. عموماً سیستم‌های حمل ونقل هوشمند را تحت عنوان پنج گروه اصلی بررسی میکنند که هرکدام حوزه‌های مختلف از این سامانه را شامل میشوند؛
الف) سامانه‌های پیشرفته‌ی اطلاعات مسافرتی(ATIS) که وظیفه‌ی آن فراهم آوردن اطلاعات وضعیت فعلی ترافیکی و جوّی جاده‌ها، تصادفات و تعمیرات جاده‌ای و همچنین اطلاع رسانی به مسافران و کاربران بمنظور استفاده‌ی بهینه از مسیرهای موجود و برقراری تعادل ترافیکی می‌باشد.
ب) سامانه‌های پیشرفته‌ی مدیریت ترافیک (ATMS)که اطلاعات ترافیکی جمعآوری شده از منابع مختلف را بررسی و یکپارچه کرده و از طریق ابزارهای کنترل ترافیک مانند سینگال‌های ترافیکی، کنترل رمپ ورودی بزرگراه ها به منظور حفظ تراکم و تابلوهای اطلاع رسانی متغیر موجود در جاده‌ها، کنترل جریان ترافیکی را در دست می‌گیرند.
ج) سامانه‌های پرداخت الکترونیکی (EPS) که شامل سیستم جمع‌آوری الکترونیکی عوارض(ETC)، سامانه‌های پرداخت عوارض بمنظور استفاده از خطوط ویژه‌ی وسایل نقلیه پرسرنشین توسط وسایل تک سرنشین و همچنین قیمت‌گذاری مسیر و خطوط پرترافیک می‌باشد.
د) سامانه‌های پیشرفته و هوشمند حمل‌ونقل همگانی (APTS)اموری در جهت تسهیل ارائه‌ی خدمات حمل‌ونقل عمومی همچون تعیین موقعیت خودکار وسیله نقلیه و اطلاع رسانی به مسافران، خدمات رزرو و تعیین کرایه را نیز شامل می‌شود.
ه) سامانه‌های پیشرفته‌ی کنترل وسائل نقلیه(AVCS) که شامل سامانهی انطباق هوشمند سرعت(ISA)، سامانه‌های هشدار و پیشگیری از تصادفات می‌شوند.
در حوزه‌یAITS وATMS، پیش‌بینی کوتاه مدت ترافیک از عناصر مهم موفقیت سیستم‌های حمل‌ونقل هوشمند محسوب می‌شود، چرا که در راستای کنترل ترافیک نه تنها وضعیت فعلی ترافیک بلکه وضعیت آینده‌ی ترافیک نیز حائز اهمیت است. از این رو الگوریتم‌های پیش‌بینی ترافیک مورد توجه ویژه‌ای در میان محققان این حوزه قرار گرفتند.
چالش‌های مسئلههمانطور که پیشتر بیان شد، مراکز کنترل ترافیک بر اساس جمعآوری آمار و اطلاعات ترافیکی، پردازش و یکپارچه سازی آنها، تصمیمات لازم جهت مدیریت و کنترل ترافیک را اتخاذ می‌کنند. در راستای بهبود کنترل ترافیک، ATIS و ATMS بعنوان اصلیترین اجزاء سیستم حملونقل هوشمند، علاوه بر وضعیت فعلی ترافیک، به وضعیت آینده ترافیک نیز احتیاج دارند. ازین‌رو پیشبینی وضعیت آینده ترافیک از جمله مباحث مهم برای این مراکز به حساب می‌آید تا با استفاده از آن استراتژی‌های لازم جهت جلوگیری از تراکم و هشدار به رانندگان جهت انتخاب مسیر بهینه، صورت گیرد. تاکنون تحقیقات متعددی در خصوص پیش‌بینی وضعیت ترافیکی آینده انجام شده است که در واقع با استفاده از داده‌های ثبت شده از وضعیت فعلی ترافیک، ترافیک مربوط به زمان‌های آتی را پیش‌بینی می‌کنند.
بطور معمول داده‌های جمع‌آوری شده در حوزه‌ی ترافیک، بصورت سری‌های زمانی در اختیار ما قرار می‌گیرند که در واقع شامل رکوردهای مختلفی هستند که در بازه های زمانی مساوی و در طی اندازه‌گیری‌های متوالی بدست می‌آیند. با استفاده از داده‌های فعلی و گذشته، مقادیر آن‌ها در آینده پیش‌بینی می‌شوند [2]. تاکنون تکنیک‌های متفاوتی در زمینه‌ی پیش‌بینی ترافیک بکار گرفته شده است که از جمله‌ی آن‌ها می‌توان به روش‌های کالمن فیلترینگ [4,3]، متدهای آماری غیرپارامتریک [5,6] ، روش‌های یادگیری متوالی[7] ، مدل‌های شبکه‌عصبی [8-11] و آنالیزهای سری‌های زمانی[13-17] اشاره کرد. از مهمترین چالش‌های اعمال این الگوریتم‌ها، حجم بالای داده‌های ترافیکی است که منجر شده تا اخیراً گرایش تحقیقات به سمت استفاده از الگوریتم‌های داده کاوی باشد.
همانطور که می‌دانیم تکنیک‌های داده کاوی قابلیت استخراج اطلاعات از داده‌هایی با حجم بسیار بالا همچون داده‌های ترافیکی را دارا هستند. از میان آن‌ها روش‌های مبتنی بر درختهای تصمیم‌گیری بطور گسترده‌ای در حوزه‌ی ترافیک مورد استفاده قرار گرفته است[18,19]. همچنین متدهای یادگیری تجمعی همانند بگینگ و بوستینگ با توجه به کارایی بالا، مورد توجه ویژه‌ای واقع شدند. ایده‌ی اصلی آن‌ها ساخت مجموعه‌ای از مدل‌ها و ترکیب نتایج آن‌ها با هدف بهبود دقت یادگیری می‌باشد[47]. در شکل -11 معماری کلی الگوریتم‌های یادگیری تجمعی را می‌بینیم که از کتاب [20] آورده شده است.

شکل 1-1. معماری کلی مربوط به متدهای یادگیری تجمعی. در این متدها، مجموعه‌ای از کلاسه‌بندها یا مدل‌های پیش‌بینی کننده M1, M2, …, Mk تولید می‌شوند و نهایتاً با ورود نمونه‌ی ناشناخته ، استراتژی‌های رأی‌گیری برای ترکیب پیش‌بینی‌های مختلف مدل‌ها استفاده می‌شوند.
رندوم فارست یکی از مشهورترین و کاراترین متدهای مبتنی بر یادگیری تجمعی در زمینه پیش‌بینی است که توسط Leo Brieman در سال 2001 ارائه شد. رندوم فارست در واقع حالتی عمومی از متدهای بگینگ به حساب می‌آید که از مجموعه‌ای از درخت‌هایCART غیر هرس شده، تشکیل شده است [21]. در حالت رگرسیون، جواب نهایی میانگین جواب‌های درختان و در حالت کلاسه بندی، کلاس نهایی با توجه به اکثریت آرا تعیین می‌شود. درخت‌های CART در واقع درخت‌های تصمیم‌گیری هستند که در آن‌ها هر گرهی والد تنها به دو بچه تقسیم می‌شود و همچنین از معیار Gini به منظور ارزیابی ویژگی ها استفاده می‌کند [20].
بطور خلاصه، اغلب روش‌های اعمال شده ، تنها بر روی اعمال الگوریتم‌های مختلف داده کاوی به مدل‌های یادگرفته شده از داده‌های پیشین هستند، حال آنکه با توجه به ماهیت ناپایداری و وابسته به زمان بودن جریان‌های ترافیکی، لازم است تا قبل از یادگیری این مدل‌ها، رفتار جریان‌های ترافیکی نیز بررسی شوند. در این راستا، آنالیزهای مختلف کلاسترینگ نیز با هدف ثبت رفتارها و روند تغیرات جریان‌های ترافیکی انجام شد تا جریان‌های با رفتارهای مشابه قبل از یادگیری، دسته بندی شوند[22, 23]. اکثریت این دسته‌بندی‌ها بر اساس زمان‌های پُرترافیک وکم‌ترافیک صورت می‌گیرد. همانطور که می‌دانیم در طی روزهای مختلف، رفتارهای ویژه‌ای در ساعات معینی از روز دنبال می‌کنند. بنابراین تفکیک و جداسازی و یادگیری مدل‌های متفاوت بر مبنای این رفتارها، نقش مؤثری در دقت الگوریتم‌های پیش‌بینی خواهد داشت. نکته‌ی حائز اهمیت در اینجا این‌است که اغلب روش‌هایی که رفتارهای جریان‌های ترافیکی را بررسی می‌کنند تنها بر روی داده‌های واقعی یا داده‌هایی که زمان رخدادشان مشخص است، قابل اعمالند. هرچند در برخی از داده‌های جمع‌آوری شده، زمان جمع‌آوری آنها مشخص نیست. بنابراین، با توجه به اهمیت موضوع، هدف این پایان‌نامه ارائه‌ی روشی مبتنی بر الگوریتم رندوم فارست است که بدون در اختیار داشتن زمان واقعی جمع آوری داده، توزیع داده را بررسی، رفتارهای ترافیکی را تشخیص و در مرحله یادگیری از آنها استفاده می‌کند.
نگاهی به فصول پایان نامهادامه‌ی مطالب عنوان شده در این پایان نامه در قالب چهار فصل و بصورت زیر سازماندهی شده‌اند؛ فصل دوم با عنوان مبانی نظری تحقیق، ضمن ارائه‌ی چهارچوب‌های نظری مورد استفاده، قالب ریاضی مسئله‌ی پیش‌بینی ترافیک را مورد مطالعه قرار می‌دهد و مفاهیم اولیه و متغیرهای مسئله را مطرح می‌کند. فصل سوم نیز با عنوان پیشینه تحقیقات، شامل خلاصه‌ای از نظریات و مطالعات پیشین انجام شده در حوزه‌ی این پایان نامه می‌باشد که در آن متدهایی که تاکنون کاربرد گسترده‌تری داشته‌اند، در قالب سه گروه تقسیم بندی و مطالعه می‌شوند.
فصل چهارم نیز تحت عنوان معرفی تکنیک پیشنهادی، مباحثی همچون آنالیز داده‌ی مورد استفاده، ارائه توصیف کلی از هدف اصلی متد و مراحل اعمال تکنیک ارائه شده را شامل می‌شود. در راستای مطالعه و بررسی عملکرد تکنیک پیشنهادی، آزمایش‌های متعددی صورت گرفته که در فصل پنجم با نام نتایج تجربی، تحلیل ها و نتایج حاصل از اعمال این تکنیک‌ها در مقایسه با دیگر روش‌ها مورد بررسی قرار خواهند گرفت.
در نهایت، نتیجه‌گیری و خلاصه‌ای از تحلیل‌های حاصل از انجام این مطالعات، در فصل ششم ارائه خواهد شد و علاوه بر آن گام‌هایی در راستای گسترش و ادامه این تحقیق در کارهای آینده، پیشنهاد می‌شوند.
فصل دوم
مبانی نظری تحقیقمقدمهپیش‌بینی دقیق وضعیت ترافیکی، امری لازم و تأثیرگذار در مدیریت مؤثر سیستم‌های حمل‌ونقل هوشمند به حساب می‌آید. از آنجا که داده‌های ترافیکی معمولاً داده‌هایی با حجم بالا هستند، تکنیک‌های کاربردی و جدیدی را برای پردازش نیاز دارند. داده کاوی بعنوان یک شاخه از علم کامپیوتر اخیراً توجه زیادی را به خود جلب کرده است که در نتیجه‌ی اعمال آن، آنالیز و پردازش پایگاه داده های بزرگ فراهم می‌شود. در واقع متدهای داده کاوی معمولاً با هدف استخراج دانش و ساخت مدل از داده‌های حجیم بکار گرفته می‌شوند[24]. از میان روش‌های گوناگون داده کاوی، تمرکز تعداد قابل توجهی از تحقیقات به روی یادگیری یادگیری تجمعی ، درخت‌های تصمیم‌گیری و بطور ویژه رندوم فارست می‌باشد که در ادامه توضیح داده خواهند شد[25].
متدهای یادگیری تجمعیدر سال‌های اخیر گرایش زیادی به سمت تکنیک‌های یادگیری تجمعی مشاهده می‌شود که ایده‌ی اصلی آن‌ها استفاده از ترکیبی از مدل‌ها به جای استفاده از یک مدل است. در واقع این متدها با هدف بهبود کارایی مدل نهایی M، مجموعه‌ای از K مدل (کلاسه‌بند یا پیش‌بینی‌کننده) شامل را ترکیب می‌کنند[20].
تعاریف مفاهیم اولیه
کلاسه بند: فرآیند پیدا کردن یک مدل (یا یک تابع) که قابلیت توصیف داده‌ای که توسط آن آموزش دیده را دارد، می‌باشد. در نهایت از این مدل می‌توان برای پیش‌بینی کلاس مربوط به نمونه‌هایی که برچسب کلاس آنها مشخص نیست، استفاده کرد. مدل بدست آمده می‌تواند با فرم‌های متفاوتی از جمله قوانین کلاسه بندی (IF-THEN) ، درخت های تصمیم‌گیری، فرمول‌های ریاضی، شبکه های عصبی و ... ارائه شود [20].
درخت تصمیم‌گیری: در واقع یک ساختار درختی شبه فلوچارت می‌باشد که هر گرهی تصمیم، نمایانگر یک تصمیم‌گیری روی مقادیر یک ویژگی است و هر شاخه بیانگر نتیجه آن تصمیم‌گیری است. همچنین برگهای یک درخت، برچسب کلاس‌ها یا توزیع‌های کلاسی را نشان می‌دهند .[20]
شبکه عصبی مصنوعی: یک مدل ریاضی الهام گرفته از شبکه عصبی انسان است که از گروه‌هایی از نِرون‌های مصنوعی تشکیل شده است. اساس محاسبات در این روش بر مبنای اتصال بهم پیوسته چندین واحد پردازشی می‌باشد و می‌تواند ساختار خود را در طی مرحله یادگیری تغییر دهد که این موضوع را با تنظیم وزن اتصال‌ها انجام می‌دهد [26].
پیش‌بینی کننده: بر خلاف کلاسه‌بند که برچسب‌های گسسته را پیش‌بینی می‌کند، پیش‌بینی‌کننده، توابع با مقادیر پیوسته را مدل می‌کند، یعنی به جای برچسب کلاس، مقادیر عددی را پیش‌بینی می‌کند. هرچند بطور عمومی اصطلاح پیش‌بینی‌کننده هم برای پیشبینی برچسب‌های گسسته و هم برچسب‌های پیوسته بکار می‌رود، اما در کتاب های مختلف از جمله کتاب [20]، این واژه مختص پیشبینی ‌مقادیر عددی است.
آنالیز رگرسیون نیز یک متدولوژی آماری است که غالباَ برای پیشبینی مقادیر عددی استفاده می‌شود. در طول این پایان نامه نیز، اصطلاح رگرسیون معادل پیشبینی کننده عددی استفاده شده است. در واقع از آنجا که داده‌های در اختیار گذاشته شده در این پایان نامه، داده‌های ترافیکی و به بیانی دقیق‌تر تعداد وسایل نقلیه عبوری از خیابان‌هاست، هدف اصلی در این‌جا نیز اعمال روشی بهینه مبتنی بر رگرسیون می‌باشد.
دو دسته از مهم ترین و شناخته شده ترین متدها در زمینه‌ی یادگیری تجمعی ، درخت‌های بوستینگ ارائه شده توسط [27] و درخت بگینگ توسط [28] می باشد که در ادامه به توضیح آن‌ها می‌پردازیم.
درخت بوستینگدر این روش نیز مدل نهایی از مجموعهای از مدل‌ها تشکیل شده است که در آن مدل‌های پایهای مبتنی بر درخت‌های تصمیم‌گیری هستند. در طی اعمال این الگوریتم، درخت‌ها به نمونه‌هایی که توسط درخت‌های قبلی نادرست پیشبینی شده اند، وزن بیشتری می‌دهند. در نهایت مدل نهایی بر مبنای رأی‌گیری وزن‌دار بین درخت‌ها انجام می‌گیرد که این وزن‌ها بر اساس میزان دقت درخت‌ها تنظیم می‌شوند [27].
درخت بگینگ درخت بگینگ مخفف Bootstrap AggregatlNG (Bagging) می باشد که در این قسمت توضیح داده شده است. الگوریتم بگینگ از مجموعهای از مدل‌های پایه‌ای تشکیل شده و به ترتیب زیر عمل می‌کند. با دریافت مجموعه‌ی آموزشی D با سایز N (تعداد نمونه های داده آموزشی)، به تعداد K مجموعه آموزشی جدید Di، با سایز n<N، تولید می‌شود که حاصل سمپل‌گیری یکنواخت و با جایگزینی از مجموعه اولیه D می‌باشد. همان‌طور که می‌دانیم این نوع سمپل‌گیری بعنوان Bootstrap sample شناخته می‌شود. K مدل مختلف با استفاده از K زیر مجموعه، آموزش داده می‌شوند و در نهایت یک مدل نهایی را تشکیل می‌دهند. این مدل نهایی در رگرسیون از میانگین‌گیری نتایج مدل‌ها و در کلاسه‌بندی از رأی‌گیری بین مدل‌ها حاصل می‌شود [29]. درخت بگینگ در واقع همان الگوریتم بگینگ است که مدل‌های پایه‌ای آن مبتنی بر درخت‌های تصمیم‌گیری هستند. همانطور که مشخص است، بر خلاف بوستینگ در بحث بگینگ، مدل‌های پایه مستقل از هم ساخته می‌شوند و به دقت مدل‌های قبلی وابسته نیستند. در شکل 2-1 الگوریتم مربوط به بگینگ را میبینیم.
Algorithm: Bagging
Input :
Sequence of N examples D <( x1 ,y1 ),….., ( xN, yN )> with labels y i€ Y={ 1,…,L }
Distribution D over the N example
Integer K specifying number of iterations
Weak Learning algorithm WeakLearn (tree)
Do k=1,2,.., K
Choose bootstrapped sample Di (n sample) by randomly from D.
Call WeakLearn k with Di and receive the hypothesis (tree) ht.
Add ht to the ensemble.
End
Test: Simple Majority Voting – Given unlabeled instance x
Evaluate the ensemble {h1,….,hk} on x
Choose the class that receives the highest total vote as the final classification.
شکل 2-1. معماری کلی الگوریتم بگینگ. با دریافت مجموعه‌ی آموزشی D با سایز N ، به تعداد K مجموعه آموزشی جدید Di، با سایز n<N، تولید می‌شود)بعنوان Bootstrap sample ). K مدل مختلف با استفاده از K زیر مجموعه، آموزش داده می‌شوند و در نهایت کلاسی که تعداد بیشتری از مدلها به آن رای دادهاند، انتخاب میشود.
از جمله عوامل تأثیرگذار در موفقیّت متدهای یادگیری تجمعی، بحث تنوع مدل‌های پایه و همچنین دقت هرکدام از مدل‌هاست. همانطور که واضح است اگر مدل‌های پایه متنوع یا به اصطلاح diverse نباشند، ترکیب آن‌ها بی فایده است. در متد بگینگ، استفاده از مجموعه‌های متفاوت از مجموعه داده اولیه، شرط تنوع را تضمین می‌کند. از طرف دیگر، زمانی یک مدل می‌تواند از تغییرات مجموعه داده آموزشی خود استفاده کند که ناپایدار باشد . ناپایدار بودن به این معناست که تغییرات کوچک در ورودی (مجموعهی آموزشی) منجر به تغییرات بزرگ در خروجی مدل شود. از جمله پیشبینی کننده‌های ناپایدار می‌توان به شبکه‌های عصبی مصنوعی و درختان تصمیم‌گیری اشاره کرد. هرچند مدل نزدیکترین همسایگی جزء کلاسه بندهای پایدار به حساب می‌آید [29].
با توجه به مباحث مطرح شده، می‌توان نتیجه‌گیری کرد که استفاده از درخت تصمیم‌گیری بعنوان مدل‌های پایه‌ای متدهای یادگیری تجمعی کارایی مؤثری دارد و برهمین اساس تحقیقات زیادی انجام و منجر به تولید الگوریتم‌های بسیار قدرتمندی نظیر رندوم فارست شد. در ادامه نیز به بررسی دو نوع متد مبتنی بر بگینگ خواهیم پرداخت.
از جمله انواع الگوریتم‌هایی که روند بگینگ را دنبال می‌کنند، می‌توان به دو نوع (1) pasting small votes و(2) رندوم فارست اشاره کرد.
pasting small votes: که طراحی آن در راستای استفاده بر روی پایگاه داده‌های بزرگ بوده است. در این الگوریتم، یک مجموعه داده به زیرمجموعه کوچکتر به نام بیت تقسیم شده و روی هرکدام یک کلاسهبند متفاوت آموزش داده می‌شود. اگر انتخاب این مجموعه داده‌ها بر اساس رندوم باشد Rvotes (مشابه بگینگ) نامیده شده و اگر بر اساس اهمیت آن بخش باشد، با نام Ivotes (مشابه بوستینگ) شناخته می‌شوند[29].
رندوم فارست: نوع دیگر روش بگینگ الگوریتم رندوم فارست است که به دلیل گستردگی استفاده از آن در این پایان‌نامه، مفاهیم آن بطور مفصل در بطور مجزا در بخش بعدی توضیح داده شده است.
رندوم فارستدر سال 2001، Breiman الگوریتم رندوم فارست را ارائه داد که یک حالت عمومی‌تر از بگینگ به حساب می‌آید و در واقع یک لایه رندوم به بگینگ اضافه می‌کند. در این الگوریتم علاوه بر اینکه هر درخت با استفاده از سمپل‌های متفاوتی از داده‌ها ساخته می‌شود، روند ساخت درخت‌ها نیز تغییر می‌کند. در واقع در یک درخت استاندارد، هر گره تصمیم با استفاده از بهترین نقطه شکست انتخاب از میان همه خصیصه‌ها شکسته می‌شود، اما در رندوم فارست، هر گره تصمیم بر مبنای بهترین نقطه شکست از میان زیرمجموعه‌ای از خصیصه‌هایی که بطور رندوم در سطح آن گره انتخاب شده اند، شکسته می‌شود [30]. معماری کلی مربوط به رندوم فارست برگرفته از [31]در شکل1-2 آمده است.

شکل 2-2. نمایی کلی از الگوریتم رندوم فارست که یک متد یادگیری تجمعی برای کلاسه‌بندی و رگرسیون است. مدل‌های پایه، درختان تصمیم‌گیری CART هستند و خروجی نهایی K، بر اساس رای‌گیری خروجی‌های B عدد درخت تعیین می‌شود. در مورد کلاسه‌بندی، رای نهایی بر مبنای مُد خروجی‌ها و در مورد رگرسیون بر اساس میانگین‌گیری تعیین می‌شود.
بکارگیری این استراتژی باعث عملکرد مناسب و کارا در مقایسه با دیگر الگوریتم‌ها همچون آنالیزهای جداسازی، بردارهای پشتیبان کننده و شبکه‌های عصبی مصنوعی می‌شود. همچنین این تکنیک فقط به تنظیم دو پارامتر (1) تعداد متغیرهای قرار گرفته در زیرمجموعه‌ی رندوم انتخاب شده و (2) تعداد درختان مورد استفاده، نیاز دارد و علاوه بر آن، حساسیت شدیدی نسبت به مقادیر این پارامترها ندارد.
مراحل توسعه‌ی رندوم فارستبطور کلی الگوریتم رندوم فارست یک مجموعه از درخت‌های شبه CART است . مروری کلی بر این الگوریتم را تحت 4 مبحث 1) مرحله رشد درختان، 2) مرحله ترکیب درختان، 3) مرحله خودآزماییو 4) مرحله پس پردازش بررسی می‌کنیم که این مباحث از [32] آمده است.
مرحله رشد درختان:
درختان موجود در رندوم فارست، شاخه‌های دوتایی دارند، یعنی هر والد، تنها به دو فرزند تقسیم می‌شود. رندوم بودن در دو مرحله به هرکدام از این درختان تزریق می‌شود، (1) در توسعه هر درخت روی نمونه‌های رندوم انتخاب شده از داده آموزشی و (2) در مرحله انتخاب بهترین نقطه شکست از میان متغیرهایی که بطور رندوم از میان همه متغیرها انتخاب شده‌اند. اگر m، تعداد کل خصیصه‌ها باشد، مقادیری که Breiman برای تعداد متغیرهای انتخابی R پیشنهاد داد، به ترتیب در فرمول‌های (2-1)، (2-2) و (2-3) بدین ترتیب بود:
(2-1)
(2-2)

(2-3)

انتخاب زیرمجموعه‌ای از خصیصه‌ها و توسعه‌ی درختان براساس آن‌ها منجر به افزایش سرعت رشد درختان و همچنین عدم نیاز به اعمال الگوریتم‌های انتخاب خصیصه می‌شود.
انتخاب نقطه شکست در رندوم فارست:
هرچند انتخاب بهترین نقطه شکست از زیرمجموعه رندوم، ممکن است لزوماً بهترین نتیجه را در بر نداشته باشد، اما تکرار این انتخاب‌ها در مورد هرگره، تصمیم‌گیری متفاوتی را در طی ساخت درخت فراهم می‌کند و نهایتاً متغیرهای مهم نیز در ساخت درخت دخیل خواهند شد. این موضوع دلیلی است در راستای تأکید بر استفاده از درخت‌های با سایز کامل، که هَرَس نشده باشند. نتایج تحقیقات نیز نشان داده‌اند که هَرس کردن این درختان منجر به کاهش کارآیی الگوریتم می‌شود.
مرحله خودآزمایی در رندوم فارست:
در طی اعمال الگوریتم رندوم فارست با توجه به مرحله نمونه برداری bootstrap، هر درخت تقریبا بر روی 63% از داده‌ها، رشد پیدا می‌کند. بنابراین 37% از داده‌ها، در مورد هر درخت استفاده نمی‌شود که به این داده‌ها “Out Of Bag” یا به اختصار OOB می‌گویند. از داده‌های OOB که در مورد هر درخت داده‌های مجزایی هستند ، می‌توان برای ارزیابی درختان توسعه یافته استفاده کرد. در واقع با استفاده از این مجموعه داده‌های OOB، الگوریتم رندوم فارست می‌تواند آمارهایی مربوط به کارآیی الگوریتم خود ارائه دهد. همچنین مسئله RF Self-testing، شبیه مسئله وارسی اعتبار می‌باشد که هر بار روی قسمت بندی‌های متفاوتی از داده اولیه محاسبه می‌شوند. بنابراین با استفاده از این قابلیت رندوم فارست، حتی اگر کل داده آموزشی بعنوان ورودی الگوریتم استفاده شود، امکان Self-testing در طی یادگیری فراهم است. علاوه برآن، این قابلیت در مورد داده‌های کوچک حائز اهمیت زیادی است، چرا که نیازی به کنار گذاشتن قسمتی از داده برای تست، لازم نیست. بنابراین از جمله الگوریتم‌های پرکاربرد در خصوص اعمال بر روی داده‌های کم سایز محسوب می‌شود. از دیگر نتایج وجود داده‌هایOOB در هنگام ساخت درخت، مقاومت در برابر مسئله بیش برازش و عمومیت‌بخشی در برابر داده‌های جدید، می‌باشد. همچنین با انتخاب زیرمجموعهای از خصیصه‌ها، نیازی به اعمال الگوریتم‌های انتخاب ویژگی نیز نخواهد بود[21].
مرحله پس پردازش در رندوم فارست:
در واقع پس از ساخت درختان، با دقت در آنها، دید بهتری در مورد داده می‌توان بدست آورد. با در نظر گرفتن هر رکورد، می‌توان تعداد دفعاتی که هر دو رکورد در برگ‌های یکسان درختان قرار گرفته‌اند، را محاسبه کرد و میزان شباهت آن‌ها را بدست آورد. معیار فاصله بدست آمده از این طریق می‌تواند برای ساخت ماتریس عدم شباهت نیز استفاده شود که بعنوان ورودی الگوریتم‌های خوشه یابی سلسله مراتبی بسیار پرکاربردند. همچنین با حرکت روی مسیر درختان، عملاً مکانیزم الگوریتم نزدیکترین همسایگی انجام می‌شود. در نظر بگیرید که برای رسیدن به یک گره در درخت، یک رکورد باید تمام شرایط در همه والدها را ارضا کند، بنابراین رسیدن دو رکورد به یک گره نشان دهنده شباهت آن‌هاست. پس همانند تکنیک نزدیکترین همسایگی که با توجه به شبیه‌ترین همسایه‌ها، بر چسب آن داده جدید را پیشبینی می‌کند، درختان موجود در رندوم فارست نیز همانند این روند را می‌توانند دنبال کنند.
مرحله ترکیب درختان در رندوم فارست:
از آنجا که در متدهای یادگیری تجمعی نهایتاً یک مدل نهایی ارائه می‌شود، پس در اینجا نیز درخت‌های آموزش دیده، باید ترکیب شوند. همانطور که پیشتر بیان شد، در مورد مسائل کلاسه بندی، بین نتایج مدل‌ها رأی‌گیری و در مورد مسائل رگرسیون از نتایج مدل‌ها میانگین‌گیری می‌شود. همچنین ترکیب مدل‌ها می‌تواند بر اساس نوعی وزن‌دهی صورت گیرد، یعنی همه مدل‌ها به یک اندازه در مدل نهایی مشارکت نداشته باشند. از جمله تلاش‌هایی که در این زمینه صورت گرفته می‌توان به موارد [33] و [34] اشاره کرد. در اکثریت این تحقیقات، وزن‌دهی و میزان مشارکت یک مدل، بر اساس دقت آن تعیین می‌شود.
تئوری‌های مرتبط با رندوم فارستدر این بخش به بیان تعاریف ریاضی موجود از رندوم فارست می‌پردازیم که در مقاله اصلی [21] در مورد رندوم فارست آمده است. همچنین تئوری‌های مرتبط با این الگوریتم همچون مسئله همگرایی، دقت و خطای عمومی آن را بررسی می‌کنیم. علاوه بر آن به معرفی مجموعه OOB پرداخته و چگونگی کاربرد آن را برای محاسبه قدرت، وابستگی و مشاهده خطا در روند ساخت الگوریتم توضیح می‌دهیم. همچنین، از آنجا که تمرکز اصلی این پایان نامه با توجه به داده‌های ترافیکی، انجام رگرسیون است، بنابراین مسئله رگرسیون رندوم فارست را نیز بررسی کرده و در انتها، مزایا و کاربردهای الگوریتم رندوم فارست را توضیح می‌دهیم.
تعریف ریاضی رندوم فارست: “یک رندوم فارست یک کلاسه بند است که از مجموعه ای (k عدد) از کلاسه بندی‌های با ساختار درختی تشکیل شدهکه بردارهای رندوم مستقل و یکنواخت توزیع شده هستند و هرکدام از درخت‌ها یک رأی واحد را برای مشهورترین کلاس با ورودی x تعیین می‌کنند" [21].
"بعبارتی برای kاُمین درخت یک بردار رندوم تولید شده که مستقل از بردارهای رندوم قبلی یعنی است، اما توزیع یکسانی دارد و هر درخت با استفاده از مجموعه آموزشی و رشد پیدا می‌کند. نهایتاً هر درخت، یک کلاسه بند را نتیجه خواهد داد که X یک بردار ورودی است"[21]. الگوریتم رندوم فارست بصورت شبه کُد در شکل 2-3 (برگرفته از [32]) آورده شده است.
Algorithm Random Forest (k)
Input : Sequence of N examples <( x1 ,y1 ),….., ( xN, yN )> with labels
y i€ Y={ 1,…,L }
Distribution D over the N example
Integer K specifying number of iterations
p = # of variables
Do For t=1,2,.., K(# trees)
Choose bootstrap sample Di from D to construct tree Ti
Select m input variables at random from p
(m<<p)
To determine the decision tree at a node of the tree
Calculate the best split based on these m variables in the training set
End
Choose the class that receives the highest total vote as the final classification.
شکل 2-3. معماری کلی مربوط به الگوریتم رندوم فارست. در طی رشدK عدد درخت، توسعه‌ی هر درخت روی نمونه‌های رندوم انتخاب شده Di صورت گرفته و از میان p خصیصه‌ی نمونه‌ها، m خصیصه بطور رندوم انتخاب می‌شوند.
در قسمت بعدی نیز، در راستای توصیف دقت رندوم فارست ، نگاهی کلی به مسائل همگرایی رندوم فارست و خطای عمومی این الگوریتم که توسط Breiman بیان شده‌اند، خواهیم داشت[21].
همگرایی رندوم فارست: با در اختیار داشتن کلاسه‌بندهای و با مجموعه آموزشی رندوم انتخاب شده از توزیع بردار رندوم x,y تابع margin را بصورت زیر تعریف می‌شود:
(2-4)

که در آن I(0) تابع نشانگر است. بطور مفهومی، فرمول margin محاسبه می‌کند که میانگین رأی‌های درست به چه میزان از رأی‌های اشتباه یعنی j≠y فاصله دارد. به بیانی دقیق‌تر، هر چقدر میزان margin بیشتر باشد، میزان اطمینان در کلاسه بندی بیشتر است. [21]
خطای عمومی رندوم فارست: همچنین با افزایش تعداد درختان، این الگوریتم از قانون Strong Law of large Numbers و ساختار درختی تبعیت می‌کند که تئوری آن بشرح زیر است:
تئوری 2-1: با افزایش تعداد درختان، بطور قطع برای غالب دنباله‌های خطای عمومی (PE*) همگراست به:
(2-5)
که در آن،
(2-6)
و
(2-7)
این نتیجه در واقع نشان دهنده‌ی دلیل بیش برازش نشدن الگوریتم رندوم فارست (حتی با در برداشتن درختان زیاد) به حساب می‌آید. در واقع این رابطه نشان می‌دهد که خطای عمومی مقداری محدود و کوچکتر از صفر است و همین مسئله باعث بیش برازش نشدن الگوریتم می‌شود.
استفاده از OOB برای مشاهده خطا، قدرت و وابستگی: همانطور که پیش‌تر توضیح دادیم، برای ساخت هر درخت، یک مجموعه داده‌ی آموزشی جدید از مجموعه داده‌ی اصلی انتخاب شده و با انتخاب رندوم ویژگی‌ها، یک درخت ساخته می‌شود. بدین ترتیب، استفاده از بگینگ می‌تواند در راستای پیشبینی خطای عمومی (PE*) ترکیب درخت‌ها و همچنین قدرت و وابستگی آن‌ها بکار گرفته شود. فرض کنید با داشتن مجموعه آموزشی T، یک مجموعه bootstrap ، Tk داریم که کلاسه‌بندهای روی آن ساخته شده‌اند. برای هر x,y موجود در داده آموزشی، فقط رأی‌های کلاسه بندهایی استفاده می‌شود که در آن TK شامل y نشده باشند. به این کلاسه بندها، کلاسه بند OOB گفته می‌شود. پیشبینی OOB برای خطای عمومی نیز نسبت خطای کلاسه بند OOB روی مجموعه آموزشی است. در واقع در هر مجموعه آموزشی Bootstrap، تقریبا 3/1 نمونه‌ها کنار گذاشته می‌شوند. بنابراین، خطای OOB بر مبنای ترکیب 3/1 از کلاسه بندها در ترکیب نهایی، محاسبه می‌شود. از آنجا که نسبت خطا با افزایش کلاسه بندها، کاهش می‌یابد، بنابراین خطای OOB خطای فعلی را Overestimate می‌کند. برای رسیدن به خطای OOB بدون سوگیری، باید در نقطه قبل از همگرایی خطای تست، آن را اجرا کرد. هرچند بر خلاف وارسی اعتبار، خطای OOB، بدون سوگیری است.
رندوم فارست برای رگرسیون
در انتها با توجه به استفاده از رگرسیون رندوم فارست در این پایان نامه، به بیان مختصری از مباحث کلی آن می‌پردازیم. همانند قبل، رگرسیون رندوم فارست از درختان مبتنی بر بردار رندوم Ө شکل می‌گیرد که درخت پیشبینی کننده، به جای برچسب کلاس‌ها، روی مقادیر عددی اعمال می‌شوند. در انتها مدل نهایی بر اساس میانگین گیری روی k عدد درخت بدست می‌آید. در مورد محاسبه خطای عمومی رگرسیون رندوم فارست می‌توان به تئوری زیر اشاره کرد [21].
تئوری 2-2 : با افزایش تعداد درختان، خطای عمومی در مورد رگرسیون نیز تحت تئوری زیر بیان شده است:
(2-8)
که میانگین مجذور خطای عمومی برای هر پیشبینی کننده عددیh(x) بصورت زیر محاسبه می‌شود.
(2-9)
مزایا و کاربردهای رندوم فارست مباحث مطرح شده در این بخش و دیگر تحقیقات می‌توان نتیجه گرفت که الگوریتم رندوم فارست از جمله تکنیک‌های قوی در زمینه‌ی کلاسه‌بندی و رگرسیون به شمار می‌آید. از دیگر فواید حاصل از بکارگیری این الگوریتم می‌توان به موارد زیر نیز اشاره کرد:
امکان مشاهده داده در مورد داده‌های با بُعد بالا
تشخیص ناهنجاری، دورافتادگی و خطا
امکان آنالیز مجموعه داده‌های با سایز کوچک (بدلیل امکان انجام محاسبات OOB)
تشخیص ویژگی‌های با اهمیت تر
حل مسئله مقادیر از دست رفته
ارائه متد جدید چرخشی کلاسترینگ با استفاده از معیارهای سنجش فاصله بین رکوردها، مبتنی بر درخت‌ها
آموزش سریع در مورد داده‌های با سایز بالا به دلیل عدم نیاز به مسئله‌ی انتخاب ویژگی
مقاوم بودن در مورد مسئله بیش برازشی و عمومیت به داده‌های جدید
سهولت استفاده به دلیل نیاز محدود به تنظیم پارامترها
و نهایتاً ارائه مدل با کارآیی و دقت بسیار بالا
نتیجه گیریهمان طور نشان داده شد، الگوریتم رندوم فارست یک ابزار قدرتمند در خصوص مسئله پیش‌بینی به حساب می‌آید. نتایجی که در دیگر تحقیقات بر روی مجموعه‌های داده‌های مختلف انجام شده نیز بیانگر کارایی قابل مقایسه‌ی این الگوریتم با دیگر تکنیک‌های قوی در این زمینه از جمله بوستینگ و دیگر انواع بگینگ، می‌باشد. همچنین در فصل پیشینه‌ی تحقیق خواهیم دید که در تحقیقات اخیر و در حوزه‌های مختلف، گرایش قابل توجهی به سمت استفاده از این الگوریتم می‌باشد. در این پایان نامه نیز به بررسی کارآیی و استفاده از الگوریتم رندوم فارست در خصوص داده‌های ترافیکی پرداخته‌ایم.
فصل سوم
پیشینه‌ی تحقیقمقدمهدر این فصل، ابتدا به بیان تعریف مسئله‌ی پیش‌بینی کوتاه مدت ترافیک یا به عبارتی پیش‌بینی سری‌های زمانی می‌پردازیم. در واقع از آنجا که داده‌های ترافیکی معمولاً در غالب بازه‌های زمانی یکسان جمع آوری می‌شوند، عموماً بعنوان سری‌های زمانی در نظر گرفته می‌شوند. پس از ارائه‌ی مفاهیم و نشانه گذاری‌ها، مطالعه‌ی روش‌های مرسوم برای حل این مسئله را در سه گروه و تحت سه بخش بعدی بررسی میکنیم. از میان این متدها، با توجه به پرکاربرد بودن روش‌های مبتنی بر مدل‌های شبکه عصبی مصنوعی و همچنین روش‌های مبتنی بر آنالیزهای سری‌های زمانی، ابتدا به بررسی پیشینه‌ی مطالعات انجام شده در این دو گروه می‌پردازیم. در انتها نیز به مطالعه‌ی روش‌های مبتنی بر متدهای دادهکاوی پرداخته می‌شود که گرایش قابل ملاحظه‌ای از تحقیقات اخیر به سمت استفاده از آن‌ها می‌باشد.
تعریف مسئلههمانطور که پیشتر بیان شد، مسئله‌ی پیشبینی ترافیک از جمله نیازهای اساسی مراکز کنترل ترافیک در راستای ایجاد تعادل ترافیکی می‌باشد. غالباً این مسئله می‌تواند به دو گروه کلی پیشبینی طولانی‌مدت و کوتاه‌مدت تقسیم‌بندی شود. در مقابل الگوریتم‌های پیشبینی طولانی‌مدت که تخمین ترافیک در زمان‌های آینده دور را شامل می‌شوند، الگوریتم‌های پیشبینی کوتاه‌مدت، به روی تخمین ترافیک در چند دقیقه تا ساعات آینده متمرکز می‌شوند که در این پایان‌نامه نیز بتمرکز اصلی بر روی بررسی این نوع الگوریتم‌ها می‌باشد.
از طرف دیگر، داده‌های جمع آوری شده از وضعیت ترافیکی، داده حجیمی هستند که غالباً در بازه‌های زمانی یکسانی ثبت شده‌اند، از این‌رو، این داده‌ها معمولاً بصورت سری‌های زمانی در نظر گرفته می‌شوند. در واقع، داده‌های سری زمانی شامل دنباله‌هایی از مقادیرند که در طی اندازه‌گیری های متناوب در زمان‌های مختلف بدست آمده اند. معمولاً این مقادیر در بازه‌های زمانی مساوی (ساعتی، روزانه، هفتگی و...) ثبت شده‌اند. از این رو می‌توان آن‌ها را در غالب بردارهای وابسته به زمان در نظر گرفت و بصورت زیر نمایش داد.
(3-1)
که در این نمایشt یک مقدار حقیقی و x(t) یک سیگنال پیوسته هست. برای بدست آوردن یک سری باید در زمان‌های گسسته از سیگنال نمونه گرفت. اگر بازه ی نمونه‌گیری، در نمونه‌گیری یکنواخت، باشد، خواهیم داشت:
(3-2)
از جمله پردازش‌های ممکن روی سری‌های زمانی، علاوه بر دسته‌بندی، توصیف و تبدیل پیشبینی مقادیر آینده x[t] است. به منظور پیش‌بینی آینده با برگشت به عقب از زمان t، سری زمانی را خواهیم‌داشت که می‌خواهیم x را در زمانهای آینده تخمین بزنیم:
(3-3)
در این نشانه‌گذاری به s، افق پیشبینی می‌گویند. اگر بخواهیم فقط یک نمونه زمانی در آینده را پیش‌بینی کنیم s را برابر 1 در نظر می‌گیریم. در واقع این مبحث، یک مسئله تقریب تابع هست که برای حل آن باید ابتدا یک مدل در نظرگرفته وآن را روی همه مقادیرگذاشته x[ti] آموزش دهیم و سپس مدل را برای پیش‌بینی x[t+s] اجرا کنیم. به عبارتی می‌توان پیش‌بینی را به دید یک نگاشت یا تابع در نظرگرفت که x ورودی و y خروجی (یک مقدار پیوسته یا با ترتیب) می‌باشد که قرار است این تابع و رابطه x و y را یاد بگیریم.
از میان روش‌های متعدد گسترش یافته در این حوزه مانند روش‌های کالمن فیلترینگ [4]، [3]، متدهای آماری غیرپارامتریک [5]، [6]، روش‌های یادگیری متوالی [7] مدل‌های شبکه‌عصبی [8-12] و آنالیزهای سری‌های زمانی[13-17] از پرکاربردترین متدهای مورد استفاده به حساب می‌آیند. در نگاهی کلی، (1) روش‌های آنالیز سری‌های زمانی بر روی ویژگی‌های سری زمانی بودن داده‌ها، تکیه دارند و غالبا برای این فرض استوارند که داده‌های ثبت شده در طی زمان‌های مختلف نسبت به هم همبستگی دارند. (2) الگوریتم‌های شبکه عصبی مصنوعی نیز متدهای یادگیری باناظر هستند که با بکارگیری مدل‌های مختلف همچون RBF، TDNN،... و تنظیم انواع پارامترها شامل تعداد لایه‌ها و نرون‌ها، سعی در حل مسئله پیش‌بینی ترافیک دارد. علاوه بر این، نظر به گرایش قابل ملاحظه‌ای از تحقیقات اخیر به سمت (3) روش‌های داده کاوی، در قسمت بعدی به بررسی آن‌ها می‌پردازیم. در واقع تکنیک های داده کاوی قابلیت استخراج اطلاعات از پایگاه داده‌های بزرگ همچون داده‌های ترافیکی را دارند. در ادامه به توضیح و بررسی هرکدام از این روش‌ها می‌پردازیم.
روش‌های مبتنی بر آنالیزهای سری زمانی:نظر به ارائه‌ی داده‌های ترافیکی در غالب داده‌های سری زمانی، آنالیزهای سری زمانی بطور گسترده‌ای مورد استفاده‌ی این حوزه قرار گرفتند. در واقع آنالیزهای سری زمانی در جهت استخراج آمارهای معنادار و دیگر خصوصیات از داده سری زمانی مورد استفاده قرار می‌گیرند. همچنین فرض اصلی آنالیزهای سری زمانی، به همبستگی داده‌های جمع آوری شده در طول زمان، استوار است .[22] این موضوع از دهه 90 در مبحث پیشبینی کوتاه مدت ترافیک اهمیت زیادی پیدا کرده است. بسیاری از روش‌های عضو این دسته، مبتنی بر مدل معروف" میانگین متحرک خودگردان یکپارچه (ARIMA) هستند که با توجه به پرکاربرد بودن آن در بسیاری از تحقیقات همچون [13] ، [14]، [15] ،[17] در ابتدا مروری بر مفاهیم آن خواهیم داشت.
مدل‌های ARIMA در سری‌های زمانی برای توصیف مدل یا پیشبینی وضعیت آینده به کار گرفته می‌شوند. این مدل سه پارامتر مهم q,d,p دارند که به ترتیب درجه خودگردانی، یکپارچگی و میانگین متحرک هستند. صفر بودن هرکدام از این پارامترها، نشان دهنده‌ی مدل‌های Auto-Regression(AR) که همان ARIMA(1,0,0)، مدل‌های Integrated(I) یا ARIMA(0,1,0) و مدل‌های Moving Average(MA) که برابر با ARIMA(0,0,1) می‌باشد. بطور کلی، مدل‌های ARIMA در مواردی که داده‌ی مورد بررسی غیر ایستا داشته باشند و روند آن‌ها قابل تشخیص باشد، بکار گرفته می‌شوند. اگر xt سری زمانی داده شده باشد که t یک عدد صحیح شاخص و xt عدد حقیقی باشد، پیشبینی با ARIMA را می‌توان ترکیبی از مدل‌های wide-sense stationary بصورت زیر در نظر گرفت:
(3-4) ( 1- i=1pαi Li ) Xt = ( 1+ i=1qӨi Li) εt
که در آن پارامتر L عملگر تأخیر و αi مربوط به بخش خودگران مدل و پارامتر قسمت میانگین متحرک هستند. همچنین tε نمایانگر خطای مدل می‌باشد و در حالت ایستا بصورت:
(3-5)
در نظر گرفت. بدین ترتیب می‌توان از تکنیک‌های استاندارد پیشبینی جهت فرموله کردن فرآیند Yt استفاده کرد و داده در زمان t یعنی xt را تخمین زد. [36]
در سال 1995، یک مدل سری‌زمانی با استفاده از روش Box Jenkin، ]15[،ارائه شد که در واقع با بکارگیری مدل‌های ARIMA به دنبال پیدا کردن تطابق سری زمانی با داده‌های بیشتر بودد. این تحقیق با هدف پیشبینی نرخ ترافیک آینده و بر روی پایگاه داده‌ی نرخ ترافیکی از 5 شریان اصلی شهر انجام شد. این روش قادر بود تا تنها با نگهداری آخرین خطای تخمینی و نمونه جریان ترافیکی جاری، مدلسازی را انجام دهد که این مطلب از جمله ویژگی‌های مطلوب آن محسوب می‌شد [35].
در راستای بهبود کیفیت پیش‌بینی در روش‌های مبتنی بر مدل‌های ARIMA، در سال 1999 مدل ARIMA Subset ارائه شد که تنها تفاوت آن با مدل ARIMA استفاده از تعداد کمتر ضرائب غیرصفر در بردار ضرائب بود. این مدل با سه مدل دیگر با نام‌های مخفف FAR، SAR و Full ARIMA مقایسه و بر روی داده‌های جمع آوری شده در طول 7 ساعت از روز در بازه‌های 5 دقیقه‌ای اعمال شد. هدف این مدل‌ها پیشبینی نرخ ترافیکی مربوط به یک گام جلوتر بود و به منظور ارزیابی آنها دو تست نویز سفید نیز اعمال شد. نتایج نشان داد که از میان دیگر مدل‌های سری زمانی، Subset ARIMA دقیق‌ترین نتیجه و بالاترین کارایی را خواهد داشت[13].
علاوه بر این، اگر مدل‌های ARIMA برای واریانس خطا در نظر گرفته شود، مدل حاصل GARCH ارائه شده توسط [37] خواهد بود. در سال 2005، Kamarianakis و همکارانش مدل GARCH را با هدف ارائه خاصیت داینامیک جریان‌های ترافیکی به کار گرفتند. در واقع نظر به تغییرات واریانس جریان‌های ترافیکی در طول زمان، هدف این مطالعه ارائه بازه‌های اطمینان بهتر، در خصوص پیش‌بینی بود. این تحقیق به روی داده‌های جمع‌آوری شده توسط حلقه‌های تشخیص وسائل نقلیه که در خیابان‌های اصلی منتهی به مرکز شهر آتن در یونان قرار داده شده بودند، انجام شد. در واقع با توجه به کارآیی مناسب مدل ARIMA در خصوص پیش‌بینی کوتاه‌مدت و پریودیک، این مدل با مدل GARCH ترکیب شد تا به کارآیی بالاتری دست یابد [16].
از جمله معایب این روش‌ها، مناسب نبودن آن‌ها برای پیش‌بینی سری‌های زمانی غیرخطی است. در سال 2003 محققان به بررسی این موضوع پرداختند و تحقیقات گسترده‌ای را به منظور ارزیابی سیستم پیاده‌سازی شده‌ی در خصوص پیش‌بینی سری‌های زمانی غیرخطی با در نظرگرفتن پارامترها و شرایط متفاوت ترافیکی، انجام دادند [17]. همچنین یک مدل خطی برای امتحان تاثیرات سطح تراکم ترافیکی، prediction horizon و تعاملات آنها روی خطای نسبی پیش‌بینی سرعت ترافیکی، ارائه دادند. نتایج حاصل، بیانگر افت کارایی مدل در مقابل رشد تراکم بود. همچنین نشان داده شد که همه پارامترها تاثیر بسزایی درمیزان خطای نسبی دارند. علاوه بر این تعاملات مهم بین پارامترهای مهم با اندیس تراکم، نشان‌داد که پیش‌بینی کوتاه‌مدت و rolling horizon در شرایط تراکم، مطلوب‌ترند[22] .
بطور کلی، تکنیک‌های مبتنی بر آنالیزهای سری زمانی برای تشخیص رفتار فصلی داده‌های ترافیکی گسترش یافتند. هرچند، واضح است که رفتار فصلی در خصوص پریودهای طولانی مدت رخ می‌دهد. همان طور که پیش‌تر بیان شد، هدف این پایان نامه پیشبینی کوتاه مدت ترافیک است. بنابراین واضح است که در این بازه‌های زمانی کوتاه، روند stochastic و نه فصلی، دیده می‌شود. پس به منظور اعمال روش‌های تخمین مبتنی بر آنالیزهای سری زمانی، نیاز به انجام پیش پردازش‌هایی شامل stationarity، نویز سفیدو غیره می‌باشد [22].
از طرف دیگر، اعمال روش‌های کلاسیک مبتنی بر آنالیزهای سری زمانی، نیازمند در اختیار داشتن یک روند صاف‌تر، با از حذف نوسانات زمانی از داده‌های حجیم ترافیکی می‌باشد. در سال 2003، Washington این هدف را در پیش گرفت. هرچند این روش برای پیشبینی کوتاه مدت، بدلیل از دست دادن اطلاعات مفید با شکست مواجه شد [38].
روش‌های مبتنی بر مدل‌های شبکه عصبی مصنوعیبر خلاف آنالیزهای سری زمانی که غالباً بر روی ساختارهای داخلی داده، مانند همبستگی و تغییرات فصلی تکیه دارند، روش‌های شبکه عصبی قابلیت تطبیق با هر پایگاه داده و با بکارگیری توابع سیگمُید مختلف و لایه‌های مخفی کافی، دارند.
در سال 1998، برای پیش‌بینی سری‌های زمانی، شبکه‌های عصبی RBF بکار گرفته شدند[9]. RBFN در واقع یک شبکه عصبی‌ایست که از توابع --ial basis بعنوان تابع‌های activation استفاده می‌کند و خروجی آن یک ترکیب خطی از توابع --ial basis اعمال شده به روی ورودی‌ها و پارامترهای نرون‌هاست. بطور معمول این شبکه‌ها در جهت تخمین تابع، پیش‌بینی سری‌های زمانی و کنترل سیستم‌ها استفاده می‌شوند. داده‌ی مورد استفاده در آن مطالعه، مشاهدات واقعی متعلق به نرخ ترافیکی آزاد راه‌ها بود که به بازه های 5-دقیقه‌ای در آمده بودند. این روش با متد ESM و سری‌های تیلور ، متد double exponential moothing BPN مقایسه شد که از میان آن‌ها RBFN با صرف زمان محاسباتی کمتری نسبت به BPN، بهترین کارآیی را نتیجه داد[22] .
در [10] یک سیستم مبتنی بر شبکه عصبی تأخیر زمانی (TDNN) ارائه شد تا بر اساس پروفایل‌های گذشته مسیرها و همسایه‌های آن‌ها، پیشبینی را انجام دهد. این مطالعه بر روی داده‌های واقعی و مصنوعی، اعمال شد تا جریان‌های ترافیکی را پیش‌بینی کند. نتایج بیانگر آن بود که بکارگیری 3 حلقه در دو جهت یک مسیر برای پیش‌بینی کافی است. از دیگر نتایج مهم این مطالعه این بود که برای رسیدن به دقت بالا، باید سطح دامنه‌ی داده‌ها در حد Horizon Prediction باشد.
به منظور بهبود استفاده از شبکه‌های TDNN، یک مدل غیر پارامتریک و داینامیک time-delay recurrent wavelet برای تخمین جریان ترافیکی توسط [8] ارائه شد. این تکنیک رفتارهای موجود در جریان‌های ترافیکی همانند منحصربفرد، خود مشابهی و و فرکتال را در روند مدل‌سازی دخیل می‌کند. همچنین برای تخمین بُعد بهینه ورودی سری‌های زمانی ترافیک از توابع آماری همبستگی استفاده کردند. این روش با دخیل کردن زمان، شامل زمان رخداد در چه هنگام از روز و چه روز از هفته، توانست برای پیشبینی طولانی- مدت و کوتاه مدت کاربرد مناسبی داشته باشد.
علاوه بر روش‌های ذکر شده، روش‌های ترکیبی دیگری از شبکه‌های عصبی و دیگر الگوریتم‌ها نیز ارائه شدند. بطور مثال، در سال 2005 ترکیبی از یک مدل شبکه عصبی و الگوریتم ژنتیک در نظر گرفته شد تا با استفاده از GA، ساختار شبکه و قوانین یادگیری را بهینه کند. این روش با مدل‌های ARIMA و state-space مقایسه و بر روی داده‌های یک خیابان اصلی در بازه‌ی ماه‌های ژانویه تا مِی سال2000، از شهر یونان ارزیابی شد. نتایج این مقایسات کارآیی روش را بخوبی نشان داد [11].
در سال 2010 نیز، متدی مبتنی بر شبکه های عصبی بر روی داده‌های مورد استفاده در این پایان نامه ارائه شد. این روش RBM را به همراه دو الگوریتم دیگر؛ فاکتورگیری شبه تجزیه‌ی مقدارهای منفرد (SVD-like) و حداقل مربعات خطی (LLS) را به کار گرفت تا تراکم ترافیک در 10 دقیقه بعدی را پیشبینی کند. در نظر گرفتن انواع پارامترها با این سه روش منجر به تشکیل یک ترکیب خطی از 20 پیشبینیکننده شد. همچنین واحدهای مخفی در این مدل توزیع شرطی برنولی در نظر گرفته شدند. علاوه بر این، آموزش فاکتورگیری SVD-like، با گام‌های G--iant descent و LLS نیز بر اساس رگرسیون خطی وزن‌دار انجام شدند. این تحقیق که در راستای مسابقهی ICDM (2010) ارائه شد، در بخش پیش‌بینی ترافیک مقام اول را کسب کرد و کارآیی قابل توجهی در مقایسه با دیگر روشها نشان داد.

پژوهش

دسته‌بندی نشده

No description. Please update your profile.

LEAVE COMMENT

نظرات (0)
امکان ثبت نظر جدید برای این مطلب وجود ندارد.