نقشه راه GIS

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

Telegram Whatsapp Youtube
کاربرد جی ای اس

 

خلاصه

مسیرها که حرکات اشیاء را در دنیای واقعی نشان می‌دهند، معنای توقف/حرکت قابل توجهی دارند. تشخیص توقف های مسیر یک مشکل اساسی در مطالعه اجسام متحرک ایجاد می کند و به دلیل نویز اجتناب ناپذیر ثبت شده همراه با داده های واقعی، چالش برانگیزتر می شود. برای استخراج توقف‌ها با اشکال و اندازه‌های مختلف از مسیرهای منفرد با نویز، این مقاله یک رویکرد خوشه‌بندی توالی گرا را ارائه می‌کند که در آن نقاط نویز در توالی توقف را می‌توان شناسایی و به عنوان بخشی از توقف طبقه‌بندی کرد. در روش ما، ابتدا دو مفهوم کلیدی معرفی می‌شوند: (1) یک دنباله هسته که چگالی دنباله را نه تنها بر اساس مجاورت در فضا، بلکه تداوم در زمان و همچنین مدت زمان در طول زمان را تعریف می‌کند. و (2) یک توالی Eps-reachability که توالی‌های اصلی را که در طول زمان با هم همپوشانی دارند یا به هم می‌رسند جمع‌آوری می‌کند. سپس، سه معیار برای ادغام توالی‌های دسترسی پذیری Eps که توسط نویز قطع شده‌اند، ارائه می‌شوند. علاوه بر این، الگوریتمی به نام SOC (خوشه‌بندی توالی گرا)، برای استخراج خودکار توقف از یک مسیر منفرد توسعه داده شده است. علاوه بر این، یک نمودار دسترسی طراحی شده است که به صورت بصری ساختار خوشه بندی مکانی-زمانی و سطوح یک مسیر را نشان می دهد. در نهایت، الگوریتم پیشنهادی در برابر دو روش پایه از طریق آزمایش‌های گسترده بر اساس مسیرهای دنیای واقعی، برخی با نویز جدی ارزیابی می‌شود و نتایج نشان می‌دهد که رویکرد ما در تشخیص توقف‌های مسیر نسبتاً مؤثر است. الگوریتمی به نام SOC (Sequence Oriented Clustering) برای استخراج خودکار توقف ها از یک مسیر منفرد ایجاد شده است. علاوه بر این، یک نمودار دسترسی طراحی شده است که به صورت بصری ساختار خوشه بندی مکانی-زمانی و سطوح یک مسیر را نشان می دهد. در نهایت، الگوریتم پیشنهادی در برابر دو روش پایه از طریق آزمایش‌های گسترده بر اساس مسیرهای دنیای واقعی، برخی با نویز جدی ارزیابی می‌شود و نتایج نشان می‌دهد که رویکرد ما در تشخیص توقف‌های مسیر نسبتاً مؤثر است. الگوریتمی به نام SOC (Sequence Oriented Clustering) برای استخراج خودکار توقف ها از یک مسیر منفرد ایجاد شده است. علاوه بر این، یک نمودار دسترسی طراحی شده است که به صورت بصری ساختار خوشه بندی مکانی-زمانی و سطوح یک مسیر را نشان می دهد. در نهایت، الگوریتم پیشنهادی در برابر دو روش پایه از طریق آزمایش‌های گسترده بر اساس مسیرهای دنیای واقعی، برخی با نویز جدی ارزیابی می‌شود و نتایج نشان می‌دهد که رویکرد ما در تشخیص توقف‌های مسیر نسبتاً مؤثر است.
کلید واژه ها: 

توقف مسیر ; دنباله اصلی ؛ نمودار دسترسی ; خوشه بندی توالی گرا

 

چکیده گرافیکی

1. پس زمینه

یک مسیر نشان دهنده مکان های در حال تکامل یک جسم متحرک در فضای جغرافیایی در یک بازه زمانی معین است. از دیدگاه دنیای کامپیوتر، یک مسیر یک ساختار ثبت گسسته حاوی اطلاعاتی در مورد موقعیت های در حال تکامل یک جسم متحرک در فضای جغرافیایی در طول یک بازه زمانی معین است. چنین ساختاری از نقاط مکانی-زمانی تشکیل شده است که هر کدام شامل حداقل دو جزء است: یک موقعیت xy و یک مهر زمانی. تعریف رسمی برای یک مسیر در زیر آورده شده است.
تعریف 1 (مسیر). یک مسیر T = ( tid , < p 0 , p 1 , …, p N >) یک ساختار دو تایی است که در آن tid یک شناسه مسیر منحصر به فرد است. داریم: (1) p i = ( x i , y i , t i ), i = 0, …, N , x i , y i , t i ∈∈R، به عنوان یک نقطه زمانی- مکانی. و (2) ∀∀0 ≤ i < j ≤ N , t i < t j .
در اینجا، به جای p = ( x ، y ، z ، t ) ، یک نقطه مسیر را به صورت p = ( x ، y ، t ) ، ارائه می دهیم ، زیرا: (1) قسمت z، یعنی ارتفاع، همیشه در دسترس نیست. در یک مجموعه داده مسیر؛ (2) در مطالعه ما و کارهای مشابه، فقط عرض جغرافیایی (قسمت y)، طول جغرافیایی (قسمت x) و مهر زمانی (قسمت t) برای محاسبه فضا (با استفاده از x و y) نزدیکی و مجاورت زمانی مورد نیاز است. با استفاده از t)؛ و (3) تغییرات قسمت z بسیار اندک است، مخصوصاً برای مسیرهای ثبت شده در داخل شهرها، و بنابراین لازم نیست که قسمت z در محاسبه فواصل جغرافیایی اعمال شود.
به هر زیرمجموعه ای از نقاط مكانی-زمانی پیوسته در یك مسیر، دنباله می گویند. با توجه به خطاهای اجتناب ناپذیر در اندازه گیری و نمونه برداری از سیگنال های GPS، نقاط مکانی-زمانی ناگزیر از موقعیت واقعی خود منحرف می شوند. چنین انحرافی همان چیزی است که در سراسر این مقاله آن را نویز می نامیم. هنگام ضبط در یک منطقه باز، این انحراف معمولاً بین 5 تا 10 متر است، در حالی که در یک منطقه نیمه بسته یا کاملاً بسته، نقاط مکانی-زمانی ممکن است ده ها یا حتی صدها متر منحرف شوند.
در طول یک مسیر، جسم متحرک همیشه موقعیت خود را تغییر نمی دهد. گاهی اوقات عمداً برای مدتی در مکانی باقی می‌ماند، که در طی آن موقعیت جسم ثابت می‌ماند یا فقط کمی تغییر می‌کند. مدل توقف حرکت [ 1 ] مسیر از این ایده ایجاد شد. طبق مدل توقف-حرکت، یک مسیر از یک سری توقف و حرکت تشکیل شده است که در آن یک حرکت از یک توقف به توقف بعدی ادامه می‌یابد. در اینجا نقطه شروع و پایان یک مسیر به عنوان دو توقف ویژه در نظر گرفته می شود.
توقف به این معنی است که برخی از فعالیت های مهم در طول یک مسیر عمداً در مکانی برای حداقل زمان انجام شده است، به عنوان مثال، یک استراحت 15 دقیقه ای برای ناهار در یک رستوران فست فود، بنابراین یک حرکت ثابت یا آهسته موقت، مانند به عنوان انتظار برای چراغ راهنمایی و پیچیدن در گوشه، نباید به عنوان یک توقف در نظر گرفته شود. از دیدگاه داده ها، توقف با دنباله ای با سرعت صفر یا سرعت بسیار کم، مانند زیر سه کیلومتر در ساعت، تجسم می یابد.
یک حرکت دو ایستگاه متوالی را به هم متصل می کند، جایی که ممکن است از یک یا چند وسیله حرکت برای حرکت از یک مکان توقف به مکان بعدی استفاده شود. به عنوان یک رفتار متحرک معقول، جسم باید حداقل مقداری حداقل مسافت را در فضا طی کند و حداقل برای حداقل مدت زمان در طول زمان ادامه یابد. یک حرکت نیز مربوط به یک دنباله است، اما با سرعت نسبتاً بالا.
جدول 1 اصطلاحات مربوط به توقف مورد استفاده در این مقاله را خلاصه می کند، که در آن توقف مجزا و توقف کشف نشده دو موقعیتی هستند که باعث توقف منفی واقعی می شوند. هنگام اعمال الگوریتم های خوشه بندی برای یک مسیر، هر خوشه خروجی با یک دنباله مطابقت دارد. با این حال، به دلیل وجود نویز، بعید است که خوشه ها به طور مستقیم توقف ایجاد کنند. بنابراین، یک الگوریتم خوب طراحی شده برای استخراج توقف باید تا حد امکان در برابر نویز مقاوم باشد. به عبارت دیگر باید از ایجاد توقف های مثبت کاذب و استاپ های منفی واقعی خودداری کرد و در نتیجه نسبت توقف های موثر را بهبود بخشید.

2. مقدمه

