基于車牌時(shí)空數(shù)據(jù)的城市熱點(diǎn)交通線路挖掘 ①

張翔宇 張 強(qiáng) 呂明琪 李素玲**

(*中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190) (**中國(guó)科學(xué)院大學(xué) 北京 100049) (***浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 杭州 310014) (****北京賽迪時(shí)代信息產(chǎn)業(yè)股份有限公司 北京 100048) (*****中華全國(guó)總工會(huì) 北京 100085)

0 引 言

智能交通系統(tǒng)(intelligent transportation system, ITS)是改善城市交通系統(tǒng)運(yùn)行性能的有效手段。近年來(lái)，越來(lái)越多的交通傳感設(shè)備(如交通攝像頭、環(huán)形線圈、微波檢測(cè)器等)被部署在城市道路上，這些交通傳感設(shè)備采集了大量的交通數(shù)據(jù)，使得智能交通系統(tǒng)逐漸從技術(shù)驅(qū)動(dòng)為主演化為數(shù)據(jù)驅(qū)動(dòng)為主[1]。因此，從交通大數(shù)據(jù)中挖掘交通運(yùn)行模式成為了一個(gè)熱門(mén)的研究領(lǐng)域。其中，城市熱點(diǎn)交通線路(以下簡(jiǎn)稱為“熱點(diǎn)線路”)是一類典型的交通運(yùn)行模式，指在固定時(shí)間段內(nèi)大量車輛共同行駛的道路路段序列[2, 3]。熱點(diǎn)線路可支持許多潛在的應(yīng)用，如路線規(guī)劃[4]、交通流預(yù)測(cè)[5]、擁堵預(yù)測(cè)[6]、城市規(guī)劃[7]等。

然而，與單一車輛的行駛模式[8]不同，熱點(diǎn)線路考慮的是城市車輛的總體流動(dòng)規(guī)律。由于單一車輛行駛的不確定性，大部分車輛的行駛軌跡只貢獻(xiàn)熱點(diǎn)線路的一部分，只有極少數(shù)車輛的行駛軌跡能完整覆蓋一條熱點(diǎn)線路。因此，現(xiàn)有軌跡模式挖掘算法要求車輛軌跡完整覆蓋行駛模式，則通常只能挖掘出很短的熱點(diǎn)線路，對(duì)城市交通總體規(guī)劃的指導(dǎo)意義不大。

針對(duì)熱點(diǎn)線路挖掘問(wèn)題，大多現(xiàn)有工作采用細(xì)粒度的車輛GPS軌跡數(shù)據(jù)[7, 9-12]。然而，由于普通車輛的GPS軌跡數(shù)據(jù)基本無(wú)法獲得，現(xiàn)有工作均采用浮動(dòng)車輛(如出租車、公交車)的GPS軌跡數(shù)據(jù)。由于浮動(dòng)車輛的占比很小，其產(chǎn)生的軌跡數(shù)據(jù)對(duì)城市道路的時(shí)空覆蓋非常有限。因此，從浮動(dòng)車輛軌跡數(shù)據(jù)中挖掘出的熱點(diǎn)線路通常難以反映真實(shí)的城市交通狀況。另一方面，交通攝像頭作為智能交通系統(tǒng)的重要基礎(chǔ)設(shè)備，由于其非侵入的特性，已經(jīng)被大量地部署在城市道路上，并被用作車輛行駛軌跡采集的最主流設(shè)備[1]。交通攝像頭最主要的功能為車牌識(shí)別，由于交通攝像頭具有空間屬性，車牌識(shí)別具有時(shí)間屬性，則一輛車的軌跡可被重構(gòu)為該車輛按時(shí)間順序經(jīng)過(guò)的交通攝像頭的序列[13]。鑒于交通攝像頭的高覆蓋率，從車牌識(shí)別時(shí)空數(shù)據(jù)中挖掘熱點(diǎn)線路是更為合理的思路。

然而，基于車牌時(shí)空數(shù)據(jù)的熱點(diǎn)線路挖掘比一般的交通模式挖掘更具挑戰(zhàn)，原因如下：首先，由于建設(shè)成本的原因，交通攝像頭通常無(wú)法覆蓋所有的道路路段。其次，由于技術(shù)限制的原因，車牌識(shí)別經(jīng)常存在遺漏和錯(cuò)誤等問(wèn)題。這些不確定性問(wèn)題導(dǎo)致現(xiàn)有交通模式挖掘方法無(wú)法有效挖掘出熱點(diǎn)線路，原因在于現(xiàn)有方法大多將車輛軌跡映射到道路網(wǎng)絡(luò)上，在此基礎(chǔ)上進(jìn)行交通模式挖掘[2, 14-16]。然而，由于交通攝像頭的空間稀疏性和識(shí)別不確定性，基于車牌時(shí)空數(shù)據(jù)重構(gòu)得到的車輛軌跡中的連續(xù)2個(gè)交通攝像頭可能間隔多個(gè)道路路段，導(dǎo)致難以進(jìn)行道路匹配。另外，大部分車輛的行駛軌跡只占熱點(diǎn)線路的部分。通常情況下，一輛車會(huì)在一條熱點(diǎn)線路的起點(diǎn)和終點(diǎn)之間駛?cè)牒婉偝觯罅寇囕v在該起點(diǎn)和終點(diǎn)之間的軌跡共同構(gòu)成了這條熱點(diǎn)線路。因此，現(xiàn)有交通模式挖掘算法(如聚類算法[17, 18]、序列模式挖掘算法[19, 20])只能挖掘出大量很短的熱點(diǎn)線路，對(duì)城市交通總體規(guī)劃的指導(dǎo)意義不大。交通模式挖掘算法通常會(huì)產(chǎn)生大量的挖掘結(jié)果，而這些結(jié)果中很多是相似和冗余的，導(dǎo)致決策人員難以從中發(fā)現(xiàn)最有價(jià)值的信息。

