基于時(shí)空分析的路口相似度計(jì)算方法

楊海清,范 琦

(浙江工業(yè)大學(xué) 信息工程學(xué)院,杭州 310023)

0 概述

城市交通路口作為城市路網(wǎng)的重要節(jié)點(diǎn)和交通梳理的關(guān)鍵,對(duì)其時(shí)空數(shù)據(jù)的分析是交通治堵的重要思路。從交通路口的海量歷史時(shí)空數(shù)據(jù)中快速檢索出與當(dāng)前路口狀態(tài)相似的數(shù)據(jù),已成為短時(shí)交通流預(yù)測(cè)和配時(shí)方案自動(dòng)化推薦發(fā)展的迫切需求[1-2]。但是傳統(tǒng)的交通時(shí)空數(shù)據(jù)分析大多將重點(diǎn)放在時(shí)空軌跡的相似度匹配上[3],對(duì)于交通路口場(chǎng)景的時(shí)空數(shù)據(jù)匹配研究較少。

以空間場(chǎng)景的相似度計(jì)算模型為基礎(chǔ),文獻(xiàn)[4]提出基于特征矩陣和關(guān)聯(lián)圖的場(chǎng)景相似度度量方法,該方法能夠較準(zhǔn)確地度量不同數(shù)目空間對(duì)象的場(chǎng)景相似度,但根據(jù)方向關(guān)系特征向量?jī)蓛善ヅ涞姆绞皆黾恿怂惴◤?fù)雜度,不適用于海量數(shù)據(jù)的匹配。文獻(xiàn)[5-6]雖然空間場(chǎng)景的匹配精度也非常高,但都沒(méi)有根據(jù)空間屬性對(duì)檢索的空間場(chǎng)景進(jìn)行約束,難以在時(shí)間維度上擴(kuò)展。以時(shí)空數(shù)據(jù)相似度計(jì)算模型為基礎(chǔ),文獻(xiàn)[7]提出基于趨勢(shì)面與SSIM的時(shí)空數(shù)據(jù)相似度算法,文獻(xiàn)[8]提出ST-Link可擴(kuò)展鏈接算法,該算法利用有效的空間和時(shí)間過(guò)濾機(jī)制,縮小匹配用戶(hù)的搜索范圍,文獻(xiàn)[9]提出一種可表示空間實(shí)體屬性的時(shí)空數(shù)據(jù)模型。但以上相似度度量方法均未考慮空間關(guān)系對(duì)時(shí)空數(shù)據(jù)相似度的影響,尤其是在交通路口場(chǎng)景中,路口附近的學(xué)校、醫(yī)院和火車(chē)站等地點(diǎn)在不同的時(shí)間段上會(huì)對(duì)交通路口的動(dòng)態(tài)數(shù)據(jù)產(chǎn)生巨大影響[10-11]。

本文提出一種基于時(shí)空分析的交通路口相似度計(jì)算方法,通過(guò)交通路口數(shù)據(jù)屬性檢索出數(shù)據(jù)庫(kù)中相匹配的路口場(chǎng)景,根據(jù)交通路口與周?chē)鷰缀螌?duì)象的空間關(guān)系判斷滿(mǎn)足約束條件的數(shù)據(jù)庫(kù)中路口場(chǎng)景,由目標(biāo)路口在時(shí)間維度上的動(dòng)態(tài)數(shù)據(jù)變化匹配數(shù)據(jù)庫(kù)中路口的相似時(shí)段,并根據(jù)時(shí)空相似度計(jì)算模型得出的相似度進(jìn)行排序,以提高交通路口在時(shí)間空間上的匹配精度和合理性。

1 路口靜態(tài)數(shù)據(jù)相似度計(jì)算模型

本文在分析路口靜態(tài)數(shù)據(jù)的過(guò)程中,將交通路口作為空間場(chǎng)景,由道路與周?chē)鷮?duì)交通流影響較大的矢量面狀幾何對(duì)象構(gòu)成。本文在目標(biāo)路口P與數(shù)據(jù)庫(kù)路口P′的相似度計(jì)算過(guò)程中,首先從P′中篩選出與P相同路口叉數(shù)的路口。在描述路口特征時(shí),本文所用的特征量集合均以最接近正北方向的路段為起始,逆時(shí)針?lè)较蚺判颉?/p>

1.1 路口屬性相似度計(jì)算模型

