·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-DB￾SCAN 对停留点的识别准确率达到 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 卷