針對(duì)上述問(wèn)題，本文提出了一種從車牌時(shí)空數(shù)據(jù)中有效挖掘熱點(diǎn)線路的方法。該方法首先從重構(gòu)的車輛軌跡數(shù)據(jù)中挖掘出子模式，并基于一個(gè)雙向樹(shù)數(shù)據(jù)結(jié)構(gòu)拼接這些子模式以形成候選熱點(diǎn)線路(該步驟稱為熱點(diǎn)線路挖掘)。然后采用聚類排序算法從候選熱點(diǎn)線路中挑選出代表性熱點(diǎn)線路(該步驟稱為熱點(diǎn)線路壓縮)。本文的主要貢獻(xiàn)如下。(1) 提出了一種無(wú)需道路網(wǎng)絡(luò)支持的、基于車牌時(shí)空數(shù)據(jù)的熱點(diǎn)線路挖掘方法。(2) 提出了一種雙向樹(shù)數(shù)據(jù)結(jié)構(gòu)，用于拼接短的子模式以形成長(zhǎng)的熱點(diǎn)線路。(3) 提出了一種聚類排序算法，用于發(fā)現(xiàn)代表性熱點(diǎn)線路。(4) 基于杭州市真實(shí)車牌時(shí)空數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)。

1 相關(guān)工作

現(xiàn)有工作主要采用數(shù)據(jù)挖掘技術(shù)從各類交通傳感設(shè)備數(shù)據(jù)中挖掘交通模式。例如，Inoue等人[15]和Banaei-Kashani等人[16]從環(huán)形線圈產(chǎn)生的交通流數(shù)據(jù)中挖掘每條道路的交通流模式。Yuan等人[9]從浮動(dòng)車輛軌跡數(shù)據(jù)中挖掘行駛模式，并用于最快路徑檢索服務(wù)。Zheng等人[10]從浮動(dòng)車輛軌跡數(shù)據(jù)挖掘兩類出行模式即熱點(diǎn)區(qū)域和熱點(diǎn)路線，并基于這兩類出行模式分析居民出行的時(shí)空規(guī)律。Janecek等人[21]基于蜂窩網(wǎng)絡(luò)數(shù)據(jù)對(duì)交通狀態(tài)進(jìn)行推斷，包括行駛時(shí)間和交通擁堵等。

現(xiàn)有基于車牌時(shí)空數(shù)據(jù)挖掘的工作大多集中在交通流估計(jì)方面。例如，Castillo等人[13]利用車牌時(shí)空數(shù)據(jù)和道路車流數(shù)據(jù)對(duì)車輛軌跡進(jìn)行重構(gòu)，在此基礎(chǔ)上構(gòu)建車輛軌跡矩陣。Mínguez等人[22]對(duì)交通攝像頭的數(shù)量和部署位置進(jìn)行優(yōu)化，在此基礎(chǔ)上對(duì)OD(起點(diǎn)-終點(diǎn))矩陣進(jìn)行估計(jì)。然而，這些方法粒度較粗，只能對(duì)某條道路上或某對(duì)起點(diǎn)終點(diǎn)間的交通流進(jìn)行總體統(tǒng)計(jì)，無(wú)法估計(jì)車輛的細(xì)粒度行駛模式，從而無(wú)法支持熱點(diǎn)線路的挖掘。

現(xiàn)有細(xì)粒度行駛模式挖掘方法大多基于細(xì)粒度的軌跡數(shù)據(jù)(如GPS軌跡數(shù)據(jù))。例如，Yao等人[17]提出了一個(gè)基于深度學(xué)習(xí)的軌跡聚類算法，首先提取時(shí)空不變特征，然后基于seq2seq模型對(duì)軌跡數(shù)據(jù)進(jìn)行表征，最后在深度表征基礎(chǔ)上實(shí)現(xiàn)聚類。Cao等人[19]將行駛模式元素定義為頻繁路段周圍的區(qū)域，在此基礎(chǔ)上提出了一種基于子串樹(shù)數(shù)據(jù)結(jié)構(gòu)的行駛模式挖據(jù)算法。然而，聚類算法或序列模式挖掘算法挖掘出的行駛模式通常較短，難以對(duì)熱點(diǎn)線路進(jìn)行有效表征，且這些工作挖掘出的基本上都是單一對(duì)象的行駛模式。實(shí)際上，單一車輛的行駛模式通常只占熱點(diǎn)線路的一小部分[2]。例如，城市中可能存在一條從居住區(qū)到工作區(qū)的熱點(diǎn)線路，但通常大部分車輛不會(huì)行駛整條熱點(diǎn)線路，而是在這條熱點(diǎn)線路的中間某處駛?cè)?、某處駛出?/p>

