Trabalho premiado de computação propõe novas formas para avaliar algoritmos, reduzindo distorções e gerando dados que podem ser usados no planejamento de infraestrutura
O estudo usou como base diferentes malhas urbanas de cidades ao redor do mundo, como São Paulo, Maceió, Barcelona e Bogotá, para avaliar algoritmos de visualização de dados – Fotomontagem Jornal da USP com imagens de: E_Pluribus_Anthony/chris 論/Wikimedia Commons; Nikhil Kurian/Pixabay
Cidades e grandes centros urbanos concentram enormes quantidades de dados que, muitas vezes, precisam ser adequadamente tratados para servirem de informações relevantes em áreas como transporte, segurança e planejamento de uma determinada região. Pesquisadores do Instituto de Ciências Matemáticas e de Computação (ICMC) da USP publicaram um artigo sobre a eficácia de diferentes algoritmos de organização de dados espaciais de áreas urbanas pautadas na ordenação de vértices em grafos.
Grafos nada mais são que estruturas matemáticas que representam relações entre conjuntos de informações. Eles são formados por vértices ou nós que são interligados por arestas. O conjunto dessas conexões é capaz de formar diagramas, que ajudam na visualização de grandes quantidades de informações e são úteis para a área de ciência de dados. A tarefa dos pesquisadores era organizar grafos e vértices de forma que pudessem representar localizações do mundo real e suas conexões.
Os grafos são como teias de informações, conectadas umas às outras por arestas – Foto: Martin Grandjean/Wikimedia Commons/CC BY-SA 4.0
Thales Vieira – Foto: Arquivo pessoal
“Cada ponto da cidade pode ter uma série de dados diferentes, que podem ser usados no planejamento de infraestrutura, seja ela pública ou privada”, comenta Thales Vieira, professor associado da Universidade Federal de Alagoas (Ufal) e um dos autores do artigo. Utilizando contextos urbanos, o estudo se baseou na análise dessas teias de informações. Formadas a partir de mapas de cidades como São Paulo, Maceió, Barcelona e Bogotá, elas concentram os dados de interesse somente nas esquinas (vértices) das ruas.
O desafio desse tipo de organização envolve as possíveis distorções que ocorrem na etapa de ordenação dos dados espaciais em único eixo, como ao inseri-los em um gráfico. A ideia é similar a representar o mapa-múndi do globo terrestre: ao lidar com mais de duas dimensões, qualquer representação em menores dimensões – como numa folha de papel ou numa tela de computador – sofrerá distorções. “Esses vértices estão em 2D e você precisa ordená-los em uma reta. Não tem como fazer isso sem perder informações”, diz Vieira.
Victor Barella – Foto: Arquivo pessoal
O professor explica que, sabendo que as esquinas estão espalhadas pelo mapa de uma cidade e que não é possível escapar dessas distorções, o ideal seria manter vizinhanças, ou seja, estabelecer intervalos próximos na ordenação que representem esquinas próximas no mapa. “Tem várias maneiras de se fazer essa ordenação, e no artigo a gente trabalha em como medir se uma ordenação ficou boa ou não”, completa Victor Barella, pós-doutorando no ICMC e integrante da pesquisa.
Redução de dimensões
As técnicas de ordenação de vértices foram avaliadas por meio de dois métodos visuais: forward e inverse. Ambas as análises partem do conceito que uma boa ordenação depende do quão próximos, ao longo de uma reta, estão os vértices que estão próximos no mapa. Enquanto a abordagem forward utiliza áreas de retângulos para verificar a proximidade desses vértices – que devem estar próximos em trechos da reta – no mapa, a abordagem inverse trabalha com regiões circulares para observar se os vértices dentro do raio do círculo também estão próximos na reta.
“Não queremos que essas esquinas consecutivas [vértices próximos] fiquem muito espalhadas pela cidade porque, na hora de fazer um gráfico com alguma propriedade que essas esquinas tenham, esse gráfico não vai ficar legal. Vai juntar esquinas que estão muito distantes num pequeno intervalo do eixo X [reta]”, explica Vieira ao citar o risco de perda de informações a partir das distorções geradas por uma má ordenação.
A partir de testes, os pesquisadores verificaram que o algoritmo t-SNE (t-distributed Stochastic Neighbor Embedding) foi o mais eficaz na aplicação de ordenação de vértices em diferentes cidades. Karelia Salinas, doutoranda do ICMC e que também participou do artigo, explica que o t-SNE é um de muitos métodos de redução de dimensionalidade — simplificação dados sem perder significativamente suas propriedades originais — que existem e é usado em outros contextos de visualização de dados. Pelo estudo, descobriu-se que ele funciona muito bem com dados urbanos sobre gráficos de ruas em cidades.
A pesquisa desenvolvida no Centro de Ciências Matemáticas Aplicadas à Indústria (CeMEAI) foi destaque na 37ª Conferência sobre Gráficos, Padrões e Imagens (Sibgrapi 2024), um dos maiores eventos da América Latina na área de computação. O trabalho foi eleito o melhor na categoria Computação Gráfica e Visualização.
O artigo A visual methodology to assess spatial graph vertex ordering algorithms pode ser lido aqui.
Mais informações: victorhb@icmc.usp.br, com Victor Barella; karelia@usp.br, com Karelia Salinas; thales@ic.ufal.br, com Thales Vieira
Texto: Fernanda Zibordi – Estagiária com orientação de Tabita Said. Com informações do ICMC
Arte: Diego Facundini – Estagiário sob supervisão de Moisés Dorado
Por Jornal da USP
