info.info-db
Ana Beatriz Cruz 
email: anacruz@acm.org
  
João Ferreira 
  
Diego Carvalho 
email: d.carvalho@ieee.org
  
Eduardo Mendes 
email: eduardo.mendes@fgv.br
  
Esther Pacitti 
email: esther.pacitti@inria.fr
  
Rafaelli Coutinho 
email: rafaelli.coutinho@cefet-rj.br
  
Fábio Porto 
email: fporto@lncc.br
  
Eduardo Ogasawara 
email: eogasawara@ieee.org
  
Detecçao 
  
Rodoviário Urbano 
  
Fabio Porto 
  
Cefet / Rj 
  
  
Detecçao de Anomalias Frequentes no Transporte Rodoviario Urbano

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduc ¸ão

Em 2007, pela primeira vez existiam mais pessoas vivendo em áreas urbanas do que em zonas rurais, resultado de uma urbanizac ¸ão expressiva que se impulsionou desde a década de 1950[United Nations, 2014]. Atualmente, mais da metade da populac ¸ão mundial vive em áreas urbanas exigindo um replanejamento dos servic ¸os públicos das zonas urbanas para provê-los de maneira sustentável e duradoura. Outrossim, os desafios relacionados ao desenvolvimento eficiente e sustentável dos servic ¸os de transporte passaram a ser investigados [START_REF] Chen | A survey of traffic data visualization[END_REF], levando à uma intensificac ¸ão das pesquisas que conjugam a análise de dados de transporte à mobilidade urbana, com o objetivo de se identificar fenômenos causadores dos estrangulamentos do transporte, como os engarrafamentos.

Os estudos sobre os estrangulamentos fazem análise de dados coletados principalmente a partir de sistemas GP/dispositivos móveis embarcados em veículos que participam do fluxo, como táxis [START_REF] Ferreira | Visual exploration of big spatio-temporal urban data: A study of new york city taxi trips[END_REF] e ônibus [START_REF] Bierlaire | A probabilistic map matching method for smartphone GPS data[END_REF]. Os dados coletados são frequentemente modelados como trajetórias de objetos móveis, pontos de início ou fim de movimento. Para análises mais sistêmicas, métodos de agregac ¸ão espac ¸o-temporal são usados para associar as observac ¸ões às posic ¸ões geográficas predefinidas (objetos permanentes) e esse tipo de agregac ¸ão reduz significativamente o volume de dados de trajetórias [START_REF] Tao | Spatio-temporal aggregation using sketches[END_REF].

Neste contexto, observa-se a necessidade de um estudo mais aprofundado sobre ótica das séries espac ¸o-temporais de objetos permanentes que possam trazer uma melhor compreensão do tráfego [START_REF] Cruz | Detecc ¸ão de anomalias no transporte rodoviário urbano[END_REF]. Este trabalho tem por objetivo identificar e classificar anomalias em dados agregados de mobilidade urbana. Para isso, uma técnica de identificac ¸ão de anomalias nos comportamentos do trânsito é aplicada sobre os dados agregados por regiões predefinidas. Para extrair conhecimentos destas anomalias, um novo método de classificac ¸ão de padrões frequentes é proposto, permitindo identificar padrões anômalos inesperados e esperados.

Além dessa introduc ¸ão, o trabalho se divide em quatro outras sec ¸ões. A sec ¸ão 2 apresenta conceitos essenciais para o entendimento do problema e da metodologia adotada. Na sec ¸ão 3, apresenta-se a metodologia aplicada. A sec ¸ão 4 descreve uma avaliac ¸ão da proposta. Finalmente, a sec ¸ão 5 apresenta as conclusões e os próximos passos.

Fundamentac ¸ão Teórica

As séries espac ¸o-temporais são definidas como sequências de observac ¸ões de objetos que contêm dados sobre o local e momento das coletas [START_REF] Cressie | Statistics for spatio-temporal data[END_REF]. As observac ¸ões podem ser emitidas por objetos permanentes ou móveis. Os objetos permanentes possuem localizac ¸ão fixa (sensores fixos) e os objetos móveis apresentam localizac ¸ões que variam com o tempo (trajetória). O modelo de dados espac ¸o-temporal mais aplicado a problemas relacionados ao tráfego é o de trajetória [START_REF] Chen | A survey of traffic data visualization[END_REF]. Os dados emitidos por sensores de posicionamento, como o GPS, possuem informac ¸ões de latitude, de longitude e do momento da coleta. Desta forma, a sequência de dados coletados por sensores de posicionamento configura naturalmente uma trajetória, sem a necessidade de pré-processamento. Entretanto, estudos que se relacionam mais diretamente com o tema deste trabalho são aqueles em que agregam informac ¸ões do objeto [START_REF] Tao | Spatio-temporal aggregation using sketches[END_REF], gerando séries espac ¸o-temporais associadas a objetos permanentes.

