Semantic-based Trajectory Data Mining Methods
Vania Bogorny
INE – UFSC
A importância de considerar a semântica
C
R
C
R
SC
T3
T3
T2
H
T2
T1
H
T1
T4
Padrão Geométrico
H
Hotel
T4
R
Restaurant
C
Cinema
Padrão SEMÂNTICO
(a) Hotel p/ Restaurante, passando por SC
(b) Cinema, passando por SC
2
Geometric Patterns X Semantic Patterns (Bogorny 2008)

There is very little or no semantics in most DM approaches for
trajectories
Consequence:
•
•
•
Patterns are purely geometrical
Difficult to interpret from the user’s point of view
Do not discover semantic patterns,
which can be independent of spatial location
Principal Problema: Falta de semântica
Trajetórias Brutas (x,y,t)
Dados Geográficos
Geografia + Trajetória Bruta =
Trajetória Semântica
4
Motivada por um
Modelo Conceitual
para Trajetórias
Trajetória Metafórica
(Spaccapietra 2008)
end
Time
(Professor, EPFL, 1988-2010)
(Professor, Dijon, 1983-1988)
(Lecturer, Paris VI, 1972-1983)
(Assistant, Paris VI, 1966-1972)
position
institution
begin
6
Modelagem Conceitual (EPFL, Suíça)
Primeiro modelo conceitual para trajetórias:


STOP: parte importante de uma trajetória do ponto de vista de uma
aplicação, considerando as seguintes restrições:

durante um stop o objeto móvel é considerado parado

O stop tem uma duração (tf - ti > 0)
MOVE: parte da trajetória entre 2 stops consecutivos ou entre um stop e o
início/fim da trajetória
7 7
The Model of Stops and Moves (Spaccapietra 2008)
STOPS

Important parts of trajectories

Where the moving object has stayed for a minimal
amount of time

Stops are application dependent

Tourism application


Hotels, touristic places, airport, …
Traffic Management Application

Traffic lights, roundabouts, big events…
MOVES

Are the parts that are not stops
Modelo de Stops e Moves
Traveler
location
0:N list
Has
1:1
Trajectory
2:N list
hasStops
1:1
0:1
From
1:1
Move
Stop
0:N
0:1
To
ƒ(T)
1:1
IsIn
0:N
Place
9
Adicionando semântica às trajetórias: usando STOPS
STOPS são dependentes da aplicação
1
2
Aeroporto
[08:00 – 08:30]
Ibis Hotel
[10:00-12:00]]
Museu Louvre
[13:00 – 17:00]
Torre Eifel
[17:30 – 18:00]
3
Aeroporto
[08:00 – 08:30]
Rótula
[08:40 – 08:45]
Congestionamento
[09:00 – 09:15]
Cruzamento
[12:15 – 12:22]
1
Semantic Trajectories

A semantic trajectory is a set of stops and
moves

Stops have a place, a start time and an end
time

Moves are characterized by two consecutive
stops
Métodos para instanciar o modelo de stops e
moves e minerar trajetórias semanticas
1
Methods to Compute Stops and Moves
1) IB-SMoT (INTERSECTION-based)
Interesting for applications like tourism and urban planning
2) CB-SMoT (SPEED-based clustering)
Interesting for applications where the speed is important,
like traffic management
3) DB-SMOT (DIRECTION-based clustering)
Interesting in application where the direction variation is important
like fishing activities
IB-SMoT
(Alvares 2007a)
A candidate stop C is a tuple (RC, C), where

RC is the geometry of the candidate stop (spatial feature type)

C is the minimal time duration
E.g. [Hotel - 3 hours]
An application A is a finite set
A = {C1 = (RC1 , C1 ), …, CN = (RCN , CN)} of candidate
stops with non-overlapping geometries RC1, … ,RCN
E.g. [Hotel - 3 hours, Museum – 1 hour]
11/5/2015
14 of 90
IB-SMoT

(Alvares 2007ª)
Input: candidate stops
// Application
trajectories

Output:

Method:

// trajectory samples
Semantic rich trajectories
For each trajectory

