Categorias
Big Data Ciência de Dados Machine Learning

Pesquisadores desenvolvem detector de fake news para notícias sobre o Covid-19

Por tratar-se de uma nova ameaça, sabe-se muito pouco sobre o coronavírus (Sars-CoV-2). Esse fator dá grande abertura para disseminação de fake news (como ficou popularmente conhecido o compartilhamento de informações falsas), que podem ir desde supostos métodos de prevenção, tratamentos caseiros, cura do vírus e até mesmo tratamentos controversos recomendados por médicos, mesmo que não haja comprovação ou evidência científica para tais. Tudo isso pode dificultar o trabalho de órgãos de saúde, prejudicar a adoção de medidas de distanciamento social pela população e acarretar aumentos dos números de infectados e de morte pelo vírus.

Para diminuir os impactos dessa desinformação, diversos sites de checagem de fatos têm ferramentas que identificam e classificam (manualmente) tais notícias. Em geral, essas ferramentas poderiam fazer uso de algoritmos de aprendizagem de máquina para classificação de notícias. Diante dessa problemática, é evidente a necessidade de elaborar mecanismos e ferramentas que possam combater eficientemente o caos das fakes news.

Por isso, durante as disciplinas de Aprendizagem de Máquina e Mineração de Dados (Programa de Pós-graduação em Ciência da Computação da Universidade Federal do Ceará (MDCC-UFC)), nós (Andreza Fernandes, Felipe Marcel, Flávio Carneiro e Marianna Ferreira) propusemos um detector de fake news para analisar notícias sobre o COVID-19 divulgadas em redes sociais. Nosso objetivo é ajudar a população quanto ao esclarecimento da veracidade dessas informações.

Agora, detalharemos o processo de desenvolvimento desse detector de fake news.

 

Objetivos do projeto

  • Formar uma base dados de textos com notícias falsas e verdadeiras acerca do COVID-19;
  • Diminuir enviesamento das notícias;
  • Experimentar diferentes representações textuais;
  • Experimentar diferentes abordagens clássicas de aprendizagem de máquina e deep learning;
  • Construir um BOT no Telegram que ajude na detecção de notícias falsas relacionadas ao COVID-19.

 

Entendendo as terminologias usadas

Para o entendimento dos experimentos realizadas, vamos conceituar alguns pontos chaves e técnicas de Processamento de Linguagem Natural.

Tokenização: Esse processo transforma todas as palavras de um texto, dado como entrada, em elementos (conhecidos como tokens) de um vetor.

Remoção de Stopwords: Consiste na remoção de palavras de parada, como “a”, “de”, “o”, “da”, “que”, “e”, “do”, dentre outras, pois na maioria das vezes não são informações relevantes para a construção do modelo.

Bag of words: É uma representação simplificada e esparsa dos dados textuais. Consiste em gerar uma bolsa de palavras do vocabulário existente no dado, que constituirá as features do dataset. Para cada sentença é assinalado um “1” nas colunas que apresentam as palavras que ocorrem na sentença e “0” nas demais.

Term Frequency – Inverse Document Frequency (TF-IDF): Indica a importância de uma palavra em um documento. Enquanto TF está relacionada à frequência do termo, IDF busca balancear a frequência de termos mais comuns/frequentes que outros.

Word embeddings: É uma forma utilizada para representar textos, onde palavras que possuem o mesmo sentido têm uma representação muito parecida. Essa técnica aprende automaticamente, a partir de um corpus de dados, a correlação entre as palavras e o contexto, possibilitando que palavras que frequentemente ocorrem em contextos similares possuam uma representação vetorial próxima. Essa representação possui a vantagem de ter um grande poder de generalização e apresentar baixo custo computacional, uma vez que utiliza representações densas e com poucas dimensões, em oposição a técnicas esparsas, como Bag of Words. Para gerar o mapeamento entre dados textuais e os vetores densos mencionados, existem diversos algoritmos disponíveis, como Word2Vec e FastText, os quais são utilizados neste trabalho.

Out-of-vocabulary (OOV): Consiste nas palavras presentes no dataset que não estão presentes no vocabulário da word embedding, logo, elas não possuem representação vetorial.

Edit Distance: Métrica que quantifica a diferença entre duas palavras, contando o número mínimo de operações necessárias para transformar uma palavra na outra.

 

Metodologia

Agora iremos descrever os passos necessários para a obtenção dos resultados, geração dos modelos e escolha daquele com melhor performance para a efetivação do nosso objetivo.

 

Obtenção dos Dados

