PDI+VC · Exercício de Programação

EP07_01 — 🟢 Classificador k-NN Passo a Passo

7.18.1 EP07_01 🟢 Classificador k-NN Passo a Passo

O KNeighborsClassifier do scikit-learn, usado ao longo do capítulo, esconde por trás de uma única chamada (.fit / .predict) uma regra de decisão bastante simples: para cada nova observação, calcular a distância a todos os exemplos de treinamento, selecionar os \(k\) mais próximos e votar pela classe majoritária entre eles.

Antes de confiar na biblioteca, você foi encarregado de implementar essa regra do zero, para um espaço de características bidimensional, exatamente como o simulador interativo de fronteira de decisão do capítulo faz internamente a cada clique do usuário.

7.18.1.1 📋 Diretrizes de Implementação

  1. Quantidade e parâmetro: Ler o inteiro \(N\) (número de exemplos de treinamento) e o inteiro ímpar \(k\) (número de vizinhos).
  2. Exemplos de treinamento: Para cada um dos \(N\) exemplos, ler três valores: as coordenadas \(x\) e \(y\) (reais) e o rótulo \(r\) (inteiro, \(0\) ou \(1\)).
  3. Consultas: Ler o inteiro \(Q\) (número de pontos de consulta) e, em seguida, as coordenadas \(x_q\), \(y_q\) (reais) de cada consulta.
  4. Distância: Para cada consulta, calcular a distância euclidiana até todos os exemplos de treinamento: \[ d(x_q, x_i) = \sqrt{(x_q - x_i)^2 + (y_q - y_i)^2}. \]
  5. Seleção dos vizinhos: Ordenar os exemplos por distância crescente e selecionar os \(k\) primeiros. Em caso de empate de distância na fronteira do k-ésimo vizinho, desempate pelo exemplo lido primeiro na entrada (ordem de leitura estável).
  6. Votação majoritária: Contar os votos de cada classe entre os \(k\) vizinhos selecionados. Se houver empate na votação (apenas possível quando \(k\) é par, o que não deve ocorrer pela diretriz do item 1, mas trate defensivamente), atribua a classe do vizinho mais próximo entre as classes empatadas.
  7. Saída: Para cada consulta, na ordem de entrada, imprimir a classe prevista. Ao final, imprimir o total de consultas classificadas como classe 1.

7.18.1.2 📌 Restrições Computacionais

  • Métrica fixa: utilize exclusivamente a distância euclidiana (não a squared distance) para a ordenação, embora o resultado da comparação seja o mesmo.
  • k sempre ímpar: a entrada garante \(k\) ímpar e \(k \le N\); ainda assim, implemente o desempate do item 6 por robustez.
  • Estabilidade: ao ordenar por distância, preserve a ordem relativa de exemplos com a mesma distância (ordenação estável).

7.18.1.3 🧠 Fundamentação Teórica

Elemento Papel no k-NN
Espaço de características Conjunto de todos os vetores \((x, y)\) possíveis
Distância euclidiana Medida de similaridade entre observações
\(k\) pequeno Fronteira irregular, alta variância
\(k\) grande Fronteira suave, alto viés
Votação majoritária Regra de decisão \(\hat y = \operatorname{moda}\{y_i : x_i \in N_k(x)\}\)

7.18.1.4 📦 Especificação de Entrada e Saída (VPL)

Entrada:

  • Linha 1: Inteiros \(N\) e \(k\), separados por espaço.
  • Próximas \(N\) linhas: três valores por linha — \(x\), \(y\) (reais) e \(r\) (inteiro \(\in \{0,1\}\)), separados por espaço.
  • Próxima linha: inteiro \(Q\).
  • Próximas \(Q\) linhas: dois valores por linha — \(x_q\), \(y_q\) (reais), separados por espaço.

Saída:

  • \(Q\) linhas, cada uma com a classe prevista (0 ou 1) para a respectiva consulta, na ordem de entrada.
  • Última linha: Total classe 1: X.

7.18.1.5 📌 Exemplos

Entrada Saída Observação
4 3
0 0 0
1 0 0
5 5 1
6 5 1
1
1 1		 0
Total classe 1: 0		 Consulta próxima do agrupamento de classe 0.
4 1
0 0 0
1 0 0
5 5 1
6 5 1
2
0.9 0.1
5.5 5.1		 0
1
Total classe 1: 1		 Com \(k=1\), cada consulta herda a classe do vizinho mais próximo.
🎮 Simulador EP07_01: Classificador k-NN Passo a Passo Votação Majoritária
Ajuste k e veja quais exemplos de treinamento (ordenados por distância) participam da votação para a consulta fixa (★ em x = 3, y = 3).
–
Figura 7.21: Simulador EP07_01: Classificador k-NN Passo a Passo 
%%writefile EP07_01.py
# Código Python
Writing EP07_01.py
TestSuite("EP07_01.py").run()
✔️ EP07_01.cases já existe em casos/
📋 5 caso(s) carregado(s) de casos/EP07_01.cases

🔍 Testando Python: EP07_01.py
⚠️ EP07_01.py: Arquivo sem conteúdo (menos de 3 linhas). Testes ignorados.