Métodos para instanciar stops e moves
• IB-SMoT
• CB-SMoT
• DB-SMoT
A Clustering-based Approach for
Discovering Interesting Places in
Trajectories (Andrey Palma, Vania Bogorny,
Bart Kuijpers and Luis Otavio Alvares), Proc.
of the ACM 23rd Annual Symposium on
Applied Computing, (ACM-SAC'08), Fortaleza,
Brazil, 16-20 March 2008, p.863-868.
79 citações em 18/10/2012
A Clustering-Based Approach for
Discovering Interesting Places in
Trajectories
Andrey Luis T. Palma
Prof Dr. Luis Otavio Alvares (Orientador)
Prof Dra. Vania Bogorny
(Co-Orientadora)
Objetivo
• Considerar a velocidade no processo de
atribuição de semântica

Uso de clusterização para identificação de
trechos lentos da trajetória
(cluster=subtrajetória com baixa velocidade)
Algoritmo CB-SMoT
Dois passos principais:
1. Encontrar as partes lentas da trajetória (clusters)
2. Atribuir mais semântica aos clusters encontrados
CB-SMoT: Clusterização

Clusters são encontrados dentro da
trajetória – as partes lentas da trajetória

Pontos são tratados tanto espacial como
temporalmente
Idéia geral
• Encontrar as partes (subtrajetórias) lentas da
trajetória
• Partes lentas = com velocidade média menor que
um certo limite
– parâmetro maxAvgSpeed (relativo a velocidade média
da trajetória)
• Partes lentas tem que ter uma duração mínima
– Parâmetro minTime
• Não queremos pontos de alta velocidade no cluster
– Parâmetro maxSpeed (relativo a velocidade média da
trajetória)
y
Exemplo de trajetória
x
Passos do algoritmo:
1.
2.
3.
Calcula-se a velocidade em cada ponto (depende do tipo de dado de entrada)
Inicia-se o processamento com pontos de baixa velocidade (eficiência): p11 no
exemplo
A partir deste ponto, pega-se, sucessivamente, o seu vizinho mais lento
(desde que sua velocidade não seja superior a maxSpeed e o ponto não
pertença a outro cluster): p10,p12,p9,p13, p14,… até que a subtrajetória
tenha duração maior que minTime
velocidade
p20
p7
p19
p4 p5
p1
p3
p2
p6
p8
p13
p14
p18
p15
p9
maxSpeed
p12
p17
p10
p11
p16
tempo
Passos do algoritmo (cont.):
4.
Se a velocidade média da subtrajetória não for superior a maxAvgSpeed,
temos um cluster, que vai ser expandido com o vizinho mais lento que não
pertença a outro cluster, enquanto a sua velocidade média não for superior
a maxAvgSpeed
velocidade
p20
p7
p19
p4 p5
p1
p3
p6
p8
p13
p14
p18
p15
p9
maxSpeed
p12
p2
p17
p10
p11
minTime
p16
tempo
Resultado
velocidade
p20
p7
p19
p4 p5
p1
p3
p6
p8
p13
p14
p18
p15
p9
maxSpeed
p12
p2
p17
p10
p11
p16
tempo
CB-SMoT: Tolerância a perdas de sinal
1)
Trajetória entra em uma
contrução
2) Sinal do GPS é perdido na
construção
3) Ao se recuperar o sinal
é possível identificar uma
baixa velocidade naquele
período de perda
Algoritmo CB-SMoT
CBSMoT(T,avg,MT,SL,A)
INPUT:
T : Trajectory avg: maxAverageSpeed
A : Application
MT : minTime
1: SpeedClustering(T,avg,MT,SL);
2: T.unifyAdjacentClusters();
3: Points = T.clusterPoints();
4: Points.sortByTime();
5: FOR EACH p IN Points DO
6:
IF p intersects some candidate stop C THEN
7:
List.add(new Association(p,C));
8:
ELSE
9:
List.add(new Association(p,null));
10:
ENDIF
11: ENDFOR
12:StopsDiscovering(List);
SL : maxSpeed
CB-SMoT: Atribuição de Semântica
• Primeiro significado semântico é intrínseco
ao passo de clusterização

