Journal of Geospatial Information Technology
مهندسی فناوری اطلاعات مکانی
jgit
Engineering & Technology
http://jgit.kntu.ac.ir
1
admin
2008-9635
8
10.61186/jgit
14
٢۵٣٨-۴١٨X
13
fa
jalali
1400
7
1
gregorian
2021
10
1
9
2
online
1
fulltext
fa
توسعه یک الگوریتم خوشه بندی مبتنی بر تراکم مکانی و زمانی برای استخراج مکان های توقف از خط سیر کاربر
Developing a spatial and temporal density-based clustering algorithm to extract stop locations from the user’s trajectory
سیستمهای اطلاعات مکانی (عمومی)
GIS
پژوهشي
Research
<span style="font-family:B Nazanin;">شناسایی مکان­های توقف در خطوط سیر یک گام اولیه و ضروری در مطالعه اشیاء در حال حرکت است و تأثیر عمده­ای در برنامه­ها و خدمات مکانی دارد. برای استخراج نقاط توقف در این پژوهش از خوشه­بندی خط سیر استفاده می­شود. الگوریتم خوشه­بندی مکانی مبتنی بر تراکم برنامه­های کاربردی با نوفه (</span><em><span dir="LTR"><span style="font-size:8.0pt;">DBSCAN</span></span></em><span style="font-family:B Nazanin;">)، الگوریتم پایه­ روش­های خوشه­بندی مبتنی بر چگالی است که با وجود دارا بودن مزایایی، دارای مشکلاتی نظیر سخت بودن تعیین پارامتر­های ورودی، عدم توانایی کشف خوشه­های با چگالی متفاوت و عدم توجه به مشکل رفت­</span> <span style="font-family:B Nazanin;">و</span> <span style="font-family:B Nazanin;">برگشت است. در روش پیشنهادی این تحقیق که مبتنی بر</span> <span style="font-family:B Nazanin;">­چگالی است</span> <span style="font-family:B Nazanin;">با استفاده از شاخص­های مکانی و زمانی و استفاده از چندین شعاع همسایگی، به استخراج نقاط توقف پرداخته می­شود. حل مشکل رفت و برگشت، استخراج خوشه­ها با چگالی متفاوت و کاهش میزان وابستگی نتایج به پارامتر­های ورودی از مزایای روش پیشنهادی است. به منظور ارزیابی الگوریتم، این روش بر روی داده­های خط سیر تولید شده در شهر اراک و نیز </span><span style="font-family:B Nazanin;">داده­های مربوط به پروژه پژوهش ژئولایف </span><span style="font-family:B Nazanin;">پیاده­سازی شد. نتایج اخذ شده با نتایج حاصل از پنج الگوریتم دیگر</span> <span style="font-family:B Nazanin;">شامل </span><em><span dir="LTR"><span style="font-size:8.0pt;">DBSCANT</span></span></em><span style="font-family:B Nazanin;">، </span><em><span dir="LTR"><span style="font-size:8.0pt;">ST-DBSCAN</span></span></em><span style="font-family:B Nazanin;">، </span><em><span dir="LTR"><span style="font-size:8.0pt;">DVBSCAN</span></span></em><span style="font-family:B Nazanin;">، </span><em><span dir="LTR"><span style="font-size:8.0pt;">VDBSCAN</span></span></em><span style="font-family:B Nazanin;"> و </span><em><span dir="LTR"><span style="font-size:8.0pt;">K</span></span></em> <span style="font-family:B Nazanin;">میانگین،</span> <span style="font-family:B Nazanin;">مورد مقایسه قرار گرفت.</span> <span style="font-family:B Nazanin;">در مقایسه روی داده­های خط سیر شهر اراک، مکان­های توقف استخراج شده توسط الگوریتم پیشنهادی و الگوریتم­های ذکر شده به ترتیب 100% ، 25% ، 75% ، 50% ، 75% و %50 به درستی استخراج شده­اند که حاکی از برتری روش توسعه داده شده است. همچنین</span><span style="font-family:B Nazanin;"> پس از استخراج نقاط توقف و حرکت، شاخص­هایی از داده­های </span><em><span dir="LTR"><span style="font-size:8.0pt;">Geolife</span></span></em><span style="font-family:B Nazanin;"> برای شناسایی روز کاری و</span><span style="font-family:B Nazanin;"> غیر کاری (تعطیل)</span><span style="font-family:B Nazanin;"> تعیین گردید که با این شاخص­ها، روش­ پیشنهادی تا 06<sub>/</sub>94% موفق عمل کرد.</span><span style="font-family:B Nazanin;"> نتایج بیانگر کاهش میزان وابستگی نتایج به پارامتر­های ورودی، استخراج نقاط توقف به طور صحیح، کاهش میزان انحراف معیار درون خوشه­ها و افزایش فاصله­ مراکز خوشه­ها می­باشد. </span><em><span dir="LTR"><span style="font-size:8.0pt;"></span></span></em><span dir="LTR"></span><span dir="LTR"></span><span dir="LTR"></span>
<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.<br>
<span dir="RTL"></span></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
پردیس دانشکده های فنی دانشگاه تهران