石陸魁，張延茹，張 欣

(1.河北工業(yè)大學(xué) 計算機科學(xué)與軟件學(xué)院,天津 300401; 2.河北省大數(shù)據(jù)計算重點實驗室(河北工業(yè)大學(xué)),天津 300401) (*通信作者電子郵箱shilukui@scse.hebut.edu.cn)

基于時空模式的軌跡數(shù)據(jù)聚類算法

石陸魁1,2*，張延茹1，張 欣1

(1.河北工業(yè)大學(xué) 計算機科學(xué)與軟件學(xué)院,天津 300401; 2.河北省大數(shù)據(jù)計算重點實驗室(河北工業(yè)大學(xué)),天津 300401) (*通信作者電子郵箱shilukui@scse.hebut.edu.cn)

針對軌跡聚類算法在相似性度量中多以空間特征為度量標準，缺少對時間特征的度量，提出了一種基于時空模式的軌跡數(shù)據(jù)聚類算法。該算法以劃分再聚類框架為基礎(chǔ)，首先利用曲線邊緣檢測方法提取軌跡特征點；然后根據(jù)軌跡特征點對軌跡進行子軌跡段劃分；最后根據(jù)子軌跡段間時空相似性，采用基于密度的聚類算法進行聚類。實驗結(jié)果表明，使用所提算法提取的軌跡特征點在保證特征點具有較好簡約性的前提下較為準確地描述了軌跡結(jié)構(gòu)，同時基于時空特征的相似性度量因同時兼顧了軌跡的空間與時間特征，得到了更好的聚類結(jié)果。

時空模式；軌跡數(shù)據(jù)；曲線邊緣檢測；相似性度量；密度聚類

0 引言

近年來隨著移動定位服務(wù)和云計算技術(shù)的發(fā)展，搜集和處理移動定位信息已成為現(xiàn)實。由移動定位數(shù)據(jù)組成的海量數(shù)據(jù)庫推動了關(guān)于移動定位數(shù)據(jù)研究的發(fā)展。作為典型的移動定位數(shù)據(jù)之一，時空軌跡數(shù)據(jù)是指沿時間順序?qū)臻g移動對象的數(shù)值型記錄，包括采樣點位置、采樣時間、速度等，而空間對象的這些特征都有可能隨著時間的推移而發(fā)生變化，人們嘗試著將這些可感而不可知的感性知識轉(zhuǎn)化為有現(xiàn)實意義的數(shù)字信息，用于生活，提供便利。然而面對規(guī)模龐大的時空軌跡數(shù)據(jù)，如何快速地從中挖掘有用價值是人們必須面對的一個重要問題。

為了從時空軌跡數(shù)據(jù)中獲取有用信息，聚類技術(shù)被用于對空間移動對象時空特征的提取。目前研究重點主要集中在軌跡數(shù)據(jù)模型定義、相似性度量和軌跡聚類方法三個方面。文獻[1]基于全區(qū)間模型對軌跡進行聚類，提出一種基于采樣和密度的軌跡聚類算法，使用軌跡全體采樣點來度量整條軌跡的相似性，并采用基于密度的聚類算法完成聚類。文獻[2]根據(jù)已有時空軌跡數(shù)據(jù)樣本提取軌跡線索特征并進行匯總，以線索相似性來衡量兩條軌跡之間的距離。然而將軌跡作為整體進行聚類的方法可能會忽略存在于整體相似度低的軌跡之間的局部相似性。文獻[3]提出了一種劃分-歸組(Partition-and-Group)聚類框架，該方法首先使用最小描述長度 (Minimum Description Length, MDL)對軌跡進行子軌跡段劃分，然后使用基于密度的聚類方法(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)對劃分后的子軌跡段進行聚類。其中MDL方法產(chǎn)生于對某種模型進行編碼壓縮的要求，其原理是計算出總描述長度最小的模型，應(yīng)用到軌跡劃分中時，可能會導(dǎo)致軌跡劃分不具有實際代表性，失去其現(xiàn)實意義。文獻[4]首先根據(jù)相鄰軌跡樣本點的轉(zhuǎn)向角對軌跡進行劃分，其次通過計算軌跡段的結(jié)構(gòu)(方向、速度、轉(zhuǎn)角、位置)相似度來判斷軌跡的匹配程度，進而完成軌跡聚類。該提取特征點的方法適用于相鄰樣本點角度變化較明顯的如道路軌跡數(shù)據(jù)中,然而在相鄰樣本點持續(xù)局部小角度變化過程中形成整體大角度變化的情況下，該判斷特征點的方法可能會導(dǎo)致移動軌跡的劃分失去其準確性。

時空軌跡數(shù)由位置坐標和相應(yīng)的時間標記合成，因此，時間特征對分析移動物體的運行模式非常關(guān)鍵。然而現(xiàn)有軌跡聚類算法中常常忽略了對時間特征的相似性度量，如文獻[1-4]，為此，本文提出基于時空模式的軌跡數(shù)據(jù)聚類方法，以劃分-歸組聚類框架為基礎(chǔ)，從軌跡特征點提取、時空相似性度量和軌跡聚類算法三個方面進行改進。首先為解決MDL或“相鄰樣本點轉(zhuǎn)角”方法提取軌跡特征點有所不足的問題，借鑒圖像曲線邊緣信息檢測的方法提取軌跡特征點，生成具有代表性的子軌跡段集合；其次采用DBSCAN算法同時根據(jù)空間和時間相似性對子軌跡段進行聚類，并使用搜索網(wǎng)格提高計算效率。

