Agrupamento não-supervisionado

Aprenda a avaliar a qualidade de um cluster

O mundo de Big Data possibilitou a extração de conhecimento útil a partir de dados coletados. Uma forma bastante utilizada para conhecer os usuários de algum serviço é agrupá-los de acordo com uma ou mais features, utilizando técnicas não-supervisionadas do aprendizado de máquina, muitas vezes referidas simplesmente como clustering. Esse agrupamento pode facilitar a descoberta de características de usuários similares e importantes. Tais características nem sempre são fáceis de serem identificadas, mesmo em análises mais profundas, uma vez que a diversidade dos dados pode causar interferência nos resultados de outras técnicas.

O primeiro desafio é categorizar os clientes de acordo com as features desejadas. Tais features podem ser obtidas através de cálculos matemáticos, identificação de padrões ou através de outro conjunto de características. Um outro desafio que merece atenção é a presença de outlier, uma vez que a utilização de algumas métricas estatísticas são sensíveis a valores muito fora do padrão.


Outlier em um Agrupamento

Nem sempre os outliers são simples de serem removidos, principalmente se estes forem esparsos entre si e com poucas características em comum. Em alguns tipos de features numéricas, este caso se agrava, pois é difícil classificar um valor como outlier sem maiores estudos. Com os dados ordenados, poderíamos por exemplo, decidir retirar uma porcentagem de dados do final da nossa estrutura, mas qual o valor percentual mais adequado? Ele representa bem os outliers? Será que não estamos removendo poucos ou muitos dados? Somente os outliers demandam um estudo próprio e a solução encontrada pode ser adequada para o conjunto de dados atuais. Mas será que a solução continuará eficaz com uma leve mudança nos dados? É por este motivo que muitas vezes é preferível manter os outliers, visto que a sua retirada pode resultar em uma melhoria muito baixa se comparada ao trabalho demandado. Para se chegar a uma conclusão sobre a remoção de outliers, é indicado uma avaliação de qualidade dos clusters.

A avaliação de qualidade vai mostrar possíveis inconsistências no agrupamento obtido, possibilitando uma maior compreensão dos dados e resultados, e consequentemente impedindo que tais inconsistências sejam tratadas como conhecimento. Uma inconsistência pode levar a tomada de decisão baseada em uma situação não condizente com a realidade, e isso pode custar caro! Apesar da importância de uma avaliação da qualidade dos clusters, ainda é difícil encontrar conteúdo para auxiliar nessa avaliação. Mesmo com todo o estudo e aprimoramento dos algoritmos existentes, nem sempre os clusters obtidos são considerados “bons”.

Teoricamente, uma boa clusterização possui grupos compostos por dados próximos entre si (baixa distância intra-cluster), e bem distantes em relação aos dados de outros grupos (alta distância inter-cluster). Em alguns casos, também é esperado que os grupos possuam aproximadamente o mesmo tamanho e que seus centróides, ou seja, o ponto médio de seus dados, sejam bem separados. Existem outras métricas que podem ser aplicadas para avaliação de um agrupamento (Coeficientes de Silhueta (en.wikipedia.org/wiki/Silhouette_(clustering)) e outros) , porém neste artigo trataremos apenas das métricas citadas anteriormente.

Distância entre Pontos

A primeira métrica que falaremos é a que prevê a medição entre os pontos de um agrupamento. Esse cálculo é aplicado em duas frentes: é calculada a distância entre os pontos de um mesmo grupo (distância intra-cluster) e a distância entre pontos de grupos distintos (distância inter-cluster).

        A distância intra-cluster irá representar o quão bem relacionados estão os dados. Ou seja, dados altamente relacionados estão mais próximos entre si do que dados com pouca relação.

Distância intra-cluster

Na figura acima vemos que os dados do cluster rosa claro seriam os mais bem relacionados entretanto, o outlier faz a distância média entre os pontos do cluster aumentar. Os pontos do cluster roxo são mais separados que os do grupo rosa, porém a relação entre seus pontos ainda é maior do que a do grupo de cor azul. Vemos então, que quanto menor a distância média intra-cluster, melhor o seu grupo será.

Porém, como podemos imaginar, somente estes valores não serão capazes de representar bem o agrupamento. É aqui que entra os valores de distância inter-clusters. Estes valores são obtidos através do cálculo da menor distância entre dois pontos de clusters distintos.

distância entre clusters

No mesmo exemplo, vemos que a distância entre os grupos roxo e rosa é maior que a distância entre os grupos roxo e azul. Isso acontece porque os dados presentes no cluster rosa são menos relacionados com os dados do cluster roxo do que os dados do cluster azul. Assim, vemos que quanto maior a distância inter-cluster, melhor será o agrupamento.

