基于LDA和优化蚁群的OD流向时空语义聚类算法

doi:10.12082/dqxxkx.2022.210535

地球信息科学学报 ›› 2022, Vol. 24 ›› Issue (5): 837-850.doi: 10.12082/dqxxkx.2022.210535

• 地球信息科学理论与方法 • 上一篇下一篇

基于LDA和优化蚁群的OD流向时空语义聚类算法

张晗¹^,²^,³(), 邬群勇¹^,²^,³^,^*()

1.福州大学空间数据挖掘与信息共享教育部重点实验室,福州 350108
2.卫星空间信息技术综合应用国家地方联合工程研究中心,福州 350108
3.福州大学数字中国研究院（福建）,福州 350003

收稿日期:2021-09-06 修回日期:2021-11-10 出版日期:2022-05-25 发布日期:2022-07-25
通讯作者: * 邬群勇（1973— ）,男,山东诸城人,博士,研究员,主要从事时空数据挖掘和地理信息服务研究。 E-mail: qywu@fzu.edu.cn
作者简介:张晗（1994— ）,男,福建永安人,硕士生,主要从事时空数据挖掘研究。E-mail: zh_curry@163.com
基金资助:
国家自然科学基金项目(41471333);中央引导地方科技发展专项(2021H0036)

A Spatio-temporal Semantic Clustering Algorithm for OD Flow Direction based on LDA and Ant Colony Optimization

ZHANG Han¹^,²^,³(), WU Qunyong¹^,²^,³^,^*()

1. Key Lab of Spatial Data Mining and Information Sharing of Ministry of Education, Fuzhou University, Fuzhou 350108, China
2. National & Local Joint Engineering Research Center of Satellite Geospatial Information Technology, Fuzhou 350108, China
3. The Academy of Digital China (Fujian), Fuzhou 350003, China

Received:2021-09-06 Revised:2021-11-10 Online:2022-05-25 Published:2022-07-25
Contact: WU Qunyong
Supported by:
National Natural Science Foundation of China(41471333);Central Guided Local Development of Science and Technology Project(2021H0036)

摘要/Abstract

摘要：

针对OD流向聚类中语义信息考虑不足和流向语义提取困难的问题,本文提出了一种基于隐含狄利克雷分布模型（Latent Dirichlet Allocation,LDA）和优化蚁群的OD流向语义聚类算法。算法首先以流向终点的POI类别为词汇构建流向文档,采用LDA主题模型提取流向语义,量化OD流向间的语义相似度,融合时间、空间和语义相似度构建流向时空语义相似度;接着以流向为节点,以流向时空语义相似度为边构建流向图,利用高斯函数映射以及图连通分量,剔除不相似的流向,实现数据精简;之后借鉴了密度峰值聚类算法思想,利用节点的介数中心性优化蚁群初始位置选取;最后基于多路切图准则（Multiway Normalized Cut, MNCUT）强化蚁群搜索的目的性,优化蚁群搜索的聚类效果,实现OD流向的时空语义聚类。以厦门市出租车公开数据集与厦门市高德地图POI数据为例进行分析与验证,结果表明本文基于LDA模型的语义提取方法可以有效提取流向的语义信息,构建有效的流向相似度度量;基于高斯函数和图连通分量特性的映射策略可以有效剔除了流向数据中的噪音,有效节省无向图构建的计算开支,大约节省了88.5%~88.8%的运行时间;基于介数中心性和多路切图准则优化的蚁群搜索聚类算法,可以有效进行流向语义聚类。相比已有方法本文方法能够更好地衡量流向间的语义相似程度,可实现按主题进行聚类划分,划分更加精细,更方便有效地进行流向语义的相关分析。

关键词: OD流向, 地理信息, 数据挖掘, 时空语义聚类, LDA, 流向语义相似度, 蚁群算法, 移动模式

Abstract:

