[發(fā)明專利]基于譜聚類的城市道路交通子區(qū)劃分方法

有效

• 申請?zhí)枺?/td>: 201810294784.1
• 申請日: 2018-03-30
• 公開（公告）號(hào): CN108320511B
• 公開（公告）日: 2020-12-29
• 發(fā)明（設(shè)計(jì)）人: 劉林;陳凝;呂偉韜;李攀
• 申請（專利權(quán)）人: 江蘇智通交通科技有限公司
• 主分類號(hào): G08G1/01
• 分類號(hào): G08G1/01;G06K9/62
• 代理公司: 南京正聯(lián)知識(shí)產(chǎn)權(quán)代理有限公司 32243
• 代理人: 王素琴

1.一種基于譜聚類的城市道路交通子區(qū)劃分方法，包括以下步驟：

S1、基于路網(wǎng)交叉口與路段的拓?fù)浣Y(jié)構(gòu)以及各節(jié)點(diǎn)的交通特征數(shù)據(jù)，建立路網(wǎng)無向圖G＝(V,E)，計(jì)算路網(wǎng)密度拉普拉斯矩陣L；

S2、計(jì)算拉普拉斯矩陣L的除0以外前k個(gè)最小的特征值及其特征向量，其中k的初值為2；根據(jù)k個(gè)特征值對應(yīng)的特征向量v₁,…,v_k構(gòu)建聚類基礎(chǔ)矩陣H＝[v₁,…,v_k]，對矩陣H的行向量實(shí)施K均值聚類算法，獲得k個(gè)簇；運(yùn)用方差分析檢驗(yàn)方法檢驗(yàn)k個(gè)群組內(nèi)的交通特征關(guān)聯(lián)度X，若存在顯著差異，則進(jìn)入步驟S3；否則，k＝k+1，重復(fù)步驟S2；

S3、由簇內(nèi)的交叉口以及交叉口間存在的路段構(gòu)成初始的子區(qū)；若存在孤立點(diǎn)，即子區(qū)內(nèi)僅包含一個(gè)節(jié)點(diǎn)編號(hào)，則將該子區(qū)隨機(jī)合并入鄰接的子區(qū)內(nèi)，根據(jù)合并情況統(tǒng)計(jì)當(dāng)前的子區(qū)總數(shù)N；

其特征在于：

S4、通過偏差檢測識(shí)別異常值點(diǎn)，并通過邊界調(diào)整解決最優(yōu)的異常點(diǎn)歸屬問題；通過子區(qū)內(nèi)外的相似度評估以及子區(qū)拆分、合并前后的相似度變化分析，對子區(qū)方案進(jìn)行迭代優(yōu)化，最終獲得子區(qū)內(nèi)節(jié)點(diǎn)關(guān)聯(lián)度相似性最大、子區(qū)間差異性最大的道路交通路網(wǎng)劃分方案；步驟S4具體為，

S41、若i≤N，則根據(jù)子區(qū)交叉口或路段交通特征關(guān)聯(lián)度X，檢測初始劃分方案內(nèi)各子區(qū)內(nèi)關(guān)聯(lián)度偏差，若存在異常值點(diǎn)，則轉(zhuǎn)入S42，否則轉(zhuǎn)入S43；其中i為子區(qū)編號(hào)，初值為1；若i＞N，結(jié)束本流程；

S42、根據(jù)路網(wǎng)拓?fù)渥R(shí)別子區(qū)i的相鄰子區(qū)集I＝{i₁,i₂…i_p}，其中i_p為相鄰子區(qū)的編號(hào)，p為相鄰子區(qū)個(gè)數(shù)，p∈[1,N-1]；檢測異常值點(diǎn)映射的節(jié)點(diǎn)或路段是否位于子區(qū)i邊界，若是，則將異常點(diǎn)映射的節(jié)點(diǎn)或路段劃入相鄰區(qū)域，求解使得成立的邊界調(diào)整方案，Var(X)為子區(qū)內(nèi)關(guān)聯(lián)度X方差，q為參與邊界調(diào)整的子區(qū)數(shù)，q∈[2,p]；若異常值點(diǎn)映射的節(jié)點(diǎn)或路段不在子區(qū)邊界上，則將異常值點(diǎn)作為子區(qū)內(nèi)的特殊點(diǎn)標(biāo)記，不參與后續(xù)的處理；

S43、判斷該子區(qū)i是否為初次劃分，若是，進(jìn)入步驟S44；否則，進(jìn)入步驟S46；

S44、計(jì)算子區(qū)內(nèi)除去特殊標(biāo)記點(diǎn)以外的點(diǎn)間關(guān)聯(lián)度X的相似度NS(X_i)；

S45、若NS(X_i)≥1，檢測子區(qū)i內(nèi)的交叉口數(shù)是否低于閾值NT；若成立則將子區(qū)i與相鄰子區(qū)合并，求解成立的合并方案，其中X_c'為合并后的i原相鄰子區(qū)的內(nèi)部關(guān)聯(lián)度，i＝i+1，回S41；若i內(nèi)的交叉口數(shù)不低于閾值NT，則回S1；

若NS(X_i)＜1，i＝i+1，回S41；

S46、計(jì)算子區(qū)內(nèi)除去特殊標(biāo)記點(diǎn)以外的點(diǎn)間關(guān)聯(lián)度X的相似度NS(X_i)，若NS(X_i)≥1，則恢復(fù)i區(qū)劃分前的方案；否則，檢測子區(qū)i內(nèi)的交叉口數(shù)是否低于閾值NT；

若成立則將子區(qū)i與相鄰子區(qū)合并，求解成立的合并方案，進(jìn)S47；否則，直接進(jìn)S47；

S47、計(jì)算子區(qū)i與路網(wǎng)內(nèi)其他子區(qū)的組間相似度并比較在子區(qū)i從原區(qū)域劃分出來前后，其歸屬區(qū)域與其他子區(qū)的組間相似度的變化趨勢，若降低，則i＝i+1，回S41；否則，恢復(fù)i區(qū)劃分前的方案；

步驟S44、S46中，計(jì)算子區(qū)內(nèi)除去特殊標(biāo)記點(diǎn)以外的點(diǎn)間關(guān)聯(lián)度X的相似度其中，i_p為相鄰子區(qū)的編號(hào)，u_i、為子區(qū)i、i_p內(nèi)關(guān)聯(lián)度X數(shù)據(jù)均值，Var(X_i)、Var(X_ip)分別為子區(qū)i、i_p內(nèi)關(guān)聯(lián)度X方差。

2.如權(quán)利要求1所述的基于譜聚類的城市道路交通子區(qū)劃分方法，其特征在于：步驟S41中，關(guān)聯(lián)度偏差檢測方式為：若則將x_i作為子區(qū)內(nèi)的離群點(diǎn)；其中，u為x_i均值，sd為標(biāo)準(zhǔn)差。