Abstract: With the development of mobile location technology and the popularity of mobile location devices, analysis of moving object trajectory data has become a hot topic in the field of spatial data mining. Based on the spatial clustering of taxi trajectory data, it can find the hot path and trend of taxi movements. Based on the traditional OPTICS（Ordering Points To Identify the Clustering Structure） algorithm by trajectory data, TR-OPTICS algorithm（Trajectory OPTICS） is proposed according to the characteristics of mass trajectory. This method uses passenger taxi trajectory as the research object, selects the feature points and divides the trajectory by MDL（Minimum Description Length） method, calculates the horizontal distance, vertical distance, angle distance of sub-trajectory to measure the similarity. In the clustering algorithm, it uses outer rectangle as search band of the core-trajectory, redefines the reach-distance and core-distance, and uses adjacency list to reduce the complexity of the algorithm. Through the Nanjing city taxi trajectory analysis, it gets the taxi hot trajectory clusters, and through repeated experiments contrast with the traditional OPTICS algorithm, DBSCAN（Density-Based Spatial Clustering of Applications with Noise） algorithm, this paper’s TR-OPTICS algorithm is better than the other two algorithms, trajectory clustering results are mainly in center road of Nanjing city, such as Central Road, Bridge South Road, Beijing East Road, Zhongshan East Road, Zhongshan North Road, Jianning Road, Ruijin Road, Itakura Street, Maigaoqiao Road. The results show that this paper’s TR-OPTICS algorithm improves the efficiency of the algorithm and improves the accuracy of clustering results.

Key words: Ordering Points To Identify the Clustering Structure（OPTICS） algorithm, trajectory clustering, spatial clustering method

摘要： 随着移动定位技术的发展和移动定位设备普及，移动对象轨迹数据分析逐渐成为空间数据挖掘领域的研究热点。基于出租车GPS轨迹数据进行空间聚类研究可以发现出租车移动的热点路径以及运动趋势。在传统OPTICS（Ordering Points To Identify the Clustering Structure）算法的基础上根据轨迹数据的特征提出了适合海量轨迹空间聚类的TR-OPTICS（Trajectory OPTICS）算法。该方法选取出租车轨迹中的载客轨迹为研究对象，经过轨迹特征点选取后采用MDL（Minimum Description Length）方式进行轨迹的二次划分，通过计算子轨迹间的水平距离、垂直距离、角度距离来度量轨迹的相似性。在聚类算法上采用外包矩形作为核心轨迹的搜索邻域，同时重新定义轨迹核心距离与轨迹可达距离，用邻接表代替空间索引来降低算法的复杂度。通过对南京市出租车载客轨迹的聚类分析，得到了出租车载客热点轨迹簇，并且经过多次实验与传统OPTICS算法、DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法对比，提出的TR-OPTICS算法在算法执行效率上均优于其他两种算法，在聚类结果上该算法可以发现载客子轨迹簇主要集中在市中心的中央路、大桥南路、北京东路、中山东路、中山北路、建宁路、瑞金路、板仓街、迈皋桥等道路，并且聚类效果优于其他两种算法。结果表明，提出的TR-OPTICS算法提高了算法执行效率，同时也提高了聚类结果的准确性。

关键词: OPTICS算法, 轨迹聚类, 空间聚类方法