با توجه به پیشرفت های سریع فناوری GPS قابل حمل، اجسام متحرک بیشتر و بیشتر (مانند افراد، اتومبیل ها، حیوانات و غیره ) در حال حاضر دستگاه های مجهز به چیپست های GPS را حمل می کنند. در نتیجه، انفجاری در جمع آوری داده های مسیر در چند سال گذشته رخ داده است که باعث ایجاد تعداد زیادی از برنامه های کاربردی شده است که از داده های مسیر به عنوان ورودی برای اهداف مختلف تحقیقاتی استفاده می کنند. نمونه هایی از این برنامه ها شامل مطالعات تحرک شخصی، مدیریت حمل و نقل شهری و تجزیه و تحلیل رفتار حیوانات است. مطالعات موجود بر روی داده های مسیر عمدتاً بر سه موضوع متمرکز شده است: مدیریت داده [ 2 ، 3 ]، تکنیک های پرس و جو [ 4 ، 5 ] و داده کاوی [ 6 ، 7]]، که هدف آن استخراج دانش با بکارگیری یا اصلاح روش های پایگاه داده سنتی به طور مستقیم بر روی داده های خط سیر خام بود. با این حال، این آثار، مسیرها را تنها نوع دیگری از داده‌های مکانی-زمانی در نظر می‌گرفتند و بنابراین نتوانستند از پتانسیل غنی معناشناسی جغرافیایی استفاده کنند.
مدل توقف حرکت، معرفی شده توسط Spaccapietra و همکاران. [ 1 ]، یک مسیر را به عنوان دنباله ای از اشیاء توقف/حرکت می بیند، که سپس می تواند با معناشناسی جغرافیایی مهم حاشیه نویسی شود. شکل 1 یک نمونه مسیر را در قالب یک مدل توقف حرکت نشان می دهد. می توان دید که توقف به این معنی است که جسم متحرک برای مدتی در مکانی می ماند تا فعالیتی را انجام دهد، در حالی که یک حرکت دو توقف متوالی را با وسیله ای برای حرکت به هم متصل می کند. مدل توقف حرکت از تحلیل‌های مسیر قوی‌تر [ 8 ] نسبت به مدل‌های مبتنی بر نقطه خام [ 2 ، 9] پشتیبانی می‌کند.]، که اغلب یک مسیر را به عنوان هندسه خط نشان می دهد. بنابراین، یک وظیفه مهم در اینجا یافتن توقف در مسیرها به طور موثر است.
در شرایط ایده آل، دقت موقعیت یابی دستگاه های GPS بین پنج تا ده متر است [ 10]. با این حال، در واقعیت، به دلیل بازتاب/مسدود کردن سیگنال‌های GPS، موقعیت‌های به دست آمده ممکن است ده‌ها یا حتی صدها متر از مکان واقعی خود دور شوند. از سوی دیگر، توقف مسیر می تواند یک اقامت در داخل ساختمان باشد یا در هر مکان در فضای باز رخ دهد، که در طی آن دستگاه GPS ممکن است عمدا خاموش شود یا به ضبط ادامه دهد. علاوه بر این، یک مسیر ممکن است به طور نامنظم نمونه برداری شود و می تواند از بخش های متعددی تشکیل شود که شامل حالت های مختلف حرکت است. در نتیجه، توقف‌های مسیر ممکن است ویژگی‌های مختلفی از خود نشان دهند: تعداد زیادی از نقاط پراکنده در اطراف مکانی (معمولاً در داخل خانه)، مجموعه‌ای از نقاط توزیع شده در یک منطقه کوچک (اغلب در خارج از منزل)، یک نقطه واحد با زمان بسیار زیاد. فاصله زمانی (ناشی از خاموش کردن دستگاه یا عدم وجود سیگنال)، یا حتی مخلوطی از اینها.
برای استخراج توقف‌ها با اشکال و اندازه‌های مختلف از مسیرهای منفرد حاوی نویز، این مقاله یک رویکرد خوشه‌بندی توالی گرا را ارائه می‌کند که در آن نقاط نویز در توالی توقف را می‌توان شناسایی و به عنوان بخشی از توقف طبقه‌بندی کرد. روش ما سعی می‌کند دنباله‌های مسیری با چگالی بالا را به‌عنوان توقف تشخیص دهد، جایی که تابع چگالی با فاصله مکانی و مدت زمانی تعریف می‌شود. چندین مفهوم جدید را برای خوشه‌بندی نقاط مسیر معرفی می‌کند و سپس سه معیار را برای ادغام توالی‌های مسیر قطع شده با نویز ارائه می‌کند. بر این اساس، الگوریتمی به نام SOC (خوشه‌بندی توالی گرا) توسعه یافته است. این از دو الگوریتم خوشه‌بندی مبتنی بر چگالی الهام گرفته شده است، DBSCAN (خوشه بندی فضایی مبتنی بر چگالی برنامه ها با نویز) [ 11 ] و OPTICS (نقاط سفارش برای شناسایی ساختار خوشه بندی) [ 12 ]. علاوه بر این، یک ابزار تجسم بر اساس فاصله دسترسی طراحی شده است تا ساختار خوشه بندی مکانی-زمانی و سطوح یک مسیر را نشان دهد. در نهایت، آزمایش‌های گسترده‌ای با مسیرهای دنیای واقعی انجام می‌شود. ارزیابی نتایج نشان می‌دهد که رویکرد ما در مقایسه با دو روش پایه در تشخیص توقف‌های مسیر، به‌ویژه برای مسیرهای مستعد نویز، نسبتاً مؤثر است.
بقیه این مقاله به شرح زیر سازماندهی شده است. بخش 2 به تشریح ادبیات فعلی مربوط به تشخیص توقف های مسیر می پردازد. در بخش 3 ، ایده های اصلی زیربنایی توالی هسته و توالی Eps-دسترسی توسعه داده شده است. بخش 4 دو تکنیک ادغام توالی را مورد بحث قرار می دهد. بخش 5 الگوریتمی را برای تشکیل خودکار توقف های مسیر ارائه می کند و نمودار دسترسی را توصیف می کند که به صورت گرافیکی توقف های مسیر را نشان می دهد. الگوریتم تشخیص در بخش 6 ارزیابی شده است . بحث و نتیجه گیری در بخش آخر ظاهر می شود.

3. آثار مرتبط

این مقاله از دو الگوریتم معروف الهام گرفته شده است: DBSCAN و OPTICS. DBSCAN یک الگوریتم خوشه‌بندی مبتنی بر چگالی است که می‌تواند برای کشف خوشه‌هایی با شکل دلخواه اعمال شود، در حالی که OPTICS را می‌توان یک تعمیم از DBSCAN برای محدوده‌های چندگانه در نظر گرفت، به‌عنوان مثال، ترتیبی تقویت‌شده از نقاط ورودی ایجاد می‌کند که ساختار خوشه‌بندی سلسله مراتبی آن‌ها را نشان می‌دهد. این دو الگوریتم خوشه بندی شناخته شده در بسیاری از کاربردها مورد استفاده قرار گرفته اند و به طور گسترده مورد مطالعه قرار گرفته اند. به عنوان مثال، ST-DBSCAN [ 13 ] الگوریتم DBSCAN را برای خوشه بندی داده های مکانی-زمانی گسترش می دهد.
برای DBSCAN و OPTICS، تعریف خوشه ای از نقاط فضایی بر اساس مفهوم دستیابی چگالی است. اساساً، اگر همسایگی p که با یک شعاع معین ( Eps ) تعریف می‌شود، دارای حداقل تعداد حداقل ( MinPts ) از نقاط دیگر باشد و در همان زمان q در آن همسایگی تعریف‌شده قرار داشته باشد، نقطه q مستقیماً از نقطه p قابل دسترسی است. . در اینجا p یک نقطه مرکزی نامیده می شود. نقطه q از نقطه p چگالی قابل دسترسی نامیده می شود اگر زنجیره ای از نقاط p 1 , p 2 , …, p n وجود داشته باشد.، که در آن p 1 = p و p n = q به طوری که p i + 1 به طور مستقیم از p i قابل دسترسی به چگالی است .
هم DBSCAN و هم OPTICS هر نقطه ورودی p را یک بار پردازش می کنند و یک کوئری همسایگی را برای آزمایش اینکه آیا p یک نقطه اصلی است یا نه انجام می دهند. اگر p یک نقطه مرکزی باشد، یک خوشه جدید ایجاد می شود که با افزودن بازگشتی نقاطی که از نقاطی که قبلاً در خوشه قرار دارند، قابل دسترسی به چگالی هستند، گسترش می یابد. سخت نیست که بفهمیم این دو الگوریتم به دو پارامتر نیاز دارند: Eps ، که حداکثر شعاع مورد نظر را توصیف می‌کند، و MinPts ، که حداقل تعداد نقاط مورد نیاز برای تشکیل یک خوشه را توصیف می‌کند.
کار این مقاله به طور مستقیم با دو دسته از مطالعات جهت گیری داده های مسیر ارتباط دارد. یک دسته از خوشه بندی مبتنی بر چگالی برای استخراج مکان های مهم با استفاده از مسیرهای متعدد استفاده می کند و دسته دیگر دنباله های جالبی را از مسیرهای منفرد استخراج می کند. کار ما ایده خوشه‌بندی را می‌پذیرد، اما به دسته دوم تعلق دارد.
به طور کلی، پارامترهای حرکت مانند سرعت و جهت نمایه کاملاً متفاوتی را نشان می دهند زیرا وضعیت حرکت از حرکت به توقف تغییر می کند. بر این اساس، اعمال برخی معیارها برای تقسیم یک مسیر برای شناسایی توقف ها بسیار طبیعی است [ 14 ، 15 ]. دو نمونه از این معیارها عبارتند از: (1) سرعت صفر (یا سرعت بسیار کم) برای حداقل مدت زمان مشخص. و (2) عدم وجود داده های GPS برای بیش از مدت زمان تعیین شده. با این حال، این معیارها تنها در شرایط ایده آل، یعنی شرایط بدون نویز، به خوبی کار می کنند. روشا و همکاران از تغییرات جهت برای تشخیص توقف استفاده کرد [ 16]، اما این تکنیک فقط در شرایط خاصی مانند هنگام تجزیه و تحلیل مسیر قایق های ماهیگیری به درستی کار می کند. در [ 17 ]، اطلاعات جغرافیایی متنی برای ایجاد توقف با آزمایش مدت زمان یک دنباله مسیر در مناطق مورد علاقه از پیش تعریف شده، یکپارچه شده است.
استخراج توقف تا حدی می‌تواند به عنوان یک مشکل تقسیم‌بندی مسیر دیده شود، که در آن یک مسیر به قطعات همگن تقسیم می‌شود. بوچین و همکاران یک چارچوب الگوریتمی برای بخش بندی یک مسیر بر اساس معیارهای مکانی-زمانی پیشرفته [ 18 ] ایجاد کرد. جونیور و همکاران اصل حداقل طول توصیف (MDL) را بررسی کرد و یک رویه تکراری بدون نظارت برای تقسیم‌بندی یک مسیر طراحی کرد [ 19 ]. با این حال، این روش‌های تقسیم‌بندی توجه کمی به وجود نویز در یک مسیر می‌کنند و بنابراین برای استخراج توقف‌ها مناسب نیستند.
خوشه بندی یک رویکرد اساسی و محبوب در زمینه داده کاوی است و همچنین ابزاری ضروری برای کاوش اطلاعات جاسازی شده در داده های مسیر است. به طور خاص، با خوشه‌بندی مبتنی بر تراکم، دو نوع مطالعه در ادبیات انجام شده است: یکی مکان‌های قابل توجهی [ 20 ، 21 ] مانند ایستگاه‌های راه‌آهن را پیدا می‌کند، جایی که بسیاری از مسیرها نقاط فراوانی را به جا می‌گذارند. دیگری الگوهای مسیر پیشرفته [ 22 ، 23 ] مانند رفتار دسته جمعی را استخراج می کند، که در آن گروهی از مسیرها برای مدت معینی نزدیک به هم می مانند.
با توجه به استخراج ایستگاه های مسیر، CB-SMoT (ایست و حرکت مسیرهای مبتنی بر خوشه) [ 24 ]، T-OPTICS (Trajectory-OPTICS) [ 25 ] و TrajDBSCAN (DBSCAN مسیر) [ 26]] سه روش مبتنی بر خوشه بندی موجود در ادبیات هستند. تا جایی که ما می دانیم، آنها نزدیک ترین و قابل مقایسه ترین روش ها با روش ما هستند. CB-SMoT ایده اصلی DBSCAN را گسترش می دهد که در آن یک نقطه هسته با آزمایش نقاط همسایه با سرعت متوسط ​​محاسبه می شود. مشکل اصلی CB-SMoT در این است که وقتی فقط چند نقطه از حد مجاز سرعت بیشتر می شود، کشف توقف ها دشوار است. T-OPTICS با پیروی از چارچوب اصلی OPTICS کار می کند، اما برای ویژگی های توقف در بعد زمانی، فقط نزدیکی را ثبت می کند و مدت زمان را در نظر نمی گیرد. TrajDBSCAN ابتدا کشف توقف ها را مطالعه می کند و سپس نحوه محاسبه توقف های مشترک و ایجاد سلسله مراتب توقف را بررسی می کند. در مقایسه با CB-SMoT و T-OPTICS، TrajDBSCAN از فاصله جغرافیایی به جای مسافت سفر برای توسعه مفهوم نقطه مرکزی استفاده می کند. و بنابراین حساسیت کمتری نسبت به سرعت پیدا می کند. با این حال، هنگام مواجهه با مسیرهایی با نویز زیاد، هنوز برای TrajDBSCAN یافتن نقاط اصلی و استخراج توقف ها دشوار است. علاوه بر این، سه روش مبتنی بر خوشه‌بندی نمی‌توانند نقاط منفرد را با فواصل زمانی زیاد به عنوان توقف شناسایی کنند (نگاه کنید بهشکل 2 b برای مثال)، و علاوه بر این، آنها نمی توانند مکانیزمی برای ادغام توالی های قطع شده با نویز در استاپ ها ارائه کنند (به شکل 3 b برای مثال نگاه کنید).

