行為軌跡時空聚類與分析*

秦昆，王玉龍，趙鵬祥，徐雯婷，徐源泉

① 武漢大學(xué) 遙感信息工程學(xué)院，武漢 430079；② 香港理工大學(xué) 土地測量及地理資訊學(xué)系，香港

與日俱增的浮動車數(shù)據(jù)(點)、GNSS(全球?qū)Ш叫l(wèi)星系統(tǒng))軌跡數(shù)據(jù)(線)及相關(guān)街道網(wǎng)絡(luò)數(shù)據(jù)等，構(gòu)成了蘊含著人們行為模式和活動規(guī)律的行為軌跡大數(shù)據(jù)。它們隱藏著具有強時空相關(guān)性的時空聚類模式，實際應(yīng)用時往往需要高時效地挖掘出其中的時空聚類模式，并對其進行高性能求解。行為軌跡數(shù)據(jù)是人類活動的記錄，與人文學(xué)和社會學(xué)問題密切相關(guān)，需要與社會因素進行關(guān)聯(lián)分析。行為軌跡大數(shù)據(jù)的高性能時空聚類與社會分析是地理信息科學(xué)與工程領(lǐng)域迫切需要解決的關(guān)鍵科學(xué)問題。

安裝了車載GNSS定位裝置并行駛在城市主干道上的出租車或公交汽車記錄的浮動車數(shù)據(jù)，是記錄行為軌跡的重要數(shù)據(jù)源。除此以外，還有為特定研究目的而設(shè)計并采集的軌跡數(shù)據(jù)(私家車軌跡數(shù)據(jù)、特定志愿者的軌跡數(shù)據(jù)等)，以及智能手機記載的軌跡數(shù)據(jù)等，可以統(tǒng)稱為行為軌跡數(shù)據(jù)。對浮動車在其行駛過程中定期記錄的車輛位置、方向和速度信息，利用地圖匹配、路徑推測等相關(guān)計算模型和算法進行處理，可以建立浮動車和相關(guān)軌跡的位置數(shù)據(jù)和城市道路在時間和空間上的關(guān)聯(lián)關(guān)系，得到浮動車的車輛行駛速度以及道路的行車旅行時間等交通擁堵信息。行為軌跡數(shù)據(jù)具有時空相關(guān)性，表現(xiàn)為數(shù)據(jù)對象在鄰近的空間位置或相近的時間里具有相似的特征。在對行為軌跡數(shù)據(jù)進行時空相關(guān)性分析的基礎(chǔ)上，利用時空聚類方法可以挖掘出具有強時空相關(guān)性的時空聚類模式，從而進一步分析和挖掘人們的出行行為模式、熱點區(qū)域[1]、異常模式[2]和擁堵模式[3]等規(guī)律性時空知識。

在城市交通規(guī)劃與管理以及城市社會管理過程中，常常需要及時甚至是實時地得到所需要的時空規(guī)律知識。行為軌跡大數(shù)據(jù)的時空聚類挖掘方法必須適應(yīng)快速處理的要求和大數(shù)據(jù)處理的考驗。傳統(tǒng)的時空聚類方法由于受到算法、計算環(huán)境以及時空數(shù)據(jù)本身特征等因素的影響，難以滿足高性能快速處理的要求，難以及時發(fā)揮有效作用。因此，必須對其加以合理取舍和適應(yīng)性改造，增強時空信息存取、處理、分析和挖掘的并行計算和彈性計算能力，使其符合高性能處理要求，以達到充分利用各種計算資源，實現(xiàn)行為軌跡大數(shù)據(jù)時空聚類的高性能求解，從而為城市交通管理和社會管理等提供高時效的規(guī)律性知識。

