PDI+VC · Ejercicio de Programación

EP07_01 — 🟢 Clasificador k-NN Paso a Paso

7.18.1 EP07_01 🟢 Clasificador k-NN Paso a Paso

El KNeighborsClassifier de scikit-learn, utilizado a lo largo del capítulo, oculta detrás de una única llamada (.fit / .predict) una regla de decisión bastante simple: para cada nueva observación, calcular la distancia a todos los ejemplos de entrenamiento, seleccionar los \(k\) más cercanos y votar por la clase mayoritaria entre ellos.

Antes de confiar en la biblioteca, se te ha encargado implementar esta regla desde cero, para un espacio de características bidimensional, exactamente como el simulador interactivo de frontera de decisión del capítulo lo hace internamente en cada clic del usuario.

7.18.1.1 📋 Directrices de Implementación

  1. Cantidad y parámetro: Leer el entero \(N\) (número de ejemplos de entrenamiento) y el entero impar \(k\) (número de vecinos).
  2. Ejemplos de entrenamiento: Para cada uno de los \(N\) ejemplos, leer tres valores: las coordenadas \(x\) e \(y\) (reales) y la etiqueta \(r\) (entera, \(0\) o \(1\)).
  3. Consultas: Leer el entero \(Q\) (número de puntos de consulta) y, a continuación, las coordenadas \(x_q\), \(y_q\) (reales) de cada consulta.
  4. Distancia: Para cada consulta, calcular la distancia euclidiana hasta todos los ejemplos de entrenamiento: \[ d(x_q, x_i) = \sqrt{(x_q - x_i)^2 + (y_q - y_i)^2}. \]
  5. Selección de vecinos: Ordenar los ejemplos por distancia creciente y seleccionar los \(k\) primeros. En caso de empate de distancia en la frontera del k-ésimo vecino, desempatar por el ejemplo leído primero en la entrada (orden de lectura estable).
  6. Votación mayoritaria: Contar los votos de cada clase entre los \(k\) vecinos seleccionados. Si hay empate en la votación (solo posible cuando \(k\) es par, lo que no debería ocurrir según la directriz del punto 1, pero tratar defensivamente), asignar la clase del vecino más cercano entre las clases empatadas.
  7. Salida: Para cada consulta, en el orden de entrada, imprimir la clase predicha. Al final, imprimir el total de consultas clasificadas como clase 1.

7.18.1.2 📌 Restricciones Computacionales

  • Métrica fija: utilizar exclusivamente la distancia euclidiana (no la distancia al cuadrado) para la ordenación, aunque el resultado de la comparación sea el mismo.
  • k siempre impar: la entrada garantiza \(k\) impar y \(k \le N\); aun así, implementar el desempate del punto 6 por robustez.
  • Estabilidad: al ordenar por distancia, preservar el orden relativo de ejemplos con la misma distancia (ordenación estable).

7.18.1.3 🧠 Fundamentación Teórica

Elemento Papel en el k-NN
Espacio de características Conjunto de todos los vectores \((x, y)\) posibles
Distancia euclidiana Medida de similitud entre observaciones
\(k\) pequeño Frontera irregular, alta varianza
\(k\) grande Frontera suave, alto sesgo
Votación mayoritaria Regla de decisión \(\hat y = \operatorname{moda}\{y_i : x_i \in N_k(x)\}\)

7.18.1.4 📦 Especificación de Entrada y Salida (VPL)

Entrada:

  • Línea 1: Enteros \(N\) y \(k\), separados por espacio.
  • Siguientes \(N\) líneas: tres valores por línea — \(x\), \(y\) (reales) y \(r\) (entero \(\in \{0,1\}\)), separados por espacio.
  • Siguiente línea: entero \(Q\).
  • Siguientes \(Q\) líneas: dos valores por línea — \(x_q\), \(y_q\) (reales), separados por espacio.

Salida:

  • \(Q\) líneas, cada una con la clase predicha (0 o 1) para la respectiva consulta, en el orden de entrada.
  • Última línea: Total clase 1: X.

7.18.1.5 📌 Ejemplos

Entrada Salida Observación
4 3
0 0 0
1 0 0
5 5 1
6 5 1
1
1 1		 0
Total clase 1: 0		 Consulta cercana al agrupamiento de clase 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 clase 1: 1		 Con \(k=1\), cada consulta hereda la clase del vecino más cercano.
🎮 Simulador EP07_01: Clasificador k-NN Paso a Paso Votación Mayoritaria
Ajusta k y observa qué ejemplos de entrenamiento (ordenados por distancia) participan en la votación para la consulta fija (★ en x = 3, y = 3).
–
Figura 7.21: Simulador EP07_01: Clasificador k-NN Paso a Paso 
%%writefile EP07_01.py
# Código Python
Overwriting EP07_01.py
TestSuite("EP07_01.py").run()
✔️ EP07_01.cases ya existe en casos/
📋 5 caso(s) cargado(s) de casos/EP07_01.cases

🔍 Probando Python: EP07_01.py
⚠️ EP07_01.py: archivo vacío (menos de 3 líneas). Pruebas omitidas.