數(shù)據(jù)缺失環(huán)境下基于DCTPLS-PCA的路網(wǎng)速度預測研究

姚加林，朱闖

數(shù)據(jù)缺失環(huán)境下基于DCTPLS-PCA的路網(wǎng)速度預測研究

姚加林，朱闖

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

準確可靠的短時交通流預測是實現(xiàn)良好交通控制與誘導的基礎，由于設備故障和通信干擾等原因，交通數(shù)據(jù)經(jīng)常存在缺失現(xiàn)象，給交通流預測造成了很大困難。在數(shù)據(jù)缺失環(huán)境下，通過基于三維離散余弦變換的補償最小二乘回歸(DCT-PLS)算法對缺失數(shù)據(jù)進行修復，利用主成分分析(PCA)對修復后的數(shù)據(jù)降維，用K近鄰(KNN)算法預測路網(wǎng)中各路段速度，并計算預測誤差。以長沙市某路網(wǎng)為例，在數(shù)據(jù)完整和數(shù)據(jù)缺失2種情況下進行數(shù)值實驗。研究結果表明：DCT-PLS算法修復精度高于概率主成分分析(PPCA)和貝葉斯主成分分析(BPCA)；PCA降維能夠大幅減少預測時的計算成本；在數(shù)據(jù)缺失環(huán)境下，基于DCTPLS-PCA的方法在大幅降低計算成本的同時，能夠保證很好的預測精度。

數(shù)據(jù)缺失；DCT-PLS；PCA；路網(wǎng)；速度預測

隨著經(jīng)濟社會的快速發(fā)展，小汽車保有量急劇增加，由此導致了日益嚴重的城市交通擁堵問題。智能交通系統(tǒng)被認為是緩解城市交通擁堵的重要方案之一，交通控制與誘導是城市交通管理中的重要組成部分，在智能交通系統(tǒng)中發(fā)揮著舉足輕重的作用。而準確可靠的短時交通流預測是實現(xiàn)良好交通控制與誘導的基礎，因此研究短時交通流預測對于緩解城市擁堵具有重要意義。數(shù)據(jù)采集是實現(xiàn)交通流預測的第一步，然而在交通數(shù)據(jù)采集過程中，由于設備故障、通信干擾等原因，經(jīng)常存在數(shù)據(jù)缺失現(xiàn)象，這給準確的交通流預測造成巨大困難。在加拿大亞伯達7 a的交通數(shù)據(jù)中有近50%的數(shù)據(jù)存在缺失，某些時段缺失比例更是高達90%[1]。數(shù)據(jù)修復是處理缺失數(shù)據(jù)的常用方法，數(shù)據(jù)修復算法可分為3類，第1類為基于向量的修復方法，包括近鄰方法[2]，回歸補值方法[3?4]等。第2類為基于矩陣的修復方法，包括概率主成分分析(PPCA)和貝葉斯主成分分析(BPCA)[5?6]等。第3類為基于張量的修復方法，包括CP分解方法和Tucker分解方法[7]等。基于矩陣的修復方法具有修復精度高、速度快的優(yōu)點，在交通數(shù)據(jù)修復領域應用廣泛，PPCA和BPCA是其中常用的2種算法。但是當缺失率高時，上述2種算法的修復結果不盡如人意?；谌S離散余弦變換的補償最小二乘回歸(penalized least square regression based on three-dimensional discrete cosine transform，DCT-PLS)算法在高缺失率時仍能保證很高的修復精度[8?9]，本文首次將該算法引入交通數(shù)據(jù)修復領域。以往的研究[10?12]多是預測單個路段上車輛的速度，但是單個路段的交通信息對于交通管理與控制的指導作用有限，因此，本文以路網(wǎng)為研究對象，預測路網(wǎng)內各路段的速度，為交通管控提供更全面的信息。當研究對象由路段擴展為路網(wǎng)，帶來了數(shù)據(jù)量激增的問題，特別是對于數(shù)據(jù)驅動的預測方法而言，數(shù)據(jù)量的激增會導致難以承受的計算成本。為解決該問題，引入數(shù)據(jù)降維技術以降低計算成本。主成分分析(Principal Component Analysis，PCA)計算簡單，易于實現(xiàn)，是常用的降維方法，本文采用該方法對修復后的數(shù)據(jù)降維。綜上，在數(shù)據(jù)缺失環(huán)境下，本文首先采用DCT-PLS算法對缺失數(shù)據(jù)進行修復，然后應用PCA算法對修復后的數(shù)據(jù)降維，最后以該數(shù)據(jù)作為實驗數(shù)據(jù)，用K近鄰(K nearest neighbors，KNN)算法預測路網(wǎng)內各路段速度。

