3.4 Consideraciones sobre las reglas k-NN

La aplicación de las reglas de clasificación por vecindad requiere, en la práctica, el conocimiento de ciertas restricciones de convergencia y del coste computacional asociado a su aplicación.

3.4.1 Consideraciones computacionales

Antes de nada hay que tener en cuenta que el coste computacional asociado a las reglas 1-NN y k-NN es equiparable. La diferencia estriba en que en la búsqueda de los k vecinos, en todo momento se debe mantener una estructura auxiliar que mantenga ordenados los k vecinos más cercanos encontrados hasta ese punto. Supongamos que se han procesado m prototipos ( Z₁, Z₂,..., Z_m) y X_NN, X_2NN,..., X_kNN son los k patrones (asociados a los m prototipos) más cercanos a X. El patrón asociado al prototipo Z_{m + 1} (X_{m + 1}) formará parte de los k vecinos más cercanos si $\delta_{E}^{}$(X, X_{m + 1}) < $\delta_{E}^{}$(X, X_kNN). Basta una sóla comparación para determinar si debe estar entre los k más cercanos. La posición exacta que le corresponde se determina fácilmente, considerando el valor de $\delta_{E}^{}$(X, X_{m + 1}), insertándo X_{m + 1} en el sitio que le corresponde. Esta última operación no es significactiva y puede considerarse despreciable frente al coste total.

 

Ejemplo

Supongamos un conjunto de N = 500 prototipos unidimensionales esbozado a continuación y a partir de él se quiere clasificar el patrón X = 10 con la regla 3-NN.

$$\underbrace{(50,1)}\, \underbrace{(25,2)}\, \underbrace{(30,2)}\, \underbrace{(40,1)}\, \underbrace{(20,2)}\, \underbrace{(60,1)}\, \underbrace{(12,2)}\,$$ R =           Z₁               Z₂               Z₃               Z₄               Z₅               Z₆                   Z₅₀₀

Cuando se han procesado los tres primeros prototipos (m = 3),

XNN = 25 (Z2)	$$\delta_{E}^{}$$(X, XNN) = $$\delta_{E}^{}$$(10, 25) = 15
X2NN = 30 (Z3)	$$\delta_{E}^{}$$(X, X2NN) = $$\delta_{E}^{}$$(10, 30) = 20
X3NN = 50 (Z1)	$$\delta_{E}^{}$$(X, X3NN) = $$\delta_{E}^{}$$(10, 50) = 40

Al procesar el cuarto prototipo encontramos que

$$\delta_{E}^{}$$(X, X₄) = $$\delta_{E}^{}$$(10, 40) = 30 < $$\delta_{E}^{}$$(X, X_3NN) = 40

por lo que éste debe formar parte de los 3 más cercanos. Como el orden de los más cercanos está determinado por la distancia se busca su sitio en la estructura y se inserta ordenadamente:

XNN = 25 (Z2)	$$\delta_{E}^{}$$(X, XNN) = $$\delta_{E}^{}$$(10, 25) = 15
X2NN = 30 (Z3)	$$\delta_{E}^{}$$(X, X2NN) = $$\delta_{E}^{}$$(10, 30) = 20
X3NN = 40 (Z4)	$$\delta_{E}^{}$$(X, X3NN) = $$\delta_{E}^{}$$(10, 40) = 30

Al procesar el quinto prototipo encontramos que

$$\delta_{E}^{}$$(X, X₅) = $$\delta_{E}^{}$$(10, 20) = 10 < $$\delta_{E}^{}$$(X, X_3NN) = 30

por lo que éste debe formar parte de los 3 más cercanos. Después de insertarlo ordenadamente:

XNN = 20 (Z5)	$$\delta_{E}^{}$$(X, XNN) = $$\delta_{E}^{}$$(10, 20) = 10
X2NN = 25 (Z2)	$$\delta_{E}^{}$$(X, X2NN) = $$\delta_{E}^{}$$(10, 25) = 15
X3NN = 30 (Z3)	$$\delta_{E}^{}$$(X, X3NN) = $$\delta_{E}^{}$$(10, 30) = 20

Al procesar el sexto prototipo encontramos que

$$\delta_{E}^{}$$(X, X₆) = $$\delta_{E}^{}$$(10, 60) = 50 > $$\delta_{E}^{}$$(X, X_3NN) = 20

por lo que éste no formará parte de los 3 más cercanos. El mismo proceso se sigue para los restantes prototipos de R.