Os dados utilizados para a elaboração dos modelos foram adquiridos das notícias falsas brasileiras sobre o COVID-19, dispostos no Chequeado, e de um web crawler dos links das notícias, utilizadas para comprovar que a notícia é falsa no Chequeado, para formar uma base de notícias verdadeiras. Além disso também foi realizado um web crawler para obtenção de notícias do Fato Ou Fake do G1.

Originalmente, os dados obtidos do Chequeado possuíam as classificações “Falso”, “Enganoso”, “Parcialmente falso”, “Dúbio”, “Distorcido”, “Exagerado” e “Verdadeiro mas”, que foram mapeadas todas para “Falso”. Com isso, transformamos nosso problema em classificação binária.

No final, obtivemos um dataset com 1.753 notícias, sendo 808 fakes, simbolizada como classe 0, e 945 verdadeiras, classe 1, com um vocabulário de tamanho 3.698. Com isso, dividimos o nosso dado em conjunto de treino e teste, com tamanhos de 80% e 20%, respectivamente.

 

Pré-processamento

Diminuição do viés. Ao trabalhar e visualizar os dados, notamos que algumas notícias verdadeiras vinham com palavras e sentenças que enviesavam e deixavam bastante claro para os algoritmos o que é fake e o que é verdadeiro, como: “É falso que”, “#Checamos”, “Verificamos que” e etc. Com isso, removemos essas sentenças e palavras, a fim de diminuir o enviesamento das notícias.

Limpeza textual. Após a etapa anterior, realizamos a limpeza do texto, consistindo em remoção de caracteres estranhos e sinais de pontuação e uso do texto em caixa baixa.

Tokenização. A partir do texto limpo, inicializamos o processo de tokenização das sentenças.

Remoção das Stopwords. A partir das sentenças tokenizadas, removemos as stopwords.

 

Representação textual

Análise exploratória

A partir do pré-processamento dos dados brutos, inicializamos o processo de análise exploratória dos dados. Verificamos o tamanho do vocabulário do nosso dataset, que totaliza 3.698 palavras. 

 

Análise do Out-of-vocabulary. Com isso, verificamos o tamanho do nosso out-of-vocabulary em relação às word embeddings pré-treinadas utilizadas, totalizando 32 palavras. Um fato curioso é que palavras chaves do nosso contexto encontram-se no out-of-vocabulary e acabam sendo mapeadas para palavras que não tem muita conexão com o seu significado. Abaixo é possível ver algumas dessas palavras mais à esquerda, e a palavra a qual foram mapeadas mais à direita.

Mapeamento de palavras

 

Análise da frequência das fake news por rede social. O dado bruto original advindo do Chequeado possui uma coluna que diz sobre a mídia social em que a fake news foi divulgada. Após uma análise visual superficial, apenas plotando a contagem dos valores dessa coluna (que acarreta até na repetição de redes sociais), notamos que os maiores veículos de propagação de fake news são o Facebook e Whatsapp.

 

 

Frequência de fake news por rede social

 

Análise da quantidade de fake news ao longo dos meses. O dado bruto original advindo do Chequeado também possui uma coluna que informava a data de publicação da fake news. Após realizar uma análise visual da distribuição da quantidade de fake news ao longo dos meses, notamos que o maior número de fake news ocorreu em abril, mês em que a doença começou a se espalhar com maior velocidade no território brasileiro. De acordo com o G1, em 28 de abril, o Brasil possuía 73.235 casos do novo coronavírus (Sars-CoV-2), com 5.083 mortes. Além disso, foi nesse mês que começaram a surgir os boatos de combate do Coronavírus via Cloroquina, além de remédios caseiros.

Volume de fake news relacionadas ao COVID-19 ao longo dos meses

 

Análise da Word Cloud. Com as sentenças tokenizadas, também realizamos uma visualização usando a técnica de Word Cloud, que apresenta as palavras do vocabulário em um tamanho proporcional ao seu número de ocorrência no todo. Com essa técnica, realizamos duas visualizações, uma para as notícias verdadeiras e outra para as fake news.

Nuvem de palavras nas notícias falsas

 

Nuvem de palavras nas notícias verdadeiras

 

Divisão treino e teste

A divisão dos conjuntos de dados entre treino e teste foi feita com uma distribuição de 80% e 20% dos dados, respectivamente. Os dados de treino foram ainda divididos em um novo conjunto de treino e um de validação, com uma distribuição de 80% e 20% respectivamente.

 

Aplicação dos modelos

