Universidad de Jaen Departamento de Informática Modelos h́ıbridos de aprendizaje basados en instancias y reglas para Clasificación Monotónica Tesis Doctoral Javier Garćıa Fernández Jaén, Diciembre de 2016 Universidad de Jaén Modelos h́ıbridos de aprendizaje basados en instancias y reglas para Clasificación Monotónica MEMORIA QUE PRESENTA Javier Garćıa Fernández PARA OPTAR AL GRADO DE DOCTOR EN INFORMÁTICA Diciembre de 2016 DIRECTORES José Ramón Cano de Amo y Salvador Garćıa López Departamento de Informática La memoria titulada “Modelos h́ıbridos de aprendizaje basados en ins- tancias y reglas de Clasificación Monotónica”, que presenta D. Javier Garćıa Fernández para optar al grado de doctor, ha sido realizada dentro del programa de doctorado “Tecnoloǵıas de la Información y la Comunicación ” del Departa- mento de Informática de la Universidad de Jaén bajo la dirección de los doctores D. José Ramón Cano de Amo y D. Salvador Garćıa López. Jaén, Diciembre de 2016 El Doctorando Los Directores Fdo: Javier Garćıa Fernández Fdo: J.R. Cano de Amo y S. Garćıa López Agradecimientos GRACIAS A TODOS Índice Introducción 1 A Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 B Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 C Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1. Conceptos Teóricos y Antecedentes 9 1.1. Descubrimiento de Conocimiento en Bases de Datos . . . . . . . . 9 1.2. Mineŕıa de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3. Aprendizaje Supervisado . . . . . . . . . . . . . . . . . . . . . . . . 18 1.4. El problema de la clasificación. . . . . . . . . . . . . . . . . . . . . 20 1.4.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.4.2. Evaluación de clasificadores . . . . . . . . . . . . . . . . . 22 1.5. Clasificación Monotónica . . . . . . . . . . . . . . . . . . . . . . . 23 1.5.1. Concepto de restricción monotónica . . . . . . . . . . . . . 24 1.5.2. Criterios de Evaluación . . . . . . . . . . . . . . . . . . . . 26 1.5.3. Clasificadores monotónicos: Taxonomı́a . . . . . . . . . . . 27 1.5.4. Clasificadores monotónicos relevantes . . . . . . . . . . . . 31 1.5.4.1. Ordered Learning Model (OLM [BD92]) . . . . . . 32 1.5.4.2. Ordinal Stochastic Dominance Learner (OSDL [LBCV08]) . . . . . . . . . . . . . . . . . . . . . . 33 vii viii ÍNDICE 1.5.4.3. MID ([BD95]) . . . . . . . . . . . . . . . . . . . . 37 1.5.4.4. Monotonic k- Nearest Neighbor Classifier [DF08] . 39 1.6. Aprendizaje mediante ejemplos anidados generalizados . . . . . . . 42 1.6.1. Coincidencia de puntos y clasificación . . . . . . . . . . . . 43 1.6.2. Propuesta Clásicas . . . . . . . . . . . . . . . . . . . . . . . 44 1.6.2.1. BNGE: Batch Nested Generalized Exemplar . . . 44 1.6.2.2. RISE: Unificando la Inducción basada en Instan- cias y Reglas . . . . . . . . . . . . . . . . . . . . . 45 2. Discusión de los Resultados 47 2.1. MoNGEL: Aprendizaje Monotónico basado en Ejemplos Anidados Generalizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2. Selección de Hiperrectángulos para Clasificación Monotónica me- diante el uso de Algoritmos Evolutivos . . . . . . . . . . . . . . . . 48 3. Publicaciones 49 3.1. MoNGEL: Monotonic Nested Generalized Exemplar Learning . . . 49 3.2. Hyperrectangles Selection for Monotonic Classification by Using Evolutionary Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 62 4. Conclusiones y Trabajos Futuros 81 4.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.2. Trabajos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.3. Publicaciones Adicionales . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.1. A Nearest Hyperrectangle Monotonic Learning Method . . 84 4.3.2. Hyperrectangles Selection for Monotonic Classification by Using Evolutionary Algorithms . . . . . . . . . . . . . . . . 85 Bibliograf́ıa 87 Índice de figuras 1. Etapas en el proceso de KDD . . . . . . . . . . . . . . . . . . . . . 2 1.1. Taxonomı́a de técnicas de mineŕıa de datos. . . . . . . . . . . . . . 13 1.2. Aprendizaje supervisado. . . . . . . . . . . . . . . . . . . . . . . . 19 1.3. Terminoloǵıa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.4. Construcción del modelo. . . . . . . . . . . . . . . . . . . . . . . . 22 1.5. Taxonomı́a de los Clasificadores Monotónicos. . . . . . . . . . . . . 28 1.6. Dominancia estocástica. . . . . . . . . . . . . . . . . . . . . . . . . 35 1.7. Ejemplos de árboles de decisión no monotónicos. . . . . . . . . . . 37 1.8. Ejemplo de MGV. . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.9. Red de transporte sobre un MGV. . . . . . . . . . . . . . . . . . . 41 1.10. Diagramas de Voronoi del vecino más cercano. . . . . . . . . . . . 42 ix Introducción El presente caṕıtulo constituye una introducción a la memoria de tesis doctoral titulada: Modelos h́ıbridos de aprendizaje basados en instancias y reglas para Clasificación Monotónica. El caṕıtulo comienza con una breve introducción al área de investigación en la que se centra esta memoria, y la motivación para la investigación realizada. A continuación, se exponen los objetivos fijados para llevar a cabo dicha investigación, seguidos de la estructura que se seguirá en el resto de la memoria. A Motivación Es conocido que los datos por śı solos no producen beneficio directo. Su ver- dadero valor radica en la posibilidad de extraer información útil para la toma de decisiones o la exploración y comprensión del fenómeno que produjo los da- tos. Tradicionalmente en la mayoŕıa de los dominios este análisis de datos se haćıa mediante un proceso semiautomático: uno o más analistas con conocimien- to de los datos y con la ayuda de técnicas estad́ısticas proporcionaban resúmenes, generaban informes, validaban modelos, etc. Por ello, surge la necesidad de plan- tear metodoloǵıas para el análisis inteligente de datos que permitan descubrir un conocimiento útil a partir de estos. Este es el concepto de proceso de KDD (des- cubrimiento de conocimiento en bases de datos; en inglés, Knowledge Discovery in Databases), que puede ser definido como el proceso no trivial de identificar patrones en los datos con las caracteŕısticas siguientes: válidos, novedosos, útiles y comprensibles. El proceso de KDD, reflejado en la Figura 1, es un conjunto de pasos interactivos e iterativos, entre los que se incluye el preprocesado de los 1 2 Introducción datos para corregir los posibles datos erróneos, incompletos o inconsistentes, la reducción del número de registros o caracteŕısticas para encontrar los más repre- sentativos, la búsqueda de patrones de interés con una representación particular y la interpretación de estos patrones incluso de una forma visual. El descubri- miento de conocimiento en bases de datos combina las técnicas tradicionales de extracción de conocimiento con numerosos recursos desarrollados en el área de la inteligencia artificial. En estas aplicaciones, el término Mineŕıa de Datos (MD) es el que ha tenido más aceptación, siendo utilizado con frecuencia para reflejar directamente todo el proceso de KDD [HK11, Agg15]. Relacionado con MD, el término aprendizaje automático (Machine Learning, ML, en inglés) sigue sien- do muy extendido entre la comunidad cient́ıfica en lo que se refiere al diseño de nuevos algoritmos [SSBD14]. Figura 1: Etapas en el proceso de KDD El uso de algoritmos de aprendizaje automático presenta dos vertientes: pue- den 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 interpretabi- lidad. Dependiendo de sus objetivos, los algoritmos de aprendizaje automático pueden ser clasificados en dos áreas diferentes: A Motivación 3 Aprendizaje Supervisado: son algoritmos centrados en emplear un con- junto de ejemplos etiquetados, describiendo información de varias variables de entrada, para predecir el valor de varias variables de salida. La cate- goŕıas más comunes de algoritmos de aprendizaje supervisado son clasifi- cació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, ..., etc). Aprendizaje No Supervisado: son algoritmos centrados en buscar nue- vos patrones y relaciones en datos no etiquetados. La categoŕıas más co- munes 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 śı 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 con- templados durante el proceso de aprendizaje (el conjunto de test) para comprobar la precisión del clasificador. 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, destacan dos subclases de algoritmos: Los algoritmos de aprendizaje basados en instancias [Aha97]. El clasificador del vecino más cercano es el algoritmo basado en instancias más conocido. Es también un importante ejemplo dentro de la familia de algoritmos de aprendizaje perezoso. Éstos son técnicas que, a diferencia del resto de técni- cas de aprendizaje automático, no construyen un clasificador durante su fase de entrenamiento. Este tipo de clasificadores han heredado muchos rasgos beneficiosos, incluyendo su relativa simplicidad, su adaptabilidad a diferentes problemas generales, su flexibilidad a la hora de ser optimizado, la no necesidad de un proceso de entrenamiento y la capacidad de poder incorporar nuevo conocimiento al clasificador de forma sencilla. 4 Introducción Los algoritmos de aprendizaje basados en inducción de reglas [F9̈9]. Son sistemas de aprendizaje que representan un paradigma transparente, fácil- mente comprensible y aplicable y más genérico que los árboles de decisión, puesto que muchas de las técnicas utilizadas en los sistemas de aprendizaje de reglas fueron adaptadas directamente de los árboles de decisión. A di- ferencia del grupo anterior, los algoritmos construyen modelos sencillos de interpretar y rápidos de usar en la fase de predicción. La construcción del modelo es el paso más tedioso de este tipo de algoritmos y su optimización para adaptarlo a problemas complejos supone un proceso muy costoso. En la literatura especializada, se ha desarrollado la teoŕıa de aprendizaje lla- mada aprendizaje de ejemplos anidados generalizados, donde el aprendizaje se lleva a cabo por objetos en un espacio Eucĺıdeo de n dimensiones En, como hi- perrectángulos. Los hiperrectángulos pueden anidarse uno dentro de otro hasta una profundidad arbitraria. Al contrario que la mayoŕıa de procesos de generaliza- ción, que sustituyen fórmulas simbólicas por fórmulas más generales, el proceso de generalización de estos algoritmos modifican los hiperrectángulos aumentándolos y cambiando su volumen de acuerdo al problema concreto. Los ejes de estos hi- perrectángulos se definen por las variables de cada ejemplo, siendo independiente del tipo de variable, numérica o categórica. La base de este tipo de modelos es una hibridación de los algoritmos de apren- dizaje basados en instancias con los algoritmos de inducción de reglas. De esta manera, los ejemplos se almacenan y se usan estrictamente como puntos en En, y las reglas se corresponden con hiperrectángulos, o ejemplos generalizados, que dis- ponen de un determinado volumen y se pueden interpretar como un sub-espacio eucĺıdeo que tiene asociado una categoŕıa de predicción. Entre las ventajas de estos modelos, destacan la simplicidad de los algoritmos de generación de mo- delos y la representación de modelos, aunando las ventajas relativas a la buena capacidad y adaptación predictiva de clasificadores basados en instancias con la posibilidad de interpretación de hiperrectángulos en forma de reglas. También cabe mencionar la posibilidad del aprendizaje anidado de generalización con ex- cepciones, si tenemos en cuenta que los hiperrectángulos se solapan o incluyen unos dentro de otros y los más pequeños son vistos como excepciones dentro de una regla más genérica. Finalmente, la flexibilidad es otra propiedad que se puede mencionar, puesto que este tipo de modelos permite la inclusión de pesos, cambios de funciones de distancias en las variables, etc. El razonamiento ordinal se refiere a una categoŕıa importante en los problemas A Motivación 5 de predicción. En éstos, tanto los atributos de entrada como las clases toman valores ordinales dentro de dominios determinados [KS13]. La clasificación de ejemplos en categoŕıas ordinales es un problema popular que ha ido atrayendo la atención de los profesionales en mineŕıa de datos durante estos últimos años. En la literatura, han aparecido multitud de términos en relación a este problema, tales como, clasificación ordinal, regresión ordinal o ranking labelling, pero todos comparten una propiedad en común: el atributo de salida o clase es ordinal. La restricción de monotonicidad entre atributos de entrada y la clase viene dada por una relación de ordenación parcial que establece el orden entre ejemplos. La restricción de monotonicidad obliga a que el orden también se mantenga en la clase y se trata de un aspecto común en muchas áreas de aplicación. Sin embargo, los modelos obtenidos por las técnicas de aprendizaje automático no garantizan el cumplimiento de esta restricción. Esto ha motivado el desarrollo de algoritmos que sean capaces de manejar dichas restricciones, como árboles de decisión. La clasificación con restricciones monotónicas, también conocida como clasificación monotónica, [BDSP89], es un problema con una restricción clara sobre la monotońıa de los datos: un valor mayor en un atributo, mientras los demás se mantienen, no debe asignarse a una clase menor [KS13]. Los árboles de decisión [HCZ+12a, MP15a], la inducción de reglas y el aprendizaje basado en instancias constituyen tres de las técnicas más prometedoras para resolver la clasificación monotónica. A pesar de los numerosos modelos y enfoques propuestos por diferentes autores para dar soporte a problemas de clasificación monotónica, éstos se han centrado normalmente en técnicas basados en modelos aislados y no h́ıbridos. Además, la aplicación de técnicas en problemas con ı́ndole real donde los ejemplos pueden presentar violaciones monotónicas apenas se ha explorado. Los resultados de in- vestigación obtenidos en este ámbito hasta la fecha no son suficientes, ya que surgen nuevas dificultades y retos que requieren un estudio más profundo de los datos y la aplicación de algoritmos de optimización complejos y adaptativos a cada problema. Algunos de estos retos y dificultades se describen a continuación: Implantación de otros modelos complejos en clasificación monotónica, que aún no se han usado en este campo y que reúnan las caracteŕısticas ventajo- sas que no se están explotando en modelos monotónicos. Este es el caso de los algoritmos basados en ejemplos anidados generalizados, que requieren de una nueva formalización de la teoŕıa para ser aplicados a este campo y un algoritmo sencillo que construya modelos monotónicos con este tipo de 6 Introducción representaciones. Necesidad de obtener modelos predictivos monotónicos sobre bases de datos reales, donde cabe la posibilidad que los ejemplos presenten violaciones monotónicas. Este campo apenas ha sido explorado y está estrechamente ligado a las aplicaciones que disponemos en la realidad. Los algoritmos deben ser capaces de trabajar con datos imperfectos y obtener modelos cuyas predicciones finales sean lo más monotónicas posibles. Alta complejidad en la obtención de modelos fiables en clasificación mo- notónica en entornos reales. Cuando los datos son imperfectos, el espacio de soluciones posibles se hace más complejo y los modelos finales pueden dejar de ser fiables sin una buena heuŕıstica de búsqueda. Los algoritmos evolutivos son técnicas inspiradas por la computación natural y diseñadas para abordar problemas de búsqueda y optimización. Estos algoritmos re- presentan un conjunto de soluciones y las evolucionan utilizando diferentes operadores que combinan y distribuyen las soluciones. La buena adapta- bilidad de los algoritmos evolutivos en tareas de aprendizaje nos permi- tirá abordar problemas complejos en clasificación monotónica en entornos reales. La constante evolución y retos actuales encontrados en los problemas de cla- sificación monotónica, algunos de los cuales acabamos de describir, condujeron durante el comienzo de esta investigación a formular la siguiente hipótesis de partida: Los algoritmos de clasificación monotónica existentes no están preparados pa- ra abordar problemas más complejos y que presentan imperfecciones en su estado original, representadas como violaciones en la monotonicidad en los datos. Por esta razón, es necesario tratar la clasificación monotónica con técnicas h́ıbridas y algoritmos de optimización avanzados para obtener modelos fiables y sencillos. B Objetivos Teniendo en cuenta los retos actuales en el campo de la clasificación mo- notónica mediante técnicas de inducción de reglas y aprendizaje basado en ins- tancias, el propósito inicial de esta investigación es el desarrollo de modelos h́ıbri- C Resumen 7 dos instancias-reglas para clasificación monotónica basados en el paradigma de ejemplos anidados generalizados o aprendizaje basado en hiperrectángulos, ca- racterizados por la alta flexibilidad en la construcción de fronteras separatorias de clases y por permitir cierta interpretabilidad en la lectura de las reglas que inducen [WD95, Dom96]. Estos nuevos algoritmos incorporarán técnicas de soft computing, como los algoritmos evolutivos, para la optimización de la precisión, simplificación y reducción de predicciones no monotónicas de los modelos resul- tantes. En base al propósito genérico del desarrollo de algoritmos basados en ejem- plos anidados generalizados para clasificación monotónica, nos planteamos los siguientes objetivos: 1. Realización de un estudio de las propuestas en la literatura en el campo de las técnicas de clasificación basados en generalización de instancias, induc- ción de reglas clásicas y aprendizaje basado en instancias para clasificación monotónica. Además, se plantea el estudio del uso de técnicas de soft com- puting, como los algoritmos evolutivos, para optimizar diferentes aspectos durante la obtención de modelos predictivos por técnicas de clasificación monotónicas. 2. Formalización de la teoŕıa de aprendizaje basada en ejemplos anidados ge- neralizados al problema de la clasificación monotónica y desarrollo de un primer algoritmo voraz que la utilice para obtener modelos h́ıbridos ba- sados en reglas-instancias, o hiperrectángulos, que produzcan predicciones monotónicas precisas. El algoritmo deberá utilizarse para aprender sobre bases de datos completamente monotónicas. 3. Desarrollo de una técnica basada en algoritmos evolutivos que persigue la selección de los mejores hiperrectángulos para optimizar los modelos de acuerdo a su precisión, simplicidad y ausencia de violaciones de monotonici- dad en las predicciones. El uso de algoritmos evolutivos nos permite abordar problemas reales donde no todos los ejemplos cumplen las expectativas de monotonicidad debido al ruido inherente de los datos. C Estructura 8 Introducción Para alcanzar los objetivos que acabamos de plantear, y según lo estable- cido en el art́ıculo 23, punto 3, de la normativa vigente para los Estudios de Doctorado en la Universidad de Jaén (Programa RD. 1393/2007), esta memoria de investigación será presentada como un conjunto de art́ıculos publicados por el doctorando. Dichas publicaciones constituyen el núcleo de la tesis, y corresponden a dos art́ıculos cient́ıficos publicados y/o aceptados en Revistas Internacionales indexadas por la base de datos JCR (Journal Citation Reports), producida por ISI (Institute for Scientic Information). Por tanto, la memoria se compone de un total de dos publicaciones, y se estructura en los siguientes caṕıtulos: Caṕıtulo 1: en él se presenta una revisión del proceso de descubrimiento de conocimiento en bases de datos y del problema abordado en la pre- sente memoria sobre la clasificación monotónica, haciendo un repaso de los conceptos básicos y antecedentes sobre problemas de mineŕıa de datos, aprendizaje supervisado y el problema de la clasificación. Para finalizar este caṕıtulo, introduciremos una visión amplia sobre el problema de la clasificación monotónica y una taxonomı́a que revisa y caracteriza un gran número de técnicas existentes en la literatura, haciendo hincapié en cuatro clasificadores monotónicos relevantes. Caṕıtulo 2: este caṕıtulo presenta un resumen de la investigación realizada para alcanzar los objetivos planteados en esta memoria, y muestra una breve discusión de los resultados obtenidos en cada propuesta. Dichas propuestas son desarrolladas en los dos art́ıculos que se encuentran en las Secciones 3.1 y 3.2. Caṕıtulo 3: Este caṕıtulo constituye el núcleo de la tesis doctoral, y contiene las dos publicaciones obtenidas como resultado de esta investigación. Caṕıtulo 4: En este caṕıtulo, se señalan las conclusiones y resultados más relevantes de la investigación realizada, aśı como las futuras ĺıneas de in- vestigación a seguir. La memoria concluye con una recopilación bibliográfica de las contribuciones más destacadas en la materia estudiada. Caṕıtulo 1 Conceptos Teóricos y Antecedentes En este caṕıtulo se revisan los conceptos teóricos y antecedentes fuente de inspiración para comprender la investigación que se presenta en esta memoria. De esta manera, en la Sección 1.1 definimos el proceso de descubrimiento de in- formación en bases de datos, y describimos las etapas que lo componen. En la Sección 1.2 introducimos la fase de mineŕıa de datos y en la Sección 1.3 describi- mos brevemente el aprendizaje supervisado, dentro del cual dedicamos especial atención a la clasificación. En la última sección explicamos con más detalle la clasificación monotónica. 1.1. Descubrimiento de Conocimiento en Bases de Datos El término descubrimiento de conocimiento en bases de datos (Knowledge Discovery in Databases, también conocido como KDD) empezó a utilizarse en 1989 para referirse al proceso complejo de búsqueda de conocimiento en bases de datos, y para enfatizar la aplicación a alto nivel de métodos espećıficos de extracción de modelos e información a partir de los datos. Fayyad et al. en [FPSS96] define el KDD como el proceso no trivial de iden- 9 10 Caṕıtulo 1. Conceptos Teóricos y Antecedentes tificar patrones válidos, novedosos, potencialmente útiles y, en última instancia, comprensibles a partir de los datos. En esta definición se resumen cuáles deben ser las propiedades deseables del conocimiento extráıdo: Válido: hace referencia a que los patrones deben seguir siendo precisos para datos nuevos (con un cierto grado de certidumbre), y no sólo para aquellos que han sido usados en su obtención. Novedoso: que aporta algo desconocido para el sistema y preferiblemente para el usuario. Potencialmente útil: la información debe conducir a acciones que reporten algún tipo de beneficio para el usuario. Comprensible: la extracción de patrones no comprensibles dificulta o impo- sibilita su interpretación, revisión, validación y uso en la toma de decisiones. De hecho, una información incomprensible no proporciona conocimiento (al menos, desde el punto de vista de su utilidad). Como se deduce de la anterior definición, el KDD es un proceso complejo que incluye no sólo la obtención de los modelos o patrones, sino también la evaluación y posible interpretación de los mismos. Los principales pasos dentro del proceso de KDD pueden son los siguientes [FPSS96]: 1. Especificación y comprensión del problema: en esta fase se diseña y organi- za el dominio de aplicación, el conocimiento previo relevante obtenido por los expertos y los objetivos finales perseguidos por el usuario final. Para ello debemos comprender los datos seleccionados y el conocimiento exper- to asociado. Este paso requiere cierta dependencia usuario/analista, pues intervienen factores como: los cuellos de botella del dominio, saber qué par- tes son susceptibles de un procesado automático y cuáles no, cuáles son los objetivos, los criterios de rendimiento exigibles, para qué se usarán los resultados que se obtengan, compromisos entre simplicidad y precisión del conocimiento extráıdo, etc. 2. Preprocesamiento de los datos [GLH15]: en esta etapa se incluyen tareas como la limpieza de los datos, integración de los datos, eliminación de ruido, estrategias para manejar valores perdidos, normalización de los datos, etc. 1.2. Mineŕıa de datos 11 Aśı mismo, se pueden incluir actividades como la búsqueda de caracteŕısti- cas útiles de los datos según sea el objetivo final, la reducción del número de variables y la proyección de los datos sobre espacios de búsqueda en los que sea más fácil encontrar una solución. Este es un paso cŕıtico dentro del proceso global, que requiere un buen conocimiento del problema y una buena intuición, y que, con frecuencia, marca la diferencia entre el éxito o fracaso de la mineŕıa de datos. 3. Mineŕıa de datos: en esta etapa se pueden seguir diferentes estrategias pa- ra obtener modelos, según el interés se centre en clasificación, regresión, agrupamiento de conceptos (clustering), detección de desviaciones, etc. En el libro de Han y Kamber ([HK11]), puede verse con detalle los diferentes métodos de mineŕıa de datos. En este paso se realiza la búsqueda de co- nocimiento con una determinada representación del mismo. El éxito de la mineŕıa de datos depende en gran parte de la correcta realización de los pasos previos. 4. Interpretación y evaluación: en este paso del proceso se realiza la interpre- tación del conocimiento extráıdo, con posibilidad de iterar de nuevo desde el primer paso. La obtención de resultados aceptables dependerá de factores como: definición de medidas de interés del conocimiento (de tipo estad́ıstico, en función de su sencillez, etc.) que permitan filtrarlo de forma automáti- ca, existencia de técnicas de visualización para facilitar la valoración de los resultados o búsqueda manual de conocimiento útil entre los resultados obtenidos, consolidación del conocimiento descubierto, incorporándolo al sistema, o simplemente documentándolo y enviándolo a la parte interesada. Este paso incluye la revisión y resolución de posibles inconsistencias con otro conocimiento extráıdo previamente. 1.2. Mineŕıa de datos La mineŕıa de datos se aplica en multitud de áreas, entre ellas se encuentran: aplicaciones empresariales, industriales, toma de decisiones en banca, seguros, finanzas, marketing, control de calidad, retención de clientes, predicción, poĺıticas de acción, sanidad, aplicaciones en investigación cient́ıfica, análisis y gestión de mercados, análisis de riesgo en banca y seguros, mineŕıa de datos en industria, diagnóstico en medicina, etc. 12 Caṕıtulo 1. Conceptos Teóricos y Antecedentes La fase de mineŕıa de datos es la más caracteŕıstica del KDD y, por esta razón, muchas veces se utiliza esta fase para nombrar todo el proceso. Consiste en la ex- tracción automatizada o conveniente de los patrones que presentan conocimiento impĺıcitamente almacenado o capturados en una gran base de datos, almacenes de datos, la web, otros repositorios de información masivos, o flujos de datos. Como un campo multidisciplinario, la mineŕıa de datos se basa en el trabajo de multitud de áreas incluyendo la estad́ıstica, aprendizaje automático, recono- cimiento de patrones, tecnoloǵıa de bases de datos, recuperación de información, redes de ordenadores, sistemas basados en el conocimiento, inteligencia artificial, computación de alto rendimiento, y visualización de datos. La mineŕıa de datos surgió durante la década de 1980, e hizo grandes avances durante la década de 1990, y continúa floreciendo en el nuevo milenio. La mineŕıa de datos es un conjunto de técnicas de análisis de datos que per- miten [WF05]: Extraer patrones, tendencias y regularidades para describir y comprender mejor los datos. Extraer patrones y tendencias para predecir comportamientos futuros. Debido al gran volumen de datos este análisis no puede ser manual (ni incluso facilitado por herramientas de almacenes de datos y OLAP) sino que debe ser (semi-)automático [OQR07]. Dicho análisis se realiza construyendo un modelo basado en los datos recopilados para este efecto. El modelo es una descripción de los patrones y relaciones entre los datos que pueden usarse para hacer prediccio- nes, para entender mejor los datos o para explicar situaciones pasadas. Para ello es necesario tomar una serie de decisiones antes de empezar el proceso: Determinar qué tipo de tarea de mineŕıa es la más apropiada. Por ejemplo, podŕıamos usar la clasificación para predecir en una entidad bancaria los clientes que dejarán de serlo. Elegir el tipo de modelo. Por ejemplo, para una tarea de clasificación podŕıamos usar un árbol de decisión, porque queremos obtener un modelo interpretable de manera sencilla por cualquier usuario. Elegir el algoritmo de mineŕıa que resuelva la tarea y obtenga el tipo de modelo que estamos buscando. Esta elección es pertinente porque existen muchos métodos para construir los modelos. Por ejemplo, para crear árboles 1.2. Mineŕıa de datos 13 de decisión para clasificación podŕıamos usar CART o C4.5, entre otros. En lo que resta de esta sección, describimos las tareas y modelos más utilizados, aśı como algunos conceptos relacionados con la construcción del modelo. Dentro de la mineŕıa de datos hemos de distinguir tipos de tareas [HK11, WF05], cada una de las cuales puede considerarse como un tipo de problema a ser resuelto por un algoritmo de mineŕıa de datos. Esto significa que cada tarea tiene sus propios requisitos, y que el tipo de información obtenida con una tarea puede diferir mucho de la ofrece otra. Las distintas tareas pueden ser predictivas, descriptivas o de verificación. En la Figura 1.1 se muestra una taxonomı́a de los diferentes algoritmos de mineŕıa de datos, según sea su finalidad: ����������� � ��� ����� ��� ���� �� ��� ����� �� ��� ��� ���� ��� � ���� ��� � �� � � �� � �� �� �� �� � � �� �� �� �� �� �� �� � � �� �� �� �� �� � � �� � � �� � � � �� �� � � � � �� �� � � �� �� � � �� � � �� �� � � � � � �� �� � � �� �� � � � � � � �� �� �� �� �� � � �� �� � �� �� � ! � � �� �� � "� � � �� �# �� � �� �� Figura 1.1: Taxonomı́a de técnicas de mineŕıa de datos. Entre las tareas predictivas encontramos la clasificación y la regresión, mien- tras que el agrupamiento (clustering), las reglas de asociación, las reglas de aso- ciación secuenciales y las correlaciones son tareas descriptivas. Veamos en mayor detalle todas ellas: 14 Caṕıtulo 1. Conceptos Teóricos y Antecedentes La clasificación es quizá la tarea más utilizada. En ella, cada instancia (o registro de la base de datos) pertenece a una clase, la cual se indica mediante el valor de un atributo que llamamos clase de la instancia. Este atributo puede tomar diferentes valores discretos, cada uno de los cuales corresponde a una clase. El resto de los atributos de la instancia se utilizan para predecir la clase. El objetivo es predecir la clase de nuevas instancias. Más concretamente, el objetivo del algoritmo es maximizar la razón de precisión de la clasificación de nuevas instancias, la cual se calcula como el cociente entre las predicciones correctas y el número total de predicciones (correctas e incorrectas). La regresión es también una tarea predictiva que consiste en aprender una función real que asigna a cada instancia un valor numérico. Ésta es la prin- cipal diferencia respecto a la clasificación; el valor a predecir es numérico. El objetivo en este caso es minimizar el error (generalmente el error cuadrático medio) entre el valor predicho y el valor real. El agrupamiento (clustering) es la tarea descriptiva por excelencia y con- siste en obtener grupos a partir de los datos. Hablamos de grupos y no de clases, porque, a diferencia de la clasificación, en lugar de analizar datos etiquetados con una clase, los analiza para generar esta etiqueta. Los datos son agrupados basándose en el principio de maximizar la similitud entre los elementos de un grupo minimizando la similitud entre los distintos grupos. Es decir, se forman grupos tales que los objetos de un mismo grupo son muy similares entre śı y, al mismo tiempo, son muy diferentes a los objetos de otro grupo. Al agrupamiento también se le denomina segmentación, ya que parte o segmenta los datos en grupos que pueden ser o no disjuntos. El agrupamiento está muy relacionado con la sumarización, que algunos autores consideran una tarea en śı misma, en la que cada grupo formado se considera como un resumen de los elementos que lo forman para aśı describir de una manera concisa los datos. Las reglas de asociación son también una tarea descriptivaque tiene como objetivo identificar relaciones no expĺıcitas entre atributos categóricos. Pue- den ser de muchas formas, aunque la formulación más común es del estilo si el atributo X toma el valor d entonces el atributo Y toma el valor b. Las reglas de asociación no implican una relación causa-efecto, es decir, puede no existir una causa para que los datos estén asociados. Este tipo de tarea se utiliza frecuentemente en el análisis de la cesta de la compra. La idea 1.2. Mineŕıa de datos 15 es identificar productos que son frecuentemente comprados juntos, informa- ción esta que puede usarse para ajustar los inventarios, para la organización f́ısica del almacén o en campañas publicitarias. Dado que la mineŕıa de datos es un campo muy interdisciplinar, existen di- ferentes paradigmas detrás de las técnicas utilizadas para esta fase: técnicas de inferencia estad́ıstica, árboles de decisión, redes neuronales, inducción de reglas, aprendizaje basado en instancias, algoritmos genéticos, aprendizaje bayesiano, programación lógica inductiva y varios tipos de métodos basados en núcleos, entre otros. Cada uno de estos paradigmas incluye diferentes algoritmos y variaciones de los mismos, aśı como otro tipo de restricciones que hacen que la efectividad del algoritmo dependa del dominio de aplicación, no existiendo lo que podŕıamos llamar el método universal aplicable a todo tipo de aplicación. Existen muchos conceptos estad́ısticos que son la base de muchas técnicas de mineŕıa de datos. Ejemplo de ello es la regresión lineal, un método simple pero frecuentemente utilizado para la tarea de regresión. Las técnicas estad́ısticas no son sólo útiles para regresión, sino que se utilizan también para discriminación (clasificación o agrupamiento). La inferencia de funciones discriminantes que se- paran clases o grupos, también se puede realizar de manera paramétrica o no paramétrica. El método más conocido es el análisis de discriminantes lineales de Fisher. Algunas de las técnicas de discriminantes no paramétricos tienen una relación muy estrecha con los métodos basados en núcleo, de los cuales las máquinas de soporte vectorial son su ejemplo más representativo, en el que se busca un discriminante lineal que maximice la distancia a los ejemplos fronterizos de los distintos grupos o clases. En otras ocasiones, deseamos calcular, para una instancia dada sin clasificar, cuál es la probabilidad de que se le asigne cada una de las clases, y seleccionar la de mayor probabilidad. Ésta es la idea que subyace en los métodos bayesianos. Uno de los métodos más utilizados es el Naive Bayes, que se basa en la regla de Bayes y que asume la independencia de los atributos dada la clase. Este método funciona bien con bases de datos reales, sobre todo cuando se combina con otros procedimientos de selección de atributos que sirven para eliminar la redundancia. Los árboles de decisión son una serie de condiciones organizadas en forma jerárquica, a modo de árbol. Son muy útiles para encontrar estructuras en es- pacios de alta dimensionalidad y en problemas que mezclen datos categóricos y numéricos. Esta técnica se usa en tareas de clasificación, agrupamiento y regre- 16 Caṕıtulo 1. Conceptos Teóricos y Antecedentes sión. Los árboles de decisión usados para predecir variables categóricas reciben el nombre de árboles de clasificación, ya que distribuyen las instancias en clases. Cuando los árboles de decisión se usan para predecir variables continuas se llaman árboles de regresión. Los árboles de decisión pueden considerase una forma de aprendizaje de reglas, ya que cada rama del árbol puede interpretarse como una regla, donde los nodos internos en el camino desde la ráız a las hojas definen los términos de la conjunción que constituye el antecedente de la regla, y la clase asignada en la hoja es el consecuente. En general, la inducción de reglas es un conjunto de métodos para derivar un conjunto de reglas comprensibles de la forma: SI cond1 Y cond2 Y......Y condn ENTONCES pred. El antecedente de la regla (la parte SI) contiene una conjunción de n condicio- nes sobre los valores de los atributos independientes, mientras que el consecuente de la regla (la parte ENTONCES) contiene una predicción sobre el valor de un atributo objetivo. Aunque los árboles de decisión pueden también producir un conjunto de reglas (tal y como hemos visto anteriormente), los métodos de inducción de reglas son diferentes ya que: las reglas son independientes y no tienen por qué formar un árbol. las reglas generadas pueden no cubrir todas las situaciones posibles. las reglas pueden entrar en conflicto en sus predicciones; en este caso, es necesario elegir qué regla se debe seguir. Un método para resolver los con- flictos consiste en asignar un valor de confianza a las reglas y usar la que tenga mayor confianza. Algunos métodos de obtención de reglas, en especial las reglas de asociación, se basan en el concepto de conjuntos de items frecuentes (frequent itemsets) y utilizan técnicas de conteo y soporte mı́nimo para obtener las reglas. Las redes neuronales artificiales (Artificial Neural Networks o AANNs) son todo un paradigma de computación muy potente que permite modelizar proble- mas complejos en los que puede haber interacciones no lineales entre variables. 1.2. Mineŕıa de datos 17 Como los árboles de decisión, las redes neuronales pueden usarse en problemas de clasificación, de regresión y de agrupamiento. Las redes neuronales trabajan directamente con datos numéricos, para usarlas con datos nominales éstos deben transformarse en números primero. Una red neuronal puede verse como un grafo dirigido con muchos nodos (ele- mentos del proceso) y arcos entre ellos (sus interconexiones). Cada uno de estos elementos funciona independientemente de los demás, usando datos locales (la entrada y la salida del nodo) para dirigir su procesamiento. En el aprendizaje basado en instancias o casos (Instance Based Learning o IBL), las instancias se almacenan en memoria, de tal forma que cuando llega una nueva instancia cuyo valor es desconocido se intenta relacionar ésta con las instancias almacenadas (cuya clase o valor es conocida) buscando las que más se parecen, con el objetivo de usar los valores de estas instancias similares para estimar los valores a obtener de la nueva instancia en cuestión. Por lo tanto, más que intentar crear reglas, se trabaja directamente con los ejemplos. Todo el trabajo en el aprendizaje basado en instancias se hace cuando llega una instancia a clasificar y no cuando se procesa el conjunto de entrenamiento. En este sentido se trata de un método retardado o perezoso, ya que retrasa el trabajo real tanto como sea posible, a diferencia de los otros métodos vistos hasta el momento que tienen un comportamiento anticipativo o voraz, produciendo generalizaciones en cuanto reciben los datos de entrenamiento. En el aprendizaje basado en instancias, cada nueva instancia se compara con las existentes usando una métrica de distancia, y la instancia más próxima se usa para asignar su clase a la instancia nueva. La variante más sencilla de este método de clasificación es conocido como el vecino más próximo (nearest neighbor). Otra variante, conocida como el método de los k vecinos más próximos (k nearest neighbors), usa los k vecinos más próximos, en cuyo caso la clase mayoritaria de estos k vecinos se asigna a la nueva instancia. El aprendizaje basado en instancias es muy útil para trabajar sobre tipos de datos no estándar, como los textos o multimedia. El único requerimiento para incluir un tipo de datos es la existencia de una métrica apropiada de distancia para formalizar el concepto de similitud. 18 Caṕıtulo 1. Conceptos Teóricos y Antecedentes 1.3. Aprendizaje Supervisado En el campo de la mineŕıa de datos, los métodos de predicción son comúnmen- te referidos como aprendizaje supervisado. Los métodos de aprendizaje supervi- sados se emplean para conseguir el descubrimiento de las relaciones entre las variables de entrada y del atributo objetivo (en la mayoŕıa de ocasiones habla- remos de clase). Las relaciones buscadas son representadas en una estructura llamada modelo. Generalmente, un modelo describe y explica experiencias, que están ocultas en los datos, y que pueden ser usadas en la predicción del valor del atributo objetivo, cuando los valores de entrada son conocidos [GLH15]. El aprendizaje supervisado está presente en muchos dominios de aplicación, como las finanzas, medicina e ingenieŕıa. En un escenario t́ıpico de aprendizaje supervisado, partimos de un conjunto de entrenamiento con el objetivo de obtener un modelo que pueda ser usado para predecir ejemplos desconocidos. Este con- junto de entrenamiento puede ser descrito de diferentes formas. La más común es un conjunto de instancias, que es básicamente una colección de tuplas que puede contener duplicados. Cada tupla es descrita por un vector con valores de atributos. Cada atributo tiene un dominio asociado de valores que son conocidos con anterioridad a la tarea de aprendizaje. Los atributos pueden ser: nominales o numéricos (enteros o reales). Los atributos nominales tienen una cardinalidad finita, mientras los dominios de atributos numéricos están delimitados por unos limites inferior y superior. El espacio de instancias (el conjunto de posibles ejem- plos) es definido como un producto cartesiano de todos los atributos de entrada. El espacio de instancias universal es definido como un producto cartesiano de todos los dominios de los atributos de entrada y el dominio del atributo objetivo. Los dos problemas clásicos que pertenecen a la categoŕıa del aprendizaje su- pervisado son la clasificación y la regresión. En la clasificación, el dominio del atributo objetivo es finito y categórico. Esto es, hay un número finito de clases o categoŕıas para predecir una muestra y estos son conocidos por el algoritmo de aprendizaje. Un clasificador puede asignar una clase a un ejemplo no conocido cuanto este ha sido entrenado a través de un conjunto de entrenamiento. La na- turaleza de la clasificación es discriminar unos ejemplos de otros, consiguiendo como uso principal una predicción fiable. De esta manera tenemos modelos ajus- tados a datos pasados. Si suponemos que el futuro es similar al pasado, entonces asumimos que podemos hacer predicciones correctas para nuevas instancias. Sin embargo, cuando el atributo objetivo esta formado por infinitos valores, como es el caso de la predicción de un número real dentro de un cierto intervalo, habla- 1.3. Aprendizaje Supervisado 19 mos de problemas de regresión. Aqúı, la propuesta del aprendizaje supervisado es ajustar un modelo para aprender el atributo objetivo de salida como función de los atributos de entrada. Obviamente, el problema de regresión presenta más dificultades que el problema de clasificación y tanto los requerimientos de compu- tación como la complejidad del modelo son mayores. Dentro de la regresión, otro tipo de aprendizaje es el análisis de las series temporales, que tiene que ver con hacer predicciones a lo largo del tiempo. Aplicaciones t́ıpicas incluyen el análisis de las cotizaciones, el mercado de valores y la previsión de ventas. El aprendizaje supervisado ([HK11]) a partir de un conjunto de ejemplos en la forma de pares (entradas, salidas), encuentra las reglas o funciones que mejor modelan la relación entre las entradas y las salidas (a modo de ejemplos, ver Figura 1.2). ��������� � �� �� � �� � Figura 1.2: Aprendizaje supervisado. 20 Caṕıtulo 1. Conceptos Teóricos y Antecedentes En un problema de aprendizaje supervisado tenemos los siguientes elementos: Variable nominal o categórica: valores discretos. Variable numérica: valores no discretos. Variable de salida: También suele llamarse clase. Clase true/false: ejemplo positivo/negativo. Clase discreta/numérica: Problema de clasificación/regresión La Figura 1.3 muestra un ejemplo de la terminoloǵıa que estamos utilizando. Figura 1.3: Terminoloǵıa. 1.4. El problema de la clasificación. La clasificación es una de las tareas de mineŕıa de datos más conocidas. Con- siste en predecir una determinada clase (categoŕıa) para un objeto. En la tarea de clasificación, dados un conjunto de ejemplos ya clasificados, se pretende cons- truir un modelo que permita clasificar nuevos casos. Es un tipo de aprendizaje supervisado donde se conoce la clase verdadera de cada uno de los ejemplos que 1.4. El problema de la clasificación. 21 se utilizan para construir el clasificador. Algunas aplicaciones t́ıpicas son: apro- bación de créditos ([CS13, SAS15]), marketing directo ([HAE13]), detección de fraudes ([BH02]), diagnóstico médico ([AA16, SASS11]), etc. 1.4.1. Definición En un problema de clasificación ([HK11]) tenemos un objeto Xi, que se describe a través de un conjunto de caracteŕısticas (m variables o atributos): Xi1, Xi2, ..., Xim, al cual le va a corresponder una etiqueta o clase entre los posi- bles valores del conjunto C = {c1, c2, ..., ct}, nominales o numéricos, y notaremos como Clase(Xi) el valor que le corresponde a Xi. A partir de ahora llamaremos instancia o ejemplo al par Ei = (Xi, Clase(Xi)). El objetivo de la tarea de la clasificación es encontrar una función f : A1 × A2 × ... × Am → C donde Ai es el dominio donde toma valores el atributo i. Las caracteŕısticas o variables elegidas dependen del problema de clasificación. Hay que diferenciar dos etapas en la tarea de la clasificación: 1. Construcción del modelo: Este asocia a cada nueva instancia o ejemplo con una determinada categoŕıa. Cada ejemplo (tupla) se sabe que pertenece a una clase (etiqueta del atributo clase). Se utiliza un conjunto de ejemplos, conjunto de entrenamiento (training set) para la construcción del modelo. El modelo obtenido se representa como un conjunto de reglas de clasificación, árboles de decisión, fórmula matemática, etc. Esta etapa se puede observar en la Figura 1.4. 2. Utilización del modelo: Tras la construcción del modelo se pueden reali- zar clasificaciones futuras y también hacer una estimación de la precisión del modelo. Para ello se utilizan un conjunto de ejemplos distintos de los utilizados para su construcción llamados conjunto de prueba (test set). Si el conjunto de test no fuese independiente del de entrenamiento ocurre un proceso de sobreajuste (overfitting). Para cada ejemplo de test se compara la clase determinada por el modelo con la clase real (conocida). El ratio de precisión es el porcentaje de ejemplos de test que el modelo clasifica correctamente. 22 Caṕıtulo 1. Conceptos Teóricos y Antecedentes Figura 1.4: Construcción del modelo. 1.4.2. Evaluación de clasificadores En la evaluación de los clasificadores hay tres aspectos que se deben estudiar [HK11]: en primer lugar los criterios para evaluar el clasificador, en segundo lugar las técnicas de validación de estos criterios y en tercer lugar las técnicas para poder comparar varios modelos construidos sobre el mismo problema para poder seleccionar el más apropiado y/o preciso. A continuación vamos a definir algunos conceptos necesarios para la evaluación de un clasificador: Matriz de Confusión : Dado un problema de clasificación con t clases, una matriz de confusión es una matriz t × t en la que una entrada ci,j indica el número de ejemplos que se han asignado a la clase cj , cuando la clase correcta es ci. Tasa de acierto: s = ∑ i ci,i n (La suma del numero de elemento clasificado 1.5. Clasificación Monotónica 23 correctamente entre el total de elementos). Tasa de error : ε = 1− s. Tras ver los criterios para valorar la bondad de un clasificador cabe hacerse la siguiente pregunta: ¿en realidad es honesta la estimación de la bondad del cla- sificador construido?. Utilizar como bondad la tasa de acierto sobre el conjunto de entrenamiento no es realista. El porcentaje obtenido suele ser demasiado opti- mista debido a que el modelo estará sobre ajustado a los datos utilizados durante el proceso de aprendizaje. Una de las técnicas de validación de clasificadores más utilizadas y reconocidas en la literatura es la validación cruzada, que consiste en: 1. Dividir el conjunto de datos en k-subconjuntos (folds), S1, . . . , Sk de igual tamaño. 2. Aprender k clasificadores utilizando en cada uno de ellos un conjunto de entrenamiento distinto. Se valida con su conjunto de test correspondiente: Entrenamiento = S1∪S2∪...∪Si−1∪Si+1∪...∪Sk Test = Si 3. Devolver como tasa de acierto (error) el promedio obtenido en las k- iteraciones 1.5. Clasificación Monotónica La clasificación monotónica tiene sus oŕıgenes en los problemas de clasifica- ción ordinales [GPOSM+16]. Por ejemplo, un empleado puede ser descrito como excelente, bueno o malo y un bono se puede calificar como AAA, AA, A, A-, etc. Al igual que una escala numérica, una escala ordinal tiene un orden, pero a dife- rencia de ella no posee una noción precisa de distancia. No podemos decir que AA está más cerca de AAA de lo que está de A, ni a la inversa. A este respecto una escala ordinal es similar a una nominal. Los problemas de clasificación ordinales son importantes, ya que son muy comunes en diferente ámbitos: Vida diaria [BDST09]. Por ejemplo, la selección de la mejor ruta para tra- bajar, dónde comprar, qué producto comprar, y dónde vivir, etc. 24 Caṕıtulo 1. Conceptos Teóricos y Antecedentes En los negocios ([Gam98]), en tareas como la selección y promoción de los empleados, la determinación de la calificación crediticia, calificación de los bonos, el rendimiento económico de los páıses, sectores y empresas, y la contratación de seguros, etc. Entorno académico ([BD92]), tales como Rankings de Manuscritos, evalua- ción de profesores, admisión de alumnos, y las decisiones sobre las becas para los estudiantes. Problemas ordinales se han investigado en la literatura en disciplinas cient́ıfi- cas tales como la toma de decisiones en psicoloǵıa y medicina ([DAB97, Roy00]), el derecho ([Kar91]) y la estad́ıstica ([BDST09]). En la última década, un número creciente de publicaciones han mostrado un progreso en el aprendizaje artificial de conceptos ordinales. Modelos de aprendizaje automático, tales como árboles de decisión, redes neuronales y máquinas de soporte vectorial han sido adaptados para la clasificación ordinal. Cada modelo tiene diferentes supuestos. Por ejemplo, una de las principales diferencias entre los diversos enfoques hacia el aprendizaje de conceptos ordinales es la manera en la que se trata la monotońıa. Algunos clasificadores necesitan ejemplos monótonos para aprender, mientras que otros son capaces de hacerlo a partir de ejemplos no monótonos también. En las siguientes secciones vamos a explicar brevemente el concepto de res- tricción monotónica, para pasar a ver algunas de las propuestas clásicas para abordar la clasificación bajo este paradigma. 1.5.1. Concepto de restricción monotónica En primer lugar definiremos el concepto de relación de orden para pasar a continuación a estudiar el concepto de monotońıa [BD95]. Relación de orden [Men64, Bir67, Rom08] Sea A un conjunto dado no vaćıo y < una relación binaria definida en A, se dice que es una relación de orden, si cumple las siguientes propiedades: Reflexividad: todo elemento de A está relacionado consigo mismo. Es decir, ∀x ∈ A : x xh,j ∀j = 1, .....,m Xi � Xh si xi,j > xh,j ó xi,j = xh,i∀j = 1, ...,m Xi ≺ Xh si xi,j < xh,j ∀j = 1, ...,m Xi � Xh si xi,j < xh,j ó xi,j = xh,j∀j = 1, ...,m (1.3) Relación monotónica Sean (Xi, Clase(Xi)) y (Xh, Clase(Xh)) dos pares (instancia,clase) se dice que son antimonotónicos si: Xi � Xh y Clase(Xi) < Clase(Xh) ó Xi � Xh y Clase(Xi) > Clase(Xh) ó Xi = Xh y Clase(Xi) 6= Clase(Xh) (1.4) Se dice que dos pares (Xi, Clase(Xi)) y (Xh, Clase(Xh)) son monótonicos entre śı, si no cumplen con alguna de las condiciones establecidas en 1.4. 26 Caṕıtulo 1. Conceptos Teóricos y Antecedentes 1.5.2. Criterios de Evaluación Los clasificadores ordinales no monotónicos pueden ser evaluados usando di- ferentes métricas [BES09, CS11, JS11, CHSG14]. Las dos métricas más comunes son la precisión y el error medio absoluto, las cuales son utilizadas de forma general en clasificación. El primero de ellos se define como: precisión = 1 n n∑ i=1 [Clase(Xi) 6= Predicción(Xi)] (1.5) donde la Clase(Xi) y la Predicción(Xi) son respectivamente el valor real de la clase y el valor predicho de la clase de la instancia, y n el número total de instancias. La precisión toma valores dentro del intervalo [0,1]. Esta medida no tiene en cuenta la magnitud del error, en cambio, el error medio absoluto (Mean Absolute Error, MAE [BES09]) incluye alguna información del orden. Esta métrica es el valor medio de las desviaciones absolutas entre el valor real de la clase y el predicho asociados a la clase de la instancia Xi: MAE = 1 n n∑ i=1 [O(Clase(Xi))−O(Predicción(Xi))] (1.6) donde MAE toma valores en el intervalo [0,Q-1] y Q es el cardinal del conjunto de los valores de la clase. Para evaluar espećıficamente la monotonicidad de los clasificadores monotóni- cos disponemos de varias métricas. La primera de ellas es el ı́ndice de No Mono- tonicidad (NMI), definida por Ben-David en [BD95] como el cociente del número de violaciones de las restricciones de monotonicidad dividido por el número total de pares de instancias. Si el conjunto de datos D tiene n instancias, el número total de pares será n2 − n. La fórmula para calcular este ı́ndice será: NMI(D) = ∑n i=1 ∑n j=1,j 6=iMij n2 − n (1.7) donde M es una matrix binaria y Mij es igual a 1 si el par formado por Xi y Xj es no monotónico y 0 en caso contrario. Para añadir información en los árboles de decisión sobre la monotonicidad se añade a la entroṕıa (E-score) una puntuación de la ambigüedad del orden 1.5. Clasificación Monotónica 27 (order-ambiguity-score [BD95]) que se calcula la siguiente manera: A = { 0 si NMI=0 −(log2NMI)−1 en otro caso (1.8) Índice de No Monotonicidad 1 (NMI1 [MDP13]): Se define como: NMI1 = 1 n(n− 1) ∑ X∈D NClash(X) (1.9) donde NClash(X) es el número de instancias del conjunto de datos D que no cumplen las restricciones de monotonicidad con respecto a X. Índice de No Monotonicidad 2 (NMI2 [MDP13]): Se define como: NMI2 = 1 n ∑ X∈D Clash(X) (1.10) donde Clash(X) = 1 si el ejemplo X es no monótono con algún otro ejemplo o instancia de D. 1.5.3. Clasificadores monotónicos: Taxonomı́a En la actualidad son cinco las familias más importantes de clasificadores mo- notónicos. Dicha clasificación ha sido realizada basándonos en sus diferentes en- foques y modelos resultantes (ver Figura 1.5). Basados en instancias: Son los más conocidos y los pioneros. En esta sec- ción encontramos aquellos métodos basados en criterios de vecindad para efectuar sus clasificaciones. En la subsección 1.5.4 se explicaran con mayor profundidad. • Ordered Learning Model (OLM [BD92]). • Ordinal Stochastic Dominance Learner (OSDL [LBCV08]). • Monotonic k-Nearest Neighbor (MkNN [DF08]). Árboles de decisión y Clasificadores basados en reglas: en este caso, se obtienen modelos de segmentación recursivos o bien conjuntos de reglas independientes. Los métodos que podemos agrupar en este ámbito son: 28 Caṕıtulo 1. Conceptos Teóricos y Antecedentes ���������� ��� � ����� � ����� ����� ���������� � � ��������������� ������������������� �������������� �� ������ ��� ����� ��� �� � � � � � � � � � � � � � �� � � � � � � � � � � � � � � � � � �� � � � � �� �� � � � �� � � � � � � � � � � �� �� � � ! � " � � ! � " � " #" � �� � � � � " " $# ! � � � � � " � % � � " " $#�� % � � %% �� % ! & $ �' � � � & � $ � " �� � � ( � % % �� % � � � � � & �" � � ) � ���� * " � ' #" � � � �� � � + � � � � �� � � � � � � � � � � � � Figura 1.5: Taxonomı́a de los Clasificadores Monotónicos. • MID [BD95]. Es una extensión del algoritmo ID3 ([Qui93]) propuesta por Ben David (será explicado con más detalle en la subsección 1.5.4). • P-DT, QP-DT [KM99]. Makino y otros propusieron un árbol de deci- sión monótono (P-DT), y un quasi monótono (QP-DT) como extensión del algoritmo ID3 en un problema de clasificación para dos clases. En ambos casos, empiezan con un conjunto de datos monótono, siendo éste un requerimiento inicial necesario, sin embargo en el caso de QP- DT la monotonicidad solo se garantiza en el conjunto de entrenamiento mientras que en P-DT el árbol debe de ser monotónico también. • MDT [LYW03]. El objetivo de este algoritmo es predecir el orden impĺıcito en relación a la comparación de parejas en la clasificación original. • REMT [HCZ+12b]. En esta propuesta se emplea una medida llamada ranking de información mutua, que es una formalización ordinal de la información mutua de Shannon. Dicha medida es sensible a la monoto- 1.5. Clasificación Monotónica 29 nicidad y robusta frente a datos ruidosos. Con ella, se pueden construir árboles clasificadores binarios garantizando una forma débil de mono- tonicidad, en caso de que el conjunto de partida fuera monotónicamen- te consistente. El algoritmo REMT propuesto demostró en los estudios realizados un comportamiento aceptable comparado con clasificadores monótonos y no monótonos. • RDMT(H) [MP15b]. El algoritmo se basa en un un árbol clasificador binario parametrizado por una medida de discriminación H empleada para segmentación, aśı como tres parámetros más para hacer un po- dado previo. De esta manera, el algoritmo garantiza una forma débil de monotonicidad del árbol resultante. • MGain [ZZZW15]. Se trata de una propuesta basada también en árbo- les clasificadores binarios. Para ello los autores proponen un ı́ndice de consistencia monotónica de un punto de corte con respecto al conjunto de datos, pero manteniendo las prestaciones predictivas del árbol de clasificación clásico. • cANTMinerPB [BO16]. Frente a los casos anteriores donde los mo- delos resultantes eran árboles de decisión, en este caso se obtiene un conjunto de reglas. Los autores proponen una extensión de un sistema de aprendizaje de clasificadores basados en reglas, donde la extracción de los modelos se lleva a cabo mediante optimización con colonias de hormigas. Multiclasificadores: aqúı encontramos algoritmos basados en técnicas de boosting combinando reglas de decisión, técnicas de bagging sobre reglas y árboles de decisión o bien métodos que fusionan modelos. A continuación presentamos los que se encuentran presentes en la literatura: • Técnicas de Boosting. ◦ LPRules [KS09]. El algoritmo consiste en tres etapas, de forma que en la primera de ellas se descompone un problema multiclase en una secuencia de subproblemas binarios. A continuación, los datos de cada subproblema binario son monotonizados emplean- do para ello una aproximación no paramétrica que explota la clase de todas las funciones monótonas. Finalmente, se genera un mul- ticlasificador de reglas usando el método LPBoost. 30 Caṕıtulo 1. Conceptos Teóricos y Antecedentes ◦ MORE [DKS09]. Este método emplea un esquema de modelado aditivo por etapas hacia adelante para generar un multiclasifica- dor de reglas de decisión para problemas binarios, basado en un mecanismo de boosting. ◦ MonRF [GHG15]. El objetivo de los autores en este caso fué el proponer un mecanismo multiclasificador de poda basado en el grado de monotonicidad de los árboles resultantes obtenidos me- diante un proceso de Random Forest. ◦ VC-DRSA Ordinal Random Forest [WZZZ15]. Este algoritmo tie- ne como pilar constitutivo la aproximación de consistencia en la dominancia de variables basada en conjuntos aproximados. Cons- ta de tres fases, donde en la primera se realiza un muestreo ordinal aleatorio basado en la aproximación anteriormente citada. En la segunda etapa se construyen árboles de decisión en paralelo em- pleando las instancias anteriormente elegidas y en la última etapa, se genera un conjunto de reglas mediante un algoritmo ordinal de Random Forest. Para ello los autores emplean MapReduce y Ha- doop. ◦ Monotonic AdaBoost [GHG16]. Este algoritmo considera árboles de decisión monotónicos combinados en un esquema AdaBoost, empleando un multiclasificador de poda basado en el grado de monotonicidad. • Técnicas de Bagging. ◦ VC-bagging [BSS10]. Los clasificadores que componen el multicla- sificador de bagging están formados por reglas de decisión induci- das mediante objetos estructurados que emplean la aproximación de consistencia en la dominancia de variables basada en conjuntos aproximados. • Técnicas de Fusión. ◦ FREMT [QXL+15]. Los autores proponen un método para fusio- nar árboles de decisión basado en dos principios: por un lado un mecanismo de reducción de atributos para el aprendizaje de clasifi- cadores basados en preservación de ranking. Como segundo factor clave, se emplea un principio de fusión basado en probabilidad maximal a través de la combinación de clasificadores base. Redes Neuronales: Estas han sido utilizadas en fechas recientes como otro 1.5. Clasificación Monotónica 31 paradigma alternativo para afrontar problemas de clasificación monotóni- cos. De entre algunos de los trabajos realizados en este sentido podemos citar: • Red neuronal parcial monótona MIN-MAX [DV10]. Los autores al comparar esta con otras redes, indican que la propuesta mejora sus prestaciones. Lo justifican dado que presenta como ventaja el consi- derar todas las variables disponibles con las restricciones apropiadas durante la fase de entrenamiento y test, sin la necesidad de eliminar o forzar la monotonicidad en variables no monotónicas. • ORNN(ELM) [FRC14]. Este método extiende modelos existentes de aprendizaje automático extremo al ámbito de la regresión ordinal. Métodos Hı́bridos: En este grupo situamos a métodos que combinan dife- rentes paradigmas. Entre ellos podemos citar: • Mongel [GFA+15]. Se trata de una de las propuestas que conforman esta tesis doctoral en la cual se combina aprendizaje basado en instan- cias con inducción de reglas. Dicho método será extensamente descrito en el Caṕıtulo 3, Sección 3.1. • EHSMC-CHC [GAA+16]. Segunda propuesta original de esta tesis doctoral donde se emplean algoritmos evolutivos para la selección de hiperrectángulos, teniendo como objetivo abordar problemas de clasi- ficación monotónica en entornos reales donde existen imperfecciones en los datos. El algoritmo será descrito en el Caṕıtulo 3, Sección 3.2. En la siguiente sección se describirán algunos de los métodos de clasificación monotónica más ampliamente utilizados y reconocidos en la literatura. 1.5.4. Clasificadores monotónicos relevantes A continuación vamos a describir con más detalle tres métodos de aprendizaje basados en instancias: OLM, OSDL y MkNN, y un método basado en árboles de decisión: MID. Estos métodos son a nuestro juicio los más importantes en el ámbito de la clasificación monotónica y por ello los hemos usado para compararlos con los métodos propuestos en nuestro estudio. 32 Caṕıtulo 1. Conceptos Teóricos y Antecedentes 1.5.4.1. Ordered Learning Model (OLM [BD92]) Es un algoritmo simple que aprende las relaciones ordinales monótonas de los datos mediante la eliminación de inconsistencias de los pares que violan las restricciones de monotonicidad. El algoritmo está basado en instancias, lo cual significa que almacena los ejemplares de aprendizaje en memoria, y es capaz de deducir las etiquetas de clase de ejemplares no visibles por alguna técnica de extrapolación generalmente local. Los ejemplares de aprendizaje se almacenan como un conjunto de reglas. En un principio, el conjunto de reglas está vaćıo. Después, durante el apren- dizaje, cada ejemplar se comprueba con cada una de las reglas del conjunto de reglas. Si el ejemplar es antimonótono con una regla, el ejemplar o la regla es seleccionado al azar, mientras que la otra se desecha. Si el ejemplar está selec- cionado se debe comprobar de nuevo con cada una de las reglas del conjunto. Si pasa esta prueba de consistencia se añade al conjunto de reglas como una regla más. De este modo, el conjunto es siempre coherente. A este conjunto de ahora en adelante lo notaremos como CISE (Consistent and Irredudant Examples). La clasificación se hace de una manera similar al aprendizaje, comparando el ejemplar a clasificar con las reglas del conjunto de reglas. Las reglas se com- prueban en el orden descendiente de los valores de atributo de decisión (es decir, clases). Al ejemplar se le asigna la clase indicada por la primera regla que lo cubre. Esto es equivalente a la asignación de la clase máxima i sugerido por las reglas que cubren al ejemplar. Si no hay una regla en el conjunto de reglas que cubra el ejemplar, dos enfoques son posibles. El primer enfoque y más simple consiste en asignarle al ejemplar la peor clase. En el segundo enfoque, la clase es asignada buscando la regla más cercana al ejemplar de acuerdo con la distancia euclidiana. OLM produce un conjunto más pequeño de reglas durante el aprendizaje [BD95]. La principal debilidad de este modelo se encuentra en el hecho de que no hace ninguna comprobación de la precisión durante el aprendizaje. Otro in- conveniente es que el conjunto de reglas depende del orden en que los ejemplares se procesan. Por otra lado, la clasificación según el vecino más cercano de los ejemplares que no estén cubiertos puede conducir a clasificaciones no monótonas. A continuación presentamos el pseudocódigo del algoritmo en su fase de apren- dizaje (ver Algoritmo 1) y en su fase de clasificación (ver Algoritmo 2). Al co- mienzo, CISE está vaćıo. Cada ejemplo se compara con todas las reglas que hay 1.5. Clasificación Monotónica 33 actualmente en CISE para determinar si se añade o no. Algoritmo 1 Fase de Aprendizaje del OLM 1: Fase 1: 2: Ordenamos los ejemplares en orden descendente de la clase de salida; 3: while haya ejemplos sin comprobar do 4: Seleccionamos un nuevo ejemplo, Ei = (Xi, Clase(Xi)) 5: Marcamos cada ejemplo Eh tq Xh = Xi 6: Remplazamos todos los ejemplos marcados con E = (Xi, Clase(Xh)) 7: end while 8: Fase 2: 9: CISE = Ø 10: while haya ejemplos sin comprobar do 11: Dado un nuevo ejemplar , Ei = (Xi, Clase(Xi)) 12: ymax = min{class(x′)|x′ ∈ T ∧ x ≤ x′} 13: if CISE = � then 14: CISE = CISE ∪ Ei 15: else 16: for para todas las reglas de CISE do 17: if existe Eh ∈ CISE tal que es redundante o inconsistente con Ei then 18: if Xi ≺ Xh y Ei es consistente y no redundante con CISE then 19: CISE = CISE − {Eh} 20: CISE = CISE ∪ {Ei} 21: else 22: CISE = CISE − {Ei} 23: end if 24: end if 25: end for 26: end if 27: if Eh no ha sido rechazado hasta ahora then 28: CISE = CISE ∪ {Eh} 29: end if 30: end while Tras crear CISE para clasificar se ordenan las reglas obtenidas de forma de- creciente según el valor de su clase. 1.5.4.2. Ordinal Stochastic Dominance Learner (OSDL [LBCV08]) Ofrece una alternativa a OLM, ya que también es un método basado en ins- tancias. Utiliza el concepto de dominancia estocástica ordinal (OSD [CV03]) para resolver la clasificación ordinal con restricciones monotónicas. Vamos a introducir una notación para definir el objetivo de este algoritmo: Y = {Clase(Xh)/Xh ∈ X}, F (Y ) el conjunto de todas las posibles distribuciones de probabilidad sobre Y y E1 la relación de dominancia estocástica de primer orden o débil, que explicaremos posteriormente. El objetivo de este algoritmo es encontrar una función F̄ : X × Y → [0, 1] que cumpla las siguientes condiciones: F̄ es no creciente en el primer argumento. 34 Caṕıtulo 1. Conceptos Teóricos y Antecedentes Algoritmo 2 Fase de Clasificación del OLM 1: while haya ejemplos Eh = (Xh, Clase(Xh)) do 2: Comparamos el ejemplar Eh con la regla actual Ei = (Xi, Clase(Xi)) ∈ CISE 3: if Xh � Xi then 4: Clasificamos Eh como Clase(Xi) 5: else 6: Clasificamos Eh con la media de las clases de los ejemplares más cercanos 7: end if 8: end while F̄ es no decreciente en el segundo argumento. F̄ (·,max(Y )) = 1. F̄ minimiza alguna función de riesgo. Definimos λ̄prob : (X,�X)→ (F (Y ),E1) como λ̄prob(Xh) := f̄xh distribución de probabilidad asociada a la función de distribución F̄xh (Xh, ·). Obtenida esta función de distribución, para cada Xh tenemos una función de distribución F̄ (Xh, · ) y su correspondiente distribución de probabilidad f̄xh . Posteriormente es fácil calcular el valor asociado a la clase de Xh calculando el valor E[f̄xh ] (esperanza de la distribución de probabilidad asociada a Xh). Dominancia Estocástica Este concepto establece una relación de orden en el conjunto de las distri- buciones de probabilidad F (Y ) [CVB03]. Dadas dos instancias Xi y Xh, las dos distribuciones de probabilidad asociadas a estas instancias fxi y fxh decimos que hay una relación estocástica de primer orden (FOSD) entre ellas si (ver Figura 1.6): fxi E1 fxh ⇔ ∀ l ∈ Y F (Xi, l) ≥ F (Xh, l) (1.11) En el algoritmo OSDL se construye dos funciones de comparación Fm y FM : una que se basa en los ejemplares de la mejor clase, entre las que están dominados estocásticamente por una instancia Xi, y la segunda, que se basa en los ejemplares de la peor clase entre los que dominan estocásticamente a Xi. Más precisamente, para una clase dada i: 1.5. Clasificación Monotónica 35 Figura 1.6: Dominancia estocástica. Fm(Xi; l) = min Xh∈(Xi] F̂Xh (l) , FM (Xi; l) = max Xh∈[x) F̂Xh (l) , (1.12) donde (Xi] = {Xh ∈ X/Xh � Xi} es el conjunto de ejemplares dominados por Xi y [Xi) = {Xh ∈ X/Xi � Xh} es el conjunto de ejemplares que dominan a Xi y F̂Xh (l) es el valor de la función de distribución de Xh en la clase l, donde la distribución de probabilidad fXh toma los siguientes valores ∀ l ∈ Y = Clases(X) fXh (l) ≡ P (clase(Xh) = l). Por otra parte, si(Xi] = Ø, entonces Fm(Xi; l) = 1 y si [Xi) = Ø, entonces Fm(Xi; l) = 0. Durante la clasificación, se realiza una interpolación de las funciones de corres- pondencia Fm y FM . Esta interpolación implica un parámetro de escala s ∈ [0; 1]: F̄ (Xi; l) = (1− s)Fm(Xi; l) + s ∗ FM (Xi; l) (1.13) Tal interpolación tiene un inconveniente: para mantener la monotońıa de la clasificación se requiere utilizar el mismo valor fijo de s para todos los ejemplares clasificados. Con el fin de tratar los datos inconsistentes y para superar el pro- blema con el parámetro de escala s una versión equilibrada de OSDL se propone 36 Caṕıtulo 1. Conceptos Teóricos y Antecedentes en [CV03]. Esta versión implica la siguiente interpolación entre las funciones de correspondencia: F̄ (Xi; l) = { (1− s)Fm(Xi; l) + s ∗ FM (Xi; l) si Fm(Xi; l) ≥ FM (Xi; l) (1−s′)Nm(Xi;l)Fm(Xi;l)+s′∗NM (Xi;l)FM (Xi;l) Nm(Xi;l)+NM (Xi;l) en otro caso (1.14) donde s, s′ ∈ [0, 1], Nm(Xi; l) es el número de instancias de (Xi] cuya clase es � l y NM (Xi; l) es el número de instancias de[Xi) cuya clase es � l. Por lo tanto, la versión equilibrada de OSDL introduce ponderación por el número de instan- cias Nm(Xi; l) y NM (Xi; l) que se hace para instancias inconsistentes. Tiene el propósito de reducir la influencia de las instancias inconsistentes en la clasifica- ción. Vistos algunos detalles de cálculo del algoritmo podemos pasar a describir las fases de aprendizaje y clasificación del algoritmo. En la fase de aprendizaje del algoritmo OSDL, se construye el clasificador en dos etapas como puede verse en el Algoritmo 3: 1. Construcción del conjunto de datos y cálculo de la función de distribución discreta estimada. 2. Calculamos el parámetro s determinado por una validación cruzada leave- one-out. En el algoritmo cada vez que hay un ejemplar nuevo (Xh, Clase(Xh)) para clasificar se aplica la función AñadirInstancia (Xh, Clase(Xh)), que añade Xh al conjunto de datos y actualiza la función de distribución discreta estimada F̂Xh . También se utiliza la función EliminarInstancia (Xh, Clase(Xh)) en es- te algoritmo que hace lo contrario que AñadirInstancia. Para terminar con la construcción del clasificador se procede a calcular el valor del parámetro s en el conjunto de valores {0.1; 0.2; ...; 1} que hace mı́nimo el valor de los errores (la diferencia entre la clase real y la clase predicha), utilizando un proceso de validación cruzada. En la fase de clasificación añadimos la instancia, modificamos F̄ (Xi; l) y Fm(Xi; l), para obtener una nueva función de distribución y de- volvemos la media de la distribución de probabilidad. 1.5. Clasificación Monotónica 37 1.5.4.3. MID ([BD95]) Utilizar árboles de decisión basados en teoŕıa de la información que emplean la entroṕıa como criterio de selección de atributos produce árboles de decisión no monotónicos (como se puede observar en la Figura 1.7), que no cumplen con las restricciones de monotońıa. A estos algoritmos se los denomina TDIDT (Top- Down-Induction Decision Trees, TDIDT [Qui93]). Figura 1.7: Ejemplos de árboles de decisión no monotónicos. Los algoritmos TDIDT que usan E-score como métrica de selección de atribu- tos no consideran el orden en los atributos de entrada y de clase. Estos algoritmos no se adaptan del todo a los problemas monotónicos. Sin embargo, los árboles de decisión proporcionan una precisión aceptable. Desafortunadamente estos dos objetivos entran en conflicto. Como solución a este problema Ben-David propu- so la adaptacion del E-score de forma que se tuviera en cuenta el orden de los atributos. A continuación vamos a definir una serie de conceptos que utilizó Ben-David para la construcción de sus árboles de decisión monotónicos, hasta llegar a una métrica que el denomina puntuación de ambigüedad total. Índice no monotónico Es el cociente del número de pares de ramas no monotónicas entre śı del árbol de decisión, dividido entre el número total de pares de la rama del árbol de decisión. Para calcular este ı́ndice, dado un árbol con K ramas, construimos una matriz M de orden K, cuyos elementos mij se definen de la siguiente forma: 38 Caṕıtulo 1. Conceptos Teóricos y Antecedentes mij = { 0 si las ramas i, j no son no monotónicas 1 si las ramas i, j son no monotonicas (1.15) El ı́ndice no monotónico del árbol se calcula como: Ia1,...,ag = ∑k i=1 ∑k i=1mij k2 − k (1.16) Puntuación de ambigüedad del orden Aa1,...,ag = { 0 si Ia1,...,ag = 0 −(log Ia1,...,ag)−1 en otro caso (1.17) Puntuación de ambigüedad total Es la suma de los E− score definida en los árboles obtenidos con el algoritmo ID3 y la puntuación de ambigüedad del orden (1.17): Ta1,...,ag = Ea1,...,ag +Aa1,...,ag (1.18) Esta métrica selecciona aquellos atributos con puntuación total de am- bigüedad más baja. Esta puntuación tiene algunas propiedades deseables para los problemas de monotonicidad ya que considera el error en la predicción y el ı́ndice de no monotonicidad. Su definición no implica la monotonicidad en el proceso de construcción del árbol. En la mayor parte de los casos el ı́ndice no monotonicidad es sustancialmente inferior a 0.50, y en la mayoŕıa de los casos es muy inferior a los valores de E-score. Una forma efectiva de expresar las dependencias entre la entroṕıa y la mo- notonicidad puede ser conseguida introduciendo un parámetro adicional para el cálculo de la ambigüedad total: Ta1,...,ag = Ea1,...,ag +R ∗Aa1,...,ag (1.19) El parámetro R expresa la importancia relativa de la monotońıa con respecto a la precisión en el problema dado. Cuando R = 0, el score del ambigüedad total usa sólo su E-score componente. Si R es un valor muy alto la consideraciones de monotońıa dominan la construcción del árbol de decisión. 1.5. Clasificación Monotónica 39 1.5.4.4. Monotonic k- Nearest Neighbor Classifier [DF08] Este algoritmo de Duivesteijn et al modifica el método clásico de los k-vecinos para su aplicación a la clasificación monotónica. Este método no paramétrico está compuesto de dos fases. En la primera fase, los datos de entrenamiento se hacen monótonos reetiquetando el menor número de casos posibles. Este con- junto de datos reetiquetados puede ser visto como un clasificador monótono con una tasa de error más pequeña en los datos de entrenamiento. En la segunda fase, se utiliza el algoritmo del vecino más cercano modificándolo para predecir las etiquetas de clase de nuevos datos, de tal manera que las restricciones de monotonicidad sean satisfechas. Reetiquetado de los datos Para reetiquetar los datos es necesario construir el grafo de violación de res- tricciones de monotonicidad (MGV). Es un grafo dirigido G = (V,E), donde V = {1, 2, ...., n} y (i, j) ∈ E si Xi ≤ Xj y Clase(Xi) > Clase(Xj). El MGV es un grafo de orden estrictamente parcial. Según se describió en [RDBDM06], el máximo subconjunto independiente (no hay vértices adyacentes) del MGV corresponde al subconjunto de tamaño máximo monótono de los datos. La Figura 1.8 muestra un ejemplo de de MGV. Si reeti- quetamos el complementario de este subconjunto máximo independiente obtenido del MGV, obtendremos con muy pocos cambios un conjunto de datos monótonos. A pesar de que encontrar un conjunto máximo independiente en un grafo arbi- trario es un problema NP-completo, esto no es aśı en grafos comparables (gráfos con orden parcial). Para este tipo de gráfos, un conjunto independiente máximo corresponde a una anticadena máxima en el orden parcial correspondiente. Esta se puede calcular en O(n3) resolviendo un problema de flujo mı́nimo en una red de transporte (problema del viajante) que se construye fácilmente a partir de la gráfica de la comparabilidad. Un ejemplo de red de transporte se puede ver en la Figura 1.9. Como resumen, para reetiquetar los datos se sigue el siguiente proceso: 1. Construir el grafo de violación de restricciones de monotonicidad, G = (V,E). 2. Transformar el grafo en una red de transporte G′ = (V ′, E′). 3. Calculamos el camino de flujo mı́nimo en la red de transporte. 40 Caṕıtulo 1. Conceptos Teóricos y Antecedentes 2 X 1 1 X 2 1 X 3 2 X 4 1 X 7 2 X 5 2 X 6 Figura 1.8: Ejemplo de MGV. 4. Los vértices de este conjunto son los del subconjunto independiente máximo M . 5. Reetiquetamos el resto de los que están en el grafo, R = V/M . Algoritmo del vecino más cercano monotónico Con el fin de satisfacer las restricciones de monotońıa, es evidente que la etiqueta de clase asignada a un nuevo punto de datos X0 se ve limitada a estar en el intervalo [ymin, ymax], donde ymin = max{Clase(X)|(x,Clase(X)) ∈ D ∧X ≤ X0} y ymax = min{Clase(X)|(x,Clase(X)) ∈ D ∧X0 ≤ X} 1.5. Clasificación Monotónica 41 Figura 1.9: Red de transporte sobre un MGV. donde D es el conjunto de datos reetiquetado. La elección de un valor de este intervalo es libre, sin embargo, y por lo tanto, tiene sentido hacer un mayor uso de los datos observados para guiar esta elección. Existen dos variantes en la regla del vecino más próximo estándar: 1. Calculamos los k vecinos más cercanos de X0 en D y predecimos la etiqueta de [ymin, ymax] que se presenta con mayor frecuencia entre esos k-vecinos. Si ninguna de las k etiquetas es permitida, elegimos al azar entre [ymin, ymax]. 2. Calculamos los k vecinos más cercanos de X0 en D con etiqueta en [ymin, ymax] y predecimos la etiqueta por mayoŕıa. Para ilustrar visualmente la diferencia entre el vecino más cercano estándar y monótono, consideramos un pequeño ejemplo. Supongamos que los datos de entrenamiento se componen de los tres puntos trazados en la Figura 1.10 (se muestran Diagramas de Voronoi). Al lado de cada punto de datos, sus coorde- nadas (x1, x2) y clase. Se puede observar la partición del espacio de entrada de acuerdo con el método del vecino más cercano. Es claro que la regla de asignación resultante no es monótona. En la imagen de la derecha se ha dado la regla de asignación para la predicción del vecino más cercano monótona. Todos los puntos menores que (4,8) no pueden obtener una etiqueta de clase mayor que 1, de for- ma que la regla de asignación se ha ajustado en consecuencia. Hay que tener en 42 Caṕıtulo 1. Conceptos Teóricos y Antecedentes cuenta que esta regla de asignación no es monótona en general, pero es monótona con respecto a los tres puntos en la muestra de entrenamiento. Figura 1.10: Diagramas de Voronoi del vecino más cercano. 1.6. Aprendizaje mediante ejemplos anidados genera- lizados El aprendizaje mediante ejemplos anidados generalizados (Nested Generali- zed Examples, NGE) es un paradigma de aprendizaje basado en ejemplos con clase, donde una hipótesis inducida tiene la forma gráfica de un conjunto de hi- perrectángulos en un espacio n dimensional Eucĺıdeo. Los ejemplares para cada clase pueden ser tanto hiperrectángulos como instancias simples [Sal91]. La en- trada de un sistema NGE es un conjunto de ejemplos de entrenamiento, cada uno descrito como un vector de parejas atributo numérico/valor y una clase aso- ciada. Los atributos pueden ser tanto numéricos como categóricos. Los atributos numéricos se presentan normalmente normalizados en el intervalo [0, 1]. En NGE, un conjunto inicial de puntos dados en el espacio n dimensional Eucĺıdeo se generaliza en un conjunto más pequeño de hiperrectángulos en forma de elementos contenidos. La elección de qué hiperrectángulo generalizar desde el subconjunto de puntos o desde otros hiperrectángulos y de cómo generalizarlo, 1.6. Aprendizaje mediante ejemplos anidados generalizados 43 depende del algoritmo concreto de NGE empleado. En las siguiente secciones, describimos los conceptos esenciales para entender el modelo de aprendizaje NGE, junto a los algoritmos más comunes que pertene- cen a este paradigma. Primero, explicamos los conceptos necesarios para entender el funcionamiento de la clasificación con este tipo de técnicas (Sección 1.6.1). Des- pués, se describen los dos algoritmos clásicos basados en hiperrectángulos, BNGE en la Sección 1.6.2.1, y RISE in la Sección 1.6.2.2. 1.6.1. Coincidencia de puntos y clasificación La coincidencia de puntos es una de las caracteŕısticas centrales del aprendiza- je por NGE y permite incluso cierta configuración y ajuste, si se desea. De forma general, este proceso calcula la distancia entre un nuevo ejemplo y un objecto almacenado en memoria del modelo (un hiperrectángulo). Para el resto de la sec- ción, nos referiremos al ejemplo a clasificar como E y al hiperrectángulo como H, independientemente de si H está formado por un punto simple o si tiene algún volumen. El modelo calcula un valor de coincidencia entre E y H midiendo la distancia eucĺıdea entre dos objetos. La distancia eucĺıdea es bien conocida cuando H es un punto simple. En caso contrario, la distancia se calcula como sigue (considerando atributos numéricos): DEH = √√√√ m∑ i=1 ( difi maxi −mini )2 donde difi =    Efi −Hupper cuando Efi > Hupper Hlower − Efi cuando Efi < Hlower 0 en otro caso m es el número de dimensiones o atributos de los datos, Efi es el valor del atributo i-ésimo del ejemplo, Hupper y Hlower son los valores más altos y más bajos de H para un atributo espećıfico y maxi y mini son los valores máximo y mı́nimo para el atributo i-ésimo en los datos de entrenamiento, respectivamente. 44 Caṕıtulo 1. Conceptos Teóricos y Antecedentes La distancia medida por esta fórmula es equivalente a la longitud de una ĺınea dibujada perpendicularmente desde el punto Efi a la superficie, arista o esquina más cercana de H. Nótese que los puntos internos a un hiperrectángulo tienen una distancia de 0 a dicho hiperrectángulo. En el caso de solapamiento de hi- perrectángulos, se pueden utilizar varias estrategias para resolver la coincidencia. La más usual es aquella que asocia el punto que cae dentro del hiperrectángulo más pequeño de entre los que solapan a la vez. El tamaño de un hiperrectángulo se define en términos de su volumen. En atributos nominales, la distancia es 0 cuando dos atributos tienen la misma categoŕıa, y 1 en caso contrario. También hay que considerar que un hiperrectángulo que tiene un hipervolumen de menos dimensiones que otro, siempre será menor. La teoŕıa NGE también se refiere a la existencia de pesos asociados con los atributos en los ejemplos, pero no se suelen considerar porque se pueden usar independientemente a la inducción basada en hiperrectángulos y porque dificulta la interpretabilidad de los modelos obtenidos. Además, en [WD95], los autores notificaron que el uso de pesos no siempre mejora el rendimiento de un algoritmo NGE. De hecho, mostraron que los pasos basados en información mutua podŕıan ser apropiados en la mayoŕıa de los casos. 1.6.2. Propuesta Clásicas EACH, BNGE y RISE son las propuestas pioneras para el aprendizaje NGE. EACH no se considera en esta sección porque los autores de BNGE demostraron que su propuesta claramente generaliza y mejora al algoritmo EACH. 1.6.2.1. BNGE: Batch Nested Generalized Exemplar BNGE es una versión por lotes del primer modelo NGE (también conocido como EACH [Sal91]) y se propuso para arreglar algunas deficiencias presentadas por el primero algoritmo NGE [WD95]. Se cambió la manera incremental de ac- tuación por un modo por lotes y también se añadieron algunas modificaciones en la regla de coincidencia, como la inclusión de un mecanismo para tratar con valo- res perdidos y el manejo de todos los posibles valores nominales en la definición de un hiperrectángulo. La generalización de un hiperrectángulo se llevo a cabo expandiendo sus fronteras justo hasta cubrir el ejemplo deseado. BNGE sólo mezcla hiperrectángulos si el nuevo hiperrectángulo generalizado 1.6. Aprendizaje mediante ejemplos anidados generalizados 45 no cubre (o no solapa con) cualquier otro hiperrectángulo de otra clase. No per- mite el solapamiento o anidamiento, que son dos debilidades identificadas en el proceso incremental de NGE seguido por EACH. 1.6.2.2. RISE: Unificando la Inducción basada en Instancias y Reglas RISE [Dom96] es un algoritmo propuesto para vencer algunas de las limita- ciones del aprendizaje basado en instancias y la inducción de reglas mediante la unificación de ambos. El algoritmo sigue las mismas indicaciones explicadas an- teriormente, pero también introduce algunas mejoras con respecto a los cálculos de las distancias, puesto que se usa la distancia SVDM [WM97] en los atributos nominales. RISE selecciona la regla con la mayor precisión (usando la correción de Laplace existente en numerosas técnicas de inducción de reglas [F9̈9]) en vez de elegir la regla más pequeña que cubre el ejemplo. BNGE y RISE siguen un mecanismo similar para producir hiperrectángulos. Comienzan desde un conjunto de entrenamiento completo e intentan mezclar los ejemplos/hiperrectángulos más cercano mientras la precisión global no se per- judique. RISE usa una metodoloǵıa leave-one-out para calcular el rendimiento y, de forma contraria a BNGE, permite el anidamiento y el solapamiento entre hiperrectángulos. 46 Caṕıtulo 1. Conceptos Teóricos y Antecedentes Algoritmo 3 Constructor del clasificador OSDL 1: for todas las instancias (Xh, Clase(Xh)) do 2: AñadirInstancia(Xh, Clase(Xh)) 3: end for 4: if minX /∈ DataSet then 5: AñadirInstancia(minX,minClases(X)) 6: end if 7: if maxX /∈ DataSet then 8: AñadirInstancia(maxX,maxClases(X)) 9: end if 10: for todas las instancias (Xh, Clase(Xh)) do 11: EliminarInstancia(Xh, Clase(Xh)) 12: Calculamos los ĺımites de F (Xh; ·) y FM (Xh; ·) 13: Inicializamos el vector error. 14: for s’ = 0 hasta s’ = 10 do 15: s← s′/10 16: Fs(Xh, ·) = (1− s) ∗ Fm(Xh, ·) + s ∗ FM (Xh, ·) 17: error[s′] = error[s′] +Abs(i−AsignarClase(fs(Xh, ·))) 18: end for 19: AñadirInstancia(Xh, Clase(Xh)) 20: end for 21: for s’ = 0 hasta s’ = 10 do 22: R[s′]← error[s′]/Cardinal(X) 23: end for 24: s← (argmins′=0,...,10R[s′])/10; Caṕıtulo 2 Discusión de los Resultados Las siguientes secciones resumen y discuten los resultados obtenidos en cada etapa espećıfica de la tesis. 2.1. MoNGEL: Aprendizaje Monotónico basado en Ejemplos Anidados Generalizados Nos proponemos el uso y la formalización de la aproximación del aprendi- zaje basado en ejemplos anidados generalizados con restricciones monotónicas, proponiendo el algoritmo MoNGEL. El aprendizaje se efectúa mediante el alma- cenamiento de objetos en el espacio Eucĺıdeo de n dimensiones que pueden ser o puntos o hiperrectángulos. Este tipo de técnicas hibridan el aprendizaje basado en instancias con el aprendizaje basado en reglas en un modelo combinado. Se lleva a cabo un análisis experimental sobre una gran colección de conjun- tos de datos monotónicos. MoNGEL se compara con otras técnicas basadas en aprendizaje basado en instancias y/o reglas, como el clasificador de vecinos cer- canos monotónico (Monotonic k-NN), el modelo de aprendizaje ordinal (OLM) y el algoritmo de aprendizaje ordinal de dominancia estocástica (OSDL). Los resul- tados obtenidos se verifican mediante el uso de tests estad́ısticos no paramétricos y muestran que MoNGEL mejora al resto de técnicas de clasificación monotóni- 47 48 Caṕıtulo 2. Discusión de los Resultados ca mencionadas en precisión, error absoluto medio y simplicidad de los modelos construidos. Además, la cuestión clave de nuestra propuesta es que el modelo resultante se compone por ejemplos generalizados que cumplen totalmente entre śı con todas las restricciones monotónicas. 2.2. Selección de Hiperrectángulos para Clasificación Monotónica mediante el uso de Algoritmos Evo- lutivos Nos planteamos la selección de los hiperrectángulos más efectivos por medio de la aplicación de algoritmos evolutivos en problemas de clasificación monotónica. La generación de un número óptimo de hiperrectángulos para clasificar un con- junto de puntos es un problema NP-duro. Los algoritmos heuŕısticos producen normalmente un subconjunto de tamaño excesivo con hiperrectángulos innecesa- rios. Por tanto, hay una necesidad de seleccionar solo aquellos más influyentes y esto se puede hacer fácilmente con algoritmos evolutivos en etapas de reducción de datos. La técnica propuesta, denominada EHSMC-CHC, se compara con un exhaus- tivo análisis experimental que involucra un gran número de conjuntos de da- tos relativos a problemas reales de clasificación y regresión. Al tratarse de datos reales, se entiende que son datos imperfectos y presentan violaciones de la restric- ción de monotonicidad en algunos ejemplos. Comparamos nuestra propuesta con otras técnicas de aprendizaje monotónico que pertenecen a ambos paradigmas, como OLM, OSDL, k-NN monotónico y MID (inducción de árboles de decisión monotónicos). El diseño experimental incorpora el uso de tests estad́ısticos no pa- ramétricos. Los resultados muestran una mejora significativa en la precisión de los modelos que están formados por un conjunto muy reducido de hiperrectángulos. Además, al igual que el algoritmo anterior, el modelo resultante se compone por ejemplos generalizados que cumplen totalmente entre śı con todas las restricciones monotónicas, a pesar de que ahora los datos de entrada presentan imperfecciones. Caṕıtulo 3 Publicaciones 3.1. MoNGEL: Monotonic Nested Generalized Exem- plar Learning Estado: En impresión. T́ıtulo: MoNGEL: Monotonic Nested Generalized Exemplar Learning. Autores: Javier Garćıa, Habib M. Fardoun, Daniyal M. Alghazzawi, José- Ramón Cano y Salvador Garćıa. Revista: Pattern Analysis and Applications ISSN: 1433-7541 Factor de Impacto (JCR 2015): 1.104 Cuartiles por Área de Conocimiento: • Cuartil 3 en Computer Science, Artificial Intelligence, Ranking 80/130 49 THEORETICAL ADVANCES MoNGEL: monotonic nested generalized exemplar learning Javier Garcı́a1 • Habib M. Fardoun2 • Daniyal M. Alghazzawi2 • José-Ramón Cano3 • Salvador Garcı́a4 Received: 27 February 2015 / Accepted: 20 July 2015 � Springer-Verlag London 2015 Abstract In supervised prediction problems, the response attribute depends on certain explanatory attributes. Some real problems require the response attribute to represent ordinal values that should increase with some of the explaining attributes. They are called classification prob- lems with monotonicity constraints. In this paper, we aim at formalizing the approach to nested generalized exemplar learning with monotonicity constraints, proposing the monotonic nested generalized exemplar learning (MoN- GEL) method. It accomplishes learning by storing objects in Rn, hybridizing instance-based learning and rule learn- ing into a combined model. An experimental analysis is carried out over a wide range of monotonic data sets. The results obtained have been verified by non-parametric sta- tistical tests and show that MoNGEL outperforms well- known techniques for monotonic classification, such as ordinal learning model, ordinal stochastic dominance learner and k-nearest neighbor, considering accuracy, mean absolute error and simplicity of constructed models. Keywords Monotonic classification � Instance-based learning � Rule induction � Nested generalized examples 1 Introduction Knowledge extraction from ordinal or ordered concepts has attracted the interest of data mining communities in recent years [36]. An ordinal data set is that with an ordinal output attribute. In the problem of ordinal classification with monotonicity constraints the goal is to predict for a given example one of the ordered class labels [7]. Examples are described by attributes with ordered values and mono- tonicity constraints are present: a higher value of an attri- bute of an example, fixing other attributes’ values, should not decrease its class assignment. A common form of prior knowledge in data analysis concerns the monotonicity of relations between the dependent and explanatory variables [32]. As an example, consider a university acceptance procedure and assume that one candidate obtains scores at least as good on all admission criteria as a second candidate. However, the second is admitted while the first is not. It seems obvious that this monotonic relationship is not only evident, but also required in order not to commit to unacceptable admission rules. When traditional classification algorithms are used to build an admission rule from a data set & Salvador Garcı́a salvagl@decsai.ugr.es Javier Garcı́a jgf00002@red.ujaen.es Habib M. Fardoun hfardoun@kau.edu.sa Daniyal M. Alghazzawi dghazzawi@kau.edu.sa José-Ramón Cano jrcano@ujaen.es 1 Department of Computer Science, University of Jaén, 23071 Jaén, Spain 2 Department of Information Systems, Faculty of Computing and Information Technology, King Abdulaziz University, Jeddah, Saudi Arabia 3 Department of Computer Science, EPS of Linares, University of Jaén, Calle Alfonso X El Sabio S/N, 23700 Linares, Jaén, Spain 4 Department of Computer Science and Artificial Intelligence, University of Granada, 18071 Granada, Spain 123 Pa