Entendendo k-Means, agrupando dados e tirando camisas

16 min readJul 30, 2018

Tem hora que você olha pros seus dados, ali, na sua frente e você tem certeza que tem alguns grupos ali escondidos que poderiam ser interessantes pra você explorar, mas você não sabe muito bem qual a maneira certa de identifica-los, não é mesmo? Hoje vamos ver um algoritmo simples AND eficaz para de descobrir automaticamente agrupamentos em uma base de dados. É extremamente intuitivo, eu prometo que você vai entender e aplicar no que você quiser! E como bônus, vamos aprender a tirar a camisa do Maurílio apenas com a força da matemática!

Somente para dar uma ideia, lembro de ter usado o algoritmo que veremos hoje algumas vezes para assuntos bem distintos:

Agrupar produtos com base em margem, velocidade de venda e custo
Segmentar regiões dentro de fotos com base nos valores dos pixels (foi parte da minha tese de mestrado)
Agrupar usuário de um aplicativo com base em uma porrada de métricas coletadas pela empresa (aqui a dificuldade era quais métricas realmente importavam — mas isso é outra história)

Mas ai fica a seu critério, você que é um cara muito bizness vai encontrar algum uso dentro da sua empresa

Poucas coisas são mais bizness que Supla usando um terno dourado num almoço de negócios com um parça falando em um Nokia old school.

Exemplo rápido pra entender pra que serve

Quando apresentei esse texto para minha editora, ele começava explicando o conceito e a matemática, que eu sinceramente acho a parte mais bonita. Ela disse que estava um pouco denso demais, que era possível que as pessoas desistissem antes mesmo de entender pra que servia tudo isso. Eu compreendo o ponto dela e resolvi então começar com um exemplo simples, com uma base de dados aberta disponível na internê mesmo. Me falem se assim é legal ou se preferiam primeiro entender a teoria e depois ver o exemplo! Enfim, se você seguiu todas as orientações do último texto e tem um jupyter notebook funcionando por ai, é a hora de abrir ele, começar um notebook novo e vamos lá!

Se você copiar e colar o código acima em um notebook novo e der um run, você deve ver as primeiras linhas da base de dados que usaremos neste exemplo. Estes dados foram extraído do servidor de datasets do Center for Machine Learning and Intelligent Systems da Universidade da UCI. Eles disponibilizam um monte de datasets para diversas situações, é uma fonte boa para experimentos. Neste caso, os dados são de gastos anuais em USD de clientes de um atacadista em 5 categorias de produtos. A base também continha informação de canal e região, mas excluí pois não serão úteis para nosso estudo.

Mais detalhes sobre estes dados no site da UCI