4. Eps-Reachability Sequence

توقف در طول یک مسیر، عملاً عملی است مانند اقامت در داخل خانه، توقف در فضای باز، یا سرگردانی در یک منطقه کوچک. بنابراین، ویژگی های ذاتی برای توقف مسیر دو برابر است: (1) نقاط نزدیک در فضا قرار دارند. و (2) توقف برای حداقل مدت زمان به طول می انجامد. برای حمایت از این دیدگاه برای توقف های مسیر، ابتدا مفهوم توالی هسته معرفی می شود. توالی هسته به عنوان اقامت طولانی در یک منطقه با شعاع کوچک تعریف می شود.
تعریف 2 (Eps-sequence). فرض کنید T یک مسیر و p یک نقطه از T باشد . دنباله Eps p ، که با Seq( p ، Eps ) مشخص شده است، حداکثر دنباله ای در T است که: (1) p را برآورده می کند. ∈∈Seq( p , Ep s); و (2) ∀∀q ∈∈Seq( p ، Eps ) که در آن فاصله ( p ، q ) ≤≤ Eps _ در اینجا، Eps یک شعاع داده شده است.
در تعریف فوق فاصله نقطه q تا نقطه p یعنی فاصله( p , q ) یک فاصله جغرافیایی است که در سراسر این مقاله با اعمال فاصله اقلیدسی محاسبه می شود . بر اساس تعریف 2، مفاهیم توالی هسته و نقطه هسته را می توان استخراج کرد، همانطور که در زیر نشان داده شده است.
تعریف 3 (توالی اصلی). فرض کنید S دنباله ای از یک مسیر باشد. S یک دنباله هسته نامیده می شود که معیارهای زیر را برآورده کند: (1) ∃∃پ ∈∈ S ، که در آن S یک Eps-دنباله از p است . و (2) فاصله زمانی S کوتاهتر از تاو نیست . در اینجا، تاو یک مدت زمانی معین است.
تعریف 4 (نقطه اصلی). فرض کنید p یک نقطه از یک مسیر باشد. نقطه p با توجه به نقطه مرکزی نامیده می شود ε�و τ�اگر Seq( p , Eps ) یک دنباله اصلی باشد.
تعریف 3 می گوید که یک دنباله هسته از مجموعه ای از نقاط پیوسته تشکیل شده است که حداقل برای مدت زمان معینی در یک ناحیه دایره ای تعریف شده باقی می مانند. نسبت 2* Eps / Tau که نشان دهنده حداکثر سرعت مجاز برای عبور از دایره با شعاع ε�( به عنوان مثال ، حرکت دقیقاً در امتداد یک قطر)، باید نسبتاً کوچک باشد تا از تشخیص اشتباه یک دنباله متحرک به عنوان یک دنباله هسته جلوگیری شود. بنابراین، یک دنباله هسته نقاط را نه تنها در فضا، بلکه در طول زمان نیز خوشه می کند، به این معنی که نقاط در یک دنباله هسته نه تنها از نظر مکانی نزدیک، بلکه از نظر زمانی نیز نزدیک هستند. توجه داشته باشید که Tau ، یک آستانه زمانی برای تعریف توالی هسته، باید به طور قابل توجهی بزرگتر از حداقل فاصله نمونه برداری در طول یک مسیر تنظیم شود.
شکل 2 دو ساختار توالی اصلی معمولی را نشان می دهد: شکل 2 a نشان می دهد که دستگاه GPS هنوز در حال ضبط موقعیت ها در طول یک رویداد توقف است، در حالی که در شکل 2 b، دستگاه GPS هنگام وقوع توقف خاموش شده است (به طور خاص، دستگاه GPS روشن شده است. پس از گرفتن نقطه 3 خاموش می شود). بر اساس ایده توالی هسته، مفاهیم فاصله هسته و فاصله دسترسی را بیشتر توسعه می دهیم.
تعریف 5 (فاصله هسته). فرض کنید p یک نقطه از یک مسیر باشد. فاصله هسته نقطه p نسبت به Eps و Tau به صورت min{ r | تعریف می شود r  ≤ ≤ Eps ∩را∩راSeq( p , r ) یک دنباله هسته است} اگر Seq( p , Eps ) یک دنباله هسته باشد. در غیر این صورت تعریف نشده است. در اینجا، UNDEFINED یک مقدار از پیش تعریف شده بزرگتر از Eps است .
فاصله هسته نشان دهنده نزدیکی مکانی یک نقطه مسیر به همسایگان زمانی آن است. در شکل 2 ، فاصله هسته در هر صورت کوچکتر از حداکثر فاصله بین نقطه مرکزی و سایر نقاط است. فاصله هسته نقطه 3 در شکل 2 b صفر است زیرا یک نقطه هسته با فاصله زمانی زیاد است.
تعریف 6 (فاصله دسترس پذیری). بگذارید p i یک نقطه از یک مسیر باشد. فاصله دسترسی p i نسبت به Eps و Tau به صورت max{فاصله هسته( pk )، فاصله( pk , p i )} تعریف می شود اگر k = max{ j | j ≤≤ من ∩را∩را p i ∈∈Seq( p j , Eps ) ∩را∩راSeq( p j , Eps ) یک دنباله اصلی است}; در غیر این صورت تعریف نشده است.
بدیهی است که اگر نقطه p در هیچ دنباله اصلی تعریف شده در p یا نقاط قبل از p قرار نگیرد ، فاصله دسترسی p مقدار از پیش تعریف شده ای بزرگتر از Eps خواهد گرفت . فاصله دسترسی یک نقطه مسیر حاکی از یک سطح خوشه بندی مکانی-زمانی با توجه به دنباله هسته است. در شکل 2 ب، فاصله دسترسی برای نقطه 2 r است، در حالی که برای نقطه 4، فاصله بین نقطه 4 و نقطه 3 است زیرا نقطه 3 نیز یک نقطه مرکزی است که به طور موقت به نقطه 4 نزدیکتر است. مشتق شده، که از آن نقاط پیوسته با فاصله قابل دسترسی نه بزرگتر از Eps تشکیل شده است .
تعریف 7 (توالی Eps-قابلیت دسترسی). فرض کنید S = { p s , p s +1 , …, p e -1 , p e } دنباله ای از مسیر T و 0 باشد ≤ ≤ س ≤≤ e < | T |. S یک دنباله دسترسی پذیری Eps با توجه به Eps و Tau نامیده می شود اگر این شرایط را برآورده کند: (1) فاصله دسترسی برای هر نقطه در S کوچکتر از Eps یا برابر با آن باشد. و (2) فواصل دسترسی برای هر دو ps -1 و p e +1 بیشتر از Eps است .
طبق تعریف 6، یک مسیر را می توان به مجموعه ای از توالی های Eps-reachability تقسیم کرد که توسط نقاطی با فاصله دسترسی بزرگتر از Eps مشخص شده است . می توان دید که طول یک دنباله Eps-reachability ممکن است به کوتاهی یک باشد، به عنوان مثال ، یک دنباله Eps-reachability که توسط یک نقطه تشکیل شده است. این اغلب زمانی اتفاق می افتد که یک نقطه فاصله زمانی نسبتا زیادی داشته باشد و در عین حال فاصله این نقطه تا نقطه بعدی نسبتاً کم باشد. چنین نقطه ای در این مقاله “نقطه بزرگ” نامیده می شود و می تواند با خاموش کردن دستگاه GPS یا عدم وجود سیگنال ایجاد شود. جابجایی نقطه بزرگ یکی از جنبه های خاص است که باید هنگام استخراج توقف های مسیر به آن توجه شود.
اگر نقاط مسیر همیشه موقعیت واقعی خود را در فضای جغرافیایی ثبت می کردند، هر دنباله دسترسی پذیری Eps در یک مسیر می تواند به عنوان یک توقف در نظر گرفته شود. با این حال، به دلیل نویز ضبط، ممکن است توقف توسط نقاط نویز قطع شود. بنابراین، ممکن است نیاز به ادغام توالی های متوالی Eps-reachability برای ایجاد توقف داشته باشد.

5. از Eps-Reachability Sequence تا Stop

به دلیل اندازه گیری سیگنال GPS و خطاهای نمونه برداری در دستگاه های تلفن همراه، انحراف موقعیت ثبت شده نادر نیست. معمولاً، داده‌های مسیر نادقیق هستند و حتی پس از فرآیندهای پیش پردازش، به عنوان مثال، تمیز کردن داده‌ها و هموارسازی داده‌ها، نویز دارند [ 27 ]. هنگام پردازش چنین داده‌های مسیر مستعد خطا، زمانی که چندین توالی دسترسی پذیری Eps توسط نقاط نویز جدا می‌شوند، ممکن است به اشتباه یک توقف تشخیص داده شود.
معیار 1: فرض کنید S 1 و S 2 دو دنباله Eps قابل دسترسی متوالی از یک مسیر باشند. اگر فاصله ( S 1 .center, S 2.center ) ≤≤2* Eps و فاصله ( S 1 .last, S 2 . first)< MinMov , سپس S 1 و S 2 باید در یک دنباله ادغام شوند. در اینجا MinMov حداقل مدت زمان حرکت است.
معیار 1 بیان می کند که اگر دو توالی Eps-دسترسی متوالی به طور نزدیک در فضا توزیع شده و با مدت زمان بسیار کوتاهی از هم جدا شوند تا به عنوان یک حرکت متحرک معقول در نظر گرفته شوند، باید در یک دنباله ادغام شوند. MinMov حداقل مدتی است که یک رفتار متحرک عادی باید طول بکشد. توجه داشته باشید که در معیار 1، مرکز یک دنباله، مرکز هندسی نیست، بلکه مرکز مکانی-زمانی است. با توجه به یک دنباله S ​​= { p s , p s +1 , …, p e -1 , p e }، مرکز مکانی-زمانی آن با وزن دادن به هر نقطه درگیر با فاصله زمانی آن، همانطور که در فرمول (1) نشان داده شده است، محاسبه می شود.