In order to solve the problem that semantic information is not fully considered in existing OD flow clustering algorithms and it is difficult to mine OD flow semantic information, this paper proposes an OD flow clustering algorithm based on the Latent Dirichlet Allocation (LDA) model and ant colony optimization algorithm. Firstly, the LDA Topic model is used to extract OD flows' semantics, and the JS divergence (Jensen-Shannon divergence) is used to quantify the semantic similarity between OD flows. We also propose a spatiotemporal semantic similarity calculation method that is constructed by integrating temporal, spatial, and semantic similarity, which provides data basis for flow clustering. Then, the graph network data structure is constructed according to the spatiotemporal semantic similarity, and the Gaussian function mapping and the connected component of the graph are used to simplify the data and eliminate the noise data. Based on the idea of CFDP algorithm (Clustering by fast search and find of density peaks algorithm), the intermediate centrality of nodes is used to optimize the selection strategy of the initial position of ant colony. Finally, the Multi-path Normalized Cut (MNCUT) graph criterion is used to strengthen the purpose of ant colony search, optimize the clustering effect of ant colony search, and realize the spatiotemporal semantic clustering for OD flow direction. Taking Xiamen taxi open data set and Xiamen map POI data as examples, the proposed method is verified. The experimental results show that: (1) The proposed method can effectively extract the semantic information of flow direction and measure the similarity degree between flow directions more comprehensively compared with the existing methods; (2) The Gaussian function mapping strategy and graph connected component feature are adopted to effectively eliminate the noise in the flow direction data, which saves the computational cost of undirected graph construction effectively by 88.5%~88.8% of the running time; (3) Compared with the existing algorithms, the clustering division of the proposed algorithm is more precise, and the correlation analysis of flow semantics can be carried out conveniently and effectively.

Key words: OD flow, geographic information, data mining, spatiotemporal semantic clustering, LDA, Flow semantic similarity, ant colony algorithm, mobile model

张晗, 邬群勇. 基于LDA和优化蚁群的OD流向时空语义聚类算法[J]. 地球信息科学学报, 2022, 24(5): 837-850.DOI:10.12082/dqxxkx.2022.210535

ZHANG Han, WU Qunyong. A Spatio-temporal Semantic Clustering Algorithm for OD Flow Direction based on LDA and Ant Colony Optimization[J]. Journal of Geo-information Science, 2022, 24(5): 837-850.DOI:10.12082/dqxxkx.2022.210535

图/表 13

图1

表1

图2

图3

算法1 基于LDA和优化蚁群的OD流向时空语义聚类算法
输入：OD流向数据F←{ $f i$ },连通分量划分阈值r,信息素重要性参数 $α$ ,启发函数重要性参数 $β$ 输出：OD流向类簇C={ $c i$ },噪音集合N={ $n i$ }
function LDA_MNCUT_ANT_CLUSTER(G,r,α,β) Step1: //无向图构图阶段,无向图G(V,E),其中V是点集合V ←{ $v i$ },E是边集合E ←{ $e ij$ } for i in F do for j in F do creat $v i, v j, e ij$ add $v i, v j, e ij$ to G Step2://连通分量划分阶段,划分连通分量Graphs{ $g i$ },并简化噪音获得待聚类集合C_Graphs{ $g i$ }
Graphs=divide(G,r)
for $g i$ in Graphs do C_Graphs=classify( $g i$ ) Step3: //对待聚类连通分量进行聚类,计算出初始位置inital,K只蚂蚁搜索求解,最后整合聚类结果 for $g i$ in C_Graphs do while Not_End_Condition do //迭代搜索,直到满足停止条件 K,inital=Initialize( $g i$ ) for k in K do res=Search(k,inital,α,β) Res=Merge(res,C)

图4

表2

图5

图6

图7

图8

图9

图10

参考文献 26

[1]	杨延杰, 尹丹, 刘紫玟, 等. 基于大数据的流空间研究进展[J]. 地理科学进展, 2020, 39(8):1397-1411.
	[ Yang Y, Yin D, Liu Z W, et al. Research progress on the space of flow using big data[J]. Progress in Geography, 2020, 39(8):1397-1411. ] DOI: 10.18306/dlkxjz.2020.08.013 doi: 10.18306/dlkxjz.2020.08.013
