Spatial-temporal clustering by fast search and find of density peaks

doi:10.11947/j.AGCS.2019.20180538

Abstract

Abstract: Spatial-temporal clustering algorithm is the basic research topic of geographic spatial-temporal big data mining. In view of the problem that traditional CFSFDP clustering algorithm cannot be applied in spatio-temporal data mining, this paper proposes a spatio-temporal constraint algorithm called ST-CFSFDP(spatial-temporal clustering by fast search and find of density peaks). ST-CFSFDP adds time constraint on the basis of CFSFDP algorithm, and modifies the calculation strategy of sample attribute value, which not only solves the problem of multi-density peak of single cluster set in the original algorithm, but also can distinguish and identify clusters at the same location and at different times. In this paper, the simulated spatiotemporal data and real indoor location trajectory data were used for the experiment, the results show that the ST-CFSFDP algorithm has a recognition rate of 82.4% at a time threshold of 90 s and a distance threshold of 5 m,which is better than the classic ST-DBCSAN, ST-OPTICS and ST-AGNES algorithm increased by 5.2%, 4.2%, and 7.6%, respectively.

Key words: geospatial-temporal big data mining, CFSFDP algorithm, ST-CFSFDP algorithm, spatio-temporal clustering

CLC Number:

P208

WANG Peixiao, ZHANG Hengcai, WANG Haibo, WU Sheng. Spatial-temporal clustering by fast search and find of density peaks[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1380-1390.

References 36

[1]	LIU Hongzhi, WU Zhonghai, ZHANG Xing. CPLR:Collaborative pairwise learning to rank for personalized recommendation[J]. Knowledge-Based Systems, 2018, 148(5):31-40.
[2]	ZHOU Yuwem, HUANG Changqin, HU Qintai, et al. Personalized learning full-path recommendation model based on LSTM neural networks[J]. Information Sciences, 2018, 444(5):135-152.
[3]	XUE Hao, HUYNH D Q, REYNOLDS M. SS-LSTM:ahierarchical LSTM model for pedestrian trajectory prediction[C]//Proceedings of 2018 IEEE Winter Conference on Applications of Computer Vision. Lake Tahoe, NV:IEEE, 2018.
[4]	MENG Fanrong, YUAN Guan, LÜ Shaoqian, et al. An overview on trajectory outlier detection[J]. Artificial Intelligence Review, 2018(10):1-20.
[5]	李志林, 刘启亮, 唐建波. 尺度驱动的空间聚类理论[J]. 测绘学报, 2017, 46(10):1534-1548. DOI:10.11947/j.AGCS.2017.20170275. LI Zhilin, LIU Qiliang, TANG Jianbo. Towardsa scale-driven theoryfor spatialclustering[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1534-1548. DOI:10.11947/j.AGCS.2017.20170275.
[6]	刘启亮, 邓敏, 石岩, 等. 一种基于多约束的空间聚类方法[J]. 测绘学报, 2011, 40(4):509-516. LIU Qiliang, DENG Min, SHI Yan, et al. A novel spatial clustering method based on multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4):509-516.
[7]	牟乃夏, 徐玉静, 张恒才, 等. 移动轨迹聚类方法研究综述[J]. 测绘通报, 2018(1):1-7. DOI:10.13474/j.cnki.11-2246.2018.0001. MOU Naixia, XU Yujing, ZHANG Hengcai, et al. A review of the mobile trajectory clustering methods[J]. Bulletin of Surveying and Mapping, 2018(1):1-7. DOI:10.13474/j.cnki.11-2246.2018.0001.
[8]	牟乃夏, 张恒才, 陈洁, 等. 轨迹数据挖掘城市应用研究综述[J]. 地球信息科学学报, 2015, 17(10):1136-1142. MOU Naixia, ZHANG Hengcai, CHEN Jie, et al. A review on the application research of trajectory data mining in urban cities[J]. Journal of Geo-information Science, 2015, 17(10):1136-1142.
[9]	KALANTARI M, YAGHMAEI B, GHEZELBASH S. Spatio-temporal analysis of crime by developing a method to detect critical distances for the Knox test[J]. International Journal of Geographical Information Science, 2016, 30(11):2302-2320.
[10]	ZALIAPIN I, GABRIELOV A, KEILIS-BOROK V, et al. Clustering analysis of seismicity and aftershock identification[J]. Physical Review Letters, 2008, 101(1):018501.
[11]	WANG Jiao, CHENG Weiming, ZHOU Chenghu, et al. Automatic mapping of lunar landforms using DEM-derived geomorphometric parameters[J]. Journal of Geographical Sciences, 2017, 27(11):1413-1427.
[12]	ZHAO Quanhua, LI Xiaoli, LI Yu, et al. A fuzzy clustering image segmentation algorithm based on hidden Markov random field models and Voronoi tessellation[J]. Pattern Recognition Letters, 2017, 85(2):49-55.
[13]	ACEDO-HERNÁNDEZ R, TORIL M, LUNA-RAMÍREZ S, et al. Automatic clustering algorithms for indoor site selection in LTE[J]. EURASIP Journal on Wireless Communications and Networking, 2016(12):87-98.
[14]	姜波, 叶灵耀, 潘伟丰, 等. 基于需求功能语义的服务聚类方法[J]. 计算机学报, 2018, 41(6):1255-1266. JIANG Bo, YE Lingyao, PAN Weifeng, et al. Service clustering based on the functional semantics of requirements[J]. Chinese Journal of Computers, 2018, 41(6):1255-1266.
[15]	林楠, 尹凌, 赵志远. 基于滑动窗口的手机定位数据个体停留区域识别算法[J]. 地球信息科学学报, 2018, 20(6):762-771. LIN Nan, YIN Ling, ZHAO Zhiyuan. Detecting individual stay areas from mobile phone location data based on moving windows[J]. Journal of Geo-information Science, 2018, 20(6):762-771.
[16]	周世波, 徐维祥. 密度峰值快速搜索与聚类算法及其在船舶位置数据分析中的应用[J]. 仪器仪表学报, 2018, 39(7):152-163. ZHOU Shibo, XU Weixiang. Clustering by fast search and find of density peaks andits application in ship location data analysis[J]. Chinese Journal of Scientific Instrument, 2018, 39(7):152-163.
[17]	MACQUEEN J. Some methods for Classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley, Calif.:University of California Press, 1967:281-297.
[18]	PARK H S, JUN C H. A simple and fast algorithm for K-medoids clustering[J]. Expert Systems with Applications, 2009, 36(2):3336-3341.
[19]	王寅同,王建东,陈海燕,等.一种代表点的近似折半层次聚类算法[J].小型微型计算机系统,2015, 36(2):215-219. WANG Yintong, WANG Jiandong, CHEN Haiyan, et al.An algorithm for approximate binary hierarchical clustering using representatives[J]. Journal of Chinese Computer Systems, 2015, 36(2):215-219.
[20]	ESTIVILL-CASTRO V, LEE I. Multi-level clustering and its visualization for exploratory spatial analysis[J]. Geoinformatica, 2002, 6(2):123-152.
[21]	HANRAHANP, SALZMAN D, AUPPERLE L. A rapid hierarchical radiosity algorithm[C]//Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques.New York, NY:ACM, 1991:197-206.
[22]	ESTER M, KRIEGEL H P, SANDERJ, et al. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland, Oregon:AAAI Press, 1996:226-231.
[23]	唐建波, 邓敏, 刘启亮. 时空事件聚类分析方法研究[J]. 地理信息世界, 2013, 20(1):38-45. TANG Jianbo, DENG Min, LIU Qiliang. On spatio-temporal events clustering methods[J]. Geomatics World, 2013, 20(1):38-45.
[24]	ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS:ordering points to identify the clustering structure[C]//Proceedings of ACM-SIGMOD International Conference on Management of Data. Philadelphia PA:ACM, 1999.
[25]	WANG Wei, YANG Jiong, MUNTZ R R. STING:a statistical information grid approach to spatial data mining[C]//Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann Publishers Inc., 1997:186-195.
[26]	BIRANTD, KUT A. ST-DBSCAN:an algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering, 2007, 60(1):208-221.
[27]	AGRAWAL K P, GARG S, SHARMA S, et al. Development and validation of OPTICS based spatio-temporal clustering technique[J]. Information Sciences, 2016, 369:388-401.
[28]	BAIESI M, PACZUSKI M. Scale-free networks of earthquakes and aftershocks[J]. Physical Review E, 2004, 69(6):066106.
[29]	KULLDORFF M, HEFFERNAN R, HARTMAN J, et al. A space-time permutation scan statistic for disease outbreak detection[J]. PLoS Medicine, 2005, 2(3):e59.
[30]	GAUDART J, POUDIOUGOU B, DICKO A, et al. Space-time clustering of childhood malaria at the household level:a dynamic cohort in a Mali village[J]. BMC Public Health, 2006(6):286-298.
[31]	LIU Qiliang, DENG Min, BI Jiantao, et al. A novel method for discovering spatio-temporal clusters of different sizes, shapes, and densities in the presence of noise[J]. International Journal of Digital Earth, 2014, 7(2):138-157.
[32]	PEI Tao, ZHOU Chenghu, ZHU A'xing, et al. Windowed nearest neighbour method for mining spatio-temporal clusters in the presence of noise[J]. International Journal of Geographical Information Science, 2010, 24(6):925-948.
[33]	LEIVA L A, VIDAL E. Warped k-means:an algorithm to cluster sequentially-distributed data[J]. Information Sciences, 2013(237):196-210.
[34]	王培晓, 王海波, 傅梦颖, 等. 室内用户语义位置预测研究[J]. 地球信息科学学报, 2018, 20(12):1689-1698. WANG Peixiao, WANG Haibo, FU Mengying, et al. Research on semantic location prediction of indoor users[J]. Journal of Geo-information Science, 2018, 20(12):1689-1698.
[35]	RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.
[36]	LI Quannan, ZHENG Yu, XIE Xing, et al. Mining user similarity based on location history[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Irvine, California:ACM, 2008:34.