基于軌跡結(jié)構(gòu)的移動對象熱點區(qū)域發(fā)現(xiàn)

呂紹仟，孟凡榮，袁 冠

(中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

(*通信作者電子郵箱shaoqianlv@cumt.edu.cn)

基于軌跡結(jié)構(gòu)的移動對象熱點區(qū)域發(fā)現(xiàn)

呂紹仟*，孟凡榮，袁 冠

(中國礦業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116)

(*通信作者電子郵箱shaoqianlv@cumt.edu.cn)

針對現(xiàn)有熱點區(qū)域發(fā)現(xiàn)算法難以從軌跡數(shù)據(jù)集中準(zhǔn)確識別活動熱點的問題，提出了基于軌跡結(jié)構(gòu)的熱點區(qū)域發(fā)現(xiàn)框架(TS_HS)。TS_HS由候選區(qū)域發(fā)現(xiàn)(CHSD)算法和熱點區(qū)域過濾(HSF)算法組成。首先，使用基于網(wǎng)格相對密度的CHSD識別空間上的軌跡密集區(qū)域作為候選熱點區(qū)域；然后，利用HSF根據(jù)候選區(qū)域中軌跡的活動特征和時間變化特征，篩選出移動對象活動頻繁的熱點區(qū)域。在Geolife數(shù)據(jù)集上進(jìn)行的實驗表明，與基于全局密度的熱門區(qū)域發(fā)現(xiàn)算法(GD_HR)以及移動軌跡時空熱點區(qū)域發(fā)現(xiàn)算法(SDHSRD)相比，TS_HS能更有效地解決多密度熱點區(qū)域的識別問題。實驗結(jié)果表明，TS_HS能夠根據(jù)軌跡的活動特征準(zhǔn)確發(fā)現(xiàn)移動對象的活動熱點區(qū)域。

移動對象；軌跡結(jié)構(gòu)；熱點區(qū)域；軌跡數(shù)據(jù)；數(shù)據(jù)挖掘

0 引言

近年來，隨著GPS(Global Positioning System)設(shè)備、衛(wèi)星和無線傳感網(wǎng)絡(luò)[1-3]等定位技術(shù)的快速發(fā)展，以及信號處理[4-6]等相關(guān)研究的不斷推進(jìn)，使得全球范圍內(nèi)的各種移動對象都可以得到有效跟蹤，由此越來越多的移動對象軌跡數(shù)據(jù)被收集并存儲在數(shù)據(jù)庫中。這些軌跡數(shù)據(jù)蘊含了大量有價值的信息，迫切需要深入、有效地分析。這些分析結(jié)果在諸如導(dǎo)航、基于位置社交服務(wù)、位置相關(guān)的廣告以及智能交通等領(lǐng)域有著廣泛的應(yīng)用。

移動對象的原始軌跡數(shù)據(jù)通常是由〈Location,t〉形式的采樣點組成的序列，其中Location是一個2維或3維的點，表示移動對象在t時刻的位置。這些采樣點是定位設(shè)備以相對固定頻率采集得到。軌跡數(shù)據(jù)是移動對象的活動在時空維度上的表達(dá)，因此分析軌跡可以挖掘出移動對象的行為特征。移動對象活動的熱點區(qū)域發(fā)現(xiàn)是軌跡數(shù)據(jù)挖掘的一個重要分支，以熱點區(qū)域為基礎(chǔ)可以將對象的活動軌跡轉(zhuǎn)化為活動區(qū)域序列，從中挖掘出移動對象活動的關(guān)聯(lián)規(guī)則[7]、頻繁模式[8]等有價值信息。此外熱點區(qū)域也能直接被應(yīng)用，例如作為交通的有效參考信息，通過發(fā)布某一時段的熱點區(qū)域可以指導(dǎo)司機(jī)避開這些區(qū)域，從而達(dá)到緩解交通擁塞的目的。

研究人員針對移動對象活動熱點區(qū)域的識別展開了廣泛而深入的研究，提出了基于密度的方法[9]、基于停留點的方法[10-13]以及基于網(wǎng)格的方法[14-15]。盡管現(xiàn)有算法能夠較為有效地發(fā)現(xiàn)活動空間上的重要位置，但是還存在以下問題：

1)無法區(qū)分多密度的活動熱點區(qū)域。熱點區(qū)域是相對的概念，通過全局的密度閾值難以區(qū)分具有不同密度的熱點區(qū)域。例如將城市與周圍的村莊相比，城市是相對密度較高的熱點區(qū)域；而將城市內(nèi)部的中央商務(wù)區(qū)(CentralBusinessDistrict,C)和郊區(qū)的住宅區(qū)相比，CBD是活動熱點區(qū)域而住宅區(qū)不是。現(xiàn)有研究大多采用基于全局密度閾值的聚類算法來檢測熱點區(qū)域，無法解決多密度熱點區(qū)域的識別問題。

2)忽略了區(qū)域熱度隨時間變化的特性。區(qū)域熱度衡量了一段時間內(nèi)移動對象活動的頻繁程度，隨著時間的推移區(qū)域熱度會不斷變化。以滑雪場為例，在每年的冬季通常會有較多的游客來滑雪，所以可以將其視為冬天的一個熱點區(qū)域；但以識別一年里的移動對象熱點區(qū)域為目標(biāo)時，滑雪場就應(yīng)該被排除，因為滑雪場在除了冬天外以外的大部分時間很少有人活動。

