Grafos e NLP para redução de custos com Google Maps

O foco do meu doutorado é detecção de anomalias em grafos. Uma vez realizei uma análise com um conjunto de dados que parecia perfeito para testar as técnicas que eu estava desenvolvendo naquele momento. O conjunto continha dados sobre a evolução de todos os casos COVID-19 de uma cidade ao longo do tempo.

A estrutura do dataset era bem simples: cada linha era um possível (ou confirmado) caso de COVID-19 contendo diversas informações - anonimizadas - sobre a evolução daquele caso, incluindo o endereço aproximado do paciente.

Minha ideia inicial consistia em utilizar os endereços para modelar um grafo e utilizar sua estrutura relacional para analisar as propriedades dos pacientes. Além disso, eu ainda poderia analisar a evolução na quantidade de casos por bairro.

Como modelar um grafo a partir de uma série de endereços?

Aqui a coisa começou a complicar um pouco. Eu precisava transformar aqueles endereços em pontos para conseguir calcular a distância entre eles e, então, modelar o grafo. O problema aqui era que os endereços contidos na base de dados eram escritos de forma livre, não existia segmentação entre cidade, bairro, rua... era uma string única escrita de forma livre pelo usuário.

Isso significa que a quantidade de endereços "únicos" era absurdamente maior até mesmo do que a quantidade de ruas existentes na cidade. Isso acontecia porque não existia padrão no cadastro de endereços, então cada endereço era único pois cada usuário escrevia um mesmo endereço de forma diferente.

Meu primeiro pensamento foi usar a API do Google Maps para padronizar os endereços e, depois, calcular a matriz de distâncias entre eles. Essa solução resolveria o problema das distâncias e o problema dos endereços não padronizados, visto que a API do Google Maps recebe o endereço como uma string.

Eu tinha alguns créditos no Google Cloud que poderia utilizar para isso e achei que seria suficiente. Quando calculei a quantidade de requisições que seriam necessárias, descobri que, não só os créditos seriam insuficientes, como eu ainda teria um custo adicional relativamente alto pelo volume de dados. Esse custo adicional era inviável naquele momento e eu comecei a pensar em estratégias para contornar essa situação.

Como reduzir a quantidade de chamadas necessárias e ainda obter todos os dados necessários?

A estratégia que adotei para contornar essa situação foi utilizar técnicas de NLP para reconhecer padrões nos endereços e agrupar aqueles que, mesmo escritos de formas diferentes, tinham grande probabilidade de representarem o mesmo lugar. Com o grafo e seus agrupamentos, eu poderia geolocalizar com a API do Google Maps apenas um endereço de cada grupo e não cada endereço individualmente.

Considerei as relações de adjacência para eleger um head de cada cluster. Escolher o elemento com maior número de conexões aumentaria a chance de conseguir usar aquele endereço geolocalizado para normalizar demais do mesmo cluster.

Com os heads de clusters escolhidos, a quantidade de requisições necessárias seria consideravelmente menor e os créditos que eu possuía seriam mais do que suficientes. Com o endereço do head de cluster geolocalizado, bastou utilizar novamente técnicas de NLP para comparar e normalizar os demais endereços. Depois desse processo surgiram algumas anomalias pontuais que foram facilmente tratadas.

No final de todo esse processo, eu tinha todos os endereços normalizados e separados por cidade, bairro e rua. Além de ter os dados de latitude e longitude de todos. Com a informação tratada e normalizada, utilizei a API do Google Maps novamente para calcular a matriz de distâncias entre os bairros e, finalmente, consegui modelar o grafo de endereços.

Depois de tudo isso eu poderia, finalmente, começar minhas análises.