面向公共安全的時(shí)空數(shù)據(jù)挖掘綜述

王永坤，王海洋，潘平峻，李龍?jiān)鹨x,

(1.上海交通大學(xué) 中國(guó)城市治理研究院，上海 200240；2.上海交通大學(xué) 光纖通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，上海 200240)

0 前 言

隨著手持設(shè)備及傳感器技術(shù)的發(fā)展，大量用戶(hù)的時(shí)間和空間軌跡數(shù)據(jù)被記錄了下來(lái)。例如，智能手機(jī)已經(jīng)普及到了城市的絕大部分人群，智能手機(jī)中內(nèi)置的軟件和硬件，可以非常準(zhǔn)確地記錄用戶(hù)在某一時(shí)刻的位置，進(jìn)而可以記錄用戶(hù)較完整的時(shí)間、空間軌跡。另外，各種車(chē)載設(shè)備也可以記錄用戶(hù)的時(shí)空軌跡，比如出租車(chē)以及各種新能源車(chē)，都搭載了傳感器，可以以近似實(shí)時(shí)的速率上傳地理位置信息。還有最近興起的共享單車(chē)也搭載了傳感器，可以比較精確地知道單車(chē)及用戶(hù)的時(shí)空軌跡情況。在一些大城市比如上海，城市公共交通系統(tǒng)中的地鐵、公共汽車(chē)、出租車(chē)等，在計(jì)費(fèi)系統(tǒng)方面已經(jīng)連通起來(lái)，所以，用戶(hù)可以使用公共交通卡在各種交通工具中切換，從而用戶(hù)的軌跡也被各種交通工具記錄了下來(lái)。

在保證用戶(hù)隱私的前提下，對(duì)用戶(hù)的時(shí)間、空間軌跡數(shù)據(jù)進(jìn)行挖掘，可以發(fā)現(xiàn)很多個(gè)體和集體的行為規(guī)律，從而為更多的上層應(yīng)用和決策提供參考。已經(jīng)有很多研究者對(duì)用戶(hù)時(shí)空數(shù)據(jù)從不同方面入手開(kāi)展了大量的研究。由于出發(fā)點(diǎn)或者目標(biāo)不同，研究者們使用的數(shù)據(jù)也多種多樣，研究方法、研究目標(biāo)也有各自的特色。

本文嘗試從公共安全管理的角度出發(fā)，調(diào)研并討論相關(guān)的研究，期待將用戶(hù)的時(shí)空數(shù)據(jù)應(yīng)用于目前城市管理者和市民最關(guān)心的公共安全方面。公共安全管理是當(dāng)前城市管理的一個(gè)非常重要而且迫切的方面。隨著經(jīng)濟(jì)的高速增長(zhǎng)和城市化的快速發(fā)展，危害城市公共區(qū)域的事件和危機(jī)也不斷出現(xiàn)，給城市管理者帶來(lái)了巨大的壓力[1]。以往的人工方法的危機(jī)監(jiān)測(cè)和應(yīng)對(duì)方式既被動(dòng)又低效，因此，使用大數(shù)據(jù)及人工智能技術(shù)，利用個(gè)體移動(dòng)設(shè)備數(shù)據(jù)以及各種傳感器監(jiān)測(cè)信息，挖掘出潛在的風(fēng)險(xiǎn)，及時(shí)預(yù)警相關(guān)管理部門(mén)，成為當(dāng)前研究的熱點(diǎn)。

本文以公共安全管理為主要目標(biāo)，分4個(gè)方面調(diào)研了相關(guān)的研究工作，并分別給出了我們的研究進(jìn)展。我們使用了2類(lèi)比較有代表性的數(shù)據(jù)，第1類(lèi)是智能手機(jī)的時(shí)間、空間軌跡數(shù)據(jù)；第2類(lèi)是城市公共交通卡的換乘數(shù)據(jù)。第1類(lèi)是從“點(diǎn)”上分析挖掘個(gè)體或者群體的活動(dòng)規(guī)律，而第2類(lèi)數(shù)據(jù)則是從“線(xiàn)”上發(fā)現(xiàn)人群的聚散規(guī)律。基于第1類(lèi)數(shù)據(jù)，針對(duì)個(gè)體的發(fā)現(xiàn)介紹了相關(guān)工作；對(duì)于第2類(lèi)數(shù)據(jù)，我們分別從短時(shí)和突發(fā)2個(gè)方面，發(fā)現(xiàn)具有潛在危害性的事件，從而向有關(guān)部門(mén)預(yù)警，防范該區(qū)域可能出現(xiàn)的公共安全事件。

1 基于個(gè)體移動(dòng)模序異常的大規(guī)?；顒?dòng)識(shí)別

隨著世界人口的不斷增多，公共安全已經(jīng)日漸成為了一個(gè)需要重點(diǎn)關(guān)注的問(wèn)題。古往今來(lái)，由于人群一段時(shí)間內(nèi)聚集地過(guò)于密集、擁堵而引起的災(zāi)禍?zhǔn)录乙?jiàn)不鮮。而近年來(lái)，有關(guān)公共場(chǎng)所大規(guī)模人群活動(dòng)的不安全事件更是層出不窮?？梢哉f(shuō)對(duì)大規(guī)?；顒?dòng)的監(jiān)管控制是公共安全治理的一個(gè)重大話(huà)題。

移動(dòng)通訊技術(shù)和定位技術(shù)的發(fā)展使得研究者可以獲取大量人群的移動(dòng)數(shù)據(jù)、捕捉用戶(hù)的移動(dòng)軌跡。通過(guò)挖掘這些帶有用戶(hù)行為特征的軌跡數(shù)據(jù)可以得出很多有意義的結(jié)論。對(duì)大規(guī)?；顒?dòng)的監(jiān)管也開(kāi)始趨向于多時(shí)間維度、更廣泛空間維度和方法多樣化。

目前針對(duì)人類(lèi)移動(dòng)性研究和大規(guī)?；顒?dòng)檢測(cè)研究現(xiàn)狀有如下幾個(gè)方面。

1.1 人類(lèi)移動(dòng)性研究現(xiàn)狀

在文獻(xiàn)[2]中，研究者發(fā)現(xiàn)人類(lèi)移動(dòng)模式并不是隨時(shí)間隨機(jī)分布的，而是在一個(gè)時(shí)間周期內(nèi)由大量重復(fù)性事件再加上一些少量的突發(fā)事件組成。這種非泊松性質(zhì)的人類(lèi)活動(dòng)性是對(duì)人類(lèi)移動(dòng)性分析的基礎(chǔ)。人類(lèi)移動(dòng)是由大部分的常規(guī)性規(guī)律性移動(dòng)和一部分差異化的突發(fā)性移動(dòng)組成。在常規(guī)性研究方面，文獻(xiàn)[3]證實(shí)了人類(lèi)移動(dòng)具有很高的可預(yù)測(cè)性，約有70%的時(shí)間用戶(hù)都基本處于其該時(shí)段最常訪(fǎng)問(wèn)的地方，這種高可預(yù)測(cè)性根源于人類(lèi)空間運(yùn)動(dòng)的高度規(guī)則性。文獻(xiàn)[4]同樣證實(shí)了這一點(diǎn)，每個(gè)個(gè)體都具有高度的時(shí)空維度的規(guī)律性。每個(gè)個(gè)體都具有一定的與時(shí)間無(wú)關(guān)的遷移距離特征，并且總是有很大可能性會(huì)回到一些高頻率出現(xiàn)過(guò)的地區(qū)。文獻(xiàn)[5]的研究者使用移動(dòng)模序?qū)θ祟?lèi)移動(dòng)模式進(jìn)行了探索。通過(guò)對(duì)使用個(gè)人問(wèn)卷調(diào)查和匿名的移動(dòng)電話(huà)數(shù)據(jù)獲得的日常移動(dòng)數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)性分析，研究者發(fā)現(xiàn)17種不同的移動(dòng)模序就可以覆蓋來(lái)自不同國(guó)家的90%調(diào)研者的移動(dòng)出行模式。同時(shí)，文獻(xiàn)[5]中提出可以使用移動(dòng)距離分布p(r)、回轉(zhuǎn)半徑r(t)、一段時(shí)間內(nèi)的訪(fǎng)問(wèn)位置數(shù)S(t)這3個(gè)指標(biāo)來(lái)描述人類(lèi)移動(dòng)模式?；谌祟?lèi)移動(dòng)模式的常規(guī)性，研究者通過(guò)定量研究發(fā)現(xiàn)在大量人群中這3個(gè)指標(biāo)存在一個(gè)普遍結(jié)論：都近似服從各自參數(shù)的冪律分布。這無(wú)疑對(duì)人類(lèi)移動(dòng)的常規(guī)性是一個(gè)有力的說(shuō)明。