Para gerar os modelos, escolhemos algoritmos e técnicas clássicas  de aprendizagem de máquina, tais como técnicas atuais e bastante utilizadas em competições, sendo eles: 

  • Regressão Logística (*): exemplo de classificador linear;
  • K-NN (*): exemplo de modelo não-paramétrico;
  • Análise Discriminante Gaussiano (*): exemplo de modelo que não possui hiperparâmetros;
  • Árvore de Decisão: exemplo de modelo que utiliza abordagem da heurística gulosa;
  • Random Forest: exemplo de ensemble de bagging de Árvores de Decisão;
  • SVM: exemplo de modelo que encontra um ótimo global;
  • XGBoost: também um ensemble amplamente utilizado em competições do Kaggle;
  • LSTM-Dense: exemplo de arquitetura que utiliza deep learning.

Os algoritmos foram utilizados por meio de implementações próprias (aqueles demarcados com *) e uso da biblioteca scikit-learn e keras.  Para todos os algoritmos, com exceção daqueles que não possuem hiperparâmetros e LSTM-Dense, realizamos Grid Search em busca dos melhores hiperparâmetros e realizamos técnicas de Cross Validation para aqueles utilizados por meio do Scikit-Learn, com k fold igual a 5.

 

Obtenção das métricas

As métricas utilizadas para medir a performance dos modelos foram acurácia, Precision, Recall, F1-score e ROC.

 

                Tabela 1. Resultados das melhores representações por algoritmo

MODELOS PRECISION RECALL F1-SCORE ACCURACY ROC
XGBoost BOW e TF-IDF* 1 1 1 1 1
SVM BOW E TF-IDF* 1 1 1 1 1
Regressão Logística BOW 0.7560 0.7549 0.7539 0.7549 0.7521
LSTM FASTTEXT 0.7496 0.7492 0.7493 0.7492 0.7492
Random Forest TF-IDF 0.7407 0.7407 0.7402 0.7407 0.7388
Árvore de Decisão TF-IDF 0.7120 0.7122 0.7121 0.7122 0.7111
Análise Discriminante Gaussiano Word2Vec 0.7132 0.7122 0.7106 0.7122 0.7089
k-NN FastText 0.6831 0.6809 0.6775 0.6638 0.6550

 

 

                Tabela 2. Resultados das piores representações por algoritmo

MODELOS PRECISION RECALL F1-SCORE ACCURACY ROC
XGBoost Word2Vec  0.7238 0.7236 0.7227 0.7236 0.7211
SVM Word2Vec 0.7211 0.7179 0.7151 0.7179 0.7135
Árvore de Decisão Word2Vec 0.6391 0.6353 0.6351 0.6353 0.6372
Random Forest Word2Vec 0.6231 0.6210 0.6212 0.6210 0.62198
Regressão Logística FastText 0.6158 0.5982 0.5688 0.59829 0.5858
Análise Discriminante Gaussiano TF-IDF 0.5802 0.5811 0.5801 0.5811 0.5786
k-NN BOW 0.5140 0.5099 0.5087 0.5042 0.5127
LSTM WORD2VEC (*) 0.4660 0.4615 0.4367 0.4615 0.4717

 

Resultados

Com os resultados apresentados percebemos que os modelos SVM e XGBoost com as representações TF-IDF e BOW atingiram as métricas igual a 100%. Isso pode ser um grande indicativo de sobreajuste do modelo aos dados. Abaixo podemos visualizar a matriz de confusão e a curva ROC dos mesmos.

Logo após vem a Regressão Logística com métricas em torno de ~75.49%! Abaixo podemos visualizar sua matriz de confusão e a curva ROC.

 

Exemplos de classificações da Regressão Logística

  • True Positive (corretamente classificada)
    • Texto que diz que vitamina C e limão combatem o coronavírus
  • True Negative (corretamente classificada)
    • Notícia divulgada em 2015 pela TV italiana RAI comprova que o novo coronavírus foi criado em laboratório pelo governo chinês.
  • False Positive (erroneamente classificada)
    • Vitamina C com zinco previne e trata a infecção por coronavírus
  • False Negative (erroneamente classificada)
    • Que neurocientista britânico publicou estudo mostrando que 80% da população é imune ao novo coronavírus

Intrigados com os resultados, resolvemos visualizar as diferentes representações de dados em 2 componentes principais (visto a alta dimensionalidade do dado, o que prejudica a análise do que está acontecendo de fato) por meio das técnicas de PCA e T-SNE, separando por cor de acordo com sua classificação. 

