李建江 陳 瑋 李 明 張 凱 劉雅俊

1(北京科技大學(xué)計算機科學(xué)與技術(shù)系 北京 100083) 2(中國科學(xué)院電子學(xué)研究所 北京 100190) (willchen.ustb@gmail.com)

對移動目標(biāo)歷史軌跡數(shù)據(jù)的挖掘已成為目前研究的熱點之一，其應(yīng)用涉及到氣象監(jiān)測、交通流量控制、智能導(dǎo)航、犯罪行為檢測等多個領(lǐng)域.然而，受特定背景、技術(shù)設(shè)備和人為等因素的影響，軌跡數(shù)據(jù)常常具有傾斜的分布，再加之先驗知識不足，從而導(dǎo)致算法不穩(wěn)定、可擴展性差.

移動目標(biāo)不僅僅局限于人類自身，海運大數(shù)據(jù)給海事領(lǐng)域提供了可供挖掘的海量信息.利用這些信息分析船舶的運行規(guī)律不僅可以提高海運管理水平，還對航海安全有指導(dǎo)性的意義.船舶自動識別系統(tǒng)(automatic identification system, AIS)是一種數(shù)字輔助導(dǎo)航系統(tǒng)，它由相關(guān)硬件(包括船載設(shè)備、岸基設(shè)施等)和軟件(涉及網(wǎng)絡(luò)、現(xiàn)代通信、計算機、電子信息等技術(shù))組成.隨著無線通信、GPS(global positioning system)等相關(guān)技術(shù)的發(fā)展，海上AIS數(shù)據(jù)被用于規(guī)律路徑提取，這對預(yù)測與理解移動目標(biāo)活動的行為具有重要的意義.為此，本文借助網(wǎng)格方法對海量軌跡數(shù)據(jù)進行壓縮，從而提出了基于密度度量方式“熱度因子”的規(guī)律路徑提取算法，為管理部門提供管理依據(jù)，有效地改善和提升管理者的決策水平.

1 相關(guān)工作

目前，挖掘移動目標(biāo)軌跡已成為研究熱點之一.GPS和移動設(shè)備的發(fā)展為用戶行為習(xí)慣的挖掘提供了獨特的機會[1].給定源和目的地可以分析個人頻繁經(jīng)過的軌跡并尋找個性化路線[2]，根據(jù)位置驅(qū)動來分析人們的日常規(guī)律，從而發(fā)現(xiàn)熱點地區(qū)[3].由于用戶頻繁經(jīng)過的地方很可能是其感興趣的空間，而分析用戶頻繁經(jīng)過的地區(qū)又可以發(fā)現(xiàn)用戶之間的相似度[4]，這對于旅游推薦[5-6]等系統(tǒng)意義重大.人類軌跡的挖掘不僅對交通[7]、旅游、商業(yè)等有巨大幫助，還可用于檢測一些異常行為[8].

目前，有很多方法可被用于分析移動目標(biāo)的軌跡，比如基于圖的聚類分析[9]、基于貝葉斯模型、Markov模型以及時間序列的軌跡分析[10]，這些方法大都基于監(jiān)督學(xué)習(xí)來推斷人們的移動規(guī)律[11]，需要設(shè)定目標(biāo)移動的模式或形狀[12]，然后通過擬合外推出符合特定模式的軌跡[13].實際上，由于數(shù)據(jù)分布的不均勻以及溝通成本等現(xiàn)實問題，很難有足夠的經(jīng)驗作為已知條件,并且現(xiàn)有的軌跡聚類方法很難將時間和空間位置信息進行有效結(jié)合，比如文獻[14]給出了一種“劃分-聚合”的TRACLUS軌跡聚類方法，該方法先將軌跡劃分為一系列子軌跡，然后使用線段密度聚類方法再聚合成完整軌跡.但是，該方法沒有考慮到軌跡數(shù)量的爆發(fā)式增長，可擴展性較差.文獻[15]中使用網(wǎng)格方法來尋找城區(qū)中的熱點區(qū)域，但需要給定初始閾值去篩選高密度網(wǎng)格，而且沒有考慮到網(wǎng)格粒度的影響，所以其擴展性和適用性尚無法讓人滿意.由于移動目標(biāo)的軌跡一般是由駕駛?cè)说闹饔^意愿和路網(wǎng)客觀約束的結(jié)果，這種不確定性使得挖掘軌跡中的頻繁模式顯得尤為重要，而在這些頻繁模式中規(guī)律路徑又是海路交通中的一個重要特征[16-17].例如借助聚類和中心線擬合等路網(wǎng)提取方法從車輛的GPS軌跡中挖掘城市主干路網(wǎng)[18]，在文獻[19]中用一種投影的方法來提取這種長時間、可共享的路徑，有效地避免了子路線指數(shù)般的生成.在路網(wǎng)交通軌跡分析中，不僅要考慮軌跡運動的幾何信息，還要結(jié)合交通語義信息來確定道路交通類型，并根據(jù)變化類型進行增量信息融合[20].以上這些方法對于抗震救災(zāi)、導(dǎo)航定位等場合都非常重要.