3)無法準(zhǔn)確發(fā)現(xiàn)活動密集區(qū)域?，F(xiàn)有研究大多關(guān)注的是發(fā)現(xiàn)空間上的軌跡密集區(qū)域，但軌跡密集區(qū)域并不等同于熱點區(qū)域，軌跡密集是活動密集的必要不充分條件。以地鐵站為例，地鐵站每天都有大量行人經(jīng)過，所以必然是軌跡密集區(qū)域。但將其視為一個活動區(qū)域并不合理，地鐵站是移動對象的必經(jīng)區(qū)域，這里的軌跡通常是速度較快、方向固定的，并不滿足活動軌跡的特征。因此需要對于軌跡密集區(qū)域中的軌跡作進(jìn)一步分析，以確定該區(qū)域是否為活動熱點區(qū)域。

在活動區(qū)域中，移動對象的運動呈現(xiàn)低速、無規(guī)則性，這些活動特點間接地反映在軌跡結(jié)構(gòu)中，軌跡結(jié)構(gòu)的概念由袁冠等[16-17]率先提出。軌跡并不是單純的采樣點序列，軌跡還蘊含了豐富的信息，如速度、形狀、轉(zhuǎn)角、加速度等，這些特征為移動對象的活動分析提供了重要意義。通過對軌跡結(jié)構(gòu)的分析可以發(fā)現(xiàn)更有意義的活動區(qū)域，而不僅僅是軌跡密集區(qū)域。

為了解決多密度軌跡數(shù)據(jù)中的移動對象活動熱點區(qū)域的發(fā)現(xiàn)問題，本文提出了基于軌跡結(jié)構(gòu)的移動對象熱點區(qū)域發(fā)現(xiàn)框架(TrajectoryStructure-basedHotspotsDiscovery，TS_HS)，圖1為TS_HS的框架。TS_HS由候選熱點區(qū)域發(fā)現(xiàn)(CandidateHotspotsDiscovery，CHSD)算法和熱點區(qū)域過濾(HotspotsFilter，HSF)算法組成。首先通過CHSD識別空間上的軌跡密集區(qū)域，這些區(qū)域都是潛在的活動密集區(qū)域，稱之為候選熱點區(qū)域。HSF對候選區(qū)域進(jìn)一步過濾，根據(jù)軌跡的結(jié)構(gòu)特征計算區(qū)域的熱度，從候選區(qū)域集中篩選出活動熱點區(qū)域。

圖1 TS_HS框架

1 相關(guān)研究

目前在軌跡挖掘領(lǐng)域中有較多熱點區(qū)域發(fā)現(xiàn)相關(guān)的工作，根據(jù)軌跡數(shù)據(jù)的時間屬性可以分為同步區(qū)域和異步區(qū)域。同步區(qū)域是指從移動對象同步運動的軌跡上發(fā)現(xiàn)的熱點區(qū)域，其主要任務(wù)是發(fā)現(xiàn)軌跡數(shù)據(jù)集中某一時刻上的移動對象活動密集區(qū)域。Hadjieleftheriou等[18]306-315提出軌跡密度的概念，軌跡密度是單位面積上經(jīng)過的軌跡數(shù)量，并根據(jù)軌跡密度從空間中發(fā)現(xiàn)當(dāng)前熱點區(qū)域。Jensen等[19]提出了二維的密度直方圖以及基于離散余弦變換的壓縮形式，進(jìn)一步提高了查詢的效率。Verhein等[20]進(jìn)一步考慮了密度的變化，拓展定義了大交通區(qū)域和穩(wěn)定區(qū)域。

異步區(qū)域是指從歷史軌跡中識別出的熱點區(qū)域。軌跡數(shù)據(jù)集的特征是不盡相同的，有些數(shù)據(jù)集中軌跡在空間上具有高度的重疊性，但是在時間上卻有較大的偏差，因此難以找到明顯的周期性規(guī)律，同步熱點區(qū)域識別的方法難以應(yīng)用于此類數(shù)據(jù)集中。異步區(qū)域的發(fā)現(xiàn)是目前研究普遍關(guān)注的問題。

利用聚類算法可以有效地從歷史軌跡中自動識別活動熱點區(qū)域。Ashbrook等[21]通過K-means聚類算法挖掘軌跡數(shù)據(jù)中的重要地點，運用K-means算法的難點是需要預(yù)先確定簇的數(shù)量。為了識別單個用戶活動的熱點區(qū)域，Zhou等[12]4-7提出了基于密度和連接的聚類(Density-and-Join-based Cluster，DJ-Cluster)算法，類似于DBSCAN(Density-Based Spatial Clustering of Applications with Noise)，DJ-Cluster算法也是基于鄰近點之間的連通性。Palma等[22]提出了基于速度的時空聚類方法，用于識別單條軌跡上的移動對象停留點，并可以有效解決諸如進(jìn)入建筑導(dǎo)致采樣點丟失等問題。

機(jī)器學(xué)習(xí)和統(tǒng)計學(xué)的方法也已被應(yīng)用于熱點區(qū)域的識別。Khetarpaul等[13]將關(guān)系代數(shù)和統(tǒng)計學(xué)方法相結(jié)合，用于評價位置點的熱門程度；Liao等[23-24]使用機(jī)器學(xué)習(xí)和概率推理的方法從GPS中識別出移動對象的日?；顒?。這類方法在檢測和評價重點位置、尋找熱點區(qū)域等方面有較好性能。