1 研究方法

1.1 DCT-PLS算法

其中：i表示第維的第個元素，n表示的第維的大小。

根據(jù)歸一化誤差，即可由DCT-PLS預測缺 失值。

1.2 PCA算法

PCA是一種統(tǒng)計方法。通過正交變換將一組可能存在相關性的變量轉換為一組線性不相關的變量，轉換后的這組變量叫主成分。其步驟為：

1) 數(shù)據(jù)標準化：設有個向量，個樣本點的矩陣，將矩陣標準化，得到矩陣矩陣的相關系數(shù)矩陣設為。

其中：

2) 計算矩陣的特征值與特征向量：解特征方程求得特征值λ(=1, 2, …,)然后求出特征值對應的正交化單位特征向量e(=1, 2, …,)

3) 計算主成分貢獻率及累計貢獻率

4) 計算主成分載荷

5) 計算各主成分得分

其中：為選取的主成分個數(shù)，其值取決于使用者選定的累計貢獻率閾值。

1.3 KNN算法

K近鄰(KNN)算法是一種典型基于數(shù)據(jù)驅動的算法，具有參數(shù)少，易于拓展的優(yōu)點。其算法步驟如下：

1) 將數(shù)據(jù)分成2部分，一部分作為訓練數(shù)據(jù)，另一部分作為測試數(shù)據(jù)。

2) 選定參數(shù)

3)維護一個大小為，按距離由小到大排列的最近鄰數(shù)組；維護一個大小為K的優(yōu)先級隊列。

4) 遍歷訓練數(shù)據(jù)，計算當前訓練數(shù)組與測試數(shù)組的距離，將該距離與最近鄰數(shù)組中最大距離max比較。

5) 若>=max，則舍棄該數(shù)組，遍歷下一個數(shù)組。若＜max，刪除優(yōu)先級隊列中最大距離的數(shù)組，將當前訓練數(shù)組存入優(yōu)先級隊列。

6) 遍歷完畢，計算優(yōu)先級隊列中個數(shù)組的多數(shù)類，并將其作為測試數(shù)組的類別。

2 實驗場景與數(shù)據(jù)處理

2.1 實驗場景

選取長沙市中心城區(qū)某一路網(wǎng)為研究對象，該路網(wǎng)內包含4個信控交叉口和26個路段。路段上的出租車GPS數(shù)據(jù)被用來估算該路段上車輛的平均速度。GPS數(shù)據(jù)包含以下信息：路段編號、每個路段上出租車數(shù)量、出租車運行速度、時間戳等。該數(shù)據(jù)的采樣間隔為2 min，因此每天采集720個數(shù)據(jù)。本文使用16 d共11 520個數(shù)據(jù)作為實驗 數(shù)據(jù)。

實驗路網(wǎng)圖如圖1所示，其中圖1(a)為衛(wèi)星圖；圖1(b)為路網(wǎng)拓撲結構圖，為方便表示和閱讀，將路段重新進行了編號。

圖1(a)中未被編號的建湘路將蔡鍔路和芙蓉路之間的人民路分為2個路段(即路段1070201/ 1070301，相反方向為1070303/1020703)，在此情況下，本文將同方向2個路段視為一個路段(路段11，相反方向編號12)，其速度值取2個路段上車輛速度的平均值。因此，實驗路網(wǎng)中總包含24個路段。

2.2 數(shù)據(jù)缺失形式

在數(shù)據(jù)采集過程中，由于設備故障、通信干擾等原因，采集到的數(shù)據(jù)經(jīng)常存在缺失的情況。根據(jù)缺失的形式不同，可以分為3種形式即隨機缺失、模塊缺失和混合缺失。本文中，在隨機缺失情況下，產生一系列隨機位置，該位置的數(shù)據(jù)缺失，用NaN代替。在模塊缺失情況下，產生一系列隨機位置，該位置及之后的個數(shù)據(jù)連續(xù)缺失(本文取10)，用NaN代替。值得注意的是，該隨機數(shù)序列中，各隨機數(shù)之間的差值不得小于-1。當數(shù)據(jù)混合缺失時，首先將數(shù)據(jù)平均分為2部分，一部分數(shù)據(jù)采用隨機缺失的方法處理，另一部分采用模塊缺失的方法處理。將數(shù)據(jù)分組可以避免出現(xiàn)同一個數(shù)據(jù)多次缺失的情況。

(a) 衛(wèi)星圖；(b) 拓撲結構圖