1 軌跡特征點的提取

1.1 相關(guān)定義

時空軌跡數(shù)據(jù)記錄了持續(xù)移動對象在某時刻出現(xiàn)在相應(yīng)位置上的一系列信息，是其運動狀態(tài)下時空屬性的表現(xiàn)。參考文獻[3]對時空軌跡數(shù)據(jù)的定義進行擴展，在這里給出時空軌跡數(shù)據(jù)集、特征點集合以及子軌跡集合的數(shù)學(xué)定義。

定義1 時空軌跡數(shù)據(jù)集。給定時空軌跡數(shù)據(jù)集TRS，共有tranum條軌跡，表示為TRS={TR1,TR2,…,TRtranum}，集合中的每條軌跡都由若干個多維樣本點組成，任意一條軌跡TRi表示為：TRi={P1,P2,…，Pitnum}，其中1≤i≤tranum，itnum為第i條時空軌跡樣本點總數(shù)。軌跡中任意一個樣本點Pj表示為Pj=〈pnum,ptraid,px,py,ptime〉，顯示出在ptime時刻，軌跡ptraid中樣本點pnum的位置為(px,py)，其中1≤j≤itnum。

定義2 特征點集合。對第i條軌跡進行子軌跡段劃分，得到能夠代表該條軌跡的特征點集合CHA_TRi，表示為CHA_TRi={tc1,tc2,…,tcicnum}，其中icnum為第i條軌跡特征點總數(shù)，集合中tci為該條軌跡的特征點，tci定義如樣本點。

定義3 子軌跡段集合。根據(jù)所有軌跡的特征點集合生成全部軌跡的子軌跡段集合，假設(shè)共有l(wèi)num條子軌跡段，子軌跡段集合定義為SUB_TRS={L1,L2,…,Lk,…,Llnum}，其中Lk=〈tck,tck+1〉(1≤k≤lnum)，tck,tck+1為相鄰特征點。

1.2 軌跡上特征點的判定

特征點定義為軌跡中行為變化相對明顯的點，能很好地對軌跡結(jié)構(gòu)進行描述，同時應(yīng)具有一定簡縮性及準確性。圖像算法中通過檢測曲線凹凸分界點來提取曲線邊緣信息的方法可以應(yīng)用到軌跡特征點的提取中。曲線的凹凸分界點指改變曲線向上或向下方向的點。過曲線上任意一點x可以作一條關(guān)于該條曲線的切線L，切線的方向與曲線上x點的方向相同，此時切線L在切點x附近的部分“最接近”曲線，由于曲線是其所有切線的包絡(luò)線，因此在較小范圍內(nèi)，曲線上的點都處于切線L的同一側(cè)。假設(shè)給定曲線是由彼此很接近的點集組成，曲線的切線可以由曲線上彼此緊挨著的兩個點構(gòu)成的正向直線代替。據(jù)此，推廣到軌跡應(yīng)用中，假設(shè)某條軌跡上存在著兩個相鄰樣本點x和x′，且這兩個樣本點之間的距離非常近，利用無限逼近思想，過這兩點可以作一條關(guān)于該條軌跡的切線，通過判斷樣本點與該點相鄰軌跡段(即切線)的變化趨勢來確定該點是否為特征點。相關(guān)定義[5]如下：

定義4 設(shè)平面上兩點的坐標分別為P1(x1,y1)和P2(x2,y2)，x1≠x2，連接P1,P2點得到一條有向直線，稱這條有向直線為正向直線，而對應(yīng)的直線方程:

F:(y2-y1)(x-x1)+(x2-x1)(y-y1)=0

(1)

為關(guān)于P1,P2的正向直線方程F。

定義5 假設(shè)平面上存在一條正向直線L，根據(jù)L將平面上的點分為兩類，處于正向直線L順時針一側(cè)的點稱為關(guān)于L的內(nèi)點，而處于正向直線L逆時針一側(cè)的點稱為關(guān)于L的外點。

定理1 記平面上兩點P1,P2的正向直線方程F12的左端表達式記為：

F12(x,y)=(y2-y1)(x-x1)+(x2-x1)(y-y1)

(2)

對于不在直線L上任一點P0(x0,y0)，則有：

1)若F12(x0,y0)<0，則點P0是關(guān)于正向直線L的內(nèi)點；

2)若F12(x0,y0)>0，則點P0是關(guān)于正向直線L的外點。

定理2 設(shè)P1(x1,y1)，P2(x2,y2)，P3(x3,y3)，P4(x4,y4)(x1

1)連接P1(x1,y1)，P2(x2,y2)點得到正向直線L1的方程為F12(x,y)=0，計算F12(x3，y3)的值；

2)連接P2(x2,y2)，P3(x3,y3)點得到正向直線L2的方程為F23(x,y)=0，計算F23(x4,y4)的值；

