TRACTS T RA JECTORY C LASSIFICATION USING T IME S ERIES Aluno: Irineu Junior Pinheiro dos Santos Orientador: Luis Otávio de Campos Álvares

TRACTSTRAJECTORY CLASSIFICATION USING TIME SERIES

Aluno: Irineu Junior Pinheiro dos Santos

Orientador: Luis Otávio de Campos Álvares

ESTRUTURA DE APRESENTAÇÃO

Introdução; Conceitos Utilizados; O Método TRACTS; Experimentos Realizados; Conclusão.

2/54

INTRODUÇÃO – MOTIVAÇÃO

Grande disponibilidade de dados de trajetórias: GPS; Celulares (triangulação e GPS); RFID;

Análise dos padrões comportamentais dos objetos móveis a partir de suas trajetórias.

3/54

INTRODUÇÃO – MOTIVAÇÃO

Diversos trabalhos tem sido propostos para realizar análise de dados espaço-temporais;

Poucos tem utilizado o conceito de classificação.

4/54

INTRODUÇÃO – OBJETIVO DO TRABALHO

5/54


Introdução;Conceitos Utilizados; Trabalhos Relacionados; O Método TRACTS; Experimentos Realizados; Conclusão.

6/54

CONCEITOS – TRAJETÓRIA

7/54

CONCEITOS - CLASSIFICAÇÃO

Produzir um modelo de classificação;

Classificar novos registros.

8/54

CONCEITOS - CLASSIFICAÇÃO

Avaliação do modelo usando a Matriz de Confusão, gerando métricas: Acurácia; Erro; Taxa de VP; Taxa de VN

9/54

CONCEITOS – SÉRIES TEMPORAIS

Séries temporais consistem de sequência de valores ou eventos obtidos sobre repetidas medidas de tempo;

Muitas aplicações envolvendo séries temporais tem sido utilizadas.

10/54

CONCEITOS – SÉRIES TEMPORAIS – TRANSFORMAÇÕES

Discrete Fourier transform (DFT) (Faloutsos et. al., 1994 );

Piecewise linear e Piecewise constant models (PAA) (Chakrabarti et. al, 2002);

Haar Wavelet (Haar, 1910). Adaptative piecewise constant approximation

(APCA) (Geurts, 2001);11/54

CONCEITOS – SAX

Realiza o tratamento de séries temporais: Facilita a mineração

de dados através do uso de árvores de sufixo, hashing, modelos de markov, etc;

Permite o uso de algoritmos de processamento de texto e de bioinformática.

12/54

CONCEITOS – SAX

Primeiro é realizada a conversão da série temporal para uma representação PAA;

Após, é realizada a conversão da representação PAA para símbolos;

Manter a equiprobabilidade.

13/54

CONCEITOS – SAX – MÚLTIPLAS SÉRIES TEMPORAIS

14/54

CONCEITOS – BITMAPS DE SÉRIES TEMPORAL

Ou Time Series Bitmap (TSB), proposto por (Kumar et. al., 2005) e permite o tratamento de strings;

Transformar sequências de caracteres em mapas de bits.

O tamanho da matriz de bits gerada é definido a partir de dois parâmetros: Dimensão (); Resolução ou Profundidade ();

15/54


Três mapas de bits com dimensão e três profundidades distintas.

16/54


Mapa de bits gerado para as strings c1: baccbdca e c2: dcddaabb.

17/54


Introdução;Conceitos Utilizados;

Trabalhos Relacionados; O Método TRACTS; Experimentos Realizados; Conclusão.

18/54

TRABALHOS RELACIONADOS

Trabalhos focados para um domínio específico: (Panagiotakis et. al., 2009): baseado na similaridade;

Depende fortemente da relação espacial entre as trajetórias; (Lee & Hoff, 2007): descobrir a atividade esportiva;

Além de uma grande necessidade de parametrização, necessita de diversas trajetórias semelhantes para caracterizar uma atividade esportiva;

(Zheng et. al., 2008): descobrir o meio de transporte; Apesar do bom processo de classificação, parte da acurácia