行為軌跡數(shù)據(jù)是人們行為活動的真實記錄，與社會因素密切相關(guān)。通過行為軌跡大數(shù)據(jù)的分析和挖掘，可以發(fā)現(xiàn)一些隱含的行為模式和活動規(guī)律，從而發(fā)現(xiàn)和理解個體與環(huán)境及其他個體間的交互作用。通過分析行為軌跡數(shù)據(jù)的特性、時空聚類模式等與社會因素的關(guān)系，我們可以解釋行為軌跡大數(shù)據(jù)及其活動模式的社會學(xué)發(fā)生機制，分析其與社會要素之間的關(guān)聯(lián)關(guān)系，從而為城市交通管理及社會管理等提供輔助信息和決策支持，并為地理信息科學(xué)與技術(shù)在人文社會學(xué)領(lǐng)域的應(yīng)用奠定基礎(chǔ)。

1 行為軌跡聚類及高性能求解方法

1.1 行為軌跡時空聚類方法

本文提出了考慮時空相關(guān)性的行為軌跡時空聚類挖掘的思路，技術(shù)路線如圖1所示。

圖1 行為軌跡時空聚類挖掘的技術(shù)路線

技術(shù)路線的具體描述如下：

(1)行為軌跡數(shù)據(jù)預(yù)處理：針對收集整理的行為軌跡數(shù)據(jù)，進行軌跡提取、噪聲去除、軌跡分段等預(yù)處理，使得提取的每個軌跡線段成為相對獨立的數(shù)據(jù)對象。

(2)時空相關(guān)性分析：從空間相關(guān)性、時間相關(guān)性和時空交互性等方面分析行為軌跡數(shù)據(jù)的時空相關(guān)性特征。

(3)屬性特征提?。菏紫确治鰡蝹€行為軌跡對象的屬性特征，提取位置、運行速度、方向等屬性特征，再進一步分析不同軌跡對象的時空相關(guān)性，提取與時空特性關(guān)聯(lián)的屬性特征。

(4)考慮時空相關(guān)性的時空聚類：考慮時空相關(guān)性，提出顧及時空相關(guān)性的時空聚類方法，主要包括時空譜聚類和時空密度聚類。這兩種方法都同時考慮了軌跡數(shù)據(jù)的屬性特征和時空相關(guān)性特征，對這兩種特征分別進行相似性度量和接近性度量。

(5)時空聚類模式挖掘：利用時空聚類方法對行為軌跡數(shù)據(jù)進行時空聚類挖掘，挖掘其時空聚類模式，如客流熱點區(qū)域、出租車接客模式、擁堵模式、出行模式等，并進一步考慮其時間特征，分析其時空演化模式。

1.2 行為軌跡時空聚類的高性能求解方法

行為軌跡時空聚類模型既是計算密集型的，也是數(shù)據(jù)密集型的，因此應(yīng)分別從算法并行和數(shù)據(jù)并行兩方面考慮，按照分布式數(shù)據(jù)庫對數(shù)據(jù)并行的要求，研究行為軌跡的數(shù)據(jù)劃分策略和彈性資源分配方法，按照高性能算法設(shè)計流程和方法，進行時空聚類算法的高性能優(yōu)化求解。

我們團隊提出了一種用于軌跡聚類的時空譜聚類并行化方法[4]。時空譜聚類算法是對傳統(tǒng)譜聚類算法的時空擴展，運用到軌跡數(shù)據(jù)中時，容易遇到運算量過大的問題。一方面，軌跡數(shù)據(jù)本身的數(shù)據(jù)規(guī)模較大，對運算資源的要求較高；另一方面，譜聚類需要進行全局計算，計算復(fù)雜度較高，加入了時間因子后，計算復(fù)雜程度進一步提升，需要對算法進行高性能求解，以減少算法的運算時間。時空譜聚類算法的主要耗時操作為相似度矩陣的構(gòu)建、拉普拉斯矩陣的構(gòu)建以及拉普拉斯矩陣的特征值分解3個階段?？梢葬槍@3個階段分別進行并行化計算。

