استفاده از تجزیه ماتریسی برای پیش‌بینی سرعت آفلاین در اسنپ

مقدمه

در این مقاله سعی می‌کنیم به کمک هم، مفهوم و کاربرد تجزیه‌ی ماتریسی (Matrix Factorization) رو یاد بگیریم و ببینیم چطور توی اسنپ تونستیم از این روش برای پیش‌بینی سرعت آفلاین تو مسأله ترافیک استفاده کنیم.

توی اسنپ یکی از اهداف مهم تیم نقشه محاسبه ETA یا همون «زمان تقریبی رسیدن» هست. ما از ETA در قسمت‌های مختلف اپلیکیشن و سرویس‌های اسنپ (مانند پیشنهاد سفر، قیمت‌گذاری سفر و نمایش به کاربر) استفاده می‌کنیم.

به عنوان مثال، به ازای هر سفر یک راننده، یک ETA بر اساس سرعت‌هایی که تو طول معابر اون سفر ثبت شده محاسبه می‌شه. فاصله باقیمانده تا مقصد به سرعت‌های قبلی موجود تقسیم می‌شه تا زمان رسیدن تقریبی تخمین زده شه.

ما از سرویسی به نام «Typical Speeds» در کنار سیستم پیشبینی بلادرنگ (real-time) سرعت خودمون استفاده می‌کنیم تا از وجود سرعت قابل‌ اطمینان تو ساعات مختلف روز برای محاسبه ETA مطمئن باشیم چرا که ممکنه در معبری خاص از معابر دخیل تو محاسبه ETA سرعتی ثبت نشده باشه. در نتیجه برای چنین شرایطی ما به سرعتی که معمولا راننده‌ها تو گذشته و تو اون ساعت خاص ازش عبور کردن استناد می‌کنیم و ازش استفاده می‌کنیم.

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

برای اینکه ETA قابل اعتمادی تولید کنیم لازمه که توی ماتریس معبر-سرعت‌مون در بازه‌های زمانی مختلف روز و هفته کم‌ترین سرعت خالی رو داشته باشیم. همونطور که در بالا اشاره کردیم ممکنه معابری در سطح کشور وجود داشته باشه که راننده‌های اسنپ از اون رد نشدن یا کم‌تر رد شدن و مشکلی که برای ما بوجود میاد، وجود ماتریس پراکنده‌ای (تنک یا اسپارس)، مثل شکل زیر، بر اثر تولید نشدن سرعت در بازه‌های زمانی مختلفه که ما به کمک روش تجزیه‌ی ماتریسی تونستیم اون رو حل کنیم.

آشنایی با مفهوم تجزیه‌ی ماتریسی (Matrix Factorization)

تجزیه‌ی ماتریسی یک مدل تعبیه‌سازی (Embedding Model) به‌حساب میاد و سعی می‌کنه با تجزیه ماتریس اصلی به حاصل‌ضرب دو ماتریس با ابعاد پایین‌تر رنک ماتریس رو کم کنه. رنک یک ماتریس به معنای تعداد سطر یا ستون‌های مستقل خطی‌ اون ماتریسه. استفاده اصلی این روش توی بحث سیستم‌های توصیه‌کننده (Recommender System) هستش که سعی‌ می‌کنه یک‌سری ويژگی که ما‌به‌ازای بیرونی (Latent Factor) ندارند رو پیدا کنه و ضرب ماتریس‌های شکسته شده فاصله کمینه‌ای با ماتریس اصلی داشته باشه (تا ماتریس‌های تا حد امکان مشابه تولید بشه). حالا با ضرب خونه‌های ماتریس‌های تجزیه شده تو هم می‌شه خونه‌های خالی تو ماتریس اصلی رو پیش‌بینی کرد.

اگر دوست دارین با جزئیات ریاضی این روش بیشتر آشنا شین پیشنهاد می‌دم این لینک رو بخونید.