é dependente da semântica de transição específica entre meios de transporte, prejudicando a sua generalização;

(García et. al., 2006): identificação do modo de voo; O trabalho realiza com muita competência a classificação do

modo de voo a partir das trajetórias de aviões, mas os filtros de Kalmam utilizados acabam sendo muito especializados nessa tarefa, prejudicando também a generalização do método.

19/54


Um método geral foi proposto por (Lee, Han, Gonzalez & Li, 2008), que introduziu o método TraClass;

O processo é dividido em duas etapas: Clusterização; Classificação:

Trajectory Based (TB): Fornece rótulos de classe para trajetória com base na etapa anterior;

Region Based (RB): Descobre as regiões com maior número de trajetórias de uma única classe, permitindo estabelecer uma região para aquela classe.

20/54


Clusterização Classificação

21/54


Introdução;Conceitos Utilizados;Trabalhos Relacionados;

O Método TRACTS; Experimentos Realizados; Conclusão.

22/54

O MÉTODO TRACTS

Objetivo: construir um método capaz de realizar classificação de trajetórias utilizando algoritmos tradicionais de classificação;

Problema: como utilizar algoritmos tradicionais de classificação com dados espaço-temporais? Formato ; Quais atributos? Quais classes?

23/54

O MÉTODO TRACTS

24/54

O MÉTODO TRACTS – PREPARAÇÃO

Formata os dados geográficos dos dispositivos de rastreamento para um formato padrão ;

Reconstrói as trajetórias de acordo com a necessidade (ex.: segmenta as trajetórias);

Elimina os ruídos das trajetórias.

25/54

O MÉTODO TRACTS – CARACTERIZAÇÃO

Realiza a extração dos valores das características da trajetória;

Fornece a semântica necessária para análise no processo de classificação;

Quais devem ser as características extraídas de cada uma das trajetórias do conjunto de dados?

26/54


Trajetórias de objetos móveis sempre terão algumas características espaço-temporais, tais como velocidade, aceleração e direção.

27/54


Características globais: Comprimento; Duração; Deslocamento;

Características locais: Velocidade entre dois pontos consecutivos; Aceleração entre duas velocidades consecutivas; Direção entre dois pontos consecutivos; Variação da direção entre duas direções

consecutivas;

28/54


Para cada uma das características locais, para cada trajetória, é realizada a transformação dos valores das características para séries temporais.

29/54

O MÉTODO TRACTS – TRANSFORMAÇÃO

Primeiramente, as séries temporais são transformadas pelo método SAX:

Todas as séries temporais são normalizadas para cada característica;

Cada série temporal é transformada em uma sequência de caracteres.

30/54


As sequências de caracteres são transformadas em mapas de bits através do método TSB;

31/54


Velocidade_aa: 15,38

Velocidade_ab: 34,62

Velocidade_ba: 30,77

Velocidade_bb: 19,23

32/54

O MÉTODO TRACTS - TRANSFORMAÇÃO Velocidade_a Velocidade_b Velocidade_c Aceleração_a Aceleração_b Aceleração_c Direção_a Direção_b Direção_c ... Comprimento Deslocamento Duração ... Classe

33/54

O MÉTODO TRACTS – CLASSIFICAÇÃO

Utiliza os atributos como entrada nos algoritmos de classificação tradicionais;

O modelo de classificação é gerado e avaliado; Podem ser gerados tantos modelos quanto forem

necessários, através da execução de diversos algoritmos, até que seja gerado um modelo de classificação com a acurácia esperada.

34/54


Introdução;Conceitos Utilizados;Trabalhos Relacionados;O Método TRACTS;

Experimentos Realizados; Conclusão.

35/54

EXPERIMENTOS REALIZADOS

A validação do método TRACTS foi realizada com os mesmos dados do método proposto pelo grupo de Jiawei Han (Lee et. al., 2008);

Foram utilizadas três bases de dados de trajetórias: Conjunto de trajetórias de três tipos de animais

distintos, rastreados por RFID; Trajetórias de navegação de dois barcos; Trajetórias de furacões.

36/54

EXPERIMENTOS REALIZADOS A classe do conjunto de dados de animais era cada um

