Cláudio de Souza Baptista
novembro/2008
 Introdução
ao mundo espaço-temporal
 Conceitos básicos
 Exemplos de STDM
 Técnicas de STDM
 Questões em aberto
 Há
muito tempo, pessoas observam
várias entidades móveis, de insetos e
peixes a planetas e estrelas, investigando
seus comportamentos de movimentos
 Tais métodos permitem:
• Observação
• Medição
• Registro
• e análise de movimentos
 Espaço
+ Tempo = Movimento
 Movimento:
• Pessoas
• Animais
 STDM:
• Buscam-se padrões de movimento e modelos
comportamentais de pessoas e animais
• Visando, por exemplo:
 Um melhor planejamento urbano
 Localização de novos negócios
 Geomarketing
 Existem
hoje mais de 1,5 bilhões de
celulares!
 Várias tecnologias de
localização/comunicação:
• GPS (em breve Galileo)
• Wi-Fi
• Bluetooth
• Wi-Max
 Consequência: Big
brother!
 Porém, há
um grande “gap” entre
mobility data e mobility knowlegde
 Segundo J.H. Poincaré:
“Science is built up with facts, as a house is
with stones. But a collection of facts is no
more a science than a heap of stones is a
house.”
 Definição:
• Uma trajetória é o caminho feito por um objeto
móvel através do espaçoonde ele se move
• uma trajetória pode ser vista como uma função
que associa momentos no tempo com posições
no espaco.
• Pode ser visto como um conjunto de pares (time,
location).
 Formas de captura de objetos móveis:
• Time-based recording: positions of entities are
•
•
•
•
recorded at regularly spaced time moments, e.g.
every 5min
Change-based recording: a record is made when the
position of an entity differs from the previous one
Location-based recording: records are made when an
entity comes close to specific locations, e.g. where
sensors are installed
Event-based recording: positions and times are
recorded when certain events occur, in particular,
activities performed by the moving entity (e.g.
calling by a mobile phone)
Various combinations of these basic approaches
 Características
do movimento:
• Time, i.e. position of this moment on the timescale
• Position of the entity in space
• Direction of the entity’s movement
• Speed of the movement (which is zero when the
entity stays in the same place)
• Change of the direction (turn)
• Change of the speed (acceleration)
• Accumulated travel time and distance
 Características
gerais de uma trajetória num
intervalo [t1, t2] :
• Geometric shape of the trajectory (fragment) in the
•
•
•
•
•
space
Travelled distance, i.e. the length of the trajectory
(fragment) in space
Duration of the trajectory (fragment) in time
Movement vector (i.e. from the initial to the final
position) or major direction
Mean, median and maximal speed
Dynamics (behaviour) of the speed
 Dynamics
(behaviour) of the speed
• Periods of constant speed, acceleration,
deceleration and stillness
• Characteristics of these periods: start and end
times, duration, initial and final positions, initial
and final speeds, etc.
• Arrangement (order) of these periods in time
 Dynamics
(behaviour) of the directions
• Periods of straight, curvilinear, circular movement
• Characteristics of these periods: start and end times,
initial and final positions and directions, major
direction, angles and radii of the curves, etc.
• Major turns (‘turning points’) with their
characteristics: time, position, angle, initial and final
directions, and speed of the movement in the
moment of the turn
• Arrangement (order) of the periods and turning
points in time
 Comparando
trajetórias (funções):
• Equality or inequality
• Order (less or greater, earlier or later, etc.)
• Distance (in space, in time or on any numeric
scale)
• Topological relations (inclusion, overlapping,
crossing, touching, etc.)

Comparando trajetórias (funções): Spatial and
temporal relations
• Co-location in space, full or partial (i.e. the trajectories
consist of the same positions or have some positions in
common)
 (a) Ordered co-location: the common positions are attained in
the same order
 (b) Unordered co-location: the common positions are attained
in different orders
• Co-existence in time, full or partial (i.e. the trajectories
are made during the same time period or the periods
overlap)
• Co-incidence in space and time, full or partial (i.e. same
positions are attained at the same time)
• Lagged co-incidence, i.e. entity e attains the same
positions as entity e but after a time delay Δt
1
0

Exemplos:
• Com que frequência os animais param?
• Quais rotas são regularmente usadas por caminhões?
• Estiveram os dois aviões próximos de colidir?
• Encontre movimentos estranhos de navios, indicando despejo ilegal de dejetos
• Quais foram as posições dos objetos e , e , . . . ,e no moment t?
1
2
n
• Qual era a distribuição espacial dos objetos e , e , . . . ,e no momento t?
1
2
n
• Quais objetos moveram-se como especificado no padrão P durante o time
interval de t a t ?
• Em quais períodos de tempo os objetos e , e , . . . , e moveram-se como
especificado pelo padrão P?
1
2
1
2
n
 Exemplos:
• Quais eram as posições relativas dos objetos e1 e e2
1
•
2
no tempo t?
Como a localização do objeto e mudou do tempo t
para o tempo t ?
Qual a diferença nos tempos quando o objeto e visitou
os lugares p e p ?
Quais são as semelhanças e diferenças entre os
movimentos dos objetos e and e no intervalo de t a
t?
Compare os intervalos de tempo quando o objeto e
(ou grupo de objetos E) moveu-se de acordo com o
padrão P e de acordo com o padrão P .
1
2
•
1
•
2
1
2
1
2
•
1
2
 Exemplo: imagine
