next up previous contents
Next: 3. Métodos de clasificación Up: 2. Estimación de la Previous: 2.1 Estimadores de Parzen

Subsections

   
2.2 Estimación mediante los k vecinos más próximos

Supongamos un espacio de representación bidimensional y una serie de prototipos de una misma clase representados en él (figura 16.A). Dado un patrón cualquiera X, si consideramos los k prototipos más próximos a X, éstos estarán localizados en un círculo centrado en X. En la figura 16.B resaltamos los 7 vecinos más cercanos a tres patrones.


  
Figura 16: A) Patrones en un espacio bidimensional. B) Los patrones considerados para la estimación de P(X|$ \omega$) mediante los 7 vecinos más cercanos son los encerrados en los círculos
\begin{figure} \centerline{ \psfig{figure=figures_3/7vecinos.eps,height=4.5cm}} \end{figure}

Parece sensato pensar que el área del círculo que encierra un número fijo de puntos, k, es menor en regiones densamente pobladas que en regiones donde los puntos están más dispersos. Este sencillo planteamiento es la base de la estimación mediante los k vecinos más próximos. En espacios multidimensionales, el círculo se convierte en una hiperesfera, y el planteamiento anterior se puede extender fácilmente ya que el volumen de la hiperesfera que encierra a k puntos está relacionado con el valor de la función de densidad de probabilidad en el centro de la hiperesfera. Veamos de qué manera.

Si Ki(X)  i = 1, 2,..., J es el número de prototipos de clase $ \omega_{i}^{}$ que se encuentran en una vecindad de X, el valor de $ \hat{p}$ (X| $ \omega_{i}^{}$) puede calcularse como la proporción de los Ni prototipos de la clase $ \omega_{i}^{}$ que se encuentran en esa vecindad:

 
$\displaystyle \hat{P}$ (X| $\displaystyle \omega_{i}^{}$)  =  $\displaystyle {\frac{K_i(X)}{N_i}}$ (24)

Si recordamos la manera en la que se estimaba la densidad de probabilidad empleando núcleos de Parzen, las vecindades son iguales para todos los patrones sobre los que se realiza la estimación y están determinadas por el parámetro $ \rho$.

Nuestro objetivo ahora es distinto ya que la vecindad no se establece en base a un parámetro fijado de antemano sino que depende del patrón considerado para la estimación:

Con esta idea, la ecuación 24 debe modificarse de manera que se pondere inversamente con el área de la región considerada. Para el caso d-dimensional, el área se convierte en el volumen de una hiperesfera centrada en X, V(X), por lo que el nuevo estimador se formula como:

 
$\displaystyle \hat{P}$ (X| $\displaystyle \omega_{i}^{}$)  =  $\displaystyle {\frac{K_i(X)}{N_i\space V(X)}}$ (25)

Para clarificar más acerca de la hiperesfera es necesario especificar que es la que está centrada en X y contiene los k vecinos más cercanos a X. En el caso bidimensional (ver figura 16), la esfera se convierte en un círculo y el volumen se convierte en superficie.

Se puede deducir que esta manera de estimar la densidad de probabilidad es diametralmente opuesta a la estimación por núcleos de Parzen ya que los métodos basados en núcleos realizan la estimación con un núcleo de ancho fijo mientras que la estimación por los vecinos más cercanos se hace mediante un ``núcleo'' de ancho variable que depende de la densidad de los prototipos en el espacio de representación.

 


Ejemplo

En este ejemplo comparamos la estimación realizada por el estimador de Parzen que emplea un núcleo hipercúbico y la estimación realizada en base a los k vecinos más cercanos. Emplearemos el conjunto de protopipos unidimensionales de un ejemplo anterior (ver figura 5).



Estimación con un núcleo de Parzen unidimensional.

Consideraremos un núcleo con ancho 5, común para las dos clases. Recordaremos que el volumen a considerar, constante para todos los puntos en los que se realiza la estimación, se reduce a una longitud en el caso unidimensional, en nuestro caso, 10. Para aplicar la ecuación 25 tendremos en cuenta que el denominador es constante para cada clase y común para las dos clases ya que N1 = N2, por lo que N1V(X) = N2V(X) = 6 x 10 = 60.

Dado un patrón cualquiera, X, consideramos el intervalo [X - 5, X + 5]:

1.
Se calcula Ki(X), el número de prototipos de cada clase que están en el intervalo considerado.
2.
Se divide entre el producto constante NiV(X).
El resultado es una estimación de la densidad de probabilidad de X para cada clase. En la figura 17.A mostramos es resultado de la estimación efectuada para X = { - 10.0, - 9.0,..., 29.0, 30.0}.



Estimación con los k vecinos más cercanos.