3)若F12(x3,y3)*F23(x4,y4)<0，說明在P3(x3,y3)點處軌跡的方向有所改變，認為P3(x3,y3)點是特征點，否則P3(x3,y3)不是特征點。

據(jù)此得到軌跡特征點提取方法，即由樣本起點P1P2構(gòu)成一條關(guān)于軌跡的切線L1，求P3點關(guān)于這條切線的內(nèi)點或外點；由P2P3點構(gòu)成另外一條關(guān)于軌跡的切線L2，求P4點關(guān)于這條切線的內(nèi)點或外點；若P3和P4關(guān)于各自相鄰切線發(fā)生變化，即P3P4不同為內(nèi)點或不同為外點，那么認為P3點是軌跡在P1P2P3P4處發(fā)生變化的點，并添加到特征點集合中。循環(huán)判斷，直到最后一個樣本點。

偽代碼如下所示。其中步驟1先將軌跡開始的點P1和P2添加到特征點集合中，從第三個點開始判斷是否為軌跡特征點，如步驟2到步驟6所示，滿足條件的軌跡點將被添加到特征點集合中，不滿足條件將依次循環(huán)判斷下一樣本點直到軌跡結(jié)束點。步驟7將軌跡結(jié)束點添加到特征點集合中，至此完成特征點提取。步驟8至步驟17為軌跡特征點識別方法Calculate_cp()來判斷current點是否為特征點，并返回邏輯值。最終利用生成的特征點集合形成該條軌跡的子軌跡段集合。

算法1CharacteristicPointsExtraction。

輸入：一條軌跡集合TRi=P1P2…Pitnum

輸出：該條軌跡特征點集合CHA_TRi={tc1,tc2,…,tcicnum}

步驟1 將P1P2點加入到集合CHA_TRi中；first=P1；

步驟2start=first;current:=start.next.next；

步驟3 while(current.next不為空)，轉(zhuǎn)至步驟8調(diào)用方法Calculate_cp計算current是否為特征點；

步驟4 若current是特征點，將current點加入到特征點集合CHA_TRi中，否則不添加；

步驟5start=start.next;current=current.next；

步驟6 循環(huán)判斷結(jié)束；

步驟7 將軌跡結(jié)束點添加到集合CHA_TRi中。

步驟8 初始化cpflag=false；

步驟9x1:=start.x;y1:=start.y；

步驟10x2:=start.next.x;y2:=start.next.y；

步驟11x3:=current.x;y3:=current.y;

步驟12x4:=current.next.x;y4:=current.next.y；

步驟13s1:=(x2-x1)*(y3-y1)+(y1-y2)*

(x3-x1)；

步驟14s2=(x3-x2)*(y4-y2)+(y2-y3)*

(x4-x2)；

主要考察了政府會計制度的改革以及國家會計制度改革對事業(yè)單位現(xiàn)有財務(wù)管理的影響，旨在促進未來治理制度和公共財務(wù)管理的某些改革。發(fā)現(xiàn)我國公用事業(yè)會計系統(tǒng)存在的一些問題，如會計核算和登記等系統(tǒng)管理不夠規(guī)范，制度內(nèi)容不健全等。在現(xiàn)行的會計和預(yù)算管理系統(tǒng)中，原有財務(wù)系統(tǒng)并不能反映該機構(gòu)的實際情況。制度核算體制改革至關(guān)重要，會計制度改革是一項長期任務(wù)。目前，事業(yè)單位會計制度改革后，可以更有效地改善事業(yè)單位會計制度，大大提高事業(yè)單位的經(jīng)濟管理和資產(chǎn)管理，同時提高事業(yè)單位的辦事效率。

步驟15s3=(x4-x2)*(y3-y2)+(y2-y4)*

(x3-x2)；

步驟16 if((s1*s2)<=0)cpflag:=true；

步驟17 returncpflag；

2 軌跡聚類算法

2.1 時空相似性度量

基于時空模式的軌跡聚類顧名思義就是要在時間和空間兩種模式下對軌跡數(shù)據(jù)進行聚類，無論忽略哪一種屬性，其聚類結(jié)果的準確性及現(xiàn)實意義都將大打折扣，那么針對目前大多數(shù)軌跡聚類算法著重考慮軌跡空間特征相似性度量忽略時間特征相似性度量的問題，本文提出一種兼顧時間與空間屬性相似性的相似性度量方法，即在空間距離的基礎(chǔ)上增加時間相似性距離判斷。

時空模式下軌跡的空間相似性度量使用模式識別中常用的空間距離度量方法[3,6]，包括平行距離、垂直距離和角度距離。假設(shè)兩條軌跡段分別為Li(si,ei)以及Lj(sj,ej)，其中si、ei、sj、ej分別表示Li和Lj的開始及結(jié)束點，并且Li≥Lj，由短軌跡段Lj兩端點sj、ej向長軌跡段Li兩端點si,ei垂直投影，得到Lj在軌跡段Li上的垂直點ps和pe，如圖1所示。

圖1 兩軌跡段空間距離示意圖

定義6 垂直距離。Li和Lj之間的垂直距離定義如下：

(3)

定義7 平行距離。Li和Lj之間的平行距離定義如下：

d//(Li,Lj)=MIN(l//1,l//2)