Repare também que ja importei algumas bibliotecas que serão uteis para as análises que faremos (pandas, numpy, etc… .

Se voce dar um data.describe(), vai ter um pequeno resumo dos dados:

Como podemos ver, temos 440 observações (o que é bem pouco mas serve para o exemplo), os dados tem um desvio padrão consideravelmente alto (a linha std, de standard deviation, olhando ela junto com a média dá pra ter uma idéia se é alto ou baixo). Isso quer dizer que os dados tem uma variedade muito grande, então se quisermos por exemplo fazer alguma campanha de marketing com base nesses dados crus, ela não será tão focada pois é um grupo com perfis de gasto muito diferentes. Seria melhor se tivéssemos grupos menores com clientes com gastos mais parecidos para a campanha ser mais efetiva, certo? Vamos tentar então agrupar esses clientes automaticamente em clusters homogêneos:

Em termos gerais, este código esta agrupando os dados em 5 clusters, numerados de 0 a 4. Mais abaixo vamos destrinchar tudo o que está acontece e todas as opções, mas por enquanto vamos olhar o resultado. Os clusters criados tem a seguinte distribuição de gastos:

*Pronto, 5 grupos de clientes, segmentados de acordo com tipo de gasto*

Como podemos ver aqui temos dados muito mais claros:

cluster 0, me parece ser os clientes que gastam pouco, distribuído ali entre todos os produtos
cluster 1 também não gasta tanto, porem os gastos são focados em groceries
cluster 2 já são os clientes que tem um dispêndio maior e são bem focados em alimentos frescos
cluster 3 também são os clientes focados em alimentos frescos, porem com um gasto total menor
cluster 4 são os clientes que gastam mais, porém focados em groceries

Então basicamente, o que o algoritmo fez de maneira automática e sem eu ter que dar nenhuma instrução explícita, foi identificar clientes com comportamentos similares, aparentemente baseado em dispêndio total e foco em produtos frescos ou groceries. Desta maneira, se quisermos fazer uma ação especial com os clientes que gastam mais em alimentos frescos, sabemos exatamente quem eles são. Ou se quisermos tentar incentivar aumentar o ticket médio, também sabemos quem são os que gastam pouco e no que eles gastam para direcionar o esforço. Legal né?

Vamos ver como funciona?

Intuição

Os dados que utilizam acima tem 6 dimensões (gastos com fresh, groceries, delicatessen, etc). Vamos começar com algo mais simples, com duas dimensões para que possamos visualizar o que esta acontecendo. Então imagine que você tem os dados abaixo (que eu criei com números aleatórios então não significam NADA, servem apenas para o exemplo):

Eu sei que vai soar idiota, mas é pra entender a intuição desse método, confia em mim. Imagine que tenhamos dois grupos nesses dados… você consegue identifica-los???

Perfeito, agora vamos tentar entender como possivelmente seu cérebro tomou essa brilhante decisão. Um caminho possível é que, sem nem você perceber, o que o seu cérebro fez foi:

Então sua decisão instantânea neste cenário teve na verdade alguns passos:

Um pre-conhecimento de que existem 2 grupos
Um chute inicial
Um refinamento baseado em distancia

Beleza, esse foi um exemplo simples que você batia o olho e resolvia. Mas e agora se ao invés de só duas dimensões, voce tivesse 6 como no nosso exemplo? Voce não conseguiria “enxergar” em um scatter plot, o número de agrupamentos não seria tão claro, você precisaria de um método para resolver. E aí??

k-Means

O algoritmo mais comum de clusterizacao é sem sombra de duvida o k-means, que segue a intuição que vimos logo acima. Vamos tentar formalizar isso em passos:

Assumindo que você queira achar k clusters nos seus dados. Seus dados tem seja la quantas dimensões (ou variáveis, ou features, como costumamos chamar) você quiser, e que você não faz a menor idéia de onde os agrupamentos estão, ou seja, não sabe onde dar o chute inicial. Apenas para que a gente consiga visualizar o que esta acontecendo em cada iteração, vamos dizer que queremos 3 clusters e nossos dados tem 2 dimensões (ou variáveis, ou features), mas os passos e os cálculos são EXATAMENTE OS MESMOS pra quantos clusters e quantas dimensões você quiser.

Essa é nossa situação inicial:

Inicie com um chute aleatório de onde estão os centros dos clusters. Neste exemplo, crie 3 pontos aleatórios (um para cada cluster).
Aloque cada ponto da sua base de dados ao centro mais próximo (um destes 3 centros que você acabou de criar). Este é seu chute inicial de alocação dos dados em k cluster (nesse caso 3).

Chute inicial de centros, alocação inicial dos pontos e re-cálculo dos centros

Agora que cada ponto da sua base de dados foi alocado a um cluster, calcule a média real (mean — sacou de onde vem o nome?) de cada um dos clusters. Este é o novo centro de cada cluster.
Como você tem um novo centro, re-aloque seus pontos com base nesse novo centro calculado. Alguns podem e devem ter mudado de alocação.

Re calculando centros e re alocando pontos

Já que alguns mudaram, você precisa re-calcular os centros de novo, não é mesmo?
Já que o centro mudou, re-aloque os pontos… você entendeu onde isso vai dar né…

re calculando centros e re alocando pontos de novo

Enfim, você repete esse ciclo até atingir uma solução estável e pronto, dados segmentados.

Um pouquinho de teoria

Eu sei, nem todo mundo gosta, mas eu preciso fazer isso pra ser levado a sério…

K-Means é um algoritmo do tipo que se convencionou chamar de unsupervised learning, o que basicamente quer dizer que você só precisa dos dados, não precisa ter um conhecimento prévio de a que classe cada observação pertence (como veremos quando falarmos sobre classificação). A idéia dele é agrupar n observações em k clusters através da minimização do momento de inércia de cada cluster. O que isso quer dizer? Quer dizer que: ele tem por objetivo encontrar uma alocação dos dados em clusters de maneira que, dentro de cada cluster, os dados estejam o mais próximos possível, assumindo que quanto mais próximos eles estiverem, mais parecidos eles são. E literalmente próximos, uma vez que o momento de inércia para os dados em questão é calculado como a soma do quadrado das distâncias de cada ponto ao centro do agrupamento. Mais claro? Vamos tentar escrever isso em matematiques? Eu também estou um pouco enferrujado, mas vamos tentar:

Imagine que:

Voce tem uma base de dados com um total de n dados, X = {x1, x2, …, xn } cada ponto x com quantas dimensões você quiser.
Voce quer agrupa-los em k clusters, C = {C1, C2, …, Ck }
A inércia de um cluster Ci pode ser calculada por:

*Calma Nazare, vamos entender o que ta escrito ai…*

i é o índice do cluster que você esta analisando, e µi portanto é a média do cluster i, que é também o centro do cluster i. ‖x-µi‖ é a distancia de um ponto x ao centro do cluster i. ∑ significa soma, e x∈Ci quer dizer para os x que pertencem ao cluster Ci. Ou seja, lendo tudo junto: para os pontos x que estão no cluster Ci, some o quadrado das distâncias de cada ponto até o centro desse cluster. E agora você já pode meter no curriculo que fala matematiques.

Esse calculo que fizemos é para UM cluster (o cluster Ci), mas temos k clusters, né? Então temos que somar isso para todos os k clusters. Sendo assim, a inércia total é:

Ou seja — como ja aprendemos — Soma da inércia de cada cluster Ci com i indo de 1 até k!

O objetivo deste algoritmo é minimizar essa inércia total!

Pronto, chega de teoria.

Principais críticas:

Tem uma frase famosa na cena estatística: “Todos os modelos estão errados, mas alguns são uteis” — Lispector, Clarice. Brinks, é na verdade de um cara chamado George Box. Os modelos partem de algumas premissas que podem ou não fazer sentido para a situação que você esta tentando modelar, ou tem alguns passos que merecem algum cuidado especial. k-means não foge disso.

1) Ele é extremamente sensível ao chute inicial dos clusters. Por exemplo, se ao invés do chute inicial que demos, tivéssemos dado esse aqui abaixo, o resultado seria bem diferente:

Isso acontece porque o k-means encontra o que é chamado um mínimo local. Lembra que a gente esta tentando minimizar a inércia total? Então, existe um mínimo real chamado de mínimo global, mas ele é difícil de achar… e o k-means (e muitos outros algoritmos) se contenta com o mínimo local. Mas e aí??? Então, pra solucionar esse problema, roda-se o algoritmo pelo menos 10 vezes e se escolhe a melhor solução, ou seja, a que tem o mínimo mais mínimo! Outra sacada é começar o algoritmo com um chute inicial não tãããão chutado assim: existe um tipo de inicialização chamado kmeans++ que evita que se escolham pontos muito próximos uns aos outros como chute inicial. Por isso que, lá no começo quando fizemos o código de exemplo no jupyter notebook, tínhamos n_init=10 e init=“k-means++”! Isso explicita que devemos rodar o algoritmo 10 vezes e cada vez deve ser iniciada da maneira conhecida como k-means++.

2) Você precisa saber de antemão o número k de clusters nos dados. Verdade, espera-se que você diga em quantos agrupamentos você quer que os dados sejam segmentados. Porém existem maneiras para você inferir (um nome elegante para chutar) quantos clusters os dados tem. A maneira mais fácil e direta é a chamada “método do cotovelo” (elbow method). Funciona mais ou menos assim:

Começa com k=1, calcula a inércia total da melhor solução, plota esse ponto em um gráfico número de clusters x “inércia total”
Passa pra k=2, calcula inércia total, põe no gráfico
k=3… e por ai vai.
Você vai ver que a inércia vai reduzir rapidamente e em determinado número de clusters k, adicionar um novo cluster não vai fazer tanta diferença, e vai ser formar um cotovelo no gráfico. Tá aí o k! Por exemplo, para os dados aleatórios que criei no exemplo acima, este é o gráfico de ganho marginal ao se adicionar um cluster:

Redução da inércia com aumento do número de clusters