Así, sea cual sea el valor de k la búsqueda requiere explorar todo el conjunto de referencia. Esto significa que el coste de la búsqueda depende linealmente de N. Ahora debemos considerar el coste del cálculo de cada distancia. Se puede comprobar fácilmente (es un buen ejercicio) que el cálculo de la distancia Euclídea tiene un coste lineal respecto a d (coste global: O(Nd )) mientras que el coste de una distancia de Mahalanobis es cuadrático respecto a d (coste global: O(Nd²)). Adicionalmente debemos considerar el espacio de almacenamiento requerido: deben consultarse todos los prototipos, por lo que los requerimientos de espacio son del orden O(Nd ).

Si consideramos que la optimalidad está garantizada cuando el conjunto de referencia es lo suficientemente grande, la aplicación de las reglas k-NN en su formulación original (fuerza bruta) resulta, en la práctica, inaplicable si se dispone de conjuntos de referencia numerosos y con datos de alta dimensionalidad.

De todo lo anterior se deduce que dos son los factores que determinan el coste computacional de las reglas k-NN:

1.

La dimensionalidad de los datos, d.

2.

El tamaño del conjunto de referencia, N.

Cuando se dispone de datos de alta dimensionalidad, puede utilizarse alguna de las técnicas de selección de características, tratadas con detalle en el capítulo 5.

Existen diferentes estrategias que permiten la aplicación de la regla del vecino más cercano para conjuntos de referencia numerosos con un coste computacional menor que el asociado a la fuerza bruta. Estas estrategias pueden agruparse en dos clases, de acuerdo a la filosofía en que se basan:

1.

Reducir el conjunto de referencia.

Se basan en la selección de un subconjunto del conjunto de referencia que tenga las mismas propiedades que el conjunto original para, una vez reducido, aplicar la regla del vecino más cercano en su formulación original (fuerza bruta) sobre el nuevo conjunto.

Si M es el número de prototipos del conjunto reducido, el orden de complejidad sigue siendo lineal respecto a M, con la salvedad de que ahora M < N (en muchos casos, y para ser más precisos, M < < N). No obstante, la selección de un conjunto de referencia reducido que refleje todas las características del conjunto general no está garantizado. Estos métodos se estudiarán con detalle en las secciones 4, 5 y 6.

2.

Mejorar la eficiencia computacional de la búsqueda del vecino más cercano.

Estos métodos trabajan con el conjunto completo de referencia y su objetivo es reducir el número de cálculos, eliminando aquellos que se consideran ``inútiles'' o ``innecesarios''.

En estos casos pueden conseguirse órdenes de complejidad del orden de O(log N) en el mejor de los casos. La utilización de estos métodos no representa ningún peligro de pérdidad de generalidad ya que están orientados, únicamente, a reducir el número de cálculos.

Entre estos métodos están los basados en ordenaciones y jerárquicos.

Los métodos basados en ordenaciones organizan los patrones del conjunto de referencia de acuerdo a alguna coordenada, y la búsqueda se realiza de acuerdo a alguna propiedad de la métrica asociada al espacio. El estudio de estos métodos escapa a nuestro interés y no los trataremos.

Los métodos jerárquicos realizan una descomposición jerárquica del conjunto de referencia que implica la organización de los patrones en una estructura de tipo árbol, para después aplicar una técnica de poda y ramificación (branch and bound) para explorar el árbol. Para obtener información adicional sobre este tema puede consultar en la siguiente dirección: http://www-etsi2.ugr.es/depar/ccia/rf/otros.htm

No obstante, hay que considerar que todos estos métodos tienen asociado un coste adicional a la búsqueda: el coste del preprocesamiento, entendido éste como el coste asociado a la selección del conjunto reducido o la construcción del árbol de búsqueda. En consecuencia, para determinadas aplicaciones se ha de considerar que el coste de preprocesamiento puede ser alto y que la elección de estos métodos como alternativa a la fuerza bruta debe considerar, necesariamente, este coste y llegar a un compromiso entre los costes de procesamiento y búsqueda.

3.4.2 Otras consideraciones

En primer lugar, debemos recordar que para asegurar la optimalidad N debe ser muy alto (virtualmente infinito). En la práctica, sin embargo, encontramos conjuntos finitos de muestras y en ocasiones muy reducidos. Aunque en la literatura se pueden encontrar soluciones a este problema, su estudio escapa a nuestro interés.

Otro problema que afecta seriamente a la eficacia (en términos de tasa de acierto o bondad) de los métodos k-NN es la presencia de prototipos erróneamente etiquetados en el conjunto de entrenamiento. Estos prototipos suelen aparecer en zonas cercanas a las regiones de decisión y afectan seriamente al resultado de la clasificación. Los métodos de edición eliminan esos prototipos que inducen a una correcta clasificación. Así, además de conseguir una reducción (en ocasiones notable) del conjunto de referencia proporcionan un conjunto de ``calidad'' que hace incrementar la tasa de acierto de la regla 1-NN cuando se aplica sobre conjuntos editados. Los métodos de edición se estudian con detalle en la sección 4.