停留點(Stops)是熱點區(qū)域識別領(lǐng)域的一個重要概念，由Alvares等[25]提出。停留點是指移動對象停留時間較長的區(qū)域。在停留點檢測的基礎(chǔ)上，Zheng等[10]791利用層次聚類算法識別空間中的熱門區(qū)域，然后挖掘出移動對象的頻繁活動序列等知識。同樣是基于停留點，Cao等[11]使用兩層圖模型對移動對象和位置之間的關(guān)系建模，從而識別出空間上前K個熱點區(qū)域。這類算法需要耗費較多的時間用于檢測停留點，此外閾值選擇得是否合理也很大程度上影響了算法的效果。

Giannotti等[14]331-339提出了基于網(wǎng)格的熱點區(qū)域發(fā)現(xiàn)算法。先將移動對象的活動空間分割為較小的子區(qū)域，然后每條軌跡投影到子區(qū)域上，最后使用基于網(wǎng)格的聚類算法合并相鄰的密集子區(qū)域來得到最終的熱點區(qū)域。為了解決文獻(xiàn)[14]中存在的大區(qū)域問題，劉奎恩等[15]提出了基于趨勢以及基于差異度的區(qū)域重構(gòu)算法，能夠從熱點區(qū)域中識別出更加具有代表性的區(qū)域。王亮等[27]913將隨機(jī)采樣移動軌跡數(shù)據(jù)在時間軸上進(jìn)行投影轉(zhuǎn)換得到對應(yīng)的時間投影數(shù)據(jù)集，然后采用自底向上和滑動時間窗口相結(jié)合的策略以提取密集時間區(qū)間，最后采用網(wǎng)格劃分技術(shù)識別各個密集時間區(qū)間上的熱點區(qū)域，進(jìn)而以識別的熱點區(qū)域為基礎(chǔ)進(jìn)行移動對象的行為模式發(fā)現(xiàn)。

2 候選熱點區(qū)域發(fā)現(xiàn)

軌跡密集是活動密集的充分不必要條件，HS_TS的基本思想是利用CHSD算法從軌跡數(shù)據(jù)中識別出軌跡密集區(qū)域作為候選區(qū)域，然后根據(jù)軌跡活動特征進(jìn)一步過濾。

2.1 候選熱點區(qū)域發(fā)現(xiàn)算法

CHSD用DBSCAN聚類算法識別空間上軌跡較密集、形狀任意的候選熱點區(qū)域。將DBSCAN算法應(yīng)用于軌跡數(shù)據(jù)需要解決兩個問題：1)時間復(fù)雜度高；2)無法識別多密度簇。

假設(shè)軌跡點的數(shù)量是np，DBSCAN算法的時間復(fù)雜度為O(np2)，軌跡數(shù)據(jù)集中的軌跡點數(shù)量以千萬計，因此DBSCAN難以直接應(yīng)用于軌跡數(shù)據(jù)上。CHSD算法通過網(wǎng)格劃分技術(shù)解決候選區(qū)域識別時間復(fù)雜度較高的問題，定義1給出了網(wǎng)格劃分的形式化定義。

定義1 網(wǎng)格劃分。給定一個d維數(shù)據(jù)集D={D1,D2,…,Dd}，其中屬性Di都是有界的，取值區(qū)間為[li,hi)，i=1,2,…,d，則[l1,h2)×[l1,h2)×…×[ld,hd)就是一個d維數(shù)據(jù)空間S?？梢詫的第i維劃分成Ni個不相交的左閉右開區(qū)間，從而將整個數(shù)據(jù)空間劃分成∏Ni個不相交的超矩形單元，每個單元稱之為一個單元格，記為C。

將移動對象活動的2維空間進(jìn)行網(wǎng)格劃分，每個單元格保存落在其內(nèi)部的軌跡概要信息，然后以單元格為對象進(jìn)行聚類。這么處理的一個優(yōu)點是處理速度快，算法的時間復(fù)雜度是軌跡點個數(shù)的線性函數(shù)，并且有利于算法實現(xiàn)增量處理。

基于密度的聚類算法依賴于一個全局的密度閾值，導(dǎo)致無法有效識別多密度的簇。利用DBSCAN對圖2所示的數(shù)據(jù)集進(jìn)行聚類，無法同時檢測到密集區(qū)域A、B、C1、C2和C3。較低的密度閾值只能檢測到密集區(qū)域A、B、C；較高的密度閾值只能檢測到C1、C2、C3。

圖2 多密度數(shù)據(jù)集聚類示意圖

本文使用基于網(wǎng)格相對密度的聚類算法[26]解決多密度數(shù)據(jù)集上候選熱點區(qū)域識別的問題。定義2～7是基于網(wǎng)格相對密度的聚類算法的相關(guān)定義。

定義2 單元格密度。用經(jīng)過單元格Ci的軌跡數(shù)量來表示Ci的單元格密度，記為d(Ci)。

定義3 鄰接單元格。當(dāng)且僅當(dāng)Ci和Cj有相鄰的邊界或者相鄰點時，Ci和Cj是鄰接單元格。記Ci的所有非空鄰接單元格集合記為Ngs(Ci)。

定義4 單元格相對密度。Ci的單元格密度與鄰接非空單元格的密度均值之比稱之為Ci的單元格相對密度，記為rd(Ci)。

定義5 核心單元格。給定相對密度閾值δrd，一個單元格Ci是核心單元格，當(dāng)且僅當(dāng)滿足不等式(1)：

rd(Ci)≥δrd

(1)

rd(Ci)足夠大意味著Ci密度遠(yuǎn)大于周圍單元格，這些單元格通常是熱點區(qū)域的中心。

定義6 直接密度可達(dá)。如果非空單元格Ci是非空單元格Cj的鄰接單元格，并且滿足不等式(2)：

1/k≤d(Ci)/d(Cj)≤k

(2)