同時(shí)人類(lèi)移動(dòng)也由一部分帶有差異化的突發(fā)性事件組成。即使面對(duì)相同原因的外界刺激，不同個(gè)性的人也會(huì)做出不同的移動(dòng)性反應(yīng)，因此，這部分突發(fā)性事件在數(shù)據(jù)中的存在可以幫助我們區(qū)分不同用戶(hù)。文獻(xiàn)[6]指出不同個(gè)體移動(dòng)性上的差別是由個(gè)體移動(dòng)模式和一定的群體異質(zhì)性相互卷積造成的。而文獻(xiàn)[7-8]都指出了人類(lèi)移動(dòng)行為很大程度上會(huì)受到彼此之間的社會(huì)交流影響。在社交關(guān)系中，雙向邊的好友關(guān)系對(duì)于空間位置移動(dòng)軌跡的影響更大。文獻(xiàn)[8]詳細(xì)對(duì)比了社交關(guān)系對(duì)移動(dòng)模式影響在不同用戶(hù)上的差別，發(fā)現(xiàn)性別、年齡的不同使得用戶(hù)在空間移動(dòng)簽到上也有很大差異。這種差異性使得在進(jìn)行移動(dòng)預(yù)測(cè)時(shí)需要考慮用戶(hù)的自身屬性。文獻(xiàn)[9]則使用社交媒體簽到數(shù)據(jù)以及由簽到數(shù)據(jù)獲得的移動(dòng)軌跡數(shù)據(jù)反向推斷用戶(hù)的一些固有屬性，進(jìn)行用戶(hù)畫(huà)像。通過(guò)移動(dòng)性的分析在推斷用戶(hù)年齡層次、婚姻狀況、教育程度上都取得了較好的成果，這從另一個(gè)方向證明了人類(lèi)移動(dòng)會(huì)受個(gè)性化因素影響。

1.2 大規(guī)模活動(dòng)檢測(cè)現(xiàn)狀

大規(guī)?；顒?dòng)或是一些異?；顒?dòng)在時(shí)空層面上，會(huì)導(dǎo)致一個(gè)區(qū)域在一個(gè)時(shí)間段內(nèi)反常地聚集大量的人群；在人群整體層面上，會(huì)導(dǎo)致一批過(guò)去時(shí)空距離沒(méi)有相關(guān)性的人在一個(gè)時(shí)間段內(nèi)聚集在一起；在個(gè)體層面上，會(huì)導(dǎo)致一個(gè)有很強(qiáng)移動(dòng)規(guī)律性的個(gè)體產(chǎn)生有異于往常的移動(dòng)行為。大規(guī)?；顒?dòng)的監(jiān)測(cè)在時(shí)間尺度上可以分成3個(gè)部分：事前預(yù)測(cè)、事中監(jiān)控和事后檢測(cè)挖掘。其中，事前預(yù)測(cè)主要使用交通數(shù)據(jù)、社交簽到數(shù)據(jù)，在已有大量用戶(hù)移動(dòng)軌跡數(shù)據(jù)和活動(dòng)記錄的基礎(chǔ)上，對(duì)未來(lái)可能發(fā)生的大規(guī)?；顒?dòng)進(jìn)行預(yù)測(cè)[10-12]。而事中監(jiān)控則主要使用一些活動(dòng)、人流量較大較密集區(qū)域的現(xiàn)場(chǎng)監(jiān)控設(shè)備進(jìn)行人流量的自動(dòng)識(shí)別統(tǒng)計(jì)[13-14]。文獻(xiàn)[13]提出了一種基于多特征融合的人數(shù)統(tǒng)計(jì)算法，可以快速而準(zhǔn)確地計(jì)算出視頻中大規(guī)模活動(dòng)人數(shù)，以方便管理者進(jìn)行現(xiàn)場(chǎng)監(jiān)管。文獻(xiàn)[14]利用多個(gè)監(jiān)控器即時(shí)地檢測(cè)人群活動(dòng)，將多個(gè)監(jiān)視器結(jié)果進(jìn)行匯總評(píng)判并可以即時(shí)地給出對(duì)活動(dòng)時(shí)間的檢測(cè)結(jié)果。事后檢測(cè)挖掘部分與本文主題契合，是本文的研究重點(diǎn)，在該領(lǐng)域同樣有大量研究成果[15-18]。文獻(xiàn)[15]把聚集的概念定義為大量個(gè)體持續(xù)、穩(wěn)定地以高密度狀態(tài)聚集在一個(gè)區(qū)域里，并研究了如何從軌跡數(shù)據(jù)庫(kù)中發(fā)現(xiàn)這種聚集模式。文獻(xiàn)[16]介紹了一種使用海量移動(dòng)手機(jī)數(shù)據(jù)作為數(shù)據(jù)源，基于貝葉斯位置推斷框架的社會(huì)事件檢測(cè)方法，并討論了一些未來(lái)可行的時(shí)間檢測(cè)技術(shù)。文獻(xiàn)[17]通過(guò)分析非洲一些國(guó)家的手機(jī)信令定位數(shù)據(jù)，定義了一種“圓柱聚類(lèi)法”來(lái)捕捉處理這種稀疏的數(shù)據(jù)，并通過(guò)一系列方法從軌跡數(shù)據(jù)中提取出異常聚集人群。最終該方法在稀疏數(shù)據(jù)集上識(shí)別異常聚集人群上的效果被證明比簡(jiǎn)單的聚集算法更好。文獻(xiàn)[18]則使用了隱馬爾科夫模型來(lái)尋找具有相同時(shí)空移動(dòng)模式的用戶(hù)并檢測(cè)其聚集行為。上述大規(guī)?；顒?dòng)檢測(cè)的相關(guān)工作數(shù)據(jù)來(lái)源與事前預(yù)測(cè)和事中監(jiān)控較為不同，大多數(shù)使用的是移動(dòng)設(shè)備的位置記錄功能，包括基站定位，社交網(wǎng)絡(luò)位置簽到、GPS(global positioning system)定位以及WIFI熱點(diǎn)定位。

最后文獻(xiàn)[19]使用移動(dòng)手機(jī)數(shù)據(jù)分析了用戶(hù)移動(dòng)性和大規(guī)模社會(huì)事件的關(guān)系，發(fā)現(xiàn)舉辦地點(diǎn)距離用戶(hù)的家越近，越會(huì)吸引用戶(hù)參加從而改變其移動(dòng)性。該研究證明了大規(guī)?；顒?dòng)和用戶(hù)移動(dòng)性之間的相互關(guān)聯(lián)和互相影響。本文將繼續(xù)深入探究這種影響在數(shù)據(jù)中的表現(xiàn)。

1.3 筆者的相關(guān)工作

進(jìn)行大規(guī)?；顒?dòng)檢測(cè)一方面可以幫助我們對(duì)人群移動(dòng)模式有更深入的了解，深入地探索大規(guī)?；顒?dòng)對(duì)人類(lèi)移動(dòng)性的影響，以及人類(lèi)移動(dòng)性變化對(duì)這種影響的反映情況。

使用移動(dòng)模序(motif)[5]作為研究方法，該方法可以抽象地表現(xiàn)單個(gè)個(gè)體的移動(dòng)結(jié)構(gòu)。我們已知大規(guī)?；顒?dòng)會(huì)對(duì)單個(gè)個(gè)體的單次移動(dòng)活動(dòng)或移動(dòng)選擇產(chǎn)生巨大影響，而借助移動(dòng)模序的變化可以探索大規(guī)?；顒?dòng)對(duì)個(gè)體的整體移動(dòng)性結(jié)構(gòu)造成的影響。

單個(gè)個(gè)體的移動(dòng)結(jié)構(gòu)變化很難影響整體移動(dòng)結(jié)構(gòu)分布的變化，而大規(guī)模活動(dòng)會(huì)造成相當(dāng)大一批人的移動(dòng)結(jié)構(gòu)都產(chǎn)生變化，因此這種變化會(huì)展示在整體移動(dòng)結(jié)構(gòu)分布上，從而使得我們可以在整體移動(dòng)結(jié)構(gòu)分布的層面上研究變化趨勢(shì)，發(fā)現(xiàn)大規(guī)?；顒?dòng)。本研究從多源時(shí)空數(shù)據(jù)中提取模序，并通過(guò)檢測(cè)個(gè)體的異常模序來(lái)推測(cè)大型活動(dòng)。圖1給出了我們的工作流程。

