Límite de decisión de Knn

Question

Soy nuevo en el aprendizaje automático y estoy tratando de dibujar el límite de decisión para k vecinos más cercanos donde k=3. Sé que el límite de decisión para k=1 sería la bisectriz perpendicular entre dos clases diferentes. Pero cómo puedo dibujar el límite de decisión para k>=3.

Answer 1

Esta es una forma sencilla de trazar el límite de decisión para cualquier clasificador (incluido el KNN con un valor arbitrario) $k$ ). Voy a suponer 2 dimensiones de entrada.

1. Entrenar el clasificador en el conjunto de entrenamiento.

2. Crear una malla uniforme de puntos que cubra densamente la región del espacio de entrada que contiene el conjunto de entrenamiento.

3. Clasifica cada punto de la cuadrícula. Almacenar los resultados en un array $A$ , donde $A_{ij}$ contiene la clase predicha para el punto en la fila $i$ , columna $j$ en la red.

4. Representar la matriz como una imagen, donde cada píxel corresponde a un punto de la cuadrícula y su color representa la clase predicha. El límite de decisión puede verse como contornos en los que la imagen cambia de color.

5. Las coordenadas y las clases previstas de los puntos de la cuadrícula también pueden pasarse a una función de trazado de contornos (por ejemplo contour() o contourf() en python o matlab). Esto trazará los contornos correspondientes al límite de decisión.

Por ejemplo, el gráfico de contornos de la derecha muestra el resultado de este procedimiento, tras ajustar un clasificador KNN ( $k=25$ ) al conjunto de datos en espiral de la izquierda:

Answer 2

Para 3 puntos, el límite (también llamado diagrama de Voronoi) se forma tomando el triángulo sobre estos puntos y dibujando las bisectrices perpendiculares. La geometría clásica nos dice que se intersecarán en un único punto, que es el centro del círculo circunscrito. Así que basta con extender las líneas azules de abajo para obtener la región.

Para un número arbitrario de puntos, existen algoritmos eficientes para dibujar la frontera que suelen ser, en el peor de los casos $O(n\log n)$ . Vea aquí: https://dccg.upc.edu/people/vera/wp-content/uploads/2013/06/GeoC-Voronoi-algorithms.pdf