船舶的航線分析和規(guī)劃是現(xiàn)代海上交通管理系統(tǒng)必不可少的內(nèi)容，Venskus等人[21]用一種自適應(yīng)算法檢測海洋交通中任何非標(biāo)準(zhǔn)的運動；Junghans等人[22]預(yù)測了目標(biāo)運動區(qū)域內(nèi)的軌跡以及該區(qū)域內(nèi)的空間范圍和方向，并利用線性回歸方法確定區(qū)域內(nèi)的目標(biāo)運動模式；也有學(xué)者用貝葉斯模型[23]來構(gòu)建一組關(guān)鍵路徑作為支撐路徑[24]，能發(fā)現(xiàn)與該路徑具有相似模式的所有路徑.由于與基于密度的簇有著緊密關(guān)系，聚類算法可找出任意形狀的簇，因此被廣泛應(yīng)用于目標(biāo)軌跡的預(yù)測模型[25].

上述方法考慮了移動目標(biāo)的某一特定模式的分析，但無法發(fā)現(xiàn)不同目標(biāo)、不同形狀的軌跡，而且可擴展性欠佳，無法適用于爆發(fā)式增長的海量軌跡數(shù)據(jù).本文提出基于網(wǎng)格熱度值的規(guī)律路徑提取算法，該算法在壓縮大量軌跡數(shù)據(jù)的同時又保持了軌跡的原有形狀和密度信息，能有效地發(fā)現(xiàn)不同形狀的規(guī)律路徑.

2 數(shù)據(jù)準(zhǔn)備和基本定義

先前關(guān)于路徑挖掘的研究大多基于模式分類，此類方法的精確度完全依賴于其支撐路徑的定義，效率不高且可擴展性較差.利用距離與密度，基于網(wǎng)格熱度值的聚類算法可找出任意形狀的軌跡簇，而且其效率也很高[26].圖1給出了本文中目標(biāo)規(guī)律路徑提取的具體框架，可實現(xiàn)從給定目標(biāo)的大量歷史信息中提取出規(guī)律路徑.

Fig. 1 The frame of rule path extraction based on the grids圖1 基于網(wǎng)格的規(guī)律路徑提取框架圖

2.1 數(shù)據(jù)準(zhǔn)備

移動目標(biāo)的歷史軌跡表示為空間上連續(xù)運動的位置點的集合，為了挖掘出海上移動目標(biāo)的運動模式，本文采用AIS船舶數(shù)據(jù)來具體分析.不同于地面上移動目標(biāo)的運動模式，船舶在水上的運動特征表現(xiàn)為靈活性差、速度較低、轉(zhuǎn)向幅度較平緩、航行時空跨度大等特征，因此船舶的軌跡在空間位置上表現(xiàn)為光滑、時空跨度大的曲線集合.這里，定義R={P1，P2，…，Pi，Pi+1，…，Pnum}為在某個時間段內(nèi)移動目標(biāo)對應(yīng)的軌跡點集合，其中，Pi=pi，ti表示移動目標(biāo)對象在時刻ti經(jīng)過的位置pi=(xi，yi).表1給出了部分AIS原始數(shù)據(jù)中目標(biāo)的軌跡信息.

Table 1 The Data Points Set of AIS表1 AIS原始數(shù)據(jù)點集

2.2 網(wǎng)格映射

由于網(wǎng)格能將空間高維數(shù)據(jù)離散化，突破維數(shù)災(zāi)難[27]，同時有效克服“距離”障礙，并且能配合有效的密度聚類算法隔離“噪聲”.在本文中，網(wǎng)格粒度scale由網(wǎng)格劃分層次l表示：

scale=360°×2-l,

(1)

式(1)表示將360°劃分為2l份.其中，單位網(wǎng)格對應(yīng)的角度用scale來表示，當(dāng)前網(wǎng)格粒度的劃分層次用l來表示.為了方便計算和理解，將經(jīng)緯度映射到直角坐標(biāo)系中，其轉(zhuǎn)換公式為

