TRACTS
TRAJECTORY 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
ESTRUTURA DE APRESENTAÇÃO
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
CONCEITOS –
BITMAPS DE SÉRIES TEMPORAL

Três mapas de bits com dimensão 𝜕 = 4 e três
profundidades distintas.
16/54
CONCEITOS –
BITMAPS DE SÉRIES TEMPORAL

Mapa de bits gerado para as strings c1: baccbdca
e c2: dcddaabb.
17/54
ESTRUTURA DE APRESENTAÇÃO
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;


(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;


Depende fortemente da relação espacial entre as trajetórias;
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
TRABALHOS RELACIONADOS
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
TRABALHOS RELACIONADOS
Clusterização
Classificação
21/54
ESTRUTURA DE APRESENTAÇÃO
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
O MÉTODO TRACTS – CARACTERIZAÇÃO

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
O MÉTODO TRACTS – CARACTERIZAÇÃO

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
O MÉTODO TRACTS – CARACTERIZAÇÃO

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
O MÉTODO TRACTS – TRANSFORMAÇÃO

As sequências de caracteres são transformadas
em mapas de bits através do método TSB;
31/54
O MÉTODO TRACTS – TRANSFORMAÇÃO
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
ESTRUTURA DE APRESENTAÇÃO
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:




Nos dados dos barcos a classe foi o nome dos mesmos:



Alce;
Gado;
Veado;
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
EXPERIMENTOS REALIZADOS
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
Temporais
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
TRACTS.3.1
Total de
atributos
utilizados
16
Acurácia de
classificaçã
o
94,07%
Algoritmo utilizado
Kstar
Tempo geração do
modelo de
classificação
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+RandomForest
2,8
TRACTS.4.3
260
96,05%
Bagging+SMO
5,5
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
32
94,86%
Bagging+SMO
2,8
TRACTS.7.2
200
96,44%
Bagging+SMO
5,5
TRACTS.7.3
1376
95,65%
SMO
0,47
TRACTS.7.4
Média
9608
-
94,07%
95,24%
SMO
2,01
-
2,45
Tam. alfabeto
profundidade
42/54
EXPERIMENTOS REALIZADOS – MELHORES
RESULTADOS DO MÉTODO TRACTS
Domínio
Config.
TRACTS
#
Atributos
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
Animais
TRACTS
97,23%
TraClass RB-TB
83,30%
TraClass TB-Only 50,00%
Acurácia
Barcos
Furacões
100,00%
71,24%
98,20%
73,10%
84,40%
65,40%
Média
89,49%
84,87%
66,60%
44/54
EXPERIMENTOS REALIZADOS

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
ESTRUTURA DE APRESENTAÇÃO
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
ESTRUTURA DE APRESENTAÇÃO
Introdução;
Conceitos Utilizados;
Trabalhos Relacionados;
O Método TRACTS;
Experimentos Realizados;
Conclusão.
52/54
TRACTS
TRAJECTORY CLASSIFICATION
USING TIME SERIES
PERGUNTAS?
Aluno: Irineu Junior Pinheiro dos Santos
Orientador: Luis Otávio de Campos Álvares
EXPERIMENTOS REALIZADOS –
RESULTADOS
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
EXPERIMENTOS REALIZADOS –
RESULTADOS
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