基于路徑旅行時間分析的交通異常檢測方法

王 璞，熊雨沙，王騁程，鄭治豪，魯恒宇

(中南大學(xué)交通運輸工程學(xué)院 長沙 410075)

交通異常狀態(tài)檢測是當前交通領(lǐng)域中一個非常重要的研究方向。迄今為止，國內(nèi)外已有的相關(guān)研究多數(shù)利用了線圈[1-2]、視頻[3-5]、紅外傳感裝置[6]等固定傳感設(shè)備采集數(shù)據(jù)。然而，由固定傳感設(shè)備采集的數(shù)據(jù)多限于檢測器斷面[7]，使交通異常檢測受到了很大局限。隨著全球定位系統(tǒng)(GPS)的日益普及，許多城市已可以實現(xiàn)對移動對象的實時跟蹤，用裝有GPS接收器的車輛作為移動傳感器來采集交通狀態(tài)信息，具有成本低、靈活性強、數(shù)據(jù)量大等優(yōu)點[8]。近年來，基于車載GPS數(shù)據(jù)的研究主要集中于車輛路徑選擇模式及路段異常判別兩個方面。

在車輛路徑的選擇模式方面，文獻[9]將路徑分割為若干子路徑，通過比較子路徑組成的相關(guān)多維向量，找出其中的異常子路徑，從而發(fā)現(xiàn)城市的異常路徑選擇行為；文獻[10]挖掘相同OD之間的不同路徑，提出了用流量構(gòu)成描述向量的方法，挖掘人類出行異常模式子圖，并利用社交媒體數(shù)據(jù)進行異常信息的補充；文獻[11]提出了基于車輛移動軌跡在線檢測異常軌跡的算法。這類方法研究重點在于發(fā)現(xiàn)人類的出行規(guī)律。

在路段異常判別方面，文獻[12]通過比較觀測路段與其他路段的相似性，構(gòu)造包含歷史趨勢信息的狀態(tài)向量，提取出離群點作為異常值；文獻[13]通過比較路段真實值流量和期望值流量，判斷路段是否為異常路段。基于路段的異常判斷能直觀清晰地反映路段通行情況，但缺乏對路段之間內(nèi)在聯(lián)系和相互作用的融合，難以確定異常產(chǎn)生的根源并進行疏導(dǎo)；文獻[14]針對車輛運行狀態(tài)如速度、加速度等的變化，推測當前行駛路段是否異常，但這類方法需要考慮不同等級路段固有屬性對車輛通行狀態(tài)的限制，應(yīng)用難度較大。

為了解決現(xiàn)有交通異常檢測方法遇到的難點，本文提出一種基于路徑旅行時間分析的交通網(wǎng)絡(luò)異常檢測算法。該算法以Map-matching技術(shù)和DBSCAN聚類算法為基礎(chǔ)，且與傳統(tǒng)方法相比具有以下特點：

1) 以路徑為研究對象。

與基于路段的交通異常檢測方法相比，基于路徑的交通異常檢測具有以下優(yōu)點：首先，該方法可以獲得更多樣本量，減小偶發(fā)情況對整體檢測結(jié)果的影響。其次，該方法能綜合考慮連續(xù)路段交通狀況的累加影響，對不同程度交通狀況的檢測結(jié)果更為精確。最后，異常路徑的發(fā)現(xiàn)能直觀顯示交通異常狀況影響區(qū)域，多個異常路徑的累加更容易形成交通異常子網(wǎng)，便于發(fā)現(xiàn)交通異常的影響程度及傳播規(guī)律。

2) 以旅行時間為判斷標準。

本文利用浮動車GPS數(shù)據(jù)得到的路徑旅行時間數(shù)據(jù)能夠避免路段固有屬性比如車道數(shù)、路面狀況等對上述指標的影響，無需相應(yīng)的路段參數(shù)即可對交通狀況進行判斷，方法簡單，通用性強。

1 路網(wǎng)數(shù)據(jù)與出租車GPS數(shù)據(jù)

1.1 路網(wǎng)數(shù)據(jù)

使用由圖1所示，26 242個節(jié)點和43 134條邊組成的高精度深圳路網(wǎng)數(shù)據(jù)。為了提高算法效率，將城市分割為83×43個1000 m×1000 m的地理子區(qū)，以地理子區(qū)為單位進行交通異常檢測。

1.2 出租車GPS數(shù)據(jù)