與本文工作最相關(guān)的是Li等人[2]提出的FlowScan算法。FlowScan算法采用一個(gè)密度聚類算法在道路網(wǎng)絡(luò)中對(duì)熱點(diǎn)道路路段進(jìn)行擴(kuò)展，從而形成熱點(diǎn)線路。然而，F(xiàn)lowScan算法采用的是細(xì)粒度車輛軌跡數(shù)據(jù)，不適應(yīng)車牌時(shí)空數(shù)據(jù)。首先，由于交通攝像頭的空間稀疏性和識(shí)別不確定性，可能存在部分道路路段未部署交通攝像頭，或未能正確識(shí)別部分行駛車輛的車牌，導(dǎo)致重構(gòu)得到的車輛軌跡數(shù)據(jù)難以準(zhǔn)確映射到道路網(wǎng)絡(luò)中。其次，F(xiàn)lowScan算法會(huì)產(chǎn)生大量的熱點(diǎn)線路，其中某些是相似和冗余的，導(dǎo)致決策人員難以從中發(fā)現(xiàn)最有價(jià)值的信息。

2 問(wèn)題定義

定義1車牌時(shí)空數(shù)據(jù)。交通攝像頭可識(shí)別過(guò)往車輛的車牌并記錄時(shí)間。因此，車牌時(shí)空數(shù)據(jù)可被定義為一個(gè)三元組的集合LD={(Ik,Ck,Tk)}，Ik為車輛k的車牌號(hào)，Ck為記錄Ik的交通攝像頭的編號(hào)，Tk為Ck記錄Ik的時(shí)間。其中，Ck代表了空間屬性(每個(gè)交通攝像頭的經(jīng)緯度位置已知)，Tk代表了時(shí)間屬性。

