Analizador Numérico



Clasificadores k-NN



Una forma básica de clasificar un caso es asignarle la misma clase que a otro caso similar cuya clasificación es conocida. Entre ellos destacan los métodos de clasificación por el vecino más cercano k-NN, donde k es impar (no tiene sentido probar con valores pares de k porque el error asociado a la regla k-NN es el mismo para 2x y 2x-1).

A la hora de construir clasificadores de este tipo han de resolverse algunas cuestiones previas, entre las que destacan:

¿Cómo se realiza la clasificación?

Podemos asignarle a un caso la clase del caso almacenado más similar (1-NN) o utilizar los grados de similaridad con distintos casos almacenados a la hora de realizar la predicción (como en el método k-NN).

¿Qué casos deben almacenarse?

Lo ideal sería almacenar aquellos casos típicos que recojan toda la información relevante necesaria para poder realizar una buena clasificación. Almacenar todos los casos conocidos haría muy ineficiente el funcionamiento del clasificador.

Los métodos de edición y condensado se utilizan para mejorar el rendimiento de este tipo de clasificadores. Los métodos de edición (como la edición de Wilson o el Multiedit) intentan eliminar los patrones mal etiquetados que puedan aparecer cerca de las fronteras de decisión. Por su parte, los métodos de condensado (como el algoritmo de Hart) procuran reducir el número de muestras del conjunto de entrenamiento sin que esto afecte a la calidad del clasificador construido.

Para reducir la complejidad computacional del problema se pueden emplear métodos de condensado o, simplemente, utilizar algoritmos optimizados como el de Fukunaga y Narendra para la obtención del vecino más cercano.

¿Cómo se mide la similaridad entre distintos casos?

Cuando los atributos son numéricos, se suele calcular la similaridad entre casos utilizando alguna métrica de distancia (que es una medida de disimilaridad), como la distancia euclídea o la distancia de Mahalanobis. Por ejemplo, se puede utilizar la raíz cuadrada de las suma de los cuadrados de las diferencias de los valores de los atributos (usando factores de escala para que la influencia de todos atributos sea similar). Cuando los atributos son discretos, establecer una medida de similaridad es bastante más problemático.

Además, si hay atributos irrelevantes, se corre el riesgo de considerar muy diferentes casos que sólo difieren en los valores que toman atributos irrelevantes para la clasificación.