基于停留點(diǎn)密度聚類的軌跡區(qū)域劃分方法

張厚祿， 唐云祁， 王子揚(yáng)

(中國(guó)人民公安大學(xué)偵查學(xué)院， 北京 100038)

0 引言

當(dāng)今世界移動(dòng)互聯(lián)網(wǎng)技術(shù)蓬勃發(fā)展，人們的工作與生活被各類移動(dòng)終端全面交叉覆蓋。如何利用移動(dòng)終端的行為數(shù)據(jù)分析行為人特點(diǎn)是數(shù)據(jù)挖掘的熱門(mén)方向。軌跡數(shù)據(jù)區(qū)域劃分是移動(dòng)終端行為數(shù)據(jù)分析的重要研究分支，也常被廣泛應(yīng)用于公共安全防范及案件偵查。在公安機(jī)關(guān)實(shí)際工作中，通過(guò)分析目標(biāo)人活動(dòng)軌跡中包含的目的性信息，可以尋找犯罪嫌疑人并評(píng)估其可疑程度，以達(dá)到案前預(yù)警、案后偵查追蹤的目的?，F(xiàn)有的各種軌跡挖掘算法已經(jīng)可以做到最大程度涵蓋軌跡包含的所有信息，但是對(duì)于這些信息的應(yīng)用程度有限。如連續(xù)針對(duì)某類地點(diǎn)(加油站、收費(fèi)站、小區(qū))實(shí)施犯罪或預(yù)備犯罪的場(chǎng)景，在沒(méi)有任何既定證據(jù)或者線索的情況下，可通過(guò)對(duì)行人的軌跡信息進(jìn)行目的性分析，進(jìn)而檢測(cè)其異常特性，這對(duì)于已發(fā)案件的偵查或者未發(fā)案事件預(yù)防都有重要的意義。而面對(duì)這一場(chǎng)景，現(xiàn)有算法受制于對(duì)軌跡區(qū)域劃分的精度不足，難以從行為人的軌跡信息中挖掘出有用線索。

一般地，行為人的活動(dòng)軌跡被表示為一條連續(xù)的曲線，這種表示方式較為直觀，但并不直接體現(xiàn)行人的“目的性”。為闡釋行人的日常活動(dòng)中的目的性，各種研究都要首先區(qū)分出不同的軌跡區(qū)域。常見(jiàn)的思路是首先將速度不超過(guò)一定閾值的軌跡點(diǎn)跡定義為停留點(diǎn)，然后對(duì)停留點(diǎn)數(shù)據(jù)聚類以達(dá)到軌跡區(qū)域劃分的目的。該方法首先從行人軌跡數(shù)據(jù)中檢測(cè)得到停留點(diǎn)，然后將整個(gè)行人軌跡線抽象為若干連續(xù)停留點(diǎn)子集，這樣行人的軌跡數(shù)據(jù)就被抽象為從一塊停留區(qū)域至下一塊停留區(qū)域的移動(dòng)過(guò)程。如常見(jiàn)的下班回家，既是一個(gè)停留點(diǎn)(工作地點(diǎn))到另一個(gè)停留點(diǎn)(家)，也是一個(gè)目的地到另一個(gè)目的地。軌跡中的停留點(diǎn)，尤其是連續(xù)停留的點(diǎn)才包含行人的絕大部分活動(dòng)信息。本文舍棄連續(xù)停留點(diǎn)之外的軌跡點(diǎn)，在連續(xù)停留點(diǎn)之間挖掘信息，利用停留點(diǎn)所隱含的信息來(lái)劃分不同的軌跡區(qū)域。

1 相關(guān)工作

針對(duì)軌跡區(qū)域劃分，許多學(xué)者都進(jìn)行了廣泛而深入的研究，從方法思路看，目前主流的方法是使用聚類將同一區(qū)域的軌跡聚集為一類，通過(guò)不同分類區(qū)分軌跡區(qū)域的方法。目前軌跡數(shù)據(jù)聚類策略主要有3個(gè)方向：基于結(jié)構(gòu)或形狀相似度的軌跡聚類方法、基于興趣地點(diǎn)的聚類方法、基于歷史活動(dòng)周期的聚類方法。各方向采用的方法界限并不明顯，且會(huì)互相交叉。