相似度矩陣是一個n×n的矩陣，使用動態(tài)時間規(guī)整算法(DTW: dynamic time warping)來計算兩點之間距離的復(fù)雜程度較高，因此當(dāng)矩陣較大時，相似度矩陣的構(gòu)建過程會消耗大量的時間。相似度矩陣中每一個元素值的計算過程都是獨立的，每個元素值的計算不依賴其他元素值計算的結(jié)果，因此可以將這些計算過程進行并行化處理。傳統(tǒng)的并行計算方法直接將矩陣連續(xù)幾行的計算任務(wù)放入一個并行計算單元中，但是在對稱矩陣的計算當(dāng)中，由于每一行的計算任務(wù)數(shù)量不一，每一個并行單元的計算時間也不一樣，主線程需要等待所有并行單元計算任務(wù)均執(zhí)行完畢后才繼續(xù)執(zhí)行，而負載不均衡容易導(dǎo)致并行效率下降。因此，利用負載均衡的并行化策略對相似度矩陣的計算過程進行并行化。由于實現(xiàn)了各并行單元的負載均衡，總體的并行效率也會有相應(yīng)的提升。拉普拉斯矩陣由相似度矩陣以及另一個矩陣(由度矩陣計算而來)相減得到，該計算過程實質(zhì)上是兩個矩陣對應(yīng)值相減的過程，每個計算過程之間是獨立的，可以將這些過程放到不同的并行單元中，實現(xiàn)并行化計算。

2 行為軌跡時空聚類的應(yīng)用分析

2.1 熱點區(qū)域提取

城市熱點區(qū)域通常是指商業(yè)較發(fā)達、居民出行次數(shù)多和交通流量較大的區(qū)域，在某種程度上是人們密集出行的體現(xiàn)。出租車軌跡數(shù)據(jù)記錄了車輛的日常運行軌跡，從軌跡數(shù)據(jù)中提取得到的上車點和下車點反映了乘客日常出行的出發(fā)地和目的地。因此，可以利用出租車軌跡進行城市熱點區(qū)域提取，從而發(fā)現(xiàn)城市的活躍區(qū)域。

我們團隊提出了一種利用決策圖和數(shù)據(jù)場提取城市熱點區(qū)域的方法[1]。首先將數(shù)據(jù)場的理論方法用于軌跡數(shù)據(jù)構(gòu)建軌跡數(shù)據(jù)場，每個軌跡點可看作一個帶有質(zhì)量的粒子，其周圍存在一個作用場，位于場中的任何軌跡點都將受到其他軌跡點的聯(lián)合作用；其次，利用勢熵法對參數(shù)σ進行優(yōu)化選取，通過計算勢熵來衡量勢場分布的合理性，最終選取勢熵最小的σ作為優(yōu)化的影響因子；然后，利用決策圖方法來選取聚類中心，聚類中心通常對應(yīng)了勢值的局部極大值點；最后，對去除噪聲點之后的軌跡數(shù)據(jù)進行類的劃分，將該數(shù)據(jù)對象與勢值比其大且距其最近的數(shù)據(jù)對象劃分到同一個類中，最終實現(xiàn)類的劃分。

以武漢市2014年5月1日至10日的出租車軌跡數(shù)據(jù)為數(shù)據(jù)源進行城市熱點提取的實驗，軌跡數(shù)據(jù)的采樣間隔為60 s。將每天的軌跡數(shù)據(jù)按小時劃分為24個時段。分時段提取軌跡數(shù)據(jù)有助于分析各個時段內(nèi)熱點區(qū)域的動態(tài)變化。圖2為工作日和周末的18:00～19:00時段內(nèi)城市熱點區(qū)域分布。結(jié)果表明：某些區(qū)域為持續(xù)性熱點區(qū)域，總體上隨時間變化較小，而另一些熱點區(qū)域只在工作日或周末的個別時間段內(nèi)出現(xiàn)。此外，在工作日，居民的出行多為“居住地—工作地”的通勤模式。在非工作日，多為“居住地—休閑地”或“休閑地間”的出行模式。因此，在非工作日，人們出行以及城市活動通常相對活躍，熱點數(shù)量也較工作日多。

