3.3 Extensiones: clase de rechazo

Las reglas de clasificación por vecindad pueden ampliarse para considerar la clase de rechazo. La extensión directa de la regla k-NN dada por la expresión 30 sería la llamada regla (k, t)-NN:

d (X) = $\displaystyle \left\{\vphantom{ \begin{array}{ll} \omega_c & \mbox{\space si\... ... \geq \space t \\ \omega_0 & \mbox{\space en otro caso} \end{array}}\right.$ $\displaystyle \begin{array}{ll} \omega_c & \mbox{\space si\space \ } K_c(X) = ... ...\}\space \geq \space t \\ \omega_0 & \mbox{\space en otro caso} \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{ll} \omega_c & \mbox{\space si\s... ... \geq \space t \\ \omega_0 & \mbox{\space en otro caso} \end{array}}\right.$

(33)

Si se desea especificar un umbral específico para cada clase, la regla anterior se conoce como la regla (k, t_c)-NN:

d (X) = $\displaystyle \left\{\vphantom{ \begin{array}{ll} \omega_c & \mbox{\space si\... ...\geq \space t_c\\ \omega_0 & \mbox{\space en otro caso} \end{array}}\right.$ $\displaystyle \begin{array}{ll} \omega_c & \mbox{\space si\space \ } K_c(X) = ... ...}\space \geq \space t_c\\ \omega_0 & \mbox{\space en otro caso} \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{ll} \omega_c & \mbox{\space si\s... ...\geq \space t_c\\ \omega_0 & \mbox{\space en otro caso} \end{array}}\right.$

(34)

Sobre la regla 1-NN no hay más opción que establecer el umbral en base a criterios de distancia. La regla 1-NN (t) se formula como sigue:

d (X) = $\displaystyle \left\{\vphantom{ \begin{array}{ll} \omega_c & \mbox{si\space \... ...{R} \end{array}\right. \\ \omega_0 & \mbox{en otro caso} \end{array}}\right.$ $\displaystyle \begin{array}{ll} \omega_c & \mbox{si\space \ } \left\{ \begin... ..., \in\, {R} \end{array}\right. \\ \omega_0 & \mbox{en otro caso} \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{ll} \omega_c & \mbox{si\space \ ... ...{R} \end{array}\right. \\ \omega_0 & \mbox{en otro caso} \end{array}}\right.$

(35)

La selección del valor umbral t se realiza después de examinar la distribución de las distancias de cada patrón a clasificar al vecino más próximo en R. Parece razonable que el valor umbral sea un valor cercano al tercer cuartil de esta distribución. De nuestra experiencia (ver [E.1]) podemos indicar que el valor exacto depende del problema, esto es, de los datos disponibles y del objetivo buscado, por lo que el valor exacto se selecciona ``ad-hoc'' después de examinar varios candidatos.

En este ejemplo mostramos la aplicación de la regla 1-NN (t) para la clasificación de una imagen de Teledetección que corresponde a una región de Groenlandia llamada Ymer Ø. El conjunto de entrenamiento tiene 8560 prototipos y 20 clases. La distribución de los prototipos no es homogéneo ya que entre las tres primeras clases acaparan el 43 % del total, repartiéndose el resto entre las otras clases.

La aplicación de la regla 1-NN (t) es particularmente aconsejable si el conjunto de clases informacionales no es exhaustivo y este el el caso que nos ocupa.

En esta región encontramos regiones extensas de aguas marinas, un gran glaciar en la parte superior derecha, algunos lagos de agua dulce de origen glaciar y en la parte inferior izquierda encontramos grandes sombras debidas a una pronunciada pendiente. No existe ninguna área de entrenamiento para estas clases informacionales que acabamos de describir y no es deseable que los píxeles de estas regiones sean clasificados en alguna de las clases seleccionadas. Si clasificamos esta imagen utilizando la regla 1-NN sin clase de rechazo, los píxeles de estas regiones serán clasificados en alguna de las clases informacionales seleccionadas, cuando deberían ser descartados ya que no son interesantes para el problema de la identificación de las estructuras geológicas presentes en esta región. Por esta razón es necesario descartarlos. Para ello utilizamos la regla 1-NN (t).

La selección de t se realizó después de calcular la distribución de las mínimas distancias. En la figura 22 mostramos la distribución de las distancias y la información estadística acerca de esta distribución.

**Figura 22:** Distribución de frecuencias de las distancias de cada patrón al prototipo más cercano y estadísticos de la distribución de distancias.
$\begin{figure} \centerline{ \psfig{figure=figures_3/histo_distancias.eps,height=6.5cm}} \end{figure}$

Lo más relevante de esta tabla es el valor del tercer cuartil, 1927, ya que el valor umbral debe estar cercano. En la figura 23.A mostramos cuatro clasificaciones obtenidas con diferentes valores de t cercanos al valor del tercer cuartil. Tan solo mostramos los píxeles descartados. En la tabla de la figura 23.B mostramos el efecto del valor umbral t sobre el número de puntos descartados. Resulta evidente que a mayor valor umbral, menos puntos son descartados.

**Figura 23:** A) Puntos descartados (en negro) con t = 1600, 1800, 2000 y 2100. B) Efecto del valor umbral t sobre el número de puntos descartados.
$\begin{figure} \centerline{ \psfig{figure=figures_3/1NNt_ymer.eps,height=7cm}} \end{figure}$

Puede observarse que las cuatro zonas de rechazo son muy similares, por lo que resulta difícil la selección de t de forma automática debido a que la bondad media de las clasificaciones obtenidas son muy similares. Esto se debe a que la medida del error se realiza mediante un conjunto de prueba y no existe ninguna zona de entrenamiento para estos píxeles que han sido descartados, por lo que tan sólo se producen ligeras variaciones en la bondad media cuando el número de píxeles descartados es mayor, ya que la probabilidad de descartar un punto de entrenamiento aumenta. En este caso, el valor umbral fué seleccionado por un experto, analizando las zonas de rechazo mostradas en la figura 23.A. Se seleccionó el valor 1600 porque proporciona unas buenas regiones de puntos desacartados en las que todos los píxeles que representan sombras, agua, hielo y el gran glaciar situado en la parte superior derecha están incluidos.

En la figura 24 mostramos la clasificación 1-NN (t) con t = 1600. La bondad media de esta clasificación es de 78.5 % (ver tabla 2).

**Figura 24:** Clasificación 1-NN (t) con t = 1600 de Ymer Ø
$\begin{figure} \centerline{ \psfig{figure=figures_3/ymer_clasif_1NNt.eps,height=6cm}} \end{figure}$

Tabla 2: Bondad del clasificador 1-NN (t) con Ymer Ø. Media = 78.50 %

Clase	Bondad	Clase	Bondad	Clase	Bondad	Clase	Bondad
1	88.74 %	6	68.67 %	11	69.70 %	16	100.00 %
2	98.21 %	7	46.75 %	12	58.47 %	17	89.92 %
3	78.87 %	8	97.32 %	13	100.00 %	18	61.36 %
4	63.86 %	9	38.10 %	14	65.87 %	19	82.20 %
5	59.40 %	10	39.24 %	15	69.79 %	20	73.83 %

En este ejemplo mostramos otra aplicación de la regla 1-NN (t) para la clasificación de una imagen de Teledetección que corresponde a una región de Groenlandia llamada Igaliko. El conjunto de entrenamiento tiene 28441 muestras y 5 clases. La distribución de estas muestras es bastante más homogénea que en el caso anterior (ver tabla 3). Al igual que en el caso anterior, en esta escena existen zonas para las que no se ha establecido una clase informacional durante el entrenamiento y que deberían ser descartadas en la clasificación. Concretamente corresponden a glaciares, zonas nevadas y algunas nubes.

Table 3: Número de prototipos por clases (Igaliko)

Clase 1	Clase 2	Clase 3	Clase 4	Clase 5	Total
3806	7542	5463	2796	8834	28441

La determinación del valor umbral de distancia se realizó mediante un procedimiento similar al ejemplo anterior y se seleccionó el valor t = 25. La razón de que este valor sea tan bajo en relación al seleccionado para el caso anterior radica en el bajo contraste de la imagen original. En la figura 25 mostramos la clasificación 1-NN (t) y en la tabla 4 mostramos la bondad de esta clasificación.

**Figura 25:** Clasificación 1-NN (t) con t = 25 de Igaliko.
$\begin{figure} \centerline{ \psfig{figure=figures_3/igal_clasif_1NNt.eps,height=6cm}} \end{figure}$

Las zonas de rechazo seleccionadas en esta clasificación son muy aceptables y recogen aquellos puntos que debían ser descartados.

Table 4: Bondad de la clasificación 1-NN (t) sobre Igaliko.

Clase 1	Clase 2	Clase 3	Clase 4	Clase 5	Media
84.40 %	99.80 %	81.81 %	26.92 %	57.01 %	74.61%