則稱Ci直接密度可達(dá)Cj。k是預(yù)先設(shè)定好的波動系數(shù)。直接密度可達(dá)是對稱的，因此如果Ci直接密度可達(dá)Cj，那么Cj也直接密度可達(dá)Ci。

定義7 密度可達(dá)。如果存在一個單元格序列C1,C2,…,Cn滿足C1=C,Cn=C′，并且Ci直接密度可達(dá)Ci+1，則稱C密度可達(dá)C′。

由核心單元格開始，CHSD算法通過不斷合并鄰接的密度可達(dá)單元格，得到最終的候選熱點區(qū)域集合。

2.2 算法步驟

算法1是CHSD算法的具體步驟。

算法1CHSD(CandidateHotspotsDiscovery)。

輸入：網(wǎng)格G，單元格寬度w，核心單元格閾值δrd，浮動系數(shù)k。 輸出：候選熱點區(qū)域CH。 /*步驟1：網(wǎng)格的劃分與軌跡投影*/

1)

根據(jù)w初始化網(wǎng)格G

2)

根據(jù)定義2將軌跡投影到網(wǎng)格G/*步驟2：單元格相對密度計算與核心單元格發(fā)現(xiàn)*/

3)

初始化核心單元格列表coreCells;

4)

Foreachcellc∈G

5)

rd← CalRelatvieDensity(c);

//定義4

6)

If(rd > δrd)

//定義5

7)

coreCells.add(c); /*步驟3：拓展核心單元格，將與其密度可達(dá)的單元格標(biāo)記上相同的標(biāo)號*/

8)

labelcount← 1;

9)

Foreachcellcc∈coreCells

10)

If(cc.label=0)

11)

candidateHotspot← Extend(g,cc,label,k);//定義7

12)

CH.add(candidateHotspot);

13)

labelcount←labelcount+1;

14)

returnCH;

步驟1 網(wǎng)格劃分與軌跡投影。首先使用參數(shù)w初始化網(wǎng)格G，然后將軌跡投影到經(jīng)過的單元格中。

步驟2 尋找核心單元格。依次計算每個單元格的相對密度，如果單元格的相對密度大于δrd，則將該單元格加入到核心單元格集合coreCells中。

步驟3 拓展核心單元格。迭代處理coreCells中的每個核心單元格，如果單元格的標(biāo)號不為0，說明該單元格已經(jīng)被合并到其他候選區(qū)域中，跳過處理。否則分配一個新的標(biāo)號，使用Extend方法將與之密度相連的所有單元格加入同一個候選區(qū)域中，并將拓展得到的候選區(qū)域加入到結(jié)果集中。

設(shè)軌跡數(shù)量為nt，單元格數(shù)量為nc，CHSD通過遍歷將軌跡投影到網(wǎng)格中的時間復(fù)雜度為O(nt)。以單元格為基本單位進(jìn)行聚類的時間復(fù)雜度為O(nc)。通常nt遠(yuǎn)大于nc，所以CHSD算法的時間復(fù)雜度趨近于O(nt)。

3 熱點區(qū)域過濾

CHSD算法只考慮了軌跡的數(shù)量特征，而沒有考慮到軌跡的結(jié)構(gòu)特征。TS_HS框架在第二階段使用HSF算法對候選熱點區(qū)域作進(jìn)一步篩選，以候選區(qū)域內(nèi)移動對象的軌跡運動特征為依據(jù)，過濾出活動密集的熱點區(qū)域。

3.1 區(qū)域熱度計算

要從軌跡密集的候選區(qū)域中進(jìn)一步篩選出活動密集區(qū)域，首要問題是如何量化表示區(qū)域活動的熱門程度。定義8形式化描述了區(qū)域熱度的計算問題。

定義8 區(qū)域熱度。給定區(qū)域S、時間段Δt和這段時間內(nèi)經(jīng)過區(qū)域S的軌跡集合TD，那么區(qū)域S在Δt時間段內(nèi)的區(qū)域熱度P可以用式(3)表示：

P=F(TD)

(3)

其中F是區(qū)域熱度計算函數(shù)。F函數(shù)的定義決定了區(qū)域熱度能否客觀反映對象的活動特征。例如文獻(xiàn)[18]中使用軌跡密度作為區(qū)域熱度，計算方法如式(4)所示：

Pdensity=|TD|/Area(S)

(4)

其中：Area(S)是區(qū)域S的面積，|·|表示有限集合的計數(shù)操作。如前文所述，軌跡密度不能反映移動對象的活動特點，因此Pdensity難以準(zhǔn)確表達(dá)區(qū)域熱度。移動對象的活動體現(xiàn)在軌跡的結(jié)構(gòu)特征中，本文提取軌跡的停留時間、轉(zhuǎn)角次數(shù)、對象覆蓋率這三個重要特征來概括對象活動的特點。

停留時間 候選區(qū)域內(nèi)移動對象的停留時間越長，發(fā)生活動的可能性就越大，區(qū)域的熱度也就越高。本文以每條軌跡的停留時間avgTime來表示在區(qū)域S內(nèi)移動對象活動的時間特征，記為式(5)：

(5)

其中si表示經(jīng)過S的第i條軌跡在S內(nèi)停留的時間。

轉(zhuǎn)角次數(shù) 熱點區(qū)域內(nèi)移動對象普遍存在運動無規(guī)則的特征，最明顯體現(xiàn)就是轉(zhuǎn)角次數(shù)多。本文以每條軌跡的轉(zhuǎn)角次數(shù)avgCorner來量化區(qū)域內(nèi)的軌跡轉(zhuǎn)角特征。avgCorner的計算方法如式(6)所示：