اس _ مرکز . x =∑هi = sپمن. x * (پمن + 1.تیمن + 1–پمن.تیمن)∑هi = s(پمن + 1.تیمن + 1–پمن.تیمن)اس _ مرکز . y=∑هi = sپمن. y* (پمن + 1.تیمن + 1–پمن.تیمن)∑هi = s(پمن + 1.تیمن + 1–پمن.تیمن)اس.مرکز.ایکس=∑من=سهپمن.ایکس*(پمن+1.تیمن+1–پمن.تیمن)∑من=سه(پمن+1.تیمن+1–پمن.تیمن)اس.مرکز.�=∑من=سهپمن.�*(پمن+1.تیمن+1–پمن.تیمن)∑من=سه(پمن+1.تیمن+1–پمن.تیمن)
معیار 2: فرض کنید S 1 و S 2 دو دنباله Eps قابل دسترسی متوالی از یک مسیر باشند. اگر بدنه محدب S 1 و S 2 با هم همپوشانی داشته باشند و فاصله ( S 1 .last, S .first )< MinMov , سپس S 1 و S 2 باید در یک دنباله ادغام شوند.
معیار 2، در مقایسه با معیار 1، به جای فاصله فضایی، یک محمول بر اساس شکل فضایی اتخاذ می کند. بر این اساس، نیازی به تعیین آستانه فاصله برای ادغام توالی ندارد. در نتیجه، معیار 2 انعطاف پذیرتر و قدرتمندتر از معیار 1 در ادغام توالی های Eps-reachability است. شکل 3 نمونه ای از ادغام توالی با دو معیار بالا را نشان می دهد، که در آن بدنه محدب یک دنباله قابل دسترسی Eps به صورت یک چند ضلعی چین خورده و مرکز مکانی-زمانی آن به عنوان یک ستاره ترسیم شده است. نقاط نویز در شکل 3به صورت مثلث مشخص شده اند. می توان دید که معیار 1 یا معیار 2 را می توان در حالت میانی اعمال کرد، زیرا برای دو دنباله دسترسی پذیری Eps جدا شده، مراکز مکانی-زمانی آنها نزدیک است، و علاوه بر این، بدنه محدب آنها همپوشانی دارند. با این حال، برای مورد مناسب، تنها معیار 2 را می توان اعمال کرد زیرا فاصله بین دو مرکز مکانی-زمانی نسبتاً زیاد است.
با توجه به دو توالی Eps-دسترسی متوالی، اگر مراکز مکانی-زمانی آنها به یک مکان آدرس پذیر نگاشت شده باشند، به احتمال بسیار زیاد همان توقف را نشان می دهند. برای یافتن مکان آدرس پذیر، یک ایده موثر این است که از یک ژئوکدر معکوس در مقابل مرکز مکانی-زمانی دنباله دسترسی پذیری Eps استفاده کنید. بنابراین، ما معیار دیگری برای ادغام توالی Eps-reachability داریم.
معیار 3 فرض کنید S 1 و S 2 دو دنباله Eps قابل دسترسی متوالی از یک مسیر باشند. اگر S 1 .center و S 2 .center به یک مکان و بازه آدرس پذیر معکوس کدگذاری شوند ( S 1 .last, S 2.first ) <MinMov , سپس S 1 و S 2 باید در یک دنباله ادغام شوند.
توجه داشته باشید که معیار 3 فقط در شرایطی اعمال می شود که مکان جغرافیایی معکوس آدرس پذیر باشد. با در نظر گرفتن Google Map API [ 28 ] به عنوان مثال، نوع آدرس‌های برگشتی باید «دقیق» یا «آدرس خیابان» باشد. با توجه به سه معیار فوق، یک توالی Eps-reachability می تواند به طور پیوسته رشد کند تا زمانی که هیچ توالی Eps-reachability جدیدی رسم و به هم متصل نشود. چنین توالی کاملاً رشد یافته ای توالی دسترسی کامل نامیده می شود. یک دنباله دسترسی کامل، یا از چندین توالی Eps-دسترسی ادغام شده یا توسط یک دنباله دسترسی پذیری Eps تشکیل شده است، همیشه از یک نقطه اصلی شروع می شود اما همیشه به یک نقطه اصلی ختم نمی شود.
برای یک دنباله دسترسی کامل، متأسفانه ممکن است نقاط انتهایی نقاطی باشند که در واقع از محل توقف منتهی می شوند، اما هنوز از آخرین نقطه هسته در توالی قابل دسترسی هستند. بنابراین، یک توالی با قابلیت دسترسی کامل باید پس از هرس کردن، اطمینان حاصل شود که با یک نقطه اصلی به پایان می رسد. پس از ادغام و پس از هرس، می توان توقف های نهایی را ایجاد کرد. بنابراین، به نقطه‌ای رسیده‌ایم که می‌توانیم یک تعریف رسمی برای توقف مسیر ارائه کنیم.
تعریف 8 (توقف مسیر). فرض کنید S یک دنباله با قابلیت دسترسی کامل در یک مسیر باشد. توقف مسیر، دنباله پیشوند S است که با آخرین نقطه هسته در S به پایان می رسد .

6. استخراج و تجسم مسیر متوقف می شود

این بخش ابتدا یک الگوریتم طراحی شده برای استخراج توقف های مسیر را توصیف می کند و سپس نمودار دسترسی را برای تجسم ساختار داخلی خوشه بندی مسیر مورد بحث قرار می دهد.

6.1. الگوریتم SOC

بر اساس بحث های قبلی در این مقاله، یک الگوریتم جدید، به نام SOC، برای استخراج توقف های مسیر توسعه داده شده است. کد شبه آن در الگوریتم 1 ارائه شده است. SOC ابتدا همه نقاط را روی مقدار فاصله دسترسی UNDEFINED تنظیم می کند و سپس با اسکن نقاط مسیر ورودی به ترتیب زمانی فاصله دسترسی را محاسبه می کند. در مرحله بعد، SOC دنباله های دسترسی پذیری Eps را مطابق تعریف 7 استخراج می کند، یعنی نقاط پیوسته ای که فاصله دسترسی آنها بزرگتر از ε�به عنوان توالی Eps-reachability شناسایی می شوند. پس از آن، توالی‌های همسایه Eps-reachability، که توسط نقاط نویز از هم جدا شده‌اند، اما در مکان و زمان نزدیک هستند، با توجه به معیارهای 1 و 2 در توالی‌های دسترسی کامل ادغام می‌شوند. توجه داشته باشید که اگر دو دنباله ادغام شوند، فواصل دسترسی برای نقاط بین این دو دنباله برای ارزش Eps به روز می شوند ، حتی اگر توسط هیچ دنباله اصلی پوشش داده نشده باشند. در مرحله بعد، یک روش هرس اعمال می شود تا اطمینان حاصل شود که هر دنباله دسترسی کامل با یک نقطه اصلی به پایان می رسد. در نهایت، اگر یک توقف شناسایی شده به عنوان یک توقف مثبت کاذب پالایش شود، از نتایج حذف خواهد شد.
جدول
الگوریتم 1. شبه کد برای SOC.
در مقایسه با DBSCAN و تنوع آن OPTICS، اگرچه SOC از ایده خوشه‌بندی چگالی نیز سود می‌برد، به سمت خوشه‌بندی دنباله‌ای گرایش دارد، نه تنها نزدیکی در فضا بلکه نزدیکی در زمان را نیز در نظر می‌گیرد. نکته دیگر تفاوت این است که در SOC، نقاط نویز در یک توقف مسیر را می توان به جای علامت گذاری به عنوان نویز، به عنوان بخشی از توقف تشخیص داد و پذیرفت. SOC همان پیچیدگی محاسباتی DBSCAN و OPTICS را دارد، یعنی O( n *log n). با این حال، برای SOC، پس از شناسایی یک دنباله هسته، فقط نقاط متعلق به آن دنباله هسته بیشتر بررسی می شود. در نتیجه، SOC معمولاً به I/O و محاسبات کمتری نسبت به DBSCAN و OPTICS نیاز دارد. یک آزمایش، با استفاده از یک مسیر واقعی تقریباً 5000 نقطه، نشان داد که زمان اجرا برای SOC 19 ثانیه اما برای OPTICS 33 ثانیه است.

6.2. حذف مثبت کاذب

هنگام گرفتن دنباله اصلی و تشکیل دنباله های Eps، SOC ایده ای شبیه به DBSCAN را اتخاذ می کند. بنابراین، قادر به ایجاد توقف های مسیری از اشکال دلخواه است. در نتیجه، حرکت آهسته خطی شکل، به عنوان مثال، رانندگی در ترافیک سنگین در ساعات شلوغی، ممکن است به عنوان توقف توسط SOC شناسایی شود. برای حذف این نوع از مثبت کاذب، دو شاخص، راستی و فاصله مرکزی، به طور مشترک بررسی می شوند. با توجه به یک دنباله S ​​= { p s , p s +1 , …, p e -1 , p e}، اندازه گیری های راستی و فاصله مرکزی را می توان با فرمول (2) محاسبه کرد. در اینجا، فاصله مرکزی ضروری است، زیرا برای یک دنباله، اگر نقاط میانی بیشتر طول مدت را مصرف کنند اما سهم کمی در مسافت سفر داشته باشند (مثلاً، نقاط میانی در یک منطقه بسیار کوچک توزیع شده یا فقط از یک نقطه بزرگ تشکیل شده است)، راستی مقدار زیادی ( یعنی نزدیک به 1) خواهد داشت، در حالی که فاصله مرکزی مقدار کوچکی خواهد داشت ( یعنی به طور قابل توجهی کوچکتر از Eps ). بنابراین، اگر هم راستی و هم فاصله مرکزی یک دنباله خوشه‌ای از برخی آستانه‌های مشخص شده فراتر رود، دنباله به عنوان یک توقف مثبت کاذب شناسایی می‌شود و باید فیلتر شود.

اس _ راستی =فاصله (پس، په)∑e – 1i = sفاصله (پمن، پمن + 1)اس _ مرکز – فاصله =∑هi = sفاصله (پمن، اس . مرکز ) * (پمن + 1.تیمن + 1–پمن.تیمن)∑هi = s(پمن + 1.تیمن + 1–پمن.تیمن)اس.صراط مستقیم=فاصله(پس، په)∑من=سه–1فاصله(پمن، پمن+1)اس.متمرکز شده است–فاصله=∑من=سهفاصله(پمن،اس.مرکز)*(پمن+1.تیمن+1–پمن.تیمن)∑من=سه(پمن+1.تیمن+1–پمن.تیمن)
هنگامی که یک دنباله با حالت یک حرکت دور دور آهسته مطابقت دارد، احتمالاً به عنوان یک توقف تشخیص داده می شود زیرا انجام چرخش زمان زیادی را صرف می کند. برای شناسایی این نوع از مثبت کاذب، مفهوم “جهت هدایت” بررسی می شود. به طور خاص، هنگامی که جهت حرکت برای قدامی و خلفی یک دنباله خوشه‌ای بسیار متفاوت است، دنباله نباید به عنوان توقف تشخیص داده شود.
در واقعیت، توقف با مدت زمان بسیار کوتاه ممکن است بیش از حد بی اهمیت باشد که توسط برنامه ها در نظر گرفته شود. بر این اساس، توالی‌های خوشه‌ای با مدت زمان کوتاه‌تر از برخی آستانه‌ها نباید به عنوان توقف شناسایی شوند. سه قانون فوق با هم در آخرین مرحله از الگوریتم SOC برای شناسایی و فیلتر کردن توقف های مثبت کاذب اعمال می شوند.

