Para alguns problemas de aprendizado de máquina, um agente precisa explicitamente de supervisão para informá-lo se os dados que ele (agente) está recebendo possuem um determinado rótulo classificador ou valor numérico. Esse tipo de aprendizado de máquina é comumente chamado de Aprendizado Supervisionado.

Embora o aprendizado supervisionado seja muito utilizado, ele não resolve todo tipo de problema. Para os problemas que não possuem uma base de dados já rotulada ou com valores numéricos que identifiquem nossos dados de treino, precisamos de um agente baseado em Aprendizado Não-Supervisionado.

Neste texto, veremos um pouco mais sobre agentes como esses últimos, que não necessitam de supervisão. Mas caso você esteja precisando de uma revisão do que é aprendizado supervisionado, escrevi esse outro texto no IAsc: Aprendizado de Máquina Supervisionado com Python.

Aprendizado Não-Supervisionado

Aprendizado não-supervisionado é a forma de aprendizado de máquina em que o agente recebe um conjunto de dados de treino não-rotulados e precisa aprender algo sobre os dados em questão. Depois disso, quando aparecerem dados de teste, o agente deve ser capaz de informar o que aprendeu com os dados de treino aplicando esse conhecimento nos dados de teste.

Uma das maneiras mais populares de se implementar o aprendizado não-supervisionado é por meio do aprendizado de agrupamentos (do inglês, clustering). Após a convergência de algoritmos de aprendizado de agrupamentos, cada agrupamento é um bloco de uma partição do conjunto de dados de treino que agrupa dados considerados próximos entre si. Apesar de agrupar, fica a cargo de algum analista ou cientista de dados entender quais as características fundamentais de determinado agrupamento. Em seguida, se é fornecido um dado de teste,
o algoritmo é capaz de informar a qual agrupamento pertence o dado de teste.

Existem algumas técnicas de aprendizado não supervisionado como: mapas auto-organizáveis e agrupamentos k-means. Neste texto iremos usar apenas agrupamentos k-means.

k-means

k-means é um popular algoritmo de aprendizado não-supervisionado que gera agrupamentos a partir de um conjunto de dados de treino. A saída gerada pelo k-means pode ser enxergada como um diagrama de Voronoi, que é um particionamento do conjunto de dados com alguns pontos centrais (também chamados de centroides). Os centroides são os dados que melhor representam o agrupamento. A Figura 1 representa um diagrama de Voronoi.

Diagrama_de_Voronoi
Figura 1 – Diagrama de Voronoi

A proximidade entre os pares de dados de treino pode ser calculada com diferentes noções de distância. Por exemplo, podemos usar distância Euclidiana ou distância de Manhattan. Diferentes fórmulas de distância utilizadas provavelmente irão gerar diferentes agrupamentos já que os cálculos não são os mesmos.

O algoritmo k-means gera agrupamentos da seguinte maneira:

  1. Recebe um inteiro positivo k e um conjunto de n dados de treino, cada um deles descrito por um vetor numérico com comprimento d.
  2. Define k pontos aleatórios no espaço dimensional d, i.e., k centroides aleatórios.
  3. Enquanto os k pontos não convergirem:
    1. Para cada dado de treino, o algoritmo encontra qual é o centroide mais próximo e define-o como representante do dado de treino.
    2. Para cada agrupamento, o algoritmo encontra quem são os dados de treino agrupados por esse ponto k, calcula a média aritmética desses dados de treino e define o resultado como novo valor para representar o agrupamento, i.e., atualiza o valor do centroide.

Implementações de k-means

O algoritmo k-means já foi implementado por muitas bibliotecas de aprendizado de máquina. Se o seu interesse por k-means é apenas prático (i.e., aplicar em algum problema real), não vale a pena tentar reinventar a roda. E neste caso, a melhor opção é usar uma biblioteca existente para sua linguagem de programação preferida. Para Python, temos algumas opções como Scikit-LearnSciPyTensorFlowOpenCV. Para Java, também temos o TensorFlow, e outras opções como WekaApache Mahout.

Se você utiliza alguma outra linguagem de programação, recomendo que pesquise no Google, não deve ser difícil encontrar alguma biblioteca que implemente o k-means.

Assim como foi feito no texto sobre aprendizado de máquina supervisionado, neste texto será utilizada a biblioteca Scikit-Learn, que é compatível com Python. A escolha feita foi essa porque além de ser uma das bibliotecas mais conhecidas e utilizadas, Python facilita a exibição de gráficos com Matplotlib e utilizei essa biblioteca para gerar alguns dos gráficos desse post.

Exemplos com k-means

Problema com uma variável

Como muitos já sabem, eu gosto de futebol apesar do meu time, o São Paulo FC, não estar bem nos últimos anos. A primeira ideia que tive foi aplicar o k-means sobre as pontuações dos times do Campeonato Brasileiro de 2016 e verificar como o k-means agrupa os times.