(6)

其中ci表示經(jīng)過S的第i條軌跡在區(qū)域S內(nèi)的轉(zhuǎn)角次數(shù)。

對象覆蓋率 熱點區(qū)域的一個重要特征是能夠吸引大量不同的對象。本文定義區(qū)域S上經(jīng)過的人數(shù)占總?cè)藬?shù)的比率為區(qū)域S的對象覆蓋率objRatio，記為式(7)。以對象覆蓋率來衡量區(qū)域?qū)λ袑ο蟮奈潭龋瑹狳c區(qū)域通常是對象覆蓋率較高的公共活動區(qū)域。

objRatio=|US|/|UTD|

(7)

UTD表示軌跡數(shù)據(jù)集TD中的用戶集合，US表示區(qū)域S內(nèi)出現(xiàn)的用戶集合。objRatio最大值為1.0，表示所有用戶都路過了區(qū)域S。

通過上述軌跡結(jié)構(gòu)的概括特征，可以有效地度量候選區(qū)域內(nèi)移動對象活動的熱度。式(8)給出了基于軌跡結(jié)構(gòu)特征的區(qū)域熱度(Trajectory Structure based Popularity Measurement, TS_PM)計算方法：

(8)

其中：max(avgTime)和max(avgCorner)表示所有候選區(qū)域中，avgTime和avgCorner的最大值。

3.2 基于時間過濾的熱點區(qū)域

熱點區(qū)域是移動對象長時間頻繁活動的區(qū)域，計算整體時間熱度來判斷熱點區(qū)域的方式忽略了區(qū)域熱度隨時間變化的特征。本文將整體時間劃分成較小的時間段，依次計算每個時間段內(nèi)的區(qū)域熱度，最后以頻繁活動的時長為依據(jù)進(jìn)行熱點區(qū)域的過濾。為了形式化定義熱點區(qū)域，本文首先給出區(qū)域歷史熱度的定義。

定義9 區(qū)域歷史熱度。給定時間段[TS,TE]，將其劃分成等長的n個時間段T1,T2,…,Ti,…,Tn(1≤i≤n)，Pi為區(qū)域在Ti時間段內(nèi)的區(qū)域熱度，那么區(qū)域熱度歷史PH是時間段[TS,TE]內(nèi)的熱度集合，即PH={Pi|1≤i≤n}。

區(qū)域歷史熱度反映了活動熱度變化特性，在區(qū)域歷史熱度的基礎(chǔ)上，本文形式化地定義移動對象活動熱點區(qū)域。

定義10 熱點區(qū)域。給定區(qū)域S的歷史熱度PH={Pi|1≤i≤n}、區(qū)域熱度閾值δP和時長閾值δT，如果不等式(9)成立：

(9)

那么區(qū)域S就是一個熱點區(qū)域。其中time(Pi)表示Pi對應(yīng)的時間段，Sub(PH)是PH的一個子集，滿足式(10)：

Sub(PH)={Pi|Pi∈PH,Pi≥δP}

(10)

熱點區(qū)域是滿足熱度閾值δP的總時長不小于δT的候選區(qū)域，這就保證了識別出的熱點區(qū)域是軌跡密度相對較高、對象活動特征明顯，并且活動時間較長的區(qū)域。

3.3 算法步驟

算法2是熱點區(qū)域過濾算法HSF的具體步驟。

算法2HSF(HotspotsFilter)。

輸入：網(wǎng)格G，候選區(qū)域集合CH，開始時間TS，結(jié)束時間TE，時間間隔tv，區(qū)域熱度閾值δP，時間閾值δT。 輸出：熱點區(qū)域HR。

1)

根據(jù)tv將時間區(qū)間[TS,TE]劃分成等長的時間集合TN

2)

ForeachchinCH

3)

activityTime← 0;

4)

ForeachtninTN

5)

P← CalPopularity(G,tn,ch);

//式(8)

6)

IfP≥δP

7)

activityTime←activityTime+tv;

//定義10

8)

IfactivityTime≥δT

9)

HR.add(ch)

10)

ReturnHR

對于每個候選區(qū)域，HSF調(diào)用CalPopularity方法計算每個時間段內(nèi)的區(qū)域熱度。CalPopularity通過查詢候選區(qū)域內(nèi)每個單元格中的軌跡結(jié)構(gòu)信息來計算區(qū)域熱度值，軌跡的結(jié)構(gòu)信息在算法1的軌跡投影階段已預(yù)先計算并保存到了相關(guān)的單元格中。變量activityTime記錄候選區(qū)域的高活動熱度時長，當(dāng)activityTime滿足時間閾值δT時，將當(dāng)前候選區(qū)域添加到結(jié)果集HR中。

設(shè)單元格數(shù)量為nc，時間被劃分為s段，HSF算法的最壞時間復(fù)雜度為O(nc*s)，也就是每個單元格都在候選區(qū)域中的時候。

4 實驗

本實驗在真實的Geolife數(shù)據(jù)集進(jìn)行，Geolife數(shù)據(jù)集包含了182個移動對象在5年中的活動軌跡，總計17 621條軌跡，總長度超過129×104km。本文對軌跡主要分布的北京地區(qū)(39.8°N～40.05°N，116.30°E～116.50°E)進(jìn)行熱點識別，該區(qū)域內(nèi)軌跡分布密度如圖3所示。

4.1 候選熱點區(qū)域發(fā)現(xiàn)