采用由13 584輛配備GPS接收器的出租車采集的GPS數(shù)據(jù)，平均數(shù)據(jù)采集頻率為15 s/次，使用2014年10月所有工作日共916 851 503個GPS坐標記錄。由于出租車空載尋客時一般車速較慢，路段速度不具有代表性，因此刪除出租車在空載狀態(tài)下的GPS數(shù)據(jù)。由于少量GPS采集設(shè)備故障，還需要對GPS數(shù)據(jù)進行清洗，刪除出租車日出行次數(shù)(由載客狀態(tài)轉(zhuǎn)變?yōu)榭蛰d狀態(tài)為一次出行)大于500次的GPS設(shè)備所產(chǎn)生數(shù)據(jù)。為保證單位時間內(nèi)充足的GPS記錄數(shù)量，只使用6:00-23:00時間段的數(shù)據(jù)。經(jīng)過以上數(shù)據(jù)預(yù)處理，平均每天有13 446 868條出租車坐標點記錄被保留下來。

2 出租車行駛路徑的獲取

在一個地理子區(qū)中，滿足以下條件的GPS軌跡點組成軌跡 T = p1→ p2→ … → pn。

1) GPS軌跡點有可能匹配到與其臨近的任意一條路段上，所以需要采用緩沖半徑公式，以GPS軌跡點為中心確定搜索范圍，選擇范圍內(nèi)的路段作為候選匹配路段，有：

式中，參數(shù)α是道路網(wǎng)定位誤差；參數(shù)w是單向道路的寬度；參數(shù)β是車輛定位的最大誤差；參數(shù)m是車輛寬度[15]。經(jīng)調(diào)研，深圳市最寬道路為深南大道，路面凈寬80 m，除去16 m綠化帶寬度，單向道路寬32 m，其他參數(shù)的取值參考文獻[15]：α=5，β=10，m= 2 ，得到ρ=30。本文將搜索范圍略微擴大，取值35 m，并刪除35 m范圍內(nèi)沒有路段的GPS軌跡點。

2)pi對應(yīng)的時間標簽值遞增。

3)pi和pi+1之間的時間間隔小于45 s。

如圖1所示，虛線框表示一個地理子區(qū)，圖中p1→ p2→…→ pn為地理子區(qū)中一條滿足條件的軌跡。

圖1 深圳路網(wǎng)和地理子區(qū)GPS軌跡

為了計算出租車的行駛路徑和路段的通行速度，使用ST-matching地圖匹配算法[16]將GPS軌跡匹配到路段上。該算法以路徑為匹配對象，結(jié)合了路網(wǎng)拓撲結(jié)構(gòu)和地理信息，是一種全局的地圖匹配算法，對低頻的GPS數(shù)據(jù)也能保持較高的匹配精度，并能方便地獲取路徑和路徑的旅行時間。算法步驟如下：

1) 獲得候選路徑。

對于一條GPS軌跡 T = p1→ p2→…→ pn，當pi與路段的距離小于d=35 m時，將加入pi的候選匹配邊集合中，pi在上的投影則為pi的第j個候選匹配點，將n個軌跡點相鄰兩點的候選匹配點兩兩組合，可得到該軌跡的若干條候選匹配路徑。

2) 空間分析。

ST-matching算法中，路網(wǎng)的地理信息和拓撲結(jié)構(gòu)都被用來評價候選匹配路徑與GPS軌跡的匹配程度，地理信息評價值用觀測可能性來衡量，拓撲結(jié)構(gòu)評價值用傳遞可能性來衡量。

觀測可能性用pi與的距離來衡量pi匹配到的概率。定義pi匹配到的觀測可能性 f ()為：

式中， di-1→i=dist(pi-1,pi)為pi-1與pi之間的歐式距離；為和的最短路徑長度。

3) 路徑匹配。

匹配可能性最高的路徑為T的最終匹配路徑為：

圖2表示一條待匹配軌跡 T = p1→ p2→…→pn，三角形標識的點都是待選的候選匹配點，p5和p6各有兩個候選匹配點，實線和虛線分別為兩條候選匹配路徑，經(jīng)計算，經(jīng)過和的路徑匹配度更高。該路徑的旅行時間為起點與終點，即p1與p6的時間標簽的差值，pi-1到pi的行駛速度為：

式中， w(i-1,t)→(i,s)是pi-1到pi的最終匹配點之間的最短路徑； t(i-1,t)→(i,s)是它們之間的時間差。如果同時間段一條路段上有多個速度記錄，可計算得到路段的平均通行速度。