A partir de observac ¸ões sobre um sistema é possível encontrar características específicas. A recorrência dessas características torna-as esperadas. Desvios significativos nas propriedades das características esperadas do sistema são consideradas anomalias [START_REF] Aggarwal | Outlier Analysis[END_REF]. No contexto de mobilidade urbana, anomalias podem indicar mudanc ¸as no comportamento por engarrafamentos ou aumento da velocidade. Elas podem ser causadas por acidentes, eventos, obras, operac ¸ões de controle como blitz e Lei Seca, protestos, desastres e feriados. São difíceis de serem encontradas e interpretadas devido ao grande volume de dados e ao grande número de ruídos que compõem o conjunto de dados analisado [START_REF] Lakhina | Diagnosing network-wide traffic anomalies[END_REF]. Dessa forma, a identificac ¸ão de anomalias é frequentemente feita sobre dados de trajetória.

A minerac ¸ão de padrões frequentes é um dos métodos para identificar padrões que ocorrem com frequência no conjunto de dados analisado [START_REF] Han | Data Mining: Concepts and Techniques[END_REF]. Esses padrões podem ser itens, sequências ou estruturas. Em todos os casos, por meio da minerac ¸ão de padrões frequentes são identificadas regras de associac ¸ão e correlac ¸ões. Uma regra de associac ¸ão é uma implicac ¸ão de formato X → Y . Seja I = {i 1 , i 2 , ..., i n } um conjunto de todos os itens, o antecedente da implicac ¸ão (X) e o consequente (Y ) são conjuntos de itens em I no qual nenhum item em X pertencente a Y e vice-versa. Logo, X ∩ Y = ∅. A partir das regras de associac ¸ão são identificados itens que ocorrem com frequência em uma mesma transac ¸ão. Para que regras de associac ¸ão sejam consideradas importantes, condic ¸ões para suporte, confianc ¸a e correlac ¸ão lift geralmente devem ser satisfeitas.

Entre as técnicas de minerac ¸ão de padrões frequentes mais difundidas, destaca-se o algoritmo Apriori [START_REF] Han | Data Mining: Concepts and Techniques[END_REF]. Ele se baseia no princípio de que um conjunto de itens será frequente se todos os seus subconjuntos também forem. Em mobilidade urbana, algoritmos de identificac ¸ão de padrões sequenciais frequentes são geralmente aplicados como base para identificar padrões frequentes em trajetórias [START_REF] Giannotti | Trajectory pattern mining[END_REF].

Diversas medidas de classificac ¸ão de padrões frequentes já foram propostas e elas se dividem em objetivas e subjetivas. As técnicas objetivas baseiam-se em propriedades estatísticas e as técnicas subjetivas, em conhecimentos de especialistas sobre o domínio [START_REF] Mcgarry | A survey of interestingness measures for knowledge discovery[END_REF]. Os valores de suporte, confianc ¸a e lift são obtidos a partir de cálculos estatísticos e são classificadas como objetivas. As técnicas objetivas frequentemente retornam algumas regras que já são conhecidas ou triviais. Por outro lado, apesar da eficácia de técnicas subjetivas e sua influência na qualidade da classificac ¸ão de padrões, a técnica é custosa devido à dificuldade e à complexidade para aquisic ¸ão de conhecimentos prévios. Nesse contexto, pesquisas tem sido desenvolvidas aplicando-se uma combinac ¸ão de técnicas subjetivas e objetivas a fim de extrair as vantagens de cada uma.

Metodologia

Este trabalho tem como objetivo identificar e classificar anomalias que ocorrem no sistema de transporte rodoviário urbano a partir das séries espac ¸o-temporais derivadas de agregac ¸ões das geolocalizac ¸ões emitidas pelos ônibus da cidade do Rio de Janeiro1 . Para isso, o processo é dividido em cinco etapas: pré-processamento (1) Extract, Transform and Load (ETL) e (2) agregac ¸ão espac ¸o-temporal; (3) identificac ¸ão de anomalias; (4) identificac ¸ão de padrões frequentes e (5) avaliac ¸ão de padrões frequentes.

