关于数据库:数据挖掘技术在轨迹数据上的应用实践

​

桔妹导读： 每天滴滴都会为上千万人提供出行服务，在这一过程中积攒了海量轨迹数据。这些轨迹数据来自于公共服务，本文介绍如何利用这些数据回馈公众，改善出行体验。

1. 背景

首先简要介绍一下什么是数据挖掘。数据挖掘（Data Mining）是指从大量数据中发现特定信息和模式的过程，也有很多人将这一过程看作常识发现（Knowledge Discovery in Database）。数据挖掘罕用的算法伎俩有回归、分类、聚类和模式发现，工程上数据挖掘通常和大数据技术分割在一起，工业实际中还须要从业人员对数据中蕴含的畛域常识有足够理解。业界开掘伎俩常常用在用户画像、商业智能（Business Intelligence）、社群关系发现等场景。本文次要分享如何从海量轨迹数据中提取要害信息，改善用户出行体验。滴滴在业务经营过程中，司机端 APP 会继续向后盾上传地位信息，这些信息被用于分单、司乘碰面、导航、里程计费。每天滴滴都会为上千万人提供出行服务，在这一过程中积攒了海量轨迹数据。这些轨迹数据不波及用户隐衷，次要反馈了公共路线上的交通状况和司机驾驶习惯。上面咱们会具体介绍两个典型场景。

2. 路网更新

作为数字路线地图的要害局部，路线交叉口是多条相互连接路线的交汇处，其几何特色和拓扑属性的精确性在挪动导航和其余位置服务中起着重要作用。随着城市倒退，交叉口的更新越来越频繁，次要蕴含挂接关系变更、新路、状态变更，这类拓扑谬误如果不能及时检测及更新，会影响路网匹配、门路布局、导航播报等基于路网数据的地图服务，产生导航绕路、播报不合理等用户体验问题。

▍2.1 技术挑战

交叉口拓扑更新能够形象成这样一个问题：路口范畴内的轨迹矢量模式与路网是否匹配？为此，须要解决以下几个关键问题：第一，轨迹数据蕴含了大量噪声，如何进行无效去噪；第二，路口地位及范畴如何确定；第三，轨迹矢量模式如何表白以及如何与路网差分。为了解决以上问题，咱们设计出的算法框架如下，蕴含三个外围模块：轨迹品质晋升，路口影响区域检测和拓扑构造校准模块。相干工作发表在数据挖掘与数据库技术顶级学术会议 International Conference on Data Engineering (ICDE) 2020 上。

▍2.2  轨迹品质晋升原始轨迹数据可能受设施故障、信号不佳等因素影响导致采集到的定位信息存在漂移甚至异样，咱们依据前后轨迹点的间隔和工夫距离进行轨迹段的宰割，保障同一轨迹段在时空上具备连续性；此外，车辆在路口个别会因为等红绿灯或交通拥堵停留，导致在短距离范畴内产生大量具备不同方向的地位信息（噪声），不仅减少了路口检测的计算开销，还给检测精度带来较大影响。

针对这一问题，咱们基于轨迹点的密度（工夫密度、空间密度）进行数据过滤，并对部分自相交轨迹段进行分段，最初通过 Douglas Peucker 算法提取轨迹段要害形态点，在保留轨迹转向特色的同时，对数据实现了压缩。因而，通过轨迹分段、去噪、压缩的预处理，实现了对原始轨迹数据的品质晋升。

▍2.3 交叉口地位及范畴生成

为了检测路线交叉口影响区内的具体拓扑信息，首先须要辨认路线交叉口的外围区域，即路口地位和覆盖范围。思考到不同路口大小不一，并且路口范畴内轨迹通常具备加速、转向等特色，咱们设计了一套基于四叉树空间划分和 Mean-shift 的自适应路口地位检测算法。在搜寻路线交叉口单元的过程中，将四叉树的最小边长设置为 25 米，并从 200 米大小边长开始的层（即从四叉树底部开始的第四层）搜寻路线交叉口单元。因为交叉口核心地位的轨迹往往比路段具备更多的转向与较低的转速，咱们对每个网格单元中的所有特色点（轨迹压缩取得）执行速度剖析和基于方向的 DBSCAN 聚类，筛选潜在的路线交叉口网格单元。随后，鉴于 Mean-Shift 算法能够在聚类过程中同时检测出密度核心，咱们通过该算法，联合候选交叉口单元内的轨迹点辨认路口的核心地位。