Como da pra ver, a inércia cai um absurdo quando usamos 2 clusters, ainda cai um tanto bom quando consideramos 3, ai depois disso não é aquela coisa… então provavelmente 3 é um número bom pra começar. Mas ai você me pergunta: Mas Paulo… se ainda tá diminuindo não é melhor usar o maior número possível?. Pergunta honesta. A verdade é que a inércia sempre vai diminuir conforme aumentamos o número de clusters, ja que os agrupamentos ficam “mais compactos” (também conhecido como menores), com pontos mais próximos e portanto com uma inércia menor. Ai é a hora que você tem que interpretar o resultado junto com o seu conhecimento do que você esta tentando modelar pra escolher algo que faça sentido. De que adianta ter 90 clusters com duas observações em cada um? Sacou?

3) Ele assume que os clusters são “esféricos”. Isso é verdade, e uma consequência do momento de inércia usar a distância euclidiana (o famoso √(a2 + b2))… é como diz a frase… pode não estar certo, mas pode ser útil… é tentar e ver se da certo pra você!

4) Os valores das diferentes variáveis usadas tem que estar em ordens de grandeza similares. Verdade, senão uma das variáveis vai dominar a analise, mas isso quase qualquer método também… é uma questão de normalizar ou não os dados antes de começar.

5) O método segmenta em clusters mas não fala o que cada cluster é. Verdade, você tem que dar uma olhada nos dados de cada cluster e interpretar o que tem lá, mas a vida é assim mesmo!

Na vida real

Naturalmente a gente não tem que fazer todas essas contas toda a vez que for fazer um k-meanszinho maroto, já existem bibliotecas prontas pra isso. No caso, vamos usar a implementação do scikit-learn, também conhecido na noite como sklearn. Se você é sagaz e já está com aquele jupyter notebook rodando o exemplo do começo do texto, vamos agora comentá-lo passo a passo.

Eu comecei importando as bibliotecas e lendo os dados como já comentei, certo? Aí o próximo passo natural é escolher o valor de k, número de clusters. Muitas vezes você já vai saber em quantos grupos quer segmentar, mas caso não saiba, pode usar o código abaixo para geral o gráfico que usamos na regra do cotovelo:

inertia = []
for i in range(1,11):
    kmeans = KMeans(n_clusters=i, random_state=1234)
    kmeans.fit(data)
    inertia.append((i,kmeans.inertia_,))

O que está acontecendo aqui:

Criamos uma lista vazia chamada inertia
para i de 1 a 10
Calculamos um k-means maroto com k = i
adicionamos na lista o par (i, inercia)