在進(jìn)行空間分析的過(guò)程中,交通路口具有車(chē)道功能、檢測(cè)器類(lèi)型、路口類(lèi)型、車(chē)道類(lèi)型和檢測(cè)器位置等屬性[12-13]。其中路段上對(duì)應(yīng)的車(chē)道功能是分析路口車(chē)道流量和飽和度的重要依據(jù),所以本文將路口車(chē)道功能屬性單獨(dú)提取出來(lái),定義路口場(chǎng)景中車(chē)道功能集合為F={X1,X2,…,Xn},其中,n表示路口叉數(shù),Xi(1≤i≤n)為第i條路段上所具有的車(chē)道功能類(lèi)型集合,即當(dāng)相鄰車(chē)道的車(chē)道功能相同時(shí),會(huì)被記錄為一種車(chē)道功能類(lèi)型。對(duì)于目標(biāo)路口P,定義其車(chē)道功能集合為Fp={X1,X2,…,Xn},并提取數(shù)據(jù)庫(kù)路口P′的車(chē)道功能集合為F′p{X′1,X′2,…,X′n}。

(1)

1.2 路口空間關(guān)系相似度計(jì)算模型

在研究交通路口的空間關(guān)系相似度度量問(wèn)題時(shí),本文將交通路口場(chǎng)景中的道路簡(jiǎn)化為線(xiàn)類(lèi)型的矢量數(shù)據(jù),交通路口周?chē)目臻g對(duì)象,如車(chē)站、學(xué)校和醫(yī)院對(duì)交通流影響較大的地點(diǎn)作為面狀矢量數(shù)據(jù)。創(chuàng)建一個(gè)在交通路口場(chǎng)景下結(jié)合拓?fù)潢P(guān)系、方位關(guān)系和距離關(guān)系的相似度計(jì)算模型。

本文采用維度擴(kuò)展的九交模型[15],確定目標(biāo)路口場(chǎng)景和數(shù)據(jù)庫(kù)路口場(chǎng)景中面狀空間對(duì)象A與道路R的拓?fù)潢P(guān)系,并計(jì)算數(shù)據(jù)庫(kù)路口場(chǎng)景與目標(biāo)路口場(chǎng)景中兩對(duì)相同拓?fù)潢P(guān)系的空間對(duì)象間的拓?fù)潢P(guān)系相似度。

根據(jù)路口叉數(shù)n將路口場(chǎng)景劃分,定義A的出口點(diǎn)集合EA={e1,e2,…,em}(m為A的總出口數(shù)),創(chuàng)建拓?fù)潢P(guān)系和方位關(guān)系統(tǒng)一的相似度計(jì)算模型,如圖1所示。

圖1 路口場(chǎng)景拓?fù)潢P(guān)系與方位關(guān)系統(tǒng)一描述模型

當(dāng)R與A為相鄰或相交關(guān)系時(shí),道路與面狀空間對(duì)象的交集維數(shù)DDIM(R∩A)≤1,并且(R∩A)?R。由于在路口場(chǎng)景中,進(jìn)口道交通流量的影響遠(yuǎn)大于出口道交通流量的影響,因此當(dāng)A與多條路段相交或相鄰時(shí),選取A在R逆時(shí)針?lè)较騾^(qū)域的部分為研究對(duì)象。目標(biāo)路口P的拓?fù)潢P(guān)系特征值TP為:

(2)

(3)

EExist(dRn∩A)]

(4)

(5)

(6)

提取目標(biāo)路口場(chǎng)景中面狀空間對(duì)象A的所有出口點(diǎn)集合EA,將EA構(gòu)成的最大面積多邊形作為A的特征多邊形。將該特征多邊形的重心與路口中心O點(diǎn)的歐式距離作為路口場(chǎng)景的距離關(guān)系特征值DDis,則P與P′的距離關(guān)系相似度SDis為:

(7)

P與P′中兩對(duì)空間對(duì)象間的空間關(guān)系相似度為:

(8)

當(dāng)空間對(duì)象R與A為相離關(guān)系時(shí),A對(duì)相鄰路段的交通流量的影響更為直接[16],因此,對(duì)于P和P′中兩對(duì)空間對(duì)象間的空間關(guān)系相似度不做計(jì)算。

2 路口動(dòng)態(tài)數(shù)據(jù)模型

交通路口的動(dòng)態(tài)數(shù)據(jù)主要來(lái)源于車(chē)道檢測(cè)器,包括進(jìn)口道的流量和飽和度等隨時(shí)間動(dòng)態(tài)變化的數(shù)據(jù)。本文以車(chē)道流量f為例,將數(shù)據(jù)庫(kù)路口P′的車(chē)道流量按協(xié)調(diào)方案的周期時(shí)長(zhǎng)在時(shí)間維度上進(jìn)行切分。根據(jù)目標(biāo)路口P的車(chē)道檢測(cè)器所提供的車(chē)道的實(shí)時(shí)流量,計(jì)算相同周期時(shí)長(zhǎng)內(nèi)P與P′的流量相似度Sf。