將移動對象活動區(qū)域劃分為125行100列的網(wǎng)格，劃分之后的單元格尺寸為0.002°×0.002°，然后將軌跡投影到網(wǎng)格中。為了驗證CHSD算法的效果，本文與文獻(xiàn)[14-15]中使用的基于全局密度的熱門區(qū)域發(fā)現(xiàn)(GlobalDensitythresholdbasedHotRegiondiscovery，GD_HR)算法以及文獻(xiàn)[27]中的移動軌跡時空熱點區(qū)域發(fā)現(xiàn)(Spatio-tempaoralHotSoptRegionDiscovering，SDHSRD)算法進(jìn)行對比。他們的研究與本實驗所關(guān)注的軌跡密集區(qū)域具有相似性和可比性，都通過網(wǎng)格劃分減少計算量，并且都通過密度閾值來判斷網(wǎng)格是否為軌跡密集區(qū)域。不同的是GD_HR采用基于全局密度閾值的聚類算法挖掘空間中的密集軌跡區(qū)域，SDHSRD則根據(jù)全局的密度閾值直接過濾出高密度的網(wǎng)格作為熱點區(qū)域。通過GD_HR、SDHSRD和CHSD算法檢測出的候選區(qū)域如圖4所示。其中：圖4(a)、圖4(b)、圖4(c)是使用SDHSRD算法發(fā)現(xiàn)的候選區(qū)域，密度閾值δd的分別取前1.5%、5.0%和8.0%處的密度值；圖4(d)和圖4(e)為GD_HR算法識別出的軌跡密集區(qū)域，密度閾值δd分別為前1.5%和5%處的密度閾值；圖4(f)是CHSD算法的實驗結(jié)果。

圖3 北京地區(qū)軌跡密度分布

圖4 候選熱點區(qū)域

對比圖4(a)、圖4(b)和圖4(c)所示可知，SDHSRD通過調(diào)整密度閾值無法區(qū)分不同密度的密集軌跡區(qū)域，并且會產(chǎn)生很多密度高面積小的小熱點區(qū)域。同樣采用全局密度閾值的GD_HR算法依舊無法解決多密度識別的問題，結(jié)果如圖4(d)和圖4(e)所示。但是通過合并操作可以克服小區(qū)域產(chǎn)生。由于不斷的合并會導(dǎo)致熱點區(qū)域更大，這種大區(qū)域難以應(yīng)用于軌跡模式識別等挖掘任務(wù)。CHSD則能夠很好地區(qū)分開不同密度的區(qū)域，并且不存在大區(qū)域或者小區(qū)域的問題，聚類結(jié)果如圖4(f)所示。

表1是SDHSRD、GD_HR和CHSD聚類結(jié)果的綜合比較，RegionNum表示候選區(qū)域數(shù)量，SmallNum表示小區(qū)域(網(wǎng)格數(shù)小于5的區(qū)域)的數(shù)量，AvgSize為候選區(qū)域的平均大小，Multi-Density表示是否能區(qū)分開多密度候選區(qū)域。

表1 候選區(qū)域效果對比

從表1中可以看出，當(dāng)δd不斷減小時，SDHSRD熱點區(qū)域中的平均區(qū)域大小變化不大，但這是由于大區(qū)域越來越大、小區(qū)域越來越多共同導(dǎo)致的，這兩類區(qū)域的存在對于后續(xù)研究的開展都是極為不利的。小區(qū)域的問題在GD_HR中得到了有效解決，只要平均密度不大于δd，GD_HR就不斷合并鄰接的單元格，密度較高的小區(qū)域因此被合并到鄰近的大區(qū)域中。這也會導(dǎo)致不同密度的簇由于相鄰而被合并，因此GD_HR也無法區(qū)分多密度的候選區(qū)域。CHSD通過計算相對密度避免了不同密度的區(qū)域因為鄰接而被合并，識別出的候選區(qū)域更小、數(shù)量更多，這種緊湊的熱點區(qū)域?qū)π枰_表達(dá)軌跡模式的應(yīng)用至關(guān)重要。

4.2 熱點區(qū)域過濾

4.2.1 區(qū)域熱度計算方法的驗證

以圖4(f)所示的候選熱點區(qū)域為基礎(chǔ)，本文通過實驗進(jìn)一步驗證基于軌跡結(jié)構(gòu)的區(qū)域熱度計算方法TS_PM的有效性。圖5是編號為#56和#76的兩個候選熱點區(qū)域內(nèi)的軌跡統(tǒng)計信息。為了便于展示，每個屬性都作了歸一化處理。

從圖5中可以看出，#56區(qū)域的軌跡密度(trajDensity)雖然較低，但是通過軌跡的結(jié)構(gòu)特征可以認(rèn)為該候選區(qū)域很可能是一個移動對象的活動區(qū)域，無論是移動對象活動的時間、轉(zhuǎn)角次數(shù)還是對象覆蓋率上都更符合活動區(qū)域特點。候選區(qū)域#76雖然軌跡密度較高，但是軌跡的活動特征不明顯，表明#76可能只是交通路口等必經(jīng)地。以軌跡結(jié)構(gòu)為基礎(chǔ)計算得到的區(qū)域熱度很好地反映了兩個候選區(qū)域中移動對象活動的差異。

圖5 候選區(qū)域軌跡結(jié)構(gòu)特征對比

4.2.2 基于時間過濾的有效性驗證

圖5計算的是候選區(qū)域在總體時間內(nèi)的區(qū)域熱度，為了進(jìn)一步驗證對候選區(qū)域進(jìn)行時間過濾的必要性，本文選取兩個整體區(qū)域熱度很接近的候選區(qū)域#73和#19，其整體區(qū)域熱度分別為1.09和1.13。以月為時間間隔分別統(tǒng)計這兩個候選區(qū)域的歷史熱度，結(jié)果如圖6所示。