(4)

定義8 角度距離。Li和Lj之間的角度距離定義如下(其中‖Lj‖為Lj的長度)：

(5)

綜上，Li與Lj之間的空間距離定義如下：

DS=d⊥(Li,Lj)+d//(Li,Lj)+dθ(Li,Lj)

(6)

計算軌跡段之間時間距離時，度量單位將是影響聚類分析結(jié)果的重要因素。諸多文獻都使用標準分數(shù)z_score對數(shù)據(jù)進行預(yù)處理，以消除數(shù)據(jù)間存在著的單位差異[7-8]。其中文獻[8]提出一種不等長時間序列(Short Time Series, STS)滑窗距離聚類算法，該算法使用z_score對時間序列進行標準化預(yù)處理，并設(shè)計基于滑窗的不等長時間序列距離計算方法，即設(shè)計長度等于較短時間段的滑動窗口，從較長時間段開始點向結(jié)束點滑動，得到一系列長度等于短時間序列的子序列集合，選擇子序列中距離較短時間序列最近的STS距離作為這兩條不等長時間序列的時間距離。然而通過實驗證明，該方法具有較高的時間復(fù)雜度，計算花費非常大。

本文使用一種簡單方法對時間數(shù)據(jù)進行預(yù)處理。首先以格林威治標準時間1987-12-31T00:00:00為時間起始點，此時設(shè)時間為1，以秒為單位依此類推，即1987-12-31T00:00:01設(shè)為2，最終時間范圍為168 825 628～272 245 926。其次鑒于數(shù)值較大計算不便，本文時間數(shù)值除以一天秒數(shù)(86 400)對時間進行標準化設(shè)置，即時間/86 400所得值為最終標準化線性時間序列。應(yīng)用到軌跡時間序列中，假設(shè)較長軌跡的時間段為Li(ist,iet)，ist和iet分別對應(yīng)Li的開始時間和結(jié)束時間，較短軌跡的時間段為Lj(jst,jet)，其中jst和jet分別對應(yīng)Lj的開始時間和結(jié)束時間，‖Li‖≥‖Lj‖。比較兩條軌跡的時間段，可得三種情況：Li完全包含Lj，Li部分包含Lj以及Li完全不包含Lj，三種情況如圖2(a)所示，其中‖Lj‖、‖Lj′‖、‖Lj″‖分別表示其長度。

應(yīng)用到實際情況中，可能存在兩條軌跡段時間跨度相差較大的情況，在這里取兩條軌跡段之間的最近距離作為兩條軌跡段的時間距離。將較短的子軌跡時間段Lj向較長的子軌跡時間段Li投影，以左投影為例，如圖2(b)所示，將較短時間段結(jié)束點jet投影至較長時間段上距離其開始點ist長度為|Lj|的點，即iet′點，其中|iet′-ist|=|Lj|。據(jù)此將Li與Lj之間的時間距離定義如下：

(7)

圖2 兩條軌跡段時間距離

考慮到空間距離和時間距離存在著不同數(shù)量級的問題，在此使用z-score標準分數(shù)對空間及時間距離進行標準化。對變量f的度量值進行如下標準化[9]。

1)計算絕對偏差的平均值：

(8)

其中：x1f,x2f,…,xnf為f的n個度量值，mf為f的均值:

(9)

2)計算標準度量值：

Zif=(xif-mf)/sf

(10)

Zif為標準化后度量值，表示原始數(shù)據(jù)偏離平均值的程度,且服從正態(tài)分布。設(shè)標準化后空間距離和時間距離分別為DS′、DT′，通過設(shè)置距離權(quán)重w(0≤w≤1)，可以用來調(diào)整對空間距離和時間距離的敏感度，那么軌跡段間時空距離定義為：

DST=w×DS′+(1-w)×DT′

(11)

2.2 時空軌跡聚類算法

通過觀察軌跡分段得到的子軌跡段集，可以發(fā)現(xiàn)子軌跡段形狀具有不規(guī)則性，且集合中含有大量的噪聲。由于DBSCAN算法通過對區(qū)域密度的連通性分析來聚類，不僅可以發(fā)現(xiàn)任意形狀的聚類簇，而且在聚類過程中能夠最大限度地避免噪聲的干擾，因此在此采用該方法對子軌跡段進行聚類。該算法需要設(shè)定兩個全局參數(shù)，即鄰域半徑eps和minlns。DBSCAN通過篩選子軌跡數(shù)據(jù)集中每個對象的eps鄰域來搜索簇，如果對象p的eps鄰域中包含的對象個數(shù)大于等于minlns個，則創(chuàng)建一個以p為核心對象的簇。然后，算法迭代地聚類從這些核心對象直接密度可達的所有對象，這個過程中可能涉及一些密度可達簇的合并，當沒有新的對象添加到任何簇時，過程結(jié)束。下面給出相關(guān)定義[10]。

定義9eps鄰域。以給定對象p為中心，半徑為eps的區(qū)域稱為該對象的eps鄰域。

定義10 核心對象。在給定對象p的eps鄰域內(nèi)，如果樣本點數(shù)大于等于minlns，則稱該對象為核心對象。