圖1 工作流程框架Fig.1 Flowchart of system

本研究場(chǎng)景下的校園內(nèi)大規(guī)?；顒?dòng)事件，映射到社會(huì)的場(chǎng)景下就是一些社會(huì)事件，這些大規(guī)模活動(dòng)或社會(huì)事件的存在可能帶有一些危害性，需要監(jiān)管者對(duì)其發(fā)生發(fā)展進(jìn)行足夠的監(jiān)管。在歷史數(shù)據(jù)上進(jìn)行大規(guī)?；顒?dòng)檢測(cè)，可以幫助管理者發(fā)現(xiàn)一些始終沒(méi)有被記錄在案的大規(guī)?；顒?dòng)。如果能夠從歷史數(shù)據(jù)中挖掘檢測(cè)到這些無(wú)備案的大規(guī)模活動(dòng)，則日后對(duì)該類(lèi)活動(dòng)可以形成及時(shí)而有效的備案。而對(duì)有備案記錄的大規(guī)?；顒?dòng)的檢測(cè)挖掘，可以研究該活動(dòng)的參與度以及該活動(dòng)在人群中的影響力，幫助監(jiān)管者對(duì)大規(guī)模活動(dòng)有更深入的掌握。通過(guò)在歷史數(shù)據(jù)上的活動(dòng)檢測(cè)，可以對(duì)大規(guī)模聚集事件進(jìn)行事前預(yù)測(cè)、事中監(jiān)控、事后挖掘3個(gè)維度的協(xié)同管理，完善大型事件的監(jiān)管機(jī)制。

2 基于時(shí)空軌跡檢索的團(tuán)伙發(fā)現(xiàn)

在實(shí)際應(yīng)用中，常常有這樣的問(wèn)題：已知一個(gè)嫌疑人的軌跡，但是不知道他有沒(méi)有其他團(tuán)伙?；蛘呓o定一個(gè)人的軌跡，如何找到和他一起移動(dòng)過(guò)的人。

用戶(hù)的時(shí)空軌跡可以看做是用戶(hù)位置隨時(shí)間變化的時(shí)間序列?；跁r(shí)空軌跡檢索的團(tuán)伙發(fā)現(xiàn)定義為以下問(wèn)題：在一群人的時(shí)空軌跡數(shù)據(jù)庫(kù)中，給定一個(gè)人的軌跡，如何找到與其具有一定相似子軌跡的人。實(shí)際的軌跡數(shù)據(jù)相似度度量需要考慮如下問(wèn)題。

1)異頻采樣性：軌跡的時(shí)間序列并不能保證按照固定的間隔采樣。例如手機(jī)信令產(chǎn)生的軌跡數(shù)據(jù)可以由用戶(hù)主動(dòng)的行為產(chǎn)生，也可以由手機(jī)與基站的通信、切換等被動(dòng)產(chǎn)生。這種采樣的不均勻性影響了相似度的度量。

2)時(shí)間序列性：軌跡點(diǎn)的產(chǎn)生伴隨著時(shí)間戳，2條軌跡的相似應(yīng)當(dāng)不僅僅在形狀上相似，還應(yīng)該在時(shí)間上相似。

3)異常點(diǎn)：由于傳感器的失效，或者設(shè)備的故障，可以會(huì)帶來(lái)時(shí)間或空間上的異常點(diǎn)。常規(guī)的歐氏距離的方法可能會(huì)因?yàn)楫惓｜c(diǎn)的存在計(jì)算出非常大的距離。

4)不等長(zhǎng)度：在實(shí)際應(yīng)用中，2條軌跡中包含的軌跡點(diǎn)數(shù)量并不能保證是一樣的。因此，相似度度量要截?cái)嚅L(zhǎng)的軌跡或者填充短的軌跡。

5)效率：為了保證實(shí)際應(yīng)用中的可用性，需要保證相似度的計(jì)算要相對(duì)簡(jiǎn)單。

6)相似子軌跡：2條軌跡相似并不一定處處相似，若2條軌跡存在一定長(zhǎng)度的子軌跡互相相似，那么也應(yīng)當(dāng)給予合適的相似度。

2.1 軌跡檢索的研究現(xiàn)狀

但在實(shí)際應(yīng)用中，2條軌跡的長(zhǎng)度不一定相等，因此，Agrawal等提出動(dòng)態(tài)時(shí)間彎曲 (dynamic time warping，DTW) 距離，DTW允許一些點(diǎn)重復(fù)使用，將相似度度量轉(zhuǎn)化為最優(yōu)化問(wèn)題，來(lái)獲得滿(mǎn)足約束條件的代價(jià)最小的路徑，使得得到的總距離最小[20-21]。DTW的算法為

(1)

(1)式中：m,n分別為軌跡A，B的長(zhǎng)度；Rest(A)指軌跡A去除首項(xiàng)后的剩余軌跡。

然而，由于軌跡數(shù)據(jù)中常常存在大量的噪聲，使得DTW無(wú)法找到合適的匹配。為了解決這個(gè)問(wèn)題，Michail等研究者提出了基于公共子序列(longest common subsequence，LCSS)的方法來(lái)度量軌跡的相似度[22]，基于LCSS的方法允許跳過(guò)某些噪聲點(diǎn)，并簡(jiǎn)化的計(jì)算的復(fù)雜度。使用閾值ε來(lái)控制2點(diǎn)匹配時(shí)允許的距離，使用閾值δ來(lái)控制軌跡中2點(diǎn)匹配允許的時(shí)間差?；贚CSS的度量算法為

LCSSε,δ(A,B)=

(2)

(2)式中，Head(A)指軌跡A去除尾項(xiàng)后的剩余軌跡。

類(lèi)似于最大公共子序列的方法，Chen等[23]提出了基于編輯距離的實(shí)序列編輯距離(edit distance on real sequence，EDR)[21]。編輯距離又稱(chēng)Levenstein距離，指兩字符串之間由其中一個(gè)轉(zhuǎn)化為另一個(gè)所需的最少編輯次數(shù)。EDR使用閾值ε來(lái)控制匹配的過(guò)程，并為子序列的匹配賦予懲罰。EDR的算法為

(3)

Chen等[23]還提出了實(shí)數(shù)代價(jià)編輯距離，通過(guò)給定一個(gè)固定的參考點(diǎn)來(lái)結(jié)合DTW和EDR的優(yōu)勢(shì)。

除了確定的軌跡外，對(duì)于不確定的軌跡，即軌跡X是確定的軌跡O和一系列的概率分布函數(shù)的組合。Chunyang等[24]研究者提出了KSQ(top-k similarity query)，KSQ集中于在不確定的軌跡數(shù)據(jù)庫(kù)中，找到最相似的k條軌跡，又稱(chēng)Top-k查詢(xún)。其中，最關(guān)鍵的部分是如何近似地量化2條不確定軌跡的相似度。KSQ采用了一個(gè)新的距離測(cè)度和一個(gè)可擴(kuò)展的索引架構(gòu)來(lái)支持查詢(xún)。

對(duì)于語(yǔ)義的軌跡，即以語(yǔ)義的位置來(lái)代替實(shí)際經(jīng)緯度位置的軌跡。Xiao等[25]研究者將相似度度量從實(shí)際的物理位置擴(kuò)展到了語(yǔ)義空間。在沒(méi)有物理空間限制的情況下，可以度量不同城市中生活的用戶(hù)的相似度。在語(yǔ)義空間中，從軌跡中生成駐留點(diǎn)，使用駐留點(diǎn)對(duì)應(yīng)興趣點(diǎn)(point of interes，POI)的分布來(lái)表示一條軌跡。這樣不同用戶(hù)的駐留點(diǎn)就可以聚類(lèi)為層次結(jié)構(gòu)。

以上的研究大多是對(duì)于整條軌跡的查詢(xún)，沒(méi)有考慮其中具有相似子軌跡的情況。對(duì)于相似子軌跡的距離測(cè)量，Jeung等[26]研究者提出了基于最小外接矩形(minimum bounding rectangle, MBR)的子軌跡度量。MBR將子軌跡用最小外接矩形包裹，然后使用矩形的端點(diǎn)坐標(biāo)(xu,yu),(xl,yl)描述軌跡?；贛BR的相似度Dmin(B1,B2)定義為點(diǎn)(B1,B2)中最小的距離，計(jì)算公式為

(4)

(5)

Lee等[27]研究者提出了另一種相似度測(cè)量，叫做軌跡-豪斯多夫距離(Trajectory-Hausdorff distance)，Dhaus是3種距離的加權(quán)和，距離測(cè)量的公式為

