Advanced models for nearest neighbor classification based on soft computing techniques

Resum

En los últimos años, se ha producido un gran incremento en la cantidad de datos que se deben procesar en aplicaciones en industria, medicina, economa y muchas otras áreas. Los investigadores y profesionales de muchas áreas están encontrando una necesidad creciente de nuevos desarrollos para recolectar, analizar y entender la información que se almacena continuamente en grandes bases de datos. La gestión y el análisis de esta cantidad de datos está por encima de las capacidades humanas y, por tanto, es necesario confiar en procedimientos automáticos para adquirir conocimientos valiosos, normalmente ocultos en esta avalancha de datos contemporánea. Por ello, el análisis de datos y la extracción de conocimiento útil se ha convertido en una tarea obligada - y en un difícil desafo - para muchos procesos de investigación y de negocio en la actualidad. Este proceso, conocido formalmente como Descubrimiento de Conocimiento en Bases de Datos (DCBD) comprende la tarea de obtener nuevo conocimiento a partir de grandes cantidades de datos. Estos nuevos fragmentos de conocimiento deben ser útiles y válidos, y deben tener sentido para el problema específico abordado. El proceso de DCDB se define generalmente como una sucesión de cinco etapas: * Selección de los datos sobre los que se aplicará el proceso de DCDB. * Preprocesamiento de los datos, incluyendo varias fases de limpieza y reducción para facilitar el desarrollo de las etapas subsecuentes. * Transformación de los datos en una representación estructurada; una representación del conocimiento del problema almacenado en los datos iniciales tan precisa como sea posible. * Construcción de nuevos patrones de conocimiento, a partir del análisis de la representación construida en el paso anterior. * Visualización de los datos, describiendo y comprendiendo los patrones obtenidos, de forma que puedan ser útiles para los usuarios. Siguiendo estas etapas, el proceso de DCDB incluye un gran número de técnicas y metodologías de las ciencias de la computación y la inteligencia artificial, para abordar numerosas tareas en cada paso. Sus etapas centrales también son definidas mediante el término minería de datos . La minería de datos es la disciplina centrada en la identificación de patrones y la predicción de relaciones entre los datos. Normalmente, sus técnicas se pueden clasificar como descriptivas (cuando son aplicadas a descubrir patrones interesantes entre los datos) o predictivas (cuando se predice el comportamiento de un modelo a través del análisis de los datos disponibles). Los procesos descriptivos y predictivos de la minera de datos son conducidos mediante algoritmos de aprendizaje automático, introducidos como mecanismos capaces de inducir conocimiento a partir de datos. Dicha inducción de conocimiento es deseable en problemas que no dispongan de una solución algorítmica eficiente, definidos vagamente, o especificados de forma informal. El uso de algoritmos de aprendizaje automático presenta dos vertientes: Pueden ser empleados simplemente como cajas negras, obteniéndose como resultado tan solo las salidas de los modelos. Sin embargo, algunos algoritmos pueden ser empleados como herramientas de representación de conocimiento, construyendo una estructura simbólica de conocimiento dispuesta a ser útil desde el punto de vista de la funcionalidad, pero también desde la perspectiva de la interpretabilidad. Dependiendo de sus objetivos, los algoritmos de aprendizaje automático pueden ser clasificados en dos áreas diferentes: * Aprendizaje supervisado: Son algoritmos centrados en emplear un conjunto de ejemplos etiquetados, describiendo información de varias variables de entrada, para predecir el valor de varias variables de salida. La categoras más comunes de algoritmos de aprendizaje supervisado son clasificación (donde la variable a predecir es discreta; por ejemplo rojo, verde, azul) y regresión (donde la variable a predecir es continua; por ejemplo: temperatura, peso ... ). * Aprendizaje no supervisado: Son algoritmos centrados en buscar nuevos patrones y relaciones en datos no etiquetados. La categoras más comunes de algoritmos de aprendizaje no supervisado son agrupamiento (el proceso de separar datos en varios grupos, manteniendo ejemplos de los mismos grupos tan similares entre sí como sea posible) y asociación (la identificación de relaciones en datos transaccionales). Los métodos de clasificación se pueden definir como técnicas que permiten aprender como categorizar elementos dentro de varias clases predefinidas. Un clasificador recibe un conjunto de datos como entrada, definido como conjunto de entrenamiento, y aprende un modelo de clasificación con él. En el proceso de validación del clasificador, se emplea un conjunto adicional de ejemplos, no contemplados durante el proceso de aprendizaje (el conjunto de test) para comprobar la precisión del clasificador. Generalmente, existen cinco maneras de medir el rendimiento de un clasificador: * Precisión: Confianza del clasificador, normalmente estimada como el porcentaje de ejemplos de test correctamente clasificados sobre el total. * Eficiencia: Tiempo consumido por el clasificador a la hora de clasificar un ejemplo de test. * Interpretabilidad: Claridad y credibilidad, desde el punto de vista humano, del modelo de clasificación. Cuanto más alta sea la interpretabilidad del modelo producido, mayor cantidad de conocimiento podrá ser extraída de él. * Velocidad de aprendizaje: Tiempo requerido por el algoritmo de aprendizaje automático para construir el modelo de clasificación. * Robustez: Número mínimo de ejemplos necesarios para obtener un modelo de clasificación preciso y fiable. En la literatura existen muchas propuestas diferentes para la realización de tareas de clasificación, incluyendo técnicas estadísticas, funciones discriminantes, redes neuronales, árboles de decisión, máquinas de vectores soporte y muchas otras. Entre ellas, existe una subclase de algoritmos que merece ser destacada por su habilidad única de realizar el proceso de aprendizaje directamente a partir de los ejemplos incluidos en el conjunto de entrenamiento: los algoritmos de aprendizaje basados en instancias. El clasificador del vecino más cercano es el algoritmo basado en instancias más conocido. Es un método no paramétrico de clasificación de patrones. Introducido por Fix y Hodges en 1951, el clasificador del vecino más cercano adquirió una popularidad considerable tras 1967, cuando varias de sus propiedades formales fueron descritas por Cover y Hart. El trabajo de Cover fue la piedra angular de una materia que ahora se ha convertido en un vivo campo de investigación para muchos investigadores de las áreas de reconocimiento de patrones y aprendizaje automático: el estudio y desarrollo de uno de los diez algoritmos más importantes en minería de datos. El clasificador del vecino más cercano es también un importante ejemplo de algoritmos de aprendizaje perezoso. Los algoritmos de aprendizaje perezoso son técnicas que, a diferencia del resto de técnicas de aprendizaje automático, no construyen un clasificador durante su fase de entrenamiento. Pueden ser definidos mediante tres propiedades: * Retrasan el procesamiento de los datos de entrenamiento hasta la fase de test. Por tanto, en los modelos de aprendizaje perezoso puro no hay fase de entrenamiento. * Su salida es obtenida como una combinación de los datos obtenidos. Por eso, a pesar de ausencia de un modelo, los datos de entrenamiento siguen siendo un elemento clave en el rendimiento de los algoritmos de aprendizaje perezoso. * La información obtenida al procesar la salida se descarta. Los algoritmos de aprendizaje perezoso puro no aprenden nada de pasos previos del proceso de clasificación. Como algoritmo de aprendizaje perezoso, el clasificador del vecino más cercano ha heredado muchos rasgos beneficiosos, incluyendo su relativa simplicidad, su adaptabilidad a diferentes problemas generales, su flexibilidad a la hora de ser optimizado, por ejemplo, mediante la optimización de su función de similaridad, la no necesidad de un proceso de entrenamiento y la capacidad de poder incorporar nuevo conocimiento al clasificador de forma sencilla (este paso, inmediato en el caso del clasificador del vecino más cercano, normalmente implica la reconstrucción de un nuevo modelo para la mayora de métodos de aprendizaje automático). Pese a todo, el clasificador del vecino más cercano también sufre debido a varios problemas: * Es computacionalmente costoso en la fase de test, dado que debe analizar el conjunto de entrenamiento completo cada vez que una nueva instancia es clasificada. * En su definición original, no es capaz de procesar datos nominales. Además, tampoco puede manejar valores perdidos (información incompleta en los datos de entrenamiento). * No dispone de capacidades de interpretabilidad, dado que no hay un modelo para explicar cómo se ha realizado la clasificación. * No es tolerante al ruido. Los ejemplos ruidosos (incorrectos) pueden afectar al comportamiento del clasificador si hay muchas instancias incorrectas en las proximidades de la instancia de test. * Es muy sensible con respecto a la medida de similaridad escogida para discriminar entre las instancias. * Se ve afectado por la presencia de atributos irrelevantes describiendo los datos. * Con la mayora de las medidas de similaridad comunes, se ve afectado por la, así llamada, maldición de la dimensionalidad, lo que significa que el clasificador del vecino más cercano no mide de forma correcta la similaridad entre las instancias cuando la dimensionalidad de los datos crece demasiado (es decir, cuando el número de atributos describiendo los datos es demasiado grande). En las últimas décadas se han desarrollado muchas propuestas para abordar estos problemas. Un número destacable de ellas están basadas en técnicas de Computación Flexible, incorporando el uso de la computación evolutiva, el razonamiento aproximando, los conjuntos difusos y otras técnicas en la mejora del clasificador del vecino más cercano. La presente tesis de desarrolla siguiendo este camino. Se diseñarán modelos avanzados para clasificación del vecino más cercano, basado en técnicas de Computación Flexible. Un número destacable de ellas están basadas en técnicas de preprocesamiento y reducción de datos, trabajando sobre los datos de entrenamiento en lugar de simplemente modificar el clasificador del vecino más cercano. Algoritmos evolutivos, conjuntos rugosos difusos y conjuntos difusos seran incorporados como herramientas útiles a la hora de definir estas técnicas para la mejora del rendimiento del clasificador, en el sentido de incrementar la precisión de la clasificación y de mejorar su eficiencia en la fase de test.