(2)

其中，x與y為第l層網(wǎng)格gxy的坐標(biāo)，lon和lat分別為經(jīng)緯度.為了盡可能在壓縮數(shù)據(jù)量的同時又不丟失數(shù)據(jù)，本文給出了網(wǎng)格“熱度值”的定義.其中，“熱度值”指軌跡點落在一個網(wǎng)格的次數(shù)或頻率，Vg表示為網(wǎng)格gxy的“熱度值”，其計算方法為

(3)

Fig. 2 Original trace points and grid maps圖2 原始軌跡點和網(wǎng)格映射圖

其中，g=gxy表示當(dāng)前網(wǎng)格；(x，y)′為軌跡點pi映射后的網(wǎng)格坐標(biāo)；N為所有的軌跡點數(shù)；vi為一個二進制變量，其值等于1時表示點pi落到g內(nèi)，其值等于0時表示沒有落到該網(wǎng)格內(nèi).因此，利用式(1)與式(2)，可以將給定的軌跡點映射至某個網(wǎng)格中.

如圖2所示，左邊的一系列軌跡點經(jīng)過映射得到右邊的網(wǎng)格點，其網(wǎng)格熱度值V3,4=7，V3,3=2，V3,1=0，….因此，可記單個網(wǎng)格為Gi=gi,Vi，其中，gi表示網(wǎng)格的位置，Vi表示該網(wǎng)格的“熱度值”，該“熱度值”不僅蘊含了目標(biāo)的“規(guī)律”信息，還在不丟失數(shù)據(jù)的前提下涵蓋了密度信息，最重要的是能壓縮大量的軌跡數(shù)據(jù)，提高效率.

2.3 方向定義

關(guān)于路徑提取的研究，如基于網(wǎng)格的規(guī)律路徑提取、基于圖像邊緣檢測的路徑提取[28]等研究，通過構(gòu)造方向矩陣來判斷路徑的方向.方向矩陣通過對1個網(wǎng)格的所有鄰居做標(biāo)記來指示方向信息，該方法設(shè)計簡單且易于實現(xiàn)，同時也帶來了巨額的內(nèi)存開銷，而且對數(shù)據(jù)準(zhǔn)確性依賴較高，抗干擾能力弱.因此，僅僅依靠鄰居網(wǎng)格是無法正確判斷路徑方向的.此外，目標(biāo)軌跡點與路徑之間的關(guān)系還需要滿足3個條件：

1) 一條路徑上的軌跡點具有分布均勻、密度高、連續(xù)性好的特點；

2) 一組有序的軌跡點構(gòu)成的路徑應(yīng)該是分段光滑、跨區(qū)域的，小短線不能作為路徑；

3) 路徑可以是開放的，也可以是閉合的，即路徑的形狀不一.

Fig. 3 Eight directions in the square圖3 方形領(lǐng)域內(nèi)8個方向示意圖

根據(jù)軌跡點與路徑之間的上述關(guān)系，針對的求解可得2個約束條件：

2) 在λ搜索到的一組光滑路徑中，其全局平均誤差不能超過δ2.

max(eg)≤δ1,g∈SN，

(4)

(5)

(6)

在本文中，λ的初始值可取初始網(wǎng)格劃分層數(shù)l0，記為λ0.而l0的值可由原始軌跡點的經(jīng)緯跨度來估算.定義第li層網(wǎng)格粒度下對應(yīng)的滑動窗口步長為λi，且λi=k×λ0.則有：

(7)

(8)

(9)

由式(9)可知，其在第1象限內(nèi)是單調(diào)遞減函數(shù)，2△l與步長的增大倍數(shù)k之間存在最優(yōu)解，而網(wǎng)格的層數(shù)l與軌跡精度密切相關(guān).因此，給定1個網(wǎng)格劃分l就可大致確定λ的取值，相應(yīng)的誤差也將得以估計；相反，給定誤差值約束，則λ的范圍也能大致估算出來.

2.4 相關(guān)性度量方式

空間自相關(guān)理論認為，空間位置鄰近對象間的相關(guān)性要遠遠大于疏遠的對象間的相關(guān)性，而且距離越近，相互關(guān)聯(lián)的程度就越高.本文的路徑提取算法使用基于局部熱度因子來確定路徑的方向，這里的熱度因子不僅表示軌跡點的密度，還表示了其空間分布上的聚集程度.本文在由給定參數(shù)λ所確定的鄰域中，不指定固定的密度和鄰近閾值，而是結(jié)合密度、熱度值和鄰近關(guān)系來確定路徑的方向信息.