6.3. نمودار قابلیت دسترسی

به طور مشابه به OPTICS، خوشه بندی مکانی-زمانی نقاط مسیر را می توان به صورت گرافیکی با استفاده از یک نمودار دسترسی پذیری نشان داد و درک کرد، که در آن مقادیر فاصله دسترسی برای هر نقطه مسیر رسم می شود. توجه داشته باشید که نقاط موجود در نمودار دستیابی به شدت از دنباله نقاط ظاهر شده در مسیر ورودی پیروی می کنند.
با توجه به SOC، سه سطح فاصله دسترسی ایجاد خواهد شد: مقادیر کوچکتر از Eps برای نقاط توقف معمولی، Eps برای نقاط نویز ادغام شده، و UNDEFINED برای نقاط حرکت. UNDEFINED می تواند هر مقدار از پیش تعریف شده ای بزرگتر از Eps باشد ، اما برای سهولت در تصویر، مقدار کمی بزرگتر از Eps مانند 1.2* Eps توصیه می شود. برای یک دنباله خوشه‌ای، فاصله دسترسی کوچکتر به معنای سطح خوشه‌بندی بالاتر است، به عنوان مثال ، یک دنباله طولانی مدت محدود در یک منطقه کوچک، در حالی که یک مقدار بزرگتر به معنای سطح خوشه‌بندی نسبتاً پایین است.
برای نمودار دسترسی یک مسیر، ساختار خوشه بندی به عنوان یک کل و سطوح خوشه بندی نقاط منفرد تحت تأثیر نسبت Eps / Tau قرار می گیرد . به طور کلی، یک Eps کوچکتر یا یک تاو بزرگتر ممکن است از پوشش دادن نقاط بیشتر توسط دنباله اصلی جلوگیری کند. بنابراین، یک توالی توقف ممکن است کوچک شود یا حتی به طور کلی ناپدید شود. در مقابل، یک Eps بزرگتر یا یک تاو کوچکتر ، یک دنباله اصلی را قادر می سازد تا نقاط بیشتری را شامل شود. بنابراین، یک توالی توقف ممکن است نقاطی را در دنباله های متحرک همسایه گسترش دهد یا حتی ببلعد. تنظیم مقادیر پارامتر برای Eps و Tauدر بخش تجربی بیشتر مورد بحث قرار خواهد گرفت.
شکل 4 نمودار دسترسی با Eps = 20 متر و تاو = 50 ثانیه را برای بخشی از یک مسیر سفر جمع آوری شده در پکن، چین نشان می دهد. قسمت بالای شکل مسیر نگاشت شده را نشان می دهد. در مجموع چهار دنباله دسترسی پذیری Eps وجود دارد (که با I-IV مشخص می شوند)، که در آن دومی سطح خوشه بندی بسیار بالاتری نسبت به بقیه دارد. توجه داشته باشید که نقطه 39 یک نقطه بزرگ با فاصله زمانی 320 ثانیه است، که دلیل آن این واقعیت است که نقطه 39 و نقطه قبل از آن در اولین دنباله دسترسی پذیری Eps گنجانده شده است. با این حال، هنگامی که پارامترهای دنباله هسته به صورت Eps = 30 m و Tau = 75 ثانیه تنظیم می شوند، دنباله های Eps-reachability III و IV در یک دنباله قابل دسترسی Eps ادغام می شوند زیرا با Eps بزرگتر، نقاط بین III و IV توسط نقاط اصلی در III قابل دسترسی هستند.

7. ارزیابی تجربی

در این بخش از چهار مجموعه داده مسیر واقعی از منابع مختلف برای آزمایش عملکرد SOC استفاده شد که از دو منظر اصلی درستی نتیجه و حساسیت پارامتر مورد ارزیابی قرار گرفت. جزئیات چهار مجموعه داده مسیر در جدول 2 ارائه شده است که در آن ستون “ایستگاه های برچسب دار” تعداد توقف های برچسب گذاری شده دستی در هر مجموعه داده را نشان می دهد.
ما دو مجموعه داده اول را خودمان در ووهان، چین در سال 2014 با استفاده از تلفن‌های همراه و ضبط‌کننده‌های GPS حرفه‌ای به دست آوردیم، در حالی که دو مجموعه داده آخر عبارتند از، بخش‌های کوچک استخراج‌شده از دو آرشیو رایگان اینترنتی GPS، OpenStreetMap [29] و GeoLife [ 30 ] .]. مجموعه داده 1 توسط اپلیکیشنی که بر روی تلفن های همراه اندرویدی مجهز به چیپست جی پی اس اجرا می شود جمع آوری شده است. حرکات ثبت شده در این مجموعه داده عمدتاً در محوطه دانشگاه انجام می شود. مجموعه داده 2 توسط دو نوع ضبط کننده حرفه ای GPS جمع آوری شد: Garmin Forerunner و Holux M-1200E. حرکات ثبت شده در این مجموعه داده مسیرهای رفت و آمد را در ساعات شلوغی ثبت کرد. مجموعه داده سوم شامل حرکات روزانه داوطلبان در پکن، چین در سال 2009 است و آخرین مجموعه داده انتخاب شده در سال 2010 توسط برخی از داوطلبان ژاپنی آپلود شد و عمدتاً مسیرهای پیاده روی در ژاپن را ثبت کرد.
مجموعه داده 1 مستقیماً در قالب توالی توقف-حرکت فرمت شد. بنابراین، اطلاعات توقف برای هر مسیر بسیار آسان است. برای سه مجموعه داده دیگر، یک رویکرد بصری مبتنی بر QGIS (سیستم اطلاعات جغرافیایی کوانتومی) [ 31 ] برای بررسی دستی و علامت‌گذاری توقف‌های مسیر اعمال شد. به طور خاص، توقف های طولانی تر از سه دقیقه در طول هر مسیر به دقت برچسب گذاری شدند. علاوه بر این، برنامه اندرویدی که برای جمع‌آوری مجموعه داده 1 استفاده می‌شود، به گونه‌ای طراحی شده است که هنگام ورود به فضای داخلی، ورود به سیستم را متوقف کند، در حالی که ضبط‌کننده‌های GPS که در جمع‌آوری مجموعه داده 2 استفاده می‌شوند، پس از شروع به ثبت نقاط، حتی در داخل خانه، ادامه می‌دهند.
مجموعه داده 1 در محوطه دانشگاه نمونه برداری شد. مجموعه داده 4 در برخی از مناطق روستایی به دست آمد. در نتیجه، نویز در دو مجموعه داده نسبتاً کم است و میانگین انحراف حدود 10 متر است. با این حال، دو مجموعه داده دیگر در شهرهای بزرگ با سیگنال‌های GPS کمتر از ایده‌آل به دلیل انعکاس/مسدود کردن سیگنال رخ داده‌اند و در نتیجه، نویز فراگیر و جدی می‌شود. به عنوان مثال، یک مسیر از مجموعه داده 2 وارد ساختمانی شد که برخی از نمونه ها چندین صد متر از موقعیت واقعی خود دور شدند. یک مسیر از مجموعه داده 3 از زیر یک راهرو عبور کرد که برخی از نمونه ها بیش از 50 متر انحراف داشتند.

7.1. تنظیمات آزمایشی

همانطور که در الگوریتم 1 بیان شد، الگوریتم SOC به سه پارامتر کلیدی بستگی دارد که در جدول 3 خلاصه شده است . در میان آنها، Eps و Tau برای تولید توالی های Eps-reachability استفاده می شوند، در حالی که MinMov برای ادغام دنباله های Eps-reachability استفاده می شود. علاوه بر این، چهار مقدار آستانه اضافی (صراط مستقیم، فاصله مرکزی، تفاوت جهت و حداقل مدت توقف) برای فیلتر کردن سه نوع توقف مثبت کاذب مورد نیاز است. پس از آزمایش با مسیرهای مثال، پارامترهای مقدار آستانه به ترتیب روی مقادیر پیش فرض 0.5، 2* Eps متر، 90 درجه و سه دقیقه تنظیم شدند. مگر اینکه به صراحت مشخص شود، همه پارامترها مقادیر پیش فرض را برای همه آزمایش ها در نظر می گیرند.
با تنظیم پیش‌فرض، نمودار دسترسی یک مسیر در فضای باز از Dataset 2 در شکل 5 نشان داده شده است (بخش سمت چپ مسیر نقشه‌برداری شده است). ما به وضوح می بینیم که در طول سفر چهار توقف وجود دارد که کاملاً با واقعیت مطابقت دارد. همچنین مشاهده می‌کنیم که اولین و آخرین ایستگاه‌ها فواصل قابل دسترس کمی دارند، به این معنی که نقاط از نظر مکانی-زمانی به خوبی خوشه‌بندی شده‌اند. در واقع، دو ایستگاه مربوط به ایستادن ساده در فضای باز است.
در طول فرآیند ادغام توالی، برای به دست آوردن یک آدرس خیابان، از کدگذاری جغرافیایی معکوس فراخوانی می شود. در عمل، ما استفاده از دو سرویس مختلف رمزگذاری جغرافیایی معکوس، یعنی نقشه های گوگل و نقشه های بایدو را انتخاب کردیم [ 32]. از آنجایی که Baidu Maps اطلاعات آدرس فراوان تری در چین دارد، الگوریتم زمانی که مرکز مکانی-زمانی یک دنباله در چین قرار می‌گیرد، سرویس geocoding معکوس Baidu Maps را فراخوانی می‌کند. در غیر این صورت، با سرویس نقشه گوگل تماس می گیرد. از آنجایی که آدرس‌های برگشتی به‌عنوان ساختارهای رشته‌ای قالب‌بندی می‌شوند، SOC به سادگی مقایسه رشته‌های استاندارد را بررسی می‌کند تا بررسی کند که آیا توالی‌ها آدرس یکسانی دارند یا خیر. توجه داشته باشید که طول و عرض جغرافیایی واقعی برای آدرس ها در تماس با سرویس Baidu Maps رمزگذاری شده است. بر این اساس، قبل از انجام ژئوکدینگ معکوس با استفاده از نقشه بایدو، مراکز مکانی-زمانی که در ابتدا با استفاده از مشخصات WGS (سیستم ژئودتیک جهانی) 84 کدگذاری شده‌اند، باید به سیستم مختصات مورد استفاده توسط نقشه بایدو ترجمه شوند. این را می توان با فراخوانی API خارجی Baidu Map نیز انجام داد.
در اجرای فعلی ما، می‌توانیم داده‌های مسیری با فرمت TXT یا GPX را بپذیریم که قبل از پردازش در حافظه خوانده می‌شوند. استاپ های به دست آمده به صورت یک فایل متنی خروجی می شوند و با متلب نمایش داده می شوند. از آنجایی که یک مسیر منفرد معمولاً اندازه کوچکی دارد، چنین پیش پردازشی مشکلی ایجاد نخواهد کرد. به عنوان مثال، اندازه ذخیره سازی یک مسیر 24 ساعته با نرخ نمونه برداری 1 ثانیه کوچکتر از هفت مگابایت است (در اینجا 10 فیلد اطلاعاتی مانند طول جغرافیایی، طول جغرافیایی و مهر زمانی ثبت شده است). حتی در مواجهه با یک خط سیر بسیار بزرگ که نمی تواند در حافظه جا بیفتد، فقط قسمت های خواندن نقطه و مکان یابی محله برای کار بر روی حافظه خارجی مانند سیستم فایل یا سیستم DB برای به روز رسانی لازم است.