É interessante notar que as representações de word embeddings utilizadas possui uma representação bastante confusa e misturada. Já as representações TF-IDF e Bag of Words são facilmente separáveis.

 

 

                            FastText PCA (Semelhante ao Word2Vec)

 

                                       FastText T-SNE

 

 

                                         Word2Vec T-SNE

 

 

                                   BOW PCA (Semelhante ao TF-IDF)

 

 

                                              BOW T-SNE

 

 

                                             TF-IDF T-SNE

 

Conclusão

A base de dados utilizada para obtenção dos modelos foi obtida por meio do site Chequeado, e, posteriormente, houve o enriquecimento dessa base por meio do  web crawler, totalizando 1.383 registros, sendo 701 fake news e 682 notícias verdadeiras. 

Para representação textual foram utilizadas as técnicas Bag of Words, TF-IDF e Word embeddings Word2Vec e FastText de 300 dimensões com pesos pré-treinados obtidas por meio da técnica CBOW com dimensões, disponibilizadas pelo Núcleo Interinstitucional de Linguística Computacional (NILC).  Para gerar os modelos foram utilizados os algoritmos Regressão Logística, kNN, Análise Discriminante Gaussiano, Árvore de Decisão, Random Forest, Gradient Boosting, SVM e LSTM-Dense. Para avaliação dos modelos foi utilizado as métricas Acurácia, Precision, Recall, F1-score, AUC-ROC e matriz de confusão.

Considerando os experimentos e os resultados, conclui-se que o objetivo principal deste trabalho, gerar modelos capazes de classificar notícias extraídas de redes sociais relacionadas ao COVID-19 como falsas e verdadeiras, foi alcançado com êxito. Como resultados, vimos que os modelos SVM e XGBoost com TF-IDF e BOW atingiram 100% nas métricas, com grandes chances de terem se sobreajustado aos dados. Com isso, consideramos como melhor modelo a Regressão Logística com a representação BOW, atingindo as métricas com valores próximos a 75.49%. 

O pior classificador foi o kNN com o BOW e LSTM-Dense com Word2Vec, porém é importante ressaltar que este último não contou com Grid Search e foi treinado com poucas épocas. No geral, as melhores representações foram a TF-IDF e BOW e a pior o Word2Vec.

Para este projeto houveram algumas dificuldades, sendo a principal delas a formação da base de dados, visto que o contexto pandêmico do COVID-19 é algo novo e devido à limitação da API do Twitter em relação ao tempo para extrair os tweets, que era originalmente a ideia da base de dados para esse projeto. Além disso, também houve a dificuldade de remoção do viés dos dados.

 

Como trabalhos futuros, visamos:

  • Ampliar a base de dados;
  • Investigar o que levou ao desempenho do SVM, XGBOOST com as representações TF-IDF e BOW.
  • Analisar performance dos modelos utilizando outras word embeddings pré-treinadas, como o BERT, Glove e Wang2vec.
  • Investigar o uso do modelo pré-treinado do BERT e com fine-tuned.
  • Aplicar PCA Probabilístico
  • Utilizar arquiteturas de deep learning mais difundidas na comunidade científica.

 

                                    

Categorias
Big Data Ciência de Dados Python

Conheça o PyMove: biblioteca Python para identificação de trajetórias padrões, mineração e análise de dados

O Insight Lab é formado por um time multidisciplinar de pesquisadores que vão desde de alunos de graduação a especialistas. Com o propósito de  desenvolver pesquisas na área de Data Science, que possam beneficiar a outros pesquisadores e a sociedade em geral, nossos pesquisadores estão sempre atentos às necessidades que as mudanças e as novas tecnologias proporcionam. 

Observamos com isso, por exemplo, que o crescente uso de sensores GPS e barateamento de tecnologias móveis, nos últimos anos, têm gerado um grande volume de dados de trajetórias. Esses dados podem trazer respostas para facilitar diversas atividades que impactam diretamente na vida das pessoas. Pensando nisso, o quê um Cientista de Dados pode fazer a partir daí?

O que é uma trajetória?

Bem, antes de tudo é muito importante entendermos o que é uma trajetória. Uma trajetória é uma sequência de pontos cronologicamente ordenados, que representam o movimento de um objeto em um espaço geográfico. Cada ponto é formado por uma marcação de tempo e coordenadas geoespaciais (latitude,longitude). As trajetórias podem representar movimentos de diferentes objetos, como:pessoas, veículos e animais.

O que podemos fazer com os dados de trajetória?

Esse tipo de dado é muito valioso não só para a Computação, mas também para áreas como Geografia, Sociologia e Urbanização, sendo bastantes utilizados para aplicações como: sistemas de transporte inteligentes e computação urbana; análise de mobilidade sustentável; no rastreamento de fenômenos naturais e identificação de padrões de migração animal e etc.