Dhaus=w1d⊥+w2d‖+w3dθ,

(6)

(6)式中：w1,x2,x3是權(quán)重，根據(jù)實(shí)際應(yīng)用取不同的值；d⊥表示軌跡之間的分離程度的聚合垂直距離；d‖表示軌跡長(zhǎng)度區(qū)別的聚合平行距離；dθ表示軌跡方向上的區(qū)別的角距離，其計(jì)算方法分別為

(7)

d‖=min(d‖,a，d‖,b)

(8)

dθ=‖L2‖·sinθ

(9)

(9)式中：θ表示角度；L2表示軌跡夾角的對(duì)邊長(zhǎng)度。

2.2 筆者的工作

對(duì)于手機(jī)基站提取的用戶(hù)軌跡，與GPS等軌跡數(shù)據(jù)不同，我們從中觀察到一種現(xiàn)象：基站中提取的用戶(hù)軌跡，大部分用戶(hù)都具有自己固定的活動(dòng)空間，用戶(hù)絕大多數(shù)軌跡都在小范圍空間里產(chǎn)生。

根據(jù)這個(gè)現(xiàn)象，我們發(fā)現(xiàn)在相似性查詢(xún)的過(guò)程中，大部分的相似性比對(duì)計(jì)算都是沒(méi)有必要的。如果2個(gè)用戶(hù)的活動(dòng)空間根本沒(méi)有交集，那么也就沒(méi)有必要比對(duì)2人的軌跡。因此，設(shè)計(jì)了基于區(qū)域駐留時(shí)長(zhǎng)的無(wú)關(guān)用戶(hù)過(guò)濾算法。將一個(gè)城市中所有基站的位置，通過(guò)mean-shift算法聚類(lèi)為上百個(gè)區(qū)域，然后為每個(gè)用戶(hù)統(tǒng)計(jì)其在各個(gè)區(qū)域的駐留時(shí)長(zhǎng)。這樣就得到了用戶(hù)的駐留特征。

得到了每個(gè)用戶(hù)的駐留特征后，就可以通過(guò)余弦相似度的方法過(guò)濾掉無(wú)關(guān)用戶(hù)。具體來(lái)講，當(dāng)查詢(xún)某個(gè)用戶(hù)的相似軌跡時(shí)，首先根據(jù)查詢(xún)的用戶(hù)的駐留特征，與其他用戶(hù)的特征進(jìn)行余弦相似度計(jì)算。該過(guò)程的計(jì)算復(fù)雜度為O(n)，遠(yuǎn)小于軌跡相似度比對(duì)的O(n2)。實(shí)驗(yàn)中保留相似度大于0.1的用戶(hù)。

這樣，在實(shí)際30萬(wàn)人的手機(jī)基站軌跡數(shù)據(jù)庫(kù)中，每個(gè)用戶(hù)只需要比對(duì)幾百個(gè)用戶(hù)的軌跡，而不用一一比對(duì)。這樣就加快了相似軌跡檢索的速度。

對(duì)于余下的用戶(hù)，我們提出了基于弗雷歇距離的滑動(dòng)窗口算法。其中，弗雷歇距離F(A,B)定義為

F(A,B)=infα,βmaxt∈[0,1]{d(A(α(t))),B(β(t))}

(10)

(10)式中：α，β分別為單位區(qū)間上的2個(gè)重新參數(shù)化(reparameterization)函數(shù)。

3 城市有軌交通網(wǎng)絡(luò)短時(shí)客流預(yù)測(cè)

短時(shí)交通流預(yù)測(cè)是智能交通系統(tǒng)(intelligent traffic system，ITS)的重要方面，其能夠緩解交通擁堵，減少交通擁堵帶來(lái)的污染和能源消耗。同時(shí)，如果沒(méi)有交通預(yù)測(cè)，人們只能依靠現(xiàn)有的交通狀態(tài)推斷未來(lái)的交通情況，這樣的推斷是不能滿(mǎn)足實(shí)際需求的。相反地，交通流預(yù)測(cè)可以利用歷史交通流和現(xiàn)有交通情況來(lái)預(yù)測(cè)未來(lái)交通情況[28]。

由于短時(shí)交通預(yù)測(cè)的重要性，大量的研究者一直在探索交通流預(yù)測(cè)的理論并提出了相應(yīng)的預(yù)測(cè)方法。雖然交通流數(shù)據(jù)復(fù)雜多變，影響其的因素眾多，如天氣狀況、節(jié)假日、特殊的事件等，但是縱觀現(xiàn)有的交通流預(yù)測(cè)方法，可以發(fā)現(xiàn)，交通流預(yù)測(cè)方法大致可以分為以下2個(gè)方面。

1)時(shí)間序列預(yù)測(cè)模型：研究者通過(guò)構(gòu)造數(shù)學(xué)模型或者利用神經(jīng)網(wǎng)絡(luò)等方法，捕捉交通流數(shù)據(jù)預(yù)測(cè)未來(lái)與過(guò)去之間交通狀態(tài)的關(guān)系

2)多模式預(yù)測(cè)模型：研究者利用交通流數(shù)據(jù)的多模式特性來(lái)預(yù)測(cè)，如空間相似性和傳播性、周與天等模式下的周期性等。其中，空間相似性和傳播性是指：交通流數(shù)據(jù)在鄰近的路段和截面，表現(xiàn)出一定空間相似性和傳播性，這一信息有助于更加準(zhǔn)確地預(yù)測(cè)未來(lái)的交通狀態(tài)。對(duì)于周、天等模式下的周期性是指：由于人們出行的習(xí)慣與大部分工作的性質(zhì)，交通流數(shù)據(jù)在天與天之間、周與周之間呈現(xiàn)了強(qiáng)烈的周期性，有效利用周期性能夠提高預(yù)測(cè)的準(zhǔn)確度[29]。

下面我們將具體分析現(xiàn)有交通流預(yù)測(cè)方法。

3.1 時(shí)間序列預(yù)測(cè)模型

由于交通流數(shù)據(jù)隨時(shí)間變化，故早期的預(yù)測(cè)方法都將其構(gòu)建成時(shí)間序列，再利用數(shù)學(xué)模型，挖掘交通流數(shù)據(jù)的時(shí)間模式變化特征來(lái)預(yù)測(cè)未來(lái)的交通流量，其預(yù)測(cè)模型可以抽象為

[wt,wt+1,…,wt+d]=f([wt-1,wt-2,…,wt-h])

(11)

(11)式中：d表示預(yù)測(cè)區(qū)間的長(zhǎng)度；h表示歷史數(shù)據(jù)的長(zhǎng)度；f()表示未來(lái)預(yù)測(cè)數(shù)據(jù)與歷史數(shù)據(jù)之間的關(guān)系函數(shù)。這種預(yù)測(cè)模型，數(shù)據(jù)只有一個(gè)時(shí)間維度，數(shù)據(jù)的表達(dá)形式呈向量流。

在時(shí)間序列預(yù)測(cè)模型中，最常見(jiàn)的是自回歸積分滑動(dòng)平均模型(autoregressive integrated moving average model，ARIMA)[30]，這種方法是基于時(shí)間序列的自相關(guān)分析來(lái)捕捉交通流數(shù)據(jù)未來(lái)與歷史的關(guān)系。由于交通流數(shù)據(jù)在時(shí)間上表現(xiàn)為強(qiáng)烈的非線(xiàn)性，而ARIMA等線(xiàn)性模型無(wú)法捕捉交通流數(shù)據(jù)的非線(xiàn)性變化，因此，一些研究者提出了大量的非線(xiàn)性預(yù)測(cè)方法，如M. Castro-Neto等[31]提出了自向量回歸模型(support vector regression)來(lái)挖掘交通流數(shù)據(jù)的非線(xiàn)性變化。為了減少自向量回歸模型的計(jì)算復(fù)雜度，James Haworth等[32]提出了線(xiàn)核嶺(online kernel ridge)回歸模型。同時(shí)，一些研究者也開(kāi)始采用神經(jīng)網(wǎng)絡(luò)(neural network，NN)來(lái)挖掘未來(lái)交通狀況和歷史數(shù)據(jù)之間的非線(xiàn)性關(guān)系。其中比較典型的一個(gè)工作是文獻(xiàn)[33], 在文中，他們提出了一種基于神經(jīng)網(wǎng)絡(luò)的交通流模型，其目的是將其納入實(shí)時(shí)自適應(yīng)城市交通控制系統(tǒng)。建模分為2個(gè)部分，首先，交通流由局部神經(jīng)網(wǎng)絡(luò)在單個(gè)信號(hào)鏈路上建模；其次，基于局部神經(jīng)網(wǎng)絡(luò)之間的通信，交通流量在廣泛的接口網(wǎng)絡(luò)上建模。同時(shí)，基于模擬數(shù)據(jù)，文章也總結(jié)了應(yīng)用于交通流量建模的神經(jīng)網(wǎng)絡(luò)的潛力。