Porém, existem casos em que os grupos obtidos possuem tantos dados e eles são tão próximos entre si, que a aplicação desta métrica se torna, se não inviável, não tão precisa quanto deveria. Nestes casos, podemos utilizar o cálculo da distância entre centróides.

Distância entre Centróides

Os centróides são os pontos médios de um cluster, ou seja, é um ponto localizado no centro de massa de um grupo, onde existe uma maior concentração de dados. Esta é uma técnica que pode ser utilizada quando existem muitos dados e estes são relativamente próximos de pontos de outro grupo.

Distância entre os centróides dos clusters

Como vemos na figura acima, apesar da pouca distância entre os clusters azul e roxo, a distância entre seus centróides é tão grande quanto, se não maior, que a distância entre os centróides dos clusters roxo e rosa. Isso significa que, apesar de alguns dados dos grupos azul e roxo serem relacionados, essa relação não representa a maior parte dos elementos desses grupos.

Essa técnica pode ser atrelada à uma análise de pontos de fronteira, como descrito a seguir.

Densidade de Pontos na Fronteira

A análise de pontos de fronteira é uma técnica que busca calcular e estudar a densidade de pontos entre dois centróides, especificamente aqueles pontos localizados bem no meio dessa distância. Essa análise pode ser aplicada quando a distância inter-cluster é baixa, para verificar se, apesar disso existem poucos pontos na fronteira entre os clusters.

Quantidade de Pontos na Fronteira entre os Clusters

No mesmo exemplo, vemos que é apenas um ponto na fronteira entre os grupos azul e roxo que faz com que a distância inter-cluster seja pequena, logo o agrupamento não é ruim como parecia.

Tamanho dos Clusters

A última métrica prevê a análise da quantidade de pontos em um cluster. Em muitos casos, um bom agrupamento deve possuir grupos homogêneos, inclusive em seu tamanho. Para realização deste cálculo pode ser utilizada a Entropia de Shannon, dada pela fórmula abaixo:

H(X) = -i=1np(xi)logbp(xi)

No qual representa a probabilidade de se escolher o dado i no conjunto de dados X e b a base escolhida para o logaritmo. O resultado deste cálculo será um valor entre 0 e 1. Para uniformizarmos este intervalo, vamos dividir o resultado da entropia por e teremos sempre um valor no intervalo fechado entre 0 e 1. Quanto maior o valor da entropia, mais bem distribuído e homogêneo é o agrupamento.

Então pessoal, todas as técnicas têm seus prós e contras e estes devem ser avaliados antes de sua aplicação.


Análise Exploratória de Dados Geoespaciais

Localização de Usuários Móveis

Nos últimos anos, notou-se um crescimento significativo na coleta de dados de localização de usuários móveis. Com isso, a indústria e a academia estão investindo cada vez mais em soluções que possibilitem a extração de conhecimento útil a partir desses dados.

As localizações dos usuários móveis são fontes importantes de informação para a chamada computação urbana, que visa melhorar a qualidade de vida dos cidadãos em termos de mobilidade, qualidade do ar e infraestrutura de tecnologia. Ao se conhecer as características geoespaciais dos usuários de uma cidade e clientes de uma empresa, por exemplo, é possível, além de oferecer melhores serviços, ofertar soluções mais personalizadas e cientes do contexto atual em que os usuários se encontram.

Existem vários desafios que tornam a extração de conhecimento a partir de dados geoespaciais não-trivial. Primeiramente, a coleta desses dados deve ser com uma certa frequência que permita que resultados precisos sejam alcançados, sem consumir os recursos de energia e comunicação dos usuários. Além disso, deve-se ter cuidado com a precisão dos dados, já que mesmo o GPS possui uma margem de erro que aumenta em ambientes fechados ou com muitos obstáculos. Considerando o grande número de usuários, o armazenamento e tratamento desses dados devem ser eficientes, para que grandes volumes de dados possam ser utilizados pelos algoritmos.

Além dos desafios técnicos, deve-se tomar alguns cuidados devido às características dos dados. Em geral, dados geoespaciais referem-se a dois valores representando a latitude e longitude que indicam uma posição na Terra. Esses valores são medidos em graus (exemplo: 19°55’54.5″S 43°56’16.8″W), sendo na maioria das vezes descritos em valores decimais, em que os minutos e segundos são convertidos para valores decimais e o sinal indica o hemisfério (exemplo: -19.931803, -43.938012).

Vale destacar que a diminuição da precisão de uma latitude ou longitude leva a um aumento no erro da localização, sendo que esse erro varia de acordo com a localização ao longo da Terra.

Conheça duas estratégias essenciais para a análise exploratória de dados geoespaciais.

Cálculo de Distâncias

Antes de apresentar as técnicas de análise, é importante falar um pouco sobre o cálculo de distâncias entre duas localizações.