dos tipos de animais: Alce; Gado; Veado;

Nos dados dos barcos a classe foi o nome dos mesmos: Point Sur; Point Lobos;

Para os furacões, a classe foi a força máxima atingida por cada um dos furacões: F1; F2; F3; F4; F5.

37/54


Para cada um dos conjunto de dados, as trajetórias, no formato foram tratadas para eliminação de ruído e sofreram processo de segmentação, conforme necessário;

Foram extraídas as características de cada uma das trajetórias (locais e globais);

As características locais foram transformadas em séries temporais, as quais sofreram um processo de transformação pelo processo SAX e TSB;

Foram montados os arquivos de entrada para a ferramenta Weka e houve o processo de classificação.

38/54

EXPERIMENTOS REALIZADOS – ARQUIVO WEKA

39/54

EXPERIMENTOS REALIZADOS – RESULTADO WEKA

40/54

EXPERIMENTOS REALIZADOS – RESULTADOS

Domínio # Trajetórias

# Pontos # Séries Temporai

s

Tempo Geração

Animais 253 287134 1012 634,06s

Barcos 404 56622 1616 61,92s

Furacões 1367 39777 5468 161,89s

41/54

EXPERIMENTOS REALIZADOS – RESULTADOS (ANIMAIS)

Configuração do

método

Total de atributos utilizados

Acurácia de

classificação

Algoritmo utilizado Tempo geração do modelo de

classificação

TRACTS.3.1

16 94,07%Kstar 0,01

TRACTS.3.2

40 94,47%Adaboost+BayesNet 0,6

TRACTS.3.3

112 95,26%Bagging+SMO 3,6

TRACTS.3.4

328 95,65%SMO 0,31

TRACTS.3.5

976 95,26%SMO 0,42

TRACTS.3.6

2920 95,26%SMO 0,69

TRACTS.4.1

20 97,23%SMO 0,17

TRACTS.4.2

68 95,26%Bagging+RandomFore

st2,8

TRACTS.4.3


TRACTS.4.4

1028 95,65%Bagging+SMO 16,5

TRACTS.4.5

4100 92,89%SMO 0,89

TRACTS.5.1

24 94,47%Adaboost+J48 1,6

TRACTS.5.2

104 95,65%Adaboost+NaiveBayes 1,6

TRACTS.5.3

504 96,05%SMO 0,34

TRACTS.5.4

2504 95,26%SMO 0,66

TRACTS.7.1


TRACTS.7.2


TRACTS.7.3

1376 95,65%SMO 0,47

TRACTS.7.4

9608 94,07%SMO 2,01

Média - 95,24% - 2,45

42/54

Tam. alfabeto profundidade

EXPERIMENTOS REALIZADOS – MELHORES RESULTADOS DO MÉTODO TRACTS

Domínio

Config. TRACTS

# Atributo

s

Acurácia Classif.

Algoritmo

Tempo

Animais TRACTS.4.1 20 97,23% SMO 0,17s

Barcos TRACTS.3.2 39 100% NaiveBayes

0,01s

Furacões TRACTS.4.3 260 71,24% AODEsr 0,44s

43/54

EXPERIMENTOS REALIZADOS –RESULTADO COMPARATIVO

Método AcuráciaAnimais Barcos Furacões Média

TRACTS 97,23% 100,00% 71,24% 89,49%TraClass RB-TB 83,30% 98,20% 73,10% 84,87%

TraClass TB-Only 50,00% 84,40% 65,40% 66,60%

44/54


Os motivos principais para a dificuldade de classificação das trajetórias de furacões foram: A classe de toda a trajetória era definida pelo

comportamento de parte dela; O domínio de dados era formado por objetos

móveis da natureza, ou seja, com comportamento caótico.

Nos domínios onde existia um comportamento racional do objeto móvel, a acurácia de classificação das trajetórias foi claramente superior;

45/54


Introdução;Conceitos Utilizados;Trabalhos Relacionados;O Método TRACTS;Experimentos Realizados;

Conclusão.

46/54

CONCLUSÃO

