[發明專利]一種基于改進k最近鄰的大規模路網狀態短時預測方法

在審

• 申請號: 201810874538.3
• 申請日: 2018-08-03
• 公開（公告）號: CN109190797A
• 公開（公告）日: 2019-01-11
• 發明（設計）人: 于海洋;季楠;任毅龍;張路;劉帥;劉晨陽
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q50/30;G08G1/01
• 代理公司: 北京和信華成知識產權代理事務所(普通合伙) 11390
• 代理人: 胡劍輝

1.一種基于k則最近鄰的大規模路網狀態預測方法，其特征在于，所述方法包括如下步驟：

步驟一：數據預處理

首先，刪除錯誤數據，對于缺失數據利用線性插值法進行填補；刪除錯誤數據依據公式(1)，對于不在該范圍內的數據視為錯誤數據予以刪除：

0≤u_l(t)≤u_max (1)

其中，u_l(t)指在t時刻路網中的第l個路段觀測到的浮動車速度值；u_max為最大速度閾值，根據道路環境或者實際限速情況確定；缺失數據的線性插值法填補如公式(2)、(3)所示：

其中，公式(2)針對時刻t的數據缺失，利用t-1和t+1時刻數據進行填補，公式(3)針對路段l的數據缺失，利用臨近路段l-1和l+1的數據進行填補；

其次，利用中值濾波算法去除噪聲；對于路段l上觀測到的時間序列數據，利用中值濾波公式(4)去噪：

v_l(t)＝median{u_l(t-1)，u_l(t)，u_l(t+1)} (4)

其中，median{·}指取中位數，v_l(t)表示t時刻路網中的第l個路段濾波后得到的速度值；

然后，根據路段限速將速度數據經行歸一化，將速度值壓縮至[0，1]區間內。對于超過1的值，用1代替；

最后，進行路網狀態表征選擇；對于路網中第i和第j個路段，計算其狀態變化序列之間的Pearson相關系數如公式(5)，據此可以得到整個路網的相關矩陣如公式(6)：

其中，S_i(t)＝(v_i(t)，v_i(t-1)，…，v_i(t-l+1))為路網中第i個路段速度數據隨時間的變化序列，序列長度為Cov(·，·)為兩個序列的協方差；D(·)為序列的方差；

其中，γ是路網相關矩陣，L是路網中的路段總數；γ是一個對稱矩陣，且對角線元素值為1，反映了路網狀態演化過程中不同路段狀態之間變化的相關性；在γ中，對于每一行或列的元素，僅保留r_ij≥r^*的一個元素；當刪除某一元素時同時刪除其對稱位置元素；

步驟二：數據集劃分

經路網狀態表征規模降維后的路段數為L’，則路網狀態的短時變化表示為包含了多個時間步狀態時空矩陣，這些時間步內的狀態被認為是對所預測狀態具有一定影響的已知狀態，設這樣的時間步有δ個；路網短時狀態演化使用路網狀態單元表征，所述路網狀態單元由一個單一時間步的狀態S(t)，稱基準狀態，和演化到該狀態的趨勢向量τ(t)組成，其中用趨勢向量刻畫了短時路網演化的過程，并將其定義為：

τ(t)＝S(t-δ+1)-S(t) (8)

所述數據單元稱路網狀態單元表征為：

X(t)＝{S(t)，τ(t)} (9)

后續的歐式距離需要運算的標量數據維度為L’；

將歷史狀態單元及其生成路網狀態歸檔于歷史數據集，其時間跨度覆蓋于觀測路網的全天各個時間段，包對于影響路網演化狀態的特殊事件；同時，劃分出一部分歷史數據作為驗證集，用于參數標定；

步驟三：最近鄰搜索

對于給定的當前路網狀態單元X(t)＝{S(t)，τ(t)}：

首先，分別定義狀態之間的距離度量和趨勢向量之間的距離度量；對于基準狀態用歐式距離度量，對體現動態變化的趨勢向量用趨勢距離來度量，其中趨勢距離如公式(10)、(11)所示：

ED_i(t)＝||S(t)-S_hist(t_i)||₂，i＝1，2，…，N (10)

其中，X_hist(t_i)＝{S_hist(t_i)，τ_hist(t_i)為歷史數據集中第i個路網狀態單元，N為歷史數據集中路網狀態單元的總數，ED和TD分別是歐式距離和趨勢距離，||·||₂為求解歐式范數即二階范數的記號；

然后，定義路網狀態單元之間的距離度量；因為趨勢距離的數值范圍在[0，2]之間，將歐式距離也縮放至這個區間內，從將這兩種距離進行融合，得到公式(12)：

其中，SD為路網狀態單元之間的距離；α為平衡因子，在[0，1]內取值，體現了SD對于基準狀態和趨勢向量兩部分度量的側重程度，即當α＝1時，SD為歐式距離，完全側重于基準狀態的度量；當α＝1時，SD為趨勢距離，完全側重于趨勢向量的度量；

最后，計算X(t)與歷史數據集每一個樣本之間的距離，并選出距離最近的k個歷史路網狀態單元，記作其生成狀態分別為

步驟四：計算預測狀態

定義實際預測量為基準狀態和生成狀態之間的增量，其增量計算公式(13)如下：

采用高斯加權的方式對k個增量的進行整合計算最終的預測狀態形式如公式(14)：

其中，為最終的預測值，為權值，具體地σ是參數。

2.根據權利要求2所述的一種基于改進k最近鄰的大規模路網狀態短時預測方法，其特征在于，所述方法還包括：

步驟五：預測方法評價與參數標定

建立以均方根誤差和絕對值百分比誤差為標準的預測模型評價指標體系，對模型的預測精度進行評價；均方根誤差和絕對值百分比誤差的計算方法分別如式(15)和(16)。

式中：u代表時段數目，n_p代表是預測時段數目；在對結果影響在預定范圍內的情況下，下取盡量小的k；利用驗證集對參數與絕對值百分比誤差之間的關系對參數進行標定。