ST-CFSFDP:快速搜索密度峰值的时空聚类算法

doi:10.11947/j.AGCS.2019.20180538

测绘学报 ›› 2019, Vol. 48 ›› Issue (11): 1380-1390.doi: 10.11947/j.AGCS.2019.20180538

ST-CFSFDP:快速搜索密度峰值的时空聚类算法

王培晓^1,3, 张恒才^2,3, 王海波⁴, 吴升^1,3

1. 福州大学数字中国研究院(福建), 福建福州 350002;
2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室, 北京 100101;
3. 海西政务大数据应用协同创新中心, 福建福州 350002;
4. 湖北工业大学经济与管理学院, 湖北武汉 430068

收稿日期:2018-11-23 修回日期:2019-04-08 出版日期:2019-11-20 发布日期:2019-11-19
通讯作者: 吴升 E-mail:ws0110@163.com
作者简介:王培晓(1994-),男,硕士生,研究方向为地理信息服务、时空数据挖掘。E-mail:peixiao_wang@163.com
基金资助:
国家重点研发计划（2017YFB0503500）；数字福建建设项目（闽发改网数字函[2016]23号）；国家自然科学基金（41771436）

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

WANG Peixiao^1,3, ZHANG Hengcai^2,3, WANG Haibo⁴, WU Sheng^1,3

1. The Academy of Digital China, Fuzhou University, Fuzhou 350002, China;
2. State Key Lab of Resources and Environmental Information System, IGSNRR, CAS, Beijing 100101, China;
3. Fujian Collaborative Innovation Center for Big Data Applications in Governments, Fuzhou 350002, China;
4. Economic and management school, Hubei University of Technology, Wuhan 430068, China

Received:2018-11-23 Revised:2019-04-08 Online:2019-11-20 Published:2019-11-19
Supported by:
The National Key Research and Development Program of China(No. 2017YFB0503500);The Digital Fujian Program(No. 2016-23);The National Natural Science Foundation of China(No. 41771436)

摘要/Abstract

摘要： 时空聚类算法是地理时空大数据挖掘的基础研究命题。针对传统CFSFDP聚类算法无法应用于时空数据挖掘的问题，本文提出一种时空约束的ST-CFSFDP（spatial-temporal clustering by fast search and find of density peaks）算法。在CFSFDP算法基础上加入时间约束，修改了样本属性值的计算策略，不仅解决了原算法单簇集多密度峰值问题，且可以区分并识别相同位置不同时间的簇集。本文利用模拟时空数据与真实的室内定位轨迹数据进行对比试验。结果表明，该算法在时间阈值90 s、距离阈值5 m的识别正确率高达82.4%，较经典ST-DBCSAN、ST-OPTICS及ST-AGNES聚类算法准确率分别提高了5.2%、4.2%和7.6%。

关键词: 地理时空大数据挖掘, CFSFDP算法, ST-CFSFDP算法, 时空聚类算法

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

中图分类号:

P208

王培晓, 张恒才, 王海波, 吴升. ST-CFSFDP:快速搜索密度峰值的时空聚类算法[J]. 测绘学报, 2019, 48(11): 1380-1390.

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.

参考文献 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.

ST-CFSFDP:快速搜索密度峰值的时空聚类算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 36

相关文章 15

编辑推荐

Metrics

本文评价

[1]	刘经南, 罗亚荣, 郭迟, 高柯夫. PNT智能与智能PNT[J]. 测绘学报, 2022, 51(6): 811-828.
[2]	韩李涛, 周丽娟, 龚城, 张爱国. 顾及步行习惯的室内导航网络及其生成算法[J]. 测绘学报, 2022, 51(5): 729-738.
[3]	方金凤, 孟祥福. 基于LBSN和多图融合的兴趣点推荐[J]. 测绘学报, 2022, 51(5): 739-749.
[4]	张睿卓. 基于多源数据的林区电力走廊安全风险评估方法[J]. 测绘学报, 2022, 51(5): 784-784.
[5]	夏吉喆, 周颖, 李珍, 李帆, 乐阳, 程涛, 李清泉. 城市时空大数据驱动的新型冠状病毒传播风险评估——以粤港澳大湾区为例[J]. 测绘学报, 2020, 49(6): 671-680.
[6]	朱庆, 冯斌, 李茂粟, 陈媚特, 徐肇文, 谢潇, 张叶廷, 刘铭崴, 黄志勤, 冯义从. 面向动态关联数据的高效稀疏图索引方法[J]. 测绘学报, 2020, 49(6): 681-691.
[7]	陆川伟, 孙群, 陈冰, 温伯威, 赵云鹏, 徐立. 车辆轨迹数据的道路学习提取法[J]. 测绘学报, 2020, 49(6): 692-702.
[8]	尹烁, 闫小明, 晏雄锋. 基于特征边重构的建筑物化简方法[J]. 测绘学报, 2020, 49(6): 703-710.
[9]	吴华意, 黄蕊, 游兰, 向隆刚. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11): 1341-1356.
[10]	郭庆胜, 刘洋, 李萌, 程晓茜, 何捷, 王慧慧, 魏智威. 基于网格模型的导航道路图渐进式化简方法[J]. 测绘学报, 2019, 48(11): 1357-1368.
[11]	吴政, 武鹏达, 李成名. 对等网络下自适应层级的矢量数据时空索引构建方法[J]. 测绘学报, 2019, 48(11): 1369-1379.
[12]	万子健, 李连营, 杨敏, 周校东. 车辆轨迹数据提取道路交叉口特征的决策树模型[J]. 测绘学报, 2019, 48(11): 1391-1403.
[13]	胡光辉, 熊礼阳, 汤国安. DEM地表坡向变率的向量几何计算法[J]. 测绘学报, 2019, 48(11): 1404-1414.
[14]	张旭, 郝向阳, 李建胜, 李朋月. 监控视频中动态目标与地理空间信息的融合与可视化方法[J]. 测绘学报, 2019, 48(11): 1415-1423.
[15]	邓晨, 游雄, 张威巍, 智梅霞. 基于2D地图的城市户外ARGIS视觉辅助地理配准技术[J]. 测绘学报, 2019, 48(10): 1305-1319.