定義2車輛軌跡。對(duì)車牌時(shí)空數(shù)據(jù)進(jìn)行交叉檢索和重構(gòu)可得到每輛車的軌跡。一輛車的軌跡可被定義為一個(gè)序列VT=，其中Ek為一個(gè)二元組Ek=(Ck,Tk)(Tk

定義3熱點(diǎn)線路。一條熱點(diǎn)線路被定義為一個(gè)序列R=(Ck代表一個(gè)交通攝像頭)，其中R中每連續(xù)K個(gè)交通攝像頭在指定時(shí)間段內(nèi)共享的車輛軌跡超過(guò)minSup條。

3 熱點(diǎn)線路挖掘

由于單一車輛行駛的不確定性，現(xiàn)有基于軌跡模式挖掘算法的熱點(diǎn)線路挖掘方法通常只能挖掘出很短的熱點(diǎn)線路。如圖1(a)所示，若要求每個(gè)行駛模式至少有4條軌跡支持，則現(xiàn)有軌跡模式挖掘算法只能挖掘出R1、R2和R3這3條較短的熱點(diǎn)線路。針對(duì)此問(wèn)題，弱化現(xiàn)有軌跡模式挖掘算法的限制，將熱點(diǎn)線路定義為一個(gè)道路路段的序列，該序列的指定長(zhǎng)度的任意子序列均共享大量共同車流。如圖1(b)所示，為一條熱點(diǎn)線路，由于其長(zhǎng)度為2的任意子序列(即、和)均共享大于等于5條車輛軌跡。

圖1 熱點(diǎn)線路挖掘問(wèn)題

由于交通攝像頭的空間稀疏性和識(shí)別不確定性，重構(gòu)得到的車輛軌跡無(wú)法準(zhǔn)確映射到道路網(wǎng)絡(luò)。因此，本文提出了一種無(wú)需道路網(wǎng)絡(luò)的從車牌時(shí)空數(shù)據(jù)中挖掘熱點(diǎn)線路的方法，該方法分為子模式挖掘和子模式拼接2個(gè)步驟。

子模式挖掘工作流程如下，給定時(shí)間段[Ts,Te]，采用子串模式挖掘算法從車輛軌跡數(shù)據(jù)中挖掘出長(zhǎng)度為K的子串模式。子串和子序列是最具代表性的2類模式，而子串模式與子序列模式的不同在于，子串模式要求模式中連續(xù)的元素在原始序列中也是連續(xù)的，而子序列模式只要求模式中連續(xù)的元素在原始序列中順序一致(可以不連續(xù))。之所以使用子串模式，是考慮到車輛在空間中的運(yùn)動(dòng)必須是連續(xù)的[19]。采用N-Gram算法挖掘子串模式：采用一個(gè)哈希表存儲(chǔ)每個(gè)子串模式和其對(duì)應(yīng)的支持度(即該子串模式出現(xiàn)的次數(shù))。對(duì)每條車輛軌跡VT，算法讀入連續(xù)的K個(gè)元素<(C1,T1)，…，(CK,TK)>。如果T1≥Ts且TK≤Te(即軌跡發(fā)生在指定時(shí)間段內(nèi))，則將作為一個(gè)候選子串模式，并將該候選子串模式在哈希表中的支持度增加1。最終，輸出所有支持度大于等于minSup的候選子串模式。

實(shí)際操作中，核心參數(shù)K和minSup的設(shè)置非常重要。一方面，參數(shù)K設(shè)置的過(guò)大會(huì)導(dǎo)致難以發(fā)現(xiàn)足量的子模式，而設(shè)置的過(guò)小則對(duì)熱點(diǎn)線路的要求過(guò)低(容易導(dǎo)致產(chǎn)生過(guò)多無(wú)意義的熱點(diǎn)線路)。另一方面，參數(shù)minSup的設(shè)置需要考慮實(shí)際的交通流量。在交通流量較大的區(qū)域中，minSup也應(yīng)設(shè)置的較大。然而，由于不同區(qū)域的實(shí)際交通流量差異較大，導(dǎo)致minSup的絕對(duì)數(shù)值難以統(tǒng)一設(shè)置。因此，通過(guò)設(shè)置一個(gè)(0, 1)的相對(duì)數(shù)值來(lái)估算minSup的絕對(duì)數(shù)值，方法如下：首先，提取所有長(zhǎng)度為2的子模式并計(jì)算它們的支持度。然后，繪制所有長(zhǎng)度為2的子模式支持度的CDF(累積分布函數(shù))曲線。最后，設(shè)置一個(gè)minSup的相對(duì)數(shù)值rMinSup(0

iCDF(p)=inf{x∈R:p≤CDF(x)}

(1)

子模式拼接工作流程如下。提出了一種將短的子模式拼接成長(zhǎng)的熱點(diǎn)線路的算法。算法流程如算法1所示，其主要工作為基于前向拼接和后向拼接概念構(gòu)造一棵雙向樹(shù)。首先，基于一個(gè)種子子模式(第3行)，算法調(diào)用遞歸函數(shù)不斷將其他子模式拼接到種子子模式上(第6行)，形成一棵雙向樹(shù)(包括一棵前向樹(shù)和一棵后向樹(shù))。然后，拼接各前向樹(shù)分支和各后向樹(shù)分支，得到候選熱點(diǎn)線路(第7～9行)。

定義4前向拼接和后向拼接。給定一個(gè)長(zhǎng)度為K的子模式P0，另一個(gè)長(zhǎng)度為K的子模式P1若滿足：P1的長(zhǎng)度為K-1的前綴可與P0的長(zhǎng)度為K-1的后綴完全匹配，則P1可與P0前向拼接。另一個(gè)長(zhǎng)度為K的子模式P2若滿足：P2的長(zhǎng)度為K-1的后綴可與P0的長(zhǎng)度為K-1的前綴完全匹配，則P2可與P0后向拼接。

算法1子模式拼接算法輸入:長(zhǎng)度為K的子模式集合PS輸出:候選熱點(diǎn)線路集合RS1.將PS復(fù)制到TS2.while TS不為空do3.從TS中找出支持度最大的子模式P4.將P從TS中刪除5.構(gòu)建2個(gè)樹(shù)節(jié)點(diǎn)fn(對(duì)應(yīng)P.CK)和bn(對(duì)應(yīng)P.C1)6.運(yùn)行函數(shù)ForwardExpand(fn)和BackwardExpand(bn)7.for以bn為根節(jié)點(diǎn)的后向樹(shù)的每個(gè)分支bbdo8.for以fn為根節(jié)點(diǎn)的前向樹(shù)的每個(gè)分支fbdo9.將bb的反轉(zhuǎn),和fb進(jìn)行拼接,得到R,并將R加入RS函數(shù)ForwardExpand(樹(shù)節(jié)點(diǎn)n)1.設(shè)P為樹(shù)節(jié)點(diǎn)n對(duì)應(yīng)的子模式2.從PS中找出所有可與P前向拼接的子模式集合FS3.forFS中每個(gè)子模式fpdo4.構(gòu)建一個(gè)新的樹(shù)節(jié)點(diǎn)nn(對(duì)應(yīng)fp. CK),并將其插入為樹(shù)節(jié)點(diǎn)n的子節(jié)點(diǎn)5.將fp從TS中刪除,并運(yùn)行函數(shù)ForwardExpand(nn)

算法1續(xù)

下面給出一個(gè)實(shí)例對(duì)子模式拼接算法進(jìn)行進(jìn)一步說(shuō)明。給定7個(gè)長(zhǎng)度為3的子模式P1= <1, 2, 3>，P2= <2, 3, 4>，P3= <2, 3, 5>，P4= <3, 4, 6>，P5= <3, 4, 7>，P6= <8, 1, 2>和P7= <9, 1, 2>，其中P1的支持度最大，則構(gòu)造的雙向樹(shù)如圖2所示(其中，樹(shù)節(jié)點(diǎn)用圓形代表，而正方形代表的是樹(shù)節(jié)點(diǎn)對(duì)應(yīng)的子模式)。從該雙向樹(shù)中，通過(guò)拼接前向樹(shù)分支和后向樹(shù)分支，可以提取出6個(gè)候選熱點(diǎn)線路，即R1= <8, 1, 2, 3, 5>，R2= <9, 1, 2, 3, 5>，R3= <8, 1, 2, 3, 4, 6>，R4= <8, 1, 2, 3, 4, 7>，R5= <9, 1, 2, 3, 4, 6>和R6= <9, 1, 2, 3, 4, 7>。

圖2 子模式拼接實(shí)例

4 熱點(diǎn)線路壓縮

熱點(diǎn)線路挖掘步驟會(huì)產(chǎn)生大量候選熱點(diǎn)線路，其中存在大量相似和冗余，導(dǎo)致決策人員難以從中發(fā)現(xiàn)最有價(jià)值的信息。以圖2為例，僅7個(gè)子模式就會(huì)產(chǎn)生6個(gè)候選熱點(diǎn)線路，而真實(shí)交通數(shù)據(jù)中通?？赏诰虺龊Ａ康淖幽Ｊ?，導(dǎo)致產(chǎn)生的候選熱點(diǎn)線路過(guò)多。此外，從圖2中產(chǎn)生的候選熱點(diǎn)線路中可發(fā)現(xiàn)，許多候選熱點(diǎn)線路非常相似(如R1和R2，R3和R4，R5和R6)。針對(duì)此問(wèn)題，提出了一個(gè)聚類排序算法，用于對(duì)候選熱點(diǎn)線路進(jìn)行壓縮，主要包括聚類和排序2個(gè)步驟：首先，聚類步驟對(duì)所有候選熱點(diǎn)線路進(jìn)行聚類。然后，排序步驟從每個(gè)聚類中挑選出最具代表性的候選熱點(diǎn)線路。

在聚類步驟中，基于最長(zhǎng)公共子序列算法定義候選熱點(diǎn)線路間的相似度，候選熱點(diǎn)線路Ri和Rj的相似度計(jì)算方法如式(2)所示。

S(Ri,Rj)=max{S(Ri→Rj),S(Rj→Ri)}

(2)

(3)

其中，LCSS(Ri,Rj)為Ri和Rj的最長(zhǎng)公共子序列。式(2)中使用了S(Ri→Rj)和S(Rj→Ri)的最大值作為Ri和Rj的相似度，其目的是為了更有利于較長(zhǎng)的候選熱點(diǎn)線路。這種情況下，較長(zhǎng)的候選熱點(diǎn)線路更容易與其他的候選熱點(diǎn)線路產(chǎn)生高相似度，使得較長(zhǎng)的候選熱點(diǎn)線路傾向于將較短的相似候選熱點(diǎn)線路吸收進(jìn)同一聚類，并更容易被挑選為聚類中的代表性候選熱點(diǎn)線路。

在此基礎(chǔ)上，采用Affinity Propagation聚類算法[23]對(duì)所有候選熱點(diǎn)線路進(jìn)行聚類處理。Affinity Propagation聚類算法的優(yōu)勢(shì)在于不需要預(yù)先設(shè)定聚類的數(shù)量，這符合熱點(diǎn)線路數(shù)量通常未知的現(xiàn)實(shí)情況。

在排序步驟中，從每個(gè)聚類中挑選出最具代表性的候選熱點(diǎn)線路。為此，給定一個(gè)聚類，計(jì)算其中每個(gè)候選熱點(diǎn)線路的權(quán)值，而熱點(diǎn)線路權(quán)值由表征度權(quán)值和重要度權(quán)值2部分構(gòu)成。

其中，表征度權(quán)值用于指示一個(gè)候選熱點(diǎn)線路代表其他候選熱點(diǎn)線路的能力，而候選熱點(diǎn)線路Rj代表候選熱點(diǎn)線路Ri的能力可由S(Ri→Rj)判斷，即Ri和Rj的最長(zhǎng)公共子序列能較多覆蓋Ri。因此，基于式(4)對(duì)候選熱點(diǎn)線路Rk的在聚類RC中的表征度權(quán)值進(jìn)行量化。

(4)

另一方面，重要度權(quán)值用于指示一個(gè)候選熱點(diǎn)線路是否經(jīng)過(guò)城市的重要區(qū)域。綜合考慮以下假設(shè)對(duì)候選熱點(diǎn)線路的重要度權(quán)值進(jìn)行量化。(1) 如果一個(gè)候選熱點(diǎn)線路包含的交通攝像頭更重要，則該候選熱點(diǎn)線路更重要。(2) 如果一個(gè)交通攝像頭被包含在更重要的候選熱點(diǎn)線路中，則該交通攝像頭更重要。(3) 一個(gè)交通攝像頭的重要度可由其檢測(cè)到的交通流量進(jìn)行量化。

上述假設(shè)中，假設(shè)(1)和假設(shè)(2)表明候選熱點(diǎn)線路和交通攝像頭間存在互增強(qiáng)關(guān)系。這與網(wǎng)頁(yè)排序算法HITS中定義的hub頁(yè)和authority頁(yè)間的關(guān)系類似，而HITS算法正是利用這種互增強(qiáng)關(guān)系計(jì)算網(wǎng)頁(yè)的重要度權(quán)值。因此，將交通攝像頭看成hub頁(yè)，將候選熱點(diǎn)線路看成authority頁(yè)，然后基于HITS算法的思想計(jì)算候選熱點(diǎn)線路的重要度權(quán)值。給定n個(gè)交通攝像頭和m個(gè)候選熱點(diǎn)線路，構(gòu)建一個(gè)m×n的矩陣MRC(其中MRC[i,j]指示第i條候選熱點(diǎn)線路是否包含第j個(gè)交通攝像頭)。假定PC和PR分別代表hub分?jǐn)?shù)向量和authority分?jǐn)?shù)向量，則可采用冪迭代算法計(jì)算最終的PC和PR。為將假設(shè)(3)反映在算法里，在每輪冪迭代中，authority分?jǐn)?shù)(代表候選熱點(diǎn)線路的分?jǐn)?shù))會(huì)按照交通攝像頭檢測(cè)到的交通流量成比例地傳播到hub分?jǐn)?shù)(代表交通攝像頭的分?jǐn)?shù))中，即交通攝像頭檢測(cè)到的交通流量作為分?jǐn)?shù)傳播的一個(gè)因子。算法2展示了基于冪迭代的候選熱點(diǎn)線路重要度權(quán)值計(jì)算算法，其中VT為一個(gè)n維的列向量(VT[k]代表第k個(gè)交通攝像頭歷史上在指定時(shí)間段內(nèi)檢測(cè)到的平均交通流量)。

