Uso de técnicas de Data Mining sobre series temporales obtenidas por simulación y aplicación de resultados en videojuego Crossroads

Universidad de Valladolid ESCUELA DE INGENIER´ IA INFORM ´ ATICA DE VALLADOLID Master en Ingenier´ıa Inform´ atica Uso de t´ ecnicas de Data Mining sobre series temporales obtenidas por simulaci ´ on y aplicaci´ on de resultados en videojuego Crossroads Alumno: Adri´ an Manzano Santos Tutor: David Escudero Mancebo Resumen Aunque el cambio clim´atico es un desaf´ıo actual de una magnitud impredecible, existen modelos de simulaci´on que permiten obtener previsiones a largo plazo de la evoluci´on del clima y la econom´ıa en funci´on de las decisiones que adoptemos. Estos simuladores permiten obtener abundante informaci´on sobre la que se pueden aplicar t´ecnicas de data mining para conocer la relaci´on entre las pol´ıticas y sus efectos. Crossroads es un videojuego que permite explotar estas evidencias. Este trabajo se centra en la clasificaci´on de series temporales, resultado de un proceso de simulaci´on, para el reconocimiento de patrones caracter´ısticos impl´ıcitos. Esto se desarrolla bajo un enfoque de doble clasificaci´on: en primer lugar, se agrupan las series que son similares entre s´ı para reducir el cuerpo de datos, y sobre el cuerpo reducido se extraen los patrones impl´ıcitos. El trabajo se desarrolla en el contexto del videojuego educativo Crossroads, cuya salida es el resultado de simulaci´on, con el fin ´ultimo de desarrollar un proceso aut´onomo de recomendaciones. Para ello, se presenta un estudio basado en la informaci´on mutua que trata de evaluar la influencia que tienen las entradas, determinadas por el jugador, sobre el patr´on caracter´ıstico asignado. Esto permite realizar una descripci´on experta del patr´on. Por otro lado, tras clasificar los patrones como “buenos” o “malos”, es posible guiar al jugador aconsejando cambios en la entrada para obtener un resultado mejor. Palabras clave: simulaci´on, clustering de series temporales multivariables, feedback en videojuego educativo, cambio clim´atico. Abstract Although climate change is a current challenge of unpredictable magnitude, there are simulation models that allow us to obtain long-term forecasts of the evolution of the climate and the economy based on the decisions we make. These simulators provide a wealth of information on which to apply data mining techniques to understand the relationship between policies and their effects. Crossroads is a video game that allows us to exploit this evidence. This work focuses on the classification of time series, resulting from a simulation process, for the recognition of implicit characteristic patterns. This is developed under a double classification approach: first of all, series that are similar to each other are grouped to reduce the data corpus, and, over the reduced data, the implicit patterns are extracted. The work is developed in the context of the educational video game Crossroads, whose output is the simulation result, with the ultimate goal of developing an autonomous process of recommendations. For this purpose, a study based on mutual information is presented, which tries to evaluate the influence that the inputs, determined by the player, have on the assigned characteristic pattern. This allows for an expert description of the pattern.On the other hand, after classifying the patterns as “good” or “bad”, it is possible to guide the player by advising changes in his input to obtain a better result. Key words: simulation, multivariate time series clustering, feedback in educational video game, climate change. ´ Indice general 1. Introducci´on 3 1.1. Contexto: Medeas y Crossroads . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Motivaci´on ....................................... 6 1.3. Objetivos ........................................ 7 1.4. Propuestadesoluci´on ................................. 8 1.4.1. PlandeTrabajo ................................ 8 1.5. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2. Series temporales multivariantes 10 2.1. Series temporales multivariantes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.1. Comparaci´on de series temporales . . . . . . . . . . . . . . . . . . . . . . 11 2.2. Clustering........................................ 12 2.2.1. K-means..................................... 13 2.2.2. Determinando el n´umero de cl´usteres: el m´etodo del codo . . . . . . . . . 14 2.2.3. Cl´ustering jer´arquico aglomerativo . . . . . . . . . . . . . . . . . . . . . . 15 2.3. Clustering de series temporales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.1. Cl´ustering para reducir el n´umero de elementos . . . . . . . . . . . . . . . 17 2.4. Valoraci´on de un cl´ustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.1. Variaci´on intra -cl´uster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.2. Coeficientes de la silueta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.3. Valoraci´on del m´etodo de cl´ustering . . . . . . . . . . . . . . . . . . . . . 20 2.5. Informaci´onMutua................................... 21 2.5.1. Normalizaci´on de la informaci´on mutua . . . . . . . . . . . . . . . . . . . 22 2.5.2. Extensi´on a variables aleatorias continuas . . . . . . . . . . . . . . . . . . 22 3. Identificaci´on y caracterizaci´on de escenarios car. 24 3.1. Formulaci´on general del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2. Metodolog´ıa de clasificaci´on: extracci´on de los escenarios caracter´ısticos . . . . . 25 3.3. Metodolog´ıa de valoraci´on del input del proceso de simulaci´on . . . . . . . . . . . 28 3.4. El conjunto de datos. An´alisis preliminar . . . . . . . . . . . . . . . . . . . . . . . 29 3.5. Implementaci´on de la metodolog´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.6. Resultados........................................ 31 3.6.1. Construcci´on del modelo: determinando los hiperpar´ametros . . . . . . . . 31 1 ´ INDICE GENERAL 2 3.6.2. Resultados de la clasificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.6.3. Evaluaci´on del cl´ustering: Coeficiente de la silueta . . . . . . . . . . . . . 36 3.6.4. Valoraci´on de la metodolog´ıa: consistencia . . . . . . . . . . . . . . . . . . 38 3.6.5. Completando los datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.7. Valoraci´on del input en funci´on del cl´uster asignado. . . . . . . . . . . . . . . . . 39 3.8. Conclusiones ...................................... 41 4. Recomendador 43 4.1. Dise˜no y funcionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.1.1. Requisitos.................................... 43 4.1.2. Explicaci´on funcional del Recomendador . . . . . . . . . . . . . . . . . . . 45 4.2. El modelo del Recomendador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3. Implementaci´on e integraci´on en Crossroads . . . . . . . . . . . . . . . . . . . . . 51 4.4. Evaluaci´on del Recomendador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.5. Comparaci´on de los modelos propuestos . . . . . . . . . . . . . . . . . . . . . . . 53 4.6. Conclusiones ...................................... 57 5. Conclusiones y trabajo futuro 58 5.1. Conclusiones ...................................... 58 A. Contenido CD y Manuales 60 A.1.ContenidoCD...................................... 60 A.2. Instalaci´on y ejecuci´on del Recomendador . . . . . . . . . . . . . . . . . . . . . . 62 B. Informaci´on Mutua por cl´usteres 63 C. Preguntas del cuestionario 66 D. Cuestionario de Evaluaci´on del Recomendador 69 Cap´ıtulo 1 Introducci´on Actualmente, la especie humana y el mundo se encuentra en un punto de inflexi´on provocado por el calentamiento global y el colapso de los ecosistemas. Mientras que la sociedad civil y los representantes pol´ıticos son los responsables de buscar y liderar un cambio necesario y una transici´on a un futuro sostenible con cero emisiones netas, LOCOMOTION1contribuye a este empe˜no desarrollando sofisticados modelos para evaluar el impacto socioecon´omico y medioambiental de las distintas opciones pol´ıticas con el fin de ayudar a la sociedad a tomar decisiones informadas sobre la transici´on a un futuro sostenible bajas emisiones. El presente trabajo se engloba dentro del proyecto LOCOMOTION y se enfoca en el reconocimiento de patrones caracter´ısticos sobre un conjunto de series temporales, resultados del proceso de simulaci´on basado en los modelos de proyecto. En este ´ambito, y con este objetivo, las t´ecnicas de cl´ustering son predominantes, basadas en la agrupaci´on de series similares. En este primer cap´ıtulo se introduce y contextualiza el problema a abordar as´ı como la motivaci´on para llevar a cabo este trabajo. Tambi´en se presentan los objetivos que se desean alcanzar, y el plan de trabajo desarrollado para conseguirlos. 1.1. Contexto: Medeas y Crossroads Se dispone de un simulador, basado en el modelo MEDEAS2(acr´onimo del ingl´es de “modelizando la transici´on energ´etica renovable en Europa”), que predice el comportamiento de determinados indicadores socioecon´omicos (como el PIB per C´apita global o el ¨ Indice de Desarrollo Humano) y medioambientales (incremento de la temperatura media global y CO2respecto al valor preindustrial) relacionados con el cambio clim´atico y el consumo de recursos. Este modelo est´a dominado por m´as de 5000 variables de entrada, que pueden ser continuas y no acotadas. 1Sitio web LOCOMOTION: https://www.locomotion-h2020.eu/ 2Sitio web MEDEAS: https://www.medeas.eu/ 3 CAP´ ITULO 1. INTRODUCCI ´ ON 4 El simulador basado en MEDEAS tiene la finalidad de alimentar un un juego educativo de concienciaci´on medioambiental, denominado Crossroads. El objetivo del videojuego es mostrar las consecuencias que diferentes decisiones pol´ıticas tienen sobre el medioambiente y el cambio clim´atico, as´ı como buscar la transici´on de una sociedad dependiente de energ´ıas f´osiles a una sociedad basada en las energ´ıas renovables de cero emisiones netas. Cabe destacar que debido al tiempo que requiere cada simulaci´on (de unos diez segundos), se utilizan datos pregrabados, evitando que el simulador forme parte del motor del juego. La mec´anica b´asica del juego consiste en que cada jugador se fija unos objetivos en t´erminos medioambientales (incremento de la temperatura en el a˜no 2100 con respecto a los valores preindustriales) y econ´omicos (PIB persona en d´olares de 1995). Posteriormente determina una serie de hip´otesis sobre la disponibilidad de recursos, impacto del cambio clim´atico y evoluci´on de la poblaci´on. Finalmente especifica un conjunto de medidas pol´ıticas de dominio amplio con efecto en la econom´ıa y en el medioambiente. A priori, las hip´otesis definidas son fijas, pues describen la situaci´on del entorno, y mediante las medidas pol´ıticas se busca conseguir una estabilizaci´on de los incrementos de temperatura en valores que no supongan un riesgo de extinci´on. La Figura 1.1 muestra un boceto de la interfaz utilizada para seleccionar una medida pol´ıtica. Figura 1.1: Boceto de Crossroads: selecci´on de hip´otesis y medidas. Fuente: [2] La elecci´on de las opciones para las hip´otesis y medidas pol´ıticas no es arbitraria. En un trabajo previo3, la complejidad de entradas que admite el modelo de simulaci´on se ha simplificado a un conjunto de doce caracter´ısticas discretas (hip´otesis y medidas pol´ıticas). En consecuencia, se puede aplicar el modelo MEDEAS sobre las decisiones del jugador para generar un escenario futuro simulado. 3MEDEAS, Grupo de Econom´ıa, Energ´ıa y Din´amica de Sistema Universidad de Valladolid: https://geeds.es, http://www.eis.uva.es CAP´ ITULO 1. INTRODUCCI ´ ON 5 El proceso de simulaci´on produce la evoluci´on temporal de numerosos indicadores socioecon´omicos y medioambientales (temperatura global, PIB mundial, CO2, ´ındice de desarrollo humano, etc.), comenzando en el a˜no 1995 y finalizando en el a˜no 2100. En lo que respecta al juego, los escenarios futuros quedan determinados por dos indicadores: incrementos de temperatura (medioambiental) y PIB per C´apita (econ´omico). En la Figura 1.2 se presenta un boceto de la interfaz de visualizaci´on de resultados dados por el juego. Adem´as de representar los indicadores simulados frente al objetivo, el juego da una valoraci´on num´erica de ciertos aspectos, tanto propios como derivados del escenario (Figura 1.2). Figura 1.2: Captura de Crossroads: visualizaci´on de resultados Por otro lado, el objetivo del juego es que los participantes comprendan que ha causado el obtener su escenario concreto y realicen cambios sobre las medidas (e hip´otesis si fuese necesario) para alcanzar un escenario medioambiental y econ´omicamente equilibrado. Se desea que el juego de una descripci´on del escenario y recomendar´a cambios a los usuarios. Esta informaci´on se presentar´a en la secci´on “RECOMENDACIONES - RESUMEN DE NUESTRAS PROPUESTAS” de la Figura 1.2, y ser´a generada por el sistema aut´onomo de recomendaciones propuesto y desarrollado en el Cap´ıtulo 4. CAP´ ITULO 1. INTRODUCCI ´ ON 6 En la Tabla 1.1 se recogen el n´umero de opciones que admite cada pregunta del cuestionario, lo que genera 437400 combinaciones diferentes de posibles respuesta completas al cuestionario. El cuestionario en detalle se recoge en el Ap´endice C. El elevado n´umero de escenarios y su imposibilidad de un analisis directo es lo que motiva este trabajo. Cuesti´on N´um. resp. Cuesti´on N´um. resp. H1 3 H2 3 H3 5 M1 5 M2 2 M3 3 M4 3 M5 3 M6 2 M7 3 M8 2 M9 4 Tabla 1.1: Preguntas y n´umero de respuestas al cuestionario 1.2. Motivaci´on El objetivo principal de este trabajo es construir el m´odulo de diagnosis y recomendaci´on aut´onomo para el videojuego Crossroads. Aunque el cuestionario supone una importante reducci´on de las entradas admitidas en el juego, el estar compuesto de doce preguntas que admiten dos, tres, cuatro o cinco opciones posibles (Ap´endice A1), supone que existen 437.400 posibles respuestas diferentes. En consecuencia, el gran n´umero de escenarios simulados imposibilita su estudio directo por expertos en la materia, as´ı como realizar una descripci´on detallada de todos ellos. Adem´as, el hecho de trabajar con datos de simulaci´on presenta una peculiaridad: existen evoluciones de temperatura y PIB que son muy similares entre s´ı (el “ojo humano” las considerar´ıa como iguales), pero que num´ericamente difieren ligeramente. . Es m´as, anal´ıticamente estas series representan un mismo escenario, pues valores finales muy similares tienen un mismo significado (obtener un incremento de temperatura valores en el a˜no cercano al 2,25ºC es un buen resultado, pero incrementos de 5ºC suponen un riesgo de extinci´on). Esta idea se ilustra formalmente en la Secci´on 3.4. Este proyecto se motiva en la incapacidad para trabajar directamente con el conjunto total de las simulaciones, as´ı como en la necesidad de identificar como una unidad aquellos escenarios que presenten evoluciones de temperatura y PIB similares. Por tanto, se desea reducir el n´umero de escenarios posibles a un conjunto peque˜no y sencillo (denominado conjunto de escenarios caracter´ısticos), para su posterior an´alisis por expertos en la materia. Adem´as, se considera necesario conocer la contribuci´on de las respuestas sobre el escenario caracter´ıstico resultante. CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 13 tici´on suelen requerir una inicializaci´on aleatoria, esta no es necesaria en los m´etodos jer´arquicos. Los m´etodos basados en cuadr´ıculas (grid) discretizan el espacio de los elementos en una cantidad finita de celdas, que forman una estructura de red. Para formar la red, cada atributo de los objetos se divide en intervalos de igual longitud, dividiendo un espacio n−dimensional en un conjunto finito de celdas. Un algoritmo t´ıpico de este enfoque es STING [25]. Los m´etodos basados en densidad construyen los cl´usteres como ´areas “densas” de elementos separadas por regiones dispersas. La idea general es que un cl´uster se expande (adquiere nuevos elementos) mientras su densidad (n´umero de elementos) sea inferior a un cierto umbral. El algoritmo t´ıpico que se basa en esta idea es DBSCAN [10]. Estos m´etodos son capaces de identificar tanto formas variadas en los cl´usteres como outliers. Finalmente, los m´etodos basados en modelos supone que cada grupo posee sigue cierto modelo en su generaci´on, y trata de ajustar los elementos del conjunto a alg´un modelo. Se diferencian dos enfoques: el enfoque estad´ıstico, como AutoClass [7] basado en el an´alisis bayesiano, y el enfoque de red neuronal, como ART [6] y los mapas de caracter´ısticas autoorganizados [15]. 2.2.1. K-means Sea Dun conjunto de nobjetos en un Espacio Eucl´ıdeo. Un m´etodo de partici´on divide el conjunto en kcl´usteres C1, . . . , Ck. Los m´etodos de partici´on basados en representantes (denominados centroides), identifican cada cl´uster Ci, de forma un´ıvoca, con un elemento del espacio µi. Conceptualmente, el centroide se puede ver como el punto central del cl´uster. En el algoritmo de k-medias el centroide se define como la media de los elementos pertenecientes a cada cl´uster. La calidad de un cl´uster en los m´etodos de partici´on por centroides se puede medir por la variaci´on intra-cl´uster, tambi´en denominada suma de los errores al cuadrado, definida como k X i=1 X x∈Ci dE(x, µi)2(2.7) donde dEdenota la distancia eucl´ıdea. Por tanto, el problema de clasificaci´on se traduce en encontrar la partici´on de ksubconjuntos de Dque minimice el valor de la distancia intra-cl´uster. Esto implica que se tendr´ıa que evaluar todas las posibles particiones de Den ksubconjuntos, cuyo n´umero guarda una relaci´on exponencial con el n´umero de elementos en D, y hace que sea computacionalmente inabordable. Se ha demostrado que el problema es NP-hard incluso para dos cl´usteres [18]. El algoritmo de k-medias, algoritmo de cl´ustering por excelencia, es una aproximaci´on escalable al problema anterior. CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 14 1. Se comienza con un conjunto inicial de centroides, que puede seleccionarse de forma aleatoria o mediante t´ecnicas heur´ısticas. 2. En cada iteraci´on, para cada muestra de Dse calcula su distancia con respecto cada uno de los centroides, y se asigna al cl´uster del centroide de m´ınima distancia. Posteriormente, los centroides se recalculan como la media de los elementos que componen su cl´uster. 3. El paso anterior se repite hasta que se cumple cierto criterio de parada. El criterio general implica que los cl´usteres permanezcan invariantes (y por tanto los centroides) en una iteraci´on. Criterios m´as avanzados implican limites en la reducci´on de la variaci´on intra-cl´uster de una iteraci´on con respecto a la anterior, de forma que, cuando la diferencia es inferior a este l´ımite se finaliza. Algorithm 1 K-medias Input: Dun conjunto de nmuestras de un Espacio Eucl´ıdeo y kel n´umero de cl´usteres. Output: Un conjunto de kcl´usteres, representados ‘por mu1, . . . , µk. 1: begin Inicializaci´on de µ1, . . . , µk 2: repeat 3: Clasificar las nmuestras de Dcon respecto al µim´as cercano. 4: Recalcular µ1, . . . , µk 5: until µ1, . . . , µkno cambien 6: end Este m´etodo, propuesto por Stuart Lloyd en 1957 [17], es una forma aproximada de obtener estimaciones de m´axima verosimilitud para las medias. En general, cuando el solapamiento entre las densidades de los componentes es peque˜no, el enfoque del m´ınimo real para la variaci´on intra-cl´uster y el procedimiento de k-medias producen resultados similares [9, Secci´on 10.4.3 ]. La complejidad computacional de este algoritmo es O(nTk), siendo nel n´umero de muestras y Tel n´umero de iteraciones. En general, kyTson de varios ordenes de magnitud inferior a n, y fijado un l´ımite m´aximo de iteraciones siempre es escalable. 2.2.2. Determinando el n´umero de cl´usteres: el m´etodo del codo Los m´etodos de clustering por particiones, como el algoritmo de k-medias, requieren que se determine previamente el n´umero de cl´usteres a construir. Para determinar este valor, se recurre al m´etodo del codo [4]. Este m´etodo se basa en la idea de que se debe elegir un n´umero de cl´usteres tal que la adici´on de un nuevo cl´uster no ofrezca una modelizaci´on mucho mejor de los datos. Para cada valor de k(n´umero de cl´usteres), este se enfrenta con la variaci´on intra-cl´uster. Para los primeros valores de kse obtendr´a un valor elevado de variaci´on intra-cl´uster, que se reduce dr´asticamente a medida que se aumenta k. Sin embargo, a partir de un determinado valor, CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 15 k0, la variaci´on intra-cl´uster pasa de decrementarse dr´asticamente a hacerlo de forma moderada, manteni´endose este comportamiento para cada k > k0. La causa de esto es que los cl´usteres quedan pr´oximos entre s´ı (el nuevo cl´uster que se construye en kest´a muy cerca de alg´un cl´uster de los construidos en k−1). Dicho k0es el valor que se elige como ´optimo para el n´umero de cl´usteres. La justificaci´on sobre el m´etodo se presenta en la Secci´on 2.4.1. Figura 2.1: Ejemplo de aplicaci´on del m´etodo del codo, donde la elecci´on es k= 5 2.2.3. Cl´ustering jer´arquico aglomerativo Se considera un conjunto Dde nobjetos a particionar. En primer lugar, se supone que cada objeto es un cl´uster, de forma que se tendr´ıan ncl´usteres diferentes. Posteriormente, se unen los dos cl´usteres que est´en m´as pr´oximos entre s´ı, lo que produce una segunda partici´on de n−1 grupos. Esto se repite, obteniendo particiones una partici´on de n−2 cl´usteres. As´ı, en cada iteraci´on se unen los dos cl´usteres m´as pr´oximos, hasta la n−´esima partici´on, en la que todos los elementos pertenecen a un ´unico cl´uster. Como notaci´on general, a la iteraci´on se le denomina nivel, de forma que el n´umero de cl´usteres en el nivel ies de n−i+ 1. En general, un cl´ustering jer´arquico se define como una sucesi´on de particiones de D {Ci={Ci 1, . . . , Ci n−i+1}}n i=1 donde se verifica que para cada par de elementos x, y ∈Dpertenecientes a un mismo cl´uster en la iteraci´on i0, entonces permanecen juntan en cualquier nivel superior (para todo i>i0) [13, Secci´on 10.3]. La forma natural de representaci´on de los agrupamientos jer´arquicos es en forma de ´arbol, denominado dendograma Figura 2.2. Este muestra c´omo se agrupan los objetos, y dada una medida de disimilitud (por ejemplo, la distancia eucl´ıdea), tambi´en muestra c´omo se incrementa en cada cl´uster. El valor de disimilitud permite determinar si los agrupamientos son “naturales”. El problema de clasificaci´on se resuelve eligiendo una partici´on de la sucesi´on de particiones. Para ello, se recurre al dendograma y se elige aquel nivel que presenta una diferencia notable CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 16 entre los valores de diferentes niveles de disimilitud. En el ejemplo de la Figura 2.2, se elegir´ıa el nivel 8. Figura 2.2: Ejemplo de agrupaci´on jer´arquico. A la izquierda se representan las muestras, y a derecha el dendograma con los diferentes niveles. El siguiente algoritmo (Algoritmo 2) realiza las agrupaciones hasta un cierto nivel lpredefinido. Algorithm 2 Agrupaci´on jer´arquica Input: D={x1, . . . , xn}un conjunto de nmuestras de un Espacio Eucl´ıdeo, kel n´umero de cl´usteres deseados. Output: Un conjunto de kcl´usteres. 1: begin Inicializar Ci← {xi}, i = 1, . . . , n 2: l←n−k+ 1 3: i←1 4: repeat 5: Buscar los dos cl´usteres m´as cercanos, denotados por Ci, Cj. 6: Ci←Ci∪Cj 7: Eliminar Cj 8: i←i+ 1 9: until i== l 10: end El problema que presenta el cl´ustering jer´arquico es su escalabilidad, pues su complejidad computacional es de O(n2), siendo nel n´umero de elementos a clasificar [9, Secci´on 10.9.2 ]. Esto se debe a que en cada iteraci´on se hace necesario calcular la distancia entre todos los cl´usteres para hallar su m´ınimo, y para un n´umero fijo de cl´usteres k, se requerir´an n−k+1 iteraciones. CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 17 2.3. Clustering de series temporales La agrupaci´on (cl´ustering) de series temporales ha demostrado ser una t´ecnica bastante eficaz para proporcionar informaci´on ´util en determinados dominios [26]. En su aplicaci´on sobre series temporales, se diferencian tres enfoques [26]: basado en datos en bruto, basado en caracter´ısticas y basado en modelos. El enfoque basado en datos en bruto utiliza directamente los datos que componen la propia serie, sin procesarlos. Este enfoque requiere definir una medida de distancia o similitud adecuada a las series temporales, siendo esta la modificaci´on principal a realizar sobre los algoritmos tradicionales. Los otros enfoques buscan extraer informaci´on inherente a la propia serie, que es utilizada en la clasificaci´on. El enfoque basado en caracter´ısticas representan la serie como un vector de caracter´ısticas de dimensi´on fija, sobre el que aplicar los algoritmos tradicionales. El enfoque basado en modelos representa la serie temporal como su proceso estoc´astico, aplicando ciertos modelos estad´ısticos (modelo oculto de Markov [19] o los modelos ARMA y ARIMA [8] [14]). El uso principal que se da al cl´ustering de series temporales con los datos en bruto es el reconocimiento de patrones impl´ıcitos en las propias series. As´ı, se supone que las series agrupadas en un mismo conjunto comparten un patr´on com´un, y utiliz´andolas se trata de hallar dicho patr´on. Por ejemplo, en el algoritmo de k-medias se recurre la media componente a componente, que consideran las series como vectores, o t´ecnicas m´as avanzadas basadas en buscar el mejor ajuste realizando “deformaciones temporales” (la media de Fr´echet para la DTW [20]). El objetivo com´un es definir una nueva serie temporal que represente a todos los elementos del cl´uster. Otro enfoque supone que todas las series de un cl´uster provienen del mismo modelo (proceso estoc´astico), y tratan de deducirlo a partir de la muestra. 2.3.1. Cl´ustering para reducir el n´umero de elementos Adem´as del reconocimiento de patrones, los algoritmos de clustering pueden ser utilizados para reducir la cantidad de elementos que componen el cuerpo de los datos (Numerosity Reduction [13, Secci´on 3.4]). Las t´ecnicas de reducci´on de la cantidad buscan sustituir el conjunto original por un conjunto alternativo, de menor tama˜no y que mantenga y que sea representativo del original. En el caso de las series temporales, esta aplicaci´on es de gran relevancia, pues la igualdad de dos series es un requisito muy estricto. Dos series discretas con mismo orden temporal Tson iguales si as´ı lo son cada una de sus componentes. El uso de determinadas medidas de comparaci´on, como la DTW, da cierta flexibilidad a la definici´on de igualdad. Utilizando el clustering, y asumiendo un cierto error, es posible acotar el dominio de informaci´on, por ejemplo, considerando como iguales todos los elementos asociados a un cl´uster, y CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 18 sustituirlos por su representante. Cuando hay una gran similitud entre los elementos del cl´uster y su representante (error peque˜no) esto produce buenos resultados. Como ejemplo sobre datos est´aticos, en [1] se aplica el algoritmo de k-medias sobre im´agenes de resonancias en escala de grises para reducir el espectro posible de tonos de gris en las im´agenes. Posteriormente se utiliza un segundo algoritmo para la segmentaci´on de im´agenes, obteni´endose mejores resultados si se aplicaba la reducci´on de tonalidad de grises. 2.4. Valoraci´on de un cl´ustering Una vez construido un cl´ustering interesa evaluar como de bueno es, en el sentido de que los agrupamientos sean naturales, maximizando la disimilitud entre los cl´usteres y minimiz´andola entre los elementos de un mismo cl´uster. Es decir, se desea responder a la pregunta “¿Qu´e calidad tiene el clustering generado por un m´etodo, y c´omo podemos comparar los cl´usterings generados por diferentes m´etodos?” [13]. En general, los m´etodos de evaluaci´on de cl´ustering se pueden clasificar en dos grandes familias, teniendo en cuenta la disponibilidad de la verdad sobre el terreno (ground truth, agrupaci´on construida por expertos humanos): m´etodos intr´ınsecos yextr´ınsecos. Los m´etodos extr´ınsecos exigen que la verdad est´e disponible, y comparan las agrupaciones obtenidas con respecto a esta. Son una especie de m´etodos supervisados, pues se tiene cierta etiqueta adem´as de la informaci´on dada por los propios datos. Los m´etodos intr´ınsecos no utilizan la verdad sobre el terreno, sino que eval´uan la bondad del cl´uster en funci´on de la separaci´on existente entre los datos. Intuitivamente, si el cl´uster minimiza la distancia dentro de los elementos de un cl´uster y la maximiza con respecto al resto, en una clasificaci´on la distancia m´ınima entre los centros ser´a inferior a la mitad de la m´axima distancia entre cada centro y cada elemento de su cl´uster. 2.4.1. Variaci´on intra -cl´uster El primer problema por analizar es si el n´umero de cl´usteres es adecuado (natural). Si J(k), k = 1, . . . , n denota la variaci´on intra-cl´uster para la partici´on ´optima de kelementos del conjunto D, entonces se verifica que J(k)< J(k+ 1) [9, Secci´on 10.10 ]. Intuitivamente, si en la partici´on ´optima de kcl´usteres se selecciona un elemento arbitrario y se crea el cl´uster formado por este ´unico elemento, la nueva partici´on de k+ 1 cl´usteres tiene una variaci´on intra-cl´uster menor que la partici´on de kcl´usteres. Por tanto, la partici´on ´optima de k+ 1 cl´usteres tendr´a una variaci´on intra-cl´uster menor. La nueva agrupaci´on que se ha formado puede no ser natural. Intuitivamente, se puede elegir un elemento del cl´uster pr´oximo a su centro, luego el nuevo cl´uster estar´ıa rodeado de elementos CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 19 de otro. El m´etodo del codo se basa en esta idea: mientras se separan cl´usteres con sus elementos dispersos (por ejemplo, alejados de su centro), se tendr´a una disminuci´on importante de la variaci´on intra-cl´uster, mientras que, si se divide un grupo de elementos cercanos entre s´ı, la disminuci´on ser´a peque˜na. Es decir, se determina el punto en el que se pasa de cl´usteres naturales, separados por zonas dispersas, a cl´usteres forzados, con grupos pr´oximos entre s´ı. Cabe destacar que la variaci´on intra-cl´uster es una medida en particiones con representante. Para otro tipo de particiones, existen t´ecnicas similares como la distancia intra-cl´uster. Con la notaci´on utilizada en (2.7), se describe como k X i=1 1 2X x∈CiX y∈Ci dE(x, y) (2.8) En particular, los dendogramas en el cl´ustering jer´arquico utilizan esta medida de disimilitud, sobre cada cl´uster, para determinar si los agrupamientos son naturales, y que partici´on elegir. 2.4.2. Coeficientes de la silueta Los coeficientes de la silueta (silhouette coefficient) [13, Secci´on 10.6.3] es una medida de la bondad en la separaci´on de los elementos de un cl´ustering. Sea D={x1, . . . , xn}un conjunto de nelementos, y sea C1, . . . , Ckuna partici´on de D(con k < n), para cada x∈Dcon x∈Ci se definen los coeficientes a(x) = 1 |Ci|−1X y∈Ci d(x, y) b(x) = m´ın 1≤j≤k, i6=j 1 |Cj|X y∈Cj d(x, y)(2.9) donde |Ci|denota el cardinal (n´umero de elementos) del conjunto Ci. El coeficiente de la silueta para xse define como s(x) = b(x)−a(x) m´ax{a(x), b(x)}(2.10) Es claro que a(x), b(x)≥0 para cualquier xsiempre que dverifique el axioma de nonegatividad. En consecuencia −1≤s(x)≤1. El valor a(x) es la distancia media a los elementos pertenecientes al mismo cl´uster que x, y eval´ua lo compacto que es el cl´uster al que pertenece x. Por otro lado, b(x) es la distancia media a los elementos que no est´an en el mismo cl´uster que x, y mide lo separado que est´a xdel resto de cl´usteres. La situaci´on deseable es que a(x) sea peque˜no (cl´uster compacto) y b(x) sea grande (xest´a alejado del resto de cl´usteres). En este caso, el valor s(x) ser´a pr´oximo a 1. Por otro lado, si CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 20 s(x)<0 entonces a(x)> b(x), por lo que xest´a m´as cerca de los objetos de otros cl´usteres que de los miembros de su propio cl´uster. Generalmente, esta es una situaci´on bastante indeseable que se desea evitar. La evaluaci´on de un cl´ustering mediante los coeficientes de la silueta se realiza con el promedio de los coeficientes para todos los objetos del cl´uster. 2.4.3. Valoraci´on del m´etodo de cl´ustering Los coeficientes de la silueta y la variaci´on intra-cl´uster son dos medidas de la bondad de una agrupaci´on. En esta secci´on se valora la metodolog´ıa de clasificaci´on empleada. En particular, se desea evaluar como de sensible es un m´etodo de cl´ustering a la desaparici´on de algunos elementos sobre el conjunto de datos. Sea D={x1, . . . , xn}un conjunto de datos, y sean Y={Y1, . . . , Yk1}yZ={X1, . . . , Zk2} dos particiones de D, se define la medida de similitud centre YyZcomo [21] c(Y, Z) = 1 n 2 n X i=1 X j>i γi,j (2.11) donde γi,j =   1 Si existen p, q ∈Ntales que xi, xj∈Ypyxi, xj∈Zq 1 Si existen p, q ∈Ntales que xi∈Yp,xi∈Zq,Xj6∈ Ypyxj6∈ Zq. 0 Resto de casos (2.12) Es decir, dados dos puntos xi, xj∈D,γi,j = 1 si est´an juntos en un cl´uster para ambas clasificaciones o est´an en cl´usteres separados en ambas clasificaciones. Cuando en una clasificaci´on los dos est´an en el mismo cl´uster y en otra no, entonces γi,j = 0. En particular, si ni,j es el n´umero de elementos que est´an simult´aneamente en las particiones YiyZj, entonces [21] c(Y, Z) = 1 n 2 n 2−  1 2 k1 X i=1   k2 X j=1 ni,j  2 +1 2 k2 X j=1 k1 X i=1 ni,j!2 − k2 X i=1 k1 X j=1 n2 i,j  (2.13) En general, dado un conjunto de datos muestra, se puede dar el caso en que sea incompleto o la poblaci´on no est´e bien representada en la muestra. Para valorar si la metodolog´ıa aplicada es sensible a la desaparici´on de datos, se considera E⊂D. Sea Y={Y1, . . . , Yk}una partici´on de D, y sea Z={Z1, . . . , Zk}una partici´on de E, se considera Y0=Y0 1, . . . , Y 0 kdonde Y0 i=Yi∩E. CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 21 En consecuencia, se tienen dos particiones de E, dadas por Zy por Y01de las que interesa evaluar como son de diferentes, se recurre a la medida canterior. Cabe destacar que si dos particiones, Y={Y1, . . . , Yk}yZ={Z1, . . . , Zk}, tienen conjuntos id´enticos, salvo permutaciones, entonces el coeficiente c(Y, Z) = 1, y cuanto m´as cercano sea el valor ca uno mayor sera la similitud. Por otro lado, de la ecuaci´on (2.11) se obtiene que c(Y, Z)≥0. 2.5. Informaci´on Mutua Generalmente, se dispone de un cuerpo de datos etiquetados donde cada muestra est´a representada por conjunto numeroso de caracter´ısticas, vistas como un punto en el espacio n−dimensional. El objetivo es elegir el m´ınimo n´umero de caracter´ısticas que permita discriminar entre las clases, sin redundancia. La medida de la informaci´on mutua, originaria de la teor´ıa de la informaci´on, ha sido utilizada de forma recurrente para la selecci´on de atributos en m´ultiples dominios [3], destacando especialmente en la construcci´on de ´arboles de clasificaci´on. Es una generalizaci´on de la Correlaci´on de Pearson que no realiza suposiciones sobre el modelo que subyace2. Sea Xuna variable aleatoria discreta con funci´on de probabilidad pX. Con abuso de notaci´on, denotaremos tambi´en por X={x1, . . . , xn}el espacio muestral de la variable aleatoria. Dada una segunda variable discreta Y,pX,Y denota la distribuci´on de probabilidad conjunta de (X, Y ), y pY(y) = Px∈Xpx,y(x, y) es la distribuci´on marginal de Y. La informaci´on mutua entre dos variables aleatorias cuantifica la cantidad de informaci´on que comparten ambas variables. Es decir, estima la reducci´on de incertidumbre en una variable aleatoria (por ejemplo Y) que supone el conocimiento u observaci´on de otra (X). En el caso discreto, se define como [22]: I(X, Y ) = X (x,y)∈X×Y, p(x,y)6=0 p(X,Y )(x, y) log p(X,Y )(x, y) pX(x)pY(y)(2.14) Por tanto, un valor de informaci´on mutua alto indica una gran reducci´on de la incertidumbre (mayor dependencia entre las variables), y un valor bajo indica una peque˜na reducci´on de la incertidumbre. 1En sentido amplio de partici´on, pues es posible que Y0 l=∅. Sin embargo, E=Sk i=1 Y0 i, con lo que valdr´ıa con “ignorar” los Y0 ivac´ıos para tener una partici´on (aunque no en kconjuntos). Para mantener la misma notaci´on, trataremos Y0 icomo una partici´on, aunque pueda haber conjuntos vac´ıos, pues estos no tienen ninguna influencia sobre la medida c(Y0, Z), si suponemos que Y0 l=∅entonces los coeficientes nl,j = 0 para cualquier j. 2La correlaci´on de Pearson supone la linealidad de dos variables, limit´andose a este tipo de relaciones. CAP´ ITULO 2. SERIES TEMPORALES MULTIVARIANTES 22 2.5.1. Normalizaci´on de la informaci´on mutua La informaci´on mutua est´a muy relacionada con otro concepto de la teor´ıa de la informaci´on, la Entrop´ıa de Shannon, que es una estimaci´on de la cantidad de informaci´on que una variable aleatoria representa. En el caso discreto, se define como [24] H(X) = −X x∈X pX(x) log pX(x) (2.15) Si Xes una variable aleatoria con espacio muestral {x1, . . . , xn}elementos, y pX(xi) es la probabilidad de xi, entonces Halcanza su m´aximo cuando se verifica pX(x1) = pX(x2) = ···pX(xn) Adem´as, en este caso H(X) = log(n) [22, Secci´on 2 ]. Adem´as, el concepto de Entrop´ıa se puede extender a la informaci´on del vector aleatorio discreto dado por las variables XeY, denominado entrop´ıa conjunta: H(X, Y ) = −X x∈XX y∈Y pX,Y (x, y) log pX,Y (x, y) (2.16) Cuando se supone independencia entre las variables, pX,Y (x, y) = pX(x)pY(y), se verifica que I(X, Y ) = 0. Es m´as, I(X, Y )≥0. Por otro lado, cuando ambas variables est´an perfectamente correlacionadas (conocer una determina un´ıvocamente la otra) , I(X, Y ) alcanza su m´aximo en H(X, Y ) = H(X) = H(Y). Es m´as, en general se verifica la siguiente desigualdad3: 0≤I(X, Y )≤H(X), H(Y)≤H(X, Y ) Por tanto, no es posible definir una cota superior gen´erica para la informaci´on mutual. Sin embargo, se puede normalizar al intervalo [0,1] utilizando la entrop´ıa o la entrop´ıa conjunta. La metodolog´ıa que utiliza la Informaci´on Mutua normalizada para la selecci´on de un subconjunto de caracter´ısticas sobre X1,...Xnen funci´on de una etiqueta Yse denomina NMIFS (Normalized Mutual Information Feature Selection) [11]. 2.5.2. Extensi´on a variables aleatorias continuas La medida de la Informaci´on Mutua, y la Entrop´ıa de Shannon se pueden extender sobre variables aleatorias continuas, XeYcon funciones de probabilidad conjunta pX,Y y marginales pXypYrespectivamente: IM(X, Y ) = ZXZY pX,Y (x, y) log pX,Y (x, y) pX(x)pY(y)dxdy h(X) = −ZX pX(x) log(pX(x))dx (2.17) 3V´ease [22, Proposici´on 3.3 ] CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 29 3.4. El conjunto de datos. An´alisis preliminar En la Secci´on 1.1 se describi´o el origen de los datos, lo que representan y su aplicaci´on. Sea x= (x1, . . . , x12) una respuesta dada al cuestionario Crossroads y sea Sel proceso de simulaci´on, un escenario se representa como la MTS ¯ y= (y1,y2) = S(x). Donde, y1es la simulaci´on de la evoluci´on de la temperatura e y2de la econom´ıa global (en t´erminos del PIB). Con las notaciones introducidas en la Secci´on 3.1,Xrepresenta las respuestas al cuestionario para las cuales es posible realizar una simulaci´on, Yrepresenta el conjunto de escenarios resultantes de cada simulaci´on, e Y(1) eY(2) son el conjunto de series univariantes de simulaciones de temperatura y de PIB respectivamente. Se dice que dos UTS, una de temperatura y otra de PIB, est´an asociadas si son componentes de una misma MTS. El principal problema que presenta este enfoque es que dos series temporales son consideradas iguales si lo son cada una de sus componentes. Sin embargo, en la Figura 3.1 se muestran diferentes series de simulaciones que representan una misma situaci´on final pero que no son id´enticas. Adem´as, existe la posibilidad de que series de temperaturas “casi id´enticas” est´en asociadas con series de PIB muy dispares, y viceversa. En la Figura 3.2 se ejemplifica este caso. Figura 3.1: Representaci´on de seis MTS de temperatura y PIB DE distintas simulaciones tales que, fijado un escenario ¯ y= (y1,y2) de los representados se verifica que, para cualquiera de las series consideradas ¯ z= (z1,z2) y para cualquier instante de tiempo i∈ {1,...,106},|y1,i −z1,i| ≤ 0,025 |y1,i|e|y2,i −z2,i| ≤ 0,025 |y2,i|. Por otro lado, hay algunas combinaciones de respuestas al cuestionario de Crossroads para las cuales no existe un resultado de simulaci´on realista (la temperatura decrece al orden de −1033). Este comportamiento particular se ha asociado al funcionamiento interno del propio modelo de generaci´on. En particular, hay 19678 respuestas con simulaciones incoherentes. CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 30 Figura 3.2: Representaci´on de escenarios con similar evoluci´on de temperatura y una amplia variedad en la evoluci´on del PIB 3.5. Implementaci´on de la metodolog´ıa Para la implementaci´on de la metodolog´ıa se utiliza el lenguaje de programaci´on Python. En particular, se recurre al m´odulo sklearn: sklearn.cluster.KMeans: algoritmo de k-medias. sklearn.cluster.AgglomerativeClustering: algoritmo de clasificaci´on jer´arquica aglomerativo sklearn.feature selection.mutual info classif: estimaci´on de la informaci´on mutua Adem´as, se ha utilizado los m´odulos pandas ynumpy para estructurar la informaci´on de las simulaciones, que se encuentra almacenada en diferentes documentos de texto plano estructurado en forma de tabla. Dado un conjunto de datos D={d1, . . . , dn}, una partici´on B1, . . . , Bkse representa como una lista (δ1, . . . , δn) con 1 ≤δi≤k, tal que di∈Bδi. A esta lista se le denomina labels. Adem´as, se pueden considerar los representantes o centros de cada cl´uster, µ1, . . . , µk Para la implementaci´on de la metodolog´ıa de clasificaci´on, as´ı como la evaluaci´on por la informaci´on mutua se han implementado tres clases: Clasificador: representa un modelo de particionado b´asico. Est´a compuesto de los labels (atributo labels ) los representante de cada cl´uster (atributo clusters centers ). ModeloDoble: representa un modelo de clasificaci´on para MTS de dos componentes. Es decir, contiene las clasificaciones independientes para la temperatura y el PIB, cada una determinada por sus labels y sus centros, definidos como instancias de la clase Clasificador. modelo2Fases: clase principal que representa todo el proceso de clasificaci´on seg´un la metodolog´ıa (Secci´on 3.2) como de evaluaci´on de la relaci´on de las entradas del proceso CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 31 de simulaci´on con el cl´uster asignado a su salida (Secci´on 3.3). Adem´as, dispone de un conjunto de funcionalidades adicionales que permiten la evaluaci´on del cl´uster y el an´alisis de la distribuci´on de las diferentes respuestas en cada cl´uster. La implementaci´on de las clases anteriores se recoge en el fichero clasesAgrupacion.py, mientras que la generaci´on del modelo, basado en estas clases, esta implementada en el fichero modelo2FasesMain.py. Tambi´en esta presente un fichero de configuraci´on conf.py donde se determinan ciertos par´ametros de ejecuci´on. 3.6. Resultados En esta secci´on se presenta el primer modelo construido, que identifica un n´umero reducido de escenarios caracter´ısticos diferentes entre s´ı para su posterior an´alisis. Para ello se sigue la metodolog´ıa propuesta en la Secci´on 3.2. Esta metodolog´ıa ha sido dise˜nada para satisfacer las peculiaridades descritas en la secci´on anterior. En la primera fase, el algoritmo de k-medias con un n´umero de cl´usteres lo suficientemente grande busca agrupar aquellas MTS que son muy similares entre s´ı. Posteriormente, con el algoritmo jer´arquico se identifican los patrones para los resultados de temperatura y PIB, que se combinan para formar los escenarios caracter´ısticos. Previo a la clasificaci´on, se han estandarizado de forma independiente los conjuntos de las series de temperatura y de PIB, pues presentan valores con diferentes magnitudes (inferior a 10 en el caso de la temperatura y superior a 1000 en el caso del PIB). 3.6.1. Construcci´on del modelo: determinando los hiperpar´ametros Para construir el modelo es necesario determinar los hiperpar´ametros que lo gobiernan: n´umero de cl´usteres para el algoritmo de k-medias y para las clasificaciones jer´arquicas de temperatura y PIB. N´umero de cl´usteres en la primera fase: k-medias En primer lugar, se determina experimentalmente, mediante el m´etodo del codo (Secci´on 2.2.2) aplicado a la distancia intra-cl´uster, el n´umero de particiones a realizar en la fase de reducci´on, representado en la Figura 3.3. En la Tabla 3.1 se representa la evoluci´on de la variaci´on intra-cl´uster con respecto a diferentes configuraciones. Se ha elegido 200 particiones, pues para este n´umero se aprecia un cambio en el decremento de la variaci´on intra-cl´uster, y en esta primera etapa es preferible tener cl´usteres similares a un cl´uster con elementos muy heterog´eneos. CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 32 Cabe destacar que, las particiones obtenidas al aumentar el n´umeros de cl´usteres tienen un efecto reductor similar sobre la variaci´on intra-cl´uster de la temperatura y del PIB, lo que indica que ninguno de los indicadores considerados esta dominando y condicionando el particionado. Figura 3.3: Distancia intra-cl´uster para el PIB y la temperatura en conjunto N´umero de cl´usteres Variaci´on intra-cl´uster Temperatura Variaci´on intra-cl´uster PIB Variaci´on intra-cl´uster total 50 368654 334380 703034 100 198670 181808 380478 150 139909 134163 274072 200 112291 108177 220468 250 970578 90309 187366 300 84396 79877 161273 Tabla 3.1: Variaci´on total intra-cl´uster para el PIB y la temperatura con diferentes configuraciones. Las medidas de error que se presentan se aplican sobre los datos estandarizados. N´umero de cl´usteres en la segunda fase: algoritmo jer´arquico Para determinar el n´umero de divisiones a realizar mediante el cl´ustering jer´arquico aglomerativo, considerando de forma independiente los conjuntos de simulaciones de temperatura y PIB, se aplican t´ecnicas heur´ısticas y experimentales sobre el dendograma (Figura 3.4) de cada indicador. En el caso de la temperatura se construyen 5 particiones, y seis para el PIB. 3.6.2. Resultados de la clasificaci´on Patrones identificados En la Figura 3.5 se pueden observar los representantes de cada partici´on para el cl´uster jer´arquico de la temperatura y del PIB. En gris se han representado las series resultantes de CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 33 Figura 3.4: Dendograma para la agrupaci´on jer´arquica de la temperatura (izquierda) y PIB (derecha) aplicar la reducci´on del cuerpo de datos. Figura 3.5: Representaci´on de las evoluciones de temperatura y del PIB extra´ıdas mediante k-medias del conjunto original (gris) y sus respectivos patrones caracter´ısticos En esta figura se puede apreciar la principal ventaja de aplicar la reducci´on de datos, dado que, al agrupar series muy similares en un ´unico elemento, se evita que las series con comportamientos m´as extremos y menos comunes se diluyan en los casos m´as usuales al aplicar la media para obtener los representantes. Construcci´on de los escenarios caracter´ısticos Como resultado de combinar los patrones de temperatura y PIB obtenidos se obtendr´ıan 30 posibles escenarios caracter´ısticos. Sin embargo, el procedimiento de clasificaci´on de los resultados de simulaci´on muestra que no todos los escenarios caracter´ısticos son posible, lo que es CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 34 coherente con el conocimiento del tema2. As´ı, se obtiene que solo son posibles 17 escenarios caracter´ısticos. Adem´as, cerca del 80 % de las simulaciones son asignadas a cinco escenarios concretos, lo que indica que algunos escenarios caracter´ısticos requieren respuestas muy concretas a determinadas preguntas. Figura 3.6: Porcentaje de escenarios asignados a cada cl´uster. Los patrones de cada cl´uster est´an definidos en la Figura 3.5. Los valores marcados con un ∗indican un porcentaje inferior a 0,5 % no nulo. Errores cometidos Adem´as de obtener un n´umero reducido de escenarios caracter´ısticos que permita su an´alisis, la clasificaci´on propuesta permite sustituir cada MTS de simulaci´on por el patr´on caracter´ıstico del correspondiente escenario. En la Tabla 3.2 se presenta el RMSE promedio del error cometido al sustituir cada MTS por el representante de cada cl´uster. Teniendo en cuenta que los datos est´an estandarizados, y que el RMSE se puede interpretar como la desviaci´on est´andar de los residuos, el error obtenido es aceptable e indican un buen ajuste (pues la dispersi´on de los residuos es inferior a la dispersi´on natural de los datos, con valor de 1 por estar estandarizados). 2Los escenarios con un PIB que crece exponencialmente se logran consumiendo gran cantidad de combustibles f´osiles para producir la energ´ıa necesaria que permita este crecimiento. Por tanto, las emisiones de gases de efecto invernadero no se reducen y la temperatura global crece. Por otro lado, escenarios m´as conservadores en los que se logra la estabilizaci´on de la temperatura en valores pr´oximos a los 2ºC requieren la reducci´on de emisiones, lo que conlleva el abandono progresivo de los combustibles f´osiles en energ´ıas renovables y ciertos sacrificios sobre el modelo econ´omico actual. CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 35 Cl´uster Tem/PIB 0 1 2 3 4 5 0 0,139 0,145 0,217 0,131 1 0,03 0,159 0,154 0,132 0,204 0,164 2 0,076 0,113 0,088 0,118 3 0,166 0,303 4 0,069 Tabla 3.2: Media del error cuadr´atico medio cometido en cada cl´uster final al sustituir la serie multivariable por el centroide. La temperatura y el PIB est´an estandarizados. Por otro lado, para interpretar el error cometido en la sustituci´on de cada los escenario simulado por su correspondiente escenario caracter´ıstico, se utiliza el error m´aximo. Los resultados se recogen en la Tabla 3.3. Temperatura (ºC) PIB per Capita ($) RMSE max 0,41 3344,73 min 9,7·10−418,32 µ0,082 1355,61 σ0,051 445,24 Error M´aximo max 1,08 7526,86 min 2,4·10−324,43 µ0,17 1355,61 σ0,12 971,63 Error M´ax. Relativo max 0,30 8,6 min 1,4·10−32,3·10−3 µ0,081 0,35 σ0,047 0,34 Rango din´amico max 7,151 55787,8 min 0,585 275,8 µ1,58 6117,45 σ0,53 3878,43 Tabla 3.3: Media del error cometido en cada cl´uster final al sustituir la serie multivariable simulada por el escenario caracter´ıstico correspondiente. En general, el error promedio cometido es peque˜no, teniendo en cuenta el dominio de cada indicador. As´ı, para la temperatura, cuyo valor promedio es de 1,583 y su valor m´aximo es de 7,715, se comente un error maximo medio de 0,17 (aproximadamente un 10 % de la temperatura promedio). En el caso del PIB, con valores promedio de 6193 y valor m´aximo de 55787, el error m´aximo medio que se comete es de 1355 (aproximadamente del 20 % del PIB promedio). En t´erminos relativos, de media se comente un error del 8 % en la estimaci´on de la temperatura y del 34 % en la del PIB. El PIB justifica que a este modelo se le haya denominado “modelo b´asico”: la variabilidad CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 36 de escenarios en el PIB es bastante grande, con errores no despreciables. Esto se debe a que series con un comportamiento similar (crecen hasta cierto punto y luego decrecen) toman valores muy diferentes en instantes concretos (por ejemplo, en su m´aximo o en el momento final) y se agrupan juntas. Este modelo presenta otro inconveniente que se detalla en el Cap´ıtulo 4. Sin embargo, teniendo en cuenta que los datos son simulados y que los errores en el m´aximo tienen un car´acter puntual no generalizado (pues el RMSE es peque˜no y aceptable), este modelo es una buena reducci´on del n´umero inicial de escenarios, en m´as del 99,9 %, y en subconjuntos cuyos representantes (escenarios caracter´ısticos) tienen comportamientos claramente diferenciados. 3.6.3. Evaluaci´on del cl´ustering: Coeficiente de la silueta Para evaluar el particionado realizado se recurre al m´etodo de la silueta (Secci´on 2.4.2). Dado el elevado n´umero de muestras, para disponer de un c´alculo que se pueda ejecutar con los recursos disponibles, se utiliza la implementaci´on de la librer´ıa sklearn.metrics denominada silhouette score. El coeficiente de la silueta promedio obtenido para este modelo es de 0,23. Dado que es mayor que cero, esto indica que, de forma global, los cl´usteres est´an separados y son “naturales”. Sin embargo, dado que el valor obtenido no es pr´oximo a 1, esto implica que los cl´usteres no son tan compactos como deber´ıan, y que para ciertos elementos espec´ıficos estos est´an mal clasificados, provocando alguna sobreposici´on puntual de cl´usteres. El procedimiento de asignaci´on es el responsable de la existencia de estos elementos “mal clasificados” (son mas pr´oximos a otro cl´uster que al suyo). Generalmente, este error se produce cuando para cierto concreto, su representante en la fase de reducci´on se obtiene con un error que sobrestima o subestima la MTS, y el escenario caracter´ıstico se vuelve a obtener sobrestimando o subestimando al representante de reducci´on respectivamente. En la Figura 3.7 se muestra, para cada cl´uster final construido por el procedimiento de asignaci´on definido en Algoritmo 3, el porcentaje de miembros asignados a otros cl´usteres segun el principio de m´ınima distancia. La notaci´on de los cl´usteres se realiza con formato XY donde Xrepresenta el cl´uster asociado a los incrementos de temperatura e Yal PIB. Teniendo en cuenta que los cl´usteres no est´an distribuidos de forma uniforme en lo que a su poblaci´on se refiere, por lo que el n´umero de MTS que se reasignar´ıan con el principio de m´ınima distancia es cercano al 10 %. Cabe destacar que las diferencias de asignaciones se producen entre cl´usteres pr´oximos, donde los patrones de temperatura y PIB presentan un orden en sentido creciente. Por ejemplo, el cl´uster 2 (02) y el cl´uster 3 (03) solo se produce un cambio en el patr´on de PIB por el menor de los mayores. An´alogamente, entre el cl´uster 3 (03) y el cl´uster 13 se produce un cambio en el patr´on de temperatura por el inmediatamente superior. CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 37 Figura 3.7: Asignaciones de las MTS a cl´usteres seg´un la metodolog´ıa de clasificaci´on frente al principio de m´ınima distancia. Se indica el porcentaje de los miembros del cl´uster por la asignaci´on propuesta que cambian al aplicar el principio de m´ınima distancia. CAP´ ITULO 3. IDENTIFICACI ´ ON Y CARACTERIZACI ´ ON DE ESCENARIOS CAR. 38 3.6.4. Valoraci´on de la metodolog´ıa: consistencia En esta secci´on se pretende evaluar la sensibilidad del modelo construido a la desaparici´on de datos y/o existencia de outliers, aplicando la t´ecnica descrita en la Secci´on 2.4.3. Para ello se eliminan de forma aleatoria un 20 % de las muestras, y se procede a calcular el coeficiente c (2.13) entre la agrupaci´on original y la nueva agrupaci´on obtenida. Los resultados obtenidos se presentan en Semilla aleatoria Coeficiente c 0 0,934 5 0,942 10 0,787 15 0,834 20 0,891 25 0,984 30 0,975 35 0,894 40 0,93 45 0,891 Tabla 3.4: Coeficientes cpara diferentes eliminaciones aleatorias de datos En consecuencia, con una probabilidad del 95 % y bajo hip´otesis de normalidad, el verdadero valor del coeficiente cse encuentra en el intervalo (0,87; 0,95). Es decir, dado que se obtiene un coeficiente muy pr´oximo a 1, la metodolog´ıa anterior es poco sensible a la supresi´on de peque˜nos subconjuntos de datos. Adem´as, los cl´usteres definidos son consistentes a la p´erdida de miembros. 3.6.5. Completando los datos De forma externa a este trabajo, utilizando las agrupaciones realizadas por el modelo se ha construido un predictor que, dadas las respuestas al cuestionario determine el cl´uster que se le asocia. La tasa de acierto de este predictor es superior al 95 %. Para las respuestas al cuestionario que no admit´ıan un resultado de simulaci´on, mediante el predictor anterior han sido asignadas a un cl´uster concreto. Adem´as, como escenario de temperatura y PIB para estas combinaciones de respuestas, se toma el represente del cl´uster predicho. A este conjunto de respuestas y simulaciones se le denomina conjunto completo, pues con las notaciones anteriormente descritas se verifica que X=H. CAP´ ITULO 4. RECOMENDADOR 45 Id Req. Funcional RF-01 Recepci´on y procesamiento de peticiones HTTP, con la informaci´on en un formato definido para extraer los objetivos de temperatura y PIB y las respuestas al cuestionario. RF-02 Generaci´on aut´onoma del feedback de cumplimiento de objetivos. RF-03 Generaci´on aut´onoma del feedback de adecuaci´on del escenario obtenido a unos objetivos globales de temperatura y PIB. RI-04 Generaci´on aut´onoma de un conjunto de cambios m´ınimos en las respuestas del jugador que le permitan alcanzar un escenario con valores econ´omicos y medioambientales equilibrados. Tabla 4.4: Requisitos Funcionales del Recomendador Id Req. no Funcional RnF-01 El sistema se construir´a como un servicio REST externo e independiente a Crossroads. RnF-02 El sistema deber´a ser capaz de generar las respuestas en menos de 5 segundos. Tabla 4.5: Requisitos no Funcionales del Recomendador 4.1.2. Explicaci´on funcional del Recomendador El Recomendador utiliza el modelo de agrupaci´on construido. Cada posibles combinaci´on de respuestas al cuestionario tienen asociado un ´unico escenario caracter´ıstico (representante del cl´uster final al que pertenece la MTS generada por el proceso de simulaci´on), de forma que el Recomendador utiliza estos escenarios en lugar de los escenarios simulados. Como entrada, el Recomendador requiere los objetivos de temperatura y de PIB que el jugador se determin´o, as´ı como las doce respuestas dadas al cuestionario del juego (que permiten determinar el escenario de simulaci´on y por extensi´on el cl´uster y e escenario caracter´ıstico). Adem´as, se alimenta de un conjunto de datos est´aticos (su estructura de almacenamiento, utilizando varios ficheros, se recoge en la Secci´on 4.3): Asociaci´on de cada combinaci´on de respuestas con su escenario caracter´ıstico. Descripci´on realizada por un experto en la materia de cada uno de los escenarios caracter´ısticos. Los enunciados de cada preguntas del cuestionario y la relaci´on de orden entre las respuestas, seg´un el valor num´erico dado para el ´ultimo a˜no. Valores num´ericos asociados a cada opci´on posible de objetivos de temperatura y PIB. Un subconjunto de escenarios caracter´ısticos que se han considerado medioambiental y econ´omicamente adecuados (Secci´on 4.2). CAP´ ITULO 4. RECOMENDADOR 46 El Recomendador sigue un proceso secuencial de cuatro fases, descrito en la Figura 4.1: Fase 1 Escenario caracter´ıstico. La entrada al proceso de recomendaci´on es una respuesta a cada una de las doce preguntas que componen el cuestionario. Con ellas, se identifica el escenario caracter´ıstico asociado, utilizado en las tres etapas restantes. Fase 2 Objetivos. En esta fase se obtiene la primera parte del feedback sobre el cumplimiento dichos objetivos. Como entrada se recibe los objetivos definidos por el propio jugador y el escenario caracter´ıstico obtenido en la primera fase. Con este ´ultimo se extraen los valores finales (para el ´ultimo a˜no simulado) de temperatura y PIB, que se compara con el valor num´erico de cada objetivo. Fase 3 Valoraci´on. En esta fase, dado el escenario caracter´ıstico asociado en la primera etapa, se incluye la correspondiente descripci´on de este, realizada por un experto. Adem´as, utilizando el subconjunto de escenarios finales considerados como adecuados en t´erminos medioambientales y socioecon´omicos, se genera una valoraci´on de la proximidad del resultado obtenido con respecto a uno adecuado. Fase 4 Recomendaci´on. Cuando proceda, se propone al jugador una serie de cambios en sus respuestas. Esta fase requiere conocer el escenario caracter´ıstico asociado y el conjunto de escenarios considerados como adecuados. a) Se seleccionan todas los posibles inputs que tengan asignado un cl´uster de los considerados adecuados. b) Entre los inputs seleccionados, se comprueba si existe alguno con las mismas hip´otesis que las respuestas dadas por el jugador. En caso afirmativo, se ignoran todos los inputs con hip´otesis diferentes. c) De las respuestas consideradas, se selecciona aquella que requiere el m´ınimo n´umero de cambios: 1) Por n´umero de cambios. En primer lugar, se valora el n´umero de respuestas diferentes entre las dadas por el jugador y cada inputs seleccionado. Se mantienen solo los inputs que hacen m´ınimo dicho valor. 2) Por severidad de cambios. Teniendo en cuenta que existe un orden en las respuestas a una misma pregunta1, se elige el input cuyos cambios sean m´as pr´oximos a las respuestas del jugador. d) Se sugieren los cambios. En la salida que ofrece el Recomendador se diferencian cuatro componentes: Cercan´ıa a los objetivos propuestos por el jugador (resultado de la Fase 2). 1Generalmente, el valor que representa la respuesta aes menor que el valor de bque es menor que el de c. Adem´as, el valor de la respuesta des menor que el de eque es menor que el de a. Por ejemplo, en el caso de la hip´otesis m1, la poblaci´on en el a˜no 2050 es: a) 8500 millones, b) 9200 millones, c) 10000 millones, d) 5000 millones, e) 7000 millones CAP´ ITULO 4. RECOMENDADOR 47 Descripci´on del escenario incluyendo las consecuencias sobre la vida de producirse, y cercan´ıa con respecto a los escenarios caracter´ısticos considerados como adecuados (resultado de la Fase 3 ) Recomendaci´on de cambios en las medidas pol´ıticas e hip´otesis cuando procediese y fuere necesario (resultado de la Fase 4 ). Figura 4.1: Actividades realizadas por el Recomendador En la Figura 4.2 se muestra un ejemplo con el funcionamiento del Recomendador. En primer lugar, se presentan las 12 respuestas que el jugador determino como sus hip´otesis y medidas pol´ıticas. Posteriormente, se muestra el resultado obtenido con esta combinaci´on de respuestas en t´erminos de incrementos de temperatura media y evoluci´on del PIB global. Tambi´en se ilustran los objetivos de temperatura y PIB que se marco el jugador. Por ´ultimo se incluye la retroalimentaci´on que da el Recomendador: En rojo, la valoraci´on con respecto a los objetivos propuestos (Fase 1). En verde, la descripci´on experta del escenario obtenido, donde se explica que ha ocurrido y por qu´e se ha producido (Fase 1 ). En azul, la valoraci´on del escenario en t´erminos econ´omicos y medioambientales (Fase 3) y, dado que el escenario obtenido no cumple con los requisitos de idoneidad, un conjunto de modificaciones sobre las medidas pol´ıticas que permitan alcanzar un escenario m´as respetuoso con el medioambiente (Fase 4 ). Finalmente se presentan los cambios a los que habr´ıa conducido la recomendaci´on dada. CAP´ ITULO 4. RECOMENDADOR 48 Figura 4.2: Ejemplo de aplicaci´on del Recomendador. CAP´ ITULO 4. RECOMENDADOR 49 4.2. El modelo del Recomendador El Modelo B´asico (Secci´on 3.6) permite identificar un conjunto muy reducido de escenarios caracter´ısticos. Sin embargo, de forma experimental, se ha visto que no es adecuado para su uso en el Recomendador. Esto es debido a que el juego utiliza la situaci´on de los indicadores en el ´ultimo a˜no para valorar el cumplimiento de objetivos, y dicho modelo, centrado en agrupaciones por la forma, comente un error no despreciable. Adem´as, dentro de ciertos cl´usteres se han mezclado situaciones aceptables e indeseadas, relacionadas con valores de temperatura pr´oximos a los 2ºC que no se estabilizan o ca´ıdas bruscas del PIB a partir de cierto a˜no. En consecuencia, se recurre a un segundo modelo, dise˜nado ad-hoc para su uso en el Recomendador, que considera 6 cl´usteres para la temperatura y 8 cl´usteres para el PIB. Esta agrupaci´on se ha realizado sobre los datos completos (Secci´on 3.6.5), con 200 cl´usteres en la fase de reducci´on de datos. El n´umero de cl´usteres para la fase de extracci´on de patrones han sido elegidos de forma emp´ırica, tras analizar los diferentes conjuntos formados en varios niveles del histograma. Figura 4.3: Patrones de temperatura y PIB para el modelo del Recomendador En lo que respecta a la temperatura, los escenarios considerados como adecuados son los que se asocian a los patrones 0,1y2representados en la Figura 4.3, en los cuales la temperatura se estabiliza en valores pr´oximos a 2,5ºC. Cabe destacar que el objetivo de Par´ıs, estabilizar la temperatura en 1,5ºC, solo se alcanza en el primero de los patrones. Por otro lado, los patrones aceptables para el PIB son los denotados por 3,4,5,6y7, donde este no decrece. En lo que respecta a los patrones 6y7, son escenarios irreales resultado de combinar ciertas hip´otesis ideales y poco probables (como recursos ilimitados o estricto control poblacional). Por tanto, pese a ser escenarios aceptables desde el punto de vista del PIB, el Recomendador los evitar´a por ser irreales. CAP´ ITULO 4. RECOMENDADOR 50 En los patrones obtenidos se produce un cierto suavizado, consecuencia de aplicar la media de los centroides (calculado como la media de sus componentes), por lo que en el instante final existe una mayor variabilidad entre el escenario y el resultado simulado. En la Figura 4.4 se muestra la distribuci´on de los resultados de simulaci´on en los cl´usteres construidos en el modelo del Recomendador. Se puede observar que los escenarios considerados adecuados representan menos del 10 % del total (en azul en la Figura 4.4). Este n´umero reducido implica que no todas las combinaciones de las hip´otesis (h1,h2 yh3) presentan alguna combinaci´on de medidas pol´ıticas cuyo resultado de simulaci´on sea un escenario adecuado. Por ello, en ciertos casos es necesario un cambio en las hip´otesis Por otro lado, el patr´on de temperatura 2podr´ıa considerarse como adecuado admitiendo cierto error en la “estabilizaci´on de la temperatura” (en gris en la Figura 4.4). En particular, la temperatura presenta valores inferiores a 2,75Cpero no siempre logra la estabilizaci´on, alcanzando el ´ultimo a˜no con tendencia creciente. Sin embargo, el considerar dicho patr´on de temperatura como adecuado aumenta notablemente el n´umero de resultados de simulaci´on v´alidos, lo que depende del error que se acepte. Figura 4.4: Distribuci´on de los resultados de simulaci´on sobre para la agrupaci´on utilizada en el Recomendador en porcentaje respecto del total. En color azul se diferencian los cl´usteres considerados adecuados, y en gris aquellos que podr´ıan considerarse admitiendo cierto error. CAP´ ITULO 4. RECOMENDADOR 51 4.3. Implementaci´on e integraci´on en Crossroads El Recomendador se ha implementado en Python como un servicio REST externo al juego, accesible mediante una petici´on HTTP-POST al recurso /recomendador del servidor web. Adem´as, se env´ıa un archivo json con la siguiente estructura: 1{ 2"objetivo_temperatura": "d", 3"objetivo_pib":"a", 4" respuestas ":[" c" ,"b" ,"c","a" ," a","a" ," a" ,"a" ,"a" ,"a","a" ," a"] 5} Donde objetivo temperatura yobjetivo pib indican, respectivamente, el objetivo de temperatura y PIB que el jugador se marc´o de un conjunto cerrado de opciones. Adem´as, respuestas contiene una lista con las respuestas que el jugador ha dado a las 12 preguntas del cuestionario. El servicio retorna un String con toda la informaci´on generada por el Recomendador. Para su implementaci´on se ha utilizado el m´odulo Flask de Python, que permite montar el servidor web. Adem´as de los m´odulos anteriormente descritos utilizados para cargar y estructurar la informaci´on (pandas ynumpy). En la Figura 4.5 se ilustra el diagrama de despliegue para Crossroads en una ´unica maquina que re´une todos los servicios. Figura 4.5: Diagrama de despliegue de Crossroads. Fuente [2] CAP´ ITULO 4. RECOMENDADOR 52 Datos est´aticos de entrada al Recomendador Adem´as de la informaci´on que recibe en la petici´on HTTP, el Recomendador requiere de un conjunto de datos e informaci´on est´atica para su funcionamiento. Esta informaci´on es invariable durante todo el proceso de recomendaci´on, e id´entica para diferentes peticiones gestionadas. Dicha informaci´on se recoge en cuatro csv y tres py de configuraci´on, y se divide entre informaci´on generada por el modelo e informaci´on externa: La informaci´on generada por el modelo se localiza en el directorio ./saves, y se compone de: •centers pib: patrones caracter´ısticos construidos para el PIB. •centers tem: patrones caracter´ısticos construidos para la temperatura. •descripci´ on escenarios.csv: descripci´on realizada de los escenarios caracter´ısticos, que presenta el primer feedback de estos. •hipoteses con cluster.csv: contiene todas las combinaciones de posibles respuestas dadas al cuestionario, y el cl´uster final (identificador del escenario caracter´ıstico) asociado. Los recursos necesarios para la configuraci´on de la aplicaci´on y la traducci´on de ciertas representaciones de datos se encuentran en la carpeta Extras: •informacion adicional.py: permite recuperar el enunciado de cada pregunta del cuestionario a partir de su identificador. •diccionario objetivos.py: permite obtener un valor num´erico para los objetivos elegidos por el jugador, representados como una respuesta a una pregunta cerrada. •config.py: contiene los valores de configuraci´on, donde se indican los patrones de temperatura y PIB considerados adecuados. Arquitectura l´ogica La implementaci´on del servicio REST en Python la compone dos archivos diferentes: app.py: implementa las funcionalidades del servidor Flask y la parte del servicio REST que no est´a relacionada con la l´ogica interna (administraci´on de las peticiones y captura de errores). recomendador.py: implementa la l´ogica interna del proceso de evaluaci´on y recomendaci´on. Su funci´on principal es invocada en app.py. Adem´as, existe un tercer archivo, dockerfile, que se utiliza en la construcci´on de la imagen Docker. Determina la versi´on e imagen de Python a instalar en la imagen, instala los m´odulos de Python necesarios (especificados en requirement.txt) y configura como se ejecutar´a el servidor, incluyendo su visibilidad y acceso. CAP´ ITULO 4. RECOMENDADOR 53 4.4. Evaluaci´on del Recomendador Con el fin de obtener una valoraci´on del funcionamiento del Recomendador se ha desarrollado un cuestionario de 10 preguntas con un formato an´alogo al ejemplo representado en la Figura 4.2. En estas preguntas se plantean escenarios medioambientalmente inadecuados, donde el incremento de temperatura crece a valores superiores a 2,5ºC y no consigue estabilizarse. De las diez cuestiones, cinco incluyen una recomendaci´on generada de forma autom´atica por el Recomendador, que mejora la evoluci´on medioambiental manteniendo la econom´ıa en niveles aceptables y superiores a los actuales. Las otras cinco preguntas tienen recomendaciones inadecuadas, escritas arbitrariamente y que no mejoran la situaci´on. Las preguntas se recogen en en Ap´endice D El participante valora seg´un su experiencia (no se muestra el resultado final con los cambios recomendados) cada recomendaci´on en una escala Likert de 1 a 5, donde uno implica que la recomendaci´on es inadecuada y no logra mejorar la situaci´on medioambiental en el ´ultimo a˜no, y 5 indica que la recomendaci´on es correcta y supone una reducci´on en el incremento de temperatura. El Recomendador realizar´a buenas valoraciones si existe una clara diferencia entre las puntuaciones de las recomendaciones arbitrarias e incorrectas y las recomendaciones autom´aticas dadas por el Recomendador. El cuestionario se recoge en el Ap´endice D. Dado que este cuestionario solo puede ser resuelto por expertos en la materia, que sean capaces de evaluar subjetivamente como un cambio en las hip´otesis y medidas pol´ıticas afecta al resultado simulado, la muestra de realizaciones que se espera es peque˜na. Adem´as, dadas las diferentes interpretaciones, se ha dado la opci´on de justificar brevemente las respuestas, para as´ı descartar “malentendidos”. En el caso que se presenta, se tiene una ´unica respuesta realizado por un experto (Dr. ´ I˜nigo Capellan), donde las recomendaciones correctas han tenido una puntuaci´on de 4,4 frente al 1,8 de las err´oneas. Por tanto, se puede afirmar que existe una diferencia notable entre las recomendaciones automatizadas y las arbitrarias. Cabe destacar que ha errado en las preguntas 6 y 7, al dar una puntuaci´on de 4 y 2 respectivamente, siendo la primera err´onea y la segunda correcta. 4.5. Comparaci´on de los modelos propuestos La metodolog´ıa de clasificaci´on requiere determinar tres par´ametros: el n´umero de elementos en la reducci´on, el n´umero de cl´usteres de temperatura y el n´umero de cl´usteres de PIB. Manteniendo fijo el primer par´ametro se han presentado dos clasificaciones diferentes: el modelo b´asico (Secci´on 3.6) y el modelo del Recomendador (Secci´on 4.2). Cabe destacar que el cuerpo de datos utilizado en el segundo modelo es mayor que el conjunto utilizado en el primer modelo, y se ha completado apoy´andose en este. CAP´ ITULO 4. RECOMENDADOR 54 En la Tabla 4.6 se presentan diferentes m´etricas de error aplicadas a ambos modelos. En general, el modelo del Recomendador presenta una mejor´ıa global en estas m´etricas2, con una reducci´on de la desviaci´on est´andar (datos m´as agrupados en torno a una media de error menor). Sin embargo, pese a que el segundo modelo presenta una mejor´ıa respecto al primero, tambi´en supone un incremento en el n´umero de cl´usteres construidos, de 17 a 26. Adem´as, la diferencia entre los escenarios es menor. Esto se puede observar en la distancia entre los centroides de temperatura o PIB (Tabla 4.7), especialmente entre aquellos que son pr´oximos entre s´ı. Por otro lado, el coeficiente de la silueta para el modelo b´asico es de 0,23, frente a 0,26 obtenido para el modelo del Recomendador. Es decir, pese a haber aumentado el n´umero de conjuntos, el valor del coeficiente sno ha aumentado en consecuencia, y por tanto las agrupaciones realizadas en el modelo del Recomendador son algo m´as “artificiales”. Por ´ultimo, dado que para medir el cumplimiento de los objetivos propuestos por el jugador se consideran exclusivamente los valores de temperatura y PIB en el ´ultimo a˜no simulado, cobra especial importancia los errores cometidos al sustituir el ´ultimo a˜no de la MTS simulada por el de su escenario caracter´ıstico asociado (Tabla 4.8). En general, el modelo del Recomendador presenta una reducci´on en el error medio cometido, as´ı como en la desviaci´on de los residuos. Es decir, de forma general el segundo modelo realiza mejores estimaciones del instante final, y las estimaciones son m´as pr´oximas al valor real. Sin embargo, se puede apreciar c´omo, puntualmente, esto no se cumple, como ocurre para la temperatura. 2aunque puntualmente puede empeorar, como en el caso del m´aximo error para la temperatura, pese a mejorar en el valor medio y tener una menor desviaci´on est´andar AP ´ ENDICE A. CONTENIDO CD Y MANUALES 61 modelo2FasesMain.py.Script principal para la generaci´on de un modelo de agrupaci´on y todos los recursos necesarios para su uso en el sistema aut´onomo de recomendaci´on. config.py.Configuraci´on de los par´ametros necesarios para la ejecuci´on de modelo2FasesMain.py. requirements.txt.Definici´on de los requisitos de paquetes de instalaci´on en Python. Para ejecutar la generaci´on del modelo basta con crear un entorno con los presentes requisitos. La versi´on de Python bajo la que se ha desarrollado es 3.8.x. Adem´as, en la carpeta de datos se presentan los datos originales y los datos completos (Secci´on 3.6.5). En la carpeta de saves se encuentran los recursos que se generan en el proceso de construcci´on del modelo b´asico (TEM+PIB 200&5+6) y en el modelo del Recomendador (TEM+PIB 200&6+8), as´ı como los resultados de la fase de reducci´on en ambos casos. Por otro lado, en la carpeta Recomendador se encuentra la implementaci´on del Recomendador como contenedor Docker. app.py.Implementaci´on del servicio REST en Flask ara la recepci´on y gesti´on de las peticiones del Recomendador. recomendador.py.Implementaci´on de la l´ogica del Recomendador. Dockerfile.Especificaci´on de los requisitos del contenedor Docker, incluyendo el entorno Python. requirements.txt.Definici´on de los requisitos de paquetes de instalaci´on en Python. Adem´as, en la carpeta Extras se recoge la informaci´on de configuraci´on del Recomendador (escenarios adecuados, traducci´on de los objetivos a valores num´ericos, enunciado de las preguntas, etc.). En la carpeta saves se presentan todos los recursos necesarios relacionado con el modelo construido (representantes finales, asignaci´on de respuestas al cuestionario con un cl´uster, descripci´on experta de los escenarios, etc.). La informaci´on anterior se encuentra en https://github.com/AdrianM97/TFM ADRIAN MANZANO (solo los scripts y notebooks sin datos de ingesta) y en https://drive.google.com/file/d/1RmoyK6Qh8eILr6GQCjid8DUjaiCnl685/view?usp=sharing (con los datos de ingesta y resultados obtenidos con los modelos estudiados). AP ´ ENDICE A. CONTENIDO CD Y MANUALES 62 A.2. Instalaci´on y ejecuci´on del Recomendador 1. Instalar Docker sudo snap install docker 2. Crear el Docker del Recomendador (en el directorio ra´ız del Recomendador, donde se encuentra el documento Dockerfile) sudo docker build --tag recomendador docker . 3. Ejecutar la imagen Docker. sudo docker run -p XXXX:5000 recomendador docker donde XXXX indica el puerto de la m´aquina local al que se relizaran las peticiones. La aplicaci´on corre en el puerto 5000 del servicio docker, donde se redirigen las solicitudes con -p XXXX:5000. Por ´ultimo, podemos usar la opci´on -d para que se ejecute en segundo plano. Ap´endice B Informaci´on Mutua por cl´usteres 63 AP ´ ENDICE B. INFORMACI ´ ON MUTUA POR CL ´ USTERES 64 Figura B.1: Distribuci´on de las hip´otesis y decisiones pol´ıticas de los elementos que pertenecen a cada cl´uster, modelo de m´ınimos AP ´ ENDICE B. INFORMACI ´ ON MUTUA POR CL ´ USTERES 65 Figura B.2: Representaci´on de la estimaci´on dada por la Informaci´on Mutua utilizando el modelo de m´ınimos Ap´endice C Preguntas del cuestionario Este ap´endice recoge las preguntas del videojuego Crossroads que permiten definir los objetivos de incrementos de temperatura y PIB, as´ı como determinar las hip´otesis y medidas pol´ıtica que a su vez establece el escenario futuro. Figura C.1: Preguntas para determinar los objetivos 66 AP ´ ENDICE C. PREGUNTAS DEL CUESTIONARIO 67 Figura C.2: Preguntas para determinar las hip´otesis y medidas pol´ıticas I AP ´ ENDICE C. PREGUNTAS DEL CUESTIONARIO 68 Figura C.3: Preguntas para determinar las hip´otesis y medidas pol´ıticas II Ap´endice D Cuestionario de Evaluaci´on del Recomendador Figura D.1: Cuestionario de Evaluaci´on del Recomendador: Pregunta 1 69 AP ´ ENDICE D. CUESTIONARIO DE EVALUACI ´ ON DEL RECOMENDADOR 70 Figura D.2: Cuestionario de Evaluaci´on del Recomendador: Pregunta 2 AP ´ ENDICE D. CUESTIONARIO DE EVALUACI ´ ON DEL RECOMENDADOR 77 Figura D.9: Cuestionario de Evaluaci´on del Recomendador: Pregunta 9 AP ´ ENDICE D. CUESTIONARIO DE EVALUACI ´ ON DEL RECOMENDADOR 78 Figura D.10: Cuestionario de Evaluaci´on del Recomendador: Pregunta 10 Preguntas Err´oneas: 2, 3, 6, 8, 10. Preguntas Correctas: 1, 4, 5, 7, 9. Bibliograf´ıa [1] Segmentaci´on de im´agenes m´edicas mediante agrupaci´on de k-medias y algoritmo mejorado de cuencas hidrogr´aficas. In Simposio IEEE Southwest 2006 sobre an´alisis e interpretaci´on de im´agenes. [2] Alda Pe˜ nafiel, M. Desarrollo del front-end y mejoras en el back-end de un juego did´actico multijugador de competici´on y consenso sobre el cambio clim´atico. 2021. [3] Bennasar, M., Hicks, Y., and Setchi, R. Feature selection using joint mutual information maximisation. Expert Systems with Applications 42, 22 (2015), 8520–8532. [4] Bholowalia, P., and Kumar, A. Ebk-means: A clustering technique based on elbow method and k-means in wsn. International Journal of Computer Applications 105, 9 (2014). [5] Brockwell, P. J., Brockwell, P. J., Davis, R. A., and Davis, R. A. Introduction to time series and forecasting. Springer, 2016. [6] Carpenter, G. A., and Grossberg, S. A massively parallel architecture for a selforganizing neural pattern recognition machine. Computer vision, graphics, and image processing 37, 1 (1987), 54–115. [7] Cheeseman, P. C., Stutz, J. C., et al. Bayesian classification (autoclass): theory and results. Advances in knowledge discovery and data mining 180 (1996), 153–180. [8] Corduas, M., and Piccolo, D. Time series clustering and classification by the autoregressive metric. Computational statistics & data analysis 52, 4 (2008), 1860–1872. [9] Duda, R. O., Hart, P. E., and Stork, D. G. Pattern Classification, 2 ed. Wiley, New York, 2001. [10] Ester, M., Kriegel, H.-P., Sander, J., Xu, X., et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In Kdd (1996), vol. 96, pp. 226– 231. [11] Estevez, P. A., Tesmer, M., Perez, C. A., and Zurada, J. M. Normalized mutual information feature selection. IEEE Transactions on Neural Networks 20, 2 (2009), 189–201. [12] Grimmett, G., and Stirzaker, D. Probability and random processes. Oxford university press, 2020. 79 BIBLIOGRAF´ IA 80 [13] Han, J., Kamber, M., and Pei, J. Data mining concepts and techniques third edition, vol. 5. 2011. [14] Kalpakis, K., Gada, D., and Puttagunta, V. Distance measures for effective clustering of arima time-series. In Proceedings 2001 IEEE international conference on data mining (2001), IEEE, pp. 273–280. [15] Kohonen, T. Self-organizing maps, vol. 30. Springer Science & Business Media, 2012. [16] Kraskov, A., St¨ ogbauer, H., and Grassberger, P. Estimating mutual information. Physical review E 69, 6 (2004), 066138. [17] Lloyd, S. Least squares quantization in pcm. IEEE transactions on information theory 28, 2 (1982), 129–137. [18] Mahajan, M., Nimbhorkar, P., and Varadarajan, K. The planar k-means problem is np-hard. In WALCOM: Algorithms and Computation (Berlin, Heidelberg, 2009), S. Das and R. Uehara, Eds., Springer Berlin Heidelberg, pp. 274–285. [19] Minnen, D., Starner, T., Essa, I., and Isbell, C. Discovering characteristic actions from on-body sensor data. In 2006 10th IEEE international symposium on wearable computers (2006), IEEE, pp. 11–18. [20] Petitjean, F., Ketterlin, A., and Ganc¸arski, P. A global averaging method for dynamic time warping, with applications to clustering. Pattern Recognition 44, 3 (2011), 678–693. [21] Rand, W. M. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association 66, 336 (1971), 846–850. [22] ROTHSCHILD, L. P. A bit of information theory. San Diego, CA: UCSD Dept. of Mathematics (2015). [23] Sakoe, H., and Chiba, S. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing 26, 1 (1978), 43–49. [24] Shannon, C. E. A mathematical theory of communication. The Bell system technical journal 27, 3 (1948), 379–423. [25] Wang, W., Yang, J., Muntz, R., et al. Sting: A statistical information grid approach to spatial data mining. In VLDB (1997), vol. 97, pp. 186–195. [26] Warren Liao, T. Clustering of time series data—a survey, vol. 38. 2005.