Questão de Análise de Informação · FGV CGE-SC 2022 (nº 52)

K-Means é um algoritmo de clusterização (agrupamento) que divide um conjunto de dados em $K$ grupos, onde cada ponto pertence ao grupo do centroide (ponto médio) mais próximo. Ele funciona em iterações: primeiro, atribui cada ponto ao centroide mais próximo, e depois recalcula a posição dos centroides como a média dos pontos em cada grupo.

Para a primeira iteração, calculamos a distância (euclidiana quadrada para simplificar) de cada ponto aos centros iniciais c1=(1,2,5) e c2=(7,6,1):

1. Distâncias a c1=(1,2,5):

   • d(x1,c1)^2 = 0
   • d(x2,c1)^2 = $(3-1)^2 + (4-2)^2 + (2-5)^2 = 4+4+9 = 17$
   • d(x3,c1)^2 = $(9-1)^2 + (5-2)^2 + (3-5)^2 = 64+9+4 = 77$
   • d(x4,c1)^2 = $(7-1)^2 + (6-2)^2 + (1-5)^2 = 36+16+16 = 68$
   • d(x5,c1)^2 = $(2-1)^2 + (3-2)^2 + (5-5)^2 = 1+1+0 = 2$
   • d(x6,c1)^2 = (8-1)^2 + (7-2)^2 + (2-5)^2 = 49+25+9 = 83\

2. Distâncias a c2=(7,6,1):

   • d(x1,c2)^2 = $(1-7)^2 + (2-6)^2 + (5-1)^2 = 36+16+16 = 68$
   • d(x2,c2)^2 = $(3-7)^2 + (4-6)^2 + (2-1)^2 = 16+4+1 = 21$
   • d(x3,c2)^2 = $(9-7)^2 + (5-6)^2 + (3-1)^2 = 4+1+4 = 9$
   • d(x4,c2)^2 = 0
   • d(x5,c2)^2 = $(2-7)^2 + (3-6)^2 + (5-1)^2 = 25+9+16 = 50$
   • d(x6,c2)^2 = (8-7)^2 + (7-6)^2 + (2-1)^2 = 1+1+1 = 3\

3. Atribuição aos grupos (ponto ao centroide mais próximo):

   • x1: d(x1,c1)^2=0 < d(x1,c2)^2=68 -> Grupo 1
   • x2: d(x2,c1)^2=17 < d(x2,c2)^2=21 -> Grupo 1
   • x3: d(x3,c1)^2=77 > d(x3,c2)^2=9 -> Grupo 2
   • x4: d(x4,c1)^2=68 > d(x4,c2)^2=0 -> Grupo 2
   • x5: d(x5,c1)^2=2 < d(x5,c2)^2=50 -> Grupo 1
   • x6: d(x6,c1)^2=83 > d(x6,c2)^2=3 -> Grupo 2

   Grupos formados:

   • Grupo 1: {x1, x2, x5} = {(1,2,5), (3,4,2), (2,3,5)}
   • Grupo 2: {x3, x4, x6} = {(9,5,3), (7,6,1), (8,7,2)}

4. Recálculo dos novos centroides:

   • c1_novo = média dos pontos do Grupo 1 = $((1+3+2)/3, (2+4+3)/3, (5+2+5)/3)$
     • c1_novo = $(6/3, 9/3, 12/3) = (2,3,4)$
   • c2_novo = média dos pontos do Grupo 2 = $((9+7+8)/3, (5+6+7)/3, (3+1+2)/3)$
     • c2_novo = $(24/3, 18/3, 6/3) = (8,6,2)$

• (A) Incorreta: Os grupos {x1, x3, x5} e {x2, x4, x6} estão incorretos. Por exemplo, x3 está mais próximo do centroide inicial c2 (distância quadrada=9) do que de c1 (distância quadrada=77), mas foi colocado no Grupo 1. Além disso, mesmo que os grupos estivessem corretos, os centroides listados seriam arredondamentos incorretos das médias dos pontos. Esta é a armadilha da banca, pois combina erros de atribuição com arredondamento dos centroides resultantes.
• (B) Incorreta: Esta alternativa sugere 3 grupos (K=3), mas o problema define 2 centros iniciais, indicando K=2. É um distrator para quem não compreende o parâmetro K.
• (C) Correta: Conforme os cálculos detalhados acima, os pontos são corretamente atribuídos aos grupos Grupo 1: {x1, x2, x5} e Grupo 2: {x3, x4, x6}. Os novos centroides, calculados como a média dos pontos em seus respectivos grupos, são c1=(2,3,4) e c2=(8,6,2).
• (D) Incorreta: Os grupos {x1, x2, x3} e {x4, x5, x6} estão incorretos, pois x3 está mais próximo de c2 e x5 está mais próximo de c1. Consequentemente, os centroides calculados a partir desses grupos também seriam diferentes dos apresentados.
• (E) Incorreta: Os grupos {x2, x3, x5} e {x1, x4, x6} estão incorretos, pois x1 está mais próximo de c1 e x3 está mais próximo de c2. Consequentemente, os centroides calculados a partir desses grupos também seriam diferentes dos apresentados.