Muitas vezes, é preciso calcular a distância entre dois pontos. Como exemplo, pode-se citar o estudo para implantação de uma antena de celular, o cálculo de estimativa de deslocamento de um usuário móvel e uma análise de contatos entre usuários. Para isso, é preciso ficar atento e lembrar que a Terra é redonda (não é uma esfera perfeita, e isso é pauta para outro momento), e que o cálculo de distância em uma esfera é diferente de um plano. Ou seja, a não ser que as distâncias sejam pequenas ou que uma margem de erro alta seja aceitável, a distância Euclidiana não será precisa. No entanto, cientistas já definiram fórmulas para o cálculo dessa distância, sendo a distância Haversine (en.wikipedia.org/wiki/Haversine_formula) a mais famosa por ser eficiente computacionalmente e muito precisa.

Vale destacar que esse cálculo retorna a distância em linha reta e que muitas vezes o deslocamento feito por um usuário está longe de ser uma linha reta. Em outras palavras, para se analisar dados de mobilidade e trajetória de usuários, é preciso mais do que isso. Uma solução é transformar o mapa viário de uma cidade de interesse em um grafo onde as arestas representam as vias de deslocamento e os vértices representam as interseções entre essas vias, e utilizar algoritmos de grafos para estudar as trajetórias, traçar o caminho mais curto e definir as melhores rotas, por exemplo. Para isso, uma alternativa é utilizar o excelente projeto colaborativo chamado OpenStreetMap (openstreetmap.org), que fornece detalhes de mapas em formatos que podem ser trabalhados computacionalmente.

Análise Exploratória

Com os dados geoespaciais em mãos, é importante fazer uma primeira análise exploratória para se ter uma visão geral dos dados. Seguem algumas dicas e técnicas:

  • Como em toda análise de dados, é preciso inicialmente limpar e remover ruídos que possam interferir nos resultados. Essa tarefa envolve, por exemplo, remover dados com localizações nulas ou inconsistentes. Também pode ser necessário fazer um filtro de uma região de interesse. Caso essa região seja um círculo, é suficiente definir o centro e o raio do círculo para remover localizações fora dele. Caso a região de interesse seja uma outra forma geométrica qualquer, é preciso utilizar alguma API específica, como por exemplo a Shapely para Python (pypi.org/project/Shapely).
  • Após limpar e filtrar os dados, é possível visualizar os mesmos em um mapa, para que sejam observados alguns padrões. Uma primeira forma bem simples é plotar todos os pontos no mapa. Essa estratégia funciona bem com poucos pontos, mas não agrega valor algum quando grandes volumes de dados são utilizados (como o mapa abaixo):
  • Uma outra estratégia que ajuda a visualizar a distribuição dos pontos é o chamado Mapa de Calor (heatmap). Esse mapa mostra onde os pontos estão concentrados de forma mais abrangente. Porém, nem sempre é possível visualizar as características de regiões mais específicas e menores.
  • Para se ter mais detalhes de uma região específica, o agrupamento por densidade de pontos pode também ajudar. Nessa técnica, pontos próximos são agrupados e a densidade do grupo é apresentada, indicando os locais mais densos de forma quantitativa.
  • Uma última alternativa que permite que se tenha uma visão mais detalhada é separar a área de interesse do mapa em quadrantes, e calcular a densidade para cada quadrante. Com isso, é possível escolher o tamanho ideal do quadrante para cada caso, e a coloração do mapa de calor indicará mais precisamente os locais mais e menos densos. Para essa solução, também é necessário utilizar alguma API de manipulação de formas geométricas, como a Shapely para Python.
  • Em muitas análises, além da dimensão espacial, a dimensão temporal também é relevante. Ou seja, tem-se interesse em verificar pontos espaciais ao longo do tempo. Para que essa análise seja feita, uma opção é fazer snapshots em intervalos de tempo definidos, gerando várias imagens ao longo do tempo. Esse intervalo de tempo pode ser tão curto quanto necessário, gerando um número muito grande de imagens, que podem então ser combinadas em um vídeo.

E para fechar:

É notável a existência de grandes volumes de dados geoespaciais coletados de dispositivos móveis. Esse contingente será ainda maior em um futuro próximo, quando veículos autônomos e a Internet das Coisas estiverem consolidados e mais facilmente acessíveis. Apesar de ajudarem na extração de conhecimento, as técnicas existentes ainda podem ser melhoradas e otimizadas. Portanto, existe um grande desafio de pesquisa e desenvolvimento para que seja possível obter o máximo de informação útil a partir de grandes volumes de dados brutos de localização.

Na Cinnecta, em parceria com a UFV, buscamos sempre a inovação e por isso avaliamos constantemente novas técnicas e algoritmos que auxiliem nessa tarefa.