توسعه یک الگوریتم خوشه بندی مبتنی بر تراکم مکانی و زمانی برای استخراج مکان های توقف از خط سیر کاربر

شناسایی مکان های توقف در خطوط سیر یک گام اولیه و ضروری در مطالعه اشیاء در حال حرکت است و تاثیر عمده ای در برنامه ها و خدمات مکانی دارد. برای استخراج نقاط توقف در این پژوهش از خوشه بندی خط سیر استفاده می شود. الگوریتم خوشه بندی مکانی مبتنی بر تراکم برنامه های کاربردی با نوفه (dbscan)، الگوریتم پایه روش های خوشه بندی مبتنی بر چگالی است که با وجود دارا بودن مزایایی، دارای مشکلاتی نظیر سخت بودن تعیین پارامتر های ورودی، عدم توانایی کشف خوشه های با چگالی متفاوت و عدم توجه به مشکل رفت و برگشت است. در روش پیشنهادی این تحقیق که مبتنی بر چگالی است با استفاده از شاخص های مکانی و زمانی و استفاده از چندین شعاع همسایگی، به استخراج نقاط توقف پرداخته می شود. حل مشکل رفت و برگشت، استخراج خوشه ها با چگالی متفاوت و کاهش میزان وابستگی نتایج به پارامتر های ورودی از مزایای روش پیشنهادی است. به منظور ارزیابی الگوریتم، این روش بر روی داده های خط سیر تولید شده در شهر اراک و نیز داده های مربوط به پروژه پژوهش ژئولایف پیاده سازی شد. نتایج اخذ شده با نتایج حاصل از پنج الگوریتم دیگر شامل dbscant، stdbscan، dvbscan، vdbscan و k میانگین، مورد مقایسه قرار گرفت. در مقایسه روی داده های خط سیر شهر اراک، مکان های توقف استخراج شده توسط الگوریتم پیشنهادی و الگوریتم های ذکر شده به ترتیب 100% ، 25% ، 75% ، 50% ، 75% و %50 به درستی استخراج شده اند که حاکی از برتری روش توسعه داده شده است. همچنین پس از استخراج نقاط توقف و حرکت، شاخص هایی از داده های geolife برای شناسایی روز کاری و غیر کاری (تعطیل) تعیین گردید که با این شاخص ها، روش پیشنهادی تا 06/94% موفق عمل کرد. نتایج بیانگر کاهش میزان وابستگی نتایج به پارامتر های ورودی، استخراج نقاط توقف به طور صحیح، کاهش میزان انحراف معیار درون خوشه ها و افزایش فاصله مراکز خوشه ها می باشد.

Developing a spatial and temporal density-based clustering algorithm to extract stop locations from the user’s trajectory

Identifying stopping points of trajectories is a preliminary and necessary step in the study of moving objects and has a major impact on spatial plans and services. In this study we use trajectory clustering to extract stopping points. DBSCAN algorithm (spatial clustering based on density of applications with noise) is the basic algorithm of densitybased clustering methods, which despite its advantages has some shortcommings such as difficulty in determining input parameters, inability to detect clusters with different densities and not paying attention to round trip problem. In the proposed method, which is based on density, we use of spatial and temporal indices and several neighborhood radii to extract stop points. Solving the round trip problem, extracting clusters with different densities and reducing the degree of dependence of the results on input parameters are the advantages of the proposed method.In order to evaluate the proposed method, this method was implemented on the data obtained by handheld GPS in Arak city and the data related to the Geolife research project. The obtained results were compared with the results of five other algorithms including DBSCAN, STBDSCAN, VDBSCAN, DVBSCAN and Kmeans. Compared to the manual GPS route data in Arak city, the stop locations extracted by the proposed algorithm and the mentioned algorithms are 100%, 25%, 75%, 50%, 75% and 50%, respectively, which are correctly extracted and show the superiority of the developed method. Also, after extracting the stopping and moving points, indicators from Geolife data were determined to identify working and nonworking days (holidays) with which the proposed method was able to act successfully up to 94.06%.The results show a decrease in the dependence of the results on input parameters, the accurate extraction of stopping points, a reduction in the standard deviation within the clusters, and an increase in the distance between the centers of the clusters.