O método TRACTS demonstrou-se eficaz na tarefa de criar um modelo de classificação com boa acurácia;

De forma geral o método foi superior a um outro método proposto para o mesmo fim, sem comprometimento da propriedade de independência de domínio considerado.

47/54

CONCLUSÃO – CONTRIBUIÇÕES

Primeiro método de classificação de trajetórias que transforma trajetórias em séries temporais;

Utilização de algoritmos tradicionais de classificação para realizar a construção de modelos de classificação de trajetórias;

Manter uma boa independência quanto ao domínio considerado no conjunto de dados, possibilitando uma análise pura das características da trajetória.

48/54

CONCLUSÃO – PUBLICAÇÕES

Esse trabalho resultou no seguinte artigo publicado: Santos, I.P., & Alvares, L.O. (2011). TRACTS: Um

método para a classificação de trajetórias de objetos móveis usando séries temporais. 8º Encontro Nacional de Inteligencia Artificial (ENIA) – CSBC, Proceedings (pp. 800-808). Natal, Brasil: Springer.

49/54

CONCLUSÃO – TRABALHOS FUTUROS

Estudo em outros domínios de aplicação, utilizando outras características geométricas da trajetória (locais e globais);

Busca de novos métodos de tratamento de strings, além do TSB, que também possibilitem a detecção de padrões interessantes a partir da string gerada pelo método SAX;

Submissão de artigo para uma revista internacional.

50/54

CONCLUSÃO – REFERÊNCIAS Chakrabarti, K., Keogh, E., Mehrotra, S., & Pazzani, M. (2002, Junho). Locally

adaptive dimensionality reduction for indexing large time series databases. ACM Transactions on Database Systems , pp. 151–162.

Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994 ). Fast subsequence matching in time-series databases. SIGMOD international conference on Management of data, Proceedings (pp. 419–429). New York, NY, EUA: ACM.

Geurts, P. (2001). Pattern Extraction for Time Series Classification. European Conference on Principles of Data Mining and Knowledge Discovery PKDD, Proceedings (pp. 115–127). London, UK: Springer.

Kamber, M., & Han, J. (2006). Data Mining: Concepts and Techniques. San Francisco, CA, EUA: Morgan Kaufmann.

Kumar, N., Lolla, V. N., Keogh, E., Lonardi, S., Ratanamahatana, C. A., & Wei, L. (2005). Time-series Bitmaps: A Practical Visualization Tool for working with Large Time Series Databases. 5th SIAM International Conference on Data Mining - SDM'05, Proceedings (pp. 531-535). Newport Beach, CA, EUA: SIAM.

Lee, J.-G., Han, J., Gonzalez, H., & Li, X. (2008). TraClass: trajectory classification using hierarchical region-based and trajectory-based clustering. VLDB Endowment (pp. 1081-1094). Auckland, Nova Zelândia: VLDB Endowment.

Lonardi, S. (2001). Global detectors of unusual words: design implementation and applications to pattern discovery in biosequences. Department of Computer Sciences, Purdue University.

51/54


Introdução;Conceitos Utilizados;Trabalhos Relacionados;O Método TRACTS;Experimentos Realizados;Conclusão.

52/54

TRACTSTRAJECTORY CLASSIFICATION USING TIME SERIES

Aluno: Irineu Junior Pinheiro dos Santos

Orientador: Luis Otávio de Campos Álvares

PERGUNTAS?


Domínio Tamanho Alfabeto SAX

Tempo Geração

Animais 3 5260,02s

Animais 7 5327,01s

Barcos 3 218,21s

Barcos 7 208,62s

Furacões 3 395,12s

Furacões 7 433,95s

54/54


Domínio

Alfabeto SAX

Profundidade

Tempo Geração

Animais 3 1 88,06s

Animais 7 4 1180,94s

Barcos 3 1 19,58s

Barcos 7 4 1097s

Furacões 3 1 4,12s

Furacões 7 4 1132,96s

55/54

Documents

TRACTS T RA JECTORY C LASSIFICATION USING T IME S ERIES Aluno: Irineu Junior Pinheiro dos Santos Orientador: Luis Otávio de Campos Álvares