另外，為了衡量修復誤差及預測誤差，采用3個常用指標，即平均絕對誤差(Mean Absolute Error，MAE)、平均絕對百分比誤差(Mean Absolute Percent Error，MAPE)、均方根誤差(Root Mean Square Error，RMSE)。

3 數(shù)值實驗

3.1 修復算法比較

PPCA和BPCA是修復交通數(shù)據(jù)常用的算法，本文從修復精度和計算時間2個維度比較PPCA、BPCA與DCT-PLS。

實驗數(shù)據(jù)缺失率從10%開始，以10%的步長遞增至90%。因為數(shù)據(jù)缺失位置(或缺失起始位置)是隨機產生的，為了降低隨機因素對實驗結果的影響，每種缺失率下均進行10次重復實驗。

表1~3列出了10次實驗的平均MAPE(10次實驗結果方差很小，這里沒有列出)。值得注意的是，表中列出的時間為90次實驗的總時間。另外，在缺失率較高時，BPCA算法在短時間內(10 min)無法完成修復工作，因此，表中沒有列出其相應的修復誤差及總計算時間。

從表1可知，隨機缺失時，在各缺失率下，DCT-PLS的修復精度均最高。當缺失率超過70%時，DCT-PLS的修復精度比PPCA高出10%。PPCA的修復精度較DCT-PLS略低，但是其運行速度更快。BPCA在缺失率不超過50%時，修復精度與PPCA及DCT-PLS相當，但是隨著缺失率進一步增加，該算法難以在短時間內完成修復工作。

圖2 3種缺失形式示意圖

表1 隨機缺失下不同算法修復誤差

表2 模塊缺失下不同算法修復誤差

表3 混合缺失下不同算法修復誤差

模塊缺失時，由表2可知，當缺失率不超過50%時，PPCA修復精度最高，隨著缺失率繼續(xù)增加，PPCA的修復誤差增長較快。

DCT-PLS在高缺失率時優(yōu)勢明顯，當缺失率達到80%時，其誤差低于20%，且較PPCA低10%左右。BPCA在低缺失率時修復精度與PPCA及DCT- PLS相近，但是當缺失率較高時，該算法的計算成本迅速增加。

與模塊缺失類似，混合缺失時，由表3可得，缺失率較低時，PPCA修復較高，隨著缺失率增加，其修復誤差快速增加。隨著缺失率增加，DCT-PLS的修復誤差也逐漸增加，但是其誤差增長幅度小于PPCA,特別是缺失率高于60%后，其誤差增長明顯低于PPCA。BPCA同樣在低缺失率時修復精度較好，但是無法在短時間內完成高缺失率數(shù)據(jù)的 修復。

綜上所述，相較于PPCA、DCT-PLS，BPCA算法在修復精度和運算時間上均沒有優(yōu)勢。PPCA算法計算速度快，在低缺失率時，修復精度高，當缺失率不超過50%時，建議采用PPCA算法進行數(shù)據(jù)修復。DCT-PLS算法計算速度較PPCA略慢，但是在各種缺失率下，其修復精度均較高，特別是高缺失率時(缺失率>60%)，其修復精度明顯高于另外2種算法，因此在高缺失率時，建議采用DCT-PLS算法。后續(xù)的預測實驗中數(shù)據(jù)缺失率很高，因此采用DCT-PLS作為本文的修復算法。

3.2 預測實驗

3.2.1 實驗參數(shù)設定

本文將前15 d的數(shù)據(jù)作為KNN算法的訓練數(shù)據(jù)，第16 d數(shù)據(jù)作為測試數(shù)據(jù)，同時，根據(jù)經(jīng)驗將K近鄰算法中K值設為5。因為GPS數(shù)據(jù)周期為2 min，因此本文的預測周期設為2 min。另外，模塊缺失中參數(shù)設為10，主成分分析中累計概率閾值取值設為90%。

3.2.2 數(shù)據(jù)完整情況

在數(shù)據(jù)完整情況下，不需要使用DCT-PLS修復數(shù)據(jù)，直接用PCA算法對數(shù)據(jù)降維。數(shù)據(jù)降維后，使用KNN算法預測。

一次預測能夠輸出全部24個路段的預測值及相應誤差，但是由于版面限制，無法對各個路段進行單獨分析，因此取24個路段的平均誤差作為路網(wǎng)的預測誤差，結果見表4。

由表4可知，在數(shù)據(jù)完整情況下，KNN能較好的預測路網(wǎng)上各路段的速度值。

表4 數(shù)據(jù)完整情況下路網(wǎng)預測誤差