圖3給出了一個(gè)候選熱點(diǎn)線路權(quán)值計(jì)算的實(shí)例。給定3條候選熱點(diǎn)線路(R1，R2和R3)和4個(gè)交通攝像頭(C1，C2，C3和C4)，假定R1，R2和R3屬于同一聚類，則R1，R2和R3的表征度權(quán)值分別為0.833，0.5和0.583。而當(dāng)執(zhí)行候選熱點(diǎn)線路重要度權(quán)值計(jì)算算法后，R1，R2和R3的重要度權(quán)值分別為0.363，0.248和0.389。因此，R1具有最高的表征度權(quán)值(由于R1與其他候選熱點(diǎn)線路的交疊部分最多)，而R3具有最高的重要度權(quán)值(由于R3經(jīng)過(guò)最重要的交通攝像頭C4)。

算法2候選熱點(diǎn)線路重要度權(quán)值計(jì)算算法輸入:關(guān)聯(lián)矩陣MRC,交通流量向量VT輸出:所有候選熱點(diǎn)線路的重要度權(quán)值1. 初始化P(0)C=[1,1,…,1︸n]T,P(0)R=[1,1,…,1︸m]T2. while算法未收斂do3. P(t+1)C=MTRC·P(t)R·VT, P(t+1)R=MRC·P(t+1)C// 第t輪迭代4. 將P(t+1)R歸一化5. 將最終PR輸出為重要度權(quán)值向量