مثلا در مثال بالا می‌تونین ببینین که یه ماتریس User-item داریم که سطرهاش کاربرای سیستم توصیه‌کننده‌مون هستن و ستون‌هامون لیستی از آیتم‌های مختلف. هر خونه از این ماتریس امتیازاتی هستش (۱ تا ۱۰) که کاربرای مختلف به آیتم‌های (فیلم، محصول، معبر و ..) مختلف دادن. اما ممکنه بعضی از خونه‌های این ماتریس به دلیل عدم مواجهه آیتمی توسط کاربر خالی باشن و ما بخوایم با استفاده از روش معرفی شده پیش‌بینیشون کنیم و برای توصیه کردن ازشون استفاده کنیم. پس برای بدست اوردن مقدار ۸ تو خونه پایین (که فرض ما اینه که از ابتدا وجود نداره)، سطر آبی رنگ ماتریس Q رو در ستون‌ آبی ماتریس P (که ماتریس‌های تجزیه شدنمون توسط تکنیک تجزیه‌ی ماتریسی هستن) ضرب می‌کنیم تا مقدار ۸ بوجود بیاد و اینطوری ما یک پیش‌بینی از امتیاز مورد نظرمون داریم.

روش پیشنهادی

تو مسأله ما این بار بجای وجود ماتریسی با ویژگی‌های کاربر و آیتم، ماتریس پراکنده و بزرگی داشتیم از زمان‌های مختلف هفته و معابر مختلف شهر‌های ایران. توی خونه‌های این ماتریس سرعت‌ها به ازای زمان و معبر ثبت شدند که از حرکات رانندگان اسنپ که توی سفر هستند بدست میاد. منظور از پراکنده بودن ماتریس (sparsity) اینه که ممکنه ما برای خیلی از زمان‌های مختلف توی معابر مختلف هیچ سرعت ثبت شده‌ای نداشته باشیم اما برای محاسبه زمان تقریبی رسیدن بهشون نیاز داریم. این‌جاست که با کمک تکنیک تجزیه‌ی ماتریسی تونستیم مقادیر خونه‌های خالی رو پیش‌بینی کنیم. اما چطور؟ به کمک چه ابزاری؟

خب از اول گفتن لازم نیست چرخ رو دوباره اختراع کنیم. اما باید حواسمون باشه که ممکنه چرخی که شما سابقه استفاده رو داشتین چرخ دوچرخه بوده اما این‌بار چرخ کامیون مورد نیازتونه. اینجاست که ورود مسأله به کلان‌داده یا همون Big Data باعث می‌شه ما بریم سمت انتخاب چرخ درست برای حل مسأله با ابعاد خودمون.

همونطور که محمد توی مقاله خودش در ارتباط با «نمایش نقاط پرتکرار برای مسافران اسنپ» توضیح داد، ما از Apache Spark برای پردازش داده‌های عظیم استفاده می‌کنیم. فرض کنید ماتریسی که ما به ازای هر هفته پردازش می‌کنیم ممکنه ابعاد میلیونی داشته باشه و طبیعاتاً استفاده از روش‌های موازی‌سازی مثل اسپارک خیلی کارمون رو راحت‌تر می‌کنه (البته که چالش‌های شیرین خودش رو هم ایجاد می‌کنه و همچنان بحث مدیریت منابع یک دغدغه اصلی برای کار با کلان‌داده‌هاست که جلوتر چند نمونه‌اش رو بررسی کردیم).

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

الگوریتم ALS (Alternating Least Square) یک روش پیاده‌سازی بصورت موازی تجزیه‌ی ماتریسی هستش که تو سال ۲۰۰۹ تونست توی مسابقه‌ای که نتفلیکس برای پیدا کردن بهترین الگوریتم برای استفاده توی سیستم‌های توصیه‌کننده برگزار کرد مقام اول رو کسب کنه و پیاده‌سازی کاملش توی کتاب‌خونه نام‌برده وجود داره.

تو مسأله ما، بعد از گرفتن داده‌های هفته‌های مورد نظر، ما شروع به تمیزکاری‌های اولیه داده می‌کنیم. مثل حذف داده‌های پرت که تو چند مرحله و با اعمال چند فیلتر و منطق انجام می‌شه. بعد از حذف داده‌های پرت ما یک ماتریس پیش‌پردازش شده آماده برای ورود به مدل ALS مون داریم که ستون‌هاش شامل بازه‌های زمانی هفتگی و سطرهای اون شامل آی‌دی‌های منحصر بفرد معابرمون هستش. هر خونه این ماتریس هم ممکنه شامل یک سرعت از قبل ثبت شده باشه یا نباشه (که هدف در نهایت اینه هیچ خونه‌ای از این ماتریس خالی نمونه).

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