3.2.3 數(shù)據(jù)缺失情況

在數(shù)據(jù)缺失情況下，首先使用DCT-PLS算法對缺失數(shù)據(jù)進行修復，之后用PCA方法降維，最后使用KNN算法預測。同樣的，為了避免隨機因素對結果的影響，每組實驗重復10次。

表5列出來了數(shù)據(jù)降維的結果(10次實驗平均值)。同樣的，由于版面限制，無法對路網(wǎng)內各路段的預測結果進行單獨分析，只列出路網(wǎng)內所有路段的平均預測誤差。表6~8中列出了10次實驗的平均誤差，圖3以盒圖的形式展示了10次實驗的 結果。

另外，城市交通網(wǎng)絡具有很強的時效性，為了驗證本文提出的方法的廣泛適用性，在3種缺失形式下，分別計算了全天平均預測誤差(即表6)，8:00~9:00時段的誤差(表9)及20:00~21:00時段的預測誤差(表10)。

表5 PCA降維后列向量個數(shù)

表6 隨機缺失下路網(wǎng)平均誤差

表7 模塊缺失下路網(wǎng)平均誤差

表8 混合缺失下路網(wǎng)平均誤差

表9 隨機缺失下路網(wǎng)平均誤差(8:00~9:00)

表10 隨機缺失下路網(wǎng)平均誤差(20:00~21:00)

圖3 10次實驗預測誤差(MAPE)

由表5可知，應用PCA之后數(shù)據(jù)變?yōu)?-12列，降維之后的數(shù)據(jù)量約為原始數(shù)據(jù)的1/12-1/2(降維之前數(shù)據(jù)由24個列向量組成(24個路段))。比較不同缺失率的降維效果可知，缺失率越高降維后剩余的數(shù)據(jù)量越少。當缺失率為90%時，降維后的數(shù)據(jù)量僅為原始數(shù)據(jù)的1/12，與原始數(shù)據(jù)中不缺失數(shù)據(jù)量(10%)相當。另外，本文中應用PCA完成一次降維所需時間約為0.5 s，相對于預測時間可以忽略不計，因此使用數(shù)據(jù)降維技術可以大幅降低基于數(shù)據(jù)驅動的預測方法的計算成本。

從表6可知，隨著數(shù)據(jù)缺失率的增加，平均誤差也相應增加。當缺失率為10%時，預測誤差為16.18%，與不缺失時的誤差相近；當缺失率為50%時，預測誤差為18.82，比不缺失時增加2.80%；當缺失率達到90%時，MAPE也僅為26.53%，較數(shù)據(jù)完整時增加了10%，MAE為4.6511，較不缺失時增加約0.8。

在模塊缺失時，由表7可得，預測誤差同樣隨著缺失率增加而逐漸增加。缺失率為10%時，誤差為17.15%，較數(shù)據(jù)完整時增加1.13%；缺失率達到90%時，MAPE為24.33%，較不缺失時僅增加8%，而MAE為4.508 0，比不缺失時增加約0.7。

由表8可知，混合缺失時，當缺失率在50%以下時，預測誤差均小于20%，較不缺失情況僅僅增加4%。當缺失率繼續(xù)增加時，預測誤差隨之增加，但是增加幅度較小。缺失率為90%時，誤差也僅為24.87%，較不缺失時僅僅增加了8%，MAE為4.529 0，比不缺失時增加約0.7。

在隨機缺失環(huán)境下，由表6、表9可知，8:00~ 9:00時段的預測誤差低于全天平均誤差。對比表6和表10可知，20:00~21:00時段的MAE及RMSE值低于全天的對應值，但是其MAPE值比全天平均MAPE值高。全天平均、8:00~9:00時段及20:00~ 21:00時段的預測誤差存在差異但預測精度均較好。在模塊缺失及混合缺失環(huán)境下可得出與隨機缺失環(huán)境下相同的結論。

從圖3中可以看出,隨著缺失率增加，MAPE值隨之增加(對MAE、RMSE有相同結論)。比較不同缺失形式可知，隨機缺失時預測效果最好，混合缺失次之，模塊缺失最差。另外，從盒圖可以看出不同缺失率下，隨機缺失時10次實驗結果的方差最小，模塊缺失與混合缺失方差相近。

4 結論

1) PPCA算法效率最高，DCT-PLS算法效率略低，BPCA算法的效率明顯低于上述2種算法。在低缺失率時，3種算法的修復精度相近；在高缺失率時，DCT-PLS算法優(yōu)勢明顯，其修復精度比PPCA高10%左右。

