移動群智感知下的交通流速缺失數據恢復算法

張建宗，陶 丹

(北京交通大學 電子信息工程學院信息處理與人工智能研究所，北京100044)

1 引 言

隨著社會的發展，機動車數量逐年增加，交通擁堵問題成為現代城市面臨的主要問題.為了減輕城市路網的壓力，對交通狀態進行有效的評估顯得尤為重要.近年來，我國大中城市在主要道路布置了大量交通傳感器(比如：攝像機、環路感應器)進行交通狀態監測，但這種方式部署困難且維護成本較高.隨著移動終端處理器、內存等硬件設備的快速發展和提升，攝像頭、麥克風、GPS、陀螺儀、加速度計等傳感器嵌入到以智能手機、平板電腦為代表的移動智能終端中.在此背景下，人們提出了一種新型的感知模式——移動群智感知[1]，即利用城市中廣泛存在的移動智能設備以及車輛，通過群體間有意識或者無意識的協作完成感知任務.由于移動群智感知模式下的感知節點分布廣泛、移動靈活，因此被廣泛應用在智能交通領域[2].其中，利用探測車數據進行城市規模的交通狀態評估就是較為常見的一種應用[3].探測車是安裝有GPS等信息采集設備的車輛，能夠周期性的將車輛位置以及行駛狀態上傳至控制中心，基于此，能夠利用某時間段內路段上的流速來表征交通狀況.由于探測車在城市范圍內的概率分布，因此當探測車數量足夠大時，使得城市級的交通狀態評估成為可能.另外，安裝在探測車上的GPS設備的普及也極大的降低了系統成本.然而，受到探測車規模的限制，導致車輛在時空上分布不均勻，此時在使用探測車數據進行交通狀態評估時存在著數據缺失，這是其應用于交通狀態評估時的主要困難之一[4].

為實現對城市級交通狀態的有效評估，得到完整的城市交通狀態地圖，需要對缺失的交通數據進行準確恢復.近年來積累了一系列利用探測車評估交通狀況的研究成果.基于公交車數據，Herring等[5]提出了一種概率模型框架來預測主干道的行程時間分布，將交通狀態建模為耦合隱馬爾可夫模型以估計模型參數.然而，這種方法需要通過現場研究和大量探測數據進行訓練.Zhu等[4]將出租車作為路況感知的探測車輛，隨后分析路況數據在時空上的結構性特點，利用低秩矩陣填充技術推測出沒有探測車經過的路段的路況信息，以此實現大范圍的路況評估；然而該方法在數據缺失程度較大時數據恢復的效果不太理想.隨著機器學習的發展，更多研究學者嘗試學習數據特征以實現數據恢復.Zhang等[6]將圖像超分辨率的概念應用于交通流量數據感知重建.Zhang等[7]利用卷積神經網絡模型學習出租車交通流模式，進而預測下一時刻的交通流分布矩陣，然而，這些重建過程都是“網格化”分布節點的數據采樣過程，與群智感知網絡節點非均勻感知過程不盡相同.由此，本文研究利用有限探測車數據進行城市級交通狀態評估，針對路網提取、交通流速矩陣獲取以及缺失數據恢復等開展了一系列研究工作.

2 交通流速缺失數據恢復框架

如圖1所示，為了實現城市級交通狀態評估，本文提出了交通流速缺失數據恢復框架.探測車會實時的向接收中心發送其運行狀態以及位置信息，本文以某一時段內某一路段的探測車速度表征交通運行狀況.首先對數據進行預處理，刪除冗余數據并清理停滯點，其次根據GPS數據獲取道路中心點完成路網提取，再次對其進行時空劃分，并計算細粒度下的交通流速，進而得到表征交通狀況的交通流速矩陣.在此基礎上，本文充分考慮數據間的時空相關性，改進壓縮感知稀疏基進而完成交通缺失數據恢復，達到路況評估的目的.

圖1 交通流速缺失數據恢復框架Fig.1 Traffic velocity missing data recovery framework

2.1 數據預處理

同一輛探測車在行駛過程中，GPS終端會周期性地將GPS數據發送到控制中心.由于設備或者噪聲等影響而產生的錯誤數據會直接影響路網提取的精度，進而影響后續的交通狀態評估.數據預處理是路網提取的前提，主要包括清除冗余數據與消除停滯點兩方面.

2.1.1 清除冗余數據

由于數據傳輸誤差，會造成越界數據的存在，常見的如車頭方向超出[0°，359°]，或者GPS點超出研究地圖的經緯度范圍，對此類數據設置閾值范圍進行清理.此外，數據中存在全部字段值均相同的情況，清除掉這些冗余的定位數據，以提升路網提取的效率.

2.1.2 消除停滯點

