DATA MINING EM
TRAJETÓRIAS DE
OBJETOS MÓVEIS
Eduarda Zanette
Greici Baretta Franzen
Mateus Mello
TRAJETÓRIAS DE OBJETOS

Aparelhos GPS, celulares, smartphones etc...

Dispositivos móveis deixam traços digitais
que podem ser coletados como trajetórias,
descrevendo a mobilidade de seus usuários
(BOGORNY);

Permite o rastreamento do indivíduo

Novo tipo de dado (Trajetória de Objetos
Móveis)
M
Figura 1: GPS de um barco de pesca de atum no litoral brasileiro
M
DADOS DE TRAJETÓRIAS
Dados espaço-temporais
 Representados por um conjunto de pontos no
espaço (x, y) em um instante de tempo (t)
 T = (x1, y1, t1), …, (xn, yn, tn)

DUAS ABORDAGENS SOBRE DATA
MINING EM TRAJETÓRIAS

Data Mining Espaço-Temporal baseado na
geometria da trajetória;
◦ Análise baseada somente na forma física da
trajetória;
◦ É considerado apenas as propriedades
geométricas (espaço e tempo);
◦ Agrupamento das trajetórias baseado em
algorítmos de densidade;
M
DUAS ABORDAGENS SOBRE DATA
MINING EM TRAJETÓRIAS

Data Mining Espaço-Temporal baseado na
semântica da trajetória;
◦ Baseado nas informações semânticas da
trajetória;
◦ Lida com dados esparsos;
◦ Pré-processamento dos dados para
enriquecimento das trajetórias.
M
DATA MINING BASEADO EM
TRAJETÓRIAS GEOMÉTRICAS

Padrões de Movimentos;

Padrões de Frequência;

Padrões Sequenciais;

Classificação;

Detecção de outliers;
M
PADRÕES DE MOVIMENTOS
(LAUBE, 2004)

Atualmente temos cinco padrões de
movimentos:
◦
◦
◦
◦
◦
Convergência;
Encontro;
Flock;
Liderança e
Recorrência (recurrence);
M
PADRÕES DE MOVIMENTOS:
CONVERGÊNCIA

Determinado número de trajetórias que
passaram por uma determinada região,
não necessariamente no mesmo
momento.
T1
T2
T4
convergência
T3
T5
M
PADRÕES DE MOVIMENTOS:
FLOCK

Determinadas trajetórias que passaram
por uma determinada região, se movendo
em uma mesma direção durante um
intervalo de tempo (ex: trânsito)
flock
M
PADRÕES DE MOVIMENTOS:
LIDERANÇA

Determinado número de trajetórias que
passaram por uma determinada região, se
movendo em uma mesma direção e ao menos
uma trajetória está liderando as outras (ex:
migração de pássaros)
liderança
M
PADRÕES DE MOVIMENTOS:
ENCONTRO

Determinado número de trajetórias que
passaram por uma determinada região, se
movendo em uma mesma velocidade e
direção.
encontro
M
PADRÕES DE MOVIMENTOS:
RECORRÊNCIA

Determinadas trajetórias visitarem uma
determinada região um número k de
vezes
F1
F1
F1
F1
recorrência
M
PADRÕES DE FREQUÊNCIAS

Grupos móveis (HWANG, 2005);

Padrão de co-localização (CAO,
2006);

Traclus (HAS, 2007);
M
PADRÕES DE FREQUÊNCIAS:
GRUPOS MÓVEIS
Os grupos considerados padrões são
determinados através de uma distância
mínima entre as trajetórias e um tempo
mínimo;
 Não é considerado a direção;
 A determinação dos grupos pode ser feita
através do algoritmo Apriori;

M
PADRÕES DE FREQUÊNCIAS:
GRUPOS MÓVEIS
M
PADRÕES DE FREQUÊNCIAS:
CO-LOCALIZAÇÃO

São trajetórias que
encontram-se
espacialmente
próximas;

Janela de tempo;

Movendo em
conjunto;
M
PADRÕES DE FREQUÊNCIAS:
TRACLUS

TRACLUS – Trajectory Clustering;


Baseado em algoritmos de densidade;
Divide a trajetória em subgrupos com T de
tamanho (parâmetro);
O agrupamento ocorre pela proximidade
destes segmentos;
Interessante para estudo da trajetórias de
furações
O tempo não é considerado



