基于速度約束的軌跡劃分方法

摘要：大多數(shù)軌跡劃分算法往往只關注于軌跡的位置和運動特征，忽略了采樣時間間隔，以及移動對象本身的速度約束。針對這些問題，本文提出一種基于速度約束的軌跡劃分方法。首先，給出了考慮了速度約束的軌跡點到軌跡段域距離的定義。其次，在軌跡域中發(fā)現(xiàn)軌跡點速度范圍，并根據速度約束來確定點在軌跡段域中運動范圍投影下的點到軌跡段域距離的最小值，然后，給出基于向量的距離簡化計算方法。真實數(shù)據實驗表明，本文方法是有效的。

關鍵詞：軌跡；劃分；時間意識；速度約束

1 前言

由于當前軌跡采樣設備如GPS，RFID等生成了大規(guī)模軌跡數(shù)據，如何有效的從這些軌跡數(shù)據中提取有用信息，是目前亟需解決的問題。現(xiàn)有研究方法大多以整條軌跡作為數(shù)據處理單元，會丟失一些有價值的軌跡內部信息。因此，在軌跡數(shù)據分析過程中，先做軌跡劃分，之后進行軌跡段數(shù)據挖掘則可以避免這些。關于軌跡劃分，國內學者已經進行了大量的研究并提出了很多有效的方法，但是這些方法只著重從軌跡空間位置入手，往往忽略了時間和軌跡速度約束。

本文在速度約束的基礎上，提出了考慮速度約束的軌跡點到軌跡段域距離概念，并給出基于向量的距離簡化計算方法。計算得到軌跡點到軌跡段域距離后，劃分過程中采用自適應劃分終止閾值約束軌跡劃分。軌跡點運動范圍投影，采用軌跡點最大最小速度約束，在時間意識范圍下，得到軌跡點在方向趨勢下的運動范圍。

2 相關定義

本文中，軌跡表示為 ，，

。

2.1 時間和速度約束下的距離

定義1子軌跡：子軌跡指的是一條軌跡中若干個連續(xù)軌跡點組成的軌跡段。可以描述為如下形式：

， ，

，其中Tri為代表整條軌跡，SubTraji代表子軌跡，Pij代表軌跡點。

軌跡上針對每一點，在速度約束的基礎上，找到點在軌跡段域上的投影范圍，之后計算其到軌跡段域的距離，在最大距離點處滿足條件后劃分軌跡，下面是有關軌跡段域，以及速度約束和基于速度約束投影的概念。

定義2軌跡段域：連接軌跡SubTraj首尾兩點所成的直線，用以表示軌跡段上的點的運動情況，用Domaintraj表示。如圖1所示，直線p0pn稱之為該軌跡段Domaintraj。

圖1 軌跡段域 圖2 投影示意圖

定義3 軌跡段的最小速度、最大速度軌跡段：

，SubTraji的最小速度為軌跡上所有點的最小速度，最大速度為軌跡上所有點的最大速度：

最大速度：

本文針對劃分，定義了一種基于速度約束的軌跡點投影。

定義4基于速度約束的軌跡點投影，如圖2，pijpi(j+1)為軌跡段中相鄰的兩軌跡點，pi1piN■為軌跡段域兩端點。 、 為最大最小速度約束下pij、pi(j+1)在pi1piN■上的投影， 則、分別為點、 在最大最小速度約束下的投影。

為基于速度約束的軌跡點到投影的距離，該距離滿足以下條件。

2.2 點到軌跡段域距離計算方法

定義5點到軌跡段域距離：

假設軌跡段終點連線直線段上每一點的軌跡速度均在軌跡段最小速度和最大速度之間，則取軌跡點到運動范圍投影最小距離作為點到軌跡段域距離，設為 。

定義6軌跡段特征點：

軌跡段上，到軌跡段域距離最大點，稱之為軌跡段特征點，在該點處如果滿足劃分閾值約束，則劃分軌跡段為兩段，該點表示為Pointc。

3 基于時間和速度約束的軌跡劃分

本文以相同時間間隔為前提，根據點到軌跡段域距離進行軌跡劃分。

3.1 自適應性劃分閾值

本文采用二分軌跡劃分法，即軌跡段域在遍歷軌跡點到軌跡段域距離后，發(fā)現(xiàn)軌跡段特征點，并在此點處將軌跡段一分為二，之后對劃分的兩條軌跡段分別再次遍歷計算以及劃分。計算點到軌跡段域距離時，得到平均點到軌跡段域距離，并引入參數(shù)k作為劃分閾值調節(jié)參數(shù)，本文提出自適應性劃分閾值，用ε表示。