圖3 一個(gè)候選熱點(diǎn)線路權(quán)值計(jì)算的實(shí)例

得到聚類中每個(gè)候選熱點(diǎn)線路的表征度權(quán)值rs和重要度權(quán)值is后，可對(duì)2個(gè)權(quán)值進(jìn)行加權(quán)求和得到候選熱點(diǎn)線路權(quán)值ws(如式(5)所示)，然后從每個(gè)聚類中挑選出權(quán)值最高的候選熱點(diǎn)線路作為最終的熱點(diǎn)線路，而這些最終的熱點(diǎn)線路可按照其包含的車流量進(jìn)行倒排排序。

ws=α×rs+(1-α)×is

(5)

5 實(shí) 驗(yàn)

5.1 數(shù)據(jù)集

采用杭州市的真實(shí)車牌時(shí)空數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，該數(shù)據(jù)集包含了部署在杭州市區(qū)的821個(gè)交通攝像頭，數(shù)據(jù)集時(shí)間跨度為2012年6月1日至2012年7月4日，以及2018年11月5日至2018年12月1日。實(shí)驗(yàn)僅考慮工作日(總共44 d)。最終數(shù)據(jù)集包含了195 579 733個(gè)車牌識(shí)別記錄，數(shù)據(jù)集中每天平均車牌識(shí)別記錄數(shù)為4 444 993(標(biāo)準(zhǔn)差為457 313)，每天平均檢測(cè)到的車輛數(shù)為724 636(標(biāo)準(zhǔn)差為73 096)。

