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

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

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

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.