定義7自適應性劃分閾值ε該值大小取決于預劃分軌跡段的平均點到軌跡段域距離，用來判斷軌跡段是否需要繼續(xù)劃分，每次劃分需要重新計算，自適應于預劃分軌跡段的劃分終止判斷。其計算方式如下：

劃分過程中，計算得到預劃分軌跡段特征點Pointc和該軌跡段平均點到軌跡段距離后，根據k值大小，如果該特征點Pointc點處滿足>ε，則將軌跡劃分為兩段，如果不滿足則終止劃分。

定義8離群點:當軌跡段中一點超出軌跡域時，即時間差乘以軌跡段域最大速度仍達不到該點，則該點被認為是離群點。

3.2 點到軌跡段域距離算法

本文劃分算法主要依據順序遍歷點到軌跡段域距離，故點到軌跡段域距離算法對劃分影響很大。算法對原始軌跡數(shù)據生成軌跡段域，并得到該軌跡段域最大最小速度，遍歷軌跡點計算其運動范圍投影，并計算其點到軌跡段域距離。算法如下：

算法1只是劃分計算的一部分，得到軌跡關鍵點以及首次平均點到軌跡段域距離 ，在前者處劃分軌跡，后者只計算首次平均距離得到迭代劃分終止條件。遍歷計算各個點到軌跡段域距離，可以在線性時間內得到劃分結果，所以其時間復雜度為O(n)，之后

最大點處即為軌跡特征點Pointc，劃分軌跡為兩段。

3.3 基于二分法的軌跡劃分算法

該算法通過迭代的方式進行深度優(yōu)先的軌跡劃分，對劃分后的軌跡段，進行平均點到軌跡段域距離的計算，如果滿足迭代，則進行繼續(xù)劃分，否則就終止該段劃分。算法最后輸出劃分后的軌跡段集合SubTrajset。

算法2在算法1的基礎上進行深度優(yōu)先搜索，計算點到軌跡段域距離，并發(fā)現(xiàn)軌跡段特征點， 在自適應劃分閾值的約束下， 判斷軌跡是否需要劃分，如果滿足劃分條件，則劃分軌跡，之后迭代判斷子軌跡劃分情況，否則不劃分。算法最壞時間復雜度為O(n2)，即在n個點的軌跡中，每一點均為特征點滿足劃分閾值約束。這種情況適用于軌跡為鋸齒波的情形，在每一拐點均需劃分軌跡，最好時間復雜度為O(n)，首次劃分后終止劃分。平均時間復雜度為O(nlogn)。算法在時間復雜度沒有顯著上升的情況下，采用自適應劃分閾值約束，很好地適應了軌跡的不同情況。

4 實驗

為了驗證本文提出的劃分算法，我們開發(fā)了軌跡數(shù)據分析系統(tǒng)TrajMiner。該系統(tǒng)由Visual C++ 2008 開發(fā)，軌跡數(shù)據存儲在Access數(shù)據表中。本文選取真實數(shù)據集作為實驗數(shù)據：大西洋颶風數(shù)據，抽取1950~2004年的數(shù)據子集，包括由17736個采樣點組成的570條軌跡，并選取經度緯度、中心最大速率，時間等多個屬性參與實驗。

4.1 實驗一 速度約束的有效性以及誤差分析

為驗證本文劃分效果的有效性，我們進行了一組對比試驗，如圖3所示，該實驗數(shù)據取自颶風數(shù)據1980年至2009年，數(shù)據逐年遞增，自適應劃分閾值參數(shù)k=1.3，實驗對比了同一軌跡數(shù)據情況下，隨著軌跡點數(shù)的增多，軌跡總長度誤差情況。誤差為原始軌跡長度減去起始點到投影點長度。圖中藍色線為具有速度約束的劃分，紅色表示普通劃分，該速度取軌跡平均速度。

從圖3可以看出，具有速度約束的劃分，軌跡長度誤差要小很多，且隨著軌跡點數(shù)的增多，誤差增長總體上趨于線性。而普通劃分的長度誤差在同一軌跡點數(shù)情況下，比前者要大很多，雖然也趨于線性增長。

圖4展示了同一軌跡數(shù)據情況下，具有速度約束的軌跡劃分和普通劃分時間對比，實驗數(shù)據依然取自颶風數(shù)據1980年至2009年，數(shù)據逐年遞增，自適應劃分閾值參數(shù)k=1.3。圖中藍色線為具有速度約束的劃分，紅色表示普通劃分，時間單位為秒。從圖中，我們可以看出劃分耗時呈現(xiàn)曲折增長，但依然可以得到總體趨于線性增長的結果。同時可以看出，具有速度約束的軌跡劃分耗時明顯比普通劃分要小很多。實驗表明，無論在劃分誤差有效性上，還是時間復雜度上，具有速度約束的軌跡劃分比普通劃分都要好很多。