Como trabalhar com esse dado?

Para que seja possível extrair informações dos dados e realizar análises consistentes dos mesmos, é preciso que um conjunto de atividades de mineração de dados, que veremos em mais detalhes a seguir, sejam executadas. Embora haja um grande volume de trabalhos e aplicações, nota-se a ausência de softwares e ferramentas que possam auxiliar pesquisadores em todo o processo para lidar e extrair as informações que esses dados possam oferecer.

Com isso, nós do Insight Data Science Lab estamos trabalhando para a elaboração de uma biblioteca open-source para Python que contemple o conjunto de etapas e atividades para lidar com esses dados: o PyMove!

O que é o PyMove?

O PyMove surgiu em meados de 2018 com o objetivo de ser uma biblioteca Python extensível que comporte um grande número de operações dentro das etapas de mineração de dados de trajetória!

O PyMove propõe :

  • Uma sintaxe familiar e semelhante ao Pandas;
  • Documentação clara;
  • Extensibilidade, já que você pode implementar sua estrutura de dados principal manipulando outras estruturas de dados, como o Dask DataFrame, matrizes numpy, etc., além de adicionar novos módulos;
  • Flexibilidade, pois o usuário pode alternar entre diferentes estruturas de dados;
  • Operações para pré-processamento de dados, mineração de padrões e visualização de dados.
Modelagem do Pymove
Estrutura de dados

A atual estrutura do PyMove é fortemente influenciada pelo trabalho de Yu Zheng, o qual propõe um paradigma que serve como um guia para realizar trabalhos de mineração de dados de trajetória. A figura 2.1.1 mostra a versão adaptada desse paradigma adotada no PyMove.

Figura 2.1.1. Um paradigma para mineração de trajetória. Fonte: Adaptado de [4]
A seguir, iremos destrinchar cada etapa citada na figura 2.1.1.
Pré-processamento

O pré-processamento de dados é uma etapa de extrema importância na mineração dos dados. Nela são realizadas atividades com o objetivo de melhorar a qualidade do dados para obtenção de melhores resultados em processamentos e análises futuras. Existem quatro técnicas básicas para esta etapa: filtragem de ruído, detecção de pontos de parada, compressão e segmentação de trajetória.

Filtragem de ruído

Alguns pontos da trajetória podem estar inconsistentes devido a problemas nos dispositivos de coleta de dados, na comunicação, ou em outros fatores externos, tais pontos são denominados ruídos. As técnicas de filtragem de ruído procuram realizar a remoção ou alinhamento desses dados ruidosos com a rede de ruas. Os pontos p5 e p9 na Figura 3.1 são, neste contexto, dados com ruído.

Figura 3.1. Trajetória com pontos lidos incorretamente. Fonte: adaptado de [1]
Detecção de pontos de parada

Pontos onde os objetos ficaram parados ou se movimentando ao redor, por um determinado limite de tempo, são chamados pontos de parada. Estes pontos podem representar: shoppings, atrações turísticas, postos de gasolina, restaurantes, entre outros. Os pontos de parada nos permitem representar uma trajetória como uma sequência de pontos com significado.
A figura 3.2 mostra uma trajetória, após a execução de um algoritmo, para detectar pontos de parada onde são encontrados três pontos de parada: casa, trabalho e supermercado. Esses pontos podem representar essa trajetória, como pontos p1, p2 e p3, respectivamente.

Compressão

Tem como objetivo reduzir o tamanho dos dados de trajetória através de um conjunto de técnicas, com o objetivo de evitar sobrecarga de processamento e minimizar a carga no armazenamento de dados, gerando uma representação mais compactada  que descreve a trajetória de um objeto.

Figura 3.2. Resultado da execução de um algoritmo de detecção de pontos de parada. Fonte: adaptado de [2].

Na Figura 3.3 podemos ver o resultado da compressão de uma trajetória, inicialmente ela é representada por doze pontos, mas após a compressão este número é reduzido para quatro pontos.

Figura 3.3. Demonstração da aplicação de uma técnica de compreensão de dados de trajetórias. Fonte: adaptado de [2].
Segmentação

Nesta etapa, a trajetória é subdividida em segmentos, de tal forma que os dados pertencentes ao mesmo segmento tenham comportamento homogêneo. A segmentação ajuda a descobrir padrões sobre os dados, diminui a complexidade computacional e é um passo obrigatório para processos de análise, como a clusterização e a classificação. A Figura 3.4 apresenta um exemplo de segmentação de trajetória pelo tempo fixo de duas horas, resultando em três novos segmentos.