定義11 直接密度可達。若給定對象q為核心對象，并且對象p在核心對象q的eps鄰域內(nèi)，那么稱對象p從對象q出發(fā)是直接密度可達。

定義12 密度可達。樣本集合D中，如果存在一個對象鏈p1，p2，…，pn，設(shè)p1=q，pn=p，若對象鏈中任意pi+1是從pi出發(fā)關(guān)于eps和minlns直接密度可達的，那么對象p是從對象q出發(fā)關(guān)于eps和minlns密度可達。

定義13 密度相連。如果樣本集合D中存在對象o，使得對象p和q都是從o出發(fā)關(guān)于eps和minlns密度可達，那么稱對象p和o是從對象q出發(fā)關(guān)于eps和minlns密度相連。

應(yīng)用到軌跡段聚類中，需要掃描整個軌跡段數(shù)據(jù)集，找到任意一個核心軌跡段，對該核心軌跡段進行擴充。擴充的方法是尋找從該核心軌跡段出發(fā)的所有密度相連的軌跡段。遍歷該核心軌跡段的eps鄰域內(nèi)的所有核心軌跡段，尋找與這些軌跡段密度相連的對象，直到?jīng)]有可以擴充的軌跡段為止。之后重新掃描數(shù)據(jù)集(不包括之前尋找到的簇中的任何軌跡段)，尋找沒有被聚類的核心軌跡段，再重復(fù)上面的步驟，對該核心軌跡段進行擴充直到數(shù)據(jù)集中沒有新的核心軌跡段為止。數(shù)據(jù)集中沒有包含在任何簇中的軌跡段可以認為是噪聲點。算法時間復(fù)雜度的限制主要體現(xiàn)在鄰域的計算，在不使用索引的情況下鄰域計算需要遍歷所有軌跡段，時間復(fù)雜度為O(n2),導(dǎo)致計算效率低；使用索引能夠降低時間復(fù)雜度，如文獻[3-4]都使用R-tree結(jié)構(gòu)進行索引來提高整體計算速度，而Gudmundsson[11]近期提出利用并行算法來計算子軌跡集群的方法，以改進現(xiàn)有串行方法為基礎(chǔ)，利用結(jié)合了GPU計算能力的并行技術(shù)來實現(xiàn)算法速度的大幅提高。由于其實現(xiàn)代價比較昂貴，在這里提出另外一種方法來降低時間復(fù)雜度。參考文獻[12]設(shè)計交通路網(wǎng)的思想，本文首先根據(jù)數(shù)據(jù)樣本集定義m*n的網(wǎng)格空間，并將每一格空間進行序號標記，統(tǒng)計每條軌跡穿過的所有網(wǎng)格。計算某條子軌跡段鄰域的時候先以該條軌跡段所在網(wǎng)格為中心，向四周擴展，形成3×3的九宮格搜索區(qū)域，最終只需判斷所有穿過該九宮格區(qū)域的軌跡，示意圖如圖3所示。

圖3 數(shù)據(jù)索引搜索圖

由此，本文提出一種改進的軌跡聚類算法，偽代碼如下：

算法2TrajectorySegmentsClustering(TSC)。

輸入：軌跡段集合TS={L1,L2,…,Llnum},鄰域半徑eps,最小軌跡段數(shù)minlns。

輸出：聚類結(jié)果集合C={C1,C2,…,Cclusnum}。

步驟1 初始化clusterId=0,并將軌跡集合中所有軌跡段初始化為unclassified。

步驟2 循環(huán)判斷集合TS中所有軌跡段，若軌跡段Li的標識為unclassified則執(zhí)行步驟3。

步驟3 根據(jù)eps計算Li的鄰域Nε(Li)。

步驟4 若|Nε(Li)|≥minlns，則為Li所有鄰域軌跡段Nε(Li)分配為當前clusterId，并將Nε(Li)-{Li}添加到待擴展序列Q中，執(zhí)行步驟8對序列Q進行可達近鄰擴展；否則將此Li設(shè)置為noise。

步驟5clusterId++；將此Li設(shè)置為classified。

步驟6 循環(huán)判斷結(jié)束。

步驟7 根據(jù)clusterId，輸出聚類結(jié)果集合C={C1,C2,…,Cclusnum}。

步驟8 while(Q不為空)，選擇Q中任意Qi。

步驟9 根據(jù)eps計算Qi的鄰域Nε(Qi)。

步驟10 若Nε(Qi)≥minlns,執(zhí)行步驟11；否則將Qi從序列Q中移除。

步驟11 對每一個X(其中X∈Nε(Qi))，若X為noise,將當前clusterId分配給X；否則將X添加至序列Q中。

步驟12 循環(huán)判斷，直到Q為空。

3 實驗結(jié)果

