【论文阅读】-- Visual Traffic Jam Analysis Based on Trajectory Data

---

期刊: IEEE Transactions on Visualization and Computer Graphics（发表日期: 12/2013）
作者: Zuchao Wang; Min Lu; Xiaoru Yuan; Junping Zhang; Huub Van De Wetering

摘要

在这项工作中，我们提出了一个基于 GPS 轨迹的城市交通拥堵可视化分析交互式系统。对于这些轨迹，我们制定了提取和导出交通拥堵信息的策略。清理轨迹后，将它们与道路网络相匹配。随后，计算每个路段的交通速度并自动检测交通拥堵事件。空间和时间相关的事件在所谓的交通拥堵传播图中串联起来。这些图表形成了交通拥堵及其在时间和空间上的传播的高级描述。我们的系统提供了多种视图，可以在传播图层面和路段层面上直观地探索和分析整个大城市的交通状况。通过在北京收集的 24 天出租车 GPS 轨迹进行案例研究，证明了我们系统的有效性。
关键词：交通可视化、交通拥堵传播

1 引言

交通拥堵是现代城市的一个严重问题。它们带来了相当大的经济损失、增加了出行时间并加剧了污染。政府花费大量资金试图监控和了解交通拥堵，但由于交通拥堵的复杂性，这似乎很困难。复杂性之一是不可预测性。有时会发生交通堵塞，有时则不会。另一个复杂性是交通拥堵是动态的且相互关联的。例如，交通拥堵可能从一条道路传播到其他道路。由于这些复杂性，对交通拥堵进行全自动分析非常困难，需要大量的经验和知识。在这项工作中，我们提出了一个可视化分析系统来研究交通拥堵的模式及其传播。我们的系统结合了自动计算和人类知识。我们首先从 GPS 轨迹中提取交通拥堵，并从中构建传播图。然后我们设计了一个可视化界面来探索交通拥堵模式和交通拥堵的传播。据我们所知，之前在视觉分析方面还没有深入研究这些交通拥堵方面的工作。

传统的交通拥堵检测方法基于路边传感器，如感应环或雷达 [31]，并且仅监控几个关键点 [25]。然而，基于 GPS 的方法理论上可以监控完整的道路网络。这使我们能够更好地研究交通拥堵传播。此外，不需要安装昂贵的路边设备。以前基于 GPS 的交通拥堵检测方法要么只研究单独的拥堵 [10, 34]，从而提供道路网络的分散交通信息，要么无法将交通拥堵归因于特定道路 [29, 15]。这些作品中的交通拥堵数据不适合视觉探索。在这项工作中，我们从 GPS 轨迹数据导出道路交通拥堵数据集，并通过构建传播图来构建检测到的交通拥堵。我们的数据更适合视觉探索。

在可视化界面中，如图1所示，我们允许用户进行多层次的探索，从单条道路的交通模式到整个城市的交通拥堵状况。我们支持各种过滤技术来查询特定类型的传播图，并且允许用户对它们进行比较。
我们的主要贡献是：

• 我们提出了一种从嘈杂的 GPS 轨迹数据中自动提取交通拥堵的流程。我们的数据是结构化的且受道路限制，因此适合视觉探索。
• 我们设计了一个可视化界面来探索交通拥堵及其传播。探索是多层次的，支持交通拥堵传播图的过滤和比较。

2 相关工作

我们的相关工作部分分为关于流量事件检测的分析小节和关于流量可视化和传播图可视化的两个视觉小节。

2.1 交通事件检测

也许检测交通事件最商业化的技术是通过类似雷达的传感器[31]。分析路边摄像头的视频流也有助于了解交通情况 [53, 22]。然而，这两种技术都需要安装高成本的设备，并且只能在道路沿线的固定位置进行监控。相比之下，GPS技术更便宜并且能够监控整个路网。因此，最近的大部分研究都集中在分析 GPS 轨迹上。

数据挖掘社区长期以来一直致力于轨迹数据的研究。他们研究了不同类型的模式 [23, 26]。有关概述，请参阅 Cheng 等人的书 [54]。

我们最感兴趣的是交通拥堵检测。交通拥堵是重要的交通事件。它们通常具有行驶时间长或速度低的特点。许多交通拥堵检测算法都是基于道路速度计算[18]，或低速车辆集群检测[10, 34]。 Bauze 等人的交通监控系统还可以通过低速检测交通拥堵[13]。我们使用基于道路速度计算的方法来检测交通拥堵。它不仅提供少数拥堵地点和几个时段的交通状况数据，而且还提供更大的区域和时段的交通状况数据。这样的数据更适合自由探索。我们的工作与上面引用的工作不同，我们关注的是交通拥堵的传播。

克罗等人。 [25] 研究了带有信号交叉口的路段上的绿波。然而，这与交通拥堵传播不同，他们的场景比我们的城市网络简单得多。最近，郑等人。发表了一篇论文[29]，研究交通异常值的因果关系。他们首先将城市划分为中等规模的区域，然后研究区域之间的交通流量。异常值被检测并排列为异常值树。我们的传播图构建使用相同的想法，但我们的重点是交通拥堵事件，而不是异常值。更重要的区别是，交通拥堵最初发生在道路上，而不是区域之间的连接处。因此，当用户检测到异常链接时，很难探索和解释他们的结果。尽管在后来的工作中[15]他们将异常链接与异常路线相关联，但仍不清楚长路线上的异常发生在哪里。在我们的结果中，我们可以直接看到交通拥堵在道路上传播，正如它们的实际情况一样。我们的模型更适合可视化分析。