局部熱度因子表示為

(10)

其中,rdk(g←g′)為第k個方向上網(wǎng)格g′到當(dāng)前網(wǎng)格g的相對距離，該相對距離表示從g′到g所經(jīng)過的最少網(wǎng)格數(shù).為了更加精確地表示在某個方向上網(wǎng)格點的緊密程度，引入Tdk=2-q，0

(11)

Fig. 4 The schematic of the heat factor 圖4 熱度因子影響解析示意圖

判斷完方向后，根據(jù)相對距離，按由小到大的順序，將該方向的網(wǎng)格依次添加到對應(yīng)路徑棧中.當(dāng)相對距離相等時，熱度值大的優(yōu)先入棧，直到該方向的所有網(wǎng)格都入棧.例如當(dāng)前的路徑軌跡點序列為Ri={3,1,2,1,1,1,1,2,4,5,4}，則下一個窗口的中心點選為最后入棧的網(wǎng)格，如圖5所示：

Fig. 5 The schematic of the heat factor 圖5 熱度因子影響解析示意圖

使用上述方法，依次向前滑動，直到該窗口內(nèi)搜索不到任何點，則一條完整的路徑搜索結(jié)束，如圖6所示，當(dāng)前路徑序列為Ri={3,1,2,1,1,1,1,2,4,5,4,4,8,3,6,4,2,1,2,2,1}.很明顯，上述搜索方法是一種在局部最優(yōu)方向提取路徑的貪婪算法.前面已討論λ的求解能將局部最大誤差和全局平均誤差控制在某個范圍內(nèi).所以，這種在局部最優(yōu)方向提取路徑的貪婪算法可在全局范圍內(nèi)得到不錯的路徑序列.

Fig. 6 The schematic of the heat factor 圖6 熱度因子影響解析示意圖

3 規(guī)律路徑提取算法

3.1 起始點篩選

先從所有軌跡點中篩選出“起始點”，也就是一條路徑的起始位置，這不僅能提高路徑提取的準(zhǔn)確性，也能減少路徑提取的效率.首先，對“起始點”做3點定義：

1) 最邊界點作為起始點的優(yōu)先級最高；

2) 從“起始點”出發(fā)，只在單一方向上有路徑，即在多個方向上有路徑的點不作為起始點；

3) 熱度區(qū)也可以作為“起始點”.

這里的“起始點”不僅指單個網(wǎng)格，而應(yīng)該是一系列符合起始點定義的網(wǎng)格集合.為了簡單起見，可從起始點集合中選取熱度值最大的中心點作為“代表”.一條軌跡的起始點可被定義為S(g,c)，其中，g為該起始點對應(yīng)的網(wǎng)格集合的“中心點”，c表示起始點包含的網(wǎng)格數(shù)目.在一些分布規(guī)律性不強的軌跡點中，起始點的初始集合很可能為空，但這并不會影響路徑提取的效果.在分布較為規(guī)律的軌跡中，對起始點的初始集合的篩選在很大程度上能夠提高算法效率和精度.

3.2 規(guī)律路徑提取算法

算法1. 基于網(wǎng)格熱度值的規(guī)律路徑提取算法(RPEH).

輸入：一組無序網(wǎng)格點集合R={g1,g2,…,gnum}、閾值λ；

① For eachgiinR

②Visit(gi)←False；

③ End For

④InitStack(s)；

⑤ For eachgiinR

⑥ IfVisit(gi) is False then

⑦Push(s,gi)；

⑧g←Pop(s)；

⑨ADJs et=JudgeDirection(g)；

⑩ IfADJs etis Null then

在算法1中，步驟①～④初始化原始網(wǎng)格和棧；在步驟⑤～⑦中依次取出一個點來判斷其是否被訪問過，如果沒有被訪問則將其入棧；步驟⑧⑨中，將棧頂元素取出，并計算λ確定的范圍內(nèi)的方向.JudgeDirection(g)是計算g周圍8個方向的熱度因子并比較其大小，然后選擇熱度因子影響最高的一個方向，并按照相對距離從小到大、熱度值從大到小的順序?qū)⒃摲较蛏纤芯W(wǎng)格存入ADJs et中;步驟⑩，當(dāng)ADJs et=?時，說明t周圍的8個方向上已無可訪問網(wǎng)格.此時，按從底到頂?shù)捻樞驅(qū)中的點依次輸出，構(gòu)成一條規(guī)律路徑.接著返回到步驟⑤，以下一個網(wǎng)格為起點開始搜索;在步驟～中，當(dāng)ADJs et≠?時，依次將ADJs et的點入棧，并將每個點的訪問狀態(tài)標(biāo)記為True，接下來跳轉(zhuǎn)到步驟⑧繼續(xù)進行遞歸搜索，一直到搜索不到為止;在步驟中，當(dāng)所有的網(wǎng)格都被搜索過一遍后，該算法結(jié)束，并返回n條路徑