為測試所提算法的有效性，使用兩個真實數(shù)據(jù)集進行測試：一是Starky收集的動物遷徙數(shù)據(jù)集(http://www.fs.fed.us/pnw/starkey/data/tables/)，提取該數(shù)據(jù)集1993年麋鹿的運動軌跡(簡稱Elk93)，并從傳感定位數(shù)據(jù)源中提取經(jīng)緯度坐標以及定位時間信息參與實驗分析；Elk93由47 204個采樣點構(gòu)成33條軌跡。二是大西洋颶風(fēng)數(shù)據(jù)(http://weather.unisys.com/hurricane/atlantic/)，選取經(jīng)度緯度、采樣時間屬性參與實驗；實驗中選取1950—2009年之間的數(shù)據(jù)，經(jīng)整理數(shù)據(jù)集由19 750個采樣點組成639條軌跡。

為直觀體現(xiàn)在軌跡提取特征點階段所提方法的合理性，實驗中選取1950年大西洋颶風(fēng)數(shù)據(jù)中的三條軌跡進行測試(共124個樣本點)，如圖4所示，圖中空心圓為樣本點，整條軌跡由彼此緊挨著的相鄰樣本點構(gòu)成。

圖4 三條颶風(fēng)軌跡數(shù)據(jù)

在實驗中，使用三種提取特征點的方法進行實驗比較，分別為文獻[3]提出的一種近似MDL方法和文獻[4]提出的利用相鄰樣本點轉(zhuǎn)角角度變化來提取特征點的方法(其中轉(zhuǎn)角閾值設(shè)置為45°)，以及本文提出的利用曲線邊緣檢測提取特征點的方法，提取結(jié)果如圖5所示。以擁有32個樣本點的2號軌跡為例，MDL算法提取了11個特征點(+標注)，簡縮率約65%，而“轉(zhuǎn)角”方法提取3個特征點(□標注)，簡縮率90.6%，曲線邊緣檢測法提取特征點4個，簡縮率約87.5%。

圖5 三種特征點提取方法比較結(jié)果

三種特征點提取方法比較結(jié)果如表1所示。三條軌跡共有124個樣本點，使用MDL方法提取特征點數(shù)為30個，在精確性方面表現(xiàn)良好，但在簡縮性方面有些不足；由于軌跡相鄰樣本點轉(zhuǎn)角變化不大導(dǎo)致根據(jù)轉(zhuǎn)角角度變化來提取特征點的方法表現(xiàn)欠佳，提取特征點數(shù)為7個，特別是1號和3號軌跡只提取到了軌跡的開始點和結(jié)束點，不能對軌跡進行準確描述。本文利用曲線邊緣檢測方法的原理，提取出的特征點數(shù)為14個，在保持原軌跡精確性和子軌跡簡潔性之間找到最優(yōu)的平衡，表明了所提方法的合理性。

表1 三種特征點提取方法結(jié)果比較

為了比較不同方法軌跡聚類的質(zhì)量，定義如下聚類質(zhì)量評價公式[3]：

(12)

在時空模式下，通過計算所有聚類簇中相互軌跡段間的平方誤差之和來衡量軌跡聚類質(zhì)量。QMeasure越小表示聚類簇內(nèi)軌跡段密度越大，聚類結(jié)果質(zhì)量越高。其中dist(x,y)為聚類簇中兩條軌跡段間的距離，如式(11)所示。為取得較好結(jié)果，在不同權(quán)重下分別對兩種數(shù)據(jù)進行實驗。圖6為eps=9、minlns=30時，對颶風(fēng)數(shù)據(jù)在不同權(quán)重下進行聚類所得聚類結(jié)果質(zhì)量分析圖。從圖中可以看到，w=0.7時聚類質(zhì)量達到最優(yōu)，整體對權(quán)重設(shè)置具有一定的敏感性。

圖6 颶風(fēng)數(shù)據(jù)在不同權(quán)重下聚類質(zhì)量對比

圖7為eps=8、minlns=28時，對ELK93進行不同權(quán)重下聚類質(zhì)量的分析比較。聚類質(zhì)量在w=0.5達到最優(yōu)，然而由于ELK93數(shù)據(jù)采樣自1993年春季到秋季期間麋鹿的運動軌跡，時間跨度較小，故而對權(quán)重設(shè)置敏感性較低。

圖7 ELK93數(shù)據(jù)在不同權(quán)重下聚類質(zhì)量對比

在此，實現(xiàn)了軌跡聚類(TRAjectoryCLUStering,TRACLUS)算法和根據(jù)轉(zhuǎn)角進行軌跡劃分并由DBSCAN完成聚類的算法(簡稱“轉(zhuǎn)角”算法)，以及本文中提出的改進算法。圖8為eps=9時對大西洋颶風(fēng)數(shù)據(jù)的聚類結(jié)果質(zhì)量分析圖，此時w為0.7。

從圖8中可以看出，使用TRACLUS算法對颶風(fēng)數(shù)據(jù)進行聚類，在minlns=31時達到質(zhì)量最優(yōu)，但由于TRACLUS在進行相似性度量時只考慮了空間特征，導(dǎo)致整體性能低于本文中提出算法?！稗D(zhuǎn)角”算法中由于根據(jù)相鄰樣本點變化角度來劃分軌跡段結(jié)果質(zhì)量低下導(dǎo)致QMeasure值較前兩種方法偏高，為解決這種情況，可事先設(shè)定轉(zhuǎn)角累加閾值，相鄰樣本點轉(zhuǎn)角低于轉(zhuǎn)角閾值時將之累加直至達到累加閾值，這時將樣本點添加為特征點同時累加閾值清零，但由于需要增加參數(shù)值設(shè)置，且對結(jié)果影響較大，因此本文沒有采用這種方法。使用本文算法聚類質(zhì)量在minlns=30時達到最優(yōu)，參數(shù)設(shè)置對聚類質(zhì)量有一定的影響，但聚類質(zhì)量值整體較前兩種算法偏低。

圖9顯示了eps=8時對ELK93數(shù)據(jù)進行聚類的聚類質(zhì)量圖，此時w為0.5。從圖中可以看出使用TRACLUS算法對ELK93數(shù)據(jù)進行聚類，聚類質(zhì)量在minlns=28時達到最優(yōu)，而minlns過大或過小都會對聚類質(zhì)量造成較大影響?！稗D(zhuǎn)角”算法結(jié)果與TRACLUS類似，在minlns=28時達到最優(yōu)，總體呈“倒U型”，但聚類質(zhì)量低于TRACLUS。使用本文算法進行聚類，聚類質(zhì)量值從minlns=25開始持續(xù)下降，在minlns=29時達到最優(yōu)，因為同時考慮了空間及時間相似性，所以聚類質(zhì)量總體較高。

圖8 颶風(fēng)數(shù)據(jù)聚類質(zhì)量圖(w=0.7)

圖9 ELK93數(shù)據(jù)聚類質(zhì)量圖(w=0.5)

以ELK93 為例，同樣使用文獻[3]中TRACLUS算法以及本文提出改進聚類算法進行比較，比對結(jié)果如圖10所示，其中(a)為使用TRACLUS算法進行聚類得到聚類簇代表軌跡，(b)為應(yīng)用本文改進算法得到的聚類結(jié)果，從圖中可以看出使用TRACLUS算法在只考慮空間相似性的情況下，生成聚類簇相比本文算法較大，簇內(nèi)密度小。觀察圖10(a)最下方的一條聚類簇代表軌跡，相應(yīng)本文算法將之生成為三個相對較小聚類簇，說明本文在同時度量軌跡數(shù)據(jù)時空相似性的情況下，生成聚類簇更加精細，更有使用價值。

圖10 ELK93聚類結(jié)果對比

4 結(jié)語

對軌跡進行劃分再聚類的方法能夠很好地發(fā)現(xiàn)存在于復(fù)雜時空軌跡中的局部相似性，然而其聚類結(jié)果對子軌跡段劃分質(zhì)量具有很強的依賴性，而軌跡特征點是影響子軌跡段劃分質(zhì)量的關(guān)鍵因素， 同時相似性度量也對聚類結(jié)果具有重要影響。針對相似性度量中忽略時間特征的問題，提出了一種基于時空特征的軌跡數(shù)據(jù)聚類方法。該方法借鑒圖像算法中曲線邊緣信息的檢測方法，通過計算軌跡上某一點與該點相鄰軌跡段的變化趨勢來判定該點是否為軌跡的特征點。實驗表明使用該方法所提取的特征點具有較高的簡潔性，并且根據(jù)特征點生成的子軌跡段集能夠準確地描述軌跡結(jié)構(gòu)，降低了軌跡劃分對聚類質(zhì)量的影響。在對子軌跡段集進行聚類的過程中，兼顧軌跡的空間與時間特征，并通過設(shè)置權(quán)重調(diào)整時空特征敏感度，實驗表明基于時空模式的軌跡數(shù)據(jù)聚類方法能夠發(fā)現(xiàn)移動對象內(nèi)在結(jié)構(gòu)及其動態(tài)規(guī)律。接下來的工作是進一步提高聚類效率。

)