Aplicando o k-means com k=5 sobre a pontuação dos times, o resultado na Figura 2 mostra 5 agrupamentos que acabam indicando a qualidade desses times. Como eu só usei a variável pontuação, os agrupamentos são baseados nessa variável. Quais foram os agrupamentos gerados? Se olharmos pelo ponto de vista de centroide, os pontos foram: [[32.0], [45.25],[52.28], [59.33], [74.0]]. O que isso indica? Que os times cujo centroide é 32.0, são times que não foram bem no campeonato e realmente tinham características de times rebaixados. O Internacional foi rebaixado com 43 pontos, mas aparece como último time do penúltimo centroide (amarelo).

Do outro lado do gráfico, times de centróide 74, eram times com pontuações de times muito bons. Nesse agrupamento ficaram Palmeiras (que foi o campeão), Santos e Flamengo (que disputaram o título). O Atlético-MG que terminou com 62 pontos aparece como um time bom, mas no segundo grupo da direita para esquerda (verde).

kmeans_k5_campeonato_brasileiro
Figura 2 – Agrupamentos gerados pelo k-means (k=5) sobre as pontuações dos 20 times da Série A no Campeonato Brasileiro de 2016.

Como podemos perceber, a maior parte dos times ficou nos grupos de cor amarela, ciano (São Paulo FC ficou aqui) e verde. Observe que o algoritmo foi capaz de aprender 5 grupos de acordo com as pontuações dos times, mas não foi capaz de dar significado a esses grupos. Poderíamos dar os seguintes nomes aos agrupamentos com base nos desempenhos de seus times: Muito Ruim, Ruim, Médio, Bom e Muito Bom. Com uma variável foi fácil entender os agrupamentos formados.

Como podemos testar o aprendizado de máquina não supervisionado? Imagine que temos um time, por exemplo: “Para Qual Lado é o Gol FC” e queremos saber se esse time irá conseguir fugir do rebaixamento este ano? Podemos inserir novos dados para o k-means como uma estimativa dos pontos que acreditamos que iremos conquistar e o k-means inserirá nosso time em um dos agrupamentos. Se a pontuação for muito baixa, provavelmente seremos rebaixados. Mas se conseguirmos mais do que 43 pontos, temos alguma chance de escapar? Testando com uma pontuação igual a 45, obtivemos do algoritmo o agrupamento de cor amarela, mesmo no qual o Internacional FC apareceu. Pode ser que 45 pontos não sejam suficientes e essa abordagem não é tão precisa porque usamos apenas a edição de 2016 do campeonato brasileiro. Se colocássemos no mesmo gráfico mais pontuações, considerando outros anos, poderíamos provavelmente chegar em um número mais confiável, mas aí estaríamos lidando com duas variáveis.

Problema com duas variáveis

Para manter a clareza de exemplo, vamos trabalhar num outro problema a partir de agora. Suponha que estamos no ano 2021 e uma das promessas do prefeito de São Paulo na última eleição foi a construção de um Giga Hospital (gigante mesmo) e como esse é um prefeito honesto e diferente da maior parte dos políticos brasileiros que conhecemos, ele decide que vai cumprir a promessa do Giga Hospital. Mais do que isso, ele quer que o Giga Hospital atenda o maior número possível de pessoas. Aqui estamos supondo que a cidade terá aproximadamente 12 milhões de habitantes.

A tabela a seguir ilustra a distribuição da população em nosso exemplo:

População Aproximada por Região em São Paulo/SP
Região População (em milhões de pessoas)
Zona Leste ~5
Zona Sul ~3
Zona Norte ~2
Zona Oeste ~1
Centro ~1

Esse é o primeiro Giga Hospital e o prefeito quer que as pessoas vejam a obra dele. Em qual região o prefeito deve ordenar a construção do hospital? Realizei um mapeamento grosseiro na Figura 3 em que para cada 1 milhão de pessoas, há 1 unidade representada por um ponto no gráfico. Apesar da aproximação ser grosseira, acredito que seja didática.

grafico_municipio_sp
Figura 3 – Mapa da Cidade de São Paulo dividido em regiões. Os pontos verde-escuros indicam onde está concentrada a população do nosso exemplo.

Suponha também que dos impostos que pagamos, sobrou verba para apenas 1 Giga Hospital. Para k=1, o algoritmo k-means do Scikit-Learn nos diz por meio da Figura 4 que o hospital (cruz vermelha) deve ficar na transição entre a Zona Sul e a Zona Leste, mas bem próximo ao centro da cidade. Dessa forma, o algoritmo está considerando o menor deslocamento da maior parte da população que no nosso exemplo está na Zona Sul e na Zona Leste.