Figura 3.4. Segmentação de uma trajetória com base no intervalo de tempo igual a duas horas. Fonte: adaptado de [2]
Map-matching

Como foi mencionado acima, os pontos gerados em uma trajetória podem não corresponder precisamente à real localização de onde o objeto em movimento passou, (figura 3.5-a).

Esta falta de precisão não é desejável para alguns tipos de aplicações, entre elas: as que trabalham com análise de fluxo de trânsito ou serviços de navegação (ZHENG,2015). Para resolver esses e outros problemas, são aplicados algoritmos de map-matching, que têm como objetivo alinhar os pontos da trajetória com a rede de ruas, (figura 3.5-b).

Figura 3.5 (a e b). Uma trajetória, antes e depois da aplicação do Map-matching. Fonte: adaptado de [1].
Indexação e recuperação de trajetórias

Durante o processo de mineração de dados de trajetórias, acabamos por precisar acessar frequentemente diferentes segmentos e amostras das trajetórias. Com o grande volume de dados, esses acessos podem demandar tempo e processamento. Por isso, é necessário a adoção de técnicas eficazes para o gerenciamento desses dados, oferecendo a recuperação rápida dos dados.

Os dois principais tipos de consultas, mostrado na Figura 2.1.1 – Um paradigma para mineração de trajetória.
  • KNN: esse tipo de consulta recupera as K, primeiras trajetórias com a distância agregada mínima, para alguns pontos ou uma trajetória específica.

Nas consultas de pontos buscamos por trajetórias que possuam uma boa conexão com os locais/pontos pesquisados, em vez de saber se a trajetória é semelhante à consulta em forma.

Nas consulta por trajetória buscamos encontrar os registros que possuam uma rota ou segmento de trajetória parecida. Essa consulta necessita da definição de uma função que delimite a similaridade e distância entre trajetórias.

  • Intervalo de consultas: recuperam os dados de trajetórias que estão contidos em um espaço ou intervalo. Essa técnica contém três abordagens para consultas de intervalo espaço-temporal.
  1. A primeira abordagem considera o tempo como a terceira dimensão além das informações que delimitam o espaço geográfico.
  2. A segunda abordagem divide um período em vários intervalos de tempo, criando um índice espacial individual.
  3. A terceira abordagem leva em consideração o espaço geográfico, dividindo-o em grades, as chamadas grids, e cria um índice temporal para as trajetórias que caem em cada célula dessa grade. Cada segmento que cai em uma grade é representado por um ponto com as coordenadas iguais ao ponto com horário inicial e o ponto com horário final do segmento.

A Figura 4 mostra as técnicas para melhoria da indexação e recuperação de dados e segmentos de trajetórias. Em (a) é mostrada a técnica de Intervalo de consulta. Nela são recuperados os pontos e segmentos de trajetórias dentro da região retangular tracejada em vermelho. Já em (b) e (c) são mostradas o uso da técnica de consulta via KNN, sendo a primeira consultas por pontos e a segunda consulta por segmentos de trajetórias similares.

Figura 4. Demonstração das abordagens utilizadas para indexação e recuperação de trajetórias. Fonte: adaptado de [4].
Modelos

Muitas aplicações exigem informações instantâneas a partir dos dados de trajetória, como é o caso de aplicações de guia de viagens ou detecção de anomalias de tráfego. Essas informações exigem algoritmos eficazes e muitas vezes são adquiridas por meio de técnicas de mineração de dados. Essas técnicas podem ser enquadradas em áreas, como classificação, detecção de anomalias, mineração de padrões e incertezas da trajetória. Abaixo é explorado o conceito de cada uma dessas técnicas.

Classificação

Trajetórias e segmentos podem ser classificados de diferentes modos e em diferentes categorias, como em: tipo de atividade, modos de transporte e até mesmo o movimento, através do uso de técnicas e algoritmos de aprendizado supervisionado.

Em geral, a classificação da trajetória é composta por três etapas principais:

  1. Utilização de métodos de segmentação da trajetória para prover segmentos;
  2. Extração de características de cada segmento;
  3. Criação de modelos para classificar cada segmento.
Detecção de anomalias

Anomalias, no contexto de dados espaço temporais, consistem em pontos ou até mesmo segmentos de uma trajetória que possuem um comportamento anormal. Não segue o padrão dos dados que representam uma trajetória, como é o caso dos pontos destacados em vermelho na Figura 3.1. Essas anomalias podem ser desencadeados por diversos eventos como: um acidente de trânsito, que obriga os carros a mudarem rapidamente de velocidade, um desvio de uma rota comum por conta de uma obra ou por estar perdido no caminho. A etapa de detecção de anomalias, se preocupa em encontrar esses pontos e/ou segmentos que violem um certo padrão de uma trajetória.