[1]PANJ,JIANGQ,SHAOZ.Trajectoryclusteringbysamplinganddensity[J].MarineTechnologySocietyJournal, 2014, 48(6): 74-85.

[2]HUNGCC,PENGWC,LEEWC.Clusteringandaggregatingcluesoftrajectoriesforminingtrajectorypatternsandroutes[J].TheVLDBJournal, 2015, 24(2): 169-192.

[3]LEEJG,HANJ,WHANGKY.Trajectoryclustering:apartition-and-groupframework[EB/OL]. [2015- 01- 13].http://xueshu.baidu.com/s?wd=paperuri%3A%287e5e7260674abe825b7a245c93edbb10%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D6CE1053AAA540B0B1F600FE0C866E986%3Fdoi%3D10.1.1.76.8098%26rep%3Drep1%26type%3Dpdf&ie=utf-8&sc_us=17938122568389976672.

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

[5] 杜國紅,徐克虎,杜濤.平面非規(guī)則曲線的一種快速識別與匹配算法[J].計算機工程與應(yīng)用,2007,43(7):81-83.(DUGH,XUKH,DUT.Quickrecognizingandmatchingalgorithmforplanarirregularcurve[J].ComputerEngineeringandApplications, 2007, 43(7): 81-83.)

[6]CHENJ,LEUNGMK,GAOY.NoisylogorecognitionusinglinesegmentHausdorffdistance[J].PatternRecognition, 2003, 36(4): 943-955.

[7]BOLLENJ,PEPEA,MAOH.Modelingpublicmoodandemotion:Twittersentimentandsocio-economicphenomena[J].ComputerScience, 2009, 44(12): 2365-2370.

