O k-means é um algoritmo de agrupamento (ou clustering) não supervisionado, amplamente utilizado para dividir um conjunto de dados em grupos (ou clusters) com base na similaridade dos dados. Ao contrário dos classificadores supervisionados, como o KNN, o k-means não requer dados rotulados. Ele simplesmente agrupa os dados em clusters distintos por um critério de distância.
Funcionamento Básico
O algoritmo do k-means é bastante simples e envolve um total de 5 passos básicos: definir a priori o número de cluster de conjunto de dados, dar uma estimativa inicial para os centroides dos clusters, classificar os dados em relação aos centroides mais próximos, atualizar a posição dos centroides e repetir esse processo de atualização até que a posição dos centroides não mude de forma significativa. Estes passos de execução do k-means estão descritos como mais detalhes logo abaixo:
- Definir o número de clusters $k$: O k-means precisa de um valor a priori do número $k$ de clusters que se deseja encontrar em um conjunto de dados de entrada. Existem várias abordagens diferentes para determinar o valor de $k$ mais apropriado.
- Inicializar os centroides $m_i^{(0)}$: Depois de determinado o número $k$ de clusters, é necessário escolher $k$ pontos no espaço de características dos dados de entrada (dados que serão agrupados) para serem os centroides iniciais (ou centros). Existem várias estratégias para inicializar esses centroides, sendo a escolha aleatória a mais comum. Neste caso, a aleatoriedade é restrita a escolher instâncias dos dados que serão agrupados. Ou seja, $k$ instâncias do conjunto de dados de entrada são escolhidas aleatoriamente para se tornarem os $k$ centroides iniciais $m_i^{(0)}$. Escolher centroides de uma forma completamente aleatória, sem considerar o conjunto de dados de entrada, normalmente não produz bons resultados.
- Atribuir as instâncias aos clusters (ou associação das categorias): Cada instância(ou ponto) $x_p$ do conjunto de dados de entrada é atribuído ao centroide mais próximo $m_i^{(t)}$ no instante $t$ segundo uma métrica de distância. Assim, são formandos $k$ conjuntos de instâncias $S_i^{(t)}$ em cada interação do algoritmo. A métrica de proximidade mais comumente usada é a distância Euclidiana. Matematicamente a associação das instâncias $x_p$ aos centros $m_i$ em conjuntos $S_i^{t}$ pode ser expressa como:
- $S_i^{(t)}=\{ x_p : { \| x_p – m_i^{(t)} \| }^2 \leq { \| x_p – m_j^{(t)} \| }^2 \quad \forall j , 1 \leq j \leq k \}$
- Atualizar os centroides (ou calculo dos centros): Após formar os $k$ conjunto $S_i^{(t)}$, um novo centroide $m_i^{(t+1)}$ é calculado como a média de todos os pontos $x_j$ pertencentes a esse conjunto. Matematicamente, a atualização dos centroides pode ser expressa como:
- $m_i^{(t+1)}=\frac{1}{|S_i^{(t)}|} \sum\limits_{x_j \in S_i^{(t)}} x_j$
- Repetir passos 3 e 4 até convergir: Os dois passos anteriores (itens 3 e 4) são repetidos até que os centroides $m_i^{(t)}$ não mudem mais de posição ou até que um critério de convergência seja atendido (por exemplo, um número máximo de iterações ou quando a mudança nos centroides for insignificante).
O objetivo do k-means é particionar um conjunto de dados de entrada em grupos de instâncias que estão próximas entre si. Entretanto, o resultado final dos agrupamentos depende da determinação de $k$ e da posição inicial dos centroides $m_i^{(0)}$. A comparação da “qualidade” de dois tipos de agrupamentos diferentes pode ser realizada através da soma das distâncias quadráticas dos pontos ao centroide mais próximo, ou seja:
\[
J = \sum_{i=1}^{k} \sum \limits_{x \in S_i} | x – m_i |^2
\]
Onde $S_i$ é o $i$-ésimo conjunto de instâncias associado ao centroide $m_i$ do cluster $i$, e $x$ são as instâncias/pontos pertencentes ao conjunto $S_i$. $J$ é o “custo” do agrupamento. Normalmente, quanto menor o $J$, melhor. Entretanto, há de se ponderar o número máximo de clusters que se deseja ou pode ser obtido. Por exemplo, se o número de clusters $k$ for igual ao número de instâncias e a inicialização dos centroides for feita em relação a estas instâncias, $J$ será, garantidamente, zero. E isso não quer dizer que o agrupamento foi “bem feito”. Ou seja, calcular a soma das distâncias quadráticas dá informações se o número de clusters $k$ pode ser aumentado ou diminuído e se sua inicialização foi boa ou ruim, mas isso não é suficiente por si só para determinar um valor exato para $k$ e $m_i^{(0)}$.
Parâmetros Importantes
- Número de clusters $k$: É o parâmetro mais crucial. O número de clusters deve ser definido previamente. Existem várias abordagens para isso, como: o método do cotovelo (Elbow, analisando a variação intra-cluster conforme $k$ aumenta) ou o índice de silhueta (Silhouette, avaliando a separação dos clusters). Entretanto, muitas vezes, quando se deseja reduzir o número de instâncias, o número de clusters pode ser definido arbitrariamente como um percentual do total de instância do conjunto de dados de entrada.
- Inicialização dos centroides: A maneira como os centroides são inicialmente escolhidos pode afetar o resultado final. A abordagem mais comum é sortear aleatoriamente amostras do conjunto de dados de entrada para serem utilizadas como centroides iniciais. Este procedimento garante que na primeira interação do algoritmo k-means todos os centroides terão pelo menos uma amostra associada.
- Critério de convergência: Define quando o algoritmo deve parar. Normalmente, ele para quando os centroides não mudam mais de valores após duas interações consecutivas ou quando atinge um número máximo de iterações.
Vantagens
- Simples e rápido: O k-means é fácil de implementar e pode ser computacionalmente eficiente em conjuntos de dados moderadamente grandes.
- Interpretabilidade: O resultado dos clusters é intuitivo e fácil de visualizar, especialmente em problemas bidimensionais ou tridimensionais.
Desvantagens
- Número de clusters: O $k$ precisa ser definido antes da execução e obter a melhor escolha pode não ser trivial.
- Sensível a outliers: O k-means pode ser distorcido por outliers ou dados muito distantes, que podem influenciar significativamente os centroides.
- Forma dos clusters: O algoritmo assume que os clusters são aproximadamente esféricos e de tamanho semelhante, o que pode ser problemático para conjuntos de dados que formam clusters de formas ou tamanhos diferentes.
- Dependência da inicialização: Uma má escolha dos centroides iniciais pode levar a agrupamentos não muito uniformes.
Aplicações
O k-means é amplamente utilizado em várias áreas, como:
- Segmentação de clientes: Em marketing, para agrupar clientes com comportamentos de compra semelhantes.
- Compressão de imagens: Para reduzir a quantidade de cores em uma imagem.
- Redução de instâncias de treinamento: Uma das aplicações mais comuns do k-means é servir como pré-processamento para reduzir instâncias/amostras em conjuntos de treinamento de algoritmos supervisionados. O k-means pode reduzir sensivelmente a quantidade de dados necessária para treinar um sistema supervisionado simplesmente agrupando instâncias/amostras redundantes e possivelmente repetidas.
Codificação
Abaixo segue uma codificação do algoritmo de k-means implementado em Scilab script.
//Exemplo de código ilustrativo de categorizador k-means
//www.drgomes.pro
//Distância euclidiana^2 considerando c e x vetores linha ou coluna
function r=dist2(c,x)
r=x-c
r=sum(r.*r)
endfunction;
//X -> Matriz vetor linha de instancias
//Mc -> Matriz vetor linha com os centroides iniciais
//nmax -> Número máximo de interações
//S1 -> Lista com os agrupamentos das instâncias
//O valor de K é determinado pelo número
//de centroides(linha) em Mc
function [Mc,S1,n]=kmeans(X,Mc,nmax)
[k,Nc]=size(Mc);
[M,Np]=size(X);
//Verifica se as dimenções dos
//centroides são iguais as das instâncias
if Nc<>Np then
printf("Os vetores dos centroides precisam ter a mesma dimensão das instâncias\n")
return
end
//Cria uma memória S para armazenar
//as instâncias associada a cada centroide
S1=zeros(M,1)
S0=S1
for n=1:nmax,
//Limpa a memória de associação das instâncias aos controides
for i=1:M,
S1(i)=0
end
//Associa os pontos aos centros
for p=1:M,
dmin=dist2(Mc(1,:),X(p,:));
cmin=1;
for c=2:k,
d=dist2(Mc(c,:),X(p,:));
if d<dmin then
dmin=d;
cmin=c;
end;
end;
//Armazena o valor do cluster associada a instância x_p
S1(p)=cmin;
end;
if S1==S0 then
return
end
//Recalcula os centros
m=zeros(Mc)
mN=zeros(M,1)
for p=1:M,
m(S1(p),:)=m(S1(p),:)+X(p,:)
mN(S1(p))=mN(S1(p))+1
end
for i=1:k,
if mN(i)==0 then
m(i,:)=Mc(i,:)
else
m(i,:)=m(i,:)/mN(i);
end
end
Mc=m
S0=S1
end;
endfunction;
O código do k-means propriamente dito está entre as linhas 16 e 80 do script acima. Um das diferenças entre a implementação e a teoria, é a utilização de um vetor para armazenar a rotulação do agrupamento de cada instância ao invés de um conjunto. Assim, no código, $S$ é um vetor com o mesmo número de dimensões que o número de instâncias dos dados de entrada. $S$ armazena o número do cluster ao qual cada instância dos dados de entrada esta associada. Exemplo, $S(3)=2$ significa que a instância $x_3$ ( linha 3 da matriz de dados $X$) está associada ao cluster número 2. Outra diferença na codificação é que o $k$ não precisa ser fornecido explicitamente. Ou seja, ao se fornecer a matriz de centroides iniciais $Mc$ o valor de $k$ será o número de vetores centroides (linhas) nessa matriz.
O método dist2 , na linha 5 do script é utilizado apenas para implementar a métrica de distância que será utilizada pelo k-means. No lugar deste código poderíamos ter qualquer outro tipo de métrica de distância.
Exemplo
Abaixo segue um exemplo prático do algoritmo do k-means sendo utilizado para realizar o agrupamento dos dados da Tabela 1. O k-means (e o script apresentado aqui) pode ser utilizado para realizar o agrupamento de milhares de instâncias/pontos, mas aqui, só para fins didáticos, vamos nos limitar a singelas 9 instâncias de duas características (2d).
Tabela 1 ( $X_{9×2}$)
| i | pi1 | pi2 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 4 | 3 |
| 4 | 5 | 3 |
| 5 | 6 | 4 |
| 6 | 1 | 2 |
| 7 | 3 | 4 |
| 8 | 1 | 5 |
| 9 | 2.1 | 3.5 |
O código do k-means anteriormente apresentado segue abaixo atualizado com mais algumas rotinas. O que foi adicionado, basicamente, foram rotinas para plotagem e visualização dos dados e, logicamente, os dados de entrada da Tabela 1 ($X$, linha 92) e os valores iniciais dos centroides ($Mc$, linha 95).
//Exemplo de código ilustrativo de categorizador k-means
//www.drgomes.pro
//rotina para plotar intâncias (vetores linha)
//X -> intâncias (vetores linha)
//arg -> parâmetros para plotagem
function plotPoints(X,arg)
if X<>[] then
plot(X(:,1),X(:,2),arg);
end
endfunction;
//Distância euclidiana^2 considerando c e x vetores linha ou coluna
function r=dist2(c,x)
r=x-c
r=sum(r.*r)
endfunction;
//X -> Matriz vetor linha de instancias
//Mc -> Matriz vetor linha com os centroides iniciais
//nmax -> Número máximo de interações
//S1 -> Lista com os agrupamentos das instâncias
//O valor de K é determinado pelo número
//de centroides(linha) em Mc
function [Mc,S1,n]=kmeans(X,Mc,nmax)
[k,Nc]=size(Mc);
[M,Np]=size(X);
//Verifica se as dimenções dos
//centroides são iguais as das instâncias
if Nc<>Np then
printf("Os vetores dos centroides precisam ter a mesma dimensão das instâncias\n")
return
end
//Cria uma memória S para armazenar
//as instâncias associada a cada centroide
S1=zeros(M,1)
S0=S1
for n=1:nmax,
//Limpa a memória de associação das instâncias aos controides
for i=1:M,
S1(i)=0
end
//Associa os pontos aos centros
for p=1:M,
dmin=dist2(Mc(1,:),X(p,:));
cmin=1;
for c=2:k,
d=dist2(Mc(c,:),X(p,:));
if d<dmin then
dmin=d;
cmin=c;
end;
end;
//Armazena o valor do cluster associada a instância x_p
S1(p)=cmin;
end;
if S1==S0 then
return
end
//Recalcula os centros
m=zeros(Mc)
mN=zeros(M,1)
for p=1:M,
m(S1(p),:)=m(S1(p),:)+X(p,:)
mN(S1(p))=mN(S1(p))+1
end
for i=1:k,
if mN(i)==0 then
m(i,:)=Mc(i,:)
else
m(i,:)=m(i,:)/mN(i);
end
end
Mc=m
S0=S1
end;
endfunction;
//Dados de entrada, lista de vetores linha
X=[[ 1,1];[2,2];[4,3];[5,3];[6,4];[1,2];[3,4];[1,5];[2.1,3.5]]
//Lista de centros (vetores linha)
Mc=[[2,2];[1,2];[1,1]];
//Mc=[[2.1,3.5];[4,4];[4,3]];
plotPoints(X,'ko');
plotPoints(Mc(1,:),'gx');
plotPoints(Mc(2,:),'bx');
plotPoints(Mc(3,:),'cx');
ax=gca(),//Captura dos parâmetros do plot atual.
ax.data_bounds=[0 0; 7 7];
ax.children.children.thickness=2
xtitle('www.drgomes.pro')
h=xstring(2.2,6.2,"Centroids starting position")
h.font_size = 3;
h.box="on"
h.fill_mode="on"
//h.alignment="center"
xlabel('x1')
ylabel('x2')
xgrid
isoview('on')
[Mc,S,n]=kmeans(X,Mc,4);
disp("Número de interações:",n)
disp("Posição dos centroides:",Mc)
disp("Classificação das instâncias em relação aos centroides:",S')
scf
plotPoints(X(S==1,:),'go');
plotPoints(X(S==2,:),'bo');
plotPoints(X(S==3,:),'co');
plotPoints(Mc(1,:),'g+');
plotPoints(Mc(2,:),'b+');
plotPoints(Mc(3,:),'c+');
ax=gca(),//Captura dos parâmetros do plot atual.
ax.data_bounds=[0 0; 7 7];
ax.children.children.thickness=2
xtitle('www.drgomes.pro')
h=xstring(2.2,6.2,"Centroids final position")
h.font_size = 3;
h.box="on"
h.fill_mode="on"
xlabel('x1')
ylabel('x2')
xgrid
isoview('on')
Abaixo segue os resultados da execução do script deste exemplo ilustrativo. Na Figura 1, temos os dados “brutos” não rotulados da Tabela 1. Todos as instâncias estão representadas como bolinhas pretas ou seja sem um rótulo definido.
Figura 1: Plotagem dos dados não rotulados da Tabela 1.
Na Figura 2, temos indicado as posições inicias escolhidas para os centroides. Estas posições iniciais foram escolhidas como sendo idênticas as instâncias da Tabela 1, $x_2=[2,2]$, $x_6=[1,2]$ e $x_1=[1,1]$. No código do exemplo, há na linha 96 uma segunda opção de centroides iniciais. Essa segunda opção de centroides iniciais leva a resultados completamente diferentes, mostrando a dependência do k-means em relação aos parâmetros iniciais.
Figura 2: Plotagem dos dados não rotulados da Tabela 1 com a posição inicial dos centroides passados para o k-means.
Na Figura 3, segue uma animação do funcionamento do k-means passo-a-passo. Notem que posição dos centroides muda a cada passo até atingir uma configuração estável ao longo das interações. No total, para os pontos da tabela 1, o algoritmo leva 4 interações para convergir. Mesmo quando o conjunto de dados de entrada é significativamente maior o k-means normalmente converge em poucas interações. Na animação também é possível notar que a coloração das instâncias também muda de uma interação para outra, dependendo do centroide mais próximo. A coloração indica a qual grupo a instância pertence.
Figura 3: Animação do funcionamento interativo do k-means. As bolinhas indicam a posição das instâncias de entrada da Tabela 1. A coloração de cada bolinha indica a qual grupo a instância pertence e os “+” indicam as respectivas posições dos centroides de cada agrupamento.
Por fim, na Figura 4, temos o resultado final dos agrupamentos construídos pelo k-means considerando $k=3$ e os seguintes centroides iniciais: $x_2=[2,2]$, $x_6=[1,2]$ e $x_1=[1,1]$.
Figura 4: Resultado final do agrupamento realizado pelo k-means com $k=3$ e após 4 interações.
Como sempre, comentários, dúvidas, sugestões e críticas são bem vindas.
That’s all folks!
Deixe um comentário