7.2. ارزیابی اثربخشی

برای تایید اثربخشی SOC، دو روش پایه در اینجا استفاده شد: تست سرعت و CB-SMoT. در روش تست سرعت، 3 کیلومتر در ساعت به عنوان حد مجاز برای تست نقاط توقف انتخاب شد. در روش CB-SMoT از همان Eps و Tau برای تولید خوشه ها استفاده شد. دو روش پایه، مشابه SOC، توقف هایی را نیز هرس می کنند که بیش از سه دقیقه طول نمی کشد. نتایج در جدول 4 نشان داده شده است که در آن “SOC بدون ادغام” به این معنی است که تابع ادغام دنباله برای آن آزمایش غیرفعال شده است. برای یک دنباله مسیر معین S ، چهار شرط وجود دارد: (1) اگر S یک توقف برچسب‌دار باشد و به عنوان یک توقف تشخیص داده شود، به عنوان یک توقف مؤثر محاسبه می‌شود. (2) اگر Sبرچسب گذاری نشد، اما به عنوان یک توقف تشخیص داده شد، به عنوان یک توقف مثبت کاذب محاسبه می شود. (3) اگر S برچسب گذاری شده باشد اما به عنوان توقف های متعدد شناسایی شود، به عنوان یک توقف جدا شمرده می شود. و (4) اگر S برچسب خورده باشد اما به عنوان توقف شناسایی نشده باشد، به عنوان یک توقف شناسایی نشده محاسبه می شود. توجه داشته باشید که ما یک فرمول داریم: “توقف های برچسب دار” = “توقف های موثر” + “توقف های جدا شده” + “توقف های شناسایی نشده”. ستون آخر نشان دهنده میانگین نسبت تعداد یک اندازه گیری به تعداد توقف های برچسب گذاری شده است.
می بینیم که SOC در همه موارد در تشخیص توقف های موثر بهتر از دو روش پایه عمل می کند. حتی بدون مرحله ادغام، میانگین دقت تشخیص توقف های موثر برای SOC 83.5٪ است، در حالی که برای CB-SMoT و تست سرعت به ترتیب 75.4٪ و 65.5٪ است. شکل 6a یک سناریوی رایج را نشان می دهد – توقفی در داخل ساختمان که SOC با موفقیت آن را تشخیص داد اما تست سرعت و CB-SMoT نتوانستند آن را تشخیص دهند. این به این دلیل اتفاق افتاد که SOC به جای مسافت سفر برای تعریف نقاط اصلی از فاصله جغرافیایی استفاده می کند و بنابراین نسبت به سرعت یک جسم کمتر حساس است و در برابر نویز قوی تر است. پس از فعال کردن تابع ادغام در SOC، در مجموع 19 توقف جدا شده با موفقیت به عنوان توقف موثر شناخته شدند. بر این اساس، میانگین نسبت تشخیص توقف های موثر به 91.3 درصد بهبود یافت. همچنین مشاهده می‌کنیم که SOC دو روش پایه را در سه معیار دیگر تحت تأثیر قرار می‌دهد: توقف‌های مثبت کاذب، توقف‌های جداشده و توقف‌های شناسایی نشده. به عنوان مثال، میانگین نسبت توقف های شناسایی نشده برای تست سرعت و CB-SMoT به ترتیب 14.6٪ و 10.0٪ است، اما برای SOC فقط 4.5٪ است.
از آنجایی که روش تست سرعت در هنگام تولید استاپ فقط سرعت را در نظر می گیرد، به نویز بسیار حساس است. از این رو، برای این روش ساده، یک توقف با نقاط بسیار به احتمال زیاد به عنوان یک توقف مجزا تشخیص داده می شود که یک یا چند نقطه میانی به دلیل نویز از آستانه سرعت فراتر رود. به همین دلیل، روش تست سرعت امکان تشخیص حرکات آهسته خط شکل یا U-turn را به عنوان توقف های مثبت کاذب کاهش می دهد. در نتیجه، تست سرعت نسبت بیشتری از توقف های جدا شده (20.0٪) اما نسبت نسبتاً پایین تر از توقف های مثبت کاذب (10.2٪) در مقایسه با CB-SMoT (به ترتیب 15.7٪ و 14.7٪) دارد.
از آنجایی که مجموعه داده‌های 2 و 3 در شهرهای بزرگ با سیگنال‌های GPS کمتر از ایده‌آل به دلیل بازتاب سیگنال چند مسیری یا مسدود شدن سیگنال نمونه‌برداری شدند، هر سه روش نسبتاً ضعیف عمل می‌کنند و بسیاری از توقف‌های برچسب‌گذاری شده را به عنوان چندین توقف کوچک شناسایی می‌کنند. برای Dataset 1، یک نکته جالب این است که SOC هیچ توقف مثبت کاذب یا جدا شده ای را تشخیص نداد زیرا سیگنال GPS در محیط دانشگاه نسبتاً خوب است. با این حال، در این مجموعه داده، 9 دنباله وجود دارد که توسط دانش آموزان به عنوان توقف توضیح داده شد اما توسط SOC شناسایی نشد. این به این دلیل است که نه توقف، اگرچه در مراحل قبلی با موفقیت شناسایی شد، در نهایت به دلیل مدت زمان کوتاه آنها ( یعنی کمتر از سه دقیقه) به عنوان توقف های مثبت کاذب فیلتر شدند .
ماندن در داخل خانه اما ادامه ثبت داده های نقطه ممکن است باعث توقف های جداگانه شود. شکل 6 ب نمونه ای از این شرایط را نشان می دهد که در آن تنها دو توقف کوچک (نقاط قرمز و سبز) مشخص شده است. در واقع، این مربوط به یک اقامت در داخل خانه حدود سه ساعت است، که در آن نقاط در اطراف یک منطقه نسبتا بزرگ پراکنده می شوند و برخی از نقاط بیش از یک کیلومتر دورتر می پرند. از آنجایی که دو ایستگاه کوچک نشان دهنده وقفه های قابل توجهی در فضا و زمان هستند، آنها نتوانستند توسط دو معیار ادغام ادغام شوند. با این حال، دو دنباله نشان داده شده در شکل 6c,d به ترتیب با معیار 1 و معیار 2 با موفقیت به عنوان دو ایستگاه منفرد ادغام شدند. برای مورد دوم، توالی‌های جدا شده به مکان آدرس‌پذیر یکسان، جغرافیایی کدگذاری شدند. به طور کلی، هر چه دستگاه GPS بیشتر در داخل خانه بماند، موقعیت‌های ثبت شده بیشتر تمایل به پراکندگی دارند، که به این معنی است که احتمال بیشتری وجود دارد که نقاط به عنوان ایستگاه‌های جدا شده تجزیه و تحلیل شوند.
علاوه بر توقف های منفی واقعی ( یعنی توقف های جدا شده و توقف های شناسایی نشده)، SOC به ناچار توقف های مثبت کاذب را معرفی می کند، حتی اگر سه قانون بررسی و اعمال شده باشد. شکل 6 e را در نظر بگیرید که مربوط به چرخش U هنگام رانندگی در زیر یک راهرو است (خطوط به رنگ سبز روشن نشان داده شده اند). از آنجایی که حرکت به دلیل ازدحام آهسته بود و دقت موقعیت به دلیل سیگنال ضعیف GPS کم بود، یک دنباله (نقاط قرمز) شناسایی شد اما فیلتر نشد و منجر به توقف مثبت کاذب شد. متأسفانه، هنگامی که یک چرخش بسیار آهسته در مکانی با سیگنال GPS ضعیف رخ می دهد، توالی ضبط شده به احتمال زیاد به عنوان یک توقف مثبت کاذب توسط SOC تشخیص داده می شود.

7.3. ارزیابی تنظیم پارامتر