道路网络中的交通状况也可以通过概率图模型（PGM）进行建模[27, 37]。该技术能够从历史数据中了解每条道路交通状况的时间变化以及道路之间的空间依赖性。因此，它可以模拟宏观交通，并可以对未来的交通状况做出预测。不过，这里我们主要是想总结历史数据，支持用户探索。我们的交通拥堵检测和传播图构建算法已经总结了历史交通，其结果很容易理解和探索。相比之下，PGM 虽然更通用，但其参数更难调整，也更难理解、探索和评估。

2.2 交通可视化

交通数据的主要类型是轨迹数据。在这种情况下，可以使用所有轨迹可视化技术。所有轨迹的概述是视觉分析的第一步。它通常需要聚合。密度图[51]通过视觉聚合提供了概述。它绘制轨迹密度并帮助识别“热点”。密度图还可以显示多变量轨迹的密度[42]和提取的事件[41]。与密度图不同，空间聚合[12]和时空聚合[6, 43]等技术通过数据聚合提供概述。它们将空间和时间维度离散化为许多区域、流或容器。对每个离散的时空单元进行统计，例如时间仓中的一个区域。然后将这些聚合信息可视化。

微观行为分析是另一项常见任务。在这种情况下，必须单独处理轨迹。赫特等人。 [21]展示了如何选择具有特定位置和属性的轨迹。郭等[19]提出一个分析道路交叉口交通的系统。刘等人。 [28]提出了一个研究城市路线多样性的系统。

时间信息在轨迹可视化中至关重要。时空立方体[20,24,7]使用z轴来表示时间，但存在视觉混乱的问题。轨迹也可以表示为时间线 [9, 16]，但空间信息会大量丢失。可以从这些时间序列中提取事件[11]。

对于轨迹属性，Tominski 等人。 [46] 和冯·兰德斯伯格等人。 [49]已经解决了他们的视觉分析问题。

上面引用的一些著作研究了轨迹事件。然而，它们都没有关注这些事件的相互作用，也没有一个关注交通拥堵。我们的工作旨在深入研究交通拥堵及其相互作用。

尽管大多数交通可视化使用轨迹数据，但有些交通可视化使用其他类型的传感器数据。帕克等人。 [35]研究交通事故数据。他们设计了一个链接视图界面，​​以可视化事件的空间、时间和多维方面。用户可以选择、过滤和聚类这些事件。皮林格等人。 [38]研究隧道内的监控录像。它们自动检测不同类型的事件并确定优先级，并在空间和时间上标记它们。对于每个事件，用户都可以查看原始视频。两者都关注交通事件，但都没有关注这些事件的交互。我们的工作研究这些相互作用，并使用轨迹数据，这需要不同的事件检测算法。

2.3 传播图可视化

传播图可以通过动画和小倍数来可视化。然而，这些技术有局限性[39]。因此，人们还设计了其他视觉隐喻。传播图的空间、时间和拓扑方面可以通过单独的技术可视化，例如 FlowMap [48]、大规模序列视图 [47] 和图布局 [44]。在一个视图中可视化所有方面仍然具有挑战性。在我们的工作中，我们应用了动画、流程图和图形布局技术。

3 概述

在本节中，我们首先提出设计要求。之后我们描述输入数据，并定义交通拥堵数据模型。最后我们介绍了系统的工作流程。

3.1 设计要求

为了研究交通拥堵，我们需要一个数据模型，根据这个模型我们提取并构造交通拥堵数据。它应该满足以下三个要求：

R1：完整 我们要求提供基本的交通拥堵信息，包括位置和时间。此外，即使没有交通堵塞，速度信息也应该始终存在。它可以帮助用户了解交通状况如何变化，并检查交通拥堵检测是否适当。

R2：结构化 我们要求模型中的交通拥堵是相互关联的：我们不仅对不同地点和时间的个别交通拥堵感兴趣，还对这些交通拥堵如何相关以及它们如何从一个位置传播到另一个位置感兴趣。

R3：道路边界 我们要求在道路上定义交通拥堵，并沿着实际发生的道路网络传播。这有助于用户在视觉探索过程中将交通拥堵数据与现实世界的知识联系起来。

探索和分析数据模型的可视化界面，应满足以下要求。

R4：信息性 我们要求系统显示交通拥堵的所有关键信息，包括位置、时间、传播路径、传播规模和道路速度。

R5：多层次 我们要求可以在多个层次上探索交通拥堵。最低级别应该是单个路段上的拥堵行为。在此基础上，我们需要分析不同路段之间的交通拥堵传播，并对不同的传播进行比较。从最高层面来说，我们要求研究整个城市的拥堵状况。

R6：可过滤 我们要求根据空间、时间属性和传播大小来过滤交通拥堵。这样，我们就可以关注特定类型的交通拥堵，并对其进行更深入的分析。

3.2 输入数据说明

我们使用GPS轨迹数据和路网数据作为输入，来计算和分析交通拥堵。 GPS轨迹数据包含很多轨迹。每个轨迹由采样点列表组成。每个采样点都有一个位置记录（二维数据的“经度、纬度”）、时间戳时间、速度幅度、速度、移动方向角度，以及可选的一组属性“a0、a1、…an−1”。这些采样点按时间升序排列。两个连续采样点之间的每个部分称为轨迹段。