que cada vez que
alguém usa o celular são gravados
registros da forma:
• users entering a cell – (userID, time, cellID, in)
• users exiting a cell – (userID,time, cellID, out)
• Ou, com GPS:
• user’s position within a cell – (userID, time, cellID,
X,Y)
 Neste
contexto, o processo de
descoberta de conhecimento geográfico
é composto de 3 passos:
• Reconstrução de trajetória
• Extração de conhecimento
• Entrega da informação
 Extração
de conhecimento:
• Questões básicas:
 Quais tipos de padrões podem ser extraídos de
trajetórias?
 Quais métodos e algoritmos deveriam ser aplicados
para extrair estas trajetórias?

Técnicas p/ Extração de conhecimento:
• Clustering
• Padrões frequentes
• Classificação

Clusters de trajetórias
 Padrão
de trajetórias
 Predição
de trajetórias

Entrega do conhecimento (Análise)
• Planning traffic and public mobility systems in
•
•
•
•
•
•
metropolitan areas
Planning physical communication networks, such as
new roads or railways
Localising new services in our towns
Forecasting traffic-related phenomena
Organising postal and logistics systems
Timely detecting problems that emerge from the
movement behaviour
Timely detecting changes that occur in the movement
behaviour
 Uma
área ainda em gestação!
 Aplicação das técnicas de mineração a
objetos móveis
 Ex.:
• Encontre todos os engarrafamentos em Recife entre
7 e 8 horas
• Pode-se construir regras do tipo:
se engarrafamento(Olinda,t)
então engarrafamento(Paulista, t + k)
Quantas trajetótias atravessarão Campina Grande
amanhã às 17h?
 Clustering
• clustering tenta agrupar indivíduos com
características similares
• Distance-based trajectory clustering
 Descobrir quais clusters e quem pertence a qual
cluster
 Abordagem básica para definir uma distância é
considerar similar aqueles pares de objetos que
seguem aproximadamente a mesma trajetória espaçotemporal
 Clustering
 Responder questões do tipo:
 Quais indivíduos de uma população se movem
conjuntamente?
 Clustering
- Observações:
• clustered trajectories seguem caminhos similares
como pode ser visto por suas projeções espaciais,
mas com velocidades diferentes e tempos diferentes
• Uma maneira simples de modelar este tipo de
comparação é representar trajetórias como vetores
de coordenadas de tamanho fixo por meio de
alguma distância, por exemplo Euclidean distance
• Podemos ignorar o tempo. Ex: Find groups of
individuals moving along the same roads
 Padrões
Espaço-temporais
• Busca representações de comportamento de
objetos ou grupo de objetos.
• Extração de padrões:
Se Length(trajectory) < 50m
então average speed(trajectory) < 40km

Padrões Espaço-temporais
• Novamente o problema clássico de DM: escolha dos
atributos:
• Agregados espacial e/ou temporal (o comprimento de
um caminho, a quantidade de tempo gasta no centro da
cidade, velocidade minima/máxima/média, a direção
mais frequente usada, etc.),
• Eventos espaciais (visitar alguma região pré-definida,
visitar duas vezes um mesmo lugar,
• Eventos spatiotemporals (monobras temporais como Uturns, parada brusca, aceleração abrupta. Ex.
 visits(x,Market square)→abrupt stop(x)→perform U-turn(x)

Ocurrence retrieval
• O usuário tem um padrão em mente e consulta
por todas as suas ocorrências (inverse query)
• Ex.: Find all trajectories that pass location A
between time t1 and t2

Predição de trajetórias
• Quo-Vadis?
• Anticipar a movimentação de individuos ou
grupos de objetos habilitam estes sistemas para
tomar ações antecipatórias em caso de atrasos,
evitando aglomerações, ou permitindo a entrega
do serviço no tempo desejado
• Ex.: location-based services can offer more
sophisticated services when knowing which
locations a user will pass and whether the user is
on the way to work or to the supermarket.

Predição de Densidade
• A densidade de objeto de uma dada área é definida
como o número de objetos dentro da área na
proporção do tamanho da área num dado ponto no
tempo
• Permite, por exemplo, identificar regiões densas,
como engarrafamento em tráfego
• Para calcular densidade, usa-se um cubo espaçotemporal, onde cada célula contém a densidade de
uma dada área, num dado ponto no tempo.
• Para predição, assume-se movimento linear dos
objetos e computa-se as densidades futuras por
interpolação

Predição de Alcançabilidade
• Reach is a time-dependent measure about the
publicity of a location within some population
• Reach is not restricted to a single location, but
can span a network of sites
• It is defined as the proportion of population that
passes at least one of the locations within the
network within a given period of time

Predição de Eventos
• Problema de predizer eventos espaço-temporais
que são associados com outras características
• Exemplo, authors predict the probability that
some crime will be committed within a given
region and time interval based on locations,
times and socio-economic features of past
incidents

Classificação de Trajetórias
• Como um caminho de um turista difere de um
habitante local?
• Outra tarefa de classificação é inferir o meio de
transporte de uma trajetória. Permite consultas
do tipo:
 What portion of a person’s daily motion can be
attributed to private vehicles?
 Which streets outside of the city centre are
predominantly used by pedestrians?

Questões em aberto:
• Privacidade
• Incerteza
• Tratamento de erro
• Trajectory DW
• Trajectory Data Models
• Query Languages
• Técnicas de Indexação
• Técnicas de Armazenamento