Check ifJurere
it intersects a candidat stop for a minimal amount of time
09-12
IbisH.
13-14
FloripaS
16-17
11/5/2015
15 of 90
Schema of Stops and Moves
Tid Sid SFTname
SFTid
1 1 Hotel
1
1 2 TouristicPlace 3
1 3 TouristicPlace 3
Sbegint
08:25
09:05
10:01
Sendt
08:40
09:30
14:20
Stops
Moves
Tid Mid S1id S2id
1 1
1
2
1 1
1
2
1 1
1
2
1 2
2
3
…
1 2
2
3
Hotel
Id Name
Stars geometry
1 Ibis
2
48.890015 2.246100, ...
2 Meridien 5
48.880005 2.283889, …
Alvares (ACM-GIS 2007)
geometry
48.888880 2.246102
48.885732 2.255031
48.860021 2.336105
48.860515 2.349018
...
48.861112 2.334167
timest
08:41
08:42 ... ... ... ... ... ...
09:04
09:41
... ... ...
...
10:00
Touristic Place
Id Name
1 Notre Dame
2 Eiffel Tower
3 Louvre
Type
Church
Monument
Museum
geometry
48.853611 2.349167,…
48.858330 2.294333,…
48.862220 2.335556,…
16
1
Queries: Trajectory Samples X Stops and Moves
Q2: How many trajectories go from a Hotel to at least one Touristic
Place?
SELECT distinct count(t.Tid)
FROM trajectory t, trajectory u, hotel h, touristicPlace p
WHERE intersects (t.geometry, h.geometry) AND
Trajectory samples
Intersects (u.geometry, p.geometry) AND
t.Tid=u.Tid AND u.timest>t.timest
Semantic Trajectories
SELECT distinct count(a.Tid)
FROM stop a, stop b
WHERE a.SFTname='Hotel' AND
b.SFTname='Touristic Place' AND a.Tid=b.Tid
No Spatial Join
AND a.Sid < b.Sid
17
Alvares (ACM-GIS 2007)
1
Queries: Trajectory Samples X Stops and Moves
Q1: Which are the places that moving object A has passed during his
trajectory?
SELECT ‘Hotel’ as place
FROM trajectory t, hotel h
WHERE t.id='A' AND
intersects (t.movingpoint.geometry,h.geometry)
UNION
SELECT ‘TouristicPlace’ as place
FROM trajectory t, touristicPlace p
WHERE t.id='A' AND
intersects (t.movingpoint.geomtetry,p.geometry)
UNION
…
SELECT SFTname as place
FROM stop
WHERE id='A‘
18
Alvares (ACM-GIS
2007)
1
Queries: Trajectory Samples X Stops and Moves
Q2: How many trajectories go from a Hotel to at least one Touristic
Place?
SELECT distinct count(t.Tid)
FROM trajectory t, trajectory u, hotel h, touristicPlace p
WHERE intersects (t.geometry, h.geometry) AND
Trajectory samples
Intersects (u.geometry, p.geometry) AND
t.Tid=u.Tid AND u.timest>t.timest
Semantic Trajectories
No Spatial Join
19
Alvares (ACM-GIS
2007)
SELECT distinct count(a.Tid)
FROM stop a, stop b
WHERE a.SFTname='Hotel' AND
b.SFTname='Touristic Place' AND a.Tid=b.Tid
AND a.Sid < b.Sid
1
Queries: Trajectory Samples X Stops and Moves
Q4: Which are the Touristic Places that moving objects have passed and
stayed for more than one hour?
SELECT temp.name, count(*) AS n_visits
FROM ( SELECT t.Tid, p.name
FROM trajectory t, touristicplace p
WHERE intersects (t.geometry,p.geometry)
GROUP BY t.Tid, p.name
HAVING count(t.*)>60) AS temp
GROUP BY temp.name
SELECT t.name, count(s.*) AS n_visits
No Spatial Join
FROM stop s, touristicplace p
WHERE s.SFTid=p.id AND (s.Sendt - s.Sbegint ) > 60
GROUP BY t.name
20
Alvares (ACM-GIS
2007)
2
CB-SMoT: Speed-based clustering
(Palma 2008)
Input: Trajectory samples
Speed variation
minTime
Output: stops and moves
Unknown stop
Jurere
09-12
Step 1: find clusters
Step 2: Add semantics to each
cluster
2.1: If intersects  during t 
stop 
IbisH.
13-14
FloripaS
16-17
11/5/2015
21 of 90
2.2: If no intersection
during t  unknown stop
Tutorial on Spatial and
Spatio-Temporal Data
Mining (ICDM 2010)
Stops (Methods SMot and CB-SMoT)
22
2
DB-SMOT : Direction-based Clustering (Manso 2010)

Input:
trajectories
minDirVariation
minTime
// trajectory samples
// minimal direction variation
// minimum time
maxTolerance

Output: semantic rich trajectories

Method:

For each trajectory

Find clusters with direction variation
higher than minDirVariation

11/5/2015
For a minimal amount of time
23 of 90
Resultados obtidos com os Métodos que Agregam
Semântica – Trajetórias de Barcos de Pesca
2
Resultados obtidos com os Metodos que Agregam
Semântica – Trajetórias de Barcos de Pesca
2
Works Summarized in this part of the Tutorial
Geometric Pattern
Mining Methods
(mining is on sample
points)
Laube 2004, 2005
Hwang 2005
Gudmundson 2006, 2007
Giannotti 2007
Lee 2007
Cao 2006, 2007
Lee 2007, 2008a, 2008b
Li 2010
Semantic Pattern Mining
Behaviour Pattern
Methods (Generate
Mining and
Semantic Trajectories using Interpretation Methods
DM - mining is on Semantic
Trajectories)
Alvares 2007
Zhou 2007
Palma 2008
Bogorny 2009
Bogorny 2010
Manso 2010
Alvares 2010
Giannotti 2009
Baglioni 2009
Ong 2010
CONSTANT: Modelo mais recente para
Trajetórias Semanticas (Bogorny et al. 2012)
2
2
2
3
3