DATA MINING EM TRAJETÓRIAS DE OBJETOS

MÓVEIS

Eduarda Zanette

Greici Baretta Franzen

Mateus Mello

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)

TRAJETÓRIAS DE OBJETOS

M

Figura 1: GPS de um barco de pesca de atum no litoral brasileiro M

DADOS DE TRAJETÓRIASDados espaço-temporaisRepresentados por um conjunto de pontos no

espaço (x, y) em um instante de tempo (t) T = (x1, y1, t1), …, (xn, yn, tn)

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;

DUAS ABORDAGENS SOBRE DATA MINING EM TRAJETÓRIAS

M

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.

DUAS ABORDAGENS SOBRE DATA MINING EM TRAJETÓRIAS

M

Padrões de Movimentos;

Padrões de Frequência;

Padrões Sequenciais;

Classificação;

Detecção de outliers;

DATA MINING BASEADO EM TRAJETÓRIAS GEOMÉTRICAS

M

Atualmente temos cinco padrões de movimentos:

◦Convergência;◦Encontro;◦Flock;◦Liderança e◦Recorrência (recurrence);

PADRÕES DE MOVIMENTOS (LAUBE, 2004)

M

Determinado número de trajetórias que passaram por uma determinada região, não necessariamente no mesmo momento.

PADRÕES DE MOVIMENTOS: CONVERGÊNCIA

M

T1T2

T3

T4

T5

convergência

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)

PADRÕES DE MOVIMENTOS: FLOCK

T2T3

T1

flock M

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)

PADRÕES DE MOVIMENTOS: LIDERANÇA

M

liderança

T2T3

T1

Determinado número de trajetórias que passaram por uma determinada região, se movendo em uma mesma velocidade e direção.

PADRÕES DE MOVIMENTOS: ENCONTRO

M

encontro

T2T3

T1

Determinadas trajetórias visitarem uma determinada região um número k de vezes

PADRÕES DE MOVIMENTOS: RECORRÊNCIA

Mrecorrência

F1

F1F1

F1

Grupos móveis (HWANG, 2005);

Padrão de co-localização (CAO, 2006);

Traclus (HAS, 2007);

PADRÕES DE FREQUÊNCIAS

M

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;

PADRÕES DE FREQUÊNCIAS: GRUPOS MÓVEIS

M

PADRÕES DE FREQUÊNCIAS: GRUPOS MÓVEIS

M

São trajetórias que encontram-se espacialmente próximas;

Janela de tempo;

Movendo em conjunto;

PADRÕES DE FREQUÊNCIAS:CO-LOCALIZAÇÃO

M

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çõesO tempo não é considerado

PADRÕES DE FREQUÊNCIAS:TRACLUS

M

MINERAÇÃO DE TRAJETÓRIAS: DETECÇÃO DE OUTLIERS

G

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.

MINERAÇÃO DE TRAJETÓRIAS: DETECÇÃO DE OUTLIERS

G

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

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

G

Descreve movimentos frequentes, considerando regiões visitadas e a duração do movimento.

Útil para gerenciamento de tráfego em áreas urbanas.

MINERAÇÃO DE TRAJETÓRIAS: PADRÕES SEQUENCIAIS

G

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

MINERAÇÃO DE TRAJETÓRIAS: PADRÕES SEQUENCIAIS

G

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.

MINERAÇÃO DE TRAJETÓRIAS: PADRÕES SEQUENCIAIS

G

Após, é averiguado o tempo de percurso entre as regiões.

time

DATA MINING BASEADO EM TRAJETÓRIAS SEMÂNTICAS

E

A IMPORTÂNCIA DE CONSIDERAR A SEMÂNTICA

DATA MINING BASEADO EM TRAJETÓRIAS SEMÂNTICAS

E

MODELO STOPS E MOVES

E

Primeiro modelo conceitual para trajetóriasSTOPS: 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.

MODELO STOPS E MOVES

E

•TRAJETÓRIAS SEMÂNTICAS SÃO UMA SEQUENCIA DE STOPS AND MOVES

•STOPS SÃO DEPENDENTES DA APLICAÇÃO

Métodos para instanciar o modelo de stops e moves e minerar trajetórias

semânticas

E

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)

IB-SMOT (Alvares, 2007)

E

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 tempo.

IB-SMOT (Alvares, 2007)

E

Verifica para cada trajetória do conjunto de dados se há intersecção com os candidatos a stop em um tempo mínimo.

IB-SMOT

E

IB-SMOT: TABELAS NO BD

E

IB-SMOT: UTILIZAÇÃO

E

Interessante para aplicações de turismo:

-Quais os pontos turísticos visitados por um turista?

-Onde ele comeu? -Onde se hospedou?

CB-SMOT (Palma, 2008)

E

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.

CB-SMOT: PARÂMETROS

E

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

CB-SMOT: IDÉIA GERAL

E

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)

CB-SMOT: IDÉIA GERAL

E

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)

CB-SMOT: PASSOS

E

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

CB-SMOT: PASSOS

E

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 nome.

CB-SMOT

E

CB-SMOT: UTILIZAÇÃO

E

Interessante onde a velocidade é importante.

Exemplo de utilização é em trajetórias de tráfego urbano, para identificar regiões com congestionamento

DB-SMOT (Manso, 2010)

E

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

DB-SMOT: PARÂMETROS

E

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

DB-SMOT: IDÉIA GERAL

E

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

DB-SMOT: IDÉIA GERAL

E

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

DB-SMOT: PASSOS

E

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.

DB-SMOT: PASSOS

E

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.

DB-SMOT

E

DB-SMOT: UTILIZAÇÃO

E

Utilizado em aplicações onde a variação de direção seja um aspecto importante:

Exemplo: aplicação de pesca

CONCLUSÃO

E

Muitas aplicações podem ser beneficiadas pela ciência desenvolvida para análise de dados de trajetórias.

CONCLUSÃO

E

CONCLUSÃO

E

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

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