M
MINERAÇÃO DE TRAJETÓRIAS:
DETECÇÃO DE OUTLIERS
Outlier: trajetória muito diferente das demais do
conjunto.
Uso na identificação de carros ou pessoas com
comportamento suspeito, fraude em cartão de
crédito.
Vários métodos analisam a trajetória como um
todo.
G
MINERAÇÃO DE TRAJETÓRIAS:
DETECÇÃO DE OUTLIERS
Método descrito por Lee (2008) divide as
trajetórias em subtrajetórias e as analisa
comparativamente umas com as outras.
É o framework
Partition—and-Detect Ou Algoritmo TraOD
G
MINERAÇÃO DE TRAJETÓRIAS:
DETECÇÃO DE OUTLIERS
G
MINERAÇÃO DE TRAJETÓRIAS:
CLASSIFICAÇÃO
Classificar objetos de acordo com suas trajetórias
e outras características. Reconhecimento de
padrões.
Muito útil para classificação de navios, no controle
de fronteiras, da pesca, poluição.
Alguns métodos também analisam a trajetória
como um todo.
G
MINERAÇÃO DE TRAJETÓRIAS:
CLASSIFICAÇÃO
Método de Lee (2008) verifica que algumas
características tendem a aparecer somente em
determinados segmentos.
G
MINERAÇÃO DE TRAJETÓRIAS:
CLASSIFICAÇÃO
Duas Fases:
•
Baseada na região
(forma clusters)
•
Baseada na trajetória
(cluster por trajetória)
G
MINERAÇÃO DE TRAJETÓRIAS:
PADRÕES SEQUENCIAIS
Descreve movimentos frequentes, considerando
regiões visitadas e a duração do movimento.
Útil para gerenciamento de tráfego em áreas
urbanas.
G
MINERAÇÃO DE TRAJETÓRIAS:
PADRÕES SEQUENCIAIS
Padrões de trajetórias = conjunto de trajetórias
individuais que partilham a propriedade de visitar
a mesma sequencia de lugares, com tempo de
viagem semelhante.
Padrão a
Ticen -5min-
praça XV
-30min-
Igreja Matriz
Padrão b
Ticen -5min-
Beiramar
-10min-
UFSC
G
MINERAÇÃO DE TRAJETÓRIAS:
PADRÕES SEQUENCIAIS
Primeiro as trajetórias são transformadas de
pontos para regiões e com as regiões de
interesse formadas, as trajetórias são novamente
inseridas.
G
MINERAÇÃO DE TRAJETÓRIAS:
PADRÕES SEQUENCIAIS
Após, é averiguado o tempo de percurso entre as
regiões.
time
G
DATA MINING BASEADO EM
TRAJETÓRIAS SEMÂNTICAS
A IMPORTÂNCIA DE CONSIDERAR A SEMÂNTICA
E
DATA MINING BASEADO EM
TRAJETÓRIAS SEMÂNTICAS
E
MODELO STOPS E MOVES




Primeiro modelo conceitual para trajetórias
STOPS: partes importantes da trajetória do
ponto de vista da aplicação, onde o objeto
móvel é considerado parado por um intervalo
de tempo
MOVES: parte da trajetória entre dois stops
consecutivos ou entre um stop e o início/fim
da trajetória.
Todas as partes da trajetória que não são
stops, são definidos como moves.
E
MODELO STOPS E MOVES
•TRAJETÓRIAS SEMÂNTICAS SÃO UMA SEQUENCIA DE
STOPS AND MOVES
•STOPS SÃO DEPENDENTES DA APLICAÇÃO
E
Métodos para instanciar o modelo de
stops e moves e minerar trajetórias
semânticas

IB-SMOT (Intersection-Based Stops and
Moves of Trajectories)

CB-SMOT (Clustering-Based Stops and
Moves of Trajectories)

DB-SMOT (DIRECTION-based Stops and
Moves of Trajectories)
E
IB-SMOT (Alvares, 2007)
STOPS: partes de uma trajetória que
interceptam um objeto geográfico de
interesse por um tempo mínimo
 Objetos geográficos de interesse =>
candidatos a stops.
 Candidato a stop: (Rc, ∆c)
Rc é a geometria do objeto geográfico de
interesse e ∆c é a duração mínima de
E
tempo.

IB-SMOT (Alvares, 2007)

Verifica para cada trajetória do conjunto
de dados se há intersecção com os
candidatos a stop em um tempo mínimo.
E
IB-SMOT
E
IB-SMOT: TABELAS NO BD
E
IB-SMOT: UTILIZAÇÃO