圖2 工作日和周末18:00～19:00時段內(nèi)的熱點區(qū)域分布

2.2 異常軌跡探測

異常軌跡是指軌跡數(shù)據(jù)中不同于大多數(shù)駕駛者常規(guī)選擇路線的軌跡。利用這些異常軌跡可以分析駕駛者或乘客的異常行為，可以為城市交通管理和社會管理等提供決策支持。軌跡聚類是異常軌跡探測的常用手段之一。利用軌跡聚類進行異常軌跡探測涉及兩個關(guān)鍵問題：軌跡的相似性度量和自動確定合適的聚類數(shù)目。

圖3 出發(fā)地和目的地之間的正常軌跡聚類簇和異常軌跡簇

我們團隊提出了一種基于編輯距離和層次聚類的異常軌跡探測方法[2]。利用編輯距離計算軌跡的相似性，利用一種編輯距離操作代價算法，使其適應(yīng)軌跡數(shù)據(jù)連續(xù)記錄的特點。利用基于層次聚類方法將軌跡數(shù)據(jù)聚類成不同的類簇，基于平方和指數(shù)自動確定聚類數(shù)目。

以武漢市2014年5月的出租車軌跡數(shù)據(jù)為數(shù)據(jù)源，選取武昌火車站為出發(fā)地，武漢火車站為目的地，獲取它們之間的所有載客軌跡，利用異常軌跡探測方法進行實驗，提取出發(fā)地和目的地之間的正常軌跡聚類簇和異常軌跡，如圖3所示。

通過對異常軌跡與正常軌跡簇的時間和長度進行比較，并進一步推斷可能的產(chǎn)生原因，異常軌跡可以劃分為4種異常行為模式，具體包括：

(1)行為模式1：長度≤正常軌跡平均長度，時間≤正常軌跡平均時間。根據(jù)該行為模式推斷：該軌跡可能是一個經(jīng)驗豐富的出租車司機憑經(jīng)驗選擇的一條捷徑。利用該方法可以自動發(fā)現(xiàn)一些最優(yōu)路線。

(2)行為模式2：長度≤正常軌跡平均長度，時間＞正常軌跡平均時間。根據(jù)該行為模式推斷：可能遇到了擁堵、交通管制等特殊事件。利用該方法可以自動發(fā)現(xiàn)一些路段中可能存在的特殊事件。

(3)行為模式3：長度＞正常軌跡平均長度，時間≤正常軌跡平均時間。根據(jù)該行為模式推斷：可能是為了趕時間，為了避開擁堵區(qū)域，而選擇了雖然路程較遠，但是可以節(jié)約時間的路線。利用該方法可以自動發(fā)現(xiàn)一些可以節(jié)約時間的路線。

(4)行為模式4：長度＞正常軌跡平均長度，時間＞正常軌跡平均時間。根據(jù)該行為模式推斷：可能是司機故意繞道。利用該方法可以自動發(fā)現(xiàn)一些可能的出租車司機故意繞道行為，從而為出租車管理提供一些參考。

2.3 交通擁堵分析

城市交通擁堵是指一定數(shù)量的車輛持續(xù)性緩慢行駛或停止所形成的聚集現(xiàn)象，可能是由城市車輛過多、道路結(jié)構(gòu)不合理等因素造成。交通擁堵分析有助于了解道路狀況，預(yù)測交通流量趨勢，進而為交通管理、城市管理等提供決策支持。