基于對(duì)該數(shù)據(jù)集的統(tǒng)計(jì)分析，發(fā)現(xiàn)交通攝像頭存在較高的空間稀疏性和識(shí)別不確定性。如圖4所示，當(dāng)縮小地圖后，可以發(fā)現(xiàn)有很多道路未部署交通攝像頭。此外，該數(shù)據(jù)集中存在23 365 567條車牌識(shí)別記錄是錯(cuò)誤的(大概占總車牌識(shí)別記錄數(shù)的12%)。再次，交通攝像頭還有可能未檢測(cè)到經(jīng)過(guò)的車輛。

圖4 交通攝像頭的空間稀疏性

5.2 調(diào)參實(shí)驗(yàn)

本文提出的方法包括2個(gè)核心參數(shù)為K和minSup，這2個(gè)核心參數(shù)的設(shè)置直接影響方法的性能。其中，參數(shù)K必須大于等于3，這是由于長(zhǎng)度小于3的子模式無(wú)法被拼接(由于交通攝像頭基本都部署在道路路口，因此2個(gè)交通攝像頭構(gòu)成一條道路路段，而長(zhǎng)度為2的子模式只包含一條道路路段)。另一方面，參數(shù)minSup的設(shè)置需要考慮實(shí)際的交通流量。

在以下實(shí)驗(yàn)中，將時(shí)間段設(shè)置為08:00-09:00(即早高峰)。圖5顯示了調(diào)整參數(shù)K和rMinSup后方法性能的變化，這里方法性能的考查指標(biāo)包括挖掘出的熱點(diǎn)線路的平均長(zhǎng)度、平均車流量、最小車流量和數(shù)量。其中，將一條熱點(diǎn)線路包含的車流量計(jì)算為其包含的長(zhǎng)度為2的子模式的平均支持度。通常情況下，希望挖掘出的熱點(diǎn)線路的平均長(zhǎng)度更長(zhǎng)、車流量更大。如圖5(a)和圖5(b)所示，增大K和rMinSup后，熱點(diǎn)線路平均長(zhǎng)度顯著縮短，而平均車流量少量增加。這說(shuō)明K和rMinSup應(yīng)該設(shè)置的小一些。然而，將K和rMinSup設(shè)置的過(guò)小會(huì)引發(fā)以下問(wèn)題：挖掘出的熱點(diǎn)線路包含的車流量過(guò)小(如圖5(c)所示)或挖掘出的熱點(diǎn)線路數(shù)量爆炸性增加(如圖5(d)所示)。因此，將這2個(gè)參數(shù)設(shè)置如下：K=3，rMinSup=0.955(對(duì)應(yīng)的minSup絕對(duì)數(shù)值為172)。

圖5 參數(shù)K和rMinSup對(duì)方法性能的影響

5.3 方法評(píng)測(cè)

將本文提出的方法(稱為OurMining)與以下方法進(jìn)行比較評(píng)測(cè)。

(1) CloSpan?；贑loSpan算法[24]挖掘子模式，并基于第4節(jié)提出的方法對(duì)子模式進(jìn)行壓縮得到最終的熱點(diǎn)線路。

(2) FlowScan?；贔lowScan算法[2]挖掘候選熱點(diǎn)線路，并基于第4節(jié)提出的方法對(duì)候選熱點(diǎn)線路進(jìn)行壓縮得到最終的熱點(diǎn)線路。FlowScan采用一個(gè)密度聚類算法在道路網(wǎng)絡(luò)中將道路路段擴(kuò)展到其鄰接道路路段以形成熱點(diǎn)線路。道路路段r的鄰接道路路段集RS滿足：r與RS中任一道路路段間的最短道路網(wǎng)絡(luò)距離小于Eps。然而，基于車牌時(shí)空數(shù)據(jù)重構(gòu)得到的車輛軌跡無(wú)法進(jìn)行道路匹配。因此，將鄰接道路路段概念修改為鄰接交通攝像頭概念，即交通攝像頭c的鄰接交通攝像頭集合CS滿足：c與CS中任一交通攝像頭的直線距離小于dEps。在此基礎(chǔ)上，采用FlowScan算法將交通攝像頭擴(kuò)展到其鄰接交通攝像頭以形成熱點(diǎn)線路。

(3) DirectMining?；诘?節(jié)提出的方法挖掘候選熱點(diǎn)線路，不對(duì)候選熱點(diǎn)線路進(jìn)行壓縮，而僅基于包含的車流量對(duì)候選熱點(diǎn)線路進(jìn)行簡(jiǎn)單倒排排序。