مجموعه‌ای از آزمایش‌ها بر روی چهار مجموعه داده مسیر برای ارزیابی تأثیر سه پارامتر کلیدی بر عملکرد SOC انجام شد. نتایج در جدول 5 آورده شده است . دو آزمایش اول سعی می‌کنند تأثیر Eps را زمانی که Tau روی پیش‌فرض ثابت است، ارزیابی کنند. با کاهش Eps (آزمایش 1)، شرایط برای تعریف یک دنباله اصلی سخت تر می شود. بر این اساس، توالی‌های Eps-reachability نه تنها از نظر اندازه کوچک می‌شوند، بلکه تعداد آنها نیز کاهش می‌یابد. در نتیجه، کاهش Eps به احتمال زیاد باعث توقف های مثبت کاذب کمتر و توقف های مجزا/تشخیص نشده بیشتر می شود، به طوری که تعداد توقف های موثر به احتمال زیاد کاهش می یابد. برعکس، به عنوان Epsافزایش می یابد (آزمایش 2)، نتایج معکوس مشاهده خواهد شد. هدف دو آزمایش بعدی ارزیابی تأثیر Tau در زمانی که Eps روی پیش‌فرض ثابت می‌شود. با کاهش تاو (آزمایش 3)، الزامات سختگیرانه برای ایجاد یک دنباله اصلی کاهش می یابد. از این رو، احتمال تشخیص توقف های مثبت کاذب افزایش می یابد، اما احتمال ایجاد توقف های جدا/ناشناخته کاهش می یابد، در نتیجه احتمالاً منجر به توقف های مؤثرتر می شود. به طور مشابه، با افزایش تاو ، نتیجه معکوس رخ می دهد (آزمایش 4). در دو آزمایش زیر، Eps متفاوت است اما Eps / Tau روی پیش‌فرض ثابت است. به عنوان Epsکاهش می‌یابد، ارضای توالی هسته سخت‌تر می‌شود و بالعکس . بنابراین، نتایج مشابه دو آزمایش اول خواهد بود.
به طور خلاصه، Eps نسبت به Tau تأثیر بیشتری بر نتایج تشخیص دارد . یک Eps خیلی کوچک یا خیلی بزرگ برای تشخیص توقف ها مضر است. یک مقدار کوچک ممکن است توقف های جداگانه ایجاد کند، در حالی که یک مقدار بزرگ ممکن است باعث توقف های مثبت کاذب شود. نسبت Eps / Tau که به طور ضمنی توقف را به سرعت متوسط ​​کوچک محدود می کند، باید نسبتاً کوچک باشد. طبق آزمایشات ما، مقادیر نزدیک به تنظیمات پیش فرض مناسب هستند.
در نهایت، ما سعی می کنیم فقط پارامتر MinMov را تغییر دهیم . با کاهش MinMov ، قابلیت ادغام SOC کاهش می یابد. در نتیجه، برخی از توقف‌های برچسب‌دار (معمولاً در داخل ساختمان رخ می‌دهند) ممکن است در ایستگاه‌های مؤثر ادغام نشوند و در عوض به‌عنوان ایستگاه‌های جدا شده ظاهر شوند. به عنوان مثال، وقتی MinMov از 150 ثانیه به 90 ثانیه کاهش می یابد (آزمایش 8)، ده توقف برچسب دار اضافی (چهار در مجموعه داده 2 و شش در مجموعه داده 3) به عنوان توقف های جدا طبقه بندی می شوند. به طور کلی، MinMov باید به اندازه کافی بزرگ باشد تا تأثیر نویز را برای مسیرهای جمع آوری شده در محیط های مستعد خطا از بین ببرد. با این وجود، یک MinMov بسیار بزرگمقدار توصیه نمی شود زیرا یک حرکت منحنی ممکن است به اشتباه تشخیص داده شود و به عنوان یک توقف ادغام شود.
توجه داشته باشید که تعیین پارامترهای ورودی مناسب برای SOC برای کاربران کار آسانی نیست. از طریق تجزیه و تحلیل بالا، ما دریافتیم که SOC در اکثر موارد با تنظیمات پیش فرض به خوبی کار می کند، به عنوان مثال ، به تشخیص بالایی از توقف های موثر دست می یابد. با این حال، برای مسیرهایی با دقت موقعیت‌یابی ضعیف (که اغلب در شهرهای بزرگ اتفاق می‌افتد)، بهتر است مقادیر بزرگ‌تری را به Eps و Tau نسبت دهیم ، مانند 50 متر و 125 ثانیه. هنگامی که یک مسیر شامل تعداد زیادی از نقاط نویز است، MinMov باید بر این اساس، به عنوان مثال، به 300 ثانیه افزایش یابد. علاوه بر این، یک آستانه پیش‌فرض سه دقیقه را برای فیلتر کردن توقف‌های بی‌اهمیت با مدت زمان کوتاه انتخاب کردیم.

8. بحث و نتیجه گیری

8.1. بحث

توقف به معنای برخی فعالیت های هدفمند است، و بنابراین، باید حداقل مدت زمان طول بکشد. از این منظر، دورهای آهسته به عنوان توقف های مثبت کاذب در این مقاله در نظر گرفته می شوند، زیرا دور برگردان صرفاً یک حرکت خالص بدون فعالیت های دیگر است. به همین دلیل است که SOC پارامتر MinStp را معرفی می کند ، که با آن می توان ایستگاه های ثابت موقت مانند انتظار برای چراغ های راهنمایی را به عنوان توقف های مثبت کاذب شناسایی کرد و فیلتر کرد. لازم به ذکر است که MinStpدر واقع یک پارامتر وابسته به برنامه است، اگرچه در این مقاله به صورت سه دقیقه ثابت شده است. به عنوان مثال، برخی از برنامه‌ها ممکن است پنج دقیقه ملاقات دوستان در خیابان را به‌عنوان توقف ببینند، اما برنامه‌های دیگر ممکن است فقط به توقف‌هایی علاقه‌مند باشند که بیش از نیم ساعت طول بکشد.
سه معیار در SOC برای رسیدگی به توقف های قطع شده توسط نقاط نویز اعمال می شود. دو معیار اول نزدیکی مکانی-زمانی نقاط در یک توقف را بررسی می‌کنند، در حالی که معیار آخر از اطلاعات مکان در پشت ایستگاه‌ها استفاده می‌کند. البته، اگر بتوان هر دنباله دسترسی پذیری Eps را به یک مکان آدرس پذیر معکوس کرد، آخرین معیار می تواند کل عملکرد ادغام توالی را به عهده بگیرد، زیرا نه تنها دقیق تر است، بلکه معنایی را نیز حمل می کند. با این حال، در واقعیت، توقف می‌تواند در مکان‌هایی بدون آدرس دقیق رخ دهد. علاوه بر این، آرشیو آدرس جمع آوری شده در ژئوکدرهای معکوس حتی برای شهرها محدود است. از این رو، دو معیار اول اولین انتخاب SOC برای ادغام توالی هستند. توجه داشته باشید که با ژئوکدینگ معکوس، توقف های خروجی می توانند معنای آدرسی را به آنها متصل کنند. که از طریق آن می توان اطلاعات پیشرفته ای مانند هدف توقف را بیشتر استنباط کرد. با این حال، این خارج از محدوده این مقاله است.
تعریف توالی هسته هیچ محدودیتی برای سرعت در نقاط منفرد ایجاد نمی کند، اما به طور ضمنی محدودیتی بر سرعت متوسط ​​با استفاده از نسبت 2* Eps / Tau اعمال می کند . همانطور که در بخش آزمایشی اعلام شد، این باید نزدیک به تنظیمات پیش فرض باشد ( یعنی 2*(30/75)*3.6 = 2.88 کیلومتر در ساعت)، که آشکارا کمتر از میانگین سرعت راه رفتن انسان است ( یعنی 5 کیلومتر در ساعت). h). از آنجا که توقف ها تظاهرات متنوعی را نشان می دهند (ممکن است نقاط منفرد یا دنباله هایی حاوی تعداد نقاط مختلف و درجات نویز باشند)، جهت حرکت، یکی دیگر از پارامترهای مهم حرکت، برای شناسایی توقف ها مناسب نیست. در عوض، SOC از آن برای فیلتر کردن توقف های مثبت کاذب ناشی از دورهای کند استفاده می کند.
لازم به ذکر است که برخی از گیرنده های GPS نه تنها موقعیت های دارای مهر زمانی را ثبت می کنند، بلکه اطلاعات اضافی مانند تعداد ماهواره های مشاهده شده و رقیق شدن موقعیت دقیق (PDOP) را نیز ثبت می کنند. هنگامی که چنین اطلاعاتی ثبت می شود، تشخیص توقف های داخلی نسبتاً آسان می شود زیرا هنگام ماندن در داخل خانه، تعداد ماهواره های مشاهده شده کمتر از چهار خواهد بود و PDOP ارزش بالایی خواهد داشت [33 ] . با این حال، این اقدامات اضافی همیشه در مسیرها در دسترس نیستند، که توضیح می‌دهد که چرا ما یک استراتژی خوشه‌بندی و سپس ادغام برای مقابله با چالش تشخیص توقف‌ها، به‌ویژه توقف‌های داخل ساختمان، ایجاد کردیم.

8.2. نتیجه

در این مقاله، ما یک رویکرد جدید برای استخراج توقف از مسیرهای تک با نویز پیشنهاد کردیم. رویکرد پیشنهادی ما از یک روش خوشه‌بندی توالی گرا استفاده می‌کند، که هم مجاورت فضایی و هم تداوم و مدت زمان در طول زمان را هنگام خوشه‌بندی نقاط مسیر در نظر می‌گیرد. سهم اصلی این مقاله به شرح زیر است:
(1) برای دریافت ویژگی های ذاتی یک توقف مسیر، مفهوم توالی هسته معرفی شد. یک دنباله هسته شامل سرعت تک تک نقاط نیست، بلکه صرفاً مستلزم آن است که نقاط یک دنباله مجاورت فضایی داشته باشند و مدت زمان نسبتاً طولانی داشته باشند. علاوه بر این، مفاهیم مورد استفاده برای رشد دنباله‌های اصلی تعریف شد و معیارهایی برای ادغام توالی‌های دسترسی پذیری EPS ارائه شد.
(2) الگوریتمی به نام SOC برای تشخیص توقف های موثر و حذف توقف های مثبت کاذب ایجاد شد. علاوه بر این، فواصل دسترس پذیری نقاط مسیر به صورت گرافیکی با استفاده از یک نمودار دسترس پذیری، که به طور شهودی ساختار خوشه بندی و سطوح یک مسیر را نشان می دهد، نشان داده شد.
(3) ما آزمایش‌های گسترده‌ای را روی چهار مجموعه داده مسیر در دنیای واقعی برای ارزیابی عملکرد SOC انجام دادیم. نتایج نشان می‌دهد که برای استخراج توقف‌ها حتی برای مسیرهایی با سطوح نویز جدی نسبتاً مؤثر است. علاوه بر این، ما دستورالعمل هایی را برای تنظیم پارامترهای ورودی برای الگوریتم SOC به مقادیر مناسب ارائه کردیم.
داده های جغرافیایی در این مقاله مورد استفاده قرار گرفت اما تنها به عملیات ادغام توالی محدود شد. در کار آینده، ما رویکرد خود را با ادغام نه تنها داده‌های جغرافیایی متنی، بلکه اطلاعات مربوط به کاربرد مانند داده‌های شبکه جاده‌ای و داده‌های کاربری زمین بهبود خواهیم داد. ادغام چنین داده هایی می تواند کمک زیادی به به دست آوردن اطلاعات ارزشمندتر در مورد توقف ها کند. علاوه بر این، ما همچنین علاقه مند به گسترش SOC برای بررسی مشکل تشخیص توقف در مقیاس های مختلف جغرافیایی هستیم.

