[發明專利]基于歸一化譜聚類算法的城市快速路交通狀態估計方法

有效

• 申請號: 202210167107.X
• 申請日: 2022-02-23
• 公開（公告）號: CN114639238B
• 公開（公告）日: 2023-02-14
• 發明（設計）人: 任剛;趙鐵聰;宋建華;陳維翰;李大韋;李豪杰
• 申請（專利權）人: 東南大學
• 主分類號: G08G1/01
• 分類號: G08G1/01;G06F18/2323;G06F18/23213;G06F18/22;G06F18/20;G06F16/215;G06F16/29;G06Q10/063;G06Q50/26
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 周科技

1.基于歸一化譜聚類算法的城市快速路交通狀態估計方法，其特征在于：該方法包括以下步驟：

(1)獲取城市快速路GPS數據并進行預處理：包括去除冗余數據，GPS數據時間排序，地圖匹配，數據選取處理；

(2)進行交通參數選定：計算目標路段的平均速度，速度離散度，作為交通狀態估計的表征參數；

(3)將表征參數平均速度和速度離散度作為二維數據點，利用歸一化譜聚類算法對數據點進行聚類分析；

(4)運用輪廓系數對聚類效果即交通狀態估計效果進行評價，比較每個聚類簇中輪廓系數均值的最大值即得到最終的聚類評價效果；

步驟(2)中，按照以下公式計算某一時間段內的速度離散度：

其中，V_dt表示t時間內的車速離散度；n表示t時間內的目標車輛數；v_i表示車速；表示t時間內的平均速度；σ₁表示t時間內的速度標準差；

步驟(3)中，利用歸一化譜聚類算法對選取的表征參數進行聚類劃分，步驟如下：

(3-1)定義譜聚類算法和交通狀態估計之間的關系：

定義數據集S＝(G,E)，其中表示相關點，即數據點，E是點與點之間的邊，用于描述兩個數據點之間的相關關系，用相似度w_ij表示邊的權重；

(3-2)確定圖論劃分準則為多路NCUT切圖：

將目標數據集劃分為k個集合，使得子簇間的相似度最小，子簇內的相似度最大；構造目標函數如下：

其中，表示集合A_i與其補集之間的關系，具體表示為A_i與其補集之間的相似度vol(A_i)表示隸屬集合A_i的所有數據點的權重之和；

其中，n表示集合A_i的數據點數；

(3-3)使用n維空間中的歐幾里得距離和高斯核函數定義數據點間的相似度w_ij，其公式如下：

w_ij＝w_ji；

其中，w(X_i,X_j)表示第i,j個數據點X_i,X_j之間的相似度，σ₂是高斯核函數的核；

(3-4)使用全連接法構建鄰接矩陣W，w_ij是矩陣W中的元素：

(3-5)定義每一個數據點和與它相聯的所有邊的相似度之和d_i，公式如下：

(3-6)構建對角矩陣D，公式如下：

(3-7)構建歸一化拉普拉斯矩陣L_sym，公式如下：

L_sym＝D^-1/2LD^-1/2＝E-D^-1/2WD^-1/2

其中，L＝D-W，E表示單位向量；對于L_sym，0是其最小的特征向量且對應的特征值是D^-1/2E；

(3-8)計算矩陣L_sym的特征向量和對應的特征值，按照特征值從小到大的順序選擇k個最小特征值和其對應的特征向量；k個特征向量構成矩陣U；

(3-9)對矩陣U的每一行進行歸一化處理得到矩陣N，表示如下：

其中，N_ij是矩陣N中的元素，u_ij是矩陣U中的元素；

(3-10)將行向量n_i∈N作為K-means算法的聚類中心，利用K-means算法進行聚類，獲得聚類結果C₁,C₂,…,C_k，其中每一種聚類結果包含的數據點集合表示為A₁,A₂,...,A_k；

步驟(4)中，運用輪廓系數SC對歸一化譜聚類算法效果進行評價，具體步驟如下：

(4-1)計算聚類之后每個簇內數據點的輪廓系數，具體公式如下：

其中，S_i^m表示第i個簇內第m個數據點的輪廓系數，-1S_i^m1，其值越接近1表明該簇的聚類結果越優越，越接近-1聚類效果越差，當S_i^m＝0時，表明該數據點位于兩個簇的邊界；C_i表示第i類簇，C_i表示C_i中數據點個數；a_m表示C_i中數據點m和內部簇中其他點的平均相似度，b_m表示C_i中數據點m與外部簇中的點的最小相似度；

(4-2)計算每個簇內輪廓系數S_i^m的均值并比較k個簇中輪廓系數均值的最大值即得到最終的聚類評價效果SC：

其中表示第k個簇內所有數據點的輪廓系數的均值。