پیش بینی زمان سفر بین شهری با استفاده از درخت تصمیم

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

پیش‌بینی زمان سفر در اصل می‌تواند با هر تکنیک رگرسیونی برای نتایج قابل اندازه گیری انجام شود. به طور خاص، یک مدل نظری را در نظر بگیرید:

y = f(x1.....xp) + e = f(x) + e

که در آن y زمان سفر وx1,.....xp ویژگی‌های متناظری هستند که متغیرهای توضیحی نیز نامیده می‌شوند به‌عنوان مثال، اطلاعات مربوط به زمان‌های سفر تاریخی، مقصد یا حتی داده‌های آب‌وهوا را که در بردار x انباشته شده‌اند (x1....... xp) در بردارند.

علاوه بر این، e یک عبارت خطا و f یک تابع رگرسیون ناشناخته است که برای توصیف رابطه بین y و x باید تخمین زده شود. برای این منظور، برنامه های کاربردی مرتبط در پیش بینی سفر از رویکردهای تحلیل سری های زمانی یا هوش مصنوعی و یادگیری ماشین استفاده کرده اند. در اینجا، ماشین‌های بردار پشتیبان ، k-نزدیک‌ترین همسایگان یا شبکه‌های عصبی و یادگیری عمیق پیشنهاد شده‌اند. ما روی روش هایی تمرکز می کنیم که از درختان به عنوان یادگیرنده پایه استفاده می کنند. به طور خاص، ما عملکرد چندین روش مبتنی بر درخت مانند CART و مجموعه‌های bagged یا تقویت‌شدهboosted را مطالعه می‌کنیم. این شامل random forest ، Extra (randomized) Trees و همچنین الگوریتم‌های Xgboost و Light-GBM است که اخیراً پیشنهاد شده است . این روش ها 1) به دلیل قوی بودن در برابر خطی بودن ویژگی‌ها و ابعاد بالا شناخته می‌شوند، 2) معمولاً آموزش آسان‌ترو 3) همچنین به بار محاسباتی کمتری نسبت به الگوریتم‌های یادگیری عمیق پیشرفته‌تر نیاز دارند. در واقع، مدل‌های Random Forests یا Stochastic Gradient Boosting پیش‌بینی‌های دقیقی را در زمینه زمان سفر نشان داده‌اند.

فرض کنیدD = (y1,x1),.....(yn,xn) داده های مشاهده شده را با xi = (xi1.... xip) نشان می دهد.

مقاله روی رگرسیون تمرکز می کند درختان از کلاس CART. ایده کلیدی این است که حریصانه فضای ویژگی را به مناطق مجزا، مثلا R1;...;Rm، تا زمانی که یک معیار توقف مشخص کامل شود تقسیم کند. در انتها، برای هر یک از نواحی مجزای حاصل که گره های پایانی نیز نامیده می شوند زمان سفر به این صورت خواهد بود:

که Nj =xi : xi,Rjاست. یعنی زمان سفر یک بردار ویژگی جدید x با در نظر گرفتن میانگین بر روی تمام yi با بردار ویژگی xi متعلق به ناحیه ای که حاوی x است، پیش بینی می شود. برای به دست آوردن عبارت مذکور، تقسیم‌های باینری به صورت بازگشتی انجام می‌شود که از مجموعه ویژگی‌های کامل (گره ریشه) شروع می‌شود و با گره‌های حاصل و غیره به صورت زیر ادامه می‌یابد: برای هر گره، مقدار ویژگی مشاهده‌شده که واریانس کل دو گره را به حداقل می‌رساند. پس از تقسیم انتخاب شده است. یک مثال اسباب بازی در شکل 1 در زیر آورده شده است، جایی که ما عمق درخت دو را انتخاب کرده ایم. در اینجا، ویژگی "روز هفته" با مقدار "آخر هفته" به عنوان انتخاب شد

اولین نقطه تقسیم درخت : دو گره بعدی فضای کامل ویژگی را به ترتیب به مشاهدات متعلق به Weekends (گره سمت چپ در ردیف اول) و همه روزهای دیگر (گره سمت راست) تقسیم می کنند. پس از آن، متغیر "زمان روز" با مقدار ویژگی "7 صبح" برای تقسیم داده های متعلق به آخر هفته انتخاب شد. دو مجموعه حاصل گره های پایانی و مقادیر پیش بینی مربوطه bc1 = 25 هستند. 7 دقیقه و bc2 = 7; 8 دقیقه طبق (1) محاسبه شد. به طور مشابه، برای روزهای هفته ویژگی "دما" با نقطه انجماد به عنوان مقدار تقسیم انتخاب شد و bc3 = 17. 4 دقیقه و bc4 = 9; 2 دقیقه محاسبه شد.

یکی از مهمترین سوالات در مورد سبد خرید انتخاب اندازه درخت است. یک استراتژی این است که ابتدا یک درخت بزرگ B0 رشد دهید تا با استفاده از تکنیک هرس، اندازه درخت را کاهش دهید. در اینجا، چندین تکنیک هرس وجود دارد و ما انتخاب کرده‌ایم که از هزینه هرس پیچیدگی (CCP) معرفی شده توسط بریمن استفاده کنیم . برای توصیف این تکنیک، ما B B0 را به عنوان هر زیردرختی از B0 در نظر می گیریم، که می توان با جمع کردن هر تعداد از گره های داخلی آن به دست آورد.

فرض کنید Qj(B) = P (xi;yi)2Rj (yi * ^cp)2=Nj میانگین مربعات خطا در ناحیه Rp باشد.

سپس CCP به صورت C (B) = Pm j=1 NjQj(B)+ m تعیین می شود. که در آن یک پارامتر تنظیم برای مبادله-o بین اندازه درخت و خوبی t وجود دارد. درخت فرعی با حداقل C (B) انتخاب می شود، به طوری که مقادیر بزرگ به اندازه درختان کوچکتر منجر می شود. این یک نکته مهم است زیرا مزیت اصلی درختان، تفسیرپذیری آنها است، همانطور که در مثال شکل بالا نشان داده شده است. با این حال، اگر اندازه درخت خیلی بزرگ باشد، تفسیر می تواند دست و پا گیر شود. علاوه بر این، درختان با هزینه یک مدل پیش‌بینی نسبتاً ساده همراه هستند که معمولاً می‌توان آن را از نظر دقت با روی آوردن به تکنیک‌های گروهی افزایش داد.