對(duì)于交通路口動(dòng)態(tài)數(shù)據(jù)模型的相似度計(jì)算,只有兩個(gè)路口在對(duì)應(yīng)路段上的車(chē)道功能類(lèi)型相同時(shí)才有匹配的意義[17-18]。所以,當(dāng)路口的空間屬性數(shù)據(jù)相似度Sv=0時(shí),取流量相似度Sf=0。根據(jù)目標(biāo)路口P的信號(hào)周期時(shí)長(zhǎng)CP和輸入起始時(shí)間t0,由路口屬性數(shù)據(jù)相似度模型中的數(shù)據(jù)集合排序方式確定P的進(jìn)口道特征流量集合Qp={Qp1,Qp2,…,Qpn},n為目標(biāo)路口P中含有進(jìn)口道的路段總數(shù),其中,Qpi(1≤i≤n)表示該路段進(jìn)口道上同種車(chē)道功能的實(shí)時(shí)特征流量集合{f1,f2,…,fξ},ξ為路段上車(chē)道功能種類(lèi)總數(shù)。以新匯路長(zhǎng)華街路口為例,路口渠化示意圖如圖2所示,流量數(shù)據(jù)如表1所示,信號(hào)周期時(shí)長(zhǎng)為60 s。

圖2 新匯路長(zhǎng)華街路口渠化示意圖

表1 新匯路長(zhǎng)華街路口某段信號(hào)周期時(shí)長(zhǎng)內(nèi)流量數(shù)據(jù)

定義每種車(chē)道功能在CP上的特征流量為:

(9)

其中,v為具有該車(chē)道功能的車(chē)道數(shù)目。因?yàn)槟繕?biāo)路口P與數(shù)據(jù)庫(kù)路口P′在同一路段上的車(chē)道功能類(lèi)型相同,所以P′在對(duì)應(yīng)路段進(jìn)口道特征流量集合Q′pi與Qpi的個(gè)數(shù)同為ξ。計(jì)算信號(hào)周期內(nèi)P與P′在相應(yīng)路段上的流量相似度Sfi:

(10)

其中,f′j為數(shù)據(jù)庫(kù)路口P′在第i條進(jìn)口道上第j種車(chē)道功能的特征流量。當(dāng)Sfi≤0時(shí),取Sfi=0,即0≤Sfi≤1。將n條進(jìn)口道的流量相似度Sfi累加取平均值,即得目標(biāo)路口與數(shù)據(jù)庫(kù)路口的起始時(shí)段相似度Sq0。當(dāng)目標(biāo)路口P的流量數(shù)據(jù)由車(chē)道檢測(cè)器持續(xù)輸入時(shí),分別計(jì)算在接下來(lái)的每段信號(hào)周期時(shí)長(zhǎng)內(nèi)P與P′的流量相似度。取所有信號(hào)周期內(nèi)流量相似度的均值,合成整個(gè)時(shí)段內(nèi)的動(dòng)態(tài)數(shù)據(jù)相似度。

3 時(shí)空數(shù)據(jù)相似度計(jì)算模型

本文通過(guò)目標(biāo)路口的空間信息,提取路口屬性數(shù)據(jù)與周?chē)乩硇畔?分別建立目標(biāo)路口P與數(shù)據(jù)庫(kù)路口P′的空間屬性相似度計(jì)算模型和空間關(guān)系相似度計(jì)算模型,在滿(mǎn)足P與P′的空間屬性相似度大于0的條件下,提取目標(biāo)路口信號(hào)周期時(shí)長(zhǎng)一定的動(dòng)態(tài)數(shù)據(jù),建立P與P′的動(dòng)態(tài)數(shù)據(jù)相似度計(jì)算模型。根據(jù)P與P′的空間屬性相似度、空間關(guān)系相似度和動(dòng)態(tài)數(shù)據(jù)相似度,對(duì)時(shí)間維度上的數(shù)據(jù)庫(kù)路口進(jìn)行排序。目標(biāo)路口場(chǎng)景P如圖3所示,數(shù)據(jù)庫(kù)路口場(chǎng)景P′如圖4所示。

圖3 目標(biāo)路口場(chǎng)景

圖4 數(shù)據(jù)庫(kù)路口場(chǎng)景

