数据挖掘技术在出行体验上的应用！
桔妹导读：每天滴滴都会为上千万人提供出行服务，在这一过程中积累了海量轨迹数据。这些轨迹数据来自于公共服务，本文介绍如何利用这些数据回馈大众，改善出行体验。
针对这一问题，我们基于轨迹点的密度（时间密度、空间密度）进行数据过滤，并对局部自相交轨迹段进行分段，最后通过Douglas Peucker算法提取轨迹段关键形状点，在保留轨迹转向特征的同时，对数据实现了压缩。因此，通过轨迹分段、去噪、压缩的预处理，实现了对原始轨迹数据的质量提升。
为了检测道路交叉口影响区内的详细拓扑信息，首先需要识别道路交叉口的核心区域，即路口位置和覆盖范围。考虑到不同路口大小不一，并且路口范围内轨迹通常具有减速、转向等特征，我们设计了一套基于四叉树空间划分和Mean-shift的自适应路口位置检测算法。在搜索道路交叉口单元的过程中，将四叉树的最小边长设置为25米，并从200米大小边长开始的层（即从四叉树底部开始的第四层）搜索道路交叉口单元。由于交叉口中心位置的轨迹往往比路段具有更多的转向与较低的转速，我们对每个网格单元中的所有特征点（轨迹压缩获得）执行速度分析和基于方向的DBSCAN聚类，筛选潜在的道路交叉口网格单元。随后，鉴于Mean-Shift算法可以在聚类过程中同时检测出密度中心，我们通过该算法，结合候选交叉口单元内的轨迹点识别路口的中心位置。
不同路口其形状有较大差异，如何更通用地基于轨迹数据确定路口的核心区范围？实质上道路交叉口的中心位置附近并不总是具有相对于路段区域更多转向行为，例如，环岛和立交桥。本文中我们利用环状几何模型逐层检测路口覆盖范围。对于一个路口而言，越到核心区边缘的环包含的转向点密度越低、速度越大，因此该路口模型适于不同形状路口的范围提取。
在最终的路口拓扑校准上，为了评估我们解决方案的有效性，我们基于滴滴实际轨迹数据和路网检测两种类型的错误拓扑：转向路径缺失和转向路径偏移。根据我们的评估，整体的精确率能够达到70%，转向路径缺失和偏移的比例在1 : 5。目前该方法已经在滴滴路网更新产线中得到应用，下图为两个典型案例（路网为淡灰色线，轨迹分布以深蓝色表示，校正的转向路径以红色箭头线突出显示。
在网约车业务场景中，可能会出现司机师傅未能按照导航路线行驶而出现路线偏移的现象，导致此类场景出现的原因可能是路况不佳、路线不合理、道路封闭，也可能是司机发现了更好的路线躲避拥堵，或者是对路线不熟悉，甚至故意绕路等。挖掘此类场景对于网约车提升地图用户体验、避免司乘纠纷、保障司乘安全具有至关重要的意义。为了解决此类问题，地图团队通过全局/局部的起终点（Origin-Destination，简称OD) 约束，基于用户历史轨迹行为特征建模，实时观测目标用户轨迹行为空间分布特征，从而检测路线偏移行为。基于用户轨迹的路线偏移检测，我们最终构建了实时触达用户的轨迹安全产品与路网状态更新体系。
基于OD轨迹路线偏移检测，通常涉及到路线表征维度多样性、OD观测空间下历史正常轨迹稀疏性、检测实时性等建模问题以及TB级轨迹大数据的离线特征存储更新、在线实时查询等工程问题。虽然在学术研究领域，轨迹异常检测已经形成了相对成熟的解决方案与不同角度的研究积累，但在实际工程实践会面临复杂多样的业务场景，具体来讲：
路线表征维度多样性
用户轨迹路线可以用一系列有序的GPS点串表征，该方式可以保留最原始的路线信息，但是会存在轨迹飘点、冗余、无法批量高效建模的问题；也可以基于轨迹匹配道路结果进而通过一系列路段表征路线，该种表征方式最为常见，同时也会存在轨迹质量、绑路策略而带来的误匹问题；还可以将GPS映射到空间瓦片表示，该方式可以有效规避以上两类问题，但是无法精确定位路网问题。因此在不同的建模场景中，应该采取不同的路线表征维度。左侧蓝色点串GPS轨迹的原始表示，右侧表示轨迹的瓦片表示。
OD观测空间下历史正常轨迹稀疏性
由于我们是在OD的空间约束下进行轨迹建模，并且需要观测在该空间下历史用户轨迹分布特征，如果用户行程起终点下关联的历史用户轨迹数量过少甚至不存在，那对于轨迹建模来讲将是巨大的挑战。检测实时性
在路线偏移的场景下，不管是路网状态异常还是订单状态异常，都要求算法能够实时、精确、可解释的计算结果并触达用户，因此要求我们的算法要能够实时地对端上上报的轨迹点进行状态判定。
为了解决异常路线偏移检测的问题，考虑到不同的产品及业务需求，我们设计并完成了以下两大类检测解决方案，下面进行简单的介绍。
▍3.2 "少而不同"绕路检测
路线形状表达
轨迹路线形状表达的目的主要是压缩轨迹，同时保证形状信息和压缩率；同时也要平滑轨迹，去除停留点与噪点。我们采用了Minimum Description Length Partition算法对轨迹进行压缩表示，该算法通过定义角度距离、垂直距离等，拓展了传统的Douglas-Peucker算法，无需定义阈值，可以自适应增量式划分和压缩轨迹。
导航特征表达
在实际业务场景中，除了轨迹路线形状之外，我们还可以实时获取到用户导航-偏航状态的特征，通过行驶方向与导航起终点方位关系，可以判定用户当前是否在朝向终点运动。红色线条为道路路线，绿色线条为轨迹路线，β1表示A1A2导航起终点夹角为锐角，朝向相近，即朝向终点运动，β2反之。
稀疏OD轨迹Embedding
为了克服上文中提到的同OD下历史正常轨迹稀疏性的问题，我们提出了一种基于地理空间关系学习的轨迹Embedding方案。该方案主要是在订单起终点的约束下，建模轨迹中途经点与起终点之间的关系，由于不涉及到具体特定轨迹，只是建模起终点与途经点关系，因而在可以在一定程度上解决OD空间下稀疏性的问题。Embedding主要更新学习过程如下：
其中，地理特征矩阵更新学习的过程为：
S1) 将行驶的轨迹T={p1, p2, … , pn}根据坐标映射到对应的路网网格中。轨迹可以表示为T={g1, g2, … , gn}其中gi为行驶轨迹中坐标pi在路网中对应的网格。
S2）使用具有固定窗口大小和固定滑动步长的滑动窗口，将轨迹T={g1, g2, … , gn}划分为若干定长的子轨迹，如滑动窗口大小为10，滑动步长为1，则原始轨迹T可被划分为子轨迹集合T’ = {Tj | Tj={gj, gj+1, … , gj+9}, 1≤i≤n-9}
S3）假设路网中有N个互不相同的路网网格，则对目标区域的所有路网网格随机初始化两个N*d维特征矩阵，特征矩阵中的每一行为一个特征向量，分别表示对应网格作为起点和终点时的特征。将两个特征矩阵拼接后可以得到一个N*2d维的特征矩阵，用于表示对应网格作为轨迹途经点（既非起点也非终点）时的特征。
S4）将S2）中得到的每条子轨迹T={g0, g1, … , gn} 根据轨迹点性质转化T={S, M1, … , Mj, D}，其中S=g0表示子轨迹起点，D=gn表示子轨迹终点，M1, … , Mj表示子轨迹途经点。
S5）在起终点约束的条件下，最大化途径点M1, … , Mj出现的平均对数概率，即可完成在在地理空间约束下的轨迹建模。根据轨迹点性质，分别从不同特征矩阵查找轨迹经过的路网网格的性质。即从起点特征矩阵中查找起点S的特征向量，为d维向量；从终点矩阵中查找终点D的特征向量，为d维向量；从途径点矩阵中查找途径点Mj的特征向量，为2d维向量。拼接起点S和终点D的特征向量和，即可得到2d维的起终点特征向量。
S6）通过反向传播更新起点、途经点和终点的特征矩阵，直到模型收敛。此时即可得到送驾区域路网网格在地理空间约束下的特征向量。实时离群点检测
为了满足轨迹实时异常检测需求，需要算法能够在系统输入的一定时间窗口的轨迹之后，完成路形表达、导航特征提取、轨迹特征Embedding之后，立即给出在该OD空间约束下，当前行程轨迹是否处于偏移状态以及该状态下基于以上特征的支持度【支持度可以定义为在OD约束下，历史正常路线途径该瓦片的订单数量 / OD约束下总订单数量】，借鉴iBOAT自适应窗口检测在线检测思路，类似的，我们提出了一种基于多特征表征的实时路线偏移检测框架，具体检测过程为：当偏航发生时，在一定时间窗口，获取目标订单行程轨迹，对该行程进行路形、导航、轨迹特征的表征与判别。下图中，图一蓝色为历史正常用户实际轨迹路线，红色为目标用户轨迹；图二为iBOAT自适应窗口判别示意图。
图一
图二
该模型主要分为两个模块，第一个算法模块是基于时间序列流量信息相似性建模，该模型可以引入经典的Siamese LSTM网络，并融合注意力机制与自定义损失函数，实时刻画历史同期流量曲线与当前流量曲线的相似性，从而在线检测流量异常。由于采取了与历史同期（例如本周一与上周一）的流量序列建模，因而对流量自然下降及波动具备很强的鲁棒性。
基于Siamese LSTM流量异常检测可以对全路网空间的流量异常进行实时检测，其检测的结果需要更强的证据佐证道路异常，因此，我们设计了第二个算法模块LSPD， 该算法侧重于通过群体用户行为的异常判别第一个算法模块结果的可解释性与概率性，主要思想是统计同OD下路线模式的分布变更，不同于轨迹异常检测算法(iBOAT) 在OD场景下关注“少而不同“的异常轨迹，我们重点关注“多而不同“的用户群体性异常行为，例如某时间段内历史用户集中出现了绕路事件，则通过我们的LSPD算法模块可以精确定位到哪些路段可能出现了道路封闭以及发生发生该类事件的置信度有多大。
在当前的工业实践中，数据挖掘也常常和一些热门词汇联席出现，比如人工智能、机器学习、大数据、数据分析、数据科学等，如下图所示。
相比于其他概念，数据挖掘不强调应用何种手段，更强调目的：从数据中提取信息。在这个意义上讲，数据挖掘天然是交叉学科，需要从业人员具备统计、机器学习、大数据乃至高并发后台服务、数据可视化等复合技能。另一方面，目前的人工智能技术水平仅仅达到刻画相关性的阶段，尚不能进行通用推理或者知识学习，所以需要从业者对研究的领域具备一定先验知识，并了解如何利用这些知识从数据中提取有高价值信息。这两个特点决定了领域数据挖掘的门槛非常高，这影响了数据价值的快速发掘和落地。笔者所在团队承担了公司内部很多挖掘任务，比如安全驾驶行为检测、路网挖掘、交通事件、地理画像、出行模式分析等等，更多的数据挖掘任务因为排期和资源限制无法快速支持，而需求方因为高技能门槛无法自行对数据进行加工和价值提取。
本文作者
▬
2017年加入滴滴，轨迹挖掘团队负责人，负责基于多模态融合的路网情报发现与路网状态更新、轨迹挖掘、地图安全特征平台等工作。
2017年加入滴滴，轨迹挖掘团队负责人，负责基于多模态融合的路网情报发现与路网状态更新、轨迹挖掘、地图安全特征平台等工作。
2016年加入滴滴，负责基于多源大数据的路网更新方向的算法工作，研究兴趣点包括时空异常检测、出行模式挖掘、路网生成等。
2016年加入滴滴，负责基于多源大数据的路网更新方向的算法工作，研究兴趣点包括时空异常检测、出行模式挖掘、路网生成等。
2018年加入滴滴，在滴滴从事轨迹模式挖掘、用户异常行为检测、道路封闭检测等工作。
2018年加入滴滴，在滴滴从事轨迹模式挖掘、用户异常行为检测、道路封闭检测等工作。
团队招聘
▬
滴滴地图与公交事业部轨迹挖掘团队利用滴滴海量的出行数据，对道路状况／交通流量／司机驾驶习惯进行建模，使用数据挖掘和机器学习技术发现路网情报和行程异常，提升滴滴用户的出行体验和平台效率。
团队长期招聘研发工程师，包括机器学习、大数据、策略架构等方向，欢迎有兴趣的小伙伴加入，可投递简历至 diditech@didiglobal.com，邮件请邮件主题请命名为「姓名-应聘部门-应聘方向」。
扫描了解更多
内容编辑 | Charlotte 联系我们 | DiDiTech@didiglobal.com