不同路口其形态有较大差别，如何更通用地基于轨迹数据确定路口的核心区范畴？本质上路线交叉口的核心地位左近并不总是具备绝对于路段区域更多转向行为，例如，环岛和立交桥。本文中咱们利用环状几何模型逐层检测路口覆盖范围。对于一个路口而言，越到核心区边缘的环蕴含的转向点密度越低、速度越大，因而该路口模型适于不同形态路口的范畴提取。

▍2.4 拓扑构造校准

在路口范畴拓扑构造的校准阶段，咱们基于检测的路口核心地位和核心区范畴向外扩大，获取交叉路口影响区内的全副轨迹。咱们对这些轨迹进行转向簇提取与中心线拟合，并将拟合的转向门路与基准路网进行地图匹配。Frechet 间隔适于评测曲线之间的相似性，然而对于简单形态的路口以及路口邻接路段间朝向偏差较小的状况，Frechet 体现不佳。鉴于此，咱们将方向权重引入轨迹相似性度量中。对于任意两条轨迹序列，别离计算终点与起点间的方向差，并联合 Frechet 间隔生成轨迹汇合的间隔矩阵。基于该矩阵联合 DBSCAN 聚类实现路口范畴内的转向簇提取。

在提取转向簇后，须要对各簇轨迹进行拟合来失去转向矢量模式。咱们采纳基于 Force Attraction 的聚类办法获取各簇对应的转向门路，相比如其余依赖点信息的拟合算法如 Sweeping 等，Force Attraction 办法可能充分运用轨迹线信息，因而对简单转向场景的拟合更加鲁棒。Force Attraction 办法首先随机采样簇中的一条轨迹作为参考轨迹，随后应用同簇内其余轨迹对参考轨迹中点的地位进行迭代调整。在调整过程中，Force Attraction 算法假设任意轨迹点上有吸引力和排斥力作用，通过搜寻两个力达到均衡的地位来取得参考轨迹对应点的新地位。因为随机采样轨迹容易导致拟合失去的中心线不精准，特地是当随机采样的参考轨迹远离理论路线核心时，拟合偏差较大。因而，咱们引入基于 Frechet 的采样策略。具体来说，咱们从簇中随机采样 k 条轨迹作为候选参考轨迹，并别离计算每个候选者与该簇的其余轨迹之间的 Frechet 间隔。将具备最小间隔和的候选轨迹视为参考轨迹。

在取得转向门路后，咱们采纳经典的 HMM 算法联合基准路网进行地图匹配。为减速匹配过程，咱们基于每个路口的转向门路集生成凸包再与路网空间关联。依据匹配概率失去低置信度转向门路，作为需修改拓扑情报。

在最终的路口拓扑校准上，为了评估咱们解决方案的有效性，咱们基于滴滴理论轨迹数据和路网检测两种类型的谬误拓扑：转向门路缺失和转向门路偏移。依据咱们的评估，整体的准确率可能达到 70%，转向门路缺失和偏移的比例在 1 : 5。目前该办法曾经在滴滴路网更新产线中失去利用，下图为两个典型案例（路网为淡灰色线，轨迹散布以深蓝色示意，校对的转向门路以红色箭头线突出显示。

3. 路线偏移

在网约车业务场景中，可能会呈现司机徒弟未能依照导航路线行驶而呈现路线偏移的景象，导致此类场景呈现的起因可能是路况不佳、路线不合理、路线关闭，也可能是司机发现了更好的路线规避拥挤，或者是对路线不相熟，甚至成心绕路等。开掘此类场景对于网约车晋升地图用户体验、防止司乘纠纷、保障司乘平安具备至关重要的意义。为了解决此类问题，地图团队通过全局 / 部分的起起点（Origin-Destination，简称 OD) 束缚，基于用户历史轨迹行为特色建模，实时观测指标用户轨迹行为空间散布特色，从而检测路线偏移行为。基于用户轨迹的路线偏移检测，咱们最终构建了实时触达用户的轨迹平安产品与路网状态更新体系。