文獻(xiàn)[34]比較和結(jié)合了2種典型的時(shí)間序列預(yù)測(cè)方法：ANN (artificial neural network)和ARIMA。在ANN模型中，過(guò)去的事件能夠被分析并且模式能夠被推斷出，利用這些模式就可以進(jìn)一步預(yù)測(cè)出未來(lái)的交通流量。該工作指出了，在ARIMA或ANN模型的傳統(tǒng)結(jié)構(gòu)中，通常都是假設(shè)先前的模式將會(huì)被延續(xù)到未來(lái)的交通行為中，但是如果這個(gè)假設(shè)不成立，則預(yù)測(cè)效果將會(huì)不佳。因此，該工作引入一種判斷調(diào)整機(jī)制來(lái)影響糾正少量和不規(guī)則的未來(lái)事件。實(shí)驗(yàn)證明判斷調(diào)整技術(shù)有助于減少預(yù)測(cè)誤差。此外，ANN和ARIMA結(jié)合的模型明顯優(yōu)于他們各自的基礎(chǔ)模型。與其他研究不同的是，該工作指出了ARIMA模型優(yōu)于ANN模型。

3.2 多模式預(yù)測(cè)模型

對(duì)于多模式預(yù)測(cè)方法，研究者在原來(lái)的時(shí)間序列數(shù)據(jù)基礎(chǔ)上增加了空間信息或周期性信息。這是因?yàn)樵诮煌髦朽徑慕煌鲾?shù)據(jù)存在著一定的關(guān)聯(lián)性，如在交通路網(wǎng)中道路上游的交通流量往往決定著下游的交通流量，而當(dāng)交通流量較大時(shí)，下游交通流量又會(huì)反過(guò)來(lái)影響上游交通流量[34]。因此，單靠時(shí)間維度上的預(yù)測(cè)模型往往會(huì)忽略空間上的特性，導(dǎo)致交通流數(shù)據(jù)信息的缺失，使得預(yù)測(cè)準(zhǔn)確率下降。故有效地利用時(shí)空特性能夠得到較好的預(yù)測(cè)性能，相應(yīng)的預(yù)測(cè)模型為

(12)

(12)式中：si表示第i個(gè)預(yù)測(cè)位置；d表示預(yù)測(cè)區(qū)間的長(zhǎng)度；h表示歷史數(shù)據(jù)的長(zhǎng)度。這樣的數(shù)據(jù)表現(xiàn)形式即為矩陣流數(shù)據(jù)。

典型的多模預(yù)測(cè)方法是Van Lint等[35]提出的狀態(tài)空間神經(jīng)網(wǎng)絡(luò)，在基礎(chǔ)的神經(jīng)網(wǎng)絡(luò)模型中加入了空間信息，即路段各個(gè)截面的交通狀態(tài)，以提高預(yù)測(cè)的準(zhǔn)確度。文獻(xiàn)[36]分析了交通流量的天模式，并確定天模式是否能夠改善流量預(yù)測(cè)。另外，該項(xiàng)工作比較了利用傳統(tǒng)模型預(yù)測(cè)交通流量與減去天模式殘差后的流量的性能，發(fā)現(xiàn)后一種情況預(yù)測(cè)效果有著明顯的改善。

文獻(xiàn)[37]提出了一種基于移動(dòng)平均(moving average，MA)，指數(shù)平滑(exponential smoothing，ES)，ARIMA和神經(jīng)網(wǎng)絡(luò)模型的交通流預(yù)測(cè)組合方法。該方法將原始的交通流時(shí)間序列構(gòu)造為以周為周期的時(shí)間序列、以天為周期的時(shí)間序列以及以小時(shí)為周期的時(shí)間序列，然后分別利用MA，ES和ARIMA來(lái)對(duì)3個(gè)相關(guān)時(shí)間序列進(jìn)行預(yù)測(cè)。最后將預(yù)測(cè)出來(lái)的序列輸入神經(jīng)網(wǎng)絡(luò)中得出最后的預(yù)測(cè)效果。該項(xiàng)工作證明了組合模型在提高交通流預(yù)測(cè)方面可以帶來(lái)實(shí)質(zhì)性的好處，同時(shí)多模式的預(yù)測(cè)方式提高了預(yù)測(cè)的準(zhǔn)確度。

文獻(xiàn)[34]提出一個(gè)基于深度學(xué)習(xí)的端到端結(jié)構(gòu)的模型來(lái)預(yù)測(cè)城市區(qū)域中進(jìn)客流和出客流。具體來(lái)說(shuō)，該方法利用殘差神經(jīng)網(wǎng)絡(luò)來(lái)建模人流的時(shí)間接近度、周期性和趨勢(shì)特征。對(duì)于每個(gè)屬性，他們都設(shè)計(jì)了一個(gè)殘差卷積單元分支，每個(gè)單元都模擬人群流量的空間屬性。該方法基于數(shù)據(jù)動(dòng)態(tài)聚合了3個(gè)殘差神經(jīng)網(wǎng)絡(luò)的輸出并給不同分支和區(qū)域分配了不同的權(quán)重。同時(shí)，該方法還加入額外的影響因子，如天氣和星期的影響，來(lái)進(jìn)一步預(yù)測(cè)最終的人流量以提高算法的魯棒性和準(zhǔn)確度。

表1總結(jié)了已有工作考慮的因素。

表1 客流預(yù)測(cè)的相關(guān)工作Tabl.1 Related work on traffic prediction

3.3 筆者的工作

對(duì)于復(fù)雜的交通網(wǎng)絡(luò)產(chǎn)生的交通流預(yù)測(cè)問(wèn)題，只依靠交通流時(shí)間序列的特征已經(jīng)不能滿(mǎn)足現(xiàn)在的預(yù)測(cè)精度需求。大多數(shù)研究者會(huì)偏向提取交通流數(shù)據(jù)的多個(gè)特征并加入其他相關(guān)信息以提高預(yù)測(cè)的精度。當(dāng)加入越多信息時(shí)，精度可以相應(yīng)得到提高，但是訓(xùn)練的復(fù)雜度也會(huì)相應(yīng)變大，需要大量的計(jì)算時(shí)間去完成一次預(yù)測(cè)。這無(wú)法滿(mǎn)足實(shí)際的實(shí)時(shí)預(yù)測(cè)需求。所以，研究者都嘗試尋求一種均衡時(shí)間復(fù)雜度和預(yù)測(cè)精度的方法。另一方面，現(xiàn)在的研究很多都是基于單個(gè)站點(diǎn)或者小塊路段，對(duì)整個(gè)交通路網(wǎng)的交通流的精準(zhǔn)預(yù)測(cè)還比較困難。因此，能在解決復(fù)雜度的情況下，完成整個(gè)路網(wǎng)的交通流實(shí)時(shí)預(yù)測(cè)，將是交通流預(yù)測(cè)研究的一個(gè)重要進(jìn)展。

筆者在這些方面也做了相應(yīng)的研究。區(qū)別于以往的向量形式和矩陣形式交通流預(yù)測(cè)算法，設(shè)計(jì)了一個(gè)新型的交通流預(yù)測(cè)算法，能充分利用交通流量的多模特性來(lái)提高預(yù)測(cè)準(zhǔn)確度。具體來(lái)講，針對(duì)復(fù)雜的交通流數(shù)據(jù)，構(gòu)建了一個(gè)不同于以往向量流或矩陣流形式的數(shù)據(jù)模型(張量模型)，能夠有效表征交通流數(shù)據(jù)的多模特性，充分利用數(shù)據(jù)中所包含的空間信息、周期信息以及時(shí)間變量信息。利用張量分解技術(shù)挖掘交通流張量的多模特性，以證明張量模型的有效性和可靠性，為進(jìn)一步預(yù)測(cè)提供理論分析。對(duì)于交通流量預(yù)測(cè)問(wèn)題，筆者將其視作張量填充，即利用張量中已知數(shù)據(jù)對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)。我們的模型主要是針對(duì)大客流預(yù)測(cè)，因此，本文中將其稱(chēng)為大客流張量模型。