由于本文將出租車作為探測車進行研究，分析出租車運營特性可知，車輛在商場、車站等地常常停滯待客，或是乘客上下車也會造成數據變化微小，通常此類停滯點數據在整體數據中占比較大，且無法提供有效的路況信息，應當刪除此類數據.同時，考慮到道路交叉口信號燈變化周期等情況，本文將連續5分鐘車速為0的數據當成停滯點進行清除.

表1為部分預處理后的數據示例，經過數據預處理后，數據剔除率高達55.67%.

表1 部分預處理后數據示例Table 1 Samples of partial preprocessed data

2.2 路網提取

在城市交通地圖中，由于探測車一般分布在道路上，而其他地方的探測車數據分布量較小，因此可以將研究區域劃分為網格，并計算網格內探測車密度，設置合理的閾值篩選出作為道路主干道的網格，并擬合形成路網，以此達到路網提取的目的.這種基于探測車數據的路網提取方法不僅可以對現有的道路網絡進行修正，還為后續的交通流速計算提供了基礎.本文將路網提取分為道路中心點提取和道路中心點擬合兩步.

2.2.1 道路中心點提取

基于網格思想，考慮到經緯度與現實距離的換算關系，同時考慮道路實際寬度，將GPS數據在空間維度以2×10-5°(約為2米)為邊長進行網格劃分，這樣能保證較小的運算復雜度同時在形成路網時誤差較小.

設定網格內軌跡點密度閾值Q1、鄰域內網格數目閾值Q2和聚類半徑E，當網格密度大于密度閾值Q1時則將此網格判定為路網網格，如果某路網網格E鄰域內的總路網網格數量大于Q2，則通過聚類算法將E鄰域內包含的網格轉化為聚類點，聚類點坐標由鄰域內所有路網網格決定.

2.2.2 道路中心點擬合

由于城市道路復雜多變，故本文采用了準均勻B樣條曲線擬合方法，該方法能夠在擬合過程中將首尾端點擬合到曲線上，得到實際路網形狀的曲線.基于網格密度的路網獲取如算法1所示.

算法1.基于網格密度的路網獲取算法

輸入：GPS數據集合I{p1，p2，…，pn}，密度閾值Q1、Q2和聚類半徑E.

輸出：路網矩陣R

1.以2×10-5°進行網格劃分，得到網格矩陣N；

2.for網格矩陣中每個位置Nij；

3. 計算網格內GPS數據密度K；

4. 如果K大于Q1，則形成新的集合C，并計算坐標值；

5.end for；

6.return聚類點集合C={C1，C2，…，Cn}；

7.for聚類點集合C中每個網格Cij；

8. 計算網格質心坐標；

9.end for；

10.return網格質心坐標集合D={D1，D2，…，Dn}；

11.對集合D進行準均勻B樣條曲線擬合；

12.return路網數據R

進行路網提取前后的對比效果如圖2(a)、圖2(b)所示.由圖可以得出：通過篩選網格密度過低的網格，可以有效地清除主干道路以外的數據點和人跡罕至的小路數據，且道路形狀保存較好.

圖2 路網提取前后對比Fig.2 Comparison before and after road network extraction

2.3 時空劃分

1)時間劃分：由于城市道路狀態在時間上變化頻繁，因此在對道路進行狀態評估時需要將其劃分為一定的時間粒度進行研究.圖3分別是以5分鐘、10分鐘和15分鐘為時間粒度下的數據缺失情況.由圖可知：雖然進行時間劃分時時段越長數據缺失率越小，但過長的時間間隔不能及時反映交通狀況的變化.因此考慮到路況變化周期，本文選取5分鐘作為時間粒度.將一天時間劃分為288(12×24)個時間片段，在以5分鐘為時間粒度時，數據缺失率高達85.3%.

圖3 不同時間粒度下數據缺失率Fig.3 Comparison ofthe levels of data missing at different time granularities

2)空間劃分：對于一條道路來說，尤其對于距離過長、交通狀態差別或變動較大的路段，難以用一個流速表征整條路段的信息.為此，本文將道路劃分為若干個子路段，用子路段的流速能夠更好地表示道路的交通狀態.

考慮到城市路網中各道路被交叉口自然分割，形成存在一定拓撲結構的路段，本文將道路交叉口作為路段劃分的自然分界點.對于長度大于0.5km的自然路段，利用公式(1)對其進一步劃分為若干子路段，

n=(?L」+1)×2

(1)

其中，n為某一路段被劃分的個數，L為路段長度，單位km.經過子路段劃分后過長的路段被劃分為長度在0.25～0.5km之間的子路段.

經過路段劃分，將研究區域內的路網劃分為了432個路段.由此完成了數據的時空劃分.

2.4 流速計算

