TELKOM
NIKA
, Vol.11, No
.1, Janua
ry 2013, pp. 115
~12
2
ISSN: 2302-4
046
115
Re
cei
v
ed Se
ptem
ber 28, 2012; Revi
se
d No
vem
ber
22, 2012; Accepted Novem
ber 30, 20
12
Using Relative Distance and Hausdorff Distance to
Mine Trajectory Clusters
Bo Gua
n
, Liangxu Liu*,
Jin
y
ang Chen
Ning
bo U
n
iver
sit
y
of T
e
chnol
og
y
Cuib
ai R
oad
8
9#, Hais
hu Dist
r
ict, Ningb
o Ch
ina, 86-
05
74-8
870
81
232
*corres
pon
di
ng
author, e-mai
l
: lurans
h@1
26.
com
A
b
st
r
a
ct
Alon
g w
i
th de
velo
p
m
ent of
locati
on servic
e and GPS t
e
chn
o
lo
gy, mi
nin
g
infor
m
ati
on fro
m
trajectory dat
a
s
ets beco
m
es
one of h
o
ttest research
top
i
c in data
mi
ni
ng. How
to efficiently
mine t
h
e
clusters fro
m
tr
ajector
i
es
attract mor
e
a
nd
more res
ear
c
her
s. In this p
a
p
e
r, a new
fra
m
e
w
ork of traject
o
r
y
clusteri
ng, call
ed T
r
ajectory
Clusteri
ng b
a
s
ed Im
prove
d
Mini
mu
m H
a
u
s
dorff Distanc
e und
er T
r
ansl
a
ti
o
n
(TraClustMHD)
is pro
pose
d
. In this fra
m
ew
o
r
k, t
he distanc
e betw
e
e
n
tw
o trajectory se
g
m
e
n
ts bas
ed
o
n
local
a
n
d
rel
a
ti
ve d
i
stanc
e is
defi
n
e
d
. An
d
then, tra
d
itio
na
l cl
usters a
l
g
o
r
i
thm is
e
m
p
l
oy
ed to
mi
ne t
h
e
clusters of trajectory se
g
m
ent. In additi
ona
l, R-
T
r
ee is employ
ed to improve th
e efficiency. T
h
e
exper
imenta
l
r
e
sults sh
ow
ed
that our
al
gorit
hm better th
an
existin
g
oth
e
r
s
w
h
ich ar
e b
a
s
ed o
n
H
aus
d
o
rff
distanc
e an
d b
a
sed o
n
li
ne H
ausd
o
rff distan
ce.
Key
w
ords
: trajecto
ry
clu
s
tering, m
o
vem
ent pattern
s, hau
sdo
r
ff distance
Copyrig
h
t
©
2013
Univer
sitas Ahmad
Dahlan. All rights res
e
rv
ed.
1. Introduc
tion
Along with th
e developm
e
n
t of GPS and Location Service, mo
re
and mo
re lo
cation data
are
colle
cted
in appli
c
ati
on serve
r
s,
su
ch a
s
,
tra
ffic cont
rol,
weath
e
r m
o
nitor, intellig
ent
navigation, bi
omedi
cine, b
u
sin
e
ss de
ci
sion
s and
an
ti-terro
ri
sm.
Ho
w to
mine
inform
ation f
r
om
these d
a
tasets be
come
s in
cre
a
si
ngly broad an
d impo
rtant re
sea
r
ch [1-2].
As clu
s
teri
ng
is one of rese
arching h
o
t-p
o
int
of data mining, there
are many re
sea
r
ch
ers
trying to mine
clu
s
ters from
location
data
,
and lots of
approa
che
s
i
n
locatio
n
dat
a clu
s
teri
ng a
r
e
prop
osed. According to
cl
usteri
ng targ
et, existing a
ppro
a
che
s
could be divid
ed into movi
ng
obje
c
t cluste
ring and traje
c
torie
s
cl
uste
ring. The former is focused on the cl
uster of movi
ng
obje
c
ts [3-7],
and the latter
is traje
c
tori
es [8
-10]. In this paper, we focu
s on the lat
t
er.
As the imag
e, Location
data is
store
d
by
point sets in mo
st
appli
c
ation
s
.
Some
approa
che
s
enga
ged
Hau
s
do
rff Dista
n
c
e a
nd its va
riants,
whi
c
h
is po
pula
r
di
stance m
e
tri
c
s in
comp
uter
gra
phics a
nd p
a
ttern re
co
gnit
i
on, to me
a
s
ure th
e simil
a
rity between
the traje
c
to
ri
es,
su
ch a
s
, line
Hau
s
do
rff distan
ce [7], Hausdorff di
sta
n
ce [12
-
1
4
]. But, these m
e
thod
s we
re
all
based o
n
ab
solute
dista
n
c
e. Obvio
u
sl
y, it is
not fitted to mea
s
ure the
dissi
m
ilarity between
trajecto
ry dat
a.
Example 1:
As sh
own in
Figure 1, give
n
seven t
r
aje
c
tory segme
n
ts
T
1
,
T
2
,
T
3
,
T
4
,
T
5
,
T
6
, an
d
T
7
.
From th
e g
r
a
ph, we
ca
n fi
nd: there are
sam
e
movin
g
pattern in
T
1
,
T
3
,
T
5
, and
T
7
, and
sa
me
moving pattern in
T
2
,
T
4
, and
T6
. Ho
wev
e
r, existing al
gorithm
s ba
sed on a
b
sol
u
te distan
ce,
such
as T
R
AOD, a
r
e difficult to disting
u
ish be
tween them.
In orde
r to solve the defe
c
ts of the ap
proa
ch
es, thi
s
pap
er p
r
op
ose
s
a ne
w
simila
rity
measure b
e
twee
n traj
ect
o
ry
segm
ent
s, which i
s
b
a
se
d o
n
rela
tive distan
ce.
In which, e
a
ch
trajecto
ry i
s
firstly divided
into the
se
gments. A
n
d
then
ea
ch
segm
ent i
s
compa
r
ed
to t
h
e
segm
ents fro
m
other traje
c
tories to obtai
n the clu
s
ters.
2. Similarit
y
Defini
tion of
Trajector
y
Segments
Haus
dorff Dis
t
anc
e
(HD
for s
h
ort)
is
us
ed
to m
e
a
s
ure
the
simila
rity between
two
point
sets,
which i
s
used to me
asu
r
e the
sh
ape bet
wee
n
binary ima
g
e
s in p
a
ttern
recognitio
n
. And
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
116
Usi
ng R
e
lativ
e
Dista
n
c
e
an
d Hau
s
d
o
rff Dista
n
ce to Mine Traj
ecto
ry Cluste
rs
(Bo
Guan
)
then, HD wa
s employe
d
to measure t
he simila
ri
ty betwe
en traj
ectori
es [5]. Ho
wever, bei
ng
different from
imag
e’s di
sorde
r
, the
p
o
ints i
n
th
e t
r
aje
c
tori
es a
r
e o
r
de
red.
T
herefo
r
e,
so
me
cha
nge
s m
u
st be ma
de in
HD to fit th
e traje
c
to
ries. For th
e con
v
enien
ce of
discu
ssi
on, t
w
o
definition
s
are introdu
ce
d firstly.
Figure 1. The
Example in Traje
c
tory Data
Defini
tion
1
:
wh
en
on
e
trajecto
ry seg
m
ent
i
s
com
pare
d
to an
o
t
her one, the
first segme
n
t
is
called
The Ta
rget
, and a
n
o
t
her one i
s
ca
lled
The Compared
.
Defini
tion
2
:
k
-com
pari
ng unit
(
k
-unit
s
)
con
s
i
s
ts of k-contin
uou
s p
o
ints in the trajecto
ry.
Let
T
= {
T
i
| 0
≤
i
<
l
} be the set of traje
c
torie
s
, and
l
is the traje
c
to
ry numbe
r,
n
i
is point
numbe
r of
T
i
, and
S
im
= {
p
im
, …,p
i
(
m+k-
1)
}
is
on
e k-u
n
it of
Traje
c
to
ry
T
i
. Given two trajec
tories
T
i
,
T
j
,
S
im
is one
k
-u
nit of
T
i
,
S
jn
is one
k
-unit
of
T
j
. the pair (
S
im
, S
jn
) is called k-unit p
a
ir.
Minimum Ha
usd
o
rff Dista
n
ce u
nde
r Transl
a
tion is a
measu
r
e u
s
ed to measure relative
distan
ce b
e
twee
n two po
ints set, and
in the field of pattern re
cog
n
ition it is often u
s
ed
in
comp
ari
ng sh
ape
s ba
sed
on the bina
ry
image. Al
tho
ugh the traj
e
c
tory an
d the
image have
th
e
same
rep
r
e
s
entation - p
o
i
nt set, gene
rally, the
image is di
so
rdere
d
, and t
r
aje
c
tory poi
nt is
diso
rde
r
. HD
is aime
d to m
easure th
e di
stan
ce b
e
twe
en di
sorde
r
p
o
int set
s
. Ho
wever, traje
c
tory
point is th
e o
r
de
r. As a
re
sult, we m
a
d
e
a chang
e i
n
HD, and e
a
c
h p
o
int of k-unit is
comp
a
r
ed
each on
e of
other
k-unit
one by o
ne.
Next, the fea
t
ure of traje
c
tory point
re
pre
s
ent
s mo
ving
pattern
of obj
ects,
and
mo
ving pattern o
w
n
s
lo
cal
sim
ilarity, that is
to say, traject
o
ry poi
nt only
i
s
simila
r to its neighb
orin
g po
ints.
Defini
tion
3:
Given a neig
hbori
ng thre
shold
ω
, point
p
i
. if point
p
j
b
e
long
s to
ω
- neigh
bori
ng set
of
p
i
only if
dist
(
p
i
- p
j
) <
ω
, denote
s
p
j
=N
ω
(
p
i
).
Our id
ea i
s
a
c
cordi
ng to
Minimum
Ha
usd
o
rff Di
sta
n
ce
unde
r T
r
ansl
a
tion, the
distan
ce
betwe
en
S
im
and
S
jn
is as
follows: let
S
im
is fixed,
S
jn
is
trans
l
ated to make them to the c
l
os
est,
and Improved
Minimum HD under T
r
an
sl
ation ca
n be
written a
s
:
Defini
tion
4
: given
k
-units
S
im
,
S
jn
, local threshold
λ
, and neigh
bou
ri
ng thre
shol
d
ω
. The relative
distan
ce i
s
de
fined as:
(1)
whe
r
e
()
(
)
0
,
...
,
1
(,
)
m
a
x
{
(
,
)
}
ix
jy
ix
r
j
y
r
rk
dt
t
d
p
p
t
()
(
)
1
1
(,
)
0
ix
r
j
y
r
k
td
i
s
t
p
p
r
k
(,
)
,
(,
)
(,
)
,(
,
)
ix
jy
ix
jy
ix
jy
ix
jy
dist
p
p
t
d
ist
p
p
dp
p
t
dis
t
p
p
T
1
T
2
T
4
T
5
T
6
T
7
T
3
Evaluation Warning : The document was created with Spire.PDF for Python.
117
ISSN: 2302-4
046
TELKOM
NIKA
Vol. 11, No
. 1, Janua
ry 2013 : 115 – 1
2
2
t
is avera
ge
distan
ce
bet
wee
n
ea
ch
p
o
int pair
(
p
i
(
m
+
x
)
,
p
j
(
m
+
x
)
) (0
≤
x<
k
-
1).
d
(
p
ix
,
p
jy
-
t
) de
note
poin
t
the dista
n
ce
betwe
en
p
jy
a
nd
p
ix
after
k-unit
S
jn
is
tr
an
s
l
a
t
ed
b
y
t
.
dist
(
p
ix
,
p
jy
) d
enote Eu
clide
an
distan
ce between
the point
s
p
ix
,
p
jy
, and
if
dist
(
p
ix
,
p
jy
)>
ω
,
p
ix
mu
st
be not
simila
r to
p
jy
.
λ
is l
o
cal
threshold,
an
d the
di
stan
ce bet
wee
n
t
w
o poi
nts is
∞
i
f
their Euclide
an distan
ce a
fter translatin
g
t
is more than
λ
.
Acco
rdi
ng to above analy
s
i
s
, we ca
n co
mpare
not onl
y the shape o
f
trajectory se
gments
but al
so i
nhe
rent m
o
ving
pattern. Imp
r
oved Mini
mu
m Hau
s
do
rff Dista
n
ce u
n
d
e
r T
r
a
n
sl
ation i
s
more
suited t
o
mea
s
u
r
e
th
e si
milarity b
e
twee
n the
trajecto
rie
s
. It
not only
elimi
nates commo
n
deviation through t
r
an
slat
ing traj
ecto
ry, but also ta
ke
s movin
g
pattern i
n
to
accou
n
t thro
ugh
measure dist
ance by point
-to point.
Bec
a
us
e
k
-u
nit is trajecto
ry segm
ent with less poi
nt numbe
r (
k
), comp
arin
g trajecto
ry
segm
ents mu
st sta
r
t with
dividing traj
e
c
tory
segm
en
ts into
k-u
n
its. Based
on t
h
is m
e
thod,
our
solutio
n
dete
r
mines,
wh
eth
e
r two traj
ect
o
ry segm
e
n
ts are
simil
a
r
o
r
not, by m
e
a
s
uri
ng th
eir
k-
units
as
following
Definition
.
Defini
tion
5
: Given two
k
-u
nits
S
im
,
S
jn
, if
d
(
S
im
,
S
jn
) is less than local
similar threshold
θ
,
S
im
,
S
jn
are Lo
cal Sim
ilarity, denote
s
S
jn
έ
LS
(
k
,
θ
)
(
S
im
).
Defini
tion
6
:
Given t
w
o trajecto
ry seg
m
ents
S
u
,
S
v
,
S
uv
+
={p|
p
∈
S
im
,
S
jn
∈
LS
(
k
,
θ
)
(
S
im
) }.
If the
followin
g
quot
ation is satisfi
ed,
S
u
,
S
v
are Global Simi
larity:
|
S
uv
+
|
≥
ζ
* |
S
u
|
whe
r
e, |
.
| denotes
point
s numbe
rs in the set, and
ζ
is Glob
al Similarity thre
shold, provide
d
by
the use
r
in ad
vance.
Input: T
r
ajectory
set
T
= {
T
1
,
T
2
,
T
3
…T
l
}
Output: Clusters set
Set
c
={
C
1
…C
num
cl
us
}
01: for each
T
i
do
02:
S
im
=
Partiti
oni
ngT
raj
e
ctor
y
(
T
i
);
03: add
S
im
into set
S
;
04:
Set
c
=
ClusterT
r
ajector
y
(
T
);
06: return
Set
c
Figure 2. Pse
udo Code of
Tra
C
lu
stMHD
3. The Fram
e
w
o
r
k o
f
Tra
C
lustMHD
I
n
t
h
is
se
ct
io
n,
we f
o
cu
s
on
T
r
aC
lu
stMH
D
fram
ework. The algo
rithm could
b
e
divided
into thre
e p
hases. Fi
rstly, each t
r
aj
ectory
co
uld
be divid
e
d
into traj
ect
o
ry segm
ent
s by
cha
r
a
c
teri
stic point; seco
n
d
ly, acco
rdin
g to above si
milarity definitions, the simil
a
rity of each two
trajecto
ry se
gments i
s
e
v
aluated, in
here, a
n
opt
imized
meth
od is int
r
od
u
c
ed to find
out
can
d
idate si
milar
k
-unit
s
; finally, traditional clu
s
teri
ng algo
rithm
is employe
d
to search
the
clu
s
ters of tra
j
ectory
segm
ents. Figu
re 2
sho
w
s its p
s
eudo
cod
e
.
3.1. Partition
e
d b
y
charac
ter point
In order to
partition the traj
ec
tory effic
i
ently,
c
h
arac
teri
stic
po
int [7] is
e
m
ployed.
Cha
r
a
c
ter p
o
i
nt is the po
int in which
moving obj
ects
cha
nge
s their
spee
d and directi
o
n
signifi
cantly. Figure 3 sho
w
s
sub
-
seg
m
ent
T
i
which is formed e
i
ght points (
p
1
,
p
2
,
…
and
p
8
).
Obvious
l
y,
p
1
,
p
4
,
p
5
,
p
6
, and
p
8
are
cha
r
acter
point
s. Figure 4 sho
w
s p
s
e
udo
co
de of partition
ing
trajecto
ry. Fo
r e
a
ch traj
ect
o
ry, the first
step i
s
ta
kin
g
sta
r
t poi
nt a
nd e
nd
point
into
Cha
r
a
c
t
e
r
Point Set
Set
cp
, the secon
d
step is that
each point woul
d be me
asure whethe
r its ch
ang
es in
the
dire
ction o
r
speed i
s
m
o
re
than given
thre
shol
d, if
it is tru
e
, this
point is re
garded a
s
cha
r
a
c
te
r
point, and ad
ded into Character Poi
n
t Set.
22
(,
)
.
.
.
.
i
r
jr
ir
j
r
ir
j
r
dis
t
p
p
p
x
p
x
p
y
p
y
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
118
Usi
ng R
e
lativ
e
Dista
n
c
e
an
d Hau
s
d
o
rff Dista
n
ce to Mine Traj
ecto
ry Cluste
rs
(Bo
Guan
)
Acco
rdi
ng to
above al
gorit
hms, traj
ecto
ry
T
i
in Figu
re
3 will b
e
pa
rtitioned by ch
ara
c
ter
points, an
d formed a
s
{
(
p
1
,
p
2
,
p
3
), (
p
4
,
p
5
), (
p
5
,
p
6
), (
p
6
,
p
7
,
p
8
)}.
Figure 3. The
Example of Cha
r
a
c
ter Poi
n
t
Input:
T
i
={
p
1,
p
2
, …, p
ni
},
MinDir, MinVel
o
c
ity
Output:
Set
cp
PartitioningT
rajecto
r
y
(
T
i
)
01: Add
p
1
,
p
ni
into the
Set
cp
;
02: for ea
ch
p
j
(
p
j
∈
T
i
, 1<
j<
n
i
) DO
03:
Dire
ctor
y
=
com
puteDirecto
ry
(
p
j-1
,
p
j
,
p
j+1
)
04
：
Veloc
i
t
y
=
com
puteV
elocit
y
(
p
j-1
,
p
j
,
p
j+1
)
05: I
f
(
Dire
c
t
ory
>
MinDi
r
)
or (
Veloc
i
ty
>
MinVelcity
)
06: Add
p
j
i
n
to the s
e
t
Set
cp
;
Figure 4. Pse
udo Code of
PartitionTrajectory
3.2. Optimized Searchin
g Method by
Featur
e Matrix
Acco
rdi
ng
to our sol
u
tion, each k-u
n
its need
to
be
compa
r
ed
to a
ll k-units from
othe
rs
trajecto
rie
s
. Obviou
sly, its comp
arin
g cost is
very e
x
pensive. Ho
w to optimize this search
ing
pro
c
e
ss i
s
a
n
o
ther im
porta
nt probl
em in
our fram
e
w
o
r
k. O
u
r
soluti
on is fin
d
ing
out all candi
d
a
te
local similar
k
-u
nits
pairs
by so
rt of si
milar of traje
c
to
ry featu
r
e.
In ord
e
r to
descri
be
cle
a
rly,
Dista
n
ce Fea
t
ure Matrix a
r
e introdu
ced
firstly. Di
sta
n
ce F
eatu
r
e
Matrix co
nsi
s
ts of point p
a
i
rs
whic
h come from two traj
ec
tories
respec
tively.
Defini
tion 7
:
Suppose Th
e Target
S
i
= {
p
i
1
, .
..,
p
im
}
and The Co
mpari
ng
S
jn
= {
p
j
1
, .
..,
p
jm
}, the
distan
ce b
e
tween ea
ch p
o
i
n
t pairs i
s
:
)
,
(
)
,
(
)
,
(
)
,
(
1
1
1
1
jn
im
jn
i
j
im
j
i
p
p
p
p
p
p
p
p
M
Defini
tion 8
:
Diag
onal
Serial No.(
DSN
o
.) is th
e differen
c
e
betwe
en the
ro
w a
nd the
colum
n
of
matrix, denot
es
DS
No
(
p
ie
,
p
jf
) =
e
-
f,
and (
p
ie
,
p
jf
) is
one matrix elements
.
Defini
tion
9
:
k
-diago
nal Neighb
orin
g
(
k-
DN
for
sh
ort
)
consi
s
t
s
of
k
matrix el
e
m
ents
only if th
e
following two
conditions are satisfied:
(1) DSNo
(
p
ie1
,
p
jf1
) = … =
DSN
o
(
p
iek
,
p
jfk
);
(2) e
2
–e
1
= … = e
k
– e
k-
1
=
1
.
Obvious
l
y,
k
-
DN
inc
l
u
des
tw
o
k
-unit
s
from t
w
o
trajecto
ry
segm
ents. T
herefo
r
e,
according to
Definition
3, two
k-u
n
its
co
uldn’t be
simi
lar only if on
e eleme
n
t (
p
ie
1
,
p
jf1
) sat
i
sf
ied
that the di
sta
n
ce
betw
een
its point
s i
s
more th
an
ne
ighbo
ur th
re
shold
ω
. Bas
e
d on this
idea, i
f
we o
r
de
rs
ma
trix element
s by (
DS
No
,
Row
I
D
). If cont
inuou
s
k
ele
m
ents
all sati
sfy
Defini
tion
3
,
corre
s
p
ondin
g
k-u
n
its in th
is k-DN is
ca
ndidate
simila
r k-unit pair.
Therefore,
ou
r solution
is
as foll
ows
(Pseu
do
cod
e
as Fi
gu
re 5
)
:
Firstly, for e
a
ch
point
p
im
of each trajecto
ry
T
i
,
N
ω
(
p
im
) is findin
g
out by so
rt of
R-T
r
ee, a
n
d
the elem
ent
(
p
im
,
p
jn
) wou
l
d
be ad
ded int
o
ca
ndidate
matrix set (Candid
a
te Se
t in the sh
ort), which elem
ents o
r
de
r by
(
i
,
DSNo
,
m
)
,
only if
p
im
,
and
p
jn
sat
i
sf
y
p
jn
∈
N
ω
(
p
im
),
dist
(
p
im
,
p
jn
)<
ω
. Se
con
d
ly, top m
a
trix elem
ent
s
(
p
im
,
p
jn
) would be rem
o
ved
from Can
d
id
ate Set one b
y
one. If continuou
s
k
el
em
ents con
s
ist
s
k-
DN
, the di
sta
n
ce b
e
twe
en
its k-unit pai
r could
be
ch
ecked to d
e
termin
e wh
eth
e
r two
k-units is
local
similar. If it is satisfied, all points of
tar
get k-unit
woul
d insert i
n
to local
simil
a
r poi
nt set S
+
,
in whi
c
h all points with
similar segment are incl
u
d
e
d
. After all pairs of traj
ect
o
ry seg
m
ent
are
che
c
ked, lo
cal simila
r d
e
g
r
ee
of the tra
j
ectory
se
gm
ent co
uld b
e
taken
out. Fi
nally, after lo
cal
simila
r deg
re
e of all traje
c
tory seg
m
ent
s is
cal
c
ulate
d
, DBSCAN,
whi
c
h is t
r
adi
tional clu
s
te
ri
ng
algorith
m
, is introdu
ce
d into mine traje
c
t
o
ry seg
m
ent
s cluste
rs.
cp
1
p
2
p
1
p
3
p
4
p
5
p
6
p
7
p
8
cp
2
cp
3
cp
4
T
i
character p
o
int
cp
5
Evaluation Warning : The document was created with Spire.PDF for Python.
119
ISSN: 2302-4
046
TELKOM
NIKA
Vol. 11, No
. 1, Janua
ry 2013 : 115 – 1
2
2
Figure 5. the Example of Distan
ce Featu
r
e Matrix
Example 2
: given A={
a
1
,a
2
,a
3
,a
4
} is
The Targe
t
in Def
i
nitoin 1(Fi
gure 5), and
T
1
=
{
t
1
,…,t
4
} is
The
Comparing.
Dista
n
ce Fea
t
ure Matrix be
tween A and
T
1
is
as
follows
.
)
,
a
(
)
,
a
(
)
,
a
(
)
,
(a
)
,
a
(
)
,
a
(
)
,
a
(
)
,
(a
)
,
a
(
)
,
a
(
)
,
a
(
)
,
(a
)
,
a
(
)
,
(a
)
,
(a
)
,
(a
)
,
a
(
)
,
a
(
)
,
(a
,
a
4
5
3
5
2
5
1
5
4
4
3
4
2
4
1
4
4
3
3
3
2
3
1
3
4
2
3
2
2
2
1
2
4
1
3
1
2
1
1
1
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
M
）
（
The follo
w ta
ke
s Example
2 as the
example to
d
e
scribe the
pro
c
e
ssi
ng of
algo
rithms. In
the first step, R-T
r
ee i
s
em
ployed to sea
r
ch all
n
e
ighb
our poi
nts of each poi
nt. In the Example 2,
all neig
hbo
ur poi
nts of {
a
1
,a
2
,a
3
,a
4
} is
N
ω
(
a
1
)
=
{
t
1
,t
21
,t
31
}
，
N
ω
(
a
2
)
=
{
t
2
,t
22
,t
32
}
，
N
ω
(
a
3
)
=
{
t
3
,t
23
}
，
N
ω
(
a
4
)
=
{
t
4
,t
24
,t
34
}. If the element, which di
stan
ce is mo
re th
an
ω
, is
s
e
t t
o
z
e
ro, Feature
Matrix betwe
en A and
T
1
is tran
slated t
o
:
Acco
rdi
ng
ab
ove di
stan
ce
feature
matri
x
, we
co
uld fi
nd o
u
t all
ca
ndidate
si
milar
k-unit
pairs ea
sily. If k is set to 3, we could
get
two ca
ndid
a
te simila
r k-u
n
i
ts pairs {
(
a
1
, t
1
), (a
2
, t
2
), (a
3
,
t
3
)}, { (a
2
, t
2
), (a
3
, t
3
), (a
4
, t
4
)} in Example 2.
3.3. TraClus
t
MHD
Alogrithm
In this
se
ctio
n, we
present
ho
w to
use t
he lo
cal
featu
r
es to im
prov
e the
efficien
cy of the
prop
osed a
p
p
roa
c
h.
We f
i
rst a
s
sume t
hat all poi
nts are in
dexed
by R-T
r
e
e
. Fig
.
6 sho
w
s the
pse
udo
code
of the
opti
m
ized
o
u
tlying traje
c
to
ry
dete
c
tion.
As me
ntione
d p
r
eviou
s
ly, this
algorith
m
co
nsi
s
ts of two
pha
ses: p
r
u
n
ing an
d re
fi
ning. Fo
r ea
ch traj
ecto
ry, the function
of
Clu
s
terin
g
Tra
j
ectory is u
s
e
d
to achieve t
he pru
n
ing a
n
d
refining.
First, for ea
ch target seg
m
ent
S
i
,
all
N
λ
(
p
ix
) a
r
e di
scovere
d
by sea
r
ching
R-Tree a
nd
then form
N
λ
(
T
i
)
,
w
h
ic
h
is
s
o
r
t
ed
b
y
(
tid
,
DSNo
.
). This p
r
o
c
e
s
s i
s
a
c
hieve
d
b
y
the functio
n
of
Queryin
g
RTree
.
Secon
d
, whil
e the orde
re
d stack
stackNeigh
is not empty, th
e following
steps are
execute
d
:
(1)
Th
e e
n
try
fEn
is obtai
n
ed from th
e t
op of
the
ord
e
red
stack
st
ackNeigh
,
an
d this recursi
v
e
operation is
skipp
ed when
all trajecto
rie
s
are p
r
o
c
e
ssed.
(2)
I
t
is
che
c
ked
wh
et
he
r
fEn
and
last
En
are
k-D
N
adja
c
ent (
lastEn
is th
e late
st top of
sta
c
k).
One of the followin
g
ope
rat
i
ons
works:
i
) If the target trajecto
ry of
fEn
is different from th
at of
lastEn
, which im
plys
fEn
is
obtaine
d fro
m
ne
w
N
λ
(
T
j
) (
j<>i
),
LSArray
i
s
clea
red,
C
an
dLSSet
i
s
clea
r,
and
curE
n
is
inse
rted into
Can
dLSSet.
ii
) if
fEn
and
lastEn
bel
ong
s to sa
me traj
ectory a
nd a
r
en’t
k-
D
N
adj
ace
n
t, C
and
L
SSet
is
clea
r, and curEn is inse
rted
into Cand
LSSet, and curDSNo is
set to DSNo of
curE
n;
11
22
33
44
a,
0
0
0
0(
a
,
)
0
0
00
(
a
,
)
0
00
0
(
a
,
)
t
t
M
t
t
（）
ω
T
1
A
a
1
a
2
a
3
a
4
t
1
t
2
t
3
t
4
ω
ω
ω
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
120
Usi
ng R
e
lativ
e
Dista
n
c
e
an
d Hau
s
d
o
rff Dista
n
ce to Mine Traj
ecto
ry Cluste
rs
(Bo
Guan
)
iii
)if
fEn
and
lastEn
are
k-
DN
adj
acent: (
a
)
fEn
is inserte
d
befo
r
e
the last element of
LSArra
y
, whi
c
h i
s
a p
o
int
pair a
r
ray wit
h
k
-length
(th
e
functio
n
ad
dEntry
i
s
call
ed);
(
b
) if
the numbe
r
of point pairs in the
LSArra
y
is
k
a
nd the dissi
m
ilarity between its
k
-
segm
ents i
s
l
e
ss
ζ
(the fu
n
c
tion
KMat
c
h
is called
)
, th
e point
s
p
ix
(
p
ix
∈
T
i
) in
LSArray
are
inse
rted into the point set
Re
sult_Ar
r
a
y
.
(3)
lastEn
is repla
c
e
d
by
fEn
.
Finally, traditional clustering anal
ysis
(DBSC
AN in here) is employe
d
to mine all
segment clu
s
ters.
Input: A s
e
t
of trajec
tories
T
= {
T
1
…T
n
}, param
eters
ζ
, k
,
ω
,
λ
, Mi
nDirec
tory
,
MinVelo
c
ity.
Output: A s
e
t of c
l
us
ters
Set
c
=
{C
1
…C
numclus
}
C
l
us
te
r
i
ng
T
r
aje
c
to
r
y
(
)
01. For
ea
ch
sub
-
se
gme
n
t
S
i
S
DO
02.
Re
sult_Ar
r
a
y
=
MatchTraje
ctory
(
S
i
,
i,
ζ
, k
,
ω
,
λ
)
03. Set
c
=Clu
ster(Re
s
ult_A
r
ray)
MatchT
raje
ct
ory
(
S, I,
θ
, p,
k
,
ω
)
01:
s
t
ackN
eigh
=
Que
r
yRT
r
ee
(
S
i
,
ω
);
02: while (
st
ackNeigh
is
n’t
NULL
)
03:
curE
n
=
sta
c
kNei
gh
.
Rev
T
op
()
;
04:
If (
c
u
rE
n. traj !=
c
u
r_traj)
{
05:
c
u
r_traj =
curEn.
traj
;
06:
C
andLSSet=NULL; LSArra
y=NULL;
07:
CandLSSet
.add
Entry(
cur
E
n
);
07: els
e
08:
If (
curE
n
.
DSN
o
!=
cur
D
S
N
o)
or (
curE
n
.
po
s
-1 ==
cu
rP
os
)
09:
CandLSSet=NULL
;
cur
D
S
N
o =
cu
rE
n.
DS
N
o
;
11:
CandLSSet
.add
Entry(
cur
E
n
);
10:
els
e
11:
If
((
CandLSSet
.s
ize())>
k
-1)
12:
isM
a
t
c
h
=
KMat
c
h
(
cu
rE
n
,
k,
λ
));
13:
I
f
(
isMatch
)
14:
LSArray
.
ad
dEntry
(
curE
n
，
C
a
ndL
SSe
t
);
15:
If
LSArray
.
Si
z
e
()
≥
ζ
*S
i
.Siz
e();
16:
R
e
s
u
lt_Array
[i][j]=
1;
17:
Els
e
Re
sult_Arra
y
[i][j]=
0;
18:
las
t
En =
c
urEn;
18 return
(
R
e
sult_A
rra
y
);
Figure 6. the Example of Distan
ce Featu
r
e Matrix
4. Experimental An
aly
s
is
4.1. Experimental Env
i
ro
nment
We imple
m
e
n
t relative alg
o
rithm
s
and
Tra
C
lu
stMHD
in Visual C++, on the XP
OS and
execute all e
x
perime
n
ts o
n
a noteboo
k with Centri
n
o
2 2.1G CP
U and 2G m
a
in memo
ry. The
experim
ental
dataset is fro
m
the
wealth
of hurri
ca
ne i
n
formatio
n in
cludi
ng chart
s
on the tra
ck
o
f
the sto
r
m pl
u
s
a text ba
se
d table of t
r
a
cki
ng info
rma
t
ion. We
sel
e
ct hu
rri
can
e
data of Atlant
ic
hurricane
s from 18
50 to
2010,
whi
c
h
has 12
94 tr
a
j
ectori
es with
303
68 p
o
int
s
. All poi
nts
in
trajecto
ry dat
a are imp
o
rte
d
into bina
ry file ac
cordi
n
g
to its traject
o
ry ID, and then ind
e
xed
by
R*-T
re
e. And clu
s
terin
g
alg
o
rithm is
DBSCAN.
4.2. Experimental Analy
s
is
Based
on en
suri
ng b
e
st p
e
rform
a
n
c
e t
h
rou
gh a
d
ju
sting each pa
rameter,
we
make
a
comp
ari
s
o
n
i
n
Traje
c
tory
Clu
s
teri
n
g
through
Line
Hausdorff
Dist
ance
[8], Haus
dorff Dis
t
anc
e
[16], and ou
r
frame
w
ork. Fi
gure
7
sho
w
s com
pari
ng
result
s in the
m
. From th
e
grap
hs,
we
could
find that all algorithm
s sh
o
w
s movin
g
p
a
ttern of
hurri
can
e
. However, there a
r
e some b
u
g
s
in the
algorith
m
s b
a
se
d o
n
Lin
e
HD
and
HD be
ca
u
s
e
ba
sed
on
absolute
dist
ance a
nd gl
oba
l
Evaluation Warning : The document was created with Spire.PDF for Python.
121
ISSN: 2302-4
046
TELKOM
NIKA
Vol. 11, No
. 1, Janua
ry 2013 : 115 – 1
2
2
comp
ari
ng. Both of them coul
d find ou
t the cl
uste
rs in Regi
on A
and C, be
ca
use thi
s
Regi
on
own
eno
ugh
trajecto
rie
s
.
But in ou
r fra
m
ewo
r
k, the
clu
s
ters in
Region A
and
C a
r
e
disa
pp
ear.
The re
ason is that moving dire
ction is ta
ken into a
c
co
unt in our fra
m
ewo
r
k.
(a)
Re
sult of usin
g Line
Ha
usd
o
rff Dista
n
ce
(b)
Re
sult of usin
g Ha
usdo
rff Distan
ce
(c) Re
sult of usin
g Tra
C
lu
stMHD
Figure 7. Co
mpari
ng Results in Three
Algorithm
Figure 8 sho
w
s th
at the compa
r
ison of
CPU Ti
m
e
in
three alg
o
rit
h
ms. From th
e gra
ph,
Tra
C
lu
stMHD own
s
high
e
r
efficien
cy than ot
he
rs.
And more trajecto
ry num
ber is, mo
re
sup
e
rio
r
ity TraCl
u
stM
HD own
s
. The
reason is
that R-Tree
are emplo
y
ed to eliminate
comp
utation
betwe
en irre
spective poi
nts.
Figure 8. Co
mpari
ng re
sul
t
in CPU time
0
1000
2000
3000
4000
5000
6000
200
400
600
800
1000
CPU
Time
Trajector
y
Number
LHD
HD
TraClustMHD
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
122
Usi
ng R
e
lativ
e
Dista
n
c
e
an
d Hau
s
d
o
rff Dista
n
ce to Mine Traj
ecto
ry Cluste
rs
(Bo
Guan
)
5. Conclusio
n
Along
with m
o
re
re
sea
r
ch
ers focusi
ng
on traj
ecto
ry
clu
s
terin
g
, thi
s
pa
pe
r p
r
op
ose
s
a
trajecto
ry cl
u
s
terin
g
fra
m
e
w
ork
ba
sed
o
n
local relative dista
n
ce. T
h
is frame
w
o
r
k not
only u
s
es
local
rel
a
tive distan
ce
to measure simi
larity
mo
re
correct, b
u
t al
so i
m
proves
the pe
rforma
nce
throug
h index
ed by R-T
r
ee
. Experimental Re
sults
sh
ow that our framework ha
s more efficie
n
c
y
and effective
than other al
g
o
rithm
s
.
Ackn
o
w
l
e
dg
ement
This wo
rk wa
s
suppo
rt
ed
by
Zhejian
g
Prov
inci
al
Educatio
n
Dep
a
rtme
nt sci
entific
resea
r
ch proj
ect of unde
r grant No. Y20111
9588, a
nd Natu
ral Scien
c
e Fo
un
dation of Nin
gbo
unde
r grant No. 2009A61
0
090, No. 20
1
0
A6101
06, a
nd No. 20
11A
6101
75.
Referen
ces
[1]
YF
Li, JW
H
an, J Y
ang.
Clusteri
n
g
Mo
ving O
b
jects.
Procee
din
g
s
o
f
the 1
0
th A
C
M SIGKDD
Internatio
na
l C
onfere
n
ce o
n
Know
led
ge Disc
o
very an
d Data
Minin
g
. Seattle. USA, 2004;
617-
622.
[2]
Ester M, Krieg
e
l, HP, Sa
nd
er J, and
Xu,
X.
A De
nsity-Ba
sed Al
gorit
h
m
for Discov
e
rin
g
Clusters
i
n
Larg
e
Sp
atia
l
Datab
a
ses w
i
t
h
No
ise
. Proc. 2
nd
Int'
l
Conf. on
K
n
o
w
l
e
dge
Discover
y
a
nd Data
Mi
ni
ng,
Portlan
d
, Oregon. 199
6; 226-
231.
[3]
S Gaffney
and P Smy
t
h.
T
r
aj
ectory cl
usterin
g
w
i
th
mixtur
e
of regr
essio
n
mo
de
ls
. Proce
edi
ngs
of
the
5
th
Internatio
na
l Co
nfere
n
ce
o
n
Kn
o
w
l
edg
e
Discover
y
a
n
d
Data M
i
ni
ng (
K
DD’9
9), Sa
n
Dieg
o
, 1
9
9
9
;
63–
72.
[4]
D Chu
dova, S
Gaf
f
ne
y
,
E Mjolsn
ess an
d
P
Sm
y
t
h.
T
r
an
slatio
n invar
i
a
n
t mixtur
e mo
dels for curve
clusteri
ng
. Pro
c
eed
ings
of th
e 9th Inter
natio
nal
Confer
enc
e
on Kn
o
w
l
e
d
g
e
Discov
e
r
y
an
d
Data Mi
nin
g
(KDD’0
3), Washin
gton. 20
03; 79-8
8
.
[5]
M Nann
i and
D Pedresc
h
i. T
i
me-focus
ed d
ensit
y- bas
ed
clusteri
ng of trajector
i
es of movin
g
obj
ects.
Journal of Intelligent Inform
ation System
s
. 2006; 27(
3): 267
-289,
[6]
H
w
ang JR, Kang HY, Li KJ.
Spatio-te
m
pora
l
Similar
i
ty an
aly
s
is betw
een tra
j
ectori
es on r
o
ad n
e
tw
orks
.
Procee
din
g
o
f
24
th
inter
n
ation
a
l c
onfe
r
ence
on
P
e
rspectiv
e
s i
n
Co
nce
p
tua
l
Mode
li
ng
(ER’05).Kl
a
g
e
n
f
urt, Austria. 2005; 280-
28
9.
[7]
J Le
e, J H
an,
and
K
y
u-Yo
un
g W
h
a
ng.
T
r
aj
ectory cl
usteri
ng: A
partitio
n
-
and-
grou
p fra
m
ew
ork
. Proc.
200
7 ACM SIGMOD Int'
l Conf. on Mana
gem
e
n
t of Data, Beiji
ng Ch
ina. 2
007
. 593-60
4.
[8]
Christia
n S Jensen, Da
n Lin,
Beng Chi
n
Ooi.
C
ontin
uo
us
Cl
usterin
g
of Movin
g
Obj
e
ct
s
. Kno
w
l
e
dge
and D
a
ta Eng
i
neer
ing. 2
007;
19(9): 11
61-
11
74.
[9]
Ying
yi
Bu, Le
i
Che
n
, Ada Wa
i-Che
e
, Fu Da
w
e
i L
i
u. E
fficient Anom
aly Monitori
ng Over
Movin
g
Object
T
r
ajectory Stre
ams
.
KDD
’
09,
Paris, F
r
ance. 200
9: 159-
168.
[10]
Z
henh
ui Li,
J
ae-Gil Le
e,
Xiaol
ei
Li
a
n
d
Jia
w
e
i
Ha
n.
Incre
m
e
n
tal Clusteri
n
g
for
T
r
ajectori
es
.
Procee
din
g
s
o
f
the 1
5
th
inte
rnatio
nal
co
nferenc
e o
n
D
a
t
abas
e S
y
stem
for Adv
ance
Appl
icatio
ns.
T
s
ukuba Japa
n. 2010: 3
2
-46.
[11]
Z
hen hu
i, Jia
w
ei Han, Min
g
Ji. et al.
MoveMine: Mini
ng
Movin
g
Object
data for disco
very of anin
a
l
mov
e
me
nt pat
terns
. ACM T
r
ansacti
ons
on
Intell
ige
n
t S
ystem an
d T
e
chno
log
y
(T
IST
)
. 201
0. 2(4):
37:1-3
7
:32
[12]
Lou J
i
a
n
-gu
a
n
g
, Liu
Qi-feng
,
T
an T
i
e-niu,
et al.
Se
man
t
ic
interpr
e
tati
on
of obj
ect activities in a
surveillance sy
stem
. Proc
ee
d
i
ngs
of the
1
6
the Inter
nati
o
nal
Co
nfere
n
c
e
o
n
Patter
n
Reco
gniti
on
(ICPR’02), W
a
shin
gton. 20
02
; 777-78
0.
[13]
June
jo IN, Jav
ed O, Sha
h
M
.
Multi featur
e
path
mo
de
lin
g
for vide
o surv
eill
anc
e
. 17th I
n
ternati
o
n
a
l
Confer
ence
on
the Pattern Re
cogn
ition
(ICP
R’04), W
a
sh
in
gton. 20
04; 71
6-71
9.
[14]
Khal
id S, Nafte
l A.
Evaluati
on
of match
i
n
g
metrics for trajec
tory-base
d
in
d
e
xin
g
an
d ret ri
eval of vi
de
o
clips
. Proceedings of the
Seventh IEEE Workshops on
Applicat
ion of
Computer
Vision (WACV/
MO2T
ION’ 05), W
a
shingto
n
. 2
005; 24
2-2
49.
[15]
Qu Lin, Z
h
ou
F
an, Che
n
Ya
o-
w
u
.
T
r
aj
ecto
ry classificati
o
n
bas
ed
on H
ausd
o
rff distan
ce for visu
a
l
surveillance sy
stem
. 20
09; 39
(6): 288-2
99.
Evaluation Warning : The document was created with Spire.PDF for Python.