在圖3、圖4中,e為空間面狀對(duì)象的出口,與路段相鄰且距離路口中心點(diǎn)O最近的出口點(diǎn)作為起點(diǎn),逆時(shí)針?lè)较蚺判?。提取目?biāo)路口的車(chē)道功能集合及其他屬性數(shù)據(jù),利用式(1)計(jì)算P與P′的空間屬性相似度。根據(jù)目標(biāo)路口場(chǎng)景P的空間數(shù)據(jù)定義空間場(chǎng)景特征描述集合Pdes={R1,R2,…,Rn},其中,Ri(1≤i≤n)為第i條路段上的空間關(guān)系描述特征集合,Ri集合中的元素為空間面狀矢量對(duì)象A,以A的e1點(diǎn)與路口中心O點(diǎn)距離大小排序(距離越小,順序越靠前),A在路段順時(shí)針?lè)较蛉∝?fù),逆時(shí)針?lè)较蛉≌?。利用?2)～式(8)分別計(jì)算P與P′在對(duì)應(yīng)路段上的空間關(guān)系相似度。

計(jì)算P與P′的動(dòng)態(tài)數(shù)據(jù)相似度的具體步驟如下:

輸入目標(biāo)路口P起始時(shí)間t0和結(jié)束時(shí)間tω、該時(shí)間段Δt內(nèi)的信號(hào)周期時(shí)長(zhǎng)CP以及Δt內(nèi)每條車(chē)道的流量數(shù)據(jù){q1,q2,…,qα}

步驟1利用式(9)確定Δt內(nèi)P在每個(gè)信號(hào)周期時(shí)長(zhǎng)中進(jìn)口道上同種車(chē)道功能的特征流量集合Qp。

步驟2取出目標(biāo)路口P在t0至t0+CP時(shí)段內(nèi)的特征流量集合,并利用式(10)計(jì)算數(shù)據(jù)庫(kù)路口P′的所有CP時(shí)段與該時(shí)段的相似度。

步驟3隨著持續(xù)輸入結(jié)束時(shí)間的推移,合成整個(gè)時(shí)間段內(nèi)兩路口的流量數(shù)據(jù)相似度并輸出數(shù)據(jù)庫(kù)路口對(duì)應(yīng)的時(shí)段。

4 實(shí)驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)包含兩部分內(nèi)容,一是根據(jù)杭州市區(qū)內(nèi)2 781個(gè)路口的空間數(shù)據(jù),驗(yàn)證路口靜態(tài)數(shù)據(jù)相似度計(jì)算方法,二是根據(jù)杭州市區(qū)內(nèi)50個(gè)路口一周內(nèi)的所有車(chē)道檢測(cè)器數(shù)據(jù)(車(chē)道流量),驗(yàn)證路口動(dòng)態(tài)數(shù)據(jù)相似度計(jì)算方法。

4.1 路口空間數(shù)據(jù)相似度計(jì)算模型實(shí)驗(yàn)

本文實(shí)驗(yàn)將杭州路口矢量數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫(kù)中,并根據(jù)路口的車(chē)道信息、路段空間信息及路口屬性等數(shù)據(jù)構(gòu)建表關(guān)聯(lián)。將杭州市區(qū)內(nèi)的所有學(xué)校空間數(shù)據(jù)(包括學(xué)校出入口)作為路口場(chǎng)景中的空間矢量面狀對(duì)象實(shí)驗(yàn)數(shù)據(jù),如圖5所示。

圖5 杭州市區(qū)內(nèi)實(shí)驗(yàn)路口、學(xué)校及路段的空間數(shù)據(jù)

本文實(shí)驗(yàn)選取杭州市文一西路益樂(lè)路口作為目標(biāo)路口,提取其車(chē)道功能屬性集合,檢索出數(shù)據(jù)庫(kù)中有68個(gè)杭州路口符合車(chē)道功能約束。分別使用場(chǎng)景相似性檢索方法[19]和空間數(shù)據(jù)檢索方法[20]對(duì)68個(gè)路口場(chǎng)景進(jìn)行檢索,得到查全率和查準(zhǔn)率如表2所示。場(chǎng)景相似性檢索方法和空間數(shù)據(jù)檢索方法均使用了方位關(guān)系與拓?fù)潢P(guān)系約束,且場(chǎng)景相似性檢索方法中還使用了空間對(duì)象的形狀約束,而本文對(duì)于路口場(chǎng)景中的空間對(duì)象使用了空間對(duì)象的出入口作為特征描述量,因此查全率相對(duì)較高,同時(shí)本文針對(duì)交通路口的空間特點(diǎn),利用交通路口場(chǎng)景中的道路作為場(chǎng)景描述坐標(biāo),因此提高了查準(zhǔn)率。