道路网络由节点和道路组成。每个节点都有一个空间位置。它可以是交点或形状点。每条道路都包含一个有序的节点列表，用于定义道路的空间位置和形状。道路可以是单向街道或双向街道。

我们的 GPS 数据集是在容易发生交通拥堵的北京市记录的真实出租车数据集。该数据集包含 28,519 辆出租车的 GPS 轨迹。据政府报告[5]估计，它们占北京所有持照出租车的43%，占北京四环内交通流量的7%。该数据集时间跨度为2009年3月2日至25日，共24天，包含379,107,927个采样点，数据大小为34.5GB。唯一的属性是布尔值passengerState，表示出租车上是否有乘客。采样率为每 30 秒 1 点。然而，60%的采样点缺失，因此，连续两个点的时间差经常超过3分钟。

我们的道路网络数据集来自 OpenStreetMap 的 jXAPI [17] 的查询。我们提取从 116.109E 到 116.673E 以及从 39.743N 到 40.119N 空间范围内的所有道路。这提供了 40.9MB 的数据，包含 169,171 个节点和 35,422 个路径。

3.3 交通拥堵数据模型

我们的模型构建了三种类型的信息：道路速度、交通拥堵以及交通拥堵之间的关系。在我们的模型中，时间被离散化为时间段。路径上的两个方向被单独处理，每个方向都作为有向路径（缩写为 dWay）。 dWay 和时间仓是最小的空间和时间单元。

道路速度信息给出了道路状况的基本描述。对于每个 dWay，在每个时间 bin，都会有一个速度记录。如果无法估计速度值可以为空。

交通拥堵信息汇总了所有检测到的交通拥堵。它由交通拥堵事件（简称为事件）列表组成。事件被定义为三元组“d,t0,t1”，其中 dWay d 是事件的位置，整数 t0 和 t1（其中 t0 ≤ t1）分别是事件的开始和结束时间 bin。因此，整个事件发生在跨越 t1 − t0 + 1 个时间段的区间 [t0…t1] 内。

交通拥堵之间的关系用交通拥堵传播图（简称为图）来表征。图是事件的有向网络，定义为“V，E”，其中V是一组事件，E是一组事件之间的有向链接。它既是非循环的又是连通的。有向链接表示为 e1 → e2，这意味着事件 e1 导致 e2，或者等效地，e2 是由 e1 引起的。一个事件可以由 0 个或多个事件引起，也可以导致 0 个或多个事件。对于每个图，可以导出一条空间传播路径（简称路径），它是 dWays 的有向网络。它可以有循环。路径中的链路 d1 → d2 意味着相应的交通拥堵从 dWay d1 传播到 d2。

3.4 工作流程

我们的视觉分析工作包括两个阶段。第一阶段是预处理，我们从输入数据开始，提取适合我们模型的交通拥堵数据。第二阶段是视觉探索，我们探索预处理的数据。图 2 概述了我们的系统。我们将在第 4 节中解释预处理阶段，在第 5 节中解释视觉探索阶段。

4 预处理

我们的预处理阶段包括六个步骤。前两个步骤提高了输入数据的质量。在步骤1路网处理中，我们通过过滤掉不相关的数据、合并和分割方式以及纠正错误来提高路网质量。在步骤 2 GPS 数据清理中，清理轨迹。一件显而易见的事情就是消除 GPS 错误。为了稍后准确估计道路速度，我们还过滤掉不反映交通状况的站点，例如停车。

为了估计道路速度，我们执行另外两个步骤。在步骤 3 地图匹配中，我们将 GPS 轨迹与道路网络进行匹配，以将轨迹速度与道路速度相关联。经过这一步，每个轨迹采样点被映射到dWay（不是车道）上的一个位置，每个轨迹段被映射到路网上的一条路径。在步骤 4 道路速度计算中，我们根据映射到 dWay 的轨迹的速度来估计 dWay 在某个时间点的速度。这可以通过平均轨迹速度来执行。由于映射轨迹数量不足以及步骤 2 中停车案例过滤不完整等原因，该估计可能不准确。

在最后两步中，传播图是根据交通拥堵事件构建的。在步骤5交通堵塞检测中，根据速度检测交通堵塞事件。对于每个 dWay，连续时间段的异常低速被视为交通拥堵事件。最后，在步骤 6 传播图构建中，我们根据检测到的交通拥堵事件的时空关系来预测它们之间的因果关系。

在本节的其余部分中，我们将更详细地讨论预处理步骤。有关其参数设置的更多详细信息请参阅附录。

4.1 路网处理

从OpenStreetMap下载的路网数据不仅包含高速公路，还包含水路、建筑物等。因此，我们首先从数据中提取所有可行驶的路线。然后我们过滤掉那些不与主网络相连的微小路段，并确保所有道路都连接在一起。之后，我们希望两个dWay之间的航向关系是清晰的、单向的。因此，我们重建路网数据中的道路，使得两条道路只能在其端点相交。在重建中，我们要求每条路的长度小于1km，这样保证了空间分辨率。

4.2 GPS数据清理

