基于K-means算法的轨迹数据热点挖掘算法  

Track Data Hot Spot Mining Algorithm Based on K-means

作　　者：徐文进[1,2] 管克航 马越 黄海广 XU Wen-jin;GUAN Ke-hang;MA Yue;HUANG Hai-guang(College of Information Science and Technology,Qingdao University of Science&Technology,Qingdao 266061,China;College of Information Science and Engineering,Ocean University of China,Qingdao 266100,China;College of Computer Science and Artificial Intelligence,Wenzhou University,Wenzhou 325000,China)

机构地区：[1]青岛科技大学信息科学技术学院,山东青岛266061 [2]中国海洋大学信息科学与工程学院,山东青岛266100 [3]温州大学计算机与人工智能学院,浙江温州325000

出　　处：《计算机与现代化》2021年第10期23-28,34,共7页Computer and Modernization

基　　金：山东省重点研发计划项目(2018GGX105005);浙江省基础公益研究计划项目(LGN20F020001)。

摘　　要：针对渔船轨迹数据具有时间序列性、数量大的特点,提出一种轨迹热点挖掘算法。该算法克服了K-means算法在渔船轨迹数据上无法捕捉热点分布的缺点。其主要的思想是:首先使用时间维度来处理数据,以置信度和KL散度作为衡量所选取数据的可靠性、正确性依据,从大量的轨迹数据中选取信息含量较高的数据,然后使用K-means聚类算法进行数据的聚类。本文所提出的算法只需要设定显著水平参数a和时间间隔T,算法本身就可通过时间维度处理数据的方法自主完成数据的选择以及置信度、KL散度的计算,并引入聚类有效性度量的方法,使K-means通过自我寻找K值来实现热点挖掘的整个过程。在渔船轨迹数据上进行本文算法与K-means算法的对比实验和数据热力图的参照实验,结果显示本文所提的算法在寻找轨迹数据热点上有优越性和正确性。In view of the characteristics of time series and large quantity of fishing boat trajectory data,this paper proposes a trajectory hot spot mining algorithm,which overcomes the disadvantage that K-means algorithm cannot capture hot spot distribution in fishing boat trajectory data.The main idea is as follows:firstly,time dimension is used to process the data,and based on confidence and KL divergence to measure the reliability and correctness of the selected data,data with high information content is selected from a large number of trajectory data,and then the K-means clustering algorithm is used to cluster the processed data.The algorithm proposed in this paper only needs to set the significant level parameter a and time interval T,the algorithm itself can independently complete the data selection and the calculation of the confidence,KL divergence by using the method of time dimension data processing,and the clustering validity measure method is introduced to realize the whole process of hot spot mining by self-searching K value of K-means.The comparison test between the proposed algorithm and K-means algorithm and the reference test of data heat map are carried out on the trajectory data of fishing boats.The results show that the proposed algorithm is superior and correct in finding hot spots of trajectory data.

关 键 词：显著水平a KL散度 时间维度 聚类有效性度量 轨迹热点 

分 类 号：TP306[自动化与计算机技术—计算机系统结构]