引用本文

程媛, 迟荣华, 黄少滨, 吕天阳. 基于非参数密度估计的不确定轨迹预测方法. 自动化学报, 2019, 45(4): 787-798. doi: 10.16383/j.aas.2018.c170419

CHENG Yuan, CHI Rong-Hua, HUANG Shao-Bin, LV Tian-Yang. Uncertain Trajectory Prediction Method Using Non-parametric Density Estimation. ACTA AUTOMATICA SINICA, 2019, 45(4): 787-798. doi: 10.16383/j.aas.2018.c170419

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170419

关键词

轨迹预测，不确定性，非参数密度估计，KS检验 

摘要

随着大量移动设备的出现，准确和高效的轨迹预测有助于提高面向位置的应用和服务的质量和水平.针对现有方法对轨迹不确定性缺乏有效建模的问题，提出了基于非参数密度估计的不确定轨迹终点预测方法.在轨迹建模及模型训练阶段，利用非参数估计对起点与终点相同的轨迹构建基于密度分布的不确定轨迹模型；在轨迹预测阶段，将待预测轨迹视为轨迹数据流，并通过KS（Kolmogorov-Smirnov）检验方法与具有相同起点的不确定轨迹模型进行匹配，其中匹配程度最高的不确定轨迹即为预测轨迹.通过真实轨迹数据集上的实验表明，与现有各类主要轨迹预测方法相比，本方法在不同条件下的预测效率与准确性都有较明显优势.

文章导读

当前, 类似手机等智能终端的广泛普及, 使人类传感信息的获取变得更加容易, 而面向这种传感信息的应用和服务则随之快速增长且类型多种多样.其中面向位置的服务在基于终端传感信息的应用中最为热门, 这类服务可实时获取用户的坐标和区域等位置信息.所获取的位置信息的历史数据可用于对用户的移动轨迹进行预测, 而较准确的预测结果能够为用户提供所需的信息和帮助.

较为常见的轨迹预测研究是轨迹序列预测. Song等[1]在预测人类移动轨迹的研究工作中, 通过个体的轨迹信息熵的测量, 量化了人类移动行为的一般性规律, 并得出人的移动行为是可预测的.其他移动轨迹预测方法还包括轨迹频繁模式挖掘[2-4]、基于复杂信息的行为模式挖掘[5-6]和混合方法[7].

由于人的移动行为极其复杂, 可能会受到信号采集、客观环境、主观意图等多种不确定因素的影响, 使得对轨迹序列难以进行较准确的预测.而移动行为复杂多变, 但一般情况下, 人的行为目的性较强, 移动轨迹终点较为明确, 因此移动轨迹预测的另一类研究问题就是移动轨迹的终点预测.

轨迹终点的预测方法一般是将待预测轨迹的数据流与历史轨迹数据进行匹配, 选择并筛选出最为相近的轨迹, 该轨迹的终点即为待预测轨迹的终点, 匹配方法也多基于常见的分类预测模型. De Brébisson等[8]以轨迹的起始坐标和背景等信息作为特征向量训练多层感知的神经网络, 通过匹配训练数据集中的轨迹实现对轨迹终点的预测.对于训练过的相似轨迹, 模型可以较好地预测; 但对于新区域的轨迹, 模型需要新的训练数据集以及新的相关信息; 另外, 网络模型本身难以解释, 使其难以通过调整和控制网络模型适应新的数据, 限制了模型的适用性. Krumm等[9]和Ziebart等[10]利用除轨迹以外的信息进行贝叶斯信念网的训练来预测轨迹的终点. Patterson等[11]也基于贝叶斯模型预测轨迹终点, 但考虑了如行走、乘车之间状态改变等形式的历史轨迹的运动模式信息. Monreale等[12]利用T-pattern决策树对移动轨迹建模, 通过匹配决策树中的路径预测轨迹终点.

随着轨迹预测研究的深入, 轨迹中的不确定性问题也逐渐被发现是限制轨迹预测准确性的重要因素, 现有研究大多从轨迹中位置间转移概率的角度来考虑不确定因素. Ashbrook等[13]在GPS数据上, 结合位置间的转移概率训练Markov模型, 并预测轨迹的终点. Gambs等[14]利用Markov Chains对轨迹位置序列中的兴趣点建模, 通过计算兴趣点间的转移概率预测轨迹的终点.现有研究中利用的Markov和贝叶斯模型均可以描述位置之间的转移概率, 但其模型属于离散类型, 对于历史信息中尚未出现过的轨迹预测结果准确性有限.因此, 乔少杰等[15]以及Besse等[16]利用高斯密度分布对轨迹建模, 并利用高斯回归过程对轨迹进行预测.这种基于连续密度的模型不仅可以以概率的形式对轨迹的不确定建模, 还能对轨迹的终点给出连续形式的解, 相较于离散模型具有更高的预测准确性.

