احتمال حضور پلیس در جاده‌های بین شهری

نقشه و مسیریاب نشان چطور احتمال حضور پلیس در جاده‌های بین شهری را تشخیص می‌دهد؟

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

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

شرح مساله:

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

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

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

جنس داده‌ها و محدودیت‌ها

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

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

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

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

روش پیشنهادی

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

با توجه به اینکه ما تعداد خوشه ها رو از قبل نمی دونیم و نیاز داریم مرکز چگالی یکسری از خوشه ها رو به عنوان احتمال حضور پلیس معرفی کنیم از روش DBSCAN که یک روش چگالی بیس کلاسترینگ هست استفاده می کنیم.

الگوریتم DBSCAN دو پارامتر اصلی epsilon و min_pnts داره که epsilon شعاعی رو برای همسایگی هر نقطه در طی فرآیند خوشه‌بندی تعریف می‌کنه و min_pnts هم مربوط می‌شه به حداقل تعداد نقاطی که باید در همسایگی epsilon نقطه مورد نظرمون باشه تا بتونیم اون رو به خوشه اضافه کنیم یا خوشه‌ای رو با اون توسعه بدیم.

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

این نمودار یک زانو داره و مقادیر تعداد نقاط همسایگی از یک جایی به بعد با شیب تندی افزایش پیدا می‌کنه. هدف اینه که با حفظ یک مقدار مشخص برای epsilon، مقدار مناسبی برای min_pnts پیدا کنیم که غالب خوشه‌های چگال‌تر استخراج بشن. از روش پیشنهادی در این مقاله برای استخراج حد بالا و حد پایین زانوی نمودارِ مقادیر مرتب‌شده‌ تعداد نقاط همسایگی epsilon نقاط استفاده کردیم. هرچقدر از پایین زانوی نمودار به سمت بالاتر بریم، خوشه‌بندی نهایی ما سختگیرانه‌تر می‌شه. با توجه به اینکه در فاز دوم ترجیح بر استخراج نقاطی هست که پلیس در اون‌ها از گذشته تاکنون ایستاده، حد پایین نمودار می‌تونه گزینه‌ مناسبی برای min_pnts و خوشه‌بندی فاز دوم باشه. به این ترتیب مقادیر برای epsilon و min_pnts به‌صورت اتوماتیک استخراج می‌شه. شکل ۴ مرکز خوشه‌های تشکیل‌شده از خوشه‌بندی کل دیتای لوکیشن ارسالی کاربرها رو نشون می‌ده (۳۳۸۴ خوشه).

بعد از اینکه از طریق خوشه‌بندی، مکان‌هایی که پلیس طی سال‌های اخیر در اون‌ها حضور داشته (طبق گزارش کاربرها) رو پیدا کردیم، با استفاده از مکان‌هایی که طی ۲ هفته (۳ یا ۴ هفته) قبل توسط کاربرها گزارش شده، تعدادی از مکان‌های استخراج شده در فاز قبل فعال و مابقی به‌صورت غیرفعال در نظر گرفته می‌شن. در واقع ما از طریق مراحل فاز قبل، تمامی نقاط اصلی که پلیس طی سال‌های اخیر حضور داشته رو استخراج کردیم و حالا بر اساس گزارشات چند هفته اخیر کاربرها، اون‌هایی که برای حضور پلیس محتمل‌تر هستن فعال می‌شن و مابقی غیرفعال در نظر گرفته می‌شن.

برای این کار، تعداد نقاطی از گزارشات چند هفته اخیر که در محدوده ( ۱۰۰ متری) لوکیشن‌های فاز قبلی قرار دارن رو برای هر لوکیشن فاز قبلی می‌شماریم. بعد از بین نقاطی که در فاصله مشخصی از هم هستن، اون‌هایی که تعداد گزارشات نزدیک بهشون بیشتره فعال و مابقی غیرفعال می‌شن. اینطوری هم ویژگی حرکت‌های دوره‌ای پلیس‌ها در گزارشات لحاظ می‌شه و هم در فواصل مناسب، گزارش احتمال حضور پلیس رو اعلام می‌کنیم. شکل ۵ تعداد مکان‌های احتمالی حضور پلیس رو بعد از طی کردن مراحل قبل، به کمک دیتای دو هفته قبلِ ارسالی توسط کاربرها نشون می‌ده.

طبق روالی که توضیح داده شد، باید هر ۲ الی ۳ هفته (هر ماه) طبق گزارشات چند هفته اخیر کاربرها، یک‌سری از لوکیشن‌های فاز دوم رو فعال و یک‌سری رو غیرفعال کنیم. این‌طوری همیشه احتمال حضور پلیس‌ به‌روز خواهد بود و دقت مناسبی هم خواهیم داشت.

ارزیابی دقت الگوریتم پیشنهادی

ارزیابی صحت مکان‌های استخراج‌شده، با استفاده از ترکیب روش‌های میدانی و فیدبک گرفتن از کاربرها در یک بازه زمانی ۱ ماهه حدود ۸۰ درصد تخمین زده شد.