Consideraremos que k = 3 para la estimación, común para las dos clases. El volumen se reduce a una longitud, pero este valor depende del patrón en el que se realice la estimación, por lo que el denominador de la ecuación 25 no es constante para cada clase y debe calcularse para cada patrón.

Dado un patrón cualquiera, X, una vez que se han calculado cuales son sus tres vecinos más cercanos,

1.
Se calcula Ki(X), el número de prototipos de cada clase que están en el intervalo considerado.
2.
Se calcula la longitud del intervalo que los contiene. Será el doble de la distancia de X al tercer vecino más cercano (depende de X).
3.
Se divide entre el producto NiV(X).
El resultado es una estimación de la densidad de probabilidad de X para cada clase. En la figura 17.B mostramos es resultado de la estimación efectuada para X = { - 10.0, - 9.0,..., 29.0, 30.0}.


  
Figura 17: Estimación de las densidades de probabilidad en el rango [-10,30]. A) con un núcleo de ancho 5 fijo. B) utilizando los 3 vecinos más cercanos
\begin{figure} \centerline{ \psfig{figure=figures_3/estimac.eps,height=11cm}} \end{figure}



Discusión.

La primera estimación se realiza empleando una vecindad de ancho fijo para cada patrón, mientras que la segunda depende del patrón considerado. En la figura 18 mostramos dos ejemplos:


  
Figura 18: Estimación de las densidades de probabilidad para X = 0 y X = 16. A) con un núcleo de ancho 5 fijo. B) utilizando los 3 vecinos más cercanos
\begin{figure} \centerline{ \psfig{figure=figures_3/anchos.eps,height=11.5cm}} \end{figure}

1.
En el punto 0 (baja densidad):

El intervalo de radio 5 centrado en X = 0 engloba a los prototipos con valores 1, 2 y 5, todos de clase 1. El valor de la densidad de probabilidad estimada para este punto es: 3/(6 x 10) = 0.05.

Los tres vecinos más cercanos al patrón X = 0 son los prototipos con valores 1, 2 y 5, todos de clase 1. El más alejado es el prototipo con valor 5, que se encuentra a distancia 5, por lo que el intervalo a considerar es de ancho 5. El valor de la densidad de probabilidad estimada para este punto es, como antes, 3/(6 x 10) = 0.05.

2.
En el punto 16 (alta densidad):

El intervalo de radio 5 centrado en X = 16 engloba a los prototipos con valores 12, 14, 15, 16, 19 y 20, todos de clase 2. El valor estimado para este punto es: 6/(6 x 10) = 0.1.

Los tres vecinos más cercanos al patrón X = 16 son los prototipos con valores 14, 15 y 16, todos de clase 2. El más alejado es el prototipo con valor 14, que se encuentra a distancia 2, por lo que el intervalo a considerar es de ancho 4. El valor de la densidad de probabilidad estimada para este punto es ahora 3/(6 x 4) = 0.125.

No obstante, al igual que hemos discutido sobre el ancho de los núcleos de Parzen, debemos dedicar especial atención al número de vecinos que tomamos para la estimación.

2.2.1 Sobre la elección de k

El problema que se plantea ahora es el de si existe un valor óptimo para k o en su defecto si se pueden dar algunas reglas para fijar este valor. En primer lugar debemos considerar que k juega un papel similar a $ \rho$ para los núcleos de Parzen, por lo que resulta evidente que la elección de k está determinado por la densidad de los puntos y debería hacerse en relación a Ni.

Puede demostrarse (ver [B.3]) que el estimador dado en 25 es insesgado y consistente si se verifican las siguientes condiciones sobre k:


$\displaystyle \lim_{N_i \rightarrow \infty}^{}$k (Ni) = $\displaystyle \infty$  
       
$\displaystyle \lim_{N_i \rightarrow \infty}^{}$k (Ni) / Ni =   0  
       

Así, una elección adecuada de k (Ni) es:

 
k (Ni)  =  cte $\displaystyle \sqrt{N_i}$ (26)

 


Ejemplo

En este ejemplo mostraremos cómo afecta el valor de k a la estimación realizada a partir del conjunto de prototipos empelado en el ejemplo anterior. En la figura 19 mostramos diferentes estimaciones calculadas con diferentes valores de k.

Observar como cuanto mayor es el valor de k más grande es la vecindad, por lo que las funciones de densidad de probabilidad se hacen más suaves.


  
Figura 19: Estimación de las densidades de probabilidad utilizando los k vecinos más cercanos:
A) k = 3, B) k = 5 y C) k = 7
\begin{figure} \centerline{ \psfig{figure=figures_3/estimac_k_varios.eps,height=12cm}} \end{figure}

next up previous contents
Next: 3. Métodos de clasificación Up: 2. Estimación de la Previous: 2.1 Estimadores de Parzen

2000-11-30