Agregação de mais significado depende da
aplicação (conjunto de RF)
Algoritmo CB-SMoT
passo 1: determinar os clusters
Unknown stop
Louvre
passo 2: adicionar semântica a
cada cluster
09-12
2.1: se intersecta  por t 
stop 
IbisH.
13-14
Orsay
16-17
2.2: senão  unknown stop
Análise dos parâmetros
• Variação do parâmetro minTime
• Variação do parâmetro maxAvgSpeed
• Variação do parâmetro maxSpeed
Variação do MinTime com
maxAvgSpeed = 0.8 e maxSpeed = 1.0
MinTime =
90 s
MinTime =
120 s
MinTime =
150 s
Variação do maxAvgSpeed com
MinTime = 30s e maxSpeed = 1.0
maxAvgSpeed = 0.6
maxAvgSpeed = 0.7
maxAvgSpeed = 0.8
Variação do parâmetro maxSpeed
maxAvgSpeed = 0.7
MinTime = 30s
maxSpeed = 0.9
maxAvgSpeed = 0.7
minTime = 30s
maxSpeed = 1.5
maxAvgSpeed = 0.8
minTime = 30s
maxSpeed = 1.0
maxAvgSpeed = 0.8
minTime = 30s
maxSpeed = 1.5
Clusters em
Copacabana
(a)
(b)
(a) 16:00 – 16:10
(b) 17:46 – 18:00
(c) 09:02 – 09:14
(c)
(d)
(d) 08:04 – 08:10
Exemplo com dados reais do Rio de Janeiro
Anexos
Anexos
Anexos
• DB-SMoT: a Direction-based spatio-temporal
clustering method (Jose Antonio Manso,
Valeria Times, Gabriel Oliveira, Luis Otavio
Alvares and Vania Bogorny), Proc. of the Fifth
IEEE International Conference on Intelligent
Systems (IEEE IS 2010), London, 7-9 July 2010.
Motivação
• Análise em trajetórias de barcos de pesca com o objetivo de
determinar as zonas onde o barco estava efetivamente
pescando
• Tentativas com o CB-SMoT não foram boas:
Motivação
• Especialista em pesca diz que durante a pesca o
barco muda bastante de direção, o que não ocorre
quando ele está navegando de um ponto a outro
• Idéia geral:
Fazer um algoritmo “similar ao CB-SMoT”, em que o
atributo importante fosse a variação da direção
Algoritmo DB-SMoT
Dois passos principais:
1. Encontrar as partes da trajetória com grande
variação de direção (clusters)
2. Atribuir mais semântica aos clusters encontrados
(semelhante ao CB-SMoT)
Passo 1: clusterização - Idéia geral
• Os clusters correspondem a partes da trajetória em que há
grande variação na direção
• Grande variação = variação de direção não inferior a um certo
limite
 parâmetro minDirChange
• Cluster tem que ter uma duração mínima
 Parâmetro minTime
• Tolerância, em número máximo de pontos contíguos sem
grande variação da direção, aceitável em um cluster.
 Parâmetro maxTol
Variação de direção
pi
pi-1

pi+1
variação da direção
p5
p3
minDC
p4
p6
p8
p9
p10
p7
p2
p1
p14
p11
p12
p15
p13
tempo
Exemplo de formação de cluster com maxTol = 1
variação da direção
p5
p3
minDC
p4
p6
p8
p9
p10
p7
p2
p1
p14
p11
p12
p15
p13
tempo
Exemplo da pesca (dados reais)
Outro exemplo de trajetória de barco
de pesca
Pesca efetiva
Gerado pelo DB-SMoT