Interessante para aplicações de turismo:
-Quais os pontos turísticos visitados por
um turista?
-Onde ele comeu?
-Onde se hospedou?
E
CB-SMOT (Palma, 2008)

Baseado em clusterização

Identifica partes da trajetória em que a
velocidade do objeto móvel é menor do
que no restante da trajetória, sendo
considerada a média da velocidade no
trecho.
E
CB-SMOT: PARÂMETROS
minTime: tempo mínimo de uma
subtrajetória com baixa velocidade para
que seja um stop
 maxAvgSpeed:velocidade média
máxima de uma subtrajetória para ser
considerada um cluster
 maxSpeed: velocidade instantânea
máxima aceitável dentro de um cluster

E
CB-SMOT: 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)
E
CB-SMOT: IDÉIA GERAL

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)
E
CB-SMOT: PASSOS

Formação de clusters pelos pontos da
trajetória onde a velocidade está abaixo
da definida (calculada pelo valor passado
multiplicado pela velocidade média) em
um tempo mínimo

Intersecção dos clusters com os
candidatos à stops
E
CB-SMOT: PASSOS

Para cada intersecção, é verificada se a
duração dessa respeitou o tempo mínimo
definido para o objeto geográfico associado.
Se respeitar, então será considerado um
stop rotulado pelo nome do objeto
geográfico, do contrário, será um stop
desconhecido, definido como Unknown stop.

Verificar se dois ou mais stops desconhecidos
se interceptam. Neste caso, terão o mesmo
E
nome.
CB-SMOT
E
CB-SMOT: UTILIZAÇÃO

Interessante onde a velocidade é
importante.

Exemplo de utilização é em trajetórias de
tráfego urbano, para identificar regiões
com congestionamento
E
DB-SMOT (Manso, 2010)

Baseado em clusterização

Clusters são formados por partes da
trajetória em que há variação de direção,
a qual deve ser maior que um
determinado valor, informado como
parâmetro
E
DB-SMOT: PARÂMETROS

minDC: variação mínima da direção

minTime: duração mínima de uma
subtrajetória com variação da direção
para ser considerada um stop

maxTol: tolerância, em número máximo
de pontos contíguos sem grande variação
da direção, aceitável em um cluster
E
DB-SMOT: 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
E
DB-SMOT: IDÉIA GERAL

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
E
DB-SMOT: PASSOS

Verifica a variação da direção de dois em dois
pontos da trajetória.
-Quando a variação ultrapassar o minDC,
então os pontos são adicionados ao cluster.
-Se for inferior a minDC, observa maxTol, para
ver se o ponto que não mudou
significativamente de direção foi ruído ou se
a mudança de direção acabou.
E
DB-SMOT: PASSOS

Confere se os pontos que tiveram
suficiente variação de direção,
respeitaram o minTime
-Em caso positivo, considera-se a
subtrajetória um cluster de grande
variação de direção.
E
DB-SMOT
E
DB-SMOT: UTILIZAÇÃO


Utilizado em aplicações onde a variação
de direção seja um aspecto importante:
Exemplo: aplicação de pesca
E
CONCLUSÃO

Muitas aplicações podem ser beneficiadas
pela ciência desenvolvida para análise de
dados de trajetórias.
E
CONCLUSÃO
E
CONCLUSÃO
Algoritmos de mineração de dados que
considerem informações semânticas e de
contexto da aplicação é uma área de
pesquisa recente
 Trabalhos futuros: projeto europeu SEEK
envolvendo Brasil, Itália e Grécia

E
REFERÊNCIAS






Introdução a Trajetórias de Objetos Móveis, 2012. Vania Bogorny, Fernando José Braz;
Conjunto de slides para curso de pós-graduação em análise de trajetórias de objetos
móveis. Vania Bogorny;
Artigo “A model for enriching trajectories with semantic geographical information”,
Alvares (2007);
Artigo “Trajectory Outlier Detection: A Partition-and-Detect Framework” , Jae-Gil Lee,
Jiawei Han, Xiaolei Li (2008);
Artigo “TraClass: Trajectory Classification Using Hierarchical Region-Based and
Trajectory-Based Clustering”, Jae-Gil Lee, Jiawei Han, Xiaolei Li, Hector Gonzalez (2008)
Artigo “Trajectory Pattern Mining”, Fosca Giannotti, Mirco Nanni, Dino Pedreschi, Fabio Pinelli
M