对于GPS数据，我们去除了五种记录：不相关数据、错误数据、低采样数据、非堵塞数据和微小轨迹数据。我们使用一组过滤器来实现此目的。

道路网络空间范围之外的数据是不相关的，并被过滤器 F1 删除。过滤器F2和F3消除了关于时间或位置的错误数据的问题。它们通常表现为具有相同时间戳的两条记录或高速段。

F1：不切实际的坐标 我们删除了 [116.109E, 116.673E] x [39.743, 40.119N] 范围之外的采样点。

F2：重复时间戳 如果轨迹中存在具有相同时间戳的点，我们只保留第一个出现的点，并删除其他具有相同时间戳的点。

F3：高速 我们认为高于 90km/h 的轨迹段速度是不现实的。在这种情况下，我们删除轨迹段并将轨迹分成两部分。

低采样率会导致轨迹具有长段或长时间间隔。我们的速度计算基于轨迹段，因此我们需要段的起点和终点之间的实际速度变化才能准确插值。在这种情况下这是不可能的。因此，过滤器F4和F5将它们去除。

F4：长距离 我们删除长度超过 2 公里的路段。

F5：长时间 我们删除时间间隔超过10分钟的片段。非拥堵停车数据是由于停车、乘客上下车、停车等待乘客而产生的。这不包括等待绿灯，因为长时间等待绿灯意味着拥堵。过滤器 F6 去除第一个停车箱，F7 去除乘客箱。

F6：停车 我们假设出租车在 30 分钟内停留在 50m 半径范围内，实际上是在停车，因此删除这些点。

F7：等待乘客 我们删除 PassengerState 属性发生变化的段。这将轨迹分成具有恒定乘客状态的轨迹。然后，我们删除较短轨迹的开头和结尾处的停靠点，假设出租车司机通常在放下旧乘客后立即等待新乘客，或者等到有新乘客。对于在开始或结束时停止，我们假设几个位置相同的点，或者速度为零的点。

F6 使用停止检测算法实现[36]。我们并不打算像原论文中那样识别有趣的点，而是停车站，包括GPS位置严重振荡的情况（图3（右））。因此，我们在他们的算法中只使用欧几里得距离，而不是沿路径的距离。

微小的轨迹大多是由过滤器生成的小片段。通过将它们渲染到屏幕上，我们发现它们几乎无法使用。我们通过过滤器 F8 删除它们。

F8：微小轨迹 我们删除所有最多 5 个采样点或长度小于 500m 的轨迹。

滤波器按以下顺序应用：F1、F2、F3、F4、F5、F6、F7，其中滤波器 F8 直接在每个滤波器之后应用，以消除微小轨迹。

4.3 地图匹配

我们采用ST匹配算法[30]进行地图匹配，因为它适合低采样率的数据。然而，该算法不能直接用于我们的工作中，我们对其进行了三点调整。首先，由于我们的路网数据中大部分路段都没有限速记录，所以T匹配是不可能的。因此，我们只进行S匹配。原论文[30]中的分析表明，准确率下降了2%。我们认为这是可以接受的。其次，由于我们的路网数据存在一些错误，例如道路方向错误和缺失道路，因此我们允许轨迹采样点和轨迹段不匹配。否则，就会出现很多错误，如图 4 所示。就准确估计道路速度而言，我们假设缺少匹配比错误匹配更好。没有候选匹配点的采样点被认为是不匹配的。传输概率V小于阈值Δ的轨迹段被认为是不匹配的。最后，我们将每个轨迹采样点与一条 dWay 上的一个位置进行匹配，因此我们需要知道出租车在每个采样点的行驶方向。这是通过简单地查看相邻采样点的匹配位置在后处理步骤中实现的。

4.4 道路速度计算

将轨迹映射到道路网络后，我们可以使用轨迹速度来计算道路速度。在此步骤中，我们仅使用轨迹的匹配部分。我们选择时间段大小为 10 分钟。对于每个 dWay 和每个时间 bin，我们提取该时间 bin 内通过 dWay 的所有出租车轨迹。我们重建出租车的运动，假设它们遵循地图匹配结果，并在两个连续采样点之间以恒定速度移动。因此，我们可以计算出每辆出租车的平均行驶速度。在删除速度异常高的出租车（通过异常检测算法[1]检测到）后，我们对剩余出租车的平均速度进行平均，得到道路速度。速度平均是按轨迹计算的，而不是按采样点计算的。我们还记录支持率，即剩余出租车的数量。支持度越高，道路速度计算的精度越高。我们定义当支持度≥最小支持度时速度估计是有效的。默认值为最小支持 = 5。

4.5 交通拥堵检测

计算出道路速度后，我们对每条 dWay 进行交通拥堵事件检测。我们的想法是基于对 dWay 自由流动速度的估计，使用每个 dWay 的速度阈值。速度限制可能是一个很好的估计。不幸的是，我们的数据中没有它。克罗等人。 [25] 根据非高峰时段速度记录估计自由流速度。然而，在北京，不同的 dWay 的非高峰时间可能有所不同。相反，我们按升序对 dWay 的所有有效速度进行排序，并选择百分比 F% 位置处的速度值。然后，此 dWay 上的每个时间段，其有效速度小于自由流速度的百分比 C%，则被称为具有低速度。默认参数值 F = 85 和 C = 45，为我们提供了 400,985 个事件。

4.6 传播图构建

