Journal of Geospatial Information Technology

fa توسعه یک الگوریتم خوشه بندی مبتنی بر تراکم مکانی و زمانی برای استخراج مکان های توقف از خط سیر کاربر Developing a spatial and temporal density-based clustering algorithm to extract stop locations from the user’s trajectory سیستمهای اطلاعات مکانی (عمومی) GIS پژوهشي Research شناسایی مکانهای توقف در خطوط سیر یک گام اولیه و ضروری در مطالعه اشیاء در حال حرکت است و تأثیر عمدهای در برنامهها و خدمات مکانی دارد. برای استخراج نقاط توقف در این پژوهش از خوشهبندی خط سیر استفاده میشود. الگوریتم خوشهبندی مکانی مبتنی بر تراکم برنامههای کاربردی با نوفه (DBSCAN)، الگوریتم پایه روشهای خوشهبندی مبتنی بر چگالی است که با وجود دارا بودن مزایایی، دارای مشکلاتی نظیر سخت بودن تعیین پارامترهای ورودی، عدم توانایی کشف خوشههای با چگالی متفاوت و عدم توجه به مشکل رفت و برگشت است. در روش پیشنهادی این تحقیق که مبتنی بر چگالی است با استفاده از شاخصهای مکانی و زمانی و استفاده از چندین شعاع همسایگی، به استخراج نقاط توقف پرداخته میشود. حل مشکل رفت و برگشت، استخراج خوشهها با چگالی متفاوت و کاهش میزان وابستگی نتایج به پارامترهای ورودی از مزایای روش پیشنهادی است. به منظور ارزیابی الگوریتم، این روش بر روی دادههای خط سیر تولید شده در شهر اراک و نیز دادههای مربوط به پروژه پژوهش ژئولایف پیادهسازی شد. نتایج اخذ شده با نتایج حاصل از پنج الگوریتم دیگر شامل DBSCANT، ST-DBSCAN، DVBSCAN، VDBSCAN و K میانگین، مورد مقایسه قرار گرفت. در مقایسه روی دادههای خط سیر شهر اراک، مکانهای توقف استخراج شده توسط الگوریتم پیشنهادی و الگوریتمهای ذکر شده به ترتیب 100% ، 25% ، 75% ، 50% ، 75% و %50 به درستی استخراج شدهاند که حاکی از برتری روش توسعه داده شده است. همچنین پس از استخراج نقاط توقف و حرکت، شاخصهایی از دادههای Geolife برای شناسایی روز کاری و غیر کاری (تعطیل) تعیین گردید که با این شاخصها، روش پیشنهادی تا 06/94% موفق عمل کرد. نتایج بیانگر کاهش میزان وابستگی نتایج به پارامترهای ورودی، استخراج نقاط توقف به طور صحیح، کاهش میزان انحراف معیار درون خوشهها و افزایش فاصله مراکز خوشهها میباشد. <div dir="rtl" style="text-align: left;">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 density-based 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, ST-BDSCAN, VDBSCAN, DVBSCAN and K-means. 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 non-working 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. </div> خط سیر, استخراج مکان های توقف, خوشه بندی مکانی-زمانی,DBSCAN Trajectory, Extraction of stop locations, Spatiotemporal clustering, DBSCAN, summer and winter, working and non-working. 105 128 http://jgit.kntu.ac.ir/browse.php?a_code=A-11-101-2&slc_lang=fa&sid=1 Negin Masnabadi نگین مسن آبادی negin.msnabadi@gmail.com 10031947532846008249 10031947532846008249 No Shahid Rajaee University دانشگاه تربیت دبیر شهید رجایی Farhad Hosseinali فرهاد حسینعلی f.hosseinali@sru.ac.ir 10031947532846008250 10031947532846008250 Yes Shahid Rajaee University دانشگاه تربیت دبیر شهید رجایی Zahra Bahramian زهرا بهرامیان zbahramian@ut.ac.ir 10031947532846008251 10031947532846008251 No University of Tehran, College of Engineering پردیس دانشکده های فنی دانشگاه تهران