由于所使用的路網(wǎng)精度較高，可能存在因起點或終點不在同一條路段的細微差別，而將兩條軌跡判定為經(jīng)過不同路徑的情況。為了保證路徑判定有一定的容差率，將地理子區(qū)進一步劃分為100 m×100 m的格子，如果兩條軌跡途經(jīng)的細分網(wǎng)格相同，則認為它們經(jīng)過同一條路徑。

圖2 地圖匹配算法示例

3 路徑的交通異常判斷算法

本文采用基于密度的DBSCAN聚類算法[17]對通過同一條路徑所有軌跡的旅行時間進行聚類。該算法需要確定兩個參數(shù)：EPS鄰域和最小樣本數(shù)MinPts，參數(shù)的選擇對聚類的結(jié)果影響較大，較小的EPS和較大的MinPts會導(dǎo)致算法對路徑旅行時間異常的判斷不夠敏感，反之，會過于敏感。使用歐式距離計算兩點之間的距離為：

30 min是目前交通狀態(tài)短時預(yù)測常用時間段之一[18]，且能保證一條路徑有足夠數(shù)據(jù)量來進行聚類分析，所以，使用30 min作為時間窗，定義每個時間窗的數(shù)據(jù)為一個聚類數(shù)據(jù)集，并將聚類數(shù)據(jù)集中的每個實例除以數(shù)據(jù)集中實例的最大值，實現(xiàn)所有實例的歸一化。根據(jù)文獻[17]對參數(shù)EPS值和MinPts值選取方法的介紹，先確定MinPts取值為4，然后找到4-距離的突增位置來確定參數(shù)EPS的值，方法如下：首先計算每兩個實例之間的歐式距離，找到與每個實例最鄰近的第4個實例，二者之間的距離稱為4-距離。然后對一個聚類數(shù)據(jù)集中實例的4-距離進行概率統(tǒng)計，發(fā)現(xiàn)絕大多數(shù)數(shù)據(jù)集的4-距離概率呈指數(shù)分布。最后對概率分布進行指數(shù)擬合，選取斜率為-1處對應(yīng)的4-距離作為EPS值。圖3a是對某個聚類數(shù)據(jù)集的4-距離進行歸一化后的概率分布圖，圖3b是將圖3a中局部區(qū)域放大后，做擬合曲線斜率為-1處的切線，對應(yīng)的橫坐標為EPS取值。

經(jīng)過聚類后，聚類數(shù)據(jù)集中的實例被分成m個團簇，定義擁有最多實例的團簇為中心團簇，中心團簇中最大值為初始異常閾值，初步認為數(shù)據(jù)集中、所有小于初始異常閾值的對象是初始正常值，初始正常值的平均值 t為路徑在所測時間段的正常旅行時間。由于存在少量聚類數(shù)據(jù)集，使實例的4-距離不滿足指數(shù)分布，且擬合的效果不穩(wěn)定，為減少DBSCAN參數(shù)對閾值計算結(jié)果的影響，根據(jù)常用異常檢測方法三倍標準差準則[19]，計算初始正常值的標準差σ。定義 t+3×σ為路徑在該時間段內(nèi)的異常閾值。如圖4所示，圖4a為某條路徑10月份工作日10:20-12:30所有旅行時間，虛線為每30 min路徑旅行時間的異常閾值。每10 min計算一次待測路徑的平均旅行時間，圖4b為某條待測路徑在10:20-12:30不同時間窗進入地理子區(qū)時，路徑的平均旅行時間，與對應(yīng)時間窗的異常閾值對比，虛線空心點所表示的旅行時間值超出了異常閾值，由圖可知，異常持續(xù)了50 min，即11:00-11:50。

圖3 DBSCAN算法參數(shù)選擇

圖4 路徑旅行時間異常判斷

4 地理子區(qū)交通異常檢測案例

交通事故或交通擁堵等交通異常事件的顯著特點是造成路段通行速度降低，因此，大量的研究基于路段的速度、流量等屬性進行路段狀態(tài)識別。然而，這種異常識別方法也存在一些不足。一些路段的速度表現(xiàn)出不規(guī)則的波動給交通異常判斷帶來困難，如圖5a和圖5b所示。因此，選擇路徑的旅行時間作為研究對象，能綜合考慮多個鄰接路段的通行情況，減小異常檢測誤差，如圖4b所示。

圖5 路段速度計算

使用上一節(jié)闡述的方法計算各路徑的異常閾值，圖6為某地理子區(qū)中檢測出的4條異常路徑旅行時間隨時間的變化，4條路徑的旅行時間均在第6個時間窗開始突增并超出異常閾值，于第8個時間窗附近達到相對高峰之后逐步恢復(fù)正常。由圖6a可知，該條路徑正常通行時的旅行時間約50 s，而旅行時間異常值最高達280 s。

