Tá aí um algoritmo muito falado na área de ciência de dados e, apesar de estar na 'boca do povo' há uns 5 anos, seus princípios são bem mais velhos do que isso. O K-Means é um algoritmo de aprendizagem não supervisionada. Ele não classifica, mas agrupa vetores de atributos similares, isto é, coloca em um mesmo agrupamento vetores similares, e por este ser computacionalmente simples e funcionar bem na prática, ele é um dos principais e mais usados métodos de agrupamento (DUDA; HART, 1973). Só no Google Acadêmico com a pesquisa "K-means" há mais de 8 mil artigos publicados. São artigos com aplicação em diversas áreas e claro que muitos são artigos 'palpiteros' que indicam algum tipo de alteração no desenrolar do algoritmo.
E eu com isso?
É importante tem em mente que algoritmos passam por alterações de melhoria e você como profissional de dados tem que ficar de olho e se atualizar. Uma forma de se atualizar é acompanhar artigos e blogs voltados a área de interesse.
Isso quer dizer que o básico serve pra nada?
Calma! Não é bem assim. O básico te fornece a base e entendimento do que acontece no algoritmo e isso é MUITO relevante.
Tá, e o que é o Algoritmo K-Means?
Este algoritmo é uma técnica iterativa muito simples e poderosa para particionar um conjunto de dados em grupos separados, onde o valor de K, deve ser pré-determinado e a distância utilizada para a similaridade (É uma medida numérica do quão parecido dois objetos são) é a distância Euclidiana (defalt).
Ele é mais conhecido como uma técnica não supervisionada de dados. Isso significa que o algoritmo irá receber dados sem atributos pré determinados. Então quer dizer que pego os dados e jogo lá? Não exatamente. Como foi dito acima o K-Means atua em sua essência com matriz de distâncias com o intuito de comparar o quão longe um ponto na reta está de outro.
Aí lascou né?
Lascou um pouquinho, mas não precisa se assustar. Há diversos tipos de distâncias e cada uma possui sua pitadinha de aventura no algoritmo K-Means.
A Distância Euclidiana é definida como a soma da raiz quadrada da diferença entre x e y em suas respectivas dimensões e que por defalt é utilizada no algoritmo. Posso trocar a distância? Claro! Vou lhe ensinar logo mais (Peraê!), mas vamos focar um parágrafo na distância Euclidiana.
Considere o banco de dados fictício abaixo.
library(tidyverse)
#(0 = Não, 1 = Sim)
banco_vacina <- tibble::tribble(
~covid, ~gripe,
1L, 0L,
1L, 0L,
0L, 1L,
0L, 0L
)Vamos calcular a distância euclidiana entre vacinou contra covid e vacinou contra gripe?
Para isso vamos utilizar a função dist() do pacote stats. A matriz de distância se encontra abaixo.
> dist(banco_vacina, method = "euclidean")
1 2 3
2 0.000000
3 1.414214 1.414214
4 1.414214 1.414214 0.000000
O que você consegue assimilar diante dessa matriz de distância?
A primeira dúvida que eu espero que você tenha é: A distância Euclidiana é adequada para dados categóricos? Se você não se fez essa pergunta fico feliz de ter colocado uma pulguinha atrás de sua orelha quando o assunto é matriz de distâncias em algoritmos de classificação/agrupamento.
E já que a pulguinha está aí atenta é importante lhe dizer que há vários tipos de distâncias. Algumas são voltadas a determinadas classes de dados e outras possuem um bom desempenho com diversas classes de dados simultaneamente. As mais comuns são:
E como bom profissional cabe a você identificar a distância que melhor se adequa aos dados do seu problema.
Contratempo: Imagina um banco de dados com 100 mil linhas. A matriz de distância calculada vai ter qual dimensão?
Mas sempre preciso de uma matriz de distância como entrada de dados?
Não necessariamente. No pacote stats temos a função kmeans() que te proporciona a possibilidade da entrada de dados ser uma matriz numérica de dados.
kmeans(x, centers, iter.max = 10, nstart = 1,
algorithm = c("Hartigan-Wong", "Lloyd", "Forgy",
"MacQueen"), trace=FALSE)
## S3 method for class 'kmeans'
fitted(object, method = c("centers", "classes"), ...)Mas você acabou de dizer que como defalt o K-Means utiliza a distância Euclidiana, como trocar?
Quando iniciei os estudos sobre o algoritmo K-Means em 2017 essa foi a minha primeira pergunta já que meus dados eram séries temporais e a distância Euclidiana com TODA certeza não se adequava ao problema. A questão é que com essa possibilidade de tipos de entrada de dados você pode calcular anteriormente a matriz de distância com a distância de interesse e colocá-la como entrada de dados na função kmeans(). Esse é o pulo do gato. Claro que nem todas funções funcionam dessa forma e, por isso, é importante dar uma espiada na documentação da função que você está utilizando.
E já que você está sacando de matriz de distância, uma outra pergunta que muitos se fazem é:
Como mensurar o K que você mencionou lá no início?
Este é outro assunto MUITO citado no universo de dados e talvez pouco discutido em seus pormenores. O 'K' é o número de centros ou número de clusters e há diversos métodos na literatura que são utilizados para este fim. Alguns dos mais aplicados para este são métodos visuais como os dendogramas que utilizam de diversas técnicas de agrupamento, o método da silhoutte e o método elbow (cotovelo). Vou focar somente no métodos elbow já que os dendogramas são resultado de uma outra análise de aprendizagem não supervisionada chamada análise de cluster hierárquica e o silhoutte vou abordar em outro post em breve.
Então vamos lá...
Qual o nosso objetivo ao realizar uma análise com o algoritmo K-Means?
Nossa objetivo é agrupar objetos semelhantes entre si e consequentemente desagrupá-los de objetos distintos.
E como isso funciona?
Vamos voltar alguns passos...
Em alguns casos, duas variáveis se relacionam de uma maneira determinística, o que significa que dado um valor de uma variável, o valor da outra variável será automaticamente determinado sem qualquer erro. Este cenário não é o que estamos procurando e sabemos que no mundo real não é o que encontramos. O nosso interesse aqui é identificar quando uma variável não é completamente determinada por outra variável, e para isso utilizamos de modelos probabilísticos.
Um dos modelos mais utilizados é a Regressão, em que a equação da regressão expressa uma relação entre x e y mediados por estatísticas amostrais utilizadas para estimarem os parâmetros de interesse. Neste método muito se fala sobre 'A reta de regressão é a que melhor se ajusta aos dados amostrais'. E como assim ela é a melhor? Este é um dos pontos que eu queria chegar.
Já ouviu falar da propriedade dos mínimos quadrados?
Se não, este é o critério para definição de qual reta se ajusta melhor aos dados amostrais que se baseia nas distâncias verticais entre os pontos dos dados originais e a reta de regressão. Essas distâncias são mais conhecidas como resíduos ou simplesmente pela fala 'observado menos previsto'. Logo, uma reta satisfaz a propriedade dos mínimos quadrados se a soma dos quadrados dos resíduos for menor possível.
E da ANOVA?
A Análise de Variância (ANOVA) é um método para se testar a igualdade de três ou mais médias populacionais através da análise de variâncias amostrais. Ela se baseia na comparação de duas estimativas diferentes da variância comum de duas populações diferentes. Essas duas estimativas são a variância entre amostras e a variância dentro das amostras, ou seja, teremos dois estimadores para a variância populacional.
Agora sim podemos falar sobre Soma de Quadrados e Estatística F.
Veja que o algoritmo K-Means está constantemente aplicando testes de comparação de médias ao longo do algoritmo entre os agrupamentos. A estatística de teste para a ANOVA é a F que é definida pela divisão da variância entre amostras pela variância dentro das amostras. Vou dar uma brevíssima pincelada e esclarecer a estatística F básica logo abaixo.
O Teste F é utilizado para comparação de variâncias amostrais (ou desvios padrões). O nome do teste é sugestivo, mas se você nunca ouviu falar na distribuição F de Fisher-Snedecor agora é o momento de conhecê-la. Ela é uma distribuição assimétrica e que se difere para cada par de graus de liberdade do denominador e numerador. Sua fórmula é dada pela divisão da maior variância amostral pela variância amostral da segunda amostra. Se o tamanho das amostras são diferentes esta fórmula tem outra definição. Dê uma olha na teoria de Inferência Estatística para entender um pouquinho mais sobre Testes de Hipóteses voltados a variância.
E como essa ANOVA funciona?
A ANOVA é baseada em Soma de Quadrados (SQ). Você encontra pela internet um resumão dela como na figura abaixo.
São três SQ's:
Soma de Quadrados Total: É a medida de variância total em torno da média geral de todos os valores amostrais combinados.
Soma de Quadrados dos Resíduos/Erro/Dentro do Grupo/ Dentro das Amostras: É uma soma que quadrados que representa a variação que se supõe comum a todas as populações em consideração.
Soma de Quadrados do Tratamento/Entre Grupos/Entre Amostras: É uma medida de variação entre as médias amostrais. Se as médias populacionais não são iguais, então pelo menos uma das médias amostrais tende a se localizar bem afastada das demais e também afastada da média geral.
Afinal, o que o método Elbow faz?
O método Elbow minimiza a variabilidade dentro do cluster, ou seja, o algoritmo faz automaticamente a soma de quadrados de resíduos ou dentro do cluster variando por K e assim lhe retorna a visualização análoga à figura abaixo.
Precisava disso tudo pra me falar isso aí Fernanda? Sim! É importante você ter ideia do que acontece por trás de algoritmos. E tem mais...
É sério?
Sim! E na real tem muito mais.
Você já pensou em como quantificar a qualidade do ajuste do seu modelo?
Lá vem a Soma de Quadrados de novo. Vamos utilizar o banco de dados abaixo. Copia e colo em seu RStudio.
library(tidyverse)
banco_vacina <- tibble::tribble(
~covid, ~gripe,
1.5, 2.5,
10, 8.3,
5.6, 7.1,
8.7, 7.6
)Aplicando o algoritmo K-Means.
modelo <- stats::kmeans(x = banco_vacina,
centers = 2,
iter.max = 10,
nstart = 1)A saída do algoritmo se encontra abaixo.
> modelo
K-means clustering with 2 clusters of sizes 3, 1
Cluster means:
covid gripe
1 8.1 7.666667
2 1.5 2.500000
Clustering vector:
[1] 2 1 1 1
Within cluster sum of squares by cluster:
[1] 10.94667 0.00000
(between_SS / total_SS = 82.8 %)
Available components:
[1] "cluster" "centers" "totss" "withinss" "tot.withinss"
[6] "betweenss" "size" "iter" "ifault"
Veja que na saída do algoritmo nós temos oito componentes e alguns deles são os SQ's. O nosso interesse é que entre os clusters haja uma grande diferença e intra grupo queremos o contrário.
> modelo$betweenss
[1] 52.69083
> modelo$tot.withinss
[1] 10.94667
> modelo$withinss
[1] 10.94667 0.00000
> modelo$totss
[1] 63.6375Note que entre grupos temos 0.8279 e intra grupos temos 0.1720. É bom? Depende do problema de negócio e o que a análise descritiva de cada cluster tem de história e interpretação.
Contratempo 2: Encontramos vários gráficos de interpretação para essa etapa do algoritmo pela internet, mas já pensou plotar 10000000000 pontos para essa etapa?
Ainda há muito para se falar sobre este algoritmo tão utilizado. Omiti muitos devaneios e ligações com métodos estatísticos. Não expliquei o impacto da alteração dos parâmetros iter.max e nstart. Não expliquei o parâmetro algorithm. Mas apesar de tantos 'buracos' e falhas, espero que você tenha se alertado sobre os parâmetros existentes e as diversas formas de estimação de cada um deles.
Fernanda Kelly R. Silva | Estatística
Comments