▍3.1 技术挑战

基于 OD 轨迹路线偏移检测，通常波及到路线表征维度多样性、OD 观测空间下历史失常轨迹稠密性、检测实时性等建模问题以及 TB 级轨迹大数据的离线特色存储更新、在线实时查问等工程问题。尽管在学术研究畛域，轨迹异样检测曾经造成了绝对成熟的解决方案与不同角度的钻研积攒，但在理论工程实际会面临简单多样的业务场景，具体来讲：

1. 路线表征维度多样性

用户轨迹路线能够用一系列有序的 GPS 点串表征，该形式能够保留最原始的路线信息，然而会存在轨迹飘点、冗余、无奈批量高效建模的问题；也能够基于轨迹匹配路线后果进而通过一系列路段表征路线，该种表征形式最为常见，同时也会存在轨迹品质、绑路策略而带来的误匹问题；还能够将 GPS 映射到空间瓦片示意，该形式能够无效躲避以上两类问题，然而无奈精确定位路网问题。因而在不同的建模场景中，应该采取不同的路线表征维度。左侧蓝色点串 GPS 轨迹的原始示意，右侧示意轨迹的瓦片示意。

1. OD 观测空间下历史失常轨迹稠密性

因为咱们是在 OD 的空间束缚下进行轨迹建模，并且须要观测在该空间下历史用户轨迹散布特色，如果用户行程起起点下关联的历史用户轨迹数量过少甚至不存在，那对于轨迹建模来讲将是微小的挑战。

1. 检测实时性

在路线偏移的场景下，不论是路网状态异样还是订单状态异样，都要求算法可能实时、准确、可解释的计算结果并触达用户，因而要求咱们的算法要可能实时地对端上上报的轨迹点进行状态断定。

为了解决异样路线偏移检测的问题，思考到不同的产品及业务需要，咱们设计并实现了以下两大类检测解决方案，上面进行简略的介绍。

▍3.2 “ 少而不同 ” 绕路检测

该类场景次要是检测繁多、多数绕路订单的异样状态，该类订单在 OD 束缚下，与其余失常雷同 OD 下其余失常订单轨迹空间散布存在显著的差别，次要体现为间断地呈现离群轨迹点，所以能够将咱们的工作转化为实时离群轨迹点检测，检测办法能够由以下局部组成：

• 路线形态表白

轨迹路线形态表白的目标次要是压缩轨迹，同时保障形态信息和压缩率；同时也要平滑轨迹，去除停留点与噪点。咱们采纳了 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 自适应窗口判断示意图。

▍3.3“多而不同”封路检测

基于“少而不同”的思路针对极少数用户轨迹偏移的异样检测次要是为了解决司乘纠纷、轨迹平安等问题；“多而不同”次要是少数用户在同 OD 空间束缚下，呈现了群体性的路线偏移，该景象往往象征路网的状态产生了变更而导航仍旧依照产生变更前状态布局，从而导致用户的个体被迫绕路。因而针对路网状态异样，以路线关闭为例，咱们提出了一种基于 Siamese LSTM (孪生长短期记忆网络) 与 LSPD（缺失路段模式检测办法）的轨迹时空模型来解决路网关闭检测问题。相干工作发表在 GIS 畛域国内会议 ACM SIGSPATIAL  2019 (International Workshop on Ride-hailing Algorithms, Applications, and Systems)(SIGSPATIAL 2019 RAAS) 该模型次要构造如下：

该模型次要分为两个模块，第一个算法模块是基于工夫序列流量信息相似性建模，该模型能够引入经典的 Siamese LSTM 网络，并交融注意力机制与自定义损失函数，实时刻画历史同期流量曲线与以后流量曲线的相似性，从而在线检测流量异样。因为采取了与历史同期（例如本周一与上周一）的流量序列建模，因此对流量天然降落及稳定具备很强的鲁棒性。