設(shè)置α= 0.5，并將熱點(diǎn)線路的平均長(zhǎng)度和最大長(zhǎng)度、top-N熱點(diǎn)線路的城市車流覆蓋率作為評(píng)價(jià)指標(biāo)。其中，top-N熱點(diǎn)線路的城市車流覆蓋率為排序最靠前的N個(gè)熱點(diǎn)線路所包含的車流量(在本文中，即排序最靠前的N個(gè)熱點(diǎn)線路所包含的長(zhǎng)度為2的子模式的支持度總和)占城市總車流量(在本文中，即所有長(zhǎng)度為2的子模式的支持度總和)的比例。參數(shù)設(shè)置如下：K= 3(針對(duì)OurMining和DirectMining)，rMinSup=0.955(針對(duì)OurMining，CloSpan，F(xiàn)lowScan和DirectMining)，dEps=1 000～5 000 m(針對(duì)FlowScan，對(duì)應(yīng)FlowScan_1000～FlowScan_5000)。此外，為保證子模式元素的空間連續(xù)性，將CloSpan算法中模式元素的最大間隔限制為3。

實(shí)驗(yàn)結(jié)果如圖6所示，可以發(fā)現(xiàn)以下現(xiàn)象。第1，CloSpan僅能挖掘出很短的熱點(diǎn)線路，這是由于序列模式挖掘算法要求支持某個(gè)序列模式的車輛軌跡必須完全覆蓋這個(gè)序列模式，而通常一輛車的軌跡只能覆蓋熱點(diǎn)線路的一部分。第2，DirectMining能夠挖掘出最長(zhǎng)的熱點(diǎn)線路，但其top-N熱點(diǎn)線路的城市車流覆蓋率較低(即使N較大時(shí))。這是由于當(dāng)不進(jìn)行熱點(diǎn)線路壓縮時(shí)，大量熱點(diǎn)線路存在高度的重疊，特別是排序靠前的熱點(diǎn)線路(由于這些熱點(diǎn)線路基本上都集中在城市最繁忙的一、兩條線路上)，因此增大N也無(wú)法提升top-N熱點(diǎn)線路的城市車流覆蓋率。第3，當(dāng)dEps設(shè)置的較低時(shí)，F(xiàn)lowScan的性能較差，且FlowScan的top-N熱點(diǎn)線路的城市車流覆蓋率低于OurMining，特別是N較大時(shí)。對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析后發(fā)現(xiàn)，F(xiàn)lowScan可發(fā)現(xiàn)高質(zhì)量的熱點(diǎn)線路，但其召回率較低，這主要是由于鄰接交通攝像頭的不確定性造成的。首先，基于直線距離定義鄰接關(guān)系不合理(原始FlowScan是基于道路網(wǎng)絡(luò)距離定義道路路段的鄰接關(guān)系)。例如，同樣是部署在一條道路路段兩端的交通攝像頭，當(dāng)該道路路段是一條城市高速路時(shí)，其直線距離會(huì)很大，導(dǎo)致算法認(rèn)為其不存在鄰接關(guān)系。其次，F(xiàn)lowScan的密度聚類算法不適應(yīng)車牌時(shí)空數(shù)據(jù)。FlowScan的密度聚類算法挑選初始種子道路路段的方式為該道路路段包含至少minSup起始車流量或minSup終止車流量，而后者在車牌時(shí)空數(shù)據(jù)中無(wú)法考查。綜上，OurMining可發(fā)現(xiàn)質(zhì)量更高的熱點(diǎn)線路(長(zhǎng)度更長(zhǎng)，且更少的實(shí)例就能覆蓋更多的城市車流)。

圖6 不同方法的性能比較

圖7展示了2條挖掘出的熱點(diǎn)線路(圖7(a)展示了從早高峰時(shí)間段中挖掘出的排名第1的熱點(diǎn)線路，而圖7(b)展示了從晚高峰時(shí)間段中挖掘出的排名第1的熱點(diǎn)線路)。圖中熱點(diǎn)線路由一個(gè)折線代表(其中，圓點(diǎn)代表起點(diǎn)，箭頭代表終點(diǎn))，2個(gè)交通攝像頭之間的折線為其在道路網(wǎng)絡(luò)中的最短路徑。由圖7可以看出，杭州市早高峰最繁忙的熱點(diǎn)線路為由城市北部去往城市中心，而晚高峰最繁忙的熱點(diǎn)線路為由濱江區(qū)穿越城市中心高架路去往城市西部居住區(qū)。

圖7 熱點(diǎn)線路可視化

6 結(jié) 論

本文提出了一種從車牌時(shí)空數(shù)據(jù)中挖掘熱點(diǎn)線路的方法。該方法首先挖掘和拼接子模式以形成候選熱點(diǎn)線路，然后對(duì)候選熱點(diǎn)線路進(jìn)行聚類和排序以得到代表性熱點(diǎn)線路?；诤贾菔姓鎸?shí)車牌時(shí)空數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明：與現(xiàn)有方法相比，本文提出的方法可以發(fā)現(xiàn)更有價(jià)值的熱點(diǎn)線路(長(zhǎng)度更長(zhǎng)，且較少的實(shí)例就能覆蓋較多的城市車流)。