3.3 異常點去除

大量實踐發(fā)現(xiàn)，對于大部分移動對象來說，其運動路徑都不會出現(xiàn)明顯的棱角，在平直的道路上也不可能完全沿著直線運動;相反，往往受障礙物或其他對象的干擾而沿曲線運動.道格拉斯-普克曲線能使用較少的點保持曲線基本形狀和趨勢.該曲線給定閾值后可有效去除多余的點，并保留曲線的基本形態(tài).一條移動目標(biāo)的軌跡應(yīng)該是分段光滑的.

本文通過設(shè)置局部的曲率閾值來去除路徑上的異常點.除了路徑的首末2個點，中間依次鄰接的3個點形成一個夾角θ.當(dāng)其值小于閾值α?xí)r，則刪除3個點中位于中間的那個點.依次計算，直到刪除該曲線所有的“尖角”點以形成一條較為光滑的曲線.如圖7所示，該方法可有效去除路徑中的“尖角”.

Fig. 7 The process of exception handling圖7 異常點處理示意圖

插值在圖像處理領(lǐng)域應(yīng)用廣泛，可有效消除軌跡中較為明顯的“鋸齒”現(xiàn)象. 三次樣條是其中使用較為廣泛的一種. 但是，當(dāng)被插值點為稀疏分布時，該插值方法將帶來比較大的誤差.為了彌補該缺點，本文先使用貝塞爾曲線將插值點增多并保存軌跡原有的局部彎曲特性，然后利用樣條插值方法對整體進行擬合，最終使路徑提取的準(zhǔn)確性得以提高.算法2給出了對RPEH算法提取出的路徑進行異常點去除和光滑處理的過程.

算法2. 異常點去除和光滑處理算法(BAS).

輸入：一條有序路徑Ri={g1,g2,…,gm}、光滑度α；

① Fori←1 tom

② Doθ←Angle(gi-1,gi,gi+1)

③ Ifθ<αthen

④Remove(gi)；

⑤i←i-1；

⑥ End If

⑦ End For

其中，步驟①～⑦去除搜索到的路徑序列中的異常點；步驟⑧使用二階貝塞爾曲線，對去除異常點后的路徑序列中連續(xù)3點形成的夾角小于一定閾值的“尖角”來進行光滑處理；為實現(xiàn)對軌跡的整體擬合，步驟⑨使用了三次樣條插值方法.其中，根據(jù)距離來估算三次樣條的擬合采樣點數(shù)，在該算法中設(shè)定至少需要20個采樣點.

4 實驗與結(jié)果

本節(jié)將主要從算法的準(zhǔn)確性、可擴展性和性能這3個方面進行測試，并使用海上交通AIS數(shù)據(jù)[29]來驗證該算法的有效性.

4.1 評價指標(biāo)

不同的聚類算法目標(biāo)函數(shù)相差很大，有基于距離的，有基于圖聚類和譜分析性質(zhì)的，還有些是基于密度等.因此，還沒有統(tǒng)一的標(biāo)準(zhǔn)進行聚類的評價，而應(yīng)根據(jù)具體應(yīng)用來具體分析.針對AIS數(shù)據(jù)的實際特點，本文使用2種方法對提出的基于網(wǎng)格熱度值的規(guī)律路徑聚類分析算法的聚類效果進行評價.

1) 外部方法.鑒于經(jīng)緯度位置信息的優(yōu)點，將每條路徑通過可視化的方法展示出來以便進行評價.該評價方法具有簡便、直觀的特點.

2) 內(nèi)部方法.路徑的聚類效果可根據(jù)軌跡的內(nèi)部信息來評價.為具體評價聚類效果，本文使用如下3種度量方式：

為所有點的平均分離度.該值越大，則軌跡簇間的分離效果越好;反之，則越差.定義TS=TRSR為評價軌跡簇聚類效果的指標(biāo)，該值越接近0說明效果越好，而當(dāng)值大于等于1時說明聚類效果較差.