從圖6可知，雖然兩個熱點區(qū)域的整體區(qū)域熱度十分相近，但是歷史熱度區(qū)別明顯。候選區(qū)域#73在2007年10月到2008年4月以及2010年12月到2011年6月這段時間內(nèi)有明顯的移動對象活動特征，除此之外的其他時間段內(nèi)都沒有頻繁的移動對象活動；而候選區(qū)域#19的移動對象活動較為平穩(wěn)，表明這是一個較長時間內(nèi)的穩(wěn)定活動區(qū)域。

對圖4(f)中的候選區(qū)域進(jìn)行篩選，設(shè)置區(qū)域熱度閾值δP=1.0、時間閾值δT=50%，得到圖7所示的北京熱點區(qū)域分布。

圖6 候選區(qū)域歷史熱度對比

圖7 北京地區(qū)熱點區(qū)域

5 結(jié)語

本文提出了基于軌跡結(jié)構(gòu)的移動對象活動熱點區(qū)域識別框架——TS_HS。TS_HS框架由CHSD算法和HSF算法兩部分組成。CHSD算法首先對空間進(jìn)行網(wǎng)格劃分與軌跡投影，然后利用多密度網(wǎng)格聚類識別活動空間上的軌跡密集區(qū)域作為候選熱點區(qū)域。在熱點區(qū)域過濾階段，提出了基于軌跡結(jié)構(gòu)的區(qū)域熱度計算方法來度量候選區(qū)域中移動對象的活躍程度，并根據(jù)區(qū)域熱度的時間變化特性過濾出最終的熱點區(qū)域。通過在Geolife數(shù)據(jù)集上進(jìn)行的實驗，從多個角度驗證了本文提出的TS_HS框架的有效性。

)

[1]WEIW,QIY.InformationpotentialfieldsnavigationinwirelessAd-Hocsensornetworks[J].Sensors, 2011, 11(5): 4794-4807.

[2]WEIW,XUQ,WANGL,etal.GI/Geom/1queuebasedoncommunicationmodelformeshnetworks[J].InternationalJournalofCommunicationSystems, 2014, 27(11): 3013-3029.

[3]WEIW,YANGXL,SHENPY,etal.Holesdetectioninanisotropicsensornets:topologicalmethods[J].InternationalJournalofDistributedSensorNetworks, 2012, 8(10): 135054.

[4]SONGH,BRANDT-PEARCEM.A2-Ddiscrete-timemodelofphysicalimpairmentsinwavelength-divisionmultiplexingsystems[J].JournalofLightwaveTechnology, 2012, 30(5): 713-726.

[5]SONGH,BRANDT-PEARCEM.Rangeofinfluenceandimpactofphysicalimpairmentsinlong-haulDWDMsystems[J].JournalofLightwaveTechnology, 2013, 31(15): 846-854.

[6]SONGH,BRANDT-PEARCEM.Model-centricnonlinearequalizerforcoherentlong-haulfiber-opticcommunicationsystems[C]//GLOBECOM2013:Proceedingsofthe2013IEEEGlobalCommunicationsConference.Piscataway,NJ:IEEE, 2013: 2394-2399.

[7]JEUNGH,LIUQ,SHENHT,etal.Ahybridpredictionmodelformovingobjects[C]//Proceedingsofthe2008IEEEInternationalConferenceonDataEngineering.Piscataway,NJ:IEEE, 2008: 70-79.

[8]YANGJ,HUM.TrajPattern:miningsequentialpatternsfromimprecisetrajectoriesofmobileobjects[M]//EDBT2006:Proceedingsofthe10thInternationalConferenceonExtendingDatabaseTechnology,LNCS3896.Berlin:Springer, 2006: 664-681.

[9]KAMIN,ENOMOTON,BABAT,etal.AlgorithmfordetectingsignificantlocationsfromrawGPSdata[C]//Proceedingsofthe2010InternationalConferenceonDiscoveryScience.Berlin:Springer, 2010: 221-235.

[10]ZHENGY,ZHANGL,XIEX,etal.MininginterestinglocationsandtravelsequencesfromGPStrajectories[C]//WWW2009:Proceedingsofthe18thInternationalConferenceonWorldWideWeb.NewYork:ACM, 2009: 791-800.

[11]CAOX,CONGG,JENSENCS.MiningsignificantsemanticlocationsfromGPSdata[J].ProceedingsoftheVLDBEndowment, 2010, 3(1): 1009-1020.

[12]ZHOUC,FRANKOWSKID,LUDFORDP,etal.Discoveringpersonallymeaningfulplaces:aninteractiveclusteringapproach[J].ACMTransactionsonInformationSystems, 2007, 25(3): 1-31.

[13]KHETARPAULS,CHAUHANR,GUPTASK,etal.MiningGPSdatatodetermineinterestinglocations[C]//Proceedingsofthe8thInternationalWorkshoponInformationIntegrationontheWeb:inConjunctionwithWWW2011.NewYork:ACM, 2011: 1-6.

[14]GIANNOTTIF,NANNIM,PINELLIF,etal.Trajectorypatternmining[C]//KDD’ 07Proceedingsofthe13thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2007: 330-339.

[15] 劉奎恩,肖俊超,丁治明,等.軌跡數(shù)據(jù)庫中熱門區(qū)域的發(fā)現(xiàn)[J].軟件學(xué)報,2013,24(8):1816-1835.(LIUKE,XIAOJC,DINGZM,etal.Discoveryofhotregionintrajectorydatabases[J].JournalofSoftware, 2013, 24(8): 1816-1835.)