grafico_municipio_sp_k1_hospital
Figura 4 – Mapa da Cidade de São Paulo dividido em regiões. Os pontos verde-escuros indicam onde está concentrada a população do nosso exemplo. A cruz indica onde deveria ser construído o Giga Hospital.

Mas e se o prefeito tivesse prometido 2 hospitais? Com k=2, a Figura 5 mostra que um hospital poderia atender a Zona Leste (cruz verde clara), que possui quase metade da população; enquanto o outro (cruz vermelha), poderia ficar entre a Zona Oeste e a Zona Sul.

grafico_municipio_sp_k2_hospital
Figura 5 – Mapa da Cidade de São Paulo dividido em regiões. Os pontos verde-escuros indicam onde está concentrada a população do nosso exemplo. As cruzes de outra cor, indicam onde deveriam ser construídos os Giga Hospitais.

Neste momento, o prefeito percebe que se eliminar algumas fontes de corrupção, seria possível ter um terceiro hospital e desafogar o hospital mais central da Figura 5. Ele pede para a equipe de TI da prefeitura enviar relatórios com k=3. Qual o resultado? Nesse cenário, a Figura 6 mostra que o prefeito poderia mandar construir um hospital na região central da Zona Leste (cruz vermelha), um outro na região Central da Zona Sul (cruz verde clara) e outro na fronteira da Zona Oeste com o Centro da cidade (cruz azul).

grafico_municipio_sp_k3_hospital
Figura 6 – Mapa da Cidade de São Paulo dividido em regiões. Os pontos verde-escuros indicam onde está concentrada a população do nosso exemplo. As cruzes de outra cor, indicam onde deveriam ser construídos os Giga Hospitais.

Poderíamos usar k ainda maiores, mas nesse caso seria difícil o prefeito conseguir cumprir a promessa. Podemos ver com isso, que muitas vezes a realidade determina qual valor de k devemos passar para o k-means.

Esse foi um exemplo um pouco mais didático e adaptado para nossa realidade. Mas se fôssemos da equipe de TI da prefeitura e incumbidos de gerar um sistema que calculasse o melhor local para a construção de um hospital, teríamos que considerar muitas outras variáveis como: números mais exatos de pessoas, distribuição da população pelos bairros, locais onde já existem hospitais ou não e o índice de satisfação no atendimento, terrenos que a prefeitura poderia usar, etc.

Embora o k-means possa ser utilizado na vida real, nem sempre é fácil conferir os agrupamentos e quais foram os fatores determinantes já que a visualização gráfica costuma ser mais difícil quando temos 4 ou mais variáveis.

Apesar de termos focado na criação dos agrupamentos, este é um problema de aprendizado de máquina porque se daqui alguns anos surgir uma nova região ou bairro na cidade, o algoritmo é capaz de indicar qual hospital essas pessoas devem usar considerando os que já existem. Para fazer isso, o k-means indica qual o melhor agrupamento para representar uma dada observação (x, y). Por exemplo, se os hospitais de Osasco passassem por uma reforma e enquanto isso os moradores da região fossem orientados a irem em hospitais de São Paulo, o algoritmo indicaria a cruz azul da Figura 6 para essas pessoas.

Os códigos-fonte dos exemplos deste texto estão disponíveis no meu GitHub.

Neste post vimos como funciona o aprendizado não-supervisionado com k-means. Vimos também exemplos de aplicação do k-means em problemas com uma variável (pontuação dos times) ou 2 variáveis (coordenadas de localização). Consegue imaginar um problema com 3 variáveis? Um bom exercício é tentar encontrar algum problema do seu dia-a-dia em que encontrar agrupamentos pode ser bom para o seu negócio. Por exemplo, você trata todos seus clientes da mesma forma? Que agrupamentos o k-means formaria com k = 2 ou k = 3 sobre seus clientes ou fornecedores?
Espero que tenham gostado do texto. Se você visita o blog frequentemente e não quer perder nenhum texto, não deixe de seguir o IAsc. Outra forma de acompanhar os textos é me seguindo no Facebook, Instagram, ou Twitter. Muito obrigado pela visita e até o próximo texto!

Referências

  1. Grus, Joel. Data Science do Zero. Primeiras Regras com o Python
  2. Lavrenko, Victor. K-Means Clustering: How it works? URL
  3. Mapas para Colorir. URL
  4. Wikipedia – Diagrama de Voronoi. URL
  5. Wikipedia – Voronoi cell. URL
  6. Wikipedia – Divisão Territorial e Administrativa da Cidade de São Paulo. URL
  7. SAS – Machine Learning. URL
  8. Scikit-Learn Clustering. URL
  9. Scikit-Learn Documentation – K-Means. URL
  10. Matplotlib 3D. URL
Anúncios