③ 異常點分離度.當(dāng)軌跡簇數(shù)為1時，SR不再適用.為了更好地評價1條軌跡的聚類效果，可用該軌跡上的異常點分離度SP來替代SR.

4.2 數(shù)據(jù)集

表2給出了測試所用運行環(huán)境的相關(guān)配置情況，表3給出了測試的AIS數(shù)據(jù)集的類型和大小.AIS數(shù)據(jù)不僅包括如船號、類型這樣的靜態(tài)數(shù)據(jù)，還包括類似經(jīng)緯度和時間這樣的動態(tài)數(shù)據(jù).此外AIS數(shù)據(jù)還具有精度高、丟失數(shù)據(jù)少的特點.因此，根據(jù)船舶的具體情況和測量經(jīng)驗，網(wǎng)格層數(shù)l取值范圍為 [9,16].

Table 2 The Configuration of the Running Environment表2 測試所用運行環(huán)境的配置情況

Table 3 Test Data Set表3 測試數(shù)據(jù)集

Fig. 8 The diagram of the relationship between l and α圖8 網(wǎng)格劃分層數(shù)l與異常點去除閾值α關(guān)系圖

針對上述5種典型目標(biāo)，實際測得的網(wǎng)格層數(shù)l與閾值α折線圖如圖8所示.從圖8可以看出，在網(wǎng)格劃分粒度不同的情況下，這5種類型目標(biāo)的變化不是很劇烈，即說明α的值對軌跡的精度影響并不大，且網(wǎng)格層數(shù)在9 ～ 16之間時，α取值范圍在[0.5,2].可取α初始值為1，然后迭代尋找其最優(yōu)值.圖9給出α=1時，層數(shù)l與λ的關(guān)系柱狀圖.從圖9可以看出，每當(dāng)層數(shù)l增加1，λ會增大2倍左右.綜上所述，當(dāng)選取某個初始網(wǎng)格劃分粒度，例如l0=11之后，則取λ0=11，α0=1.要提取某個目標(biāo)軌跡的路徑，可通過輪換變量法依次求解l，λ，α這3個變量的最優(yōu)值.

Fig. 9 The diagram of the relationship between l and λ圖9 網(wǎng)格劃分層數(shù)l與λ關(guān)系圖

4.3 聚類效果評價

本文選取5種不同類型船舶，根據(jù)提出的基于網(wǎng)格熱度值的規(guī)律路徑聚類分析算法，計算出其軌跡，并與實際的目標(biāo)軌跡進行比較，結(jié)果如圖10所示.從圖10可以清晰地看出，這5種類型船舶的航行路線基本符合它們的活動路線.

Fig. 10 The visual figure of target track圖10 目標(biāo)軌跡航線可視化圖

表4給出了5個目標(biāo)軌跡簇的緊湊度和分離度的統(tǒng)計結(jié)果.可以看出，Target4的TS值最大，說明其聚類效果最差，這符合Target4的實際軌跡最為復(fù)雜這一真實情況，但其他幾個目標(biāo)的聚類效果較好.對于目標(biāo)軌跡復(fù)雜的情況，我們會在后面的研究中做進一步的介紹.

Table 4 The Evaluation Results of Cluster表4 聚類評價結(jié)果

圖11給出了本文提出并實現(xiàn)的REPH算法與常用的TRACLUS[14]算法之間聚類效果的對比情況.可以看出，除了Target4之外，REPH算法比TRACLUS算法的TS都要小，說明當(dāng)目標(biāo)軌跡比較規(guī)律時，本文提出并實現(xiàn)的REPH算法其聚類效果明顯更好.

Fig. 11 The comparison of clustering effect with RPEH and TRACLUS圖11 與TRACLUS算法的聚類效果對比圖

4.4 性能對比

本文提出并實現(xiàn)的基于網(wǎng)格熱度值的船舶規(guī)律路徑提取算法，其進行聚類分析所耗費的時間如圖12所示.從圖12可以看出，隨著原始軌跡點數(shù)目的爆發(fā)式增長，該算法所花費的時間并未急劇增加，而是以較為平緩的趨勢(圖12中的虛線)增長，其原因在于本文提出的方法在很大程度上壓縮了數(shù)據(jù)，提高了計算效率.

Fig. 12 The relationship of trace points and running time圖12 軌跡點數(shù)和運行時間關(guān)系圖