我們?cè)谏虾５罔F數(shù)據(jù)上評(píng)估了大客流張量模型，并與已有的數(shù)學(xué)模型(ARIMA，SARIMA)和機(jī)器學(xué)習(xí)模型(SVR，NN，LSTM)進(jìn)行了比較。

選用平均絕對(duì)百分比誤差(mean absolute percentage error，MAPE)和平均絕對(duì)誤差(mean absolute error，MAE)作為評(píng)估指標(biāo)。實(shí)驗(yàn)結(jié)果如表2所示。表2中第2列是正則化的MAE，可以看到大客流張量模型比已有性能最好的SRIMA模型仍然低34%。對(duì)于MAPE，張量填充模型也提高了1.04%～27.78%。

表2 預(yù)測(cè)性能對(duì)比Tab.2 Forecasting performance

4 城市公交系統(tǒng)突發(fā)客流早期預(yù)警

城市地鐵中的突發(fā)客流是指短時(shí)間內(nèi)聚集大量的乘客，這會(huì)給交通系統(tǒng)帶來(lái)不良影響并誘發(fā)踩踏事件發(fā)生。對(duì)突發(fā)客流早期預(yù)警可以使城市管理部門(mén)提前做出應(yīng)急準(zhǔn)備，防止緊急事件發(fā)生。目前城市地鐵管理系統(tǒng)仍然缺乏有效的預(yù)警工具[39]。

針對(duì)交通(乘客)流量已有很多相關(guān)研究，然而更多的研究專(zhuān)注于交通流量短時(shí)預(yù)測(cè)和交通流量監(jiān)控。交通流量短時(shí)預(yù)測(cè)方法對(duì)于常規(guī)交通(乘客)流量有較好的性能，然而對(duì)于突發(fā)交通(乘客)流量預(yù)測(cè)精度較差。交通流量監(jiān)控方法僅對(duì)當(dāng)下的情景做出感知，并假設(shè)當(dāng)前的情況能夠?qū)Χ唐诘膶?lái)情況提供最好的估計(jì)，然而這一假設(shè)不適合突發(fā)交通流量。已有研究缺乏針對(duì)突發(fā)交通流量的早期預(yù)警。

以上研究方法已在許多研究問(wèn)題中應(yīng)用，例如交通系統(tǒng)客流量、高速公路車(chē)流量、區(qū)域人群流量。相關(guān)研究運(yùn)用了多種數(shù)據(jù)源，例如公交卡交易數(shù)據(jù)、GPS軌跡數(shù)據(jù)、視頻監(jiān)控?cái)?shù)據(jù)等。

下面將具體分析現(xiàn)有交通流預(yù)測(cè)方法。

4.1 短時(shí)預(yù)測(cè)方法

短時(shí)預(yù)測(cè)多使用數(shù)學(xué)模型挖掘模式，再根據(jù)捕捉的模式預(yù)測(cè)未來(lái)的交通流量。Wei等[40]使用一個(gè)包括經(jīng)驗(yàn)?zāi)B(tài)分布和反向傳播神經(jīng)網(wǎng)絡(luò)的混合模型預(yù)測(cè)地鐵系統(tǒng)中的乘客流量。Li 等[41]提出了多尺度徑向基 (multi scale radial basis function, MSRBF)網(wǎng)絡(luò)預(yù)測(cè)特殊事件場(chǎng)景下的客流量。Sun等[42]提出了混合模型(小波支持向量機(jī))，把客流量分解成不同頻率的流量序列,并針對(duì)各自特征分別建模預(yù)測(cè)地鐵系統(tǒng)中的客流量。

針對(duì)城市中的區(qū)域人流量，也有相關(guān)的短時(shí)預(yù)測(cè)研究，例如文獻(xiàn)[34，43-44]使用GPS軌跡數(shù)據(jù)利用深度殘差網(wǎng)絡(luò)等模型建模預(yù)測(cè)城市每個(gè)區(qū)域的進(jìn)出人流量。Zhang等[45]使用移動(dòng)終端(手機(jī))采集數(shù)據(jù)，提出了一個(gè)混合模型預(yù)測(cè)城市區(qū)域的人群流量。

對(duì)于高速公路車(chē)流量的短時(shí)預(yù)測(cè)，也有一些相關(guān)研究。Abadi等[46]利用交通數(shù)據(jù)提出了一個(gè)基于自回歸模型算法預(yù)測(cè)交通網(wǎng)絡(luò)中所有路段的車(chē)流量。Lv等[47]提出了一個(gè)基于深度學(xué)習(xí)的車(chē)流量短時(shí)預(yù)測(cè)方法，該方法同時(shí)考慮了時(shí)間和空間的相關(guān)性。 Hou等[48]則關(guān)注一城市工作區(qū)的車(chē)流量預(yù)測(cè)。

4.2 監(jiān)控方法

很多研究專(zhuān)注于對(duì)交通系統(tǒng)客流量、區(qū)域人群客流量、高速公路車(chē)流量的監(jiān)控。

Liu等[49]使用視屏監(jiān)控?cái)?shù)據(jù)，利用計(jì)算機(jī)視覺(jué)、數(shù)字圖像處理等技術(shù)來(lái)監(jiān)控客流量，以防止踩踏事件的發(fā)生。同時(shí)利用GIS(geographic information systems)技術(shù)提出了一個(gè)客流監(jiān)控算法，該算法可以動(dòng)態(tài)地展示城市交通網(wǎng)絡(luò)中實(shí)時(shí)的客流量分布，并刻畫(huà)其變化趨勢(shì)。并分析不同指標(biāo)的適用條件和使用范圍,最后提出客流預(yù)警閾值方面的參考建議。

Liang等[50]對(duì)上海的一條老街的人群流量進(jìn)行監(jiān)控，并通過(guò)圖像處理方法使用視頻監(jiān)控?cái)?shù)據(jù)計(jì)算不同時(shí)間段的人群客流量。Xu等[51]提出了一個(gè)考慮多因素的區(qū)域人群流量監(jiān)控方法，考慮區(qū)域人群密度、區(qū)域人群更迭速率、區(qū)域進(jìn)出人流比、平均速度等多因素對(duì)大型商業(yè)區(qū)的人群流量進(jìn)行監(jiān)控。

Quinn等[52]使用視頻監(jiān)控?cái)?shù)據(jù)對(duì)道路的車(chē)流量數(shù)據(jù)進(jìn)行監(jiān)控,提出一種基于概率推理的方法來(lái)使交通監(jiān)控的標(biāo)準(zhǔn)方法變得更加健壯。此外該方法可以不需要進(jìn)行車(chē)輛分割過(guò)程，將交通道路視為流體，并估計(jì)流量，而不是跟蹤單個(gè)車(chē)輛。該方法即使在有噪音的情況下也可以準(zhǔn)確地監(jiān)控交通流量。

在以上的監(jiān)控方法中，當(dāng)流量超過(guò)了閾值系統(tǒng)會(huì)發(fā)出報(bào)警。但是這些方法可以做到實(shí)時(shí)監(jiān)控卻難以提前發(fā)出報(bào)警，而突發(fā)交通流量多是很短時(shí)間之內(nèi)發(fā)生的，因此，監(jiān)控方法難以給城市管理人員足夠的準(zhǔn)備時(shí)間對(duì)突發(fā)交通流量采取措施。

4.3 早期預(yù)警方法

有關(guān)交通流量早期預(yù)警的研究較為有限。Zhou 等[53]設(shè)計(jì)了一個(gè)新穎的方法可以提前預(yù)警某區(qū)域的大量人群。他們利用百度地圖中查詢(xún)數(shù)量與定位用戶(hù)數(shù)量之間的強(qiáng)相關(guān)模式，發(fā)現(xiàn)當(dāng)某地址有大量的查詢(xún)數(shù)據(jù)時(shí)，一段時(shí)間后往往會(huì)有大量人群聚集，并基于此提出區(qū)域人群早期預(yù)警模型。但他們的工作集中在固定區(qū)域的人流預(yù)測(cè)，而不適合軌道交通系統(tǒng)中的客流。

表3是對(duì)以上工作的總結(jié)。

4.4 筆者的工作

我們定義了交通系統(tǒng)突發(fā)客流早期預(yù)警問(wèn)題，針對(duì)突發(fā)客流，希望能夠?qū)崿F(xiàn)以下2個(gè)目標(biāo)。

1)提前告警。提前足夠長(zhǎng)的時(shí)間發(fā)出公共交通系統(tǒng)中突發(fā)客流即將到來(lái)的告警，使城市管理相關(guān)人員有足夠長(zhǎng)的時(shí)間采取措施做出防范。