现有研究虽然采用了不同的预测方法, 但几乎均需要根据待检测的移动轨迹与历史轨迹数据的匹配程度进行轨迹终点的判断.然而在真实的移动场景中, 人的移动行为具有较强的不确定性, 一是由于信息采集设备的能效问题可能导致录入的信息存在不同程度的损失或干扰, 使获取的信息与真实信息存在偏差; 再者由于人与社会的复杂性, 人的移动具有较强的不确定性, 使得在以同一目标为终点进行移动时可能出现任意不同的移动轨迹, 例如为了躲避交通的拥堵可能选择路程相对较远的路线, 或为了兴趣或特殊目的而选择比较随意的移动路线等.可见, 真实的移动场景中的轨迹充满了各种各样的不确定性, 一个用户当前的移动轨迹可能与任意一条历史轨迹均不相同, 但实际上又可能与某条历史移动轨迹具有相同的起始点和终点.针对这样的体现用户不确定移动行为的轨迹, 现有方法难以对终点进行较准确的预测.对于移动轨迹的研究面临的问题来说, 一方面是无法准确地确定移动对象的移动轨迹细节(例如移动对象下一个准确的移动位置), 另一方面是难以通过单一或简单的假设理论模型进行确定的建模, 这种复杂性与不确定性的存在, 使得理想条件下对移动轨迹的预测难以获得较准确的结果.面对这种问题, 本文将结合不确定性的研究思路根据用户当前的移动行为其轨迹终点进行预测.

一个用户的移动轨迹由其经过的若干个位置信息构成.如果将一个用户的移动轨迹视为不确定的, 那么起始点和终点相同的若干移动轨迹则构成了表示两点间所有经过路线的不确定轨迹数据集, 即包含了两点间所有可能路线的样本集.此时可以从该不确定样本集内的所有移动轨迹中获得用户在两点间的移动行为分布特征, 而这种行为的分布特征具体体现为轨迹中位置信息的分布特征.如果认为移动轨迹中的位置点服从某种密度分布, 那么对于概率密度较高的位置, 分析当前用户的移动轨迹时会有较高的可能性选择该位置.而非参数估计方法能够在不假设分布类型的前提下构建更符合数据实际分布特征的概率密度函数, 因此本文基于这种不确定性的研究思路, 提出一种基于非参数密度估计的面向不确定轨迹的终点预测方法.首先基于非参数估计方法, 对已获取的两点间的所有移动轨迹数据构建符合其分布特征的概率密度函数; 然后在分析当前用户的移动轨迹时, 基于假设检验方法度量待检测轨迹与已有的不确定轨迹关于轨迹中位置点分布特征的相似性, 分析待检测轨迹未来可能经过的位置点以及可达的终点.所提方法主要利用不确定性的分析方法, 结合所有历史移动轨迹信息的特点, 对移动轨迹进行建模, 使得模型能够基于概率分布函数体现历史数据中所有用户的移动行为特征, 最终达到能够对历史数据中尚未出现的轨迹也具有极好的识别能力, 即在更接近人类移动行为特征的条件下, 对其轨迹的未来移动位置和终点进行较准确的预测.本文首先构建不确定移动轨迹模型; 进而提出不确定移动轨迹相似性度量方法; 然后据此对待检测的移动轨迹的终点进行预测; 接着通过实验验证所提方法的有效性; 最后得出结论.

图 1  不确定轨迹示意图

图 2  轨迹预测示意图

图 3  停留时间的频次分布图

针对移动对象轨迹的随机性与不确定性问题, 本文提出了一种基于非参数统计方法的不确定轨迹预测算法.首先利用核密度估计方法对轨迹数据集中的不确定轨迹进行建模, 通过概率密度函数表示其不确定性的分布特征, 基于非参估计的方法能够获得较客观的符合数据实际分布的不确定轨迹分布情况; 然后利用KS检验的方法分析输入轨迹与已知的不确定轨迹分布间的匹配关系, 从而根据相匹配的不确定轨迹预测输入轨迹的目标终点.所提方法充分考虑轨迹中体现的移动用户行为的不确定性, 对历史轨迹中任意可能的位置进行计算, 因此在实际预测问题中, 能够获得较好的建模和预测能力, 在真实数据集上的实验也验证了所提方法的有效性和可靠性.

作者简介

程媛

哈尔滨理工大学计算机科学与技术学院讲师.主要研究方向为数据挖掘, 不确定性研究.E-mail:changuang7@sina.com

黄少滨 

哈尔滨工程大学计算机科学与技术学院教授.主要研究方向为分布式计算与仿真, 模型检测, 数据集成.E-mail:huangshaobin@hrbeu.edu.cn

吕天阳 

审计署计算机技术中心国家仿真实验室高级工程师.主要研究方向为复杂网络, 计算机审计.E-mail:raynor1979@163.com

迟荣华  

哈尔滨工程大学计算机科学与技术学院博士研究生.主要研究方向为机器学习, 不确定性研究.本文通信作者.E-mail:chironghua@126.com