3.1 Las reglas 1-NN y k-NN

Las reglas de clasificación por vecindad están basadas en la búsqueda en un conjunto de prototipos de los k prototipos más cercanos al patrón a clasificar.

La búsqueda no se realiza necesariamente en el conjunto completo de prototipos, T, por lo que denominaremos conjunto de referencia (y lo notaremos por R) al conjunto de prototipos sobre el que se buscará el(los) vecino(s) más cercano(s). Debemos adelantar que R no tiene porqué ser un subconjunto de T: los métodos adaptativos de aprendizaje (sección 6) proporcionan un conjunto de referencia que no es (usualmente) un subconjunto de T. Sin embargo, los métodos de edición y condensado si proporcionan un subconjunto de T como conjunto de referencia.

En cualquier caso, sea cual sea el conjunto de referencia debe especificarse una métrica para poder medir la proximidad. Suele utilizarse por razones computacionales la distancia Euclídea, $\delta_{E}^{}$, para este fín.

3.1.1 Regla 1-NN

La regla de clasificación por vecindad más simple es la regla de clasificación del vecino más cercano o simplemente 1-NN. Se basa en la suposición de que la clase del patrón a etiquetar, X, es la del prototipo más cercano en R, al que notaremos por X_NN. Si | R| = N esta regla puede expresarse como:

 

$$\omega_{c}^{} \left\{\vphantom{ \begin{array}{l} \delta(X,X_{NN}) = {\stackre... ...}\space \{\delta(X,X_i)\}\\ (X_{NN}, \omega_c)\, \in\, {R} \end{array}}\right. \begin{array}{l} \delta(X,X_{NN}) = {\stackrel{\mbox{min}} {\sp... ...dots N}}}\space \{\delta(X,X_i)\}\\ (X_{NN}, \omega_c)\, \in\, {R} \end{array} \left.\vphantom{ \begin{array}{l} \delta(X,X_{NN}) = {\stackrel... ...}\space \{\delta(X,X_i)\}\\ (X_{NN}, \omega_c)\, \in\, {R} \end{array}}\right.$$ (29)

En la figura 20.A mostramos cómo se clasificaría el patrón X con la regla 1NN para un problema de clasificación de dos clases. Existen cuatro prototipos de clase 1 (representados por cruces) y cinco prototipos de clase dos (representados por asteriscos). El prototipomás cercano es de clase 2, por lo que ésta será la clase asociada a X.

El efecto de esta regla es el de dividir el espacio de representación en N ``regiones de influencia'', una por cada prototipo. Cada una de esas regiones tiene forma poligonal y los bordes corresponden a los puntos situados a igual distancia entre prototipos. Cada una de estas regiones se conoce como región de Voronoi y la partición poligonal del espacio de representación se conoce como partición de Voronoi. En la figura 20.B mostramos la partición de Voronoi asociada a este sencillo problema.

  

Figura 20: A) Clasificación 1-NN. B) En trazo contínuo, la frontera de decisión; en trazo discontínuo, los bordes de la partición de Voronoi asociada.

Cada región de Voronoi puede considerarse como una región de decisión (restringida al prototipo central), por lo que la región de decisión de una clase será la unión de todas las regiones de Voronoi de los prototipos de esa clase. La consecuencia es que las fronteras de decisión serán fronteras lineales a trozos.

3.1.2 Regla k-NN

La regla de clasificación por vecindad más general es la regla de clasificación de los k vecinos más cercanos o simplemente k-NN. Se basa en la suposición de que los prototipos más cercanos tienen una probabilidad a posteriori similar.

Si K_i(X) es el número de muestras de la clase $\omega_{i}^{}$ presentes en los k vecinos más próximos a X, esta regla puede expresarse como:

 

$$\omega_{c}^{} \max_{\space i=1 \ldots J}^{}$$ (30)

En la figura 21 mostramos cómo se realizaría la clasificación 3-NN del mismo patrón que se utilizó como ejemplo de clasificación 1-NN en la figura 13. En este caso, K₁(X) = 1 y K₂(X) = 2 por lo que X se etiquetará como de clase 2.

  

Figura 21: Clasificación 3-NN.