Repare que o k-means do sklearn funciona da seguinte maneira: você começa iniciando ele (kmeans = KMeans(...)) e depois você aplica ele aos dados (kmeans.fit(dados). Quando fazemos isso, ele realiza todos as contas, e ai podemos acessar alguns resultados, como kmeans.interta_ para conferirmos o momento de inércia total que foi calculado. Mais sobre essa implementação aqui.

Ai, com a lista montada, da pra fazer o gráfico com o código abaixo:

plt.plot([w[0] for w in inertia],[w[1] for w in inertia], marker="X")

Aqui, [w[0] for w in inertia] é a lista do elemento 0 de cada dupla dentro da nossa lista inertia, ou seja [1, 2, 3... 10]. Usando w[1] ao invés de w[0] você tem a lista com os valores das inércias. Ai o pot.plot faz o gráfico x e y respectivamente deles:

Olhando o gráfico, inferi que k=5 seria um bom palpite. Ai fui lá e formalizei meu k-means da seguinte maneira:

kmeans = KMeans(n_clusters=5, init='k-means++', n_init=10, random_state=1234)
kmeans.fit(data)
cluster_list = kmeans.labels_

Aqui temos:

kmeans com as seguintes opções:
5 clusters, conforme inferimos anteriormente
inicialização do tipo k-means++, que como já comentamos é uma maneira de se espaçar o chute aleatório inicial de uma maneira a evitar uma convergência para uma solução ruim, diminuindo o impacto do chute inicial
Vamos rodar o algoritmo 10 vezes usar a opção que melhor minimize o momento de inércia. Isso é feito automaticamente quanto se usa o n_init. Assim se diminui o impacto do chute inicial e o fato da otimização cair em um mínimo local. Vai ser o mínimo mais mínimo que encontrarmos.
random_state é uma maneira de me certificar que, quem usar o valor que coloquei aí, vai usar o mesmo gerador de números aleatórios que eu. é uma pratica comum para que os resultados sejam reproduzíveis.
kmeans.fit(data) já conhecemos, aplica o algoritmo aos nossos dados
kmeans.labels_, após o algoritmo ter sido aplicado aos dados, é a lista com o índice de a que clusters (de 0 a 4) cada observação pertence.
Pronto, é isso. Para os nerds que estão lendo a documentação do sklearn ou já conhecem a função, eu sei, eu podia ter usado o .fit_predict ao invés do .fit, mas achei que assim ficava mais claro.

Agora vamos conferir se o resultado faz sentido? Para isso o que vou fazer é:

Adicionar a coluna cluster ao dataframe de dados que já tínhamos.
Calcular a média dos dados por cluster e plotar no formato de gráfico barras

data["clusters"] = cluster_list
data.groupby("clusters").aggregate("mean").plot.bar()

E com isso chegamos ao nosso resultado, como ja explicamos antes. Se a empresa quiser investir em uma campanha focada nos clientes que compram produtos frescos, são os clientes do cluster 2.

*Imprime, põe na mesa do chefe e explica tudo isso com muita confiança, pede aumento*

Bonus track

Agora, pra descontrair, vamos ver um uso alternativo: segmentação de imagens. Acho que hoje em dia todo mundo sabe que uma imagem é um conjunto de pixels, certo? Vamos tentar aplicar o k-means a pixels.

Matematicamente um pixel é um ponto tridimensional, uma dimensão é a intensidade de vermelho, outra a intensidade de verde e a ultima a intensidade de azul (assumindo que você esta trabalhando no espaço conhecido como RGB). Uma foto é portanto uma coleção de pontos tridimensionais, da mesma maneira que no exemplo anterior cada cliente era um ponto em um espaço de hexadimensional (tínhamos 6 dimensões, lembra?).

Então esta belíssima imagem do nosso amigo Palestrinha pode ser representada por um conjunto de 160000 pixels, já que neste caso a imagem tem 400 x 400 pixels (na imagem abaixo os 4 primeiros pixels):

Abraço para todos os entusiastas do audiovisual

Vamos fazer exatamente a mesma coisa, ok? Primeiro calcular a diminuição da inércia ao aumentarmos o numero de clusters (para escolhermos o valor de k):

Pra mim k=3 soa honesto. Aí de maneira semelhante aplicamos o k-means à tabela de pixels usando este valor de k e temos como resultado o cluster a que cada pixel pertence. Vamos visualizar o resultado?

Não é maneiro?? Agora imagine que você quer isolar apenas a bela camisa do palestrinha. É o cluster 1. Vamos filtrar na nossa foto original apenas os pixels que pertencem ao cluster 1:

Isolando assim, a gente pode pegar a cor principal, o formato, procurar por camisas similares no nosso banco de dados e por aí vai. Ou simplesmente plotar tudo menos o cluster 1, tirando assim a camisa do nosso amigo:

Algumas observações:

Repare no mapa dos clusters que o fundo da imagem eh um pouco “sujo”. Isso acontece porque essa (e muitas outras fotos na internê) são jpg comprimidos com algoritmos que prezam mais velocidade que qualidade, e muitas vezes isso gera o que chamamos de artefatos de compressão, que são muitas vezes imperceptíveis para nossos olhos, mas estão la nos números
Se você olhar no código vai ver que eu estou transformando de RGB para HSV, que é uma outra forma tridimensional de representar as cores . Não queria me estender muito sobre isso hoje, mas o ponto é: dependendo do que você quer fazer, RGB nem sempre é a melhor maneira de representar cores. Talvez um dia escreva um texto só sobre isso se alguém tiver interesse!

Conclusão

Foi longo, eu sei, mas não foi tão difícil assim, vai… Tudo faz sentido se você parar pra pensar direitinho.

Pra quem quiser o código inteiro, vou disponibilizar os notebooks no link abaixo, com mais alguns comentários.

pauloesampaio/kmeans

kmeans - Alguns exemplos de k-means

github.com

Como sempre, qualquer dúvida vamos conversando!! Semana que vem falamos de algoritmos de classificação, na minha opinião o que tem de mais útil por aí e base para coisas mais complexas tipo neural networks!

Abraços!