通常車輛在道路上的行駛速度能夠直接反映道路的通行狀況，因此本文將路段內車輛流速作為評價交通狀態的指標.通常人們在計算交通流速時是通過計算某一路段內經過車輛的速度的平均值或是通過車輛的行駛軌跡與時間估計流速，但這種方法在樣本極差較大時或是車輛數目較少時會帶來較大的誤差.因此本文區分兩種典型情形并設計了一種自適應的流速估計方法.

1)樣本數大于δ且極差大于μ，此時說明該路段內通過的車輛較多，但不同車輛間車速有著較大的差異.因此根據樣本數據的奇偶性，利用公式(2)計算該路段內的流速的中位值.式中v為路段內流速，un為第n個車速數據.

(2)

2)樣本數小于δ或者樣本數大于δ且極差小于μ，此時說明了該路段內通過的車輛較少，或是車輛較多且不同車輛間的車速差別不大，使用公式(3)計算該路段內的流速.

(3)

自適應的流速估計方法采用均值計算的思想，設置參數在數據滿足一定條件下使用中位值法以避免離群點的影響.本文隨機節選8個路段計算其流速，圖4為不同流速計算方法的結果對比.相比傳統平均值法、中位值法，本文設計的流速計算方法更接近準確值，為后續的交通狀態評估奠定了堅實的基礎.

圖4 不同流速計算方法的對比Fig.4 Comparison of different velocity calculation methods

通過數據預處理、路網提取、時空劃分以及流速計算等一系列處理，得到了存在缺失的交通流速矩陣.交通流速矩陣示例如表2所示.這樣，可以將探測車數據轉化為交通流速矩陣，矩陣的行列對應著路網的路段和時段，由此可以更加方便地進行時空建模和數據恢復.

表2 交通流速矩陣示例Table 2 Sample of traffic velocity matrix

3 基于時空相關性的壓縮感知數據恢復算法

皮爾遜相關系數是刻畫變量之間關聯性常用的參數，因此本文選取皮爾遜相關系數來揭示交通流速數據間的時空關聯，對于二維向量存在：

(4)

實驗選取了同一路段相鄰7個時間片段和同一時段相鄰的7個路段分別計算其相關系數，結果如圖5(a)、圖5(b)所示.分析圖中數據可知：編號越接近的時段或路段其皮爾遜系數越大，路段(時段)間隔小于3時系數基本都在0.8以上，數據間有著強烈的時空關聯性.

圖5 時空相關性Fig.5 Spatio-temporal correlation

由于探測車數量有限，對數據進行時空劃分后使得數據存在大量的缺失.近年來對探測車進行交通數據恢復時通常認為數據缺失是無規律的，然而通過分析上一章節得到的流速矩陣發現：矩陣中數據缺失存在著一定的規律.根據缺失數據的位置特點，將數據缺失情形分為以下3種：

1)隨機缺失：交通流速缺失元素隨機的分布在矩陣的各個位置.如果缺失的數據在流速矩陣中表現為分散的維度小于等于3(例如1×3、2×1)的行列矩陣，則將此類情形歸為隨機缺失.產生這種情況的原因可能是不同時段不同路段探測車的概率分布所致.

2)整塊缺失：交通流速缺失數據導致流速矩陣中出現大塊的空白情況，即缺失數據在流速矩陣中呈現為行列皆大于2(例如3×3、3×4)的子矩陣，則此類情況為整塊缺失.產生此情況的原因可能是某一區域探測車長時間未覆蓋.

3)行列缺失：交通流速矩陣中某行或某列數據連續缺失，表現為元素大于3的行矩陣或者列矩陣(例如4×1、1×5)，則此類情況為行列缺失.產生這種情況的原因可能是連續一段時間內沒有探測車經過或是一段道路長時間未被探測車覆蓋.

特別地，一些特殊情形可以劃分為3種缺失情形的組合，不再贅述.

本文改進了壓縮感知算法的稀疏基，以避免大范圍數據缺失帶來的影響，將缺失數據的預測問題建模成稀疏向量的恢復問題.在此，設計了一種基于時空相關性的壓縮感知數據恢復算法STC-CS(Spatio-Temporal Correlation based Compressed Sensing).

交通流速往往在時間上平滑變化，即在兩個相鄰的時間粒度下交通流速值變化較小，因此設計時間稀疏基矩陣T：

(5)

則流速si在矩陣T下的投影為γt=Tsi，令φt=T-1，則流速可以稀疏表示為si=φtγt.

由于城市路網之間往往存在著一定的拓撲結構，這種拓撲結構揭示了數據間的空間相關性，因此設計空間稀疏基矩陣：

(6)

由上所述，分別從時空兩個角度考慮設計了稀疏表示基，將其進行Kronecker積運算就可以得到交通流速的稀疏表示基：

φ=φt?H

(7)

則交通流速矩陣可以進行稀疏表示為：

si=φα

(8)

假設帶有缺失的流速矩陣為si，定義矩陣W∈Rm×n表示S中是否缺失

(9)