圖6 路徑旅行時間隨時間變化

為衡量異常路徑覆蓋路段受影響程度，引入R值進行計算：計算路徑在各個時間窗的受影響程度=平均旅行時間/t，取受影響程度最大的時間窗進行各路段R值的計算：

式中，vr為一個月中該時間窗的平均通行速度；va為受影響程度最大時間窗的平均通行速度。圖7a所示為路徑1在第8個時間窗依次經(jīng)過路段vr和va的對比。

圖7b中加粗路段為異常路徑覆蓋路段，由R值分布可看出各路段受影響的程度。

圖7 路段速度分析

為驗證該交通異常檢測結(jié)果，從新浪微博中搜索信息，發(fā)現(xiàn)如表1所示事件。

表1 微博實例

該事件初始定位在圖7b所示的地理圖標位置，事件描述與所測交通異?；鞠喾?，微博所反映的事件發(fā)生在11:28，為圖6中箭頭所示位置。而算法在11:00就檢測出交通異常，比微博發(fā)出提前28分鐘，微博發(fā)出時間基本位于路徑旅行時間最大的時間窗內(nèi)，從微博內(nèi)容可看出此時交警還在趕往途中。圖6b展示了交通異常的產(chǎn)生和消散過程，圖7b展示了交通異常的集中區(qū)域。

將地理子區(qū)內(nèi)所有交通異常路徑經(jīng)過的節(jié)點和邊組成的網(wǎng)絡(luò)定義為“基于路徑的交通異常子網(wǎng)”，如圖8a中的粗線所示。建立基于路段的交通異常子網(wǎng)用于比較。定義路段在檢測時間窗的車輛行駛平均速度μc，路段在工作日相同時段的車輛行駛平均速度為μm，標準差為σe，當μc＜ μm-3 × σe時認為路段的車輛行駛速度發(fā)生異常。提取車輛行駛速度發(fā)生異常的邊組成的網(wǎng)絡(luò)，得到“基于路段的交通異常子網(wǎng)”，如圖8b、圖8d所示。

在發(fā)生交通事故的時間窗：基于路徑的交通子網(wǎng)連成一個大團簇，如圖8a所示；而基于路段的交通異常子網(wǎng)分布較為雜亂，有幾個零散的團簇，如圖8b所示。在交通運行正常的時間窗：基于路徑的交通子網(wǎng)根本不存在，如圖8c所示；而基于路段的交通異常子網(wǎng)還是有一些零散的小團簇存在，這是由于個別路段偶發(fā)速度波動引起的，如圖8d所示。可以看出，基于路徑的交通異常子網(wǎng)在交通正常與異常狀態(tài)下的區(qū)別更為明顯，有助于提高交通異常判斷的準確性，上述結(jié)果也體現(xiàn)了基于路徑的交通異常檢測方法的優(yōu)勢：有利于減小偶發(fā)情況對整體檢測結(jié)果的影響。

圖8 異常網(wǎng)絡(luò)規(guī)模

5 結(jié) 束 語

近年來，隨著數(shù)據(jù)分析挖掘技術(shù)的發(fā)展，路段旅行時間和擁堵的判別方法已經(jīng)日益成熟，出行者在出行時可以借助各種軟件，查看到各個路段的實時路況信息，比如擁堵情況、運行速度、限速情況等。但是，局部的、可以自行消散的路段異常出現(xiàn)頻繁，使交管部門較難準確識別出真正存在嚴重問題的區(qū)域。

本文針對有一定規(guī)模的道路交通異常突發(fā)情況，提出了基于路徑旅行時間的交通異常檢測算法。該算法不同于常用的基于路段通行能力和狀態(tài)進行異常檢測的方法，可以減少由單一的路段信息和車輛偶然因素導(dǎo)致的異常誤判，檢測出具有規(guī)模的、自行消散困難的、異于歷史通行狀態(tài)的交通異常網(wǎng)絡(luò)，為交通管理部門提供可信度更高的交通異常監(jiān)測結(jié)果。算法在現(xiàn)實路網(wǎng)和真實數(shù)據(jù)環(huán)境下的應(yīng)用證明其檢測的交通異常時空信息及時有效，所檢測出的帶有時間和空間信息的交通異常，能為交通管理者疏導(dǎo)交通提供重要管控和決策信息。

本文研究得到霍英東青年教師基金基礎(chǔ)研究課題(141075)及中南大學(xué)創(chuàng)新驅(qū)動計劃(2016CSX014)的資助，在此表示感謝。