圖3 劃分誤差有效性對比圖4 劃分時間有效性對比

4.2 實驗二，參數(shù)影響的有效性分析

本實驗取大西洋颶風1950-2009年數(shù)據驗證k值大小同劃分軌跡段數(shù)目關系。具體情況如圖5所示，圖5為不同k值下，得到劃分后的子軌跡數(shù)目，驗證k值對劃分所得子軌跡數(shù)目的影響。

從圖5可以看出，本算法劃分后子軌跡段數(shù)目同k值大小的敏感區(qū)域位于k∈(1.3，2.1)中。k值在(1，1.3)范圍時，由于k值太小，所得子軌跡段數(shù)目也就越多。隨著k的增大，子軌跡段數(shù)目基本呈指數(shù)下降。

圖6對比隨著k值增大，劃分所用時間情況，即k值變化對劃分時間的影響。從圖中我們可以看出，劃分時間基本同劃分所得子軌跡數(shù)目成正比，趨勢基本一樣，表明劃分時間主要用于軌跡迭代。隨著k的不斷增大，劃分時間逐漸減小，而當達到一定k值，所有軌跡均不滿足劃分條件時，劃分時間趨近于0。本實驗同時表明，本算法時間復雜度同劃分所得子軌跡數(shù)基本呈正比。

4.3 實驗三，軌跡點數(shù)對劃分時間影響

本實驗選取自1950年到2009年颶風數(shù)據進行實驗，k=1.8，時間單位為ms，對比軌跡數(shù)目逐漸增多時，劃分耗時情況。實驗過程中，以5年為單位增加軌跡數(shù)據。如圖7所示，可以看出，隨著軌跡數(shù)目的增多，劃分時間線性增長。

5 結束語

大多數(shù)軌跡劃分算法往往只關注于軌跡的位置和運動特征，忽略了采樣時間間隔，以及其本身的速度約束，本文提出一種基于速度約束的軌跡劃分方法。首先，提出了基于速度約束的軌跡點到軌跡段域距離的概念。其次，給出了基于向量的距離簡化計算方法。最后為滿足迭代劃分適應軌跡各部分數(shù)據特性，給出了自適應劃分終止閾值。真實數(shù)據實驗表明，該算法可以高效準確的劃分軌跡。本文未來關注點為針對時間意識和速度約束下的劃分，應針特定數(shù)據發(fā)現(xiàn)更為準確的終止閾值，用于軌跡聚類。

參考文獻

[1]I.K.Cihan，H.G.Senel.Gray Level Topological Corner Detection.Proc.ISIE 2007:1727-1730

[2]S.Rasetic，J.Sander，J.Elding，and M.A.Nascimento.A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing.In Proc.of VLDB，2005.

[3]V.Athitsos，M.Hadjieleftheriou，G.Kollios，and S.Sclaroff.Query-sensitive embeddings.In SIGMOD，2005.

[4]Jae-Gil Lee，Jiawei Han，Kyu-Young Whang.Trajectory Clustering: A Partition-and-Group Framework.2007 ACM SIGMOD international conference on Management of data: 593-604.

[5]Cheng Chang，Baoyao Zhou.Multi-granularity Visualization of Trajectory Clusters Using Sub-trajectory Clustering.ICDM Workshops，2009: 577-582.

[6]M.Buchin，A.Dreimel，M.van Kreveld，V.Sacristán.An Algorithmic Framework for Segmenting Trajectories based on Spatio-Temporal Criteria.The 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2010.

[7]Aris Anagnostopoulos，Michail Vlachos，Marios Hadjieleftheriou，Eamonn J.Keogh，Philip S.Yu: Global distance-based segmentation of trajectories.KDD 2006: 34-43.

[8]Hyunjin Yoon，Cyrus Shahabi.Robust Time-Referenced Segmentation of Moving Object Trajectories.ICDM，2008:1121-1126.

[9]E.Bingham，A.Gionis，N.Haiminen，H.Hiisil¨a，H.Mannila，and E.Terzi.Segmentation and dimensionality reduction. In SIAM Data Mining Conf 2006:371-383

[10]D. Chetverikov and Z. Szabo. A simple and efficient algorithm for detection of high curvature points in planar curves. CAIP 2003: 746-753.

作者簡介：王敏芬（1977，11-），女，籍貫：江蘇宜興，學歷：本科，職稱：計算機中級，主要研究方向：政府網站制作和維護。