No pré-processamento (etapa 1), os dados são tratados até que possam ser minerados. Duas etapas principais o compõem: ETL e agregac ¸ão espac ¸o-temporal. A etapa ETL é responsável pela extrac ¸ão e limpeza dos dados abertos de mobilidade da cidade do Rio de Janeiro. Por meio da agregac ¸ão espac ¸o-temporal (etapa 2), os dados são convertidos em séries espac ¸o-temporais associadas a objetos permanentes, resultando em uma visão alternativa dos dados de mobilidade. A etapa seguinte (etapa 3) consiste na identificac ¸ão de anomalias para compreensão de impactos de eventos, mudanc ¸as no tráfego e feriados. Neste presente trabalho, as anomalias nas séries espac ¸o-temporais são identificadas com a aplicac ¸ão de conceitos estatísticos conforme proposto em [START_REF] Cruz | Detecc ¸ão de anomalias no transporte rodoviário urbano[END_REF].

De modo a extrair conhecimento útil, as anomalias são estudadas por meio da aplicac ¸ão da técnica de identificac ¸ão de padrões frequentes. Os padrões identificados, chamados de regras de associac ¸ão, configuram uma implicac ¸ão lógica, na qual o antecedente é chamado condic ¸ão e o consequente é chamado consequência. O algoritmo de identificac ¸ão de padrões frequentes adotado (etapa 4) é o Apriori. O algoritmo de identificac ¸ão de padrões frequentes é executado sobre as anomalias do transporte rodoviário variando-se os valores de suporte e confianc ¸a. Para cada valor de cada parâmetro selecionado, são avaliados os números de regras de associac ¸ão resultantes e a qualidade dessas regras. A identificac ¸ão de padrões frequentes é aplicada a duas granularidades diferentes: anomalias identificadas ao longo do ano e em cada mês individualmente.

Para classificar os padrões frequentes identificados, um método adaptado da técnica proposta por [START_REF] Liu | Analyzing the subjective interestingness of association rules[END_REF], que combina abordagens subjetivas e objetivas de classificac ¸ão, é proposto (etapa 5). Em [START_REF] Liu | Analyzing the subjective interestingness of association rules[END_REF], a selec ¸ão de regras esperadas é feita por meio da informac ¸ão dos conhecimentos de especialistas. De modo a não depender dos conhecimentos de um especialista, a primeira etapa da técnica de classificac ¸ão de padrões proposta consiste em encontrar padrões que ocorram em uma visão anual das anomalias. Dessa forma, aplica-se o algoritmo de identificac ¸ão de padrões frequentes sobre as anomalias identificadas ao longo de um ano. As regras de associac ¸ão produzidas na visão anual são consideradas regras esperadas se possuem apenas um termo na condic ¸ão e se o suporte e o lift são superiores aos valores mínimos passados como parâmetro.

A classificac ¸ão de padrões frequentes é, então, aplicada a menores granularidades (em cada mês) segundo os valores de lift e de regras não esperadas (RNE), que mensura o quão não esperada é uma regra. Para calcular o valor de RNE, as condic ¸ões (antecedentes) e consequências das regras são avaliadas, recebendo valor entre 0 e 1 para sinalizar se o antecedente (AE) e a consequência (CE) são esperados. Para isso, os termos que compõem as condic ¸ões e consequências das regras produzidas por meio da identificac ¸ão de padrões frequentes de menor granularidade são comparadas com os termos das regras esperadas produzidas na visão anual para gerar os valores AE e CE. O valor de mensurac ¸ão de regras esperadas (RE) é resultante da média aritmética dos valores AE e CE. O valor de RNE é o inverso do valor de RE. Assim, quanto maiores são os valores de RNE e do lift, maior será a relevância da regra.

Avaliac ¸ão Experimental

Essa sec ¸ão descreve os resultados obtidos pela abordagem proposta sobre dados coletados de maio de 2014 a abril de 2015. No ano de 2014, observaram-se medidas que visavam melhorias na dinâmica do trânsito no Rio de Janeiro e o Brasil sediou a Copa do Mundo. A metodologia de identificac ¸ão de anomalias aplicada sobre período avaliado resultou na identificac ¸ão de 398.662 anomalias. Com excec ¸ões de julho e de agosto de 2014, o número de anomalias identificadas em todos os meses é inferior à 1% do volume de dados total de cada mês. De modo geral, domingos possuem mais anomalias de velocidade maior que o intervalo típico em todos os meses. O mês de maio de 2014 teve maior número de anomalias que indicam velocidades inferiores ao intervalo típico. Nesse período, ocorreram diversas manifestac ¸ões, greves de rodoviários e muitas obras na cidade do Rio de Janeiro ainda não haviam sido finalizadas.

A técnica de alisamento por média foi aplicada nos dados de horário e velocidade para discretizá-los e cada unidade espacial foi associada ao bairro no qual está localizado. Foram usados o suporte mínimo de 1% e a confianc ¸a mínima de 39% no algoritmo Apriori para identificac ¸ão de padrões. O Apriori foi executado para anomalias identificadas ao longo do ano e em cada mês individualmente. Foram produzidas 292 e 2614 regras de associac ¸ão para as perspectivas anual e mensal, respectivamente.