2) 使用PCA算法降維后數(shù)據(jù)量變?yōu)樵瓉淼?/2-1/12，說明使用降維技術可以大幅減少數(shù)據(jù)量，從而降低預測時的計算成本。

3) 3種缺失形式下，當缺失率為10%時，預測誤差較數(shù)據(jù)完整時僅增加1%左右，當缺失率達到90%時，預測誤差也僅增加10%左右，證明在數(shù)據(jù)缺失環(huán)境下，基于DCTPLS-PCA的方法在大幅降低計算成本的同時，能夠保證很好的預測精度。

[1] 徐健銳, 李星毅, 施化吉. 處理缺失數(shù)據(jù)的短時交通流預測模型[J]. 計算機應用, 2010, 30(4): 1117?1120. XU Jianrui, LI Xingyi, SHI Huaji. Short-term traffic flow prediction model for processing missing data[J]. Computer Applications, 2010, 30(4): 1117?1120.

[2] Smith B, Scherer W, Conklin J. Exploring imputation techniques for missing data in transportation management systems[J]. Transportation Research Record: Journal of the Transportation Research Board, 2003(1836): 132? 142.

[3] CHEN C, Kwon J, Rice J, et al. Detecting errors and imputing missing data for single-loop surveillance systems[J]. Transportation Research Record: Journal of the Transportation Research Board, 2003 (1855): 160? 167.

[4] ZHONG M, Lingras P, Sharma S. Estimation of missing traffic counts using factor, genetic, neural, and regression techniques[J]. Transportation Research Part C: Emerging Technologies, 2004, 12(2): 139?166.

[5] QU L, LI L, ZHANG Y, et al. PPCA-based missing data imputation for traffic flow volume: A systematical approach[J]. IEEE Transactions on Intelligent Transportation Systems, 2009, 10(3): 512?522.

[6] LI L, LI Y, LI Z. Efficient missing data imputing for traffic flow by considering temporal and spatial dependence[J]. Transportation Research Part C: Emerging Technologies, 2013(34): 108?120.

[7] Kolda T G, Bader B W. Tensor decompositions and applications[J]. SIAM Review, 2009, 51(3): 455?500.

[8] Garcia D. Robust smoothing of gridded data in one and higher dimensions with missing values[J]. Computational Statistics & Data Analysis, 2010, 54(4): 1167?1178.

[9] WANG G, Garcia D, LIU Y, et al. A three-dimensional gap filling method for large geophysical datasets: Application to global satellite soil moisture observations [J]. Environmental Modelling & Software, 2012(30): 139?142.

[10] ZHENG L, ZHU C, ZHU N, et al. Feature selection- based approach for urban short-term travel speed prediction[J]. IET Intelligent Transport Systems, 2018, 12(6): 474?484.

[11] TANG J, LIU F, ZOU Y, et al. An improved fuzzy neural network for traffic speed prediction considering periodic characteristic[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(9): 2340?2350.

[12] MA X, DAI Z, HE Z, et al. Learning traffic as images: A deep convolutional neural network for large-scale transportation network speed prediction[J]. Sensors, 2017, 17(4): 818.

Research on road network speed prediction based on DCTPLS-PCA under data missing

YAO Jialin, ZHU Chuang

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

Accurate and reliable short-term traffic flow prediction is the basis of traffic control and guidance. However, traffic data missing that result from communication interference and other reasons, makes traffic flow prediction difficult. In this paper, the compensated least square regression algorithm (DCT-PLS) based on 3D discrete cosine transform was used to repair the missing data, and then the dimension of the repaired data was reduced by principal component analysis (PCA). Finally, the K-nearest neighbor (KNN) algorithm was used to predict the speed of each link of the road network, and the prediction error is calculated. The numerical experiments were conducted with and without the data missing based on a real network information in Changsha. The results show that the accuracy of repairing data of DCT-PLS algorithm is higher than that of probabilistic principal component analysis (PPCA) and Bayesian principal component analysis (BPCA); PCA can greatly reduce the computational cost of prediction. Under data missing, the method based on DCTPLS-PCA can greatly reduce the computational cost and ensure good prediction accuracy.

data missing; DCT-PLS; PCA; road network; speed prediction

U491

A

1672 ? 7029(2019)10? 2612 ? 08

10.19713/j.cnki.43?1423/u.2019.10.030

2019?01?01

姚加林(1961?)，男，湖南婁底人，副教授，從事交通運輸規(guī)劃與管理研究；E?mail：yaojialn@csu.edu.cn

(編輯 蔣學東)