Clustering Method of Moving Points Based on Density and Directionality

  • Authors

    • Jinman Kim
    • Hyeonsang Hwang
    • EuiChul Lee
    2018-12-13
    https://doi.org/10.14419/ijet.v7i4.39.24384
  • Clustering, density-based spatial clustering of applications with noise (DBSCAN), trajectory, point of interest (POI), global positioning system (GPS).

  • Background/Objectives: Density-based spatial clustering of applications with noise (DBSCAN) is a data-clustering algorithm that applies density-based clustering methods. Because it considers the density only at a single instance, this method is problematic when clusters of points change with time.

    Methods/Statistical analysis: Our method analyzes the "staying time" and "directionality" of the GPS trajectory. As it incorporates directionality and has improvements over a conventional DBSCAN method, it is termed as DBSCAN-D. The "staying time" is the interval between two locations where the GPS data are obtained. The "directionality" is the direction toward the upcoming position relative to the previous location. This is obtained by analyzing the GPS data that are generated sequentially.

    Findings: Because the time series data such as GPS data can effectively utilize the directionality information according to the recorded movements, the proposed DBSCAN-D method is found to be particularly suitable for clustering applications.

    Improvements/Applications: In our work, we have applied open GPS data (Geolife), and confirmed that the proposed method exhibits superior performance compared to the existing DBSCAN method.

     

     

  • References

    1. [1] Mudgil S, Nambula H, Bharathi B. Location Based Services with Location Centric Profiles. International Journal of Electrical and Computer Engineering. 2016 Dec;6(6):3001-5.

      [2] Adams PM, Ashwell GWB, Baxter R. Location-Based Services-an overview of the standards. BT Technology Journal 2003 Jan;21(1):34-43.

      [3] Wikipedia. Point of interest [Internet]. 2018 [updated 2018 Mar 7; cited 2018 Aug 2]. Available from: https://en.wikipedia.org/wiki/Point_of_interest

      [4] Heo YK, Oh JS, Paudel P, Thapa P, Jeon HJ, Jeong MA, et al. Density Based system for Recommendation of Hybrid POI. Proceeding of the Conference of the Institute of Electronics Engineers of Korea. 2015 June:1318-1322. Available from: http://www.dbpia.co.kr/Journal/ArticleDetail/NODE06385314

      [5] Khetarpaul S, Chauhan R, Gupta SK, Subramaniam LV, Nambiar U. Mining GPS data to determine interesting locations. In Proceedings of the 8th International Workshop on Information Integration on the Web: in conjunction with WWW 2011. 2011 Mar:8.

      [6] Dou AJ, Kalogeraki V, Gunopulos D, Mielikinen T, Tuulos V, Foley S, et al. Data clustering on a network of mobile smartphones. 2011 IEEE/IPSJ International Symposium on Applications and the Internet. 2011 Jul:118-127.

      [7] Kirmse A, Udeshi T, Bellver P, Shuma J. Extracting patterns from location history. Proceeding of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2011 Nov:397-400.

      [8] Ester M, Kriegel H, Sander J, Xu X. A density-based algorithm for discovering clusters in large geospatial databases with noise. Proceeding of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). 1996:226-231.

      [9] Lim J, Kook J, Kim J. DBSCAN-D: A Density-Based Clustering Method of Directionality. International Journal of Applied Engineering Research. 2017;12(13):3927-3932.

      [10] Santhisree K, Damodaram A, Appaji SV, NagarjunaDevi D. Web usage data clustering using DBSCAN algorithm and set similarities. 2010 International Conference on Data Storage and Data Engineering. 2010 Feb:220-224. DOI: 10.1109/DSDE.2010.14.

      [11] Schlitter N, Falkowski T, Lässig J. DenGraph-HO: Density-based Hierarchical Community Detection for Explorative Visual Network Analysis. Research and Development in Intelligent Systems XXVIII. 2011 Oct:283-296.

      [12] Kim HS, Lim HS, Yong HS. Design and development of the clustering algorithm considering weight in spatial data mining. Journal of Intelligence and Information Systems. 2002 Dec;8(2):177-187. Available from: http://www.jiisonline.org/

      [13] Kim B. Design and Development of Clustering Algorithm Considering Influences of Spatial Objects. The Journal of the Korea Contents Association. 2006 Dec;6(12):113-120.

      [14] Zheng Y, Xie X, Ma WY. Geolife: A collaborative social networking service among user, location and trajectory. IEEE Data Engineering Bulletin. 2010 June;33(2):32-39.

      [15] Zheng Y, Zhang L, Xie X, Ma WY. Mining interesting locations and travel sequences from GPS trajectories. Proceedings of the 18th international conference on World Wild Web. 2009 Apr:791-800. DOI: 10.1145/1526709.1526816.

      [16] Zheng Y, Li Q, Chen Y, Xie X, Ma WY. Understanding Mobility Based on GPS Data. Proceedings of ACM conference on Ubiquitous Computing. 2008 Sep:312-321. DOI: 10.1145/1409635.1409677.

      [17] Microsoft. GeoLife GPS Trajectories [Internet]. 2012 [updated 2012 Aug 9; cited 2018 Aug 2]. Available from: https://www.microsoft.com/en-us/download/details.aspx?id=52367&from=https%3A%2F%2Fresearch.microsoft.com%2Fen-us%2Fdownloads%2Fb16d359d-d164-469e-9fd4-daa38f2b2e13%2F&751be11f-ede8-5a0c-058c-2ee190a24fa6=True

      [18] Jiang H, Yu Q, Liu C, Zhu Q, Guo L. The Analysis of CRM Customer Information Based on Data Mining. Proceeding of the Ninth International Conference on Natural Computation. 2013 Jul:978-983. DOI: 10.1109/ICNC.2013.6818118.

  • Downloads

  • How to Cite

    Kim, J., Hwang, H., & Lee, E. (2018). Clustering Method of Moving Points Based on Density and Directionality. International Journal of Engineering & Technology, 7(4.39), 594-598. https://doi.org/10.14419/ijet.v7i4.39.24384