假設完整的流速數據為S，則：

si=S⊙W

(10)

由上述公式可知，矩陣W的第i行表示時間序列中的數據是否缺失，而缺失數據的預測就是利用未缺失的數據作為測量值恢復原數據.由此設計觀測矩陣：

(11)

如果矩陣ψi∈RMi×K在(m，n)處的值為1，表明第m個測量值是在第n個時段得到的.就可以得到觀測矩陣：

(12)

令y表示si的觀測值，則矩陣si觀測向量可表示為：

y=ψφα

(13)

已知y、ψ、φ，就可以通過求解凸優化問題求解α，進而恢復交通流速數據.

4 實驗仿真

本文基于移動群智感知思想，使用探測車數據進行路況評估.數據來源為東莞市1000輛出租車采集的約25萬條數據(1)OpenData2[EB/OL].http：//www.openits.cn/openData2/604.jhtml.，時間跨度為10天，覆蓋范圍為經度23.0°～23.07°E，緯度113.7°～113.84°N，每條探測車數據包含車輛編號、位置、時間、車輛速度以及車頭方向等信息.

本文設計了兩組對比實驗：隨機缺失情形下不同數據缺失程度對比與50%數據缺失程度下不同缺失情形對比.實驗與3D形函數時空插值修復法(3D-SHAPE)[8]、基于灰色GM(1，N)模型[9]、基于統計學的插值計算法(SI)以及最近鄰算法(KNN)這4種方法進行對比.其中，3D-SHAPE是將數據的時空相關性加入到3D函數中進行數據恢復.基于灰色GM(1，N)模型是基于灰色殘差GM(1，N)模型的數據修復算法.SI與KNN是依據相鄰數據間關系進行數據恢復.

為了比較以上方法在本文實驗數據集下的恢復結果，本文采用均方根誤差(RMSE)、均絕對誤差(MAE)、平均絕對值誤差率(MAPE)作為性能評價標準.

1)隨機缺失情形下的數據恢復效果

為了比較隨機缺失情形下不同數據缺失程度的數據恢復性能，本文選取了數據缺失程度分別為30%、50%和80%的數據，并使用上述5種算法對缺失數據進行恢復.數據恢復性能如表3所示.

表3 不同缺失程度下數據恢復性能對比Table 3 Comparison of data recovery performances at different evels of data missing

分析可知：當數據缺失程度較小時，由于未缺失數據能夠提供較多的信息，因此5種數據恢復算法都能夠較為準確的恢復缺失數據.其中SI算法和KNN算法的恢復效果相較于其他3種算法略差.在數據缺失程度為50%和80%時，SI算法和KNN算法的恢復性能顯著下降，而另外3種考慮數據時空特性的數據恢復算法恢復的交通流速數據更加準確，更接近實際中的交通流速數據.在數據缺失程度為50%時，3D-SHAPE算法、GM(1，N)算法和STC-CS算法的MAPE值基本相同，但在MAE與RMSE的表現上各有優勢.當數據缺失程度進一步加大時，由于缺乏臨近數據的支持，導致SI算法和KNN算法的性能表現變得更差.3D-SHAPE算法與GM(1，N)算法恢復效果略有下降，而本文所提的STC-CS算法由于是基于數據時空特征將數據稀疏表示，重構原始數據進而恢復缺失數據，因此恢復效果優于其他算法，仍然能夠較為準確地恢復缺失數據.

2)不同缺失情形下的數據恢復效果

該實驗將數據缺失程度統一設定為50%.隨機缺失情形下的數據恢復效果與表3(b)實驗條件、實驗結果相同；整塊缺失與行列缺失情形下，塊/行列的規模和數目是隨機的.表4為5種算法在3種不同缺失情形下的數據恢復效果.

表4 不同缺失情形下的數據恢復性能對比Table 4 Comparison of data recovery performances at different missing cases

通過分析可知：相較于整塊缺失與行列缺失，隨機缺失下由于缺失數據均勻分布，使得5種數據恢復算法的表現最好.行列缺失情形下本文所提的STC-CS算法的數據恢復效果相較于3D-SHAPE與GM(1，N)性能略優.在整塊缺失情形下由于大塊數據的缺失使得塊中心位置的參考數據變少，導致5種數據恢復算法的誤差變大，但相比較而言本文提出的算法恢復效果表現最佳，這是由于STC-CS算法將原始交通流速矩陣映射到其他維度，有效地避免了上述現象.

5 總 結

充分考慮探測車數據的時空特征，本文開展交通流速缺失數據恢復研究.設計了基于網格密度提取路網的方法，提出了自適應的路段流速計算方法，進而得到交通流速矩陣，基于數據時空特征改進了壓縮感知的稀疏基實現有效數據恢復.一系列實驗驗證本文所提方法在缺失程度較大時能夠有效地恢復缺失數據.