Questão de Tecnologia da Informação · FGV DATAPREV 2024 (nº 62)

O algoritmo k-NN (k-Nearest Neighbors) classifica um novo ponto de dados encontrando os 'k' pontos mais próximos (vizinhos) no conjunto de treinamento e atribuindo a ele a classe mais comum entre esses vizinhos. A distância euclidiana é usada para medir a proximidade entre os pontos.

Vamos calcular as distâncias do novo ponto $x=(5.0, 5.0)$ para cada ponto do conjunto de dados:

• $d((5.0, 5.0), (1.0, 1.0)) = \sqrt{(5-1)^2 + (5-1)^2} = \sqrt{4^2 + 4^2} = \sqrt{16+16} = \sqrt{32} \approx 5.656$ (Classe C)
• $d((5.0, 5.0), (1.0, 5.0)) = \sqrt{(5-1)^2 + (5-5)^2} = \sqrt{4^2 + 0^2} = \sqrt{16} = 4.0$ (Classe A)
• $d((5.0, 5.0), (4.0, 5.0)) = \sqrt{(5-4)^2 + (5-5)^2} = \sqrt{1^2 + 0^2} = \sqrt{1} = 1.0$ (Classe B)
• $d((5.0, 5.0), (5.0, 1.0)) = \sqrt{(5-5)^2 + (5-1)^2} = \sqrt{0^2 + 4^2} = \sqrt{16} = 4.0$ (Classe D)
• $d((5.0, 5.0), (5.0, 4.0)) = \sqrt{(5-5)^2 + (5-4)^2} = \sqrt{0^2 + 1^2} = \sqrt{1} = 1.0$ (Classe B)

Ordenando as distâncias em ordem crescente:

1. Ponto (4.0, 5.0), Classe B, Distância = 1.0
2. Ponto (5.0, 4.0), Classe B, Distância = 1.0
3. Ponto (1.0, 5.0), Classe A, Distância = 4.0
4. Ponto (5.0, 1.0), Classe D, Distância = 4.0
5. Ponto (1.0, 1.0), Classe C, Distância $\approx 5.656$

(A) Incorreta: Para k=2, os dois vizinhos mais próximos são (4.0, 5.0) e (5.0, 4.0), ambos da Classe B. Portanto, a classe seria B, não A. A regra de desempate mencionada não é padrão e não se aplicaria aqui.
(B) Correta: Para k=1, o vizinho mais próximo é o ponto com a menor distância. Há um empate entre (4.0, 5.0) e (5.0, 4.0), ambos com distância 1.0. Ambos pertencem à Classe B. Assim, a classe de $x$ para k=1 é B.
(C) Incorreta: Para k=1, a classe é determinada pelo vizinho mais próximo. O ponto (1.0, 1.0) da Classe C é o mais distante ($\approx 5.656$), não o mais próximo. O conceito de "votação" é para k > 1.
(D) Incorreta: Para k=3, os três vizinhos mais próximos seriam (4.0, 5.0) (Classe B), (5.0, 4.0) (Classe B) e, devido ao empate na 3ª posição, um dos pontos com distância 4.0, por exemplo, (1.0, 5.0) (Classe A). A maioria seria B (2 votos para B, 1 para A). A classe D não seria a maioria. O critério de distância ponderada é uma variação do k-NN clássico.
(E) Incorreta: O algoritmo k-NN opera perfeitamente com atributos-alvo categóricos (as "Classes"), que é o objetivo da classificação. Os atributos preditores (P e Q) são numéricos, o que permite o cálculo de distâncias.