表2 檢索方法的查準(zhǔn)率和查全率對(duì)比

根據(jù)目標(biāo)路口的空間數(shù)據(jù),在數(shù)據(jù)庫(kù)路口場(chǎng)景中進(jìn)行匹配,得到實(shí)驗(yàn)結(jié)果如表3所示。從實(shí)驗(yàn)結(jié)果中可以看出,本文中的算法對(duì)于未能與目標(biāo)路口場(chǎng)景完全匹配的數(shù)據(jù)庫(kù)路口場(chǎng)景,仍能根據(jù)局部匹配程度得出空間關(guān)系相似度,因?yàn)槁房趫?chǎng)景受到車(chē)道功能類(lèi)型約束,所以導(dǎo)致檢索出的路口場(chǎng)景相似度較低。

表3 空間場(chǎng)景相似路口檢索結(jié)果

4.2 路口動(dòng)態(tài)數(shù)據(jù)相似度計(jì)算模型實(shí)驗(yàn)

本文實(shí)驗(yàn)從杭州2 000多個(gè)路口中選取車(chē)道檢測(cè)器較靈敏,且路口進(jìn)口車(chē)道覆蓋較全面的50個(gè)路口在一周內(nèi)的動(dòng)態(tài)流量數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)。選取崇義路文二西路路口北向路段周二上午9時(shí)30分—10時(shí)的路口進(jìn)口車(chē)道實(shí)時(shí)流量作為實(shí)驗(yàn)數(shù)據(jù),如圖6所示。

圖6 崇義路文二西路路口北向路段流量數(shù)據(jù)

由車(chē)道檢測(cè)器數(shù)據(jù)可知,目標(biāo)路口實(shí)時(shí)信號(hào)周期時(shí)長(zhǎng)為140 s,提取目標(biāo)路口所有路段起始信號(hào)周期內(nèi)的特征流量集合為{[11,10,0],[0,14],[11,19]}。從數(shù)據(jù)庫(kù)路口中提取出與目標(biāo)路口靜態(tài)數(shù)據(jù)相似度最高的路口,并計(jì)算其信號(hào)周期時(shí)長(zhǎng)同為140 s的時(shí)間段內(nèi)路口流量數(shù)據(jù)與目標(biāo)路口起始信號(hào)周期內(nèi)流量數(shù)據(jù)的相似度,當(dāng)相似度滿(mǎn)足指定閾值(本文實(shí)驗(yàn)取0.5)后,分別計(jì)算在下個(gè)信號(hào)周期內(nèi)的流量數(shù)據(jù)相似度。由路口靜態(tài)數(shù)據(jù)模型計(jì)算得出之江路姚江路路口的靜態(tài)相似度最高。若數(shù)據(jù)庫(kù)路口中存在該目標(biāo)路口,則本文將分別選擇該路口和與該路口靜態(tài)數(shù)據(jù)相似度最高的路口,進(jìn)行動(dòng)態(tài)數(shù)據(jù)相似度計(jì)算,實(shí)驗(yàn)結(jié)果如圖7、圖8所示。

圖7 相同路口動(dòng)態(tài)數(shù)據(jù)實(shí)驗(yàn)結(jié)果

圖8 不同路口動(dòng)態(tài)數(shù)據(jù)實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可以看出,本文將交通路口的靜態(tài)數(shù)據(jù)作為動(dòng)態(tài)數(shù)據(jù)匹配的約束條件,能夠有效地提高算法效率。相較于時(shí)空索引檢索算法[21],本文方法能夠更有效地匹配相似的時(shí)段,具有較強(qiáng)的實(shí)用性。

5 結(jié)束語(yǔ)

本文提出一種基于時(shí)空分析的交通路口相似度計(jì)算方法,從空間場(chǎng)景相似度和動(dòng)態(tài)數(shù)據(jù)相似度等角度綜合分析了交通路口時(shí)空數(shù)據(jù)間的差異,在計(jì)算交通路口相似度的過(guò)程中,構(gòu)建適用于交通路口的靜態(tài)數(shù)據(jù)模型,提高交通路口相似度分析的合理性及魯棒性,在構(gòu)建時(shí)空數(shù)據(jù)模型時(shí),研究動(dòng)態(tài)數(shù)據(jù)在時(shí)間維度上的變化趨勢(shì),以使算法適用于智能交通領(lǐng)域中單點(diǎn)路口配時(shí)方案。實(shí)驗(yàn)結(jié)果表明,相較于時(shí)空索引檢索算法,該算法能夠有效提高交通路口檢索的查全率以及在時(shí)間空間上的匹配精度。