基于隐马尔可夫模型的时空轨迹语义匹配方法.pdf

书书书第 卷第期 年月地 理 与 地 理 信 息 科 学 收稿日期：；修回日期：基金项目：国家重点研发计划项目“地理空间知识图谱与知识库引擎”（）；国家自然科学基金项目“基于地理认知的地理场景数据模型与数据组织方法”（）作者简介：刘星雨（），女，硕士研究生，主要研究方向为时空轨迹数据挖掘。：基于隐马尔可夫模型的时空轨迹语义匹配方法刘 星 雨，盛 业 华，秦 佳 睿，刘 青 昊，叶 龙 杰（南京师范大学地理科学学院，江苏 南京 ；南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 ；江苏省地理信息资源开发与利用协同创新中心，江苏 南京 ；香港理工大学土地测量及地理资讯学系，香港 ）摘要：时空轨迹数据关联的语义信息能更好地反映用户行为，对于 密集分布的城市区域，轨迹的语义信息很难根据单一的距离或时间要素进行匹配，该文设计一种基于隐马尔可夫模型（）的时空轨迹语义匹配方法。首先，利用时间阈值与距离阈值提取逗留点，并利用考虑时间的 聚类方法对逗留点进行聚类，得到由抽象停留位置构成的轨迹；然后，结合 数据获得停留位置的候选语义，再以停留位置序列为观测序列，以每个停留位置所关联的候选地点作为隐藏状态建立，并用改进的加权距离的 方法计算的观测概率；最后，解算得到最有可能的访问地点序列作为轨迹的语义匹配结果。该方法不依赖其他外部数据或训练数据，适用于 密集分布的城市区域，基于真实时空轨迹数据集的实验结果验证了该方法的有效性。关键词：时空轨迹；地理语义关联；语义轨迹；隐马尔可夫模型；兴趣点中图分类号：；文献标识码：文章编号：（）引言移动定位、位置服务等技术的发展和移动设备的普及衍生了大量轨迹数据，广泛应用于交通监测、模式挖掘、路径规划、位置预测，等方面。原始时空轨迹数据通常包含用户的行为模式等信息，但该数据更新频率快、数据量大、价值密度低，缺乏访问地点相关的语义信息，不利于用户行为的全面理解。年 等提出用语义信息丰富轨迹数据，此处“语义”指可读的地理标签（如酒店、旅游场所等），能反映用户可能发生的活动。时空轨迹数据与地理信息的集成有助于挖掘用户行为模式，进而提供个性化推荐与出行规划等服务。时空轨迹语义匹配是将原始时空轨迹与一系列访问地点关联的过程，主要包含两个步骤：时空轨迹停留位置提取。例如，等提出一种利用时间和空间阈值识别轨迹停留点的方法；等，通过改进 聚类算法进行轨迹停留点提取；等 提出一种基于三层模型的分层聚类算法，以提取用户访问过的物理场所。上述方法均取得较好效果，然而大多数基于聚类的方法在处理大量轨迹时时间成本过高，并且停留位置识别的准确性在很大程度上取决于参数的选择。等 先用时空阈值提取粗粒度的停留点，但在利用 聚类算法提取细粒度的停留点时忽略了轨迹的时间特征。利用地理空间对象、交通网络或兴趣点（）等数据将语义信息分配给停留位置，。语义信息与停留位置的关联依赖于现有的地理空间数据库，以 数据为例，通过关联时空轨迹与 数据，可以追踪到每个用户有意义的轨迹点和最可能访问的地点信息。等，对轨迹语义标签采用手动输入，人力和时间成本高，不适用于大规模的轨迹数据；等 将停留区域内的所有 作为轨迹的语义，等 选取距离停留中心最近的 点作为轨迹的语义，这些方法简单地考虑距离或拓扑关系，对于 密集的区域并不适用。等 使用反向地理编码技术得到停留位置的街道地址，然而要获得能反映用户具体访问地点的语义，仍需进一步处理；等 提出一种概率生成模型，利用停留位置周围不同类型的 数量构建特征向量，以确定每个停留位置的访问目的；等 利用词频逆文档频率（）为每个停留区构建特征向量，以反映访问类别的不确定性，同时避免了识别访问确切 的困难；等 采用高斯分布函数建立空间概率模型，但需要参考外部数据；还有学者利用隐马尔可夫模型（，）和更可靠的时间、顺序、语义等信息推断最有可能的候选地点序列，对于 密集区域有很好的应用效果，但在模型构建时难以计算观测概率。为解决上述问题，本文设计一种基于的概率模型，并对的观测概率矩阵计算方法进行改进，用于匹配原始时空轨迹的语义信息。方法设计本文方法框架如图所示，包括轨迹停留位置提取和语义匹配两个步骤。首先，基于原始时空轨迹数据提取停留位置分割轨迹；然后，将停留位置与 数据关联得到候选地点，形成带有候选语义标签的停留位置序列；最后，以停留位置序列为观测序列，以每个停留位置所关联的候选地点作为隐藏状态建立，并使用改进的加权距离的 方法计算模型的观测概率矩阵，之后基于动态规划的 算法解算，得到概率最大的地点作为最终的语义匹配结果。图 本文方法框架犉 犻 犵 犉 狉 犪 犿 犲 狑 狅 狉 犽狅 犳 狋 犺 犲狆 狉 狅 狆 狅 狊 犲 犱犿 犲 狋 犺 狅 犱 轨迹停留位置提取时空轨迹犜犼是一系列由 等设备记录的位置点的集合，犜犼狆，狆，狆，狆犻（狓犻，狔犻，狋犻），犼，其中，表示轨迹犜犼中位置点的数量，表示轨迹集合犜的总轨迹数量，狓犻、狔犻分别表示位置点的经度、纬度，狋犻（狋犻狋犻）表示在该位置对应的时间戳。本文提出一种利用时空阈值和聚类的时空轨迹停留位置提取方法（图），该方法包括两个阶段：从原始轨迹中提取逗留点。本文借鉴文献 方法，将一定空间范围 内停留时间超过阈值 的连续轨迹点犜 狆狊，狆狊，狆犲 视为一个逗留点簇，满足 （狆狊，狆犲）且狋犲狋狊 ，逗留点犛（狆，狋 ，狋 ）是逗留点簇的中心点，狆（狓，狔），其中，狓、狔表示逗留点簇的平均经度、纬度，狋 、狋 表示逗留开始、结束的时间。使用考虑时间的 聚类方法对逗留点进行聚类，从中发现图 原始时空轨迹中提取停留位置两阶段模型犉 犻 犵 犜 狑 狅 狊 狋 犪 犵 犲犿 狅 犱 犲 犾 犳 狅 狉 犲 狓 狋 狉 犪 犮 狋 犻 狀 犵 狋 犺 犲 狊 狋 犪 狔狆 犾 犪 犮 犲 犳 狉 狅 犿狋 犺 犲 狉 犪 狑狊 狆 犪 狋 犻 狅 狋 犲 犿 狆 狅 狉 犪 犾 狋 狉 犪 犼 犲 犮 狋 狅 狉 犻 犲 狊停留位置。文献 方法对阈值非常敏感，当逗留范围达到阈值上限后，逗留点会被拆分成多个连续的具有相同语义的点簇，直接用该点簇进行位置匹配，会存在冗余的语义信息。为解决这一问题，本文采用考虑时间的 聚类算法对提取的逗留点进行聚类，以确定最终的停留位置。主要涉及聚类半径和时间阈值两个输入参数，此处用时间阈值替换 中的最小点数，对提取的逗留点进行聚类，记录每个簇的中心点作为最终的停留位置。由于第一阶段的处理大大减少了聚类阶段的数据量，与仅采用聚类的停留提取方法相比，本文方法效率更高。基于的轨迹语义匹配对上一步得到的停留位置设置缓冲区半径狉，落入该缓冲区内的所有 均被视为候选地点，对于 分布密集的区域，一个停留位置可能对应多个 ，导致语义模糊。然而，用户在访问不同类型地点时通常有一定顺序，前一位置的类型有助于当前位置的识别。因此，本文引入进行地点的语义匹配，具体实现过程如图所示。可表示为（犃，犅，），其中，犃为状态转移概率矩阵，犅为观测概率矩阵，为初始状态概率矩阵。本文将停留位置序列视为观测状态，将每个停留位置所关联的候选地点作为隐藏状态建立隐马尔可夫模型。观测序列犞狏，狏，狏狀，狏犻表示一个停留位置，隐藏状态犘（狏犻）狆犻，狆犻，狆犻犿是与每个停留位置关联的候选地点集合，狆犻犼表示与停留位置狏犻相关联的第犼个候选地点。为避免计算页第地 理 与 地 理 信 息 科 学第 卷图 基于隐马尔可夫模型的候选地点匹配过程犉 犻 犵 犆 犪 狀 犱 犻 犱 犪 狋 犲狆 犾 犪 犮 犲犿 犪 狋 犮 犺 犻 狀 犵狆 狉 狅 犮 犲 狊 狊 犫 犪 狊 犲 犱狅 狀犎犕犕犃和的状态数量过多，在计算时使用候选地点的地点类型代替详细的地点名称，候选地点类型的集合犆犮，犮，犮，为地点类型的总数，假设所有待匹配的停留位置中共有狇个候选地点犙狆，狆，狆狇，则每个参数的计算方法如下：）初始状态概率矩阵。初始状态概率矩阵表示模型在初始时刻（即没有任何观测数据时）各状态出现的概率，记为犻，犻为犻类候选地点出现的次数与候选地点总数之比（式（）。初始状态概率向量仅计算一次，在后续计算中保持不变。狆犻犙：犮（狆犻）犮狇，狆犻犙：犮（狆犻）犮狇，狆犻犙：犮（狆犻）犮狇（）式中：犮（狆犻）为候选地点狆犻的地点类型。）状态转移概率矩阵犃。状态转移概率矩阵犃犪犻 犼表示停留位置从一种类型转移到另一种类型的概率矩阵，即第个停留位置的候选地点类型是犮犻、第 个停留位置的候选地点类型是犮犼的数量与犮犻类型候选地点发生转换的总次数犖犮犻之比（式（）。状态转移概率矩阵仅计算一次，在后续计算中保持不变。犪犻 犼狆犙：犮（狆）犮犻 狆 犙：犮（狆）犮犼犖犮犻（）式中：狆犘（狏），狆 犘（狏），犘（狏），犘（狏）犞。）观测概率矩阵犅。观测概率是模型根据当前状态获得各观测值的概率，描述了由隐藏状态生成观测状态的可能性，记为犅犫犼（犽）狀。方法是数据挖掘中常用的统计度量算法，部分学者将该模型应用于轨迹语义的提取，本文利用该方法计算观测概率矩阵。将地点的类型视为单词，将每个停留位置视为文件，当一个停留位置包含多个相同类型的地点时，该类地点对于该停留位置的影响更大，并且特殊的 比常见的 类型可能更具代表性。考虑到距离位置中心点越近的 是该位置语义的可能性越大，对原始 计算公式（式（）增加距离因素，得到改进后的 计算公式（式（）。犳犼狀犼犖 （）犫犼（犽）狀犻 （狇犻，狆 ）（狇犼，狆 ）狀犻 （狇犻，狆 ）犳犼（）式中：犫犼（犽）为某时刻位置类型犮犼停留位置为狏犽的概率，狀犼为在停留位置狏犽中犼类候选 的数量，犖为此停留位置所包含的 总数，为停留位置总数，为包含犼类 的停留位置数量，（狇犻，狆 ）为候选地点狇犻距停留位置中心点狆 的距离。根据上述方法构建后，利用基于动态规划的 算法 解算最可能的隐藏状态序列，即最可能的候选地点访问序列，将该序列作为最终的语义信息与轨迹停留位置相关联。实验结果及分析 实验数据集本文采用微软亚洲研究院收集的 数据集 和从 签到数据中收集的 数据集 对本文方法进行验证。数据集记录了 年月 年月 个用户的 条 轨迹数据，主要分布在北京市，每个轨迹点由经纬度、时间戳等信息组成，主要记录了用户通勤、娱乐和体育活动等轨迹，能反映不同用户在真实地理空间中的活动。该轨迹数据的采集设备和采样率不同，的轨迹是以密集形式记录（如每 或 记录个点），利用该数据可以充分测试停留位置提取方法的稳健性和实用性。数据集包含了 年月 年月 个用户在纽约市的 条签到信息，每条记录包含用户、经纬度、签到地点名称、地点类型以及签到时间。根据用户 提取每个用户每天的签到记录作为一条带有语义信息的轨迹序列，筛选出内大于次的签到，用于语义匹配精度的对比分析。北京市的 数据由高德地图获取，纽约市的 数据由 提供，每条 均包含地点名称、地点类型、经纬度等信息。本文将 地点类型划分为类：服务场所、居住区、办公场所、学校、休闲与娱乐、购物服务、餐饮服务、交通。实验环境及评价指标本文实验环境为 ，（）（）、内存页第第期 刘星雨，盛业华，秦佳睿，等：基于隐马尔可夫模型的时空轨迹语义匹配方法 ，算法实现基于 编译工具，采用 语言。采用精确率（犐 ）、召回率（犐 ）和犉值个指标评估算法性能，公式如下：犐 （）（）犐 （）（）犉（犐 犐 ）（犐 犐 ）（）式中：为将正类预测为正类的数量，为将负类预测为正类的数量，为将正类预测为负类的数量。结果和准确性评估 轨迹停留位置提取实验将第一阶段逗留点提取的空间范围 和停留时间阈值 分别设置为 、，将第二阶段聚类的聚类半径和时间阈值分别设置为 、，在 数据集上共提取 个停留位置，如图所示，越靠近市中心，停留位置越密集。由本文方法与 算法 和 算法 提取停留位置的耗时对比（图）可知，随着轨迹点数量的增加，种算法的耗时均增加，但本文方法增长趋势较平缓，且耗时较少，证明本文方法能在较少的时间内处理大量的数据，效率更高。图 数据集停留位置的空间分布犉 犻 犵 犛 狆 犪 狋 犻 犪 犾 犱 犻 狊 狋 狉 犻 犫 狌 狋 犻 狅 狀 狅