2)定量預(yù)估。在發(fā)出預(yù)警時(shí)或其后的一段時(shí)間內(nèi)，作出對(duì)突發(fā)客流峰值時(shí)間、峰值數(shù)量的預(yù)估。

然后我們對(duì)公交卡刷卡數(shù)據(jù)進(jìn)行了初步探索，不僅對(duì)客流量(進(jìn)客流)進(jìn)行了分析，也同時(shí)也考慮了出客流，進(jìn)出信息可以通過(guò)交易金額來(lái)推斷。圖3展示了“上海體育場(chǎng)”地鐵站某一天的進(jìn)出客流量，淺色線(xiàn)為出客，深色線(xiàn)為進(jìn)客流。如圖2所示，我們得知，有一場(chǎng)足球賽于當(dāng)天17:00—18:50在該地鐵站附近舉辦，這是導(dǎo)致突發(fā)客流的原因。

表3 交通早期預(yù)警相關(guān)研究Tab.3 Related work about early warning on traffic

圖2 上海體育場(chǎng)地鐵站的進(jìn)出客流量Fig.2 Passengers of Shanghai stadium

可以看到，在當(dāng)有大型活動(dòng)舉辦時(shí)，離舉辦場(chǎng)館較近的地鐵站的進(jìn)出客流量在活動(dòng)前后有2個(gè)“尖峰”—異常出客流量和突發(fā)進(jìn)客流量。通常情況下，前者持續(xù)時(shí)間較長(zhǎng)，峰值通常較小，對(duì)交通系統(tǒng)幾乎沒(méi)有負(fù)面影響。相比之下，后者在較短的時(shí)間內(nèi)有非常高的峰值，并可能對(duì)公共安全造成危害。此外，兩者之前通常有2小時(shí)以上的延遲。

由此可見(jiàn)，如果僅靠歷史客流信息結(jié)合數(shù)學(xué)模型很難提前預(yù)知突發(fā)客流(深色線(xiàn))。但是，考慮了出客流信息以及人群行為之后，可以較明顯地看到突發(fā)客流的模式，并基于此提出突發(fā)客流早期預(yù)警框架。

筆者的框架考慮了宏觀乘客流量和微觀個(gè)人出行行為。它由2個(gè)模型組成：異常流量檢測(cè)告警模型和突發(fā)流量峰值估計(jì)模型。異常流量檢測(cè)告警的目標(biāo)是通過(guò)彈性滑動(dòng)窗口在線(xiàn)檢測(cè)異常出客流量，基于移位小波樹(shù)(shifted wavelet tree, SWT)的時(shí)間序列模型[56]。當(dāng)檢測(cè)到異常出客流量時(shí)，進(jìn)行告警，提醒未來(lái)一段時(shí)間可能會(huì)有大量突發(fā)的客流。同時(shí)，突發(fā)流量峰值估計(jì)模型開(kāi)始計(jì)算即將到來(lái)的突發(fā)客流的峰值時(shí)間和峰值數(shù)量。突發(fā)流量峰值估計(jì)模型使用多元回歸模型計(jì)算峰值時(shí)間，并結(jié)合流量預(yù)測(cè)模型和物理模型所組成的混合模型來(lái)估計(jì)峰值量。

筆者使用上海市2015年4月的公卡交易數(shù)據(jù)評(píng)估筆者的框架和模型。正則化的實(shí)驗(yàn)結(jié)果如表4所示。使用了3個(gè)典型地鐵站來(lái)對(duì)筆者的模型進(jìn)行評(píng)估，并與其他代表性模型如SARIMA，SVR，NN進(jìn)行比較，選用RMSE(root mean square error)誤差作為評(píng)估指標(biāo)。從表4可見(jiàn)，其他模型峰值RMSE誤差是筆者模型的1.28～14.58倍。

表4 峰值流量預(yù)估的RMSETab.4 Normalized RMSE of peak volume prediction

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

筆者調(diào)研了面向公共安全的時(shí)空數(shù)據(jù)挖掘的研究進(jìn)展，并針對(duì)2類(lèi)數(shù)據(jù)集，分別介紹了基于個(gè)體移動(dòng)模序異常的大規(guī)模活動(dòng)識(shí)別、城市有軌交通網(wǎng)絡(luò)短時(shí)客流預(yù)測(cè)以及城市公交系統(tǒng)突發(fā)客流早期預(yù)警，同時(shí)介紹了筆者的最新研究進(jìn)展。公共安全管理對(duì)城市的發(fā)展和市民生活無(wú)比重要，利用時(shí)空數(shù)據(jù)可以真切地感知并預(yù)警潛在的危險(xiǎn)事件，因此該研究具有重要的現(xiàn)實(shí)意義。

[1] 趙汗青.中國(guó)現(xiàn)代城市公共安全管理研究[D].長(zhǎng)春：東北師范大學(xué),2012.

ZHAO Hanqing. Study of China’s Modern City Public Safety Management[D].Changchun: Northeast Normal University, 2012

[2] BARABASI A L. The origin of bursts and heavy tails in human dynamics[J]. Nature, 2005, 435(7039): 207-211.

[3] HADDADI H, HUI P, BROWN I. MobiAd: private and scalable mobile advertising[C]//Proceedings of the fifth ACM international workshop on Mobility in the evolving internet architecture. New York, NY, USA: ACM, 2010: 33-38.

[4] GONZALEZ M C, HIDALGO C A, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782.

[5] SCHNEIDER C M, BELIK V, COURONNé T, et al. Unravelling daily human mobility motifs[J]. Journal of The Royal Society Interface, 2013, 10(84):246-253.

[6] GONZALEZ M C, HIDALGO C A, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-782.

[7] YANG S, YANG X, ZHANG C, et al. Using social network theory for modeling human mobility[J]. IEEE network, 2010, 24(5): 6-13.

[8] 盧揚(yáng).人類(lèi)移動(dòng)行為模式研究[D].成都：電子科技大學(xué),2015.

LU Yang. Study of Human Mobility Pattern[D]. Chengdu: University of Electronic Science and Technology of China, 2015.

[9] ZHONG Y, YUAN N J, ZHONG W, et al. You are where you go: Inferring demographic attributes from location check-ins[C]//Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. New York, NY, USA: ACM, 2015: 295-304.

[10] 戴蓉蓉,朱海紅,李霖.基于ARIMA模型的市內(nèi)人群移動(dòng)預(yù)測(cè)[J].測(cè)繪工程,2016,25(2):38-41.

DAI Rongrong, ZHU Haihong, LI Lin. Intra-urban human mobility prediction based on ARIMA model[J]. Engineering of Surveying and Mapping, 2016, 25(2): 38-41.

[11] 楊喜平,方志祥,趙志遠(yuǎn),等.城市人群聚集消散時(shí)空模式探索分析——以深圳市為例[J].地球信息科學(xué)學(xué)報(bào),2016,18(4):486-492.

YANG X, FANG Z, ZHAO Z, et al. Exploring Urban Human Spatio-temporal Convergence-Dispersion Patterns: A Case Study of Shenzhen City[J]. Journal of Geo-Information Science, 2016, 18(4): 486-492.

[12] ADAM A, RIVLIN E, SHIMSHONI I, et al. Robust real-time unusual event detection using multiple fixed-location monitors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(3): 555-560.

[13] 郭婷.大規(guī)模群體人數(shù)檢測(cè)算法研究[D].西安：西安科技大學(xué),2014.

GUO T. Research on Algorithm of Counting High-Density Crowd[D]. Xi’an: Xi’an University of Science and Technology, 2014.

[14] HAGBERG A, SWART P, CHULT D S. Exploring Network Structure, Dynamics, and Function Using NetworkX[C]// Proceedings of the 7th Python in Science conference (SciPy 2008).[S.l.]: Conference Publication, 2008: 11-15.

[15] ZHENG Yu, YUAN N J,ZHENG K, et al. On discovery of gathering patterns from trajectories[C]// Proceeding ICDE ’13 Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013) Washington, DC, USA: IEEE Computer Society, 2013: 242-253.

[16] TRAAG V A, BROWET A, CALABRESE F, et al. Social event detection in massive mobile phone data using probabilistic location inference[C]//Privacy, security, risk and trust (PASSAT) and 2011 IEEE Third International conference on social computing (SocialCom), 2011 IEEE Third International Conference on. Boston, MA, USA: IEEE, 2011: 625-628.