现在我们已经提取了所有 dWay 的事件，我们通过定义事件之间的有向链接来构建传播图。我们使用基于规则的方法。我们假设有向链接 e1 → e2 存在当且仅当 e1.t0 ≤ e2.t0 ≤ e1.t1，并且 e1.d 紧邻 e2.d 之前。前一个语句是一个时间约束，表示当 e2 开始时，e1 仍在发生。后一种说法是空间约束，表示两个事件在空间上是相连的，交通拥堵向后传播。后向传播是我们的假设，这意味着交通拥堵将以与交通流方向相反的方向传播。尽管尚未得到充分验证，但许多观察和实验 [14, 45] 支持这一点。我们有这个限制是因为我们的时间分辨率不够高。当我们观察到两条相邻道路同时拥堵时，从数据中并不清楚哪条道路通向哪条道路。在我们的道路网络中，通常会出现一条 dWay 领先于另一条的情况。一个例外是同一条双向街道上的两个方向。我们不在它们之间建立任何链接，因为这种传播与掉头交通流相关。根据经验，这种掉头交通流通常在总交通流量中不占主导地位，并且不太可能传播交通拥堵。此外，我们的测试表明添加此类链接会在构建的图表中添加相当大的噪音。

我们使用 STOTree 算法的修改版本 [29] 构建图，最终得到 226,227 个图，其中 162,429 个仅包含一个事件。我们计算每个图的空间传播路径和三个大小度量：事件数量、时间跨度和总距离。后者是图中所有交通拥堵事件的长度（以公里为单位）的总和。

5 可视化设计

根据3.1节的设计要求，我们为我们的系统提供了五个视图（四个窗口）。我们设计了一个基于像素的道路速度视图（嵌入图 1(b)）来显示一个 dWay 的速度和事件。我们设计了一个图列表视图（图1（c））来显示传播图，并设计了图投影视图（图1（e））来显示它们的拓扑关系。我们设计了一个空间视图（图1（a））来显示每个dWay上的交通拥堵密度，以及一个突出显示的图的传播路径。我们还设计了一个多面过滤器视图（图 1（d））来过滤传播图。

5.1 基于像素的道路速度视图

在我们的系统中，道路速度和交通拥堵事件携带低级别交通拥堵信息。在为他们设计可视化时，我们有两个问题。首先，我们需要一个紧凑的可视化，以便能够并排呈现多条道路以进行比较。其次，根据我们的经验，道路速度变化具有很强的每日和每周模式。在分析中呈现它们很重要。

考虑到这些问题，我们为 dWay 设计了一个基于像素的表格可视化，如图 5© 所示。每行代表一天，每列代表 10 分钟的时间间隔，每个单元格代表一个时间段。或者，该表可以通过黑色水平线分为每周块。我们使用单元格颜色来表示相应时间点 dWay 上的道路速度。色标如图 5(b) 所示：红色代表低速，绿色代表高速。对于没有有效速度估计的单元，我们使用灰色。鼠标悬停在单元格上会显示详细的速度信息，包括单元格的时间、速度值及其括号之间的支持度。

为了显示此 dWay 上的事件，我们在道路速度视图上绘制黑框。图 5© 说明了这一点。方框中覆盖的单元格对应于交通拥堵的时间段。具体来说，左/右边界表示事件的开始/结束时间。如果我们对事件比速度细节更感兴趣，我们可以使用像元大小来标记事件，如图 5(d) 所示。我们使交通拥堵事件中的单元（我们称为事件单元）比非事件单元更大。事件以这种方式弹出，并且不需要黑框来标记事件。当我们将道路速度视图嵌入到空间视图中时，这尤其有用，如图 1(b) 所示。然后，由于屏幕空间有限，我们不得不牺牲事件信息的速度。使用黑盒会严重隐藏单元格颜色。

在道路速度视图中，我们可以通过单击事件来突出显示交通拥堵传播图，然后该事件将用粗黑框标记（图 5©、(d)）。包含此事件的传播图将突出显示，并显示在空间视图中。

我们仅显示满足过滤器的单元格的信息，其他单元格变为灰色，包括时间范围（由时间过滤器定义）之外的非事件单元格以及不属于所选传播图的事件单元格。时间范围之外的事件有可能不是灰色的，只要其对应的传播图与时间范围相交即可。过滤后的道路速度视图如图 5(e) 所示。

5.2 图形列表视图

显示各个道路上的速度和事件后，我们考虑显示传播图。这是更高层次的信息，揭示了不同道路上交通拥堵的相互作用。在设计可视化来显示传播图时，我们有两个问题。首先，传播图有很多，但我们只能在屏幕上同时显示几个。其次，我们需要比较传播图。我们设计图表列表视图来满足上述要求。

为了减少要显示的传播图的数量，我们使用过滤和排序。我们在图投影视图（第 5.3 节）中有一个拓扑过滤器，在空间视图（第 5.1 节）中有一个空间过滤器，在属性过滤器视图（第 5.5 节）中有五个用于时间和大小的直方图过滤器。我们只显示满足这些过滤器的传播图。当图仍然太多时，我们对它们进行排序，只显示前 N 个图，通常 N ∈ [10, 50]。排序可以基于事件的数量、时间跨度或总距离。