Mineração de padrões

Diferentes padrões de mobilidade podem ser identificados numa trajetória individual ou em um conjunto de trajetórias. Os padrões de mobilidade de trajetória em quatro categorias: Clusterização de trajetórias, Moving Together Patterns, , Padrões Periódicos e Padrões de Frequências Sequenciais.

  1. Clusterização: as técnicas dessa categoria têm como finalidade agrupar trajetórias em busca de algum padrão ou característica que diferenciem grupos.
  2. Moving Together Patterns: essa categoria reúne técnicas que procuram detectar indivíduos e/ou objetos que se movem juntos por determinado período de tempo, sendo bastante útil para detectar padrões. Esses padrões podem ter diversas aplicações, como ajudar a entender fenômenos de migração e tráfego de espécies.
  3. Padrões Periódicos: reúne técnicas que procuram identificar comportamentos e padrões temporais em trajetórias, como a ida a um dentista durante um intervalo de tempo, ou até mesmo os animais, que migram anualmente de um lugar a outro. A análise deste tipo de padrão auxilia na previsão de comportamentos futuros do objeto e na compressão de dados.
  4. Padrões de Frequências Sequenciais: reúne técnicas que possuem a finalidade de encontrar padrões onde objetos partilhem a mesma sequência de localização, num período similar de tempo. Os pontos da sequência não necessariamente precisam ser pontos consecutivos na trajetória original. Essas técnicas são amplamente utilizados em aplicações como recomendação de trajetória, predição de localização, compressão de dados.
Incerteza em trajetórias

Indivíduos e objetos realizam movimentos contínuos em determinados locais em que trafegam. Porém, devido à limitação de algumas aplicações ou por questão de economia de energia dos sensores, os dados que representam essa trajetória são enviados periodicamente. Desse modo, a localização desse indivíduo e/ou objeto será incerta, ou até mesmo desconhecida, entre dois pontos que descrevem sua trajetória.

Na Figura 6 é perceptível que entre dois pontos é possível tomar caminhos diferentes, por exemplo: partindo do ponto p1 é possível chegar ao ponto p2 de diferentes formas. Este contexto ocasiona a incerteza dos caminhos tomados entre pontos de uma trajetória.

Nessa linha de pesquisa, há duas sub-áreas, descritas a seguir:

  • Redução de incertezas: consiste em desenvolver técnicas que visam diminuir a incerteza da trajetória entre dois pontos.
  • Preservação de privacidade: consiste em desenvolver técnicas que visam ampliar a incerteza de trajetórias sem afetar a qualidade de um serviço ou o uso desses dados, visando proteger um usuário do vazamento de privacidade causado pela divulgação de suas trajetórias.
Figura 6. Demonstração de uma trajetória formada por três pontos, p1, p2 e p3. Fonte: adaptado de [4].
Visualização de trajetórias

A aplicação de técnicas de visualização de dados nos grandes volumes de dados de trajetórias podem facilitar a compreensão do comportamento de objetos em movimento, como veículos e descoberta de tráfego, social, geoespacial e até padrões econômicos. Essas visualizações podem ser combinadas com procedimentos de processamento dos dados, visando diminuir, limpar e filtrar os dados.

Para visualizar dados de trajetória são necessárias técnicas que exploram canais visuais como cor, tamanho, forma, orientação aplicadas a diferentes marcas como pontos, linhas, áreas, volumes e superfícies para representar estes dados, transformando-os em representações visuais apropriadas.

Há diferentes técnicas de visualização a serem aplicadas como:
  • Gráfico de Linhas: visualizações orientadas ao tempo enfatiza a exibição de padrões, periodicidade, tendências e anormalidade dos dados de trajetória. Nesse tipo de representação é amplamente utilizado gráfico de linhas, onde o eixo X delimita o tempo e o Y outra característica do dado, como os picos de velocidade de uma trajetória.
  • Mapa estáticos: são abordagens bastante comuns para representar informações de localização geográfica, como a análise de trajetórias de mobilidade ou fluxo de tráfego em uma rede distribuída. Convencionalmente, uma trajetória é representada por uma linha ou uma curva, podendo explorar combinações de variáveis, como cor, tamanho e direção, em relação às suas propriedades.
  • Clusters: Quando há uma grande massa de dados de trajetória, pode haver sobreposição de pontos em uma visualização. Com isso as visualizações com clusters em mapas ajudam bastante em análises, visto que um grupo de pontos que em determinado momento se sobrepunham, tornam-se um só. Essa técnica permite obter uma visão geral rápida de seus conjuntos de clusters.