較早的研究中會(huì)使用一些常見(jiàn)的聚類算法如K-MEANS、STING[1]、DBSCAN[2]等，由于密度聚類方法可以發(fā)現(xiàn)任意簇的形狀，近些年的研究重點(diǎn)都在改進(jìn)DBSCAN算法上。為克服DBSCAN難以確定最佳參數(shù)的缺點(diǎn)，Chi[3]為提出HFDST算法，該方法將快速搜索方法應(yīng)用于軌跡聚類，并通過(guò)兩個(gè)參數(shù)Rho、Delta和遞歸函數(shù)來(lái)確定未分類的其他子軌跡，以達(dá)到克服DBSCAN算法參數(shù)敏感的問(wèn)題；Xiaohui[4]提出一種抽樣方法，使用DBSCAN識(shí)別分組以后根據(jù)持續(xù)時(shí)長(zhǎng)和相似性評(píng)分，最后返回得分最高的K組；Peng[5]提出一種基于Spark和SPDBSCAN算法提升聚類效率的方法，該方法改進(jìn)了DBSCAN算法使之能夠并行進(jìn)行，提升了計(jì)算效率；胡圓[6]提出一種基于RDBSCAN算法的異常軌跡檢測(cè)方法，通過(guò)密度區(qū)分然后得到異常程度最高的TOP-N異常軌跡；江玉玲[7]采用Frechet距離作為相似度判別依據(jù)，改進(jìn)了DBSCAN算法以對(duì)船舶軌跡進(jìn)一步聚類；Feng[8]提出了基于密度的車(chē)輛軌跡聚集方法，該方法考慮到路網(wǎng)形狀重建軌跡數(shù)據(jù)，通過(guò)密度聚類結(jié)果分析軌跡特性從而引導(dǎo)駕駛員避免交通堵塞；Chen[9]提出一種線性序列的提取方法，該方法首先分割軌跡數(shù)據(jù)，再計(jì)算相鄰點(diǎn)的角度并使用DBSCAN方法對(duì)其進(jìn)行聚類；袁志琴[10]提出一種面向變尺度密度數(shù)據(jù)的分級(jí)聚類算法，該方法提出的分步驟軌跡聚類思路較為新穎。

2 相關(guān)定義

為更好地描述后續(xù)工作的實(shí)現(xiàn)過(guò)程，當(dāng)描述算法需要調(diào)用概念時(shí)，直接使用以下定義。定義圖示如圖1所示。

圖1 相關(guān)定義圖示

定義1 (軌跡，Trajectory Dataset)設(shè)TD(Trajectory Dataset)為一個(gè)軌跡數(shù)據(jù)集，點(diǎn)P為其中的軌跡點(diǎn)，則軌跡點(diǎn)按時(shí)間先后順序可表示為T(mén)D={P1,P2,P3,…,Pn}。