为了比较传播图，我们制作了一个小型多重接口，如图 1© 所示。它将传播图显示为图标。这些图标以矩阵样式排列。每个图标代表一个图，并显示其空间传播路径、时间信息和三个尺寸测量值。传播路径的颜色表示每个位置的拥塞时间，红色为4小时，橙色为10分钟。当用户突出显示图形图标时，该图形的路径将在空间视图中详细显示。图 6 显示了图形图标的更详细设计。图标设计和矩阵布局一起允许并排比较传播图。然而，在矩阵布局中，两个相距较远的图很难进行比较。因此，我们允许用户固定有趣的图表。固定的图表在原始图标矩阵下方单独列出为图标，方便比较，并允许随时查看。除了固定之外，我们还允许用户选择一张图表并突出显示空间相似的所有图表。对这些相似图的搜索仅限于可见的前 N ​​个图。选定的图放在图列表的前面，而相似的图则按相似度递减的顺序紧接着放在其后面。所选图表及其类似图表的图标有红框。我们将两个图的空间相似性定义为其 dWay 集合的 Jaccard 系数 [2]。

5.3 图形投影视图

同样关注传播图层面，图投影视图总结了所有图的路径的拓扑信息。然而，大量的图表使得投影变得困难。我们的基本思想是首先将图划分为拓扑簇，然后对簇进行投影。为了创建聚类，我们通过删除所有中 dWay，即入度和出度均为 1 的 dWay，对每个图的路径执行拓扑保留简化。然后我们计算每个简化路径“I0, O0, I1, O1, …, In, On”的特征向量，其中Ii是入度为i的节点数，Oi是出度为i的节点数，n 是所有入度和出度的最大值。特征向量的每个维度都被单独归一化。具有相同特征向量的图被放入同一簇中。在我们的例子中，n = 4，我们得到 212 个簇。对于聚类投影，我们使用 MDS [52]。两个簇之间的距离定义为特征向量之间的欧几里得距离。界面如图1(e)所示。每个簇都呈现为一个点，颜色表示它包含的图形数量。颜色越深意味着图表越多。鼠标悬停会显示图形的确切数量，并使用 OGDF 库 [3] 的 Sugiyama 布局 [44] 渲染图形。传播方向是从上到下。用户还可以绘制套索来过滤此视图中的图形。

5.4 空间视图

我们需要对城市级别的交通拥堵进行概述并对传播图进行详细检查。这些任务是在空间视图中实现的。见图1(a)。

交通拥堵的空间密度用于提供城市层面的概览。该密度在每个 dWay 上定义为该 dWay 上的总拥堵时间。我们使用颜色来编码密度：深红色表示 dWay 最拥堵；红色表示不太拥堵，其次是橙色。灰色表示没有拥塞。

突出显示的传播图的路径呈现为黑色的流程图。我们特别关心路径的拓扑，例如起点/终点和合并/分支点。起点是“造成”堵塞的 dWays，而终点是“吸收”堵塞的 dWays。在分支点，一条 dWay 中的拥塞会传播到至少两条 dWay。在合流点，一条 dWay 中的拥堵至少是由两条 dWay 造成的。为了突出这些特征，我们使用黑色圆圈作为起点，使用黑色箭头作为终点。通过查看路径可以简单地发现分支/合并点。除了观看静态路径外，用户还可以播放传播动画。通过在空间视图中嵌入迷你道路速度视图，

我们允许用户检查多个 dWay 的速度和事件信息。绿色点画线段连接迷你道路速度视图和它代表的 dWay。用户可以创建、移动和删除迷你道路速度视图。将它们并排对齐可以让用户比较道路的速度模式。

用户可以绘制橡皮筋矩形来设置图形的空间过滤器。这由图 1(a) 中的绿色矩形表示。他们还可以播放轨迹动画。通过这种方式，他们可以粗略地验证检测到的交通拥堵，并进行详细的观察。

5.5 多面过滤视图

我们提供了五个交互式直方图来对传播图进行动态查询。图 1(d) 对此进行了说明。底部的两个直方图显示了交通拥堵的时间分布。一份按日期，一份按日时间。在日期柱状图的左上角，有两个按钮，允许用户仅观察工作日或周末的数据。顶部的三个直方图显示了事件数量、时间跨度和总距离的大小分布。在每个直方图上，用户可以选择一个范围。直方图上的五个范围查询，加上空间视图中的空间查询，以及图投影视图中的拓扑过滤器，构成了我们系统的整个过滤。这种过滤机制是交叉过滤的简化[50]。只有满足所有过滤器的传播图才会被选择，并列在图列表视图中。

我们为直方图提供两种视觉模式。在绝对模式下（图7（a）），我们仅显示通过过滤器的数据的统计信息，以橙色显示。箱的高度是线性比例的。在相对模式下（图7（b）），我们还将所有数据的统计数据显示为灰色背景。由于所有数据和通过过滤器的数据的尺度可能相差很大，因此 bin 的高度采用对数尺度。我们在直方图上标记突出显示的传播图的信息。图 7 显示了日期直方图中的标记（作为黑色三角形）和时间直方图中的标记（作为点画线覆盖的时间范围）。、

6 可视化结果和案例研究

我们的系统为用户提供多角度的复杂交通数据的可视化洞察。以下案例展示了我们视觉分析系统的能力和有效性。

6.1 案例一、路段层面探索与分析

