第15卷第1期 智能系统学报 Vol.15 No.1 2020年1月 CAAI Transactions on Intelligent Systems Jan.2020 D0L:10.11992tis.201910026 基于时空约束密度聚类的停留点识别方法 陆剑锋2，郭茂祖2，张显3，赵玲玲4 (1.北京建筑大学电气与信息工程学院，北京100044,2.北京建筑大学建筑大数据智能处理方法研究北京市 重点实验室，北京100044：3.北京建筑大学深部岩土力学与地下工程国家重点实验室，北京100083：4.哈尔滨 工业大学计算机科学与技术学院，黑龙江哈尔滨150001) 摘要：轨迹停留点的识别是轨迹分析、出行活动语义挖掘的关键。针对基于密度聚类的停留点识别方法对时 空信息的表达缺陷，提出新的时空约束停留点识别方法，在密度聚类中引入轨迹的间接时空特征表示，将具有 时空相似性的轨迹点进行聚合；采用与聚类过程相统一的时空特征约束对轨迹簇进行细粒度识别。算法在进 行约束的时候再次利用到聚类时候所用的输入数据特征，特征的充分利用提高了识别的准确率。实验结果验 证了本文方法的有效性。 关键词：停留点识别；密度聚类；时空约束；间接时空特征；时空相似性：聚合；过程统一；细粒度 中图分类号：TP301文献标志码：A 文章编号：1673-4785(2020)01-0059-08 中文引用格式：陆剑锋，郭茂祖，张显，等.基于时空约束密度聚类的停留点识别方法.智能系统学报，2020,15(1)：59-66. 英文引用格式：LU Jianfeng,GUO Maozu,ZHANG Yu,.etal.Stay point recognition method based on spatio-temporal constraint density clusteringJ.CAAI transactions on intelligent systems,2020,15(1):59-66. Stay point recognition method based on spatio-temporal constraint density clustering LU Jianfeng,GUO Maozu,ZHANG Yu,ZHAO Lingling' (1.School of Electrical and Information Engineering,Beijing University of Civil Engineering and Architecture,Beijing 100044, China,2.Beijing Key Laboratory of Intelligent Processing for Building Big Data,Beijing University of Civil Engineering and Archi- tecture,Beijing 100044,China;3.State Key Laboratory for Geomechanics and Deep Underground Engineering,Beijing University of Civil Engineering and Architecture,Beijing 100083,China;4.School of Computer Science and Technology,Harbin Institute of Tech- nology,Harbin 150001.China) Abstract:The recognition of the track stay point is the key to the trajectory analysis and the semantic mining of travel activities.Aiming at the defect of spatio-temporal information based on density clustering,the new method of space- time constrained stay point recognition is proposed.In the density clustering,the indirect spatio-temporal feature repres- entation of the trajectory is introduced,and the trajectory points with spatio-temporal similarity are aggregated.The spa- tio-temporal feature constraint unified with the clustering process is used to fine grain the trajectory cluster.Therefore, when the constraints are used,the input data features used in the clustering are reused,and the full utilization of the fea- tures improves accuracy of the recognition.The experimental results verify effectiveness of the proposed method. Keywords:stay point identification;density clustering;space-time constraint;indirect spatio-temporal feature;spatio- temporal similaily;aggregatied;process uniformity;fine-grained 随着信息技术的发展以及移动通信设备等记 收稿日期：2019-10-31. 基金项目：国家自然科学基金项目(61871020,61502117， 录GPS轨迹数据的工具的普及，更为细致和丰富 61305013):北京市教委科技计划重点项目 (KZ201810016019):北京市属高校高水平创新团队 的出行轨迹信息被大量记录下来。将人们的出 建设计划项目(DHT20190506):国家重点研发计划 行GPS轨迹数据进行采集、处理并根据停留点特 项目(2016YFC0600901). 通信作者：赵玲玲.E-mail:zhaoll(@hit.edu.cn 征深入挖掘轨迹的语义信息，是了解个体轨迹特
DOI: 10.11992/tis.201910026 基于时空约束密度聚类的停留点识别方法 陆剑锋1,2，郭茂祖1,2，张昱1,3，赵玲玲4 （1. 北京建筑大学 电气与信息工程学院，北京 100044; 2. 北京建筑大学 建筑大数据智能处理方法研究北京市 重点实验室，北京 100044; 3. 北京建筑大学 深部岩土力学与地下工程国家重点实验室，北京 100083; 4. 哈尔滨 工业大学 计算机科学与技术学院，黑龙江 哈尔滨 150001） 摘 要：轨迹停留点的识别是轨迹分析、出行活动语义挖掘的关键。针对基于密度聚类的停留点识别方法对时 空信息的表达缺陷，提出新的时空约束停留点识别方法，在密度聚类中引入轨迹的间接时空特征表示，将具有 时空相似性的轨迹点进行聚合；采用与聚类过程相统一的时空特征约束对轨迹簇进行细粒度识别。算法在进 行约束的时候再次利用到聚类时候所用的输入数据特征，特征的充分利用提高了识别的准确率。实验结果验 证了本文方法的有效性。 关键词：停留点识别；密度聚类；时空约束；间接时空特征；时空相似性；聚合；过程统一；细粒度 中图分类号：TP301 文献标志码：A 文章编号：1673−4785(2020)01−0059−08 中文引用格式：陆剑锋, 郭茂祖, 张昱, 等. 基于时空约束密度聚类的停留点识别方法 [J]. 智能系统学报, 2020, 15(1): 59–66. 英文引用格式：LU Jianfeng, GUO Maozu, ZHANG Yu, et al. Stay point recognition method based on spatio-temporal constraint density clustering[J]. CAAI transactions on intelligent systems, 2020, 15(1): 59–66. Stay point recognition method based on spatio-temporal constraint density clustering LU Jianfeng1,2 ，GUO Maozu1,2 ，ZHANG Yu1,3 ，ZHAO Lingling4 (1. School of Electrical and Information Engineering, Beijing University of Civil Engineering and Architecture, Beijing 100044, China; 2. Beijing Key Laboratory of Intelligent Processing for Building Big Data, Beijing University of Civil Engineering and Architecture, Beijing 100044, China; 3. State Key Laboratory for Geomechanics and Deep Underground Engineering, Beijing University of Civil Engineering and Architecture, Beijing 100083, China; 4. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: The recognition of the track stay point is the key to the trajectory analysis and the semantic mining of travel activities. Aiming at the defect of spatio-temporal information based on density clustering, the new method of spacetime constrained stay point recognition is proposed. In the density clustering, the indirect spatio-temporal feature representation of the trajectory is introduced, and the trajectory points with spatio-temporal similarity are aggregated. The spatio-temporal feature constraint unified with the clustering process is used to fine grain the trajectory cluster. Therefore, when the constraints are used, the input data features used in the clustering are reused, and the full utilization of the features improves accuracy of the recognition. The experimental results verify effectiveness of the proposed method. Keywords: stay point identification; density clustering; space-time constraint; indirect spatio-temporal feature; spatiotemporal similaily; aggregatied; process uniformity; fine-grained 随着信息技术的发展以及移动通信设备等记 录 GPS 轨迹数据的工具的普及，更为细致和丰富 的出行轨迹信息被大量记录下来。将人们的出 行 GPS 轨迹数据进行采集、处理并根据停留点特 征深入挖掘轨迹的语义信息，是了解个体轨迹特 收稿日期：2019−10−31. 基金项目：国家自然科学基金项 目 (61871020， 61502117， 61305013) ；北京市教委科技计划重点项 目 (KZ201810016019)；北京市属高校高水平创新团队 建设计划项目 (IDHT20190506)；国家重点研发计划 项目 (2016YFC0600901). 通信作者：赵玲玲. E-mail：zhaoll@hit.edu.cn. 第 15 卷第 1 期 智 能 系 统 学 报 Vol.15 No.1 2020 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2020
·60· 智能系统学报 第15卷 征的重要方式，能够帮助了解人们的出行需求及 据，识别准确率高但抗噪声能力不强。Liao等1) 行为方式，发现城市居民的出行动态，发掘人的 提出的条件随机场算法考虑轨迹的前后信息，能 移动性规律，指导以人为本的城市交通建设，因 够获得重要的出行轨迹数据。该算法考虑的地方 此具有重要的研究意义。但是，GPS轨迹数据的 较多，因此预测结果会产生很多不可预估的问题。 增多、用户的出行方式多样化以及出行目的复杂 基于区分策略方法方面，李毓瑞等提出的 性使得对于出行轨迹数据的识别存在困难，已有 基于密度的停留点识别方法能够很好地找到特定 的识别方法在面对当前轨迹数据的复杂性与多维 的停留点，但是这种方法并不能找到所有的停留 性的时候越来越难以实现既定的目的。因此，需 点。杜润强1提出的停驻点识别方法有效的避 要更为准确的停留点识别方法，以进一步挖掘轨 免了常规停留点的识别错误，使得停驻点的识别 迹数据所蕴含的深层语义信息，为更为丰富的上 更合理，但这种仿真式的识别算法在处理轨迹数 层应用提供支撑。 据噪声上存在一定的问题。HERDER等I6提出 目前，停留点识别的方法分为3类：基于聚类 的旅游推荐算法能够获得用户的访问信息并且及 策略的方法、基于概率策略的方法和基于区分策 时给予用户一定的推荐，但该技术并没有发展成熟。 略的方法。 时空语义1为停留点的识别提供了新的思 基于聚类策略的方法方面，吕志娟山提出的 路，但是，现有的基于时空语义的轨迹点识别方 个人轨迹模式挖掘算法能够获得细腻的轨迹数据 法以经纬度加上时间戳直接进行聚类分段，聚类 信息，但是这要花费更多的时间，并且还会引入 后的轨迹段虽然考虑了时间的特征，但是时间戳 更高比例的噪声。Jiang等)提出的两步法能够 的差异导致轨迹段的细散化，使得轨迹段的特征 有效的聚集并合成接近真实的语义数据，效率高 不明显，不利于后续的识别。 但准确性有待提高。张文元等倒的算法简单高 因此，本文从停留点的识别出发，基于时空约 效，但不适应于密度分布不均的数据集。杨震等 束密度聚类的停留点识别算法对个体出行轨迹进 的方法提高了预测准确率的同时也具有良好的普 行停留点的识别。针对方法中采用了轨迹的间接 适性与多步预测性能。石陆魁等提出的基于时 时空表示：两点间的距离和平均速度，这既保留 空模式的轨迹数据聚类算法因同时兼顾了轨迹的 了轨迹的时空特征，又减少了轨迹段的分散程 空间和时间特征，因此在轨迹时空聚类中有更好 度，能够保留停留点和移动点的特征差异。在轨 的描述，但因为加人了时间度量使得聚类的效率 迹段的识别阶段，因为考虑了轨迹点的速度和距 有所降低。FuI6等提出的两步聚类算法能够大 离等特征，同时也提出了3种约束方法，使得轨迹 大降低GPS信号丢失和数据漂移的影响，并识别 点的识别更加细腻化，提高了识别性能的同时还 独特的位置。算法的搜索速度快但不是自动的， 能够挖掘更多更深层次的轨迹信息。 并且需要一些先验参数。Xiang等提出的基于 序列方式的聚类算法考虑了轨迹的连续性和持续 1基于DBSCAN算法的停留点识别方法 时间，聚类抗噪声能力强，但仅限序列合并数据。 此外，Lei Gongt81在2015年提出的算法C-DB- 本节对密度聚类算法DBSCAN(density-based SCAN对停留点的识别准确率达到90%，但是算 spatial clustering of applications with noise)进行介 法的约束条件方向变化约束存在极大缺陷，即可 绍，在DBSCAN算法的基础上详细说明改进的 能适用于识别数据点频率较高的连续GPS轨迹 ST DBSCAN算法，实验将根据ST DBSCAN算 数据，然而只要轨迹点停止或变化较小，算法约 法聚类得到的轨迹段进行约束与识别，最终识别 束条件就无法有效进行识别。Lei Gong在20I8 停留点和移动点。 年的改进算法利用到嫡的原理。因此预测精 1.1 DBSCAN算法 度有一定提升，但是该约束也有一定缺陷，即停 DBSCAN引入了密度可达和密度相连的概 止的轨迹点或者移速较慢的轨迹点不一定是活动 念，将密度大于给定阈值的点作为核心点，所有 点，它们可能是等车或者是交通道路堵塞的点。 相互可达的点作为一个聚类，不属于任何一个类 基于概率策略的方法方面，张鹏提出的数 的点作为噪声数据，因此可以将一个基于密度的 据挖掘算法能够获得一定的用户出行行为特征， 簇看作是密度相连的点的最大集合。算法的优点 但模型的网络资源利用率还需要有效提高。向隆 在于可以识别形状复杂的聚类，不受噪声的干 刚等)提出的核密度算法兼顾停留的识别完整 扰，而且聚类的结果不受数据输入顺序的影响。 性和准确性，可以有效识别复杂多样的轨迹数 缺点是对于定义的参数Eps和MinPts敏感，而且
征的重要方式，能够帮助了解人们的出行需求及 行为方式，发现城市居民的出行动态，发掘人的 移动性规律，指导以人为本的城市交通建设，因 此具有重要的研究意义。但是，GPS 轨迹数据的 增多、用户的出行方式多样化以及出行目的复杂 性使得对于出行轨迹数据的识别存在困难，已有 的识别方法在面对当前轨迹数据的复杂性与多维 性的时候越来越难以实现既定的目的。因此，需 要更为准确的停留点识别方法，以进一步挖掘轨 迹数据所蕴含的深层语义信息，为更为丰富的上 层应用提供支撑。 目前，停留点识别的方法分为 3 类：基于聚类 策略的方法、基于概率策略的方法和基于区分策 略的方法。 基于聚类策略的方法方面，吕志娟[1] 提出的 个人轨迹模式挖掘算法能够获得细腻的轨迹数据 信息，但是这要花费更多的时间，并且还会引入 更高比例的噪声。 Jiang 等 [2] 提出的两步法能够 有效的聚集并合成接近真实的语义数据，效率高 但准确性有待提高。张文元等[3] 的算法简单高 效，但不适应于密度分布不均的数据集。杨震等[4] 的方法提高了预测准确率的同时也具有良好的普 适性与多步预测性能。石陆魁等[5] 提出的基于时 空模式的轨迹数据聚类算法因同时兼顾了轨迹的 空间和时间特征，因此在轨迹时空聚类中有更好 的描述，但因为加入了时间度量使得聚类的效率 有所降低。Fu [6] 等提出的两步聚类算法能够大 大降低 GPS 信号丢失和数据漂移的影响，并识别 独特的位置。算法的搜索速度快但不是自动的， 并且需要一些先验参数。Xiang [7] 等提出的基于 序列方式的聚类算法考虑了轨迹的连续性和持续 时间，聚类抗噪声能力强，但仅限序列合并数据。 此外，Lei Gong[8] 在 2015 年提出的算法 C-DBSCAN 对停留点的识别准确率达到 90%，但是算 法的约束条件方向变化约束存在极大缺陷，即可 能适用于识别数据点频率较高的连续 GPS 轨迹 数据，然而只要轨迹点停止或变化较小，算法约 束条件就无法有效进行识别。Lei Gong 在 2018 年的改进算法利用到熵[10] 的原理。因此预测精 度有一定提升，但是该约束也有一定缺陷，即停 止的轨迹点或者移速较慢的轨迹点不一定是活动 点，它们可能是等车或者是交通道路堵塞的点。 基于概率策略的方法方面，张鹏[11] 提出的数 据挖掘算法能够获得一定的用户出行行为特征， 但模型的网络资源利用率还需要有效提高。向隆 刚等[12] 提出的核密度算法兼顾停留的识别完整 性和准确性，可以有效识别复杂多样的轨迹数 据，识别准确率高但抗噪声能力不强。Liao 等 [13] 提出的条件随机场算法考虑轨迹的前后信息，能 够获得重要的出行轨迹数据。该算法考虑的地方 较多，因此预测结果会产生很多不可预估的问题。 基于区分策略方法方面，李毓瑞等[14] 提出的 基于密度的停留点识别方法能够很好地找到特定 的停留点，但是这种方法并不能找到所有的停留 点。杜润强[15] 提出的停驻点识别方法有效的避 免了常规停留点的识别错误，使得停驻点的识别 更合理，但这种仿真式的识别算法在处理轨迹数 据噪声上存在一定的问题。HERDER 等 [16] 提出 的旅游推荐算法能够获得用户的访问信息并且及 时给予用户一定的推荐，但该技术并没有发展成熟。 时空语义[17-18] 为停留点的识别提供了新的思 路，但是，现有的基于时空语义的轨迹点识别方 法以经纬度加上时间戳直接进行聚类分段，聚类 后的轨迹段虽然考虑了时间的特征，但是时间戳 的差异导致轨迹段的细散化，使得轨迹段的特征 不明显，不利于后续的识别。 因此，本文从停留点的识别出发，基于时空约 束密度聚类的停留点识别算法对个体出行轨迹进 行停留点的识别。针对方法中采用了轨迹的间接 时空表示：两点间的距离和平均速度，这既保留 了轨迹的时空特征，又减少了轨迹段的分散程 度，能够保留停留点和移动点的特征差异。在轨 迹段的识别阶段，因为考虑了轨迹点的速度和距 离等特征，同时也提出了 3 种约束方法，使得轨迹 点的识别更加细腻化，提高了识别性能的同时还 能够挖掘更多更深层次的轨迹信息。 1 基于 DBSCAN 算法的停留点识别方法 本节对密度聚类算法 DBSCAN(density-based spatial clustering of applications with noise) 进行介 绍，在 DBSCAN 算法的基础上详细说明改进的 ST_DBSCAN 算法，实验将根据 ST_DBSCAN 算 法聚类得到的轨迹段进行约束与识别，最终识别 停留点和移动点。 1.1 DBSCAN 算法 DBSCAN 引入了密度可达和密度相连的概 念，将密度大于给定阈值的点作为核心点，所有 相互可达的点作为一个聚类，不属于任何一个类 的点作为噪声数据，因此可以将一个基于密度的 簇看作是密度相连的点的最大集合。算法的优点 在于可以识别形状复杂的聚类，不受噪声的干 扰，而且聚类的结果不受数据输入顺序的影响。 缺点是对于定义的参数 Eps 和 MinPts 敏感，而且 ·60· 智 能 系 统 学 报 第 15 卷
第1期 陆剑锋，等：基于时空约束密度聚类的停留点识别方法 ·61· 通常很难准确的确定该聚类参数，因此不适于高 下一点的距离以及平均速度特征，这比仅考虑点 维数据集。DBSCAN定义如下： 与点之间的空间距离特征，有更好的特征选择。 E邻域：给定对象半径为E内的区域称为该 因此，相对于原始的DBSCAN算法，在特征的种 对象的E邻域。 类上有更多的选择。时空约束的聚类算法公式如下： 核心对象：如果给定对象E邻域内的样本点 C=∑(E,d&E,)&M(p》 数大于等于MinPts,则称该对象为核心对象。 式中：C为改进的密度聚类算法得到的簇，E,为 直接密度可达：对于样本集合D,如果样本 空间邻域，v是输入数据速度，d为输入数据距 点q在p的E邻域内，并且p为核心对象，那么对 离，v和d是经纬度与时间转换后得到的数据； 象g从对象p直接密度可达。 &为逻辑门与，E2为时间邻域；M为聚类点的最少 密度可达：对于样本集合D,给定一串样本 点个数。 点p1P2,…PaP-p1,9FPa,假如对象P:从P-1直接密 1.3基于ST DBSCAN算法的轨迹点聚类 度可达，那么对象q从对象p密度可达。 在传统的轨迹点识别方面，停留点的识别主 密度相连：存在样本集合D中的一点o,如果 要以经纬度加上时间戳直接进行聚类分段，聚类 对象o到对象p和对象q都是密度可达的，那么 后的簇虽然考虑了时间的特征，但是时间戳的差 p和q密度相联。 异导致轨迹段的细散化，使得轨迹段的特征不明 1.2 ST DBSCAN算法 显，不利于后续的识别。因此采用了轨迹的间接 为了表达某些时空序列的时间特征，在DB 时空表示：两点间的距离和平均速度，这既保留 SCAN算法基础上加人了时间维度，让一个点仅 了轨迹的时空特征，又减少了簇的分散程度，所 考虑它设定一定时间长度内的点，因此能够识别 以能够保留停留点和移动点的特征差异。图1 一些来回移动且密度比较大的簇；输入的数据不 根据ST_DBSCAN算法对轨迹点进行聚类分段， 再是经纬度转换的空间距离特征，而是一个点到 最后利用约束条件识别出停留点和移动点。 办公场所 轨迹信息 办公场所 轨迹点 地点 出行方式 提取 提取 家1.2 T提取 办公场所： still 商场 1.2 2.walk 家 2公中 街道路 街道路 1.2,3 商际1、2 S.car 去噪声 6.bus 道、道路 7.train .subwa ST_DBSCAN 公园 聚类分段并识别 公园 图1基于ST DBSCAN算法的停留点识别方法流程 Fig.1 ST_DBSCAN algorithm clusters and identifies track points ST DBSCAN聚类算法描述 N={Wi,N2,…,M,…,Nm,…,Nn} 输入GPS轨迹数据集D,空间领域约束E1, 其中1<m<n,噪声N程碎片化，并且噪声之间的特 时间领域约束E2,聚类点最少点个数M。其中： 征不明显，所以噪声N不参与下一步识别。 D={T,y,d={t1,t2,…,tn),(y,2,…,vn),(d,d2,…,dn)h 1.4 ST DBSCAN算法约束条件 T是时间戳，v是速度，d是距离。 根据上一部分ST DBSCAN聚类算法得到的 输出聚类后得到簇C与噪声N。其中： 簇C,利用恰当的约束条件来识别停留点和移动点。 C={C1,C2,…,Cm}= 约束算法如下： [G,2,…,t),(1,2,…,),(d,d2,…,dl 输入簇C。其中，C={C,C2,…,Cm}。 [t…,t）,(…,y）,(d,…,dyl. 输出停留点序列P,和移动点序列Pm。其 中P={P1,Pa,…,Pm},Pm={Pml,P2,…,Pmn}。 [,…,tn),(ye,…,yn),(d,…,dn)] 约束算法： 并且<k<n。Cn是聚类得到的具有相似特征的簇。 1)判断各簇C~C.是否含有静止的点，没有
通常很难准确的确定该聚类参数，因此不适于高 维数据集。DBSCAN 定义如下： Ε 邻域：给定对象半径为 Ε 内的区域称为该 对象的 Ε 邻域。 核心对象：如果给定对象 Ε 邻域内的样本点 数大于等于 MinPts，则称该对象为核心对象。 直接密度可达：对于样本集合 D，如果样本 点 q 在 p 的 Ε 邻域内，并且 p 为核心对象，那么对 象 q 从对象 p 直接密度可达。 密度可达：对于样本集合 D，给定一串样本 点 p1 ,p2 ,···,pn ,p=p1 ,q=pn，假如对象 pi 从 pi−1 直接密 度可达，那么对象 q 从对象 p 密度可达。 密度相连：存在样本集合 D 中的一点 o，如果 对象 o 到对象 p 和对象 q 都是密度可达的，那么 p 和 q 密度相联。 1.2 ST_DBSCAN 算法 为了表达某些时空序列的时间特征，在 DBSCAN 算法基础上加入了时间维度，让一个点仅 考虑它设定一定时间长度内的点，因此能够识别 一些来回移动且密度比较大的簇；输入的数据不 再是经纬度转换的空间距离特征，而是一个点到 下一点的距离以及平均速度特征，这比仅考虑点 与点之间的空间距离特征，有更好的特征选择。 因此，相对于原始的 DBSCAN 算法，在特征的种 类上有更多的选择。时空约束的聚类算法公式如下： C = ∑n 1 (E1 (v,d)&E2 (t)&M (p)) 式中：C 为改进的密度聚类算法得到的簇，E1 为 空间邻域，v 是输入数据速度，d 为输入数据距 离 ，v 和 d 是经纬度与时间转换后得到的数据； &为逻辑门与，E2 为时间邻域；M 为聚类点的最少 点个数。 1.3 基于 ST_DBSCAN 算法的轨迹点聚类 在传统的轨迹点识别方面，停留点的识别主 要以经纬度加上时间戳直接进行聚类分段，聚类 后的簇虽然考虑了时间的特征，但是时间戳的差 异导致轨迹段的细散化，使得轨迹段的特征不明 显，不利于后续的识别。因此采用了轨迹的间接 时空表示：两点间的距离和平均速度，这既保留 了轨迹的时空特征，又减少了簇的分散程度，所 以能够保留停留点和移动点的特征差异。图 1 根据 ST_DBSCAN 算法对轨迹点进行聚类分段， 最后利用约束条件识别出停留点和移动点。 办公场所 家 商场 提取 提取 提取 轨 迹 点 地点 出行方式 家: 1、2 2、3、4 5、6 7、8 ST_DBSCAN 办公场所: 1、2 公园: 1、2、3 商场: 1、2 街道、道路: 移动点 停留点 时间、 经纬度 轨迹点 去噪声 聚类分段并识别 轨迹信息 街道 路 口 公园 办公场所 家 街道 路 口 公园 1. still 2. walking 商场 3. run 4. bike 5. car 6. bus 7.train 8.subway 图 1 基于 ST_DBSCAN 算法的停留点识别方法流程 Fig. 1 ST_DBSCAN algorithm clusters and identifies track points ST_DBSCAN 聚类算法描述 D = {T, v,d} = {(t1,t2,··· ,tn),(v1, v2,··· , vn),(d1,d2,··· ,dn)} 输入 GPS 轨迹数据集 D，空间领域约束 E1， 时间领域约束 E2，聚类点最少点个数 M。其中： ， T 是时间戳，v 是速度，d 是距离。 输出 聚类后得到簇 C 与噪声 N。其中： C = {C1,C2,··· ,Cn} = [(t1,t2,··· ,ti),(v1, v2,··· , vi),(d1,d2,··· ,di)], [(ti ,··· ,tj ) , ( vi ,··· , vj ) , ( di ,··· ,dj )], . . . [(tk ,··· ,tn),(vk ,··· , vn),(dk ,··· ,dn)] 并且 i<j<k<n。Cn 是聚类得到的具有相似特征的簇。 N = {N1,N2,··· ,Nl ,··· ,Nm,··· ,Nn} 其中 l<m<n，噪声 N 程碎片化，并且噪声之间的特 征不明显，所以噪声 N 不参与下一步识别。 1.4 ST_DBSCAN 算法约束条件 根据上一部分 ST_DBSCAN 聚类算法得到的 簇 C，利用恰当的约束条件来识别停留点和移动点。 约束算法如下： 输入 簇 C。其中，C={C1 ,C2 ,···,Cn}。 输出 停留点序列 Ps 和移动点序列 Pm。其 中 Ps={Ps1 ,Ps2 ,···,Psn}，Pm={Pm1 ,Pm2 ,···,Pmn}。 约束算法： 1）判断各簇 C1~Cn 是否含有静止的点，没有 第 1 期 陆剑锋，等：基于时空约束密度聚类的停留点识别方法 ·61·
·62· 智能系统学报 第15卷 则进行： 算法与约束条件的停留点识别性能，在Win- 2)如果簇C的所有速度特征'，的和的平均 dows7系统下利用Python3.6版本软件编写算法 值"v=4ms大于设定阈值则标记为移动点，不符 和约束条件。实验共测试3种聚类算法：STDB- 合的进行约束1和约束2： SCAN算法、C DBSCAN算法ISI和DBSCAN TE 约束1设置一个速度阈值V,=0.6m/s, 算法。每种方法的输入数据相同，采用均方根 T2为在簇中轨迹点速度特征大于2所占的百 误差(RMSE)来度量算法精度，公式为 分比。 约束2设置一个速度V=1.5ms的阈值，在 RMSE (Xreali-Xpre) 约束1的基础上，并且簇的平均速度小于3的标 实验分3步进行，数据预处理，参数选择以及 记为移动点，其他的标记为停留点。 评估ST DBSCAN算法的性能。 3)有静止的点，则进行约束3： 2.1 数据预处理 约束3计算簇里面速度为0的点的百分比 实验数据来源于Ubicomp2018-SHL挑战赛 D(若百分比D比接近1说明它是越有可能是交通 的华为数据集(Sussex-Huawei locomotion dataset)y 堵塞的点)以及如果簇的D符合并且上一个簇是 用户的出行轨迹可视化图如图2。 移动点，同时上一个簇的点的移动速度大于V= 6ms则标记为移动点。 1.0 4)否则标记为停留点。 0.8 0.6 1.5时间复杂度 0.4 本文算法聚类阶段的时间复杂度是O(n×i), 0.2 subway n是点的个数，i是找出Eps领域中的点所需要的 0.0 -0.2 时间，最大的时间复杂度是O(n):约束阶段的时 6 -0.4 间复杂度是O(m),m是轨迹段个数，j是找出停 50.8 51.0 51.251.451.651.8 lat (N) 留点和移动点的时间，最大的时间复杂度是Om)。 因此本文算法的时间复杂度为O(n2+m),算法最 图2用户出行轨迹可视化 大时间复杂度为O2n)。 Fig.2 Visualization of travel trajectories 2实验结果与分析 表1给出了数据的原始标签类型，本文根据 原始标签的特点进行数据的再次标注，给出2种 为了验证本文提出的基于ST DBSCAN聚类 数据标签：停留点和移动点以及相应的依据。 表1数据的原始标签及新标签标注 Table 1 Original label and new label annotation of data 轨迹点类型 数据（停留点定义为0，移动点为1） 特点 Bike:1 Car:1 两点之间的距离相差较远，两点之间的速度大，点与 非活动移动点 Bus:1 点之间的密度稀疏；若有严重交通堵塞状态，则轨迹 移动点 Train:1 点的状态可能处于停止状态 Subway:1 Car:1(Heavy traffic) 移动停留点 介于非活动移动点之间，点之间的密度小部分集中 Bus:1(Heavy traffic) Run:0 介于移动点和停留移动速度较小 若接下来是移动停留点或是非活动移动点，那么大 Walking;Outside:1 点之间的点 且有规律的点 概率是移动点：若不是则是停留点 Walking:Inside:0 Still;Stand;Outside:0 活动移动点 点的密度集中，但无规律 Still:Stand:Inside:0 停留点 Still:Sit:Outside:0 非移动停留点 点的密度集中且两点之间的速度与距离非常小 Still;Sit;Inside:0
则进行： 2）如果簇 C 的所有速度特征 V1 的和的平均 值 vavg=4 m/s 大于设定阈值则标记为移动点，不符 合的进行约束 1 和约束 2： 约 束 1 设置一个速度阈 值 V2=0.6 m/s， T_2 为在簇中轨迹点速度特征大于 V2 所占的百 分比。 约束 2 设置一个速度 V3=1.5 m/s 的阈值，在 约束 1 的基础上，并且簇的平均速度小于 V3 的标 记为移动点，其他的标记为停留点。 3）有静止的点，则进行约束 3： 约束 3 计算簇里面速度为 0 的点的百分比 D(若百分比 D 比接近 1 说明它是越有可能是交通 堵塞的点) 以及如果簇的 D 符合并且上一个簇是 移动点，同时上一个簇的点的移动速度大于 V4= 6 m/s 则标记为移动点。 4）否则标记为停留点。 1.5 时间复杂度 本文算法聚类阶段的时间复杂度是 O(n×i)， n 是点的个数，i 是找出 Eps 领域中的点所需要的 时间，最大的时间复杂度是 O(n 2 )；约束阶段的时 间复杂度是 O(m×j)，m 是轨迹段个数，j 是找出停 留点和移动点的时间，最大的时间复杂度是 O(m 2 )。 因此本文算法的时间复杂度为 O(n 2 +m 2 )，算法最 大时间复杂度为 O(2n 2 )。 2 实验结果与分析 为了验证本文提出的基于 ST_DBSCAN 聚类 算法与约束条件的停留点识别性能，在 Windows7 系统下利用 Python3.6 版本软件编写算法 和约束条件。实验共测试 3 种聚类算法：ST_DBSCAN 算法、C_DBSCAN 算法[8] 和 DBSCAN_TE 算法[9]。每种方法的输入数据相同，采用均方根 误差 (RMSE) 来度量算法精度，公式为 RMSE = vt 1 N ∑n i=1 ( Xreal,i − Xpre,i )2 实验分 3 步进行，数据预处理，参数选择以及 评估 ST_DBSCAN 算法的性能。 2.1 数据预处理 实验数据来源于 Ubicomp 2018-SHL 挑战赛 的华为数据集 (Sussex-Huawei locomotion dataset) [19] ， 用户的出行轨迹可视化图如图 2。 1.0 0.8 0.6 0.4 0.2 0.0 −0.2 −0.4 lon (E) 50.8 51.0 51.2 lat (N) 51.4 51.6 51.8 null still walking run bike car bus train subway 图 2 用户出行轨迹可视化 Fig. 2 Visualization of travel trajectories 表 1 给出了数据的原始标签类型，本文根据 原始标签的特点进行数据的再次标注，给出 2 种 数据标签：停留点和移动点以及相应的依据。 表 1 数据的原始标签及新标签标注 Table 1 Original label and new label annotation of data 轨迹点类型 数据(停留点定义为0，移动点为1) 特点 移动点 非活动移动点 Bike:1 Car:1 Bus:1 Train:1 Subway:1 两点之间的距离相差较远，两点之间的速度大，点与 点之间的密度稀疏；若有严重交通堵塞状态，则轨迹 点的状态可能处于停止状态 移动停留点 Car:1(Heavy traffic) Bus:1(Heavy traffic) 介于非活动移动点之间，点之间的密度小部分集中 介于移动点和停留 点之间的点 移动速度较小 且有规律的点 Run:0 Walking;Outside:1 Walking;Inside:0 若接下来是移动停留点或是非活动移动点，那么大 概率是移动点；若不是则是停留点 停留点 活动移动点 Still;Stand;Outside：0 Still;Stand;Inside：0 点的密度集中，但无规律 非移动停留点 Still;Sit;Outside：0 Still;Sit;Inside: 0 点的密度集中且两点之间的速度与距离非常小 ·62· 智 能 系 统 学 报 第 15 卷
第1期 陆剑锋，等：基于时空约束密度聚类的停留点识别方法 ·63· 此外，由于数据带有一定噪声，例如经纬度的 如图5，每份数据的识别精度在参数t2的调 漂移，部分轨迹点的标签有一定的缺失。因此， 整下变化都特别大而且识别精度变化差异特别的 对数据进行过滤噪声0处理，如表2。 明显，这说明每个轨迹数据文件因为自身的数据 表2数据标签 特征不一样，因而最佳参数也不一样。因此，本 Table 2 Data labels 文在识别轨迹数据的时候，选用的是各自轨迹数 行动方式 停留点为0：移动点为1速度/ms) 据的最佳参数，而记录数据的时候是记录最优参 数所识别的精度。如图6，在与其他算法对比的 Still,walking intside 0 01.5 时候将选用最优的参数识别的精度进行对比。 Walking outside 0-1.5 1.00 run 0 1.5-4 0.98 1 bike 1 4-6 ￥0.95 -user2/1 car 0或6-25 -user2/ ◆user3/1 bus 0或6-25 0.90 潮 train 1 6-40 0.88 0.86 4 7 subway 6-40 5 6 eps2 此部分的数据标签的特征是按照正常情况下 图3数据识别率与时间邻域eps2的关系曲线 设定的，例如，car与bus因为交通拥堵而导致的 Fig.3 Relationship between data recognition rate and time neighborhood eps2 停留将会出现速度为0的点，即用户在交通道路 上等待的部分将在轨迹段识别里的约束部分进行 1.00 识别。 0.98 -user 2.2 ST DBSCAN算法中的参数选择 ◆-user∠ 基于时空约束的密度聚类算法中，需要选择 user 0.94 -user3/1 合适的参数。空间阈值epsl与MinPts要与对比 userj/ user3/3 0.92 算法保持一致，所以参数选择与对比算法一 样。时间阈值eps2由于考虑的是连续轨迹点临 0.90 0.2 0.30.40.50.6 近的关系，如图3，在eps2=5的时候识别率都达 01 0 到饱和(user是用户，user1、user2、user3是3个用 图4数据识别率与参数D的关系曲线 户，user1/1是第1个用户第1天记录的数据集， Fig.4 Relationship between data recognition rate and user3/3是第3个用户第3天记录的数据集)，因 parameter D 而经过调试选取的时间邻域值eps2为5。D是 1.6 判断一个簇中轨迹点速度为零的百分比，百分 ◆-user1/.1 ◆-User2/1+user3/1 user2/2 user3/2 比越高越能够说明这段簇是因为等车或堵车所 1.4 -user1/3 user2/3 -user3/3 造成的停留，如图4，D在达到0.2之后识别率达 1.2 到饱和，说明数据集里面因为等车或堵车所造 1.0 成的停留并没有对整体识别率产生决定性的影 0.8 响，此外，还有可能是数据集里面根本没有等车 0.6 或堵车所造成的停留。因而经过一段时间的调 0. 0.10.20.30.40.50.60.70.80.91.0 试之后，得到比较优秀的结果的参数是空间域 t 2 epsl=4,时间域eps2=5,MinPts=4,D=0.2。因为实 图5数据识别率与参数t2的关系曲线 验包含9组轨迹数据集，此外，由于still、walking Fig.5 Relationship between data recognition rate and outside和walking inside是本文识别轨迹点的算 parameter t_2 法所关注的重点，因而对于不同的轨迹数据集 2.3 ST-DBSCAN算法性能评估 来说参数t2是不一样的，同时精确度变化也是 为了评估本文方法的性能，选取了同样基于 最大的。 聚类策略的C DBSCAN算法阁以及DBSCAN TE
此外，由于数据带有一定噪声，例如经纬度的 漂移，部分轨迹点的标签有一定的缺失。因此， 对数据进行过滤噪声[20] 处理，如表 2。 表 2 数据标签 Table 2 Data labels 行动方式 停留点为0；移动点为1 速度/(m·s−1) Still, walking intside 0 0~1.5 Walking outside 1 0~1.5 run 0 1.5~4 bike 1 4~6 car 1 0或6~25 bus 1 0或6~25 train 1 6~40 subway 1 6~40 此部分的数据标签的特征是按照正常情况下 设定的，例如，car 与 bus 因为交通拥堵而导致的 停留将会出现速度为 0 的点，即用户在交通道路 上等待的部分将在轨迹段识别里的约束部分进行 识别。 2.2 ST_DBSCAN 算法中的参数选择 基于时空约束的密度聚类算法中，需要选择 合适的参数。空间阈值 eps1 与 MinPts 要与对比 算法保持一致，所以参数选择与对比算法一 样。时间阈值 eps2 由于考虑的是连续轨迹点临 近的关系，如图 3，在 eps2=5 的时候识别率都达 到饱和 (user 是用户，user1、user2、user3 是 3 个用 户 ，user1/1 是第 1 个用户第 1 天记录的数据集， user3/3 是第 3 个用户第 3 天记录的数据集)，因 而经过调试选取的时间邻域值 eps2 为 5。D 是 判断一个簇中轨迹点速度为零的百分比，百分 比越高越能够说明这段簇是因为等车或堵车所 造成的停留，如图 4，D 在达到 0.2 之后识别率达 到饱和，说明数据集里面因为等车或堵车所造 成的停留并没有对整体识别率产生决定性的影 响，此外，还有可能是数据集里面根本没有等车 或堵车所造成的停留。因而经过一段时间的调 试之后，得到比较优秀的结果的参数是空间域 eps1=4，时间域 eps2=5，MinPts=4，D=0.2。因为实 验包含 9 组轨迹数据集，此外，由于 still、walking outside 和 walking inside 是本文识别轨迹点的算 法所关注的重点，因而对于不同的轨迹数据集 来说参数 t_2 是不一样的，同时精确度变化也是 最大的。 如图 5，每份数据的识别精度在参数 t_2 的调 整下变化都特别大而且识别精度变化差异特别的 明显，这说明每个轨迹数据文件因为自身的数据 特征不一样，因而最佳参数也不一样。因此，本 文在识别轨迹数据的时候，选用的是各自轨迹数 据的最佳参数，而记录数据的时候是记录最优参 数所识别的精度。如图 6，在与其他算法对比的 时候将选用最优的参数识别的精度进行对比。 1.00 0.98 0.95 0.94 0.92 0.90 0.88 0.86 2 3 4 eps2 5 6 7 user2/1 user2/2 user2/3 user1/1 user1/2 user1/3 user3/1 user3/2 数据识别率 user3/3 图 3 数据识别率与时间邻域 eps2 的关系曲线 Fig. 3 Relationship between data recognition rate and time neighborhood eps2 1.00 0.98 0.95 0.94 0.92 0.90 0.1 0.2 0.3 0.4 0.5 0.6 user2/1 user2/2 user2/3 user1/1 user1/2 user1/3 user3/1 user3/2 数据识别率 user3/3 D 图 4 数据识别率与参数 D 的关系曲线 Fig. 4 Relationship between data recognition rate and parameter D 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.1 0.2 0.3 0.4 0.5 0.6 t_2 0.7 0.8 0.9 1.0 user2/1 user2/2 user2/3 user1/1 user1/2 user1/3 user3/1 user3/2 user3/3 数据识别率 图 5 数据识别率与参数 t_2 的关系曲线 Fig. 5 Relationship between data recognition rate and parameter t_2 2.3 ST-DBSCAN 算法性能评估 为了评估本文方法的性能，选取了同样基于 聚类策略的 C_DBSCAN 算法[8] 以及 DBSCAN_TE 第 1 期 陆剑锋，等：基于时空约束密度聚类的停留点识别方法 ·63·