[17] DONG Y, PINELLI F, GKOUFAS Y, et al. Inferring unusual crowd events from mobile phone call detail records[C]// Proceeding ECMLPKDD’15 Proceedings of the 2015th European Conference on Machine Learning and Knowledge Discovery in Databases. Switzerland: Springer, 2015: 474-492.

[18] WITAYANGKURN A, HORANONT T, SEKIMOTO Y, et al. Anomalous event detection on large-scale gps data from mobile phones using hidden markov model and cloud platform[C]//Proceedings of the 2013 ACM conference on Pervasive and ubiquitous computing adjunct publication.New York, NY, USA: ACM, 2013: 1219-1228.

[19] CALABRESE F, PEREIRA F C, DI LORENZO G, et al. The geography of taste: analyzing cell-phone mobility and social events[C]//International Conference on Pervasive Computing. Berlin Heidelberg: Springer, 2010: 22-37.

[20] AGRAWAL R, FALOUTSOS C, SWAMI A N. Efficient similarity search in sequence databases[C]//Proceeding FODO ’93 Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms. London, UK: Springer-Verlag, 1993: 69-84.

[21] CHEN Lei, ?ZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD international conference on Management of data.New York, NY, USA: ACM, 2005: 491-502.

[22] VLACHOS M, KOLLIOS G, GUNOPULOS D. Discovering similar multidimensional trajectories[C]//Data Engineering, 2002. Proceedings. 18th International Conference on. San Jose, CA, USA, USA: IEEE, 2002: 673-684.

[23] CHEN Lei, RAYMOND Ng. On the marriage of Lp-norms and edit distance[C]// Proceeding VLDB ’04 Proceedings of the Thirtieth international conference on Very large data bases. Toronto, Canada: VLDB Endowment 2004:792-803.

[24] MA C, LU H, SHOU L, et al. KSQ: Top-k similarity query on uncertain trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(9): 2049-2062.

[25] LI Quannan, ZHRNG Yu, XIE Xing, et al. Mining user similarity based on location history[C]//Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems. New York, NY, USA: ACM, 2008.

[26] JEUNG H, YIU M L, JENSEN C S. Trajectory pattern mining[M]//Computing with spatial trajectories. New York: Springer, 2011: 143-177.

[27] LEE, Jae-Gil, HAN Jiawei, WHANG Kyu-Young. Trajectory clustering: a partition-and-group framework[C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data. New York, NY, USA: ACM, 2007:594-604.

[28] BOLSHINSKY E, FREIDMAN R. Traffic flow forecast survey[R]. Hefa, Israel: Technion-Israel Institute of Technology. Technical Report, 2012.

[29] 伍元?jiǎng)P.基于動(dòng)態(tài)張量填充的短時(shí)交通流預(yù)測(cè)研究[D].北京：北京理工大學(xué),2015.

WU Yuankai. Short-tem Traffic Prediction based on Dynamic Tensor Completion[D].Beijing: Beijing Institute of Technology, 2015.

[30] van der VOORT M, DOUGHERTY M, WATSON S. Combining Kohonen maps with ARIMA time series models to forecast traffic flow[J]. Transportation Research Part C: Emerging Technologies, 1996, 4(5): 307-318

[31] CASTRO-NETO M, JEONG Y S, JEONG M K, et al. Online-SVR for short-term traffic flow prediction under typical and atypical traffic conditions[J]. Expert systems with applications, 2009, 36(3): 6164-6173.

[32] HAWORTH J, SHAWE-TAYLOR J, CHENG T, et al. Local online kernel ridge regression for forecasting of urban travel times[J]. Transportation Research Part C: Emerging Technologies, 2014(46): 151-178.

[33] LEDOUX C. An urban traffic flow model integrating neural networks[J]. Transportation Research Part C: Emerging Technologies, 1997, 5(5): 287-300.

[34] ZHANG J, ZHENG Y, QI D. Deep Spatio-Temporal Residual Networks for Citywide Crowd Flows Prediction[C]// Proceeding of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17). arXiv preprint arXiv:1610.00081.[S.l.]：AAAI，2017，2016.

[35] van LINT J W C, HOOGENDOORN S P, van ZUYLEN H J. Accurate freeway travel time prediction with state-space neural networks under missing data[J]. Transportation Research Part C: Emerging Technologies, 2005, 13(5): 347-369.

[36] CHEN C, WANG Y, LI L, et al. The retrieval of intra-day trend and its influence on traffic prediction[J]. Transportation research part C: emerging technologies, 2012(22): 103-118.

[37] TAN M C, WONG S C, XU J M, et al. An aggregation approach to short-term traffic flow prediction[J]. IEEE Transactions on Intelligent Transportation Systems, 2009, 10(1): 60-69.

[38] CHANG S C, KIM R S, KIM S J, et al. Traffic-flow forecasting using a 3-stage model. In Intelligent Vehicles Symposium[C]// Intelligent Vehicles Symposium, 2000. IV 2000. Proceedings of the IEEE, Dearborn, MI, USA:IEEE, 2000:451-456.

[39] YANG J T. Safety risk analysis and countermeasures study on regular mass passenger flow of china’s urban subway[J] Procedia Engineering, 2016(135):175-179.

[40] WEI Y, CHEN M C. Forecasting the short-term metro passenger flow with empirical mode decomposition and neural networks[J]. Trans-portation Research Part C: Emerging Technologies, 2012, 21(1): 148-162.

[41] LI Y, WANG X, SUN S, et al. Forecasting short-term subway passenger flow under special events scenarios using multiscale radial basis function networks[J]. Transportation Research Part C: Emerg- ing Technologies, 2017(77): 306-328.

[42] SUN Y, LENG B, GUAN W.A novel wavelet-svm short-time passenger flow prediction in beijing subway system[J]. Neurocomputing, 2015(166):109-121.

[43] ZHANG J, ZHENG Y, QI D,et al. Dnn-based prediction model for spatio-temporal data[C]// Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY, USA: ACM, 2016:92.

[44] HOANG M X, ZHENG Y, SINGH A K. Fccf: forecasting citywide crowd flows based on big data[C]//Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, NY, USA: ACM, 2016: 6.

[45] ZHANG K, WANG M, WEI B, et al. Identification and prediction of large pedestrian flow in urban areas based on a hybrid detection approach[J]. Sustainability, 2016, 9(1): 36.

[46] ABADI A, RAJABIOUN T, IOANNOU P A. Traffic flow prediction for road transportation networks with limited traffic data[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(2):653-662.

[47] LV Y, DUAN Y, KANG W, et al. Traffic flow prediction with big data: a deep learning approach[C]//IEEE Transactions on Intelligent Transportation Systems, 2015, 16(2): 865-873.

[48] HOU Y, EDARA P, SUN C. Traffic flow forecasting for urban work zones[J].IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4):1761-1770.

[49] LIU S, ZHU Z, CHENG Q, et al. Analysis and design of public places crowd stampede early-warning simulating system[C]//Industrial Informatics-Computing Technology, Intelligent Technology, Industrial Information Integration (ICIICII), 2016 International Conference on. Wuhan, China: IEEE, 2016: 210-213.

[50] LIANG J, YANG J T, WU P Y. A graded pedestrian flow early warning for an ancient street[C]//Procedia Engineering, 2016(135): 118-122.

[51] XU X, MA Y, LI T, et al. Risk early-warning study of passenger flow in business district[C]//Emergency Management and Management Sciences (ICEMMS), 2010 IEEE International Conference on. Beijing, China: IEEE, 2010: 310-313.

[52] QUINN J A, NAKIBUULE R. Traffic flow monitoring in crowded cities[C]//2010 AAAI Spring Symposium Series, Artificial Intelligence for Development.[S.l.]:AAAI Publications, 2010:73-78.

[53] ZHOU J, PEI H, WU H. Early warning of human crowds based on query data from Baidu map: Analysis based on shanghai stampede[EB/OL].(2016-03-22). https://arxiv.org/abs/1603.06780.

[54] BAI Li, WANG Fuzhang, ZHANG Ming. Urban rail transit network passenger flow monitoring and early warning system based on GIS[J]. Urban Rapid Rail Transit, 2013,26(6):56-59.

[55] GALLO M, SIMONELLI F, de LUCA G, et al. An artificial neural network approach for spatially extending road traffic monitoring measures[C]//Environmental, Energy, and Structural Monitoring Systems (EESMS), 2016 IEEE Workshop on. Bari, Italy: IEEE, 2016:1-5.

[56] ZHU Y, SHASHA D. Efficient elastic burst detection in data streams[C]//Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. New York, NY, USA: ACM, 2003:336-345.

(編輯：魏琴芳)