從圖12還可以看出，原始軌跡點數(shù)為184 300，396 721，1 016 728的目標(biāo)軌跡壓縮接近100%，這些目標(biāo)雖有十幾萬甚至上百萬個軌跡點，但基本上都集中在一個固定區(qū)域，這也揭示了在圖12中原始軌跡點數(shù)為184 300的目標(biāo)的計算時間反而比原始軌跡點數(shù)為3 905的目標(biāo)軌跡的計算時間短的原因.總的來說，通過數(shù)據(jù)壓縮，本文提出的算法的性能顯著提高，能夠滿足實際需要.

圖13給出了本文提出并實現(xiàn)的REPH算法與常用的TRACLUS算法之間性能的比較，從中可以看出本文提出并實現(xiàn)的REPH算法的性能明顯優(yōu)于TRACLUS算法，尤其是當(dāng)數(shù)據(jù)量較大的時候.因此，無論是從聚類效果還是從性能方面，本文提出并實現(xiàn)的基于網(wǎng)格熱度值的規(guī)律路徑提取算法REPH都有明顯的優(yōu)勢.

Fig. 13 The comparison of clustering effect with RPEH and TRACLUS圖13 與TRACLUS算法的聚類性能對比圖

5 總 結(jié)

本文提出了一種基于網(wǎng)格熱度值的船舶規(guī)律路徑提取算法，通過計算局部方形鄰域內(nèi)的熱度因子來判斷路徑的方向，并利用異常點去除和光滑處理相結(jié)合的方法，能夠有效地發(fā)現(xiàn)移動目標(biāo)不同形狀的軌跡.最后，以可視化的方式對提取出的路徑進行了直觀展示，并通過算法精度和性能測試表明了算法的可行性.實驗結(jié)果表明:與常用的TRACLUS算法相比，本文提出并實現(xiàn)的基于網(wǎng)格熱度值的船舶規(guī)律路徑提取算法具有更好的聚類效果而且性能更高.

本文提出的算法屬于無監(jiān)督的聚類分析算法，當(dāng)遇到分布稀疏且不規(guī)律的軌跡時其局部誤差可能會變大.因此，在后續(xù)的工作中，將進一步引入時間密度和時間序列來對復(fù)雜的軌跡進行處理.此外，我們還會引入基于活動圖的復(fù)雜模型來表示目標(biāo)的運動模式，這種模型不僅能識別規(guī)律的航線，還能處理復(fù)雜的船舶活動狀態(tài)和時序等信息.本文的規(guī)律路徑提取算法無論是對未來研究工作的進一步開展還是對海上船舶的行為預(yù)測都有重要意義，對海陸交通提供更有效的服務(wù)奠定了基礎(chǔ).

[1]Choujaa D, Dulay N. Predicting human behaviour from selected mobile phone data points[C] //Proc of the 12th ACM Int Conf on Ubiquitous Computing. New York: ACM, 2010: 105-108

[2]Chang Kaiping, Wei Lingyin, Yeh M Y, et al. Discovering personalized routes from trajectories[C] //Proc of the 3rd ACM SIGSPATIAL Int Workshop on Location-Based Social Networks. New York: ACM, 2011: 33-40

[3]Farrahi K, Gatica-Perez D. What did you do today?Discovering daily routines from large-scale mobile data[C] //Proc of the 16th ACM Int Conf on Multimedia. New York: ACM, 2008: 849-852

[4]Li Quannan, Zheng Yu, Xie Xing, et al. Mining user similarity based on location history[C] //Proc of the 16th ACM SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2008: Article No.34

[5]Zheng Yu, Zhang Lizhu, Xie Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C] //Proc of the 18th Int Conf on Worlid Wide Web. New York: ACM, 2009: 791-800

[6]Alivand M, Hochmair H. Extracting scenic routes from VGI data sources[C] //Proc of the 2nd ACM SIGSPATIAL Int Workshop on Crowdsourced and Volunteered Geographic Information. New York: ACM, 2013: 23-30

[7]Zheng Jiangchuan, Lionel M. An unsupervised framework for sensing individual and cluster behavior patterns from human mobile data[C] //Proc of the 2012 ACM Conf on Ubiquitous Computing. New York: ACM, 2012: 153-162

[8]Liao Lin, Patterson D J, Fox D, et al. Learning and inferring transportation routines[J]. Artificial Intelligence, 2007, 171(5/6): 311-331

[10]Huang Xin, Luo Jun, Wang Xin. Finding frequent sub-trajectories with time constraints[C] //Proc of the 2nd ACM SIGKDD Int Workshop on Urban Computing. New York: ACM, 2013: Article No.13

[11]Zheng Yu, Li Quannan, Chen Yukun, et al. Understanding mobility based on GPS data[C] //Proc of the 10th Int Conf on Ubiquitous Computing. New York: ACM, 2008: 312-321

