---

期刊: 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條高速公路，然后重新估計參數，并重新進行交通擁堵檢測。

參考文獻