Em problemas de padrões frequentes, espera-se encontrar regras inesperadas, novas ou que tenham utilidade em tomadas de decisões e ac ¸ões de especialistas. Algumas regras de associac ¸ão produzidas não agregam conhecimentos relevantes. Por isso, aplicase a metodologia de classificac ¸ão das regras. As regras esperadas apresentaram lift > 1 e suporte relativamente alto. Por esse motivo, regras com apenas um termo no antecedente, lift ≥ 1 e suporte > 0, 05 foram classificadas como regras esperadas. Foram identificadas 23 regras esperadas. Por exemplo, a regra {velocidade = Lenta} => {tipo = M enor} é esperada. Ela indica que quando a velocidade é Lenta, a anomalia é do tipo Menor, ou seja, inferior ao intervalo típico. Elas servem de base para classificar as regras produzidas com a aplicac ¸ão do Apriori sobre anomalias do ano e de cada mês individualmente.

A Figura 1 ilustra o número de regras por classificac ¸ão sob perspectiva de mês e ano. A análise sobre as regras de associac ¸ão para anomalias identificadas ao longo do ano identificou 70 regras como inesperadas. Aproximadamente 70% das regras são consideradas esperadas. A mesma análise foi feita para anomalias identificadas a cada mês individualmente. Para esta perspectiva, apenas 583 regras foram consideradas completamente inesperadas, ou seja, RN E = 1, e 1.282 regras, onde 0 <RNE< 1. Para fazer uma análise das regras, elas foram ordenadas de forma crescente pelo valor de RNE e número de termos na condic ¸ão, e de forma decrescente de acordo com o lif t. Com essa ordenac ¸ão, espera-se que regras inesperadas e mais generalistas estejam no topo. Seguindo esse critério, as regras classificadas como mais relevantes tem informac ¸ões de datas ou de bairros. Em relac ¸ão aos bairros, destacam-se Vila Militar, Jardim Sulacap, São Cristóvão, Manguinhos e Guaratiba com grande número de anomalias que indicaram velocidade inferior ao intervalo típico. Vila Valqueire, por sua vez, possui anomalias que indicaram velocidade superior ao intervalo típico, com 92% de confianc ¸a.

Por meio da análise das regras que contém informac ¸ão de data na condic ¸ão, a regra classificada como mais relevante é o dia 29/06/2014 (domingo), que tem como consequência a velocidade inferior ao intervalo típico. A regra, além de ir contra o tipo de anomalia esperada para um domingo, possui lift = 2, 17 e 91% de confianc ¸a. Uma análise sobre reportagens referentes a data em questão indicou que, além de estar ocorrendo a Copa do Mundo, houve um protesto na zona sul do Rio de Janeiro e uma operac ¸ão conjunta da Secretaria de Ordem Pública e Secretaria de Municipal de Transportes de fiscalizac ¸ão de táxis na Rodoviária Novo Rio.

Conclusão

Este trabalho propõe uma metodologia para identificar e classificar as anomalias no comportamento do trânsito analisadas por agregac ¸ões espac ¸o-temporais. Foram usados dados da cidade do Rio de Janeiro. A metodologia proposta identificou características das principais anomalias e classificou-as como esperadas ou inesperadas. A aplicac ¸ão da identificac ¸ão de regras esperadas se mostrou eficiente não apenas para classificac ¸ão das anomalias pontuais, como para entendimento de comportamentos sistêmicos do trânsito. Existem ainda, oportunidades para trabalhos futuros com a aplicac ¸ão da metodologia proposta em outros conjuntos de dados, como dados de sistemas de transporte privado e táxis. Diferentes técnicas de identificac ¸ão de anomalias também podem ser exploradas a fim entender como elas podem impactar nos resultados e nas análises.

Figura 1 .

 1 Figura 1. N úmero de regras por classificac ¸ão sob perspectiva de m ês e ano.

SBC 33rd Brazilian Symposium on Databases (SBBD) August 25-26, 2018 -Rio de Janeiro, RJ, Brazil

Os dados são obtidos pelo Portal de Dados Abertos da Prefeitura do Rio de Janeiro: http://data.rio/

SBC 33rd Brazilian Symposium on Databases (SBBD) August 25-26, 2018 -Rio de Janeiro, RJ, Brazil

Este artigo propõe a identificac ¸ão e a classificac ¸ão de anomalias no sistema de transporte rodoviário urbano a partir de agregac ¸ões espac ¸o-temporais a objetos permanentes.