我們團隊提出了一種基于時間與空間相似性和相異性的時空密度聚類方法[3]，該方法將傳統(tǒng)空間軌跡點聚類擴展為時空軌跡段聚類，進而提取交通擁堵區(qū)域；然后運用 Ripley′s K 函數(shù)描述不同時段下城市擁堵的聚集性程度隨距離的變化關(guān)系；基于軌跡數(shù)據(jù)場理論定量化探索不同時段下交通擁堵的強度分布。最后，通過對城市擁堵區(qū)域的形態(tài)進行時空分析，提出了11種城市擁堵區(qū)域的時空變化模式：新增模式、消散模式、分裂模式、合并模式、分裂合并模式、穩(wěn)定模式、穩(wěn)定移動模式、收縮模式、收縮移動模式、增長模式和增長移動模式等。

出租車軌跡數(shù)據(jù)是研究城市交通擁堵的重要數(shù)據(jù)源之一。以武漢市2014年5月1日、5月11日、5月13日的出租車軌跡數(shù)據(jù)(分別代表節(jié)假日、周末、工作日)為數(shù)據(jù)源進行實驗，獲取3種日期類型對應(yīng)的城市擁堵區(qū)域及其分布模式。以5月13日(工作日)為例，結(jié)果如圖4所示。

圖4 交通擁堵分析(2014年5月13日)實驗結(jié)果圖

通過分析不同時期的城市擁堵分布結(jié)果，得到以下結(jié)論：①存在常發(fā)性擁堵區(qū)域，主要分布于車站、部分商圈與主干道附近，例如漢口火車站、解放大道、珞喻路和王家灣等區(qū)域。②一天內(nèi)擁堵分布具有高低峰，高峰時段的擁堵空間跨度與類簇數(shù)量明顯高于低峰時段。③不同日期的空間分布情況具有不同偏向，工作日多分布于行政工作區(qū)，周末更傾向于休閑娛樂區(qū)，而節(jié)假日明顯聚集于旅游景點區(qū)。④擁堵在不同日期下的時間分布也不盡相同，節(jié)假日與休息日較為相似，擁堵的時間跨度在全天較為均勻，工作日則更為集中地分布在高峰時段，且擁堵強度也更為突出。這表明人們的出行時間在周末和節(jié)假日較為分散和自由，而在工作日的出行時間更為集中。⑤關(guān)于擁堵事件的發(fā)生，呈現(xiàn)顯著的節(jié)假日＞周末＞工作日的特征。⑥緩速軌跡相較于一般軌跡在道路網(wǎng)上更為集中。⑦低峰時段K值高于高峰時段，表明低峰時的擁堵主要集中發(fā)生于少數(shù)特定路段，這使得整體聚集程度較高。

3 總結(jié)與展望

行為軌跡大數(shù)據(jù)的高性能時空聚類與社會分析是地理信息科學(xué)與工程領(lǐng)域迫切需要解決的關(guān)鍵科學(xué)問題。本文對行為軌跡時空聚類及其高性能求解的方法進行了探索，研究了行為軌跡時空聚類在熱點區(qū)域提取、異常軌跡探測、交通擁堵分析等方面的應(yīng)用，還需要將行為軌跡時空聚類結(jié)合社會地理計算、空間交互網(wǎng)絡(luò)分析等進一步深入研究。

[1]ZHAO P X, QIN K, YE X Y, et al. A trajectory clustering approach based on decision graph and data field for detecting hotspots [J].International Journal of Geographical Information Science, 2017,31(6): 1101-1127.

[2]WANG Y L, QIN K, CHEN Y X, et al. Detecting anomalous trajectories and behavior patterns using hierarchical clustering from taxi GPS data [J]. ISPRS International Journal of Geo-Information,2018, 7(1): 1-20.

[3]LIU C K, QIN K , KANG C G. exploring time-dependent traffic congestion patterns from taxi trajectory data [C]//ICSDM 2015 -Proceedings 2015 2nd IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services, October 13, 2015,Fuzhou, China. 2015: 39-44.

[4]GU Y Z, QIN K, CHEN Y X, et al. Parallel spatiotemporal spectral clustering with massive trajectory data [C]//The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Science, Volume XLII-2/W7. ISPRS Geospatial Week 2017, 18-22 September 2017, Wuhan, China. 2017: 1173-1180.