基于 Siamese LSTM 流量异样检测能够对全路网空间的流量异样进行实时检测，其检测的后果须要更强的证据佐证路线异样，因而，咱们设计了第二个算法模块 LSPD，该算法侧重于通过群体用户行为的异样判断第一个算法模块后果的可解释性与概率性，次要思维是统计同 OD 下路线模式的散布变更，不同于轨迹异样检测算法 (iBOAT) 在 OD 场景下关注“少而不同“的异样轨迹，咱们重点关注“多而不同“的用户群体性异样行为，例如某时间段内历史用户集中呈现了绕路事件，则通过咱们的 LSPD 算法模块能够精确定位到哪些路段可能呈现了路线关闭以及产生产生该类事件的置信度有多大。

以北京市某处路线关闭事件为例，该路线在下午 17 时左右产生路线关闭，咱们的零碎在 18 时通过 Siamese LSTM 深度网络检测出该路线存在显著的流量异样，异样置信度为 0.99，随后，该事例被零碎流转至 LSPD 检测模块寻求更多的轨迹证据佐证该路线确实存在路线异样，在该模块，咱们的算法检测到在部分起起点（OD）的作用下，用户的出行形式曾经产生了微小的变动，之前少数用户抉择右侧红色路线，而以后状态下，用户多抉择左侧蓝色路线（红色路线的反对度从 30 升高到 6，而蓝色路线的反对度则由 3 回升至 43），从而被零碎整体判断该路线呈现了路线异样，即路线关闭。

4. 总结

在以后的工业实际中，数据挖掘也经常和一些热门词汇联席呈现，比方人工智能、机器学习、大数据、数据分析、数据迷信等，如下图所示。

相比于其余概念，数据挖掘不强调利用何种伎俩，更强调目标：从数据中提取信息。在这个意义上讲，数据挖掘人造是交叉学科，须要从业人员具备统计、机器学习、大数据乃至高并发后盾服务、数据可视化等复合技能。另一方面，目前的人工智能技术水平仅仅达到刻画相关性的阶段，尚不能进行通用推理或者常识学习，所以须要从业者对钻研的畛域具备肯定先验常识，并理解如何利用这些常识从数据中提取有高价值信息。这两个特点决定了畛域数据挖掘的门槛十分高，这影响了数据价值的疾速挖掘和落地。笔者所在团队承当了公司外部很多开掘工作，比方平安驾驶行为检测、路网开掘、交通事件、天文画像、出行模式分析等等，更多的数据挖掘工作因为排期和资源限度无奈疾速反对，而需求方因为高技能门槛无奈自行对数据进行加工和价值提取。

咱们下一步的指标是尝试将轨迹数据挖掘能力中台化或者平台化，可能将算法、工程、大数据、可视化等能力凋谢进去，大幅升高数据挖掘老本，使得数据的价值能被最大化利用。实际上这一挑战不是咱们团队或者公司独有的，互联网公司可能会存在无奈以适合的老本从数据中提取价值的问题，导致数据挖掘技术只在多数高 ROI 场景下失去利用。行将到来的 5G 和万物互联时代，这一问题会更加重大。欢送对此感兴趣的同学退出咱们，一起钻研和摸索如何解决这些挑战。

本文作者

2017 年退出滴滴，轨迹开掘团队负责人，负责基于多模态交融的路网情报发现与路网状态更新、轨迹开掘、地图平安特色平台等工作。

2016 年退出滴滴，负责基于多源大数据的路网更新方向的算法工作，钻研趣味点包含时空异样检测、出行模式开掘、路网生成等。

2018 年退出滴滴，在滴滴从事轨迹模式开掘、用户异样行为检测、路线关闭检测等工作。

团队招聘

滴滴地图与公交事业部轨迹开掘团队利用滴滴海量的出行数据，对路线情况/交通流量/司机驾驶习惯进行建模，应用数据挖掘和机器学习技术发现路网情报和行程异样，晋升滴滴用户的出行体验和平台效率。

团队长期招聘研发工程师，包含机器学习、大数据、策略架构等方向，欢送有趣味的小伙伴退出，可投递简历至 diditech@didiglobal.com，邮件请邮件主题请命名为「姓名 - 应聘部门 - 应聘方向」。

延长浏览

内容编辑 | Charlotte
分割咱们 | DiDiTech@didiglobal.com

滴滴技术 出品