:: دوره 9، شماره 2 - ( 7-1400 ) ::
جلد 9 شماره 2 صفحات 128-105 برگشت به فهرست نسخه ها
توسعه یک الگوریتم خوشه بندی مبتنی بر تراکم مکانی و زمانی برای استخراج مکان های توقف از خط سیر کاربر
نگین مسن آبادی ، فرهاد حسینعلی* ، زهرا بهرامیان
دانشگاه تربیت دبیر شهید رجایی
چکیده:   (1937 مشاهده)
شناسایی مکان­های توقف در خطوط سیر یک گام اولیه و ضروری در مطالعه اشیاء در حال حرکت است و تأثیر عمده­ای در برنامه­ها و خدمات مکانی دارد. برای استخراج نقاط توقف در این پژوهش از خوشه­بندی خط سیر استفاده می­شود. الگوریتم خوشه­بندی مکانی مبتنی بر تراکم برنامه­های کاربردی با نوفه (DBSCAN)، الگوریتم پایه­ روش­های خوشه­بندی مبتنی بر چگالی است که با وجود دارا بودن مزایایی، دارای مشکلاتی نظیر سخت بودن تعیین پارامتر­های ورودی، عدم توانایی کشف خوشه­های با چگالی متفاوت و عدم توجه به مشکل رفت­ و برگشت است. در روش پیشنهادی این تحقیق که مبتنی بر ­چگالی است با استفاده از شاخص­های مکانی و زمانی و استفاده از چندین شعاع همسایگی، به استخراج نقاط توقف پرداخته می­شود. حل مشکل رفت و برگشت، استخراج خوشه­ها با چگالی متفاوت و کاهش میزان وابستگی نتایج به پارامتر­های ورودی از مزایای روش پیشنهادی است. به منظور ارزیابی الگوریتم، این روش بر روی داده­های خط سیر تولید شده در شهر اراک و نیز داده­های مربوط به پروژه پژوهش ژئولایف پیاده­سازی شد. نتایج اخذ شده با نتایج حاصل از پنج الگوریتم دیگر شامل DBSCANT، ST-DBSCAN، DVBSCAN، VDBSCAN و K میانگین، مورد مقایسه قرار گرفت. در مقایسه روی داده­های خط سیر شهر اراک، مکان­های توقف استخراج شده توسط الگوریتم پیشنهادی و الگوریتم­های ذکر شده به ترتیب 100% ، 25% ، 75% ، 50% ، 75% و %50 به درستی استخراج شده­اند که حاکی از برتری روش توسعه داده شده است. همچنین پس از استخراج نقاط توقف و حرکت، شاخص­هایی از داده­های Geolife برای شناسایی روز کاری و غیر کاری (تعطیل) تعیین گردید که با این شاخص­ها، روش­ پیشنهادی تا 06/94% موفق عمل کرد. نتایج بیانگر کاهش میزان وابستگی نتایج به پارامتر­های ورودی، استخراج نقاط توقف به طور صحیح، کاهش میزان انحراف معیار درون خوشه­ها و افزایش فاصله­ مراکز خوشه­ها می­باشد.
واژه‌های کلیدی: خط سیر، استخراج مکان های توقف، خوشه بندی مکانی-زمانی، DBSCAN
متن کامل [PDF 1960 kb]   (630 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: سیستمهای اطلاعات مکانی (عمومی)
دریافت: 1399/9/21 | پذیرش: 1400/7/24 | انتشار: 1400/7/30
فهرست منابع
1. [1] Q. Yu, Y. Luo, C. Chen, and X. Zheng, "Road Congestion Detection Based on Trajectory Stay-Place Clustering," ISPRS International Journal of Geo-Information, vol. 8, no. 6, pp. 264, 2019. [DOI:10.3390/ijgi8060264]
2. [2] A. MORADI, and M. MALEK, "Design and implementation of a context-aware ubiquitous GIS for tourists Case study: Maragheh City," Geographical data, vol. 27, no. 106 pp. 71-85, 2018 , (Persian).
3. [3] M. Azizkhani, and M. Malek, "Design and Implementation of Location-based Service for Targeted Advertising," Geospatial Engineering Journal, vol. 9, no. 2, pp. 11-16, 08/01, 2018, (Persian).
4. [4] J. Bian, D. Tian, Y. Tang, and D. Tao, "A survey on trajectory clustering analysis," ArXiv, vol. abs/1802.06971, 2018.
5. [5] M. Karimi, M. S. Mesgari, M. A. Sharifi, and P. Pilehforooshha, "Developing a methodology for modelling land use change in space and time," Journal of Spatial Science, vol. 62, no. 2, pp. 261-280, 2017. [DOI:10.1080/14498596.2017.1283253]
6. [6] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise." Presented at the KDD, Oregon ,Portland, 1996.
7. [7] K. N. Ahmed, and T. Razak, "An Overview of Various Improvements of DBSCAN Algorithm in Clustering Spatial Databases," International Journal of Advanced Research in Computer and Communication Engineering, vol. 5, no. 2, pp. 360-363, 2016.
8. [8] A. Moayedi, R. Ali Abbaspour, and A. R. Chehreghan, "Assessment of the Performance of Clustering Algorithms in the Extraction of Similar Trajectories," Journal of Geomatics Science and Technology, vol. 8, no. 4, pp. 135-149, 2019 , (Persian).
9. [9] L. Duan, L. Xu, F. Guo, J. Lee, and B. Yan, "A local-density based spatial clustering algorithm with noise," Information Systems, vol. 32, no. 7, pp. 978-986, 2007. [DOI:10.1016/j.is.2006.10.006]
10. [10] B. Borah, and D. K. Bhattacharyya, "DDSC : A Density Differentiated Spatial Clustering Technique," Journal of Computers, vol. 3, no. 2, pp. 72-79, 2008. [DOI:10.4304/jcp.3.2.72-79]
11. [11] C.-F. Tsai, and C.-T. Wu, "GF-DBSCAN: A new efficient and effective data clustering technique for large databases.", Presented at the MUSP'09: Proceedings of the 9th WSEAS international conference on Multimedia systems & signal processing, Hangzhou, China,2009.
12. [12] H. Peter, and A. A, "An Optimised Density Based Clustering Algorithm," International Journal of Computer Applications, vol. 6, no. 9, pp. 16-19, 2010. [DOI:10.5120/1102-1445]
13. [13] W. Ashour, and S. Sunoallah, "Multi Density DBSCAN," Presented at the Intelligent Data Engineering and Automated Learning , Berlin, Heidelberg, 2011. [DOI:10.1007/978-3-642-23878-9_53]
14. [14] A. Ram, J. Sunita, A. Jalal, and K. Manoj, "A Density Based Algorithm for Discovering Density Varied Clusters in Large Spatial Databases," International Journal of Computer Applications, vol. 3, no. 6, pp. 1-4, 2010. [DOI:10.5120/739-1038]
15. [15] T. Wu, H. Shen, J. Qin, and L. Xiang, "Extracting Stops from Spatio-Temporal Trajectories within Dynamic Contextual Features," Sustainability, vol. 13, no. 2, p. 690, 2021. [DOI:10.3390/su13020690]
16. [16] P. Sun, S. Xia, G. Yuan, and D. Li, "An overview of moving object trajectory compression algorithms," Mathematical Problems in Engineering, vol. 2016, no. 3, pp. 1-13, 2016. [DOI:10.1155/2016/6587309]
17. [17] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, "Trajectory pattern mining," in 13th ACM SIGKDD international conference on Knowledge discovery and data mining, San Jose, California, USA, 2007, pp. 330-339. [DOI:10.1145/1281192.1281230]
18. [18] T. S. Madhulatha, "An overview on clustering methods," IOSR Journal of Engineering, vol. 2, no. 4, pp. 719-725, 2012. [DOI:10.9790/3021-0204719725]
19. [19] G. Yuan, P. Sun, J. Zhao, D. Li, and C. Wang, "A review of moving object trajectory clustering algorithms," Artificial Intelligence Review, vol. 47, no. 1, pp. 123-144, 2017. [DOI:10.1007/s10462-016-9477-7]
20. [20] P.Khalife, S.Niazmardi, and R.A.Abbaspour, "Evaluation of Partitioning Methods for Clustering of Spatial Trajectories " presented at the The 1st National Conference on Data Mining in Earth Sciences, Arak, Iran, 2020, (Persian).
21. [21] M. Syakur, B. Khotimah, E. Rohman, and B. Dwi Satoto, "Integration K-Means Clustering Method and Elbow Method For Identification of The Best Customer Profile Cluster," IOP Conference Series: Materials Science and Engineering, vol. 336, no. 1, pp. 12-17, 2018. [DOI:10.1088/1757-899X/336/1/012017]
22. [22] G.Schoier, G.Borruso, "Individual movements and geographical data mining". In Proceedings of the International Conference on Computational Science and ITS Applications, p. 11, 2011.
23. [23] P. Liu, D. Zhou, and N. Wu, "VDBSCAN: Varied Density Based Spatial Clustering of Applications with Noise," presented at the 2007 International Conference on Service Systems and Service Management, Chengdu, China, 2007. [DOI:10.1109/ICSSSM.2007.4280175]
24. [24] A. Sharma and D. Upadhyay, "VDBSCAN Clustering with Map-Reduce Technique," presented at the Recent Findings in Intelligent Computing Techniques, Singapore, 2018. [DOI:10.1007/978-981-10-8636-6_32]
25. [25] A. W. M. M. Parvez, "Data set property based 'K'in VDBSCAN Clustering Algorithm," World of Computer Science and Information Technology Journal (WCSIT), vol. 2, no. 3, pp. 115-119, 2012.
26. [26] D. Birant and A. Kut, "ST-DBSCAN: An algorithm for clustering spatial-temporal data," Data & knowledge engineering, vol. 60, no. 1, pp. 208-221, 2007. [DOI:10.1016/j.datak.2006.01.013]
27. [27] G. Kautsar and S. Akbar, "Trajectory pattern mining using sequential pattern mining and k-means for predicting future location," in Journal of Physics: Conference Series, Medan, Indonesia, 2017, vol. 801, no. 1, pp. 12-17: IOP Publishing. [DOI:10.1088/1742-6596/801/1/012017]
28. [28] A. Nasiri, S. Azimi, and R. A. Abbaspour, "Data Reduction of Spatio-temporal Trajectories using a Modified Online Compression Algorithm," Engineering Journal of Geospatial Information Technology, vol. 6, no. 3, pp. 23-38, 2018. [DOI:10.29252/jgit.6.3.23]
29. [29] S. Aghel Shahneshin, S. S. Mirvahabi, and R. A. Abbaspor, "An Algorithm for Compression of a Spatio-Temporal Trajectory Preserving Its Semantic Nature," Engineering Journal of Geospatial Information Technology, vol. 3, no. 4, pp. 83-95, 2016, (Persian). [DOI:10.29252/jgit.3.4.83]
30. [30] R. Shourouni and M. Malek, "Route recommendation based on local users' trajectories," (in eng), Journal of Geospatial Information Technology, vol. 4, no. 4, pp. 53-67, 2017, (Persian). [DOI:10.29252/jgit.4.4.53]
31. [31] A. Hosseinpoor Milaghardan, R. A. Abbaspour, and A. Chehreghan, "A Framework for Exploring the Frequent Patterns based on Activities Sequence," Engineering Journal of Geospatial Information Technology, vol. 7, no. 4, pp. 101-114, 2020, (Persian).
32. [32] R. C. Tryon, "Cumulative communality cluster analysis," Educational and Psychological Measurement, vol. 18, no. 1, pp. 3-35, 1958. [DOI:10.1177/001316445801800102]
33. [33] J. Han, J. Pei, and M. Kamber, Data mining: concepts and techniques. Elsevier, 2011.
34. [34] A. K. Jain, "Data clustering: 50 years beyond K-means," Pattern recognition letters, vol. 31, no. 8, pp. 651-666, 2010. [DOI:10.1016/j.patrec.2009.09.011]
35. [35] A. K. Jain, M. N. Murty, and P. J. Flynn, "Data clustering: a review," ACM computing surveys (CSUR), vol. 31, no. 3, pp. 264-323, 1999. [DOI:10.1145/331499.331504]
36. [36] T. Anagnostopoulos, C. B. Anagnostopoulos, S. Hadjiefthymiades, A. Kalousis, and M. Kyriakakos, "Path prediction through data mining," in IEEE International Conference on Pervasive Services, Istanbul, Turkey 2007, pp. 128-135, 2007. [DOI:10.1109/PERSER.2007.4283902]
37. [37] T. Idé and M. Sugiyama, "Trajectory regression on road networks," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 25, no. 1, 2011.
38. [38] L. O. Alvares, V. Bogorny, B. Kuijpers, J. A. F. de Macedo, B. Moelans, and A. Vaisman, "A model for enriching trajectories with semantic geographical information," in Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, Seattle, Washington, pp. 1-8, 2007 [DOI:10.1145/1341012.1341041]
39. [39] J. A. M. Rocha, V. C. Times, G. Oliveira, L. O. Alvares, and V. Bogorny, "DB-SMoT: A direction-based spatio-temporal clustering method," in 2010 5th IEEE international conference intelligent systems, London, UK 2010, pp. 114-119: IEEE,2010. [DOI:10.1109/IS.2010.5548396]
40. [40] D. Ashbrook, and T. Starner, "Using GPS to learn significant locations and predict movement across multiple users," Personal and Ubiquitous Computing, vol. 7, no. 5, pp. 275-286, 2003. [DOI:10.1007/s00779-003-0240-0]
41. [41] J. Krumm and E. Horvitz, "Predestination: Inferring Destinations from Partial Trajectories," in International Conference on Ubiquitous Computing, Berlin, Heidelberg, 2006, pp. 243-260: Springer Berlin Heidelberg. [DOI:10.1007/11853565_15]
42. [42] C. Zhou, D. Frankowski, P. Ludford, S. Shekhar, and L. Terveen, "Discovering personal gazetteers: an interactive clustering approach," in Proceedings of the 12th annual ACM international workshop on Geographic information systems, Washington, DC, USA, pp. 266-273, 2004. [DOI:10.1145/1032222.1032261]
43. [43] J. Tang, L. Liu, and J. Wu, "A trajectory partition method based on combined movement features," Wireless Communications and Mobile Computing, vol. 2019, no. 2, pp. 1-13, 2019. [DOI:10.1155/2019/7803293]
44. [44] Y. Yang, J. Cai, H. Yang, J. Zhang, and X. Zhao, "TAD: A trajectory clustering algorithm based on spatial-temporal density analysis," Expert Systems with Applications, vol. 139, pp. 112846, 2020. [DOI:10.1016/j.eswa.2019.112846]
45. [45] S. Shang, K. Xie, K. Zheng, J. Liu, and J.-R. Wen, "VID Join: Mapping Trajectories to Points of Interest to Support Location-Based Services," Journal of Computer Science and Technology, vol. 30, no. 4, pp. 725-744, 2015. [DOI:10.1007/s11390-015-1557-7]
46. [46] L. Gong, T. Yamamoto, and T. Morikawa, "Identification of activity stop locations in GPS trajectories by DBSCAN-TE method combined with support vector machines," Transportation Research Procedia, vol. 23, no. 3, pp. 146-154, 2018. [DOI:10.1016/j.trpro.2018.10.028]
47. [47] D. S. Lamb, J. Downs, and S. Reader, "Space-time hierarchical clustering for identifying clusters in spatiotemporal point data," ISPRS International Journal of Geo-Information, vol. 9, no. 2, pp. 85-103, 2020. [DOI:10.3390/ijgi9020085]
48. [48] N. Kami, N. Enomoto, T. Baba, and T. Yoshikawa, "Algorithm for Detecting Significant Locations from Raw GPS Data," in International Conference on Discovery Science, Berlin, Heidelberg, pp. 221-235, 2010. [DOI:10.1007/978-3-642-16184-1_16]
49. [49] T. Luo, X. Zheng, G. Xu, K. Fu, and W. Ren, "An Improved DBSCAN Algorithm to Detect Stops in Individual Trajectories," ISPRS International Journal of Geo-Information, vol. 6, no. 3, pp. 63, 2017. [DOI:10.3390/ijgi6030063]
50. [50] A. H. Milaghardan, R. A. Abbaspour, and C. Claramunt, "A Dempster-Shafer based approach to the detection of trajectory stop points," Computers, Environment and Urban Systems, vol. 70, pp. 189-196, 2018. [DOI:10.1016/j.compenvurbsys.2018.03.007]
51. [51] M. Zimmermann, T. Kirste, and M. Spiliopoulou, "Finding Stops in Error-Prone Trajectories of Moving Objects with Time-Based Clustering," in International Conference on Intelligent Interactive Assistance and Mobile Multimedia Computing, Berlin, Heidelberg, pp. 275-286, 2009. [DOI:10.1007/978-3-642-10263-9_24]
52. [52] C. Zhou, D. Frankowski, P. Ludford Finnerty, S. Shekhar, and L. Terveen, "Discovering personally meaningful places: An interactive clustering approach," ACM Transportation Infformation Syststem., vol. 25, no. 3, pp. 12-es, 2007. [DOI:10.1145/1247715.1247718]
53. [53] J. Gudmundsson, M. van Kreveld, and B. Speckmann, "Efficient detection of motion patterns in spatio-temporal data sets," in Proceedings of the 12th annual ACM international workshop on Geographic information systems, Washington, DC, USA, pp. 250-257, 2004. [DOI:10.1145/1032222.1032259]
54. [54] P. Pilehforooshha and M. Karimi, "A local adaptive density-based algorithm for clustering polygonal buildings in urban block polygons," Geocarto International, vol. 35, no. 2, pp. 141-167, 2020. [DOI:10.1080/10106049.2018.1508313]
55. [55] G. Gartner, and W. Hiller, "Impact of Restricted Display Size on Spatial Knowledge Acquisition in the Context of Pedestrian Navigation," Location Based Services and TeleCartography II: From Sensor Fusion to Context Models, G. Gartner and K. Rehrl, eds., pp. 155-166, Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. [DOI:10.1007/978-3-540-87393-8_10]



XML   English Abstract   Print



بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.
دوره 9، شماره 2 - ( 7-1400 ) برگشت به فهرست نسخه ها