منابع

  1. اسپاکاپیترا، اس. پدر و مادر، سی. دامیانی، م. مکدو، جی. پورتو، اف. وانگنوت، سی. دیدگاه مفهومی در مسیرها. دانستن داده ها مهندس 2008 ، 65 ، 126-146. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  2. Cudré-Mauroux، P. وو، ای. Madden, S. Trajstore: یک سیستم ذخیره سازی تطبیقی ​​برای مجموعه داده های مسیر بسیار بزرگ. در مجموعه مقالات بیست و ششمین کنفرانس بین المللی مهندسی داده، لانگ بیچ، کالیفرنیا، ایالات متحده آمریکا، 1 تا 6 مارس 2010.
  3. روده، RH; Bohlen، MH; ارویگ، م. جنسن، CS; لورنتزوس، NA; اشنایدر، ام. Vazirgiannis، M. پایه ای برای بازنمایی و پرس و جو از اجسام متحرک. ACM Trans. سیستم پایگاه داده 2000 ، 25 ، 1-42. [ Google Scholar ] [ CrossRef ]
  4. حاجی الفتریو، م. کولیوس، جی. باکالوف، پ. تسوتراس، جستارهای الگوی مکانی-زمانی پیچیده VJ. در مجموعه مقالات سی و یکمین کنفرانس بین المللی پایگاه های داده بسیار بزرگ، تروندهایم، نروژ، 30 اوت تا 2 سپتامبر 2005.
  5. Sakr, MA; گوتینگ، پرس و جوهای الگوی فضای زمانی RH. GeoInformation 2011 ، 15 ، 497-540. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  6. جیانوتی، اف. نانی، م. پینلی، اف. Pedreschi، D. استخراج الگوی مسیر. در مجموعه مقالات سیزدهمین کنفرانس بین المللی ACM SIGKDD در مورد کشف دانش و داده کاوی، سن خوزه، کالیفرنیا، ایالات متحده آمریکا، 12 تا 15 اوت 2007.
  7. لی، جی جی; هان، جی. Whang، KY خوشه‌بندی مسیر: یک چارچوب پارتیشن و گروهی. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD 2007 در مورد مدیریت داده ها، پکن، چین، 11-14 ژوئن 2007.
  8. یان، ز. چاکرابورتی، دی. پدر و مادر، سی. اسپاکاپیترا، اس. Aberer، K. مسیرهای معنایی: محاسبات داده های تحرک و حاشیه نویسی. ACM Trans. هوشمند سیستم تکنولوژی 2012 ، 9 ، 1-34. [ Google Scholar ] [ CrossRef ]
  9. خو، جی. گوتینگ، RH. یک مدل داده عمومی برای اجسام متحرک GeoInformation 2013 ، 17 ، 125-172. [ Google Scholar ] [ CrossRef ]
  10. Wolf, J. کاربردهای فناوری های جدید در بررسی های سفر. در دسترس آنلاین: http://www.isctsc.cl/archivos/2004/B4%20-%20Resource%20Wolf.pdf (دسترسی در 01 ژوئن 2015).
  11. استر، ام. کریگل، اچ ام. ساندر، جی. Xu, X. یک الگوریتم مبتنی بر چگالی برای کشف خوشه ها در پایگاه داده های فضایی بزرگ با نویز. در مجموعه مقالات دومین کنفرانس بین المللی کشف دانش و داده کاوی، پورتلند، OR، ایالات متحده آمریکا، 2 تا 4 اوت 1996.
  12. آنکرست، م. برونیگ، MM; کریگل، اچ پی؛ Sander, J. OPTICS: نقاط ترتیب برای شناسایی ساختار خوشه بندی. در مجموعه مقالات کنفرانس بین المللی ACM SIGMOD در مدیریت داده ها، فیلادلفیا، PH، ایالات متحده آمریکا، 31 مه تا 3 ژوئن 1999.
  13. بیرانت، دی. Kut, A. ST-DBSCAN: الگوریتمی برای خوشه بندی داده های مکانی-زمانی. دانستن داده ها مهندس 2007 ، 60 ، 208-211. [ Google Scholar ] [ CrossRef ]
  14. کروم، جی. Horvitz، E. Predestination: استنتاج مقاصد از مسیرهای جزئی. در مجموعه مقالات UbiComp 2006: هشتمین کنفرانس بین المللی محاسبات در همه جا، کشور Orange، CA، ایالات متحده آمریکا، 17-21 سپتامبر 2006.
  15. لی، کیو. ژنگ، ی. Xie، X. چن، ی. لیو، دبلیو. Ma, W. شباهت کاربر ماینینگ بر اساس تاریخچه مکان. در مجموعه مقالات کنفرانس ACM Sigspatial on Advanced in Geographical Information Systems، اروین، کالیفرنیا، ایالات متحده آمریکا، 5-7 نوامبر 2008.
  16. روشا، جی. زمان، V. اولیویرا، جی. آلوارس، ال. بوگورنی، وی. Times, V. DB-SMoT: یک روش خوشه بندی مکانی-زمانی مبتنی بر جهت. در مجموعه مقالات کنفرانس سیستم های هوشمند IEEE، لندن، انگلستان، 7 تا 9 ژوئیه 2010.
  17. آلوارس، لو. بوگورنی، وی. کویجپرز، بی. فرناندز، جی. مولانز، بی. Vaisman, A. مدلی برای غنی سازی مسیرها با اطلاعات جغرافیایی معنایی. در مجموعه مقالات پانزدهمین سمپوزیوم بین المللی سالانه ACM در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، WA، ایالات متحده آمریکا، 7-9 نوامبر 2007.
  18. بوچین، م. دریمل، ا. کرولد، ام. Sacristan، V. بخش‌بندی مسیرها: چارچوب و الگوریتم‌هایی با استفاده از معیارهای مکانی-زمانی. جی. اسپات. Inf. علمی 2011 ، 3 ، 33-63. [ Google Scholar ]
  19. جونیور، ا. مورنو، بی. تایمز، وی. متین، س. Cabral, L. GPASP-UTS: الگوریتمی برای تقسیم‌بندی مسیر بدون نظارت. بین المللی جی. جئوگر. Inf. علمی 2015 ، 29 ، 46-68. [ Google Scholar ] [ CrossRef ]
  20. ژنگ، ی. ژانگ، ال. Xie، X. Ma، W. استخراج مکان های جالب و توالی سفر از مسیرهای GPS. در مجموعه مقالات هجدهمین کنفرانس بین المللی وب جهانی، مادرید، اسپانیا، 20-24 آوریل 2009.
  21. کائو، ایکس. کنگ، جی. جنسن، CS استخراج مکان های معنایی قابل توجه از داده های GPS. Proc. VLDB Enddow. 2011 ، 3 ، 1009-1021. [ Google Scholar ] [ CrossRef ]
  22. دوج، اس. ویبی، آر. Lautenschutz، AK به سمت طبقه بندی الگوهای حرکت. Inf. Vis. 2008 ، 7 ، 240-252. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  23. پدر و مادر، سی. اسپاکاپیترا، اس. رنسو، سی. آندرینکو، جی. آندرینکو، ن. بوگورنی، وی. دامیانی، م. گکولالاس-دیوانیس، ع. مکدو، جی. پلکیس، ن. و همکاران مدلسازی و تحلیل مسیرهای معنایی کامپیوتر ACM. Surv. 2012 ، 45 ، 1-32. [ Google Scholar ] [ CrossRef ]
  24. پالما، AT; بوگورنی، وی. کویجپرز، بی. Alvares, LO یک رویکرد مبتنی بر خوشه برای کشف مکان های جالب در مسیرها. در مجموعه مقالات سمپوزیوم ACM 2008 در محاسبات کاربردی، فورتالزا، برزیل، 16 تا 21 مارس 2008.
  25. زیمرمن، ام. کرست، تی. Spiliopoulou، M. یافتن توقف در مسیرهای مستعد خطا در اجسام متحرک با خوشه بندی مبتنی بر زمان. اشتراک. محاسبه کنید. Inf. علمی 2009 ، 53 ، 275-286. [ Google Scholar ]
  26. تران، LH؛ نگوین، QVH؛ انجام، NH; Yan, Z. کشف توقف مستحکم و سلسله مراتبی در مسیرهای پراکنده و متنوع. در دسترس آنلاین: http://infoscience.epfl.ch/record/175473 (در تاریخ 01 فوریه 2016 قابل دسترسی است).
  27. شوسلر، ن. Axhausen، KW پردازش داده های خام از سیستم های موقعیت یابی جهانی بدون اطلاعات اضافی. J. Transp. Res. هیئت 2009 ، 2105 ، 28-36. [ Google Scholar ] [ CrossRef ]
  28. نقشه های گوگل: API های کدگذاری جغرافیایی. در دسترس آنلاین: https://developer.google.com/maps/documentation/geocoding (در 10 ژوئیه 2015 قابل دسترسی است).
  29. نقشه خیابان باز در دسترس آنلاین: http://www.openstreetmap.org (در 03 ژوئن 2015 قابل دسترسی است).
  30. GeoLife: ساخت شبکه های اجتماعی با استفاده از تاریخچه موقعیت مکانی انسان. در دسترس به صورت آنلاین: http://research.microsoft.com/en-us/projects/geolife (دسترسی در 01 ژوئن 2015).
  31. QGIS: یک سیستم اطلاعات جغرافیایی رایگان و منبع باز. در دسترس آنلاین: http://qgis.org/en/site (دسترسی در 20 سپتامبر 2015).
  32. Baidu Maps: Geocoding APIS. در دسترس آنلاین: http://developer.baidu.com/map/index.php?title=webapi/guide/webservice-geocoding (در 10 ژوئیه 2015 قابل دسترسی است).
  33. اوگل، جی. گونسلر، آر. باخمن، دبلیو. کوتساک، م. Wolf, J. دقت سیستم موقعیت یابی جهانی برای تعیین پارامترهای عملکرد راننده. ترانسپ Res. ضبط 2002 ، 1818 ، 12-24. [ Google Scholar ] [ CrossRef ]
Ijgi 05 00029 g001 1024
شکل 1. یک مسیر مثال در قالب یک مدل توقف حرکت.
Ijgi 05 00029 g002 1024
شکل 2. دو دنباله اصلی معمولی: ( الف ) یک دنباله هسته که با ضبط مداوم ایجاد می شود. و ( ب ) یک دنباله اصلی ناشی از مکث ضبط.
Ijgi 05 00029 g003 1024
شکل 3. ادغام توالی: ( الف ) یک توالی توقف به خوبی خوشه ای. ( ب ) یک توالی توقف که با معیار 1 ادغام شده است. و ( ج ) یک توالی توقف که توسط معیار 2 ادغام شده است.
Ijgi 05 00029 g004 1024
شکل 4. یک نمودار نمونه دسترسی با توجه به Eps = 20m و Tau = 50s.
Ijgi 05 00029 g005 1024
شکل 5. یک مسیر از مجموعه داده 2 و نمودار دسترسی آن.
Ijgi 05 00029 g006 1024
شکل 6. موارد: ( الف ) توقف مؤثر اقامت کوتاه مدت در داخل خانه، بدون ادغام شناسایی شده است. ( ب ) توقف مجزا برای اقامت طولانی مدت در داخل ساختمان؛ ( ج ) توقف موثر سرگردانی در فضای باز، ادغام شده توسط معیار 1. ( د ) توقف مؤثر تناسب اندام داخل سالن، ادغام شده توسط معیار 2. و ( ه ) توقف مثبت کاذب یک چرخش آهسته در زیر یک راهرو.
جدول
جدول 1. معانی اصطلاحات مربوط به توقف.
جدول
جدول 2. چهار مجموعه داده مسیر آزمایشی.
جدول
جدول 3. سه پارامتر کلیدی SOC.
جدول
جدول 4. SOC در مقابل دو روش پایه در تشخیص توقف.
جدول
جدول 5. تأثیر سه پارامتر کلیدی بر نتایج اجرا.

;کاربردهای GISمقالات

آموزش کاربردی ArcGISالهام ابراهیم زادهکاربرد جی ای اسکاربرد جی ای اس در زمین شناسی

بدون نظر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

همواره حمایت دانشجویان عزیزمان همراه ما بوده و این سببب شده که گامی محکم به‌سوی ایجاد یک مرجع برای آموزش GIS برداریم. با این امید که بتوانیم قدردان حمایت شما بزرگواران باشیم.

  • خانه
  • آموزش
  • فیلم آموزشی
  • تماس با ما
  • درباره ما
  • وبلاگ
  • سمنان /خیابان کاشانی/ساختمان فناوری اطلاعات/پ 8
  • 09120049370