Visualização dos dados de gorjetas das viagens de táxis fazendo uso do gráfico de linhas para demonstrar a quantidade de gorjetas obtidas pelas viagens de táxi no período de tempo de 1 a 7 de maio de 2011. Cada linha representa a gorjeta por viagem em uma região. Fonte: Wei Chen, Fangzhou Guo, and Fei-Yue Wang. A survey of traffic data visualization. IEEE Transactions on Intelligent Transportation Systems, 16:2970–2984, 12 2015.

 

Exploração do uso de recursos visuais para visualização em mapas estáticos. Fonte: adaptado de [3].
  • Mapas de Calor: Essa visualização é gerada a partir de uma matriz de células, onde cada célula é colorida de forma gradiente com base em valores ou função dos dados, sendo bastante útil quando é necessário gerar visualizações para grande volume de dados, fornecendo uma visão geral dos maiores e menores valores dos dados.

 

Visualização de todos os pontos sob um mapa gerado pelo Folium. Fonte: documentação Folium.

 

Utilização da técnica de cluster para visualizar os pontos sob um mapa gerado pelo Folium. Fonte: documentação Folium.
Tutorial

Depois de explorar mais sobre a arquitetura do PyMove e vislumbrar o mundo dos dados de trajetória, agora vamos botar a mão na massa!

Neste tutorial iremos entender como representar dados de trajetória no PyMove, aplicar funções de pré-processamento e visualização de dados existentes no PyMove!

Para isso, vamos utilizar o conjunto de dados utilizado neste trabalho, o Geolife GPS trajectory dataset, [5]. Ele é resultado da coleta realizada no projeto Geolife, da Microsoft Research Asia, por 178 usuários por mais de quatro anos. Esses dados registram uma grande variedade de movimentos de dos usuários, incluindo não só caminhos rotineiros, como também atividades esportivas e de lazer, amplamente distribuídos em mais de 30 cidades da China e em algumas cidades localizadas nos EUA e na Europa.

Esse conjunto de dados possui 17.621 trajetórias, registradas por GPS, com uma distância total de 1.251.654 quilômetros e duração de 48.203 horas. Os dados estão dispostos em 182 pastas, numeradas de 000 à 181, onde cada uma simbolizava um usuário. Os arquivos que contém os dados de localização possuem os valores separados por vírgula, onde representam, respectivamente, a latitude, longitude, campo sem valor, altitude, número de dias que passaram após a data 30/12/1999, data e tempo.

Por limitações de processamento e em busca de diversidade, nesse trabalho são utilizados os dados dos usuários 000, 010, 011 e 100, totalizando em 1.206.506 pontos de trajetórias.

Instalação do PyMove

Primeiro, vamos clonar o repositório!
COMANDO 1: git clone -b developer https://github.com/InsightLab/PyMove

Segundo, vamos criar um ambiente!
COMANDO 2: conda create -n pymove pip python=3.7

Terceiro, acesse o ambiente recém criado.
COMANDO 3: conda activate pymove

Quarto, vamos instalar as dependências da nossa biblioteca!
COMANDO 4: cd PyMove python setup.py install

Quinto, agora é só usar!
COMANDO 5: import pymove

 

Referências:

[1] G. A. M. Gomes, E. Santos, and C. A. Vidal. VISUALIZAÇÃO INTERATIVA DE DINÂMICAS DE TRÁFEGO ATRAVÉS DE DADOS DE TRAJETÓRIAS. PhD thesis, PD thesis, Universidade Federal do Ceará, 2018.

[2] G. A. M. Gomes, E. Santos, and C. A. Vidal. VISUALIZAÇÃO INTERATIVA DE DINÂMICAS DE TRÁFEGO ATRAVÉS DE DADOS DE TRAJETÓRIAS. PhD thesis, PD thesis, Universidade Federal do Cear´a, 2018.

[3] Tiago Gon¸calves, Ana Afonso, and Bruno Martins. Visualization techniques of trajectory data: Challenges and imitations. CEUR Workshop Proceedings, 1136, 01 2013.

[4] Yu Zheng. Trajectory data mining: An overview. ACM Transaction on Intelligent Systems and Technology, September 2015.

[5] Yu Zheng, Hao Fu, Xing Xie, Wei-Ying Ma, and Quannan Li. GeoLife User Guide 1.2. Microsoft Reasearch Asia, 2(April 2007):31–34, 2011

Sair da versão mobile