[12]Zhang Kun, Wang Cuirong, Li Shaoheng. An automatic detection and segmentation algorithm of video multiple moving targets for computer vision[C] //Proc of the 7th Int Conf on Internet Multimedia Computing and Service. New York: ACM, 2015: Article No.48

[13]Griffin T, Huang Y, Seals S. Routing-based map matching for extracting routes from GPS trajectories[C] //Proc of the 2nd Int Conf on Computing for Geospatial Research & Applications. New York: ACM, 2011: Article No.24

[14]Lee J G, Han Jiawei, Whang K Y. Trajectory clustering: A partition-and-group framework[C] //Proc of the 2007 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2007: 593-604

[15]Hio C, Bermingham L, Cai Guochen, et al. A hybrid grid-based method for mining arbitrary regions-of-interest from trajectories[C] //Proc of Workshop on Machine Learning for Sensory Data Analysis. New York: ACM, 2013: 5-8

[16]Guo Limin,Ding Zhiming,Hu Zelin,et al. Prediction of uncertainty trajectory based on road network[J]. Journal of Computer Research and Development, 2010, 47(1): 104-112 (in Chinese)

(郭黎敏, 丁治明, 胡澤林, 等. 基于路網(wǎng)的不確定性軌跡預(yù)測[J]. 計算機研究與發(fā)展, 2010, 47(1): 104-112)

[17]He Yuanhao, Wei Haiping, Zhou Ye, et al. Algorithm for extracting regions of interest from vehicle GPS trajectory[J]. Engineering of Surveying & Mapping, 2016, 25(5): 47-51

[18]Ouyang Hong, Liu Jianxiong, Liu Yizhi, et al. An extraction method of road network based on walking GPS trajectories[J]. Computer & Modernization, 2014(2): 124-128

[19]Falvi G, Pedersen T B. Mining long, sharable patterns in trajectories of moving objects[J]. Geoinformatica, 2009, 13(1): 27-55

[20]Yang Wei,Ai Tinghua. A method for road network updating based on vehicle trajectory big data[J]. Journal of Computer Research and Development, 2016, 53(12): 2681-2693 (in Chinese)

(楊偉, 艾廷華. 基于車輛軌跡大數(shù)據(jù)的道路網(wǎng)更新方法研究[J]. 計算機研究與發(fā)展, 2016, 52(12): 2681-2693)

[21]Venskus J, Kurmis M, Andziulis A, et al. Self-learning adaptive algorithm for maritime traffic abnormal movement detection based on virtual pheromone method[C] //Proc of Int Symp on Performance Evaluation of Computer and Telecommunication Systems. Piscataway, NJ: IEEE, 2015: 1-6

[22]Junghans C, Gertz M. Modeling and prediction of moving region trajectories[C] //Proc of ACM SIGSPATIAL Int Workshop on GeoStreaming. New York: ACM, 2010: 23-30

[23]Shiga M, Mamitsuka H. Variational Bayes co-clustering with auxiliary information[C] //Proc of the 4th MultiClust Workshop on Multiple Clusterings, Multi-View Data, and Multi-Source Knowledge-Driven Clustering. New York: ACM, 2013: Article No.5

[24]Deshmukh A A, Aylett R. Exploring socially intelligent recharge behaviour for human-robot interaction[C] //Proc of the 2014 ACM/IEEE Int Conf on Human-Robot Interaction. New York: ACM, 2014: 150-151

[25]Park N H, Lee W S. Statistical grid-based clustering over data streams[J]. ACM SIGMOD Record, 2004, 33(1): 32-37

[26]Hung C C, Peng W C, Lee W C. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes[J]. The VLDB Journal, 2015, 24(2): 169-192

[27]Hinneburg A, Keim D A. Optimal grid-clustering: Towards breaking the curse of dimensionality in high-dimensional clustering[C] //Proc of the 25th Int Conf on Very Large Data Bases. San Francisco, CA: Morgan Kaufmann, 1999: 506-507

[28]Neves R F P, Zanchettin C, Mello C A B. An adaptive thresholding algorithm based on edge detection and morphological operations for document images[C] //Proc of ACM Symp on Document Engineering. New York: ACM, 2013: 107-110

[29]Cai Xinmei. AIS application and development[J]. Mechanical and Electrical Equipment, 2011, 28(2): 28-30 (in Chinese)

(蔡新梅. AIS應(yīng)用與發(fā)展[J]. 機電設(shè)備, 2011, 28(2): 28-30)