[2]	李涛王, 姣娥, 黄洁. 基于腾讯迁徙数据的中国城市群国庆长假城际出行模式与网络特征[J]. 地球信息科学学报, 2020, 22(6):1240-1253. doi: 10.12082/dqxxkx.2020.190686
	[ Li T, Wang J E, Huang J. Research on Travel pattern and network characteristics of inter-city travel in China's urban agglomeration during National Day week based on Tencent Migration data[J]. Journal of Geo-information Science, 2020, 22(6):1240-1253. ] DOI: 10.12082/dqxxkx.2020.190686 doi: 10.12082/dqxxkx.2020.190686
[3]	张政, 陈艳艳, 梁天闻. 基于网约车数据的城市区域出行时空特征识别与预测研究[J]. 交通运输系统工程与信息, 2020, 20(3):89-94.
	[ Zhang Z, Chen Y Y, Liang T W. Regional Travel Demand Mining and Forecasting Using Car-hailing Order Records[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(3):89-94. ] DOI: 10.16097/j.cnki.1009-6744.2020.03.014 doi: 10.16097/j.cnki.1009-6744.2020.03.014
[4]	杨格格, 宋辞, 裴韬, 等. 北京对外交通枢纽乘客OD时空分布特征[J]. 地球信息科学学报, 2016, 18(10):1374-1383. doi: 10.3724/SP.J.1047.2016.01374
	[ Yang G G, Song C, Pei T, et al. 2016. Passengers' OD temporal-spatial distribution characteristics of the external traffic hubs in Beijing[J]. Journal of Geoinformation Science, 2016, 18(10):1374-1383. ] DOI: 10.3724/SP.J.1047.2016.01374 doi: 10.3724/SP.J.1047.2016.01374
[5]	Guo X G, Xu Z J, Zhang J Q, et al. An OD flow clustering method based on vector constraints: A case study for Beijing taxi origin-destination data[J]. ISPRS International Journal of Geo-information, 2020, 9(2):128. DOI: 10.3390/ijgi9020128 doi: 10.3390/ijgi9020128
[6]	Duan L, Xu L D, Guo F, et al. A local-density based spatial clustering algorithm with noise[J]. Information systems (Oxford), 2007, 32(7):978-986. DOI: 10.1016/j.is.2006.10.006 doi: 10.1016/j.is.2006.10.006
[7]	Guo D S, Zhu X, Jin H, et al. Discovering spatial patterns in origin-destination mobility data[J]. Transactions in GIS, 2012, 16(3):411-429. DOI: 10.1111/j.1467-9671.2012.01344.x doi: 10.1111/j.1467-9671.2012.01344.x
[8]	Gao Y Z, Li T, Wang S W, et al. A multidimensional spatial scan statistics approach to movement pattern comparison[J]. International journal of geographical information science : IJGIS, 2018, 32(7):1304-1325. DOI: 10.1080/13658816.2018.1426859 doi: 10.1080/13658816.2018.1426859
[9]	Song C, Pei T, Ma T, et al. Detecting arbitrarily shaped clusters in origin-destination flows using ant colony optimization[J]. International Journal of Geographical Information Science : IJGIS, 2019, 33(1):134-154. DOI: 10.1080/13658816.2018.1516287 doi: 10.1080/13658816.2018.1516287
[10]	项秋亮, 邬群勇, 张良盼. 一种逐级合并OD流向时空联合聚类算法[J]. 地球信息科学学报, 2020, 22(6):1394-1405. doi: 10.12082/dqxxkx.2020.190276
	[ Xiang Q L, Wu Q Y, Zhang L P. An OD flow spatio-temporal joint clustering algorithm based on step-by-step merge strategy[J]. Journal of Geo-information Science, 2020, 22(6):1394-1405. ]
[11]	Xiang Q L, Wu Q Y. Tree-Based and optimum cut-based origin-destination flow clustering[J]. ISPRS international journal of geo-information, 2019, 8(11):477. DOI: 10.3390/ijgi8110477 doi: 10.3390/ijgi8110477
[12]	Chu D, Sheets D A, Zhao Y, et al. Visualizing hidden themes of taxi movement with semantic transformation[A]. 2014 IEEE Pacific Visualization Symposium, 2014.DOI: 10.1109/PacificVis.2014.50 doi: 10.1109/PacificVis.2014.50
[13]	Blei D M, Ng Andrew, Jordan M I. Latent dirichlet allocation[J]. The Journal of Machine Learning Research, 2003, 3(4-5):993-1022.
[14]	Salton G, Wong A, Yang C. Salton G. A vector space model for automatic indexing[J]. Communications of the ACM, 1975, 18(11):613-620. DOI: 10.1145/361219.361220 doi: 10.1145/361219.361220
[15]	陈世莉, 陶海燕, 李旭亮, 等. 基于潜在语义信息的城市功能区识别——广州市浮动车GPS时空数据挖掘[J]. 地理学报, 2016, 71(3):471-483. doi: 10.11821/dlxb201603010
	[ Chen S L, Tao H Y, Li X L, et al. Discovering urban functional regions using latent semantic information: Spatiotemporal data mining of floating cars GPS data of Guangzhou[J]. Acta Geographica Sinica, 2016, 71(3):471-483. ] DOI: 10.11821/dlxb201603010 doi: 10.11821/dlxb201603010
[16]	冷彪, 赵文远. 基于客流数据的区域出行特征聚类[J]. 计算机研究与发展, 2014, 51(12):2653-2662.
	[ Leng B, Zhao W Y. Region ridership characteristic clustering using passenger flow data[J]. Journal of Computer Research and Development, 2014, 51(12):2653-2662. ] DOI: 10.7544/issn1000-1239.2014.20131124 doi: 10.7544/issn1000-1239.2014.20131124
[17]	叶小莺, 万梅, 唐蓉, 等. 基于图聚类与蚁群算法的社交网络聚类算法[J]. 计算机应用研究, 2020, 37(6):1670-1674,1687.
	[ Ye X Y, Wan M, Tang R, et al. Clustering algorithm of social network based on graph clustering and ant colony optimization algorithm[J]. Application Research of Computers, 2020, 37(6):1670-1674,1687. ] DOI: 10.19734/j.issn.1001-3695.2018.12.0881 doi: 10.19734/j.issn.1001-3695.2018.12.0881
[18]	白璐, 赵鑫, 孔钰婷, 等. 谱聚类算法研究综述[J]. 计算机工程与应用, 2021, 57(14):15-26.
	[ Bai L, Zhao X, Kong Y T, et al. Survey of spectral clustering algorithms[J]. Computer Engineering and Applications, 2021, 57(14):15-26. ] DOI: 10.3778/j.issn.1002-8331.2103-0547 doi: 10.3778/j.issn.1002-8331.2103-0547
[19]	张文会, 苏永民, 戴静, 等. 居住区共享停车泊位分配模型[J]. 交通运输系统工程与信息, 2019, 19(1):89-96.
	[ Zhang W H, Su Y M, Dai J, et al. Distributing model For shared parking in the residential zones[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(1):89-96. ] DOI: 10.16097/j.cnki.1009-6744.2019.01.014 doi: 10.16097/j.cnki.1009-6744.2019.01.014
[20]	Von L U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4):395-416. DOI: 10.1007/s11222-007-9033-z doi: 10.1007/s11222-007-9033-z
[21]	Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.DOI: 10.1126/science.1242072 doi: 10.1126/science.1242072 pmid: 24970081
[22]	Hoffman M-D, Blei D-M, Bach F-R. Online learning for latent dirichlet allocation[A]. International Conference on Neural Information Processing Systems Curran Associates Inc, 2010.
[23]	王婷婷, 韩满, 王宇. LDA模型的优化及其主题数量选择研究——以科技文献为例[J]. 数据分析与知识发现, 2018, 2(1):29-40.
	[ Wang T T, Han M, Wang Y. Optimizing LDA model with various topic numbers: Case study of scientific literature[J]. Data Analysis and Knowledge Discovery, 2018, 2(1):29-40. ] DOI: 10.11925/infotech.2096-3467.2017.0715 doi: 10.11925/infotech.2096-3467.2017.0715
[24]	Mimno D M, Wallach H M, Talley E M, et al. Optimizing semantic coherence in topic models[A]. Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, EMNLP 2011, 27-31 July 2011, John McIntyre Conference Centre, Edinburgh, UK, A meeting of SIGDAT, a Special Interest Group of the ACL. Association for Computational Linguistics, 2011.
[25]	Rathore P, Ghafoori Z, Bezdek J C, et al. Approximating dunn's cluster validity indices for partitions of big data[J]. IEEE transactions on cybernetics, 2019, 49(5):1629-1641.DOI: 10.1109/TCYB.2018.2806886 doi: 10.1109/TCYB.2018.2806886 pmid: 29994745
[26]	Guan J Y, Li S, He X X, et al. Fast hierarchical clustering of local density peaks via an association degree transfer method[J]. Neurocomputing (Amsterdam), 2021, 455(3):401-418. DOI: 10.1016/j.neucom.2021.05.071 doi: 10.1016/j.neucom.2021.05.071

主题编号	主题词汇分布	语义解释
Topic0	0.549×"汽车服务" + 0.103×"公司企业" + 0.087×"购物" + 0.062×"美食" + 0.054×"生活服务"	租车购车
Topic1	0.390×"旅游景点" + 0.084×"美食" + 0.065×"购物" + 0.059×"生活服务" + 0.058×"公司企业"	游玩出行
Topic2	0.331×"教育培训" + 0.302×"生活服务" + 0.087×"美食" + 0.081×"交通设施" + 0.076×"购物"	教育培训
Topic3	0.550×"交通设施" + 0.333×"教育培训" + 0.098×"美食" + 0.017×"购物" + 0.002×"生活服务"	交通出行
Topic4	0.568×"公司企业" + 0.074×"购物" + 0.067×"金融" + 0.063×"美食" + 0.050×"生活服务"	工作通勤
Topic5	0.715×"房地产" + 0.091×"交通设施" + 0.075×"美食" + 0.045×"生活服务" + 0.044×"购物"	探亲访友
Topic6	0.430×"购物" + 0.255×"美食" + 0.072×"生活服务" + 0.055×"公司企业" + 0.041×"休闲娱乐"	购物出行
Topic7	0.336×"休闲娱乐" + 0.168×"美食" + 0.164×"酒店" + 0.068×"交通设施" + 0.057×"公司企业"	休闲娱乐
Topic8	0.356×"金融" + 0.123×"美食" + 0.098×"购物" + 0.089×"公司企业" + 0.087×"生活服务"	金融理财
Topic9	0.319×"医疗" + 0.127×"购物" + 0.119×"美食" + 0.077×"金融" + 0.061×"生活服务"	就医出行

序号	基准	LDA	中心性	MNCUT	DVI	CHI	DBI	时间/s
1	√				0.9186E-22	0.13486	2.6478	1747
2	√	√	√	√	1.1598E-22	0.18349	1.7699	1535
3	√		√	√	1.1468E-22	0.18615	1.7817	1517
4	√	√		√	0.9345E-22	0.15876	1.9683	1964
5	√	√	√		1.1198E-22	0.17145	2.1784	1418

基于LDA和优化蚁群的OD流向时空语义聚类算法

A Spatio-temporal Semantic Clustering Algorithm for OD Flow Direction based on LDA and Ant Colony Optimization

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 26

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	魏伟, 丁双莹, 刘方方, 李金铠, 郑鹏. 旅游信息科学：多学科交叉融合背景下的理论与实践探究[J]. 地球信息科学学报, 2023, 25(9): 1747-1764.
[2]	林志坤, 吴小竹. 考虑驾驶员驾驶风格的车辆跟驰模型[J]. 地球信息科学学报, 2023, 25(9): 1798-1812.
[3]	邢子瑶, 董芯蕊, 昝糈莉, 杨帅, 黄梓焓, 刘哲, 张晓东. 融合VGI和遥感等多源数据的洪涝范围提取与模拟方法[J]. 地球信息科学学报, 2023, 25(9): 1869-1881.
[4]	张彤, 刘仁宇, 王培晓, 高楚林, 刘杰, 王望舒. 感知物理先验的机器学习及其在地理空间智能中的研究前景[J]. 地球信息科学学报, 2023, 25(7): 1297-1311.
[5]	刘敬一, 彭举, 唐建波, 胡致远, 郭琦, 姚晨, 陈金勇. 融合多特征的轨迹数据自适应聚类方法[J]. 地球信息科学学报, 2023, 25(7): 1363-1377.
[6]	赵渺希, 陈佳鸿, 师浩辰, 李涛, 李莉婷. 区位推荐算法试用于文本地名的空间网络复现——以《三国志》纪传文本为例[J]. 地球信息科学学报, 2023, 25(7): 1386-1404.
[7]	黄宗财, 陆锋, 仇培元, 彭澎. 网络文本蕴含地理信息质量评估框架[J]. 地球信息科学学报, 2023, 25(6): 1121-1134.
[8]	桂志鹏, 胡晓辉, 刘欣婕, 凌志鹏, 姜屿涵, 吴华意. 顾及地理语义的地图检索意图形式化表达与识别[J]. 地球信息科学学报, 2023, 25(6): 1186-1201.
[9]	陈传明, 龚杉, 杨峰, 肖振兴, 俞庆英. 基于停留区域识别的子轨迹异常检测方法[J]. 地球信息科学学报, 2023, 25(4): 684-697.
[10]	张玲莉, 王丽珍, 杨培忠. 工业污染对癌症影响的挖掘方法：改进的空间同位模式[J]. 地球信息科学学报, 2023, 25(12): 2340-2360.
[11]	王敏璇, 阳璇, 查启航, 孙睿, 任娜. 顾及空间分布的改进薄板样条矢量数据几何精度降低方法[J]. 地球信息科学学报, 2023, 25(11): 2120-2133.
[12]	柯玮文, 吴升, 柯日宏. 基于OD流向语义和时空语义聚类的居民出行特征分析方法[J]. 地球信息科学学报, 2023, 25(11): 2150-2163.
[13]	朱佳波, 王益, 张拾斤, 陈家亮, 杨璐. 基于路径模拟和空间句法的封闭式非门禁居住小区犯罪人逃逸行为研究[J]. 地球信息科学学报, 2023, 25(11): 2178-2190.
[14]	华一新, 赵鑫科, 张江水. 地理信息系统研究新范式[J]. 地球信息科学学报, 2023, 25(1): 15-24.
[15]	伍跃飞, 李建微, 毕胜, 朱馨, 王前锋. 面向山地徒步应急救援路径规划的改进蚁群算法研究[J]. 地球信息科学学报, 2023, 25(1): 90-101.