规划问道
数据精英夏季特训营开车啦！
同时报名还可享更多优惠：
任选2套同报，再减200元！
任选3套同报，再减360元！
任选4套同报，再减520元！
任选5套同报，再减700元！
任选6套同报，再减900元！
（以上优惠不包括营5和营14）
在主干道路网中，因交通信号灯计时设置不当引起的车辆的反复“停-走”也会导致大量的交通延时、增加尾气排放以及燃油浪费。所以，交通信号灯动态计时信息的感知和预测是一个非常值得研究的课题。本项目的研究目的是设计能从低采样出租车GPS轨迹数据的统计模式中挖掘信号灯的配时参数并对其状态信息进行预测的方法和系统。
本项目研究的理论意义在于：(1) 将基于低采样轨迹的轨迹细粒度重构问题描述成多约束优化问题，并提出有效的方法解决；(2) 提出有效模型用于描述路口车辆的启动延时与其在车队中位置关系，并用于准确估计其启动延时；(3) 将基于含噪、不完备观测数据的信号灯配时参数学习问题描述为周期分析问题，并提出快速算法求解。本项目研究的应用价值在于：它有助于提高燃油利用率，降低有害气体排放；减少不必要的停等和路口拥堵，以节省出行时间，加强行车的安全性。
项目结题成果报告
以下研究成果内容摘自项目结题成果报告。该项目报告共计24页，关注城市数据派微信公众号，在微信公众号对话框中输入 2495，即可获得报告全文PDF的下载方式：
(1)主要研究内容
本项目执行过程中所研究的主要内容包括以下几个方面:①利用低采样率GPS 轨迹数据反演车辆的细粒度运动行为，即利用稀疏采样GPS轨迹反推车辆过路口时的停-走状态。该停-走状态是用于提取信号灯状态信息的关键因素。②自动获取定时控制交通信号灯配时参数,即利用稀疏采样的信号灯状态数据分析信号灯的计时周期，进而推每个周期内的红、绿灯的计时长度。该研究内容所面临的主要挑战是基于稀疏含噪数据的周期分析,传统周期分析方法在数据稀疏且含噪的情况下失效，所以需要设计新的算法来解决该问题。③定时控制交通信号灯的状态预测;在已知定时控制信号灯的计时周期和红绿信号灯的周期内时长分配的情况下，信号灯的状态预测问题就转变成周期的绝对起始时间确定问题。④位置数据的隐私保护。由于设计实现基于众包的信号灯信息感知平台时涉及参与感知用户的位置隐私保护问题,所以课题执行过程中又考虑了位置隐私保护问题的研究。
(2)取得的主要研究进展、重要结果、关键数据等及其科学意义或应用前景，项目执行过程中，所取得的重要研究进展介绍如下，
①基于低采样轨迹的运动轨迹细粒度重构算法研究
在项目计划书的指导下，本年度实际开展的工作主要包括:轨迹地图匹配和细粒度重构算法的研究。深入研究针对地采样GPS轨迹数据的地图匹配算法，在现有算法的基础上进一步提出匹配精度更高、效率更快的地图匹配算法。通过提升轨迹重构精度以进一步提升信号灯配时参数估计的准确性,进而根据估计得到的配时信息来更准确地估计和预测信号灯的状态。相关研究成果具体介绍如下严盛隆，于娟，周后盘，“IIVMM:针对低频 GPS 轨迹的改进交互式投票匹配算法,”计算机科学,vol.46,no.9,pp.325-332,2019.
地图匹配是根据离散采样的定位数据(GPS 坐标)识别移动对象(车辆、行人等)在道路网络中的运动路径的过程。它是许多基于GPS轨迹数据分析和位置分析等相关应用的必要处理步骤。针对现有的算法在应用于低采样轨迹数据时存在的匹配准确率和效率较低的问题,我们提出一种基于交互式投票的改进地图匹配算法算法框架和描述见图1。该算法不仅考虑距离特征、道路的拓扑结构以及路段的限速，还考虑了每个GPS的点实时移动方向和速度，以提高算法的匹配准确率;其次，算法中还加入了基于方向和限速的滤波器，通过约束条件过滤候选噪声路段，以提高算法的匹配效率。为了验证算法的性能，作者使用了两组真实数据集对所提算法与现有的IMM 算法和 AIVMM 算法进行比较。实验结果表明，所提算法在匹配性能上优于现有的两种现有的算法。
通过对现有地图匹配算法的分析总结，发现它们存在以下问题:1)现有算法中大部分都未能有效平衡匹配效率与准确率;2)现有算法处理低采样率轨迹数据的性能仍有待提升:3)现有算法大都对噪声数据非常敏感。针对上述问题，针对高频轨迹，提出了一种基于隐马尔科夫模型(Hidden MarkovModel,HMM)的快速地图匹配算法。首先，提出一种基于滑动窗口的轨迹简化方法，用于过滤原始轨迹中的大量冗余点和部分噪点;然后，提出一种自适应候选路段搜索算法用于白适应地计算每个GPS点的候选集;最后使用基于HMM地图匹配算法查询最优路径。实验部分采用了两组真实高频数据集验证算法的性能。实验结果表明所提算法在保证匹配准确率的同时，将匹配效率提高至基于HMM地图匹配算法的 4-5 倍。
周后盘;严盛隆;于娟,“一种针对低频 GPS 轨迹的改进交互式投票匹配方法,CN109459045A,12-Mar-2019.已公开专利
该发明专利公开了一种针对低频GPS轨迹的改进交互式投票地图路径匹配方法，不仅考虑距离特征、道路的拓扑结构以及路段的限速，还考虑了每个GPS的点实时移动方向和速度,以提高匹配准确率;另外,该发明中还加入了滤波器,通过约束条件去除候选噪声路段，以提高匹配效率。该发明具有匹配准确率高效率高和鲁棒性强的优点。
另外，针对现有的候选路段搜索方法效率低下的问题，我们还提出了一种自适应候选路段搜索方法，并已撰写成发明专利。本方法首先通过DP轨迹压缩方法压缩轨迹，主要作用是去除连续漂移点和一系列停滞点(保证在一个小范围内只有一个噪点或停驻点);然后利用传统候选路段搜索方法计算压缩轨迹的候选集;最后通过基于最短路径的可疑噪点检测方法检测出所有可疑点，并自适应地扩大搜索范围，计算新的候选集。
在上述研究的基础上,我们对地图匹配算法的研究工作进行了深入的调研和总结，调研成果已整理成论文投稿。相关算法的总结见图2。为后续的深入研究提供更好的储备。
信号灯的计时周期是指信号灯的两次相邻绿灯开始时间间隔(或两次相邻红灯开始时间间隔)，是信号灯计时信息中的一个非常重要的参数。主要考虑采用出租车GPS轨迹自动估算路口信号灯的计时周期。信号灯的计时周期可以通过绿灯开始时间计算。首先，从轨迹数据中提取信号灯的绿灯开始时间;然后，利用提取的绿灯开始时间估计信号灯的计时周期。由于轨迹数据本身的稀疏性和出租车到达路口时间间隔的稀疏性，使得我们能获取的观察数据是稀疏、含噪且含离群数据。所以，信号灯计时周期的估计问题即为基于稀疏、含噪观测数据的周期估计问题。为解决该问题，我们提出基于公因子逼近的系列周期估计算法，包括:MFAGCD(Most Frequent Approximate Greatest Common Divisor)算法和rMFAGCD(robust MFAGCD)算法,具体算法描述见图3。很好地解决了基于稀疏、含噪且含离群观测数据的信号灯计时周期估算问题,能够比较准确地估计路口的计时周期进而分析路口计时周期的变化规律。rMFAGCD算法是在MFAGCD法基础上的改进，采用新的偏移项消除策略以更好地克服离群数据的影响。相对于现有的方法，所提算法的主要优点是:更好的抗稀疏性;收敛快，利用少量的观测数据获得准确的周期估计;无需严格的真实周期取值区间作为先验知识，仅需已知周期取值的下界;可扩展性好。
给定某路口，以及一段时间内通过该路口的所有出租车GPS轨迹数据，所要解决的问题是利用这些数据分析该路口信号灯的计时周期P。为解决信号灯周期性分析问题，提出一个基于GPS轨迹数据的信号灯周期性分析系统，该系统由三个主要模块构成:数据预处理、信号灯绿灯计时开始事件及状态序列提取和基于状态序列的周期分析。首先，在数据预处理阶段从采集的GPS轨迹数据库中查询所有经过指定路口的轨迹数据，并根据轨迹的行驶方向进行分类。然后，利用轨迹数据提取出信号灯的状态信息。信号灯状态信息的提取过程可细分为两个步骤首先，根据GPS轨迹数据推断车辆过路口时的通行行为，根据车辆过路口时的通行行为推断对应时间间隔内信号灯的状态信息。其次，利用提取出的绿灯开始时间序列对信号灯的计时周期进行估算。首先，可以根据出租车过路口时的轨迹数据中的速度和距离信息分析它的通行行为，再根据它过路口时的通行行为，即直接通行还是停等再通行，推导信号灯在其通过的时间区间内的状态信息。然后，采用各条轨迹分时段投票的方式,聚集整个轨迹数据采样时间所覆盖的时间段内大量通行车辆在路口的轨迹信息，获得在这段时间内信号灯的状态序列。最后基于轨迹数据分析所获得的信号灯状态序列,采用现有的周期估算方法并结合可视化方法来估算信号灯的计时周期和红绿灯各自的计时长度。具体的信号灯状态提取算法和周期估计算法见图 4。
③位置隐私保护相关算法研究
Rong Fang,Jianmin Han, Juan Yu, et al.,Differentially Private LocationPreservation withStair-case Mechanism under Temporal Correlations, EACollaborateCom 2020-16thEAl International Conference on CollaborativeComputing: Networking, Applications and Worksharing, October 16-18, 2020
针对时间相关性下的位置隐私保护问题提出基于8-位置集的staircase 位置扰动算法。传统位置隐私保护方法没有考虑同一用户连续时间戳下位置相关性带来的隐私泄露问题，基于8-位置集的位置隐私是解决这一问题的最新隐私模型,它克服了传统方法中忽略时间相关性所带来的隐私泄露问题。但是，现有的实现8-位置集隐私的加噪机制存在效率低、同等隐私预算条件下对位置数据产生过多扰动的不足。针对此不足，我们提出一种新的位置扰动算法，即基于stairecase的8-位置集扰动算法。最后，通过在真实数据集上的实验，验证了我们所提方法的有效性，即加噪效率的提升和扰动位置有用性的提升。该算法可以用于本课题的基于众包的信号灯信息感知平台中，解决参与感知用户的隐私担忧，进而吸引更多的参与者加入感知任务。
Xin Yao, Juan Yu, Jianmin Han, Qi Liu, Jianfeng Lu, Hao Peng, DP-PCSM：
Differentially Private Trajectory Publication with Private Coresets and StaircaseMechanism, submitted.
移动用户的轨迹数据的发布和共享会带来严重的隐私泄露问题。因为轨迹中隐含了移动用户的家庭住址、个人活动偏好、生活轨迹模式等重要的个人隐私信息。针对用户位置轨迹数据发布中可能存在的隐私泄露问题提出一种基于隐私核心集和 staircase 机制的轨迹差分隐私保护方法。现有的轨迹差分隐私保护方法存在效率低和数据可用性损失严重等问题。我们提出的基于隐私核心集和stairecase 机制的方法就是为了解决隐私保护效率和数据可用性问题。通过基于真实轨迹数据的实验,验证了我们的方法在轨迹扰动效率和扰动轨迹可用性方面都较已有典型方法有所提升。随着人们对隐私问题的日渐重视，给轨迹数据的收集以及众包参与者的召集带来了更大的阻力。该研究工作也可以用于本课题研究中的数据收集和基于众包的信号灯信息感知平台中,帮助解决因轨迹数据收集而带来的隐私泄露问题。
……
还有更多成果内容，详见项目结题成果报告。该项目报告共计24页，关注城市数据派微信公众号，在微信公众号对话框中输入2495，即可获得报告全文PDF的下载方式。
原文始发于微信公众号（城市数据派）：基于大规模出租车GPS轨迹数据的交通信号灯动态计时信息感知丨城市数据派