[16] 袁冠,夏士雄,張磊,等.基于結(jié)構(gòu)相似度的軌跡聚類算法[J].通信學(xué)報,2011,32(9):103-110.(YUANG,XIASX,ZHANGL,etal.Trajectoryclusteringalgorithmbasedonstructuralsimilarity[J].JournalonCommunications, 2011, 32(9): 103-110.)

[17] 袁冠.移動對象軌跡數(shù)據(jù)挖掘方法研究[D].徐州:中國礦業(yè)大學(xué),2012:39-59.(YUANG.Researchontheminingmethodsoftrajectorydataformovingobjects[D].Xuzhou:ChinaUniversityofMiningandTechnology, 2012: 39-59.)

[18]HADJIELEFTHERIOUM,KOLLIOSG,GUNOPULOSD,etal.On-linediscoveryofdenseareasinspatio-temporaldatabases[C]//Proceedingsofthe8thInternationalSymposiumonAdvancesinSpatialandTemporalDatabases.Berlin:Springer, 2003: 306-324.

[19]JENSENCS,LIND,OOIBC,etal.Effectivedensityqueriesoncontinuouslymovingobjects[C]//Proceedingsofthe22ndInternationalConferenceonDataEngineering.Piscataway,NJ:IEEE, 2006: 71-71.

[20]VERHEINF,CHAWLAS.Miningspatio-temporalassociationrules,sources,sinks,stationaryregionsandthoroughfaresinobjectmobilitydatabases[C]//Proceedingsofthe2010InternationalConferenceonDatabaseSystemsforAdvancedApplications.Berlin:Springer, 2010: 187-201.

[21]ASHBROOKD,STARNERT.UsingGPStolearnsignificantlocationsandpredictmovementacrossmultipleusers[J].Personal&UbiquitousComputing, 2003, 7(5): 275-286.

[22] PALMA A T, BOGORNY V, KUIJPERS B, et al.A clustering-based approach for discovering interesting places in trajectories [C]// SAC’ 08: Proceedings of the 2008 ACM Symposium on Applied Computing.New York: ACM, 2008: 863-868.

[23] LIAO L, PATTERSON D J, FOX D, et al.Building personal maps from GPS data [J].Annals of the New York Academy of Sciences, 2006, 1093(1): 249-65.

[24] LIAO L, FOX D, KAUTZ H.Extracting places and activities from GPS traces using hierarchical conditional random fields [J].International Journal of Robotics Research, 2007, 26(1): 119-134.

[25] ALVARES L O, BOGORNY V, KUIJPERS B, et al.A model for enriching trajectories with semantic geographical information [C]// GIS’ 07: Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems.New York: ACM, 2007: Article No.22.

[26] CHENG G Q.Clustering algorithm for multi-density based on grid relative density [J].Computer Engineering & Applications, 2009, 45(1): 156-158.

[27] 王亮,胡琨元,庫濤,等.隨機(jī)采樣移動軌跡時空熱點區(qū)域發(fā)現(xiàn)及模式挖掘[J].吉林大學(xué)學(xué)報:工學(xué)版,2015,45(3):913-920.(WANG L, HU K Y, KU T, et al.Discovering spatiotemporal hot spot region and mining patterns from moving trajectory random sampling [J].Journal of Jilin University Engineering and Technology Edition, 2015, 45(3): 913-920.)

This work is supported by the Natural Science Foundation of Jiangsu Province (BK20130208).

LYU Shaoqian, born in 1992, M.S.candidate.His research interests include moving trajectory data mining, machine learning.

MENG Fanrong, born in 1962, Ph.D., professor.Her research interests include database, data mining.

YUAN Guan, born in 1982, Ph.D., associate professor.His research interests include trajectory data mining.

Trajectory structure-based moving object hotspots discovery

LYU Shaoqian*, MENG Fanrong, YUAN Guan

(CollegeofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,XuzhouJiangsu221116,China)

Focused on the issue that the existing algorithms are unable to accurately detect active hotspots from trajectory data, a novel Trajectory Structure-based Hotspots discovery (TS_HS) algorithm was proposed.TS_HS consisted of the following two algorithms: Candidate Hotspots Discovery (CHSD) algorithm and Hotspots Filter (HSF) algorithm.First, trajectory dense regions were detected by the grid based clustering method CHSD as candidate hotspots.Second, the active hotspots region of moving objects were filtered by using HSF algorithm according to moving feature and time-varying characteristic of trajectories.The experiments on the Geolife dataset show that TS_HS is an effective solution for multi-density active hotspot problem, compared with Global Density threshold based Hot Region discovery (GD_HR) and Spatio-temporal Hot Spot Region Discovering (SDHSRD).The simulation results show that the proposed framework can detect active hotspots effectively based on the structure feature and time-varying characteristic of trajectory.

moving object; trajectory structure; hotspot; trajectory data; data mining

2016-08-15;

2016-08-25。 基金項目:江蘇省自然科學(xué)基金資助項目(BK20130208)。

呂紹仟(1992—)，男，江蘇南京人，碩士研究生，主要研究方向：軌跡數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)； 孟凡榮(1962—)，女，遼寧沈陽人，教授，博士，CCF會員，主要研究方向：數(shù)據(jù)庫、數(shù)據(jù)挖掘； 袁冠(1982—)，男，江蘇徐州人，副教授，博士，CCF會員，主要研究方向：軌跡數(shù)據(jù)挖掘。

1001-9081(2017)01-0054-06

10.11772/j.issn.1001-9081.2017.01.0054

TP391.4

A