[8] 劉琴,王愷樂,饒衛(wèi)雄.不等長時間序列滑窗STS距離聚類算法[J].計算機科學(xué)與探索,2015,9(11):1301-1313.(LIUQ,WANGKL,RAOWX.Non-equaltimeseriesdataclusteringalgorithmwithslidingwindowSTSdistance[J].JournalofFrontiersofComputerScienceandTechnology, 2015, 9(11): 1302-1313.)

[9] 張延玲,劉金鵬,姜保慶.移動對象子軌跡段分割與聚類算法[J].計算機工程與應(yīng)用,2009,45(10):65-68.(ZHANGYL,LIUJP,JIANGBQ.Partitionandclusteringforsub-trajectoriesofmovingobjects[J].ComputerEngineeringandApplications, 2009, 45(10): 65-68.)

[10]ESTERM,KRIEGELHP,SANDERJ,etal.Adensity-basedalgorithmfordiscoveringclustersinlargespatialdatabasewithnoise[C]//Proceedingsofthe2ndInternationalConferenceonKnowledgeDiscoveryandDataMining.MenloPark:AAAIPress, 1996: 226-231.

[11] GUDMUNDSSON J, VALLADARES N. A GPU approach to subtrajectory clustering using the Fréchet distance [J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(4): 924-937.

[12] 廖律超,蔣新華,鄒復(fù)民,等.一種支持軌跡大數(shù)據(jù)潛在語義相關(guān)性挖掘的譜聚類方法[J]. 電子學(xué)報,2015,43(5):956-964.(LIAO L C, JIANG X H, ZOU F M, et al. A spectral clustering method for big trajectory data mining with latent semantic correlation [J]. Acta Electronica Sinica, 2015,43(5):956-964.)

[13] 龔璽,裴韜,孫嘉,等.時空軌跡聚類方法研究進展[J].地理科學(xué)進展,2011,30(5):522-534.(GONG X, PEI T, SUN J, et al. Review of the research progresses in trajectory clustering methods [J]. Progress in Geography, 2011, 30(5): 522-534.)

[14] ELNEKAVE S, LAST M, MAIMON O. Incremental clustering of mobile objects [C]// Proceedings of the 2007 ACM SIGMOD InternationalConference on Management of Data. New York: ACM, 2007:593-604.

[15] YUAN G, SUN P, ZHAO J, et al. A review of moving object trajectory clustering algorithms [EB/OL]. [2015- 01- 09]. https://www.researchgate.net/publication/299434359_A_review_of_moving_object_trajectory_clustering_algorithms.

This work was partially supported by Natural Science Foundation of Hebei Province (F2016202144), the Science and Technology Research Project of Colleges and Universities in Hebei Province(ZD2014030), the Tianjin Research Project of Application Foundation and Advanced Technology (14JCZD JC31600).

SHI Lukui, born in 1974, Ph. D., professor. His research interests include machine learning, data mining.

ZHANG Yanru, born in 1990, M. S. candidate. Her research interests include machine learning, data mining.

ZHANG Xin, born in 1992,M.S.candidate.Her research interests include machine learning, data mining.

Trajectory data clustering algorithm based on spatio-temporal pattern

SHI Lukui1,2*, ZHANG Yanru1, ZHANG Xin1

(1.SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China；
2.HebeiProvinceKeyLaboratoryofBigDataCalculation(HebeiUniversityofTechnology),Tianjin300401,China)

Because the existing trajectory clustering algorithms in the similarity measurement usually used the spatial characteristics as the standards the characteristics lacking the consideration of temporal, a trajectory data clustering algorithm based on spatial-temporal pattern was proposed. The proposed algorithm was based on partition-and-group framework. Firstly, the trajectory feature points were extracted by using the curve edge detection method. Then the sub-trajectory segments were divided according to the trajectory feature points. Finally, the clustering algorithm based on density was used according to the spatio-temporal similarity between sub-trajectory segments. The experimental results show that the trajectory feature points extracted using the proposed algorithm are more accurate to describe the trajectory structure under the premise that the feature points have better simplicity. At the same time, the similarity measurement based on spatio-temporal feature obtains better clustering result by taking into account both spatial and temporal characteristics of trajectory.

spatio-temporal pattern; trajectory data; curve edge detection; similarity measurement; density based clustering

2016- 07- 21;

2016- 09- 12。

天津市應(yīng)用基礎(chǔ)與前沿技術(shù)研究計劃項目(14JCZDJC31600);河北省自然科學(xué)基金專項(F2016202144 )；河北省高等學(xué)校科學(xué)技術(shù)研究項目(ZD2014030)。

石陸魁(1974—)，男，河北邯鄲人，教授，博士，CCF會員，主要研究方向：機器學(xué)習(xí)、數(shù)據(jù)挖掘； 張延茹(1990—)，女，河北張家口人，碩士研究生，主要研究方向：機器學(xué)習(xí)、數(shù)據(jù)挖掘； 張欣(1992—)，女，河北衡水人，碩士研究生，主要研究方向：機器學(xué)習(xí)、數(shù)據(jù)挖掘。

1001- 9081(2017)03- 0854- 06

10.11772/j.issn.1001- 9081.2017.03.854

TP181

A