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

有效

• 申請號: 201810294784.1
• 申請日: 2018-03-30
• 公開（公告）號: CN108320511B
• 公開（公告）日: 2020-12-29
• 發明（設計）人: 劉林;陳凝;呂偉韜;李攀
• 申請（專利權）人: 江蘇智通交通科技有限公司
• 主分類號: G08G1/01
• 分類號: G08G1/01;G06K9/62
• 代理公司: 南京正聯知識產權代理有限公司 32243
• 代理人: 王素琴

本發明提供一種基于譜聚類的城市道路交通子區劃分方法，建立路網無向圖，計算路網密度拉普拉斯矩陣L；根據k個特征值對應的特征向量v₁,…,v_k構建聚類基礎矩陣，并實施K均值聚類算法獲得k個簇；構成初始的子區；對孤立點隨機合并入鄰接的子區內，得到當前的子區總數；通過偏差檢測識別異常值點，并通過邊界調整解決最優的異常點歸屬問題；通過子區內外的相似度評估以及子區拆分、合并前后的相似度變化分析，對子區方案進行迭代優化，最終獲得子區內節點關聯度相似性最大、子區間差異性最大的道路交通路網劃分方案。該方法根據節點關聯度的相似特征高效、穩定地獲得交通道路網絡劃分方案，且最大程度保障子區間的特征差異性與子區內部的特征相似性。

技術領域

本發明涉及一種基于譜聚類的城市道路交通子區劃分方法。

背景技術

城市道路交通網絡是具有隨機特性的復雜網絡，將關系緊密的交叉口和路段的集合組成子區域，并針對各子區的特征實施控制、誘導、管理、規劃，能夠降低道路交通系統復雜性，甚至從宏觀層面達到協調優化的效果。在交通信號控制領域，動態的控制子區劃分能夠提高信號協同控制的穩定性和可靠性；在交通誘導領域，子區的劃分為協同誘導效果的發揮提供支撐；在交通規劃、交通安全分析等領域，則以靜態子區劃分為主，考慮土地利用、人口、經濟等宏觀特征。

目前在區域劃分領域，譜圖劃分理論逐步得到應用。采用這種方法劃分得到的小區內部交通流特征具有較高相似性，而各小區之間具有較大的差異性，且在劃分空間上具有連續性的優點。目前普遍應用的二分譜聚類的算法，基于Laplacian非零次小特征值及其特征向量聚類得出圖形分割結果，沒有充分利用包含有用劃分信息的其他特征向量，并且在需要分割出多個子圖時必須迭代使用，具有信息丟失量大、計算效率低、不穩定的缺陷。

上述問題是在城市道路交通子區劃分過程中應當予以考慮并解決的問題。

發明內容

本發明的目的是提供一種基于譜聚類的城市道路交通子區劃分方法，通過多重約束條件與相似度的迭代評估，獲得子區內相似度最大、子區間差異性最大的最優解，解決現有技術中存在的二分譜聚類的算法，在基于Laplacian非零次小特征值及其特征向量聚類得出圖形分割結果時，沒有充分利用包含有用劃分信息的其他特征向量，并且在需要分割出多個子圖時必須迭代使用，而出現的信息丟失量大、計算效率低、不穩定的缺陷的問題。

本發明的技術解決方案是：

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

S1、基于路網交叉口與路段的拓撲結構以及各節點的交通特征數據，建立路網無向圖G＝(V,E)，計算路網密度拉普拉斯矩陣L；

S2、計算拉普拉斯矩陣L的除0以外前k個最小的特征值及其特征向量，其中k的初值為2；根據k個特征值對應的特征向量v1,…,vk構建聚類基礎矩陣H＝[v1,…,vk]，對矩陣H的行向量實施K均值聚類算法，獲得k個簇；運用方差分析檢驗方法檢驗k個群組內的交通特征關聯度X，若存在顯著差異，則進入步驟S3；否則，k＝k+1，重復步驟S2；

S3、由簇內的交叉口以及交叉口間存在的路段構成初始的子區；若存在孤立點，即子區內僅包含一個節點編號，則將該子區隨機合并入鄰接的子區內，根據合并情況統計當前的子區總數N；

S4、通過偏差檢測識別異常值點，并通過邊界調整解決最優的異常點歸屬問題；通過子區內外的相似度評估以及子區拆分、合并前后的相似度變化分析，對子區方案進行迭代優化，最終獲得子區內節點關聯度相似性最大、子區間差異性最大的道路交通路網劃分方案。

進一步地，步驟S4具體為，

S41、若i≤N，則根據子區交叉口或路段交通特征關聯度X，檢測初始劃分方案內各子區內關聯度偏差，若存在異常值點，則轉入S42，否則轉入S43；其中i為子區編號，初值為1；若i＞N，結束本流程；