定義2 (停留點(diǎn)集，Stay-point Dataset)假設(shè)TD中停留點(diǎn)序數(shù)集合為T(mén)DON,TDON={a,b,c,d,…,i}((0

定義3 (子軌跡，Sub-trajectory Dataset)對(duì)于軌跡TD={P1,P2,P3Pn}，假設(shè)存在整數(shù)1≤j

定義4 (連續(xù)停留點(diǎn)子軌跡，Sub-trajectory Dataset of Continually Stay-point)對(duì)于連續(xù)點(diǎn)序列數(shù)集合SP={a,b,c,d,…,i}(0

定義5 (連續(xù)停留點(diǎn)子軌跡代表點(diǎn)，Represent Point of Continually Stay-point Sub-trajectory)每個(gè)連續(xù)停留點(diǎn)子軌跡只保留一個(gè)點(diǎn)Q代表該子集的經(jīng)緯度和時(shí)間，額外加上用戶在該子軌跡中的總停留時(shí)間。對(duì)于連續(xù)停留點(diǎn)子集SPCm，其代表點(diǎn)Qm包含經(jīng)度(Latm)、緯度(Lngm)、時(shí)間(Tm)以及子集內(nèi)總停留時(shí)長(zhǎng)(STm)，全部的Q組成集合RPC。

定義6 (區(qū)域代表點(diǎn)，Response Point of Region)將子軌跡代表點(diǎn)按照密度聚類(Density Cluster)的方式聚集為QDC1、QDC2…QDCu等類。聚類完成后，每個(gè)類中取一個(gè)代表點(diǎn)形成區(qū)域代表點(diǎn)集RPR。

定義7 (行為模式，Behavior Pattern)經(jīng)過(guò)密度聚類之后，子軌跡代表點(diǎn)按照時(shí)間順序可組成一條新軌跡RTD，相鄰兩個(gè)不同區(qū)域代表點(diǎn)構(gòu)成一組模式TPv(0

3 算法流程

停留地點(diǎn)往往伴隨著有目的性的用戶活動(dòng)。為突出目的性造成的軌跡異常，研究思路集中在用戶在符合條件的停留點(diǎn)之間切換的頻率。流程分3個(gè)大部分：停留點(diǎn)預(yù)處理(初步過(guò)濾數(shù)據(jù))、密度聚類處理(地理空間上相近地點(diǎn)聚類)、模式匹配及異常篩選。具體流程如圖2所示。

圖2 流程圖示

3.1 預(yù)處理

為直觀查看點(diǎn)分布情況，首先將經(jīng)緯度轉(zhuǎn)化為地圖中的實(shí)際距離。經(jīng)緯度與現(xiàn)實(shí)距離轉(zhuǎn)換關(guān)系如公式1：

(1)

計(jì)算距離和速度時(shí)，兩點(diǎn)Pi,pj之間距離計(jì)算[11]公式如公式2：

(2)

將坐標(biāo)轉(zhuǎn)換為現(xiàn)實(shí)空間距離之后，就可以直接計(jì)算各個(gè)點(diǎn)之間的速度。速度計(jì)算出來(lái)之后，經(jīng)過(guò)速度閾值V(一般取正常成年人平均步行速度1 m/s)過(guò)濾，形成停留點(diǎn)集SP以及連續(xù)停留點(diǎn)子集。此時(shí)的連續(xù)停留點(diǎn)子集中，包含有一些總停留時(shí)間很短的點(diǎn)，這類點(diǎn)多出現(xiàn)在路口附近，并不帶有“目的”。為避免這些點(diǎn)造成干擾，只保留連續(xù)停留時(shí)長(zhǎng)不小于1 min的連續(xù)子集。由于處理過(guò)后，同一軌跡相鄰的停留點(diǎn)之間間隔都是10 s，所以連續(xù)停留點(diǎn)數(shù)目閾值設(shè)置為6。這樣每個(gè)連續(xù)點(diǎn)集合就能至少代表一項(xiàng)活動(dòng)[12]，求得所有連續(xù)子軌跡的子軌跡代表點(diǎn)，組成代表點(diǎn)集NSP。具體算法實(shí)現(xiàn)如下。

算法1：預(yù)處理算法

Input：軌跡TD={P1,P2,P3,…,Pn}，速度閾值V，停留點(diǎn)連續(xù)點(diǎn)數(shù)閾值num。

Output：連續(xù)停留點(diǎn)代表點(diǎn)集合NSP

1TJi→NSP

2 fori=1 tom-1;

3k=0;l=0;

5 if speedi

6k=k+1;

7INDk=i;

8 addPi&INDktoSP;

9 else

10 end if

11 end for

12 forj=1 tok

13 ifINDk+1=IND(k+1);

14 addSPjtoSPCl; ∥將連續(xù)的停留點(diǎn)歸到一個(gè)子集

15 else

16l=l+1;

17 end if

18 end for

19 fori=1 tol

20 if numel (SPCi)

21 delet SPCi;

22 else

23 addSPCito NSP;

24 end if

25 end for

26 return NSP

3.2 密度聚類

DBSCAN是一種經(jīng)典的基于密度的非監(jiān)督空間聚類算法，它可以將具有足夠密度的區(qū)域劃分成簇，可以在具有噪聲的軌跡數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇類，并將發(fā)現(xiàn)的簇類定義為密度相連的點(diǎn)的最大合集。以此為代表的密度聚類算法不需要指定類的數(shù)量。使用DBSCAN算法聚類軌跡數(shù)據(jù)以利用隱含語(yǔ)義的研究有很多，相關(guān)的研究非常充分。

要了解DBSCAN算法原理，首先有5個(gè)關(guān)鍵概念[13]：鄰域、核心對(duì)象(Core Points)、直接密度可達(dá)(Directly Density-reachable)、密度可達(dá)(Density-reachable)、密度相連(Density-connected)。

鄰域指的是指定對(duì)象p半徑epsilon內(nèi)的區(qū)域。

核心對(duì)象是指如果指定對(duì)象p的鄰域內(nèi)樣本點(diǎn)數(shù)大于等于參數(shù)MinPts，則對(duì)象p就是核心對(duì)象。

直接密度可達(dá)指的是，對(duì)于一個(gè)集合TD，如果p在核心對(duì)象q的鄰域內(nèi)，則p從q出發(fā)是直接密度可達(dá)的。

密度可達(dá)指的是，對(duì)于集合TD，如果存在一個(gè)對(duì)象鏈P1,P2,…,Pn，P1=q，Pn=p，對(duì)于Pi∈TD，1≤i≤n，Pi+1是從Pi出發(fā)直接密度可達(dá)，則對(duì)象P是從對(duì)象q關(guān)于epsilon和MinPts密度可達(dá)的。

密度相連指的是如果存在對(duì)象O∈TD，使得對(duì)象P和q都是從o出發(fā)關(guān)于epsilon和MinPts密度可達(dá)，那么對(duì)象p到q是關(guān)于epsilon和MinPts是密度相連的。

如圖3所示，各個(gè)點(diǎn)周?chē)膱A圈代表了對(duì)象的鄰域，P1對(duì)于P2來(lái)說(shuō)是直接密度可達(dá)的，P1、P2、P3、P4、P5、P6之間彼此密度可達(dá)且密度相連，P7對(duì)于其余點(diǎn)則無(wú)聯(lián)系。

圖3 密度聚類示意圖

考慮到在現(xiàn)實(shí)中，個(gè)人活動(dòng)頻繁的地點(diǎn)呈現(xiàn)出一種地點(diǎn)與目的性混雜的分布情況，表現(xiàn)為其活動(dòng)點(diǎn)不是點(diǎn)狀或線狀分布的，而是呈現(xiàn)出區(qū)域化、多目的性混雜的狀態(tài)。DBSCAN (Density-Based Spatial Clustering of Applications with Noise)聚類方法[14]可以適應(yīng)多種聚類形狀，可以將不同活動(dòng)區(qū)域聚類成不同類別。

在DBSCAN概念的基礎(chǔ)上，聚類完整過(guò)程如下：首先在子軌跡中搜索出密度極大點(diǎn)，將極大點(diǎn)定義為子軌跡代表點(diǎn)，每個(gè)子軌跡的代表點(diǎn)組成子軌跡代表點(diǎn)集，在子軌跡代表點(diǎn)集中搜索密度相連的點(diǎn)聚集成簇，同時(shí)輸出簇中密度極大點(diǎn)，輸出為區(qū)域代表點(diǎn)。區(qū)域代表點(diǎn)代表了某個(gè)區(qū)域內(nèi)的所有停留點(diǎn)，因此可以看成是一類活動(dòng)。

DBSCAN算法有兩個(gè)參數(shù)，分別是epsilon和minPts，其中epsilon控制簇生長(zhǎng)過(guò)程中的搜索半徑，minPts控制最小簇點(diǎn)的數(shù)量。將DBSCAN算法的生長(zhǎng)器部分做出了調(diào)整：生長(zhǎng)器在搜索同簇類時(shí)，不產(chǎn)生噪聲簇，取而代之的是產(chǎn)生零散的小簇，并且所有點(diǎn)都被歸入簇中。這樣就可以使用密度聚類的簇標(biāo)號(hào)代表點(diǎn)的位置，后續(xù)算法就不必關(guān)注具體的坐標(biāo)數(shù)據(jù)。這給后續(xù)異常檢測(cè)算法減小了復(fù)雜度，并且也保證了數(shù)據(jù)的可靠性。具體過(guò)程如算法2所示。

算法2：密度聚類及模式輸出算法

Input：NSP，epsilon，minPts

Output：RTDBP

1.c=0；

2. IDX=DBSCAN(NSP，epsilon，minPts)

3. fori=1 to max(IDX)

4. a=find(IDX==i)；

5. QDCi=NSP(a)； ∥軌跡數(shù)據(jù)編碼化

6. end for

7. fori=1：numel(NSP)

8. ifIDXi+1=IDX(i+1)

9. nexti

10. else

11.c=c+1;

12.TPc=(IDXi,IDX(i+1));

13. end if

14. end for

15. returnRTDBP; ∥輸出行為模式集合

在處理過(guò)程中，軌跡數(shù)據(jù)輸出的內(nèi)容也發(fā)生了較大的變化。為了保證代表點(diǎn)集合能夠逆推到最初停留點(diǎn)集SP中的經(jīng)緯度等原始信息，在算法運(yùn)算過(guò)程中一直使用序數(shù)保留了各點(diǎn)集之間關(guān)鍵數(shù)據(jù)的映射信息，以減小算法運(yùn)行時(shí)的復(fù)雜度。序列的映射作用如圖4所示。

圖4 軌跡點(diǎn)集中的序數(shù)起到的映射作用

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

實(shí)驗(yàn)環(huán)境為Windows10、64位系統(tǒng)，Intel Core i7-9750H@2.60 GHz CPU，16 GB內(nèi)存，512 GB+1 TB固態(tài)硬盤(pán),軟件為MATLAB R2016a,QGIS 3.12.2。實(shí)驗(yàn)數(shù)據(jù)集Geolife數(shù)據(jù)集[15]是微軟研究Geolife項(xiàng)目從2007年4月到2012年8月收集的182個(gè)用戶的軌跡數(shù)據(jù)。這些數(shù)據(jù)包含了一系列按時(shí)間先后產(chǎn)生的點(diǎn)，每一個(gè)點(diǎn)包含經(jīng)緯度、海拔等信息，共17 621條軌跡。

4.1 實(shí)驗(yàn)數(shù)據(jù)預(yù)處理

為展示實(shí)驗(yàn)過(guò)程，選用005用戶(包含109 046個(gè)軌跡點(diǎn))作為例子。實(shí)際生活中，人的步行速度大約是1 m/s，用這個(gè)速度作為閾值V，將不超過(guò)此速度的點(diǎn)劃入停留點(diǎn)集SPTD。實(shí)驗(yàn)中多數(shù)數(shù)據(jù)是以5 s為一個(gè)間隔采集的數(shù)據(jù)，所以可以通過(guò)觀察連續(xù)停留點(diǎn)數(shù)量反映軌跡持續(xù)的時(shí)長(zhǎng)和分布區(qū)域之間的關(guān)系。

為驗(yàn)證連續(xù)停留點(diǎn)數(shù)目取6是否符合直觀印象中的“既能過(guò)濾掉零散的點(diǎn)，又不會(huì)損失包含活動(dòng)信息的數(shù)據(jù)”，文中遍歷了num取1～10的所有情況，取其中1、4、7、10為例子，在GIS平臺(tái)上效果如圖5所示。

圖5 005用戶不同連續(xù)數(shù)量停留點(diǎn)的分布圖示(部分)

從圖5中可以發(fā)現(xiàn)，連續(xù)停留點(diǎn)子軌跡的連續(xù)數(shù)量越大、分布范圍越集中、長(zhǎng)時(shí)間活動(dòng)的點(diǎn)更多；連續(xù)停留點(diǎn)的連續(xù)數(shù)量越小，分布越分散、長(zhǎng)時(shí)間活動(dòng)的點(diǎn)更少。經(jīng)觀察，當(dāng)連續(xù)停留點(diǎn)數(shù)量大于6(總停留時(shí)間大于60 s)時(shí)，停留點(diǎn)在路網(wǎng)中分布明顯少很多，分布相對(duì)集中，此時(shí)既可以排除意外情況造成的停留點(diǎn)干擾，也可以減少后續(xù)密度聚類算法的復(fù)雜程度，方便與其他算法對(duì)比效果。

為控制預(yù)處理部分中兩個(gè)經(jīng)驗(yàn)值(停留點(diǎn)速度閾值V和連續(xù)停留點(diǎn)數(shù)目num)可能對(duì)實(shí)驗(yàn)結(jié)果和對(duì)比算法產(chǎn)生的影響，后續(xù)實(shí)驗(yàn)不論是本文算法還是用作對(duì)比算法，都使用預(yù)處理后的數(shù)據(jù)實(shí)驗(yàn)對(duì)比，以保證對(duì)比實(shí)驗(yàn)所用數(shù)據(jù)集完全相同。

4.2 實(shí)驗(yàn)數(shù)據(jù)預(yù)處理

篩選完符合條件的連續(xù)停留點(diǎn)子軌跡后，計(jì)算出子軌跡代表點(diǎn)。對(duì)所有子軌跡代表點(diǎn)的經(jīng)緯度密度聚類，聚類結(jié)果代表了地理空間中距離相近的停留點(diǎn)。密度聚類的參數(shù)只有epsilon(minPts是判斷噪聲點(diǎn)的值，必須取1，以防止噪聲點(diǎn)集破壞點(diǎn)的分布)。為大致確定epsilon的最有取值范圍，分別取25、50、100、150、200進(jìn)行實(shí)驗(yàn)聚類。實(shí)驗(yàn)結(jié)果如圖6所示，圖中不同顏色代表不同的聚類簇。

圖6 不同epsilon取值對(duì)聚類的影響(部分)

不難發(fā)現(xiàn)，epsilon取較小值時(shí)，聚類較為精細(xì)，劃分出的軌跡區(qū)域也更為精細(xì)。分別以15、20、25代入。為提高區(qū)分的細(xì)粒度，模式頻率閾值S不宜太大，因此分別取4、5、6。

按照劃分區(qū)域是否正確，不同參數(shù)下算法劃分區(qū)域的精確率(Precision)正確率(Accuracy)如表1所示。

表1 本文算法不同參數(shù)情況下區(qū)域劃分的精確率和正確率 %

4.3 與其他方法對(duì)比

為驗(yàn)證方法的準(zhǔn)確性，在相同環(huán)境、同樣經(jīng)過(guò)預(yù)處理的數(shù)據(jù)集條件下，與OPTICS算法取較優(yōu)解時(shí)的結(jié)果做了橫向?qū)Ρ?。OPTICS算法是DBSCAN算法的改進(jìn)版本，可以遍歷DBSCAN各項(xiàng)參數(shù)下的聚類結(jié)果，以輔助確定DBSCAN最優(yōu)參數(shù)。其參數(shù)有minPts和epsilon,但這兩項(xiàng)參數(shù)只是一個(gè)形式，并不會(huì)影響到相對(duì)輸出順序，也不會(huì)影響最優(yōu)結(jié)果。

當(dāng)minPts分別取3、5、7，epsilon取15時(shí)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 OPTICS算法不同參數(shù)情況下區(qū)域劃分的指標(biāo)

同樣的數(shù)據(jù)從開(kāi)始處理到算法運(yùn)行結(jié)束，OPTICS算法運(yùn)算時(shí)長(zhǎng)為0.5 s。文中提出方法運(yùn)算時(shí)長(zhǎng)為0.1 s，使用時(shí)間略短。除去預(yù)處理部分，文中方法將軌跡數(shù)據(jù)多次精簡(jiǎn)，密度聚類的數(shù)據(jù)量很少，因此復(fù)雜度也很小。該方法的空間復(fù)雜度S(n)=O(f(n))，時(shí)間復(fù)雜度最大為T(mén)(n)max=O(3n)，而OPTICS算法的時(shí)間復(fù)雜度為O(n2)。

5 結(jié)論

通過(guò)實(shí)驗(yàn)結(jié)果得到的準(zhǔn)確率和正確率，以及與OPTICS算法比較的結(jié)果，可以得出以下結(jié)論。

(1)算法能夠較好地識(shí)別出軌跡區(qū)域，參數(shù)選取最優(yōu)時(shí)，其正確率可達(dá)76%，同時(shí)精度也很高。

(2)與OPTICS算法結(jié)果對(duì)比可得，OPTICS算法對(duì)于精細(xì)化區(qū)域劃分效果很差，精確率只有22%左右。而文中算法得到的結(jié)果精確率穩(wěn)定在90%左右，計(jì)算精度比OPTICS約高70%。

(3)提出的方法對(duì)參數(shù)輸入比較敏感。epsilon取15和取25，正確率差別較大(7%)，實(shí)際應(yīng)用時(shí)要注意參數(shù)選擇。