برای پیدا کردن بهترین پارامترها با داشتن داده‌های فعلی‌مون، از روش Grid Search استفاده کردیم که پیاده‌سازی اسپارکی اون رو می‌تونین این‌جا پیدا کنید.

تو این روش ابتدا یک آرایه از مقادیری به ازای هر هایپرپارامتر که حس کردیم می‌تونن کاندیداهایی خوبی باشن به‌عنوان ورودی به این کلاس دادیم و بعد یه روش ارزیابی مثل در اوردن خطای MAE استفاده کردیم و در کنار CrossValidator، که وظیفه تجزیه داده‌های ورودی به k بخش رو داره که هر دفعه 1/k مجزا رو به عنوان داده تست استفاده می‌کنه، استفاده کردیم و در نهایت با مقایسه خطای هر مدل بهترین مدل با کم‌ترین خطا رو پیدا کردیم.

حالا با داشتن بهترین مدل، داده ورودیمون رو به مدل دادیم و از نتیجش برای پیش‌بینی سرعت‌های جدید استفاده کردیم.

بیاین یک مثال از دنیای واقعی رو به کمک هم بررسی کنید. فرض کنین می‌خوایم بررسی کنیم این پیش‌بینی‌ها برای خیابون سعیدی (خیابون کنار شرکتمون) چطور عمل کرده و برای ساعات مختلف روز چه پیش‌بینی‌هایی برای سرعت تولید کرده.

مثلا مشاهده کردیم که برای بازه ۱۲ تا ۱۵ هر روز (به غیر از جمعه‌ها) یه الگوی مشخص وجود داره و سرعت از ۱۶ کیلومتر بر ساعت شروع می‌شه و رفته‌رفته با نزدیک شدن به ساعت‌های پایان کار اداره‌جات، این سرعت هم کاهش پیدا می‌کنه و تا ۱۰ کیلومتر بر ساعت می‌ره از نظر مدل ALS که نشون می‌ده تونسته درک درستی از ترافیک اون معبر در زمان‌های مختلف داشته باشه.

برای اینکه از صحت این سرعت‌ها نیز مطمئن بشیم اون رو با چندتا از داده‌های سرعت واقعی ثبت شده توی سیستممون تو اون ساعت مقایسه کردیم و اعدادی که مشاهده کردیم با دقت خیلی خوبی نزدیک بودن که نتیجه‌اش رو می‌تونین در نمودار زیر ببینین:

بعد از اینکه یه بازه زمانی خاص از خیابون سعیدی توی یک روز خاص رو بررسی کردیم، رفتیم سراغ بررسی عملکرد مدلمون توی کل هفته.

همونطور که تو نمودار بالا می‌بینین، در مقایسه با سرعت‌های واقعی ثبت شده طی اون هفته، مدل ما تونسته با دقت بالایی مقادیر سرعت و جریان ترافیک رو تشخیص بده و به ما اطمینان بده که می‌تونیم از پیش‌بینی‌هاش به‌عنوان رویکرد جدید برای Typical Speedsمون استفاده کنیم و سرعت‌های ناموجود رو موجود کنیم و دقت ETAمون رو هم متعاقباً افزایش بدیم.

پایان

ممنون که پست رو تا انتها خوندید. خوشحال می‌شم اگر نظر یا سؤالی دارید، توی کامنت‌ها با من در میون بگذارید. از مهدیه زینالی هم برای فراهم کردن تصویرسازی‌های زیبای این پست بسیار ممنونم.

در ضمن، اگه حس می‌کنین از پروژه‌هایی شبیه به این خوشتون میاد و در نتیجه علاقه دارید به تیم ما ملحق بشید، خوشحال می‌شیم که رزومه‌هاتون رو از طریق آدرس engineering@snapp.cab برای ما ارسال کنید. مراقب خودتون باشید!