通过道路速度视图，我们的系统为用户提供路段交通速度的聚合可视化。图 8 显示了北京的七个路段（dWays）。每个道路速度视图都可以清晰地直观地概括该路段的交通拥堵模式。我们可以观察到，对于大多数道路来说，早上6:00左右就开始出现交通拥堵，并且大多数工作日都会出现早、下午的交通高峰，而周末的交通则要少得多。图8（b）显示了北三环的一段路段，可以清楚地看到人们上班时的早高峰和人们回家时的晚高峰。对于靠近小学的道路，早高峰来得更早，因为家长在上班之前先送孩子上学（图8（c））。图 8(d) 和 (e) 显示了具有截然不同行为的道路的两个相反方向。这些差异可能会导致从家到工作地点的定向交通。图 8(f) 显示了另一种受当地活动严重影响的模式。这条路位于一个大型展览中心的南面，只有在有展览的日子才会拥堵。虽然上述大多数拥堵都具有一定的规律性和可预测性，但有些交通拥堵的发生更具随机性。机场快线路段（图8（g））通常交通顺畅，但偶尔也会因事故而出现拥堵。图8（h）所示的道路位于北京工人体育场以东，有很多酒吧。整个晚上的交通负荷更大。周五和周六晚间交通较早，因为周末人们会较早前往酒吧。

6.2 案例2.可视化传播图分析

通过过滤交通拥堵传播的时间、空间和大小属性，用户可以使用我们的可视化界面探索不同的交通拥堵传播图。可以在道路速度视图中检查详细的传播。图 9(a) 和 (b) 显示了两种不同的交通拥塞传播。图 9© 和 (d) 显示了它们的道路速度。图9(a)中的拥堵传播发生在北京西三环莲花桥路段。道路上的A处首先遭遇交通拥堵。由于明显的时间延迟，B 段和 C 段几乎同时变得拥堵。图 9(b) 展示了更复杂的交通拥塞传播。事情发生在北京北五环八达岭高速路口。这种传播是由两个来源引起的：D和H。首先H是拥塞的。随后，I、J、K 逐渐拥堵，但有一定延迟。当D拥堵时，F的一个分支E受到严重影响。与此同时，F也变得拥堵。当H没有拥塞时，I到K也都没有拥塞。 E继续拥堵，直到D不再拥堵。

6.3 案例3.拥塞传播模式探索

我们使用户能够比较某个区域在不同时间的交通拥堵传播图。例如，万泉河大桥位于北京四环西北角；参见图10(a)的右下角。图 10(b) 显示了该桥上某路段的速度。除3月18日数据缺失外，整个数据集呈现出较强的周期性。每个工作日，早上7点到10点左右就会出现交通拥堵，周末则上午的拥堵被下午的拥堵取代。为了详细研究工作日早上的传播情况，我们逐日列出它们，如图 10(a) 所示。我们发现，所有这些拥堵都源于中关村科技园区周围的道路，这个地区是高科技企业集中的地区。尽管交通拥堵传播图的某些分支有所不同，但这些图的主体是相同的，先从东到西，再到南。

7 讨论

我们系统中的预处理步骤需要许多参数。它们对于生成可用的交通拥堵数据以供进一步的视觉探索非常重要。然而，为这些参数找到正确的设置并非易事。目前，我们基于分布分析、经验以及与手动标记数据的比较来这样做。我们还对这些参数进行敏感性分析。此外，我们的可视化界面为用户提供了提取的交通拥堵数据的视觉反馈。当用户对结果不满意时，可以使用不同的参数重做预处理的最后两步。我们工作站上的北京出租车数据大约需要一分钟。

我们的工作重点是事件分析，并使用移动物体的动画来直观地评估检测到的交通拥堵。进一步的空间和时间分析是可能的。例如，通过根据路段随时间的速度变化对路段进行聚类，或者根据当时速度的空间分布对时间段进行聚类。时空和时空 SOM [8] 提供了这样的技术。我们将来会考虑的。

我们的工作研究交通拥堵的因果关系和传播。然而，研究交通状况的相关性也很重要。这可以使用 PGM 来完成。 PGM 提供了根据当前观测结果预测不同时间不同道路的交通状况的可能性。它还能够对负相关进行建模，这显然很有趣。我们考虑将 PGM 纳入我们的视觉分析中。

在智能交通系统中，事故前的预警比事故后的响应更重要，因为它可能有助于挽救生命和成本。对于交通拥堵，旅行者可能期望路线规划变得更加智能和适应性强。这显然在很大程度上取决于交通拥堵的预测性能。我们目前的工作更多的是堵塞后分析。然而，我们计划扩展我们的系统以包括实时预测。

最后，总结大量传播图是一项挑战。尤其难以将它们清楚地放入语义簇中，同时考虑空间、时间、大小和拓扑方面。我们的系统分别处理这些方面，并针对每个方面进行概述。

8 结论和未来工作

在这项工作中，我们提出了一个交互式视觉分析系统来分析现实的大规模道路网络中的交通拥堵。我们使用北京出租车 GPS 24 天轨迹以及来自 OpenStreetMap 的相应街道网络。在数据驱动的方法中，我们清除 GPS 轨迹中的传感器错误并修复道路网络中的明显错误。利用清理后的数据，我们可以准确地将驾驶轨迹映射到道路网络，然后计算道路速度。在估计每个路段的自由流动速度后，我们根据相对低速检测自动检测道路上的交通拥堵事件。这些事件在传播图中的串联显示了交通拥堵如何在空间上传播到相邻道路以及在时间上传播。然后，根据自动计算结果，我们构建了一个可视化界面，用于对检测到的交通拥堵信息进行交互式探索，既可以在路段上进行详细说明，也可以在地图上的空间视图和小倍数视图中进行更高级别的探索。传播图。我们通过有效过滤空间、时间、大小和拓扑来支持分析，并通过按大小和相似性排序提供图形的结构化可视化。最后，我们提供了一些案例研究来证明我们系统的有效性。我们的系统可以为用户提供多层次、多角度的洞察。

我们未来的工作包括改进交通拥堵模型、支持更多分析任务以及实现实时交通预测。我们还将尝试对传播图进行更好的视觉编码。我们考虑对我们的系统进行正式评估。

致谢

作者感谢Datatang和OpenStreetMap提供的数据，感谢匿名审稿人提出的宝贵意见和建议。该工作得到国家自然科学基金项目（No. 61170204）和国家自然科学基金重点项目（No. 61232012）的资助。

附录

我们的预处理步骤有很多参数。正确设置它们至关重要，但并非微不足道。我们在下面讨论参数设置。

A GPS数据清理

我们的 GPS 数据清理依赖于一组过滤器。他们都试图删除错误或无用的数据。适当的参数设置旨在在去除点的百分比R和噪声水平之间取得平衡。我们对其中大多数进行敏感性分析，显示如果参数略有变化，将删除多少或多/少的数据。我们使用 One-at-a-time 策略 [4]，并计算 R 对每个参数的偏导数。我们在表1中总结了过滤器参数。当前的参数设置删除了74.5%的数据，其中大部分是F6和F7删除的停止点。

B 地图匹配

采用Mao等人的技术[32]，通过与手动标记的数据进行比较来分析地图匹配结果。我们从数据集中随机选择 500 个轨迹，包含 14,632 个采样点并自动匹配它们。在允许不匹配的情况下进行手动校正后，我们将结果视为“基本事实”。基于“地面实况”的地图匹配精度定义为： 精度 = Σin=1 |Mi ∩ Ti|/ Σin=1 |Mi ∪ Ti|，其中 n 是轨迹数量，Mi 和 Ti 分别是分别是地图匹配结果和地面实况中第 i 条轨迹的有向路径集合。

我们选择 500 个轨迹中的 400 个来估计最佳参数：候选搜索半径 r、候选数量 k、正态分布标准差 σ（我们假设平均值 μ 为零）以及最小传输概率 Δ。原始STmatching论文[30]推荐r=50m，k=5，σ=20m，没有Δ，相当于Δ=0.0。测试 r ε {20m, 50m, 100m}, k ε {3, 5, 10}, σ ε {10m, 20m, 50m} 和 Δ ε {0.0, 0.2, 0.4, 0.6} 的组合，得到的准确度范围为81.6% 至 91.7%。这些组合中的最佳组合（r = 50m、k = 5、σ = 20m、Δ = 0.2）在剩余 100 条轨迹上的准确率达到 92.6%，我们用它来进行地图匹配。结果，5%的采样点和7%的轨迹段不匹配。

C 道路速度计算

参数min support的设置是预测的置信度和速度估计的数量之间的平衡（见图11）。如果用户想要准确的数据，那么他们会选择高值。如果他们想要更多数据，则价值较低。我们的默认设置是最小支持度 = 5。在此设置下，给定 ±4mph 误差范围，高速公路计算速度的理论置信度 [33] 在所有条件下保证高于 58%，在正常交通量下为 85% 。然而，对动脉的置信度相当低（44% 和 72%）。用户可以更改此设置。对于每个 dWay，我们定义一个 Coverage 值，它是具有有效速度的时间 bin 的比率，即 support ≥ min support。图 12 显示了结果。

D 交通堵塞检测

还通过与人工标记的数据进行比较来分析交通拥堵检测结果。我们从北京四环内的路网中随机选择 50 个高速公路路段 (dWays)。我们播放一天交通数据的动画，并手动标记拥堵时间段。这种标记有点主观，因为有时道路状况介于拥堵和畅通之间，有时该道路上的轨迹数量不足。在这些情况下，结果取决于人的判断。尽管如此，我们仍然假设标记数据是“基本事实”，据此我们计算准确度：准确度 = Σin=1 |Si ∩Li|/ Σin=1 |Si ∪Li|，其中 n 是dWays，Si 是第 i 个 dWay 检测为拥塞的时间 bin 集合，Li 是第 i 个 dWay 在“基本事实”中标记为拥塞的时间 bin 集合。

我们使用标记数据来估计最佳参数，包括自由流速度F的速度百分比和拥堵速度C的速度百分比。我们测试了F从100到70和C从60到30，两者的间隔都是5。结果如图13所示。虽然F=75、C=50的组合给出了最高的准确率，即79.7%，但它并不稳定。我们选择一个稳定的组合 F = 85,C = 45，其准确率达到 76.3%。

该标签提供了一种将人类偏好纳入交通拥堵检测的方法。例如，当用户只想确定且严重的交通拥堵时，可以相应地重新标记50条高速公路，然后重新估计参数，并重新进行交通拥堵检测。

参考文献