Programación matemática y aprendizaje automático

PROGRAMACIÓN MATEMÁTICA Y APRENDIZAJE AUTOMÁTICO Alejandro Sanz Moreno Departamento de Estadística e Investigación Operativa Sevilla, Junio de 2024 PROGRAMACIÓN MATEMÁTICA Y APRENDIZAJE AUTOMÁTICO Alejandro Sanz Moreno Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Tutor Justo Puerto Albandoz Índice 1. Introducción al aprendizaje automático 4 2. Modelos de Clasificación no supervisada: Análisis Cluster 7 2.1. Centroide............................... 11 2.1.1. Descripción del modelo . . . . . . . . . . . . . . . . . . 11 2.1.2. Método de K-medias . . . . . . . . . . . . . . . . . . . . 11 2.1.3. Algoritmo de K-medias .................. 15 2.1.4. Algoritmo de Lloyd . . . . . . . . . . . . . . . . . . . . . 16 2.2. Medianoide.............................. 17 2.2.1. Introducción del modelo . . . . . . . . . . . . . . . . . . 17 2.2.2. Método de K-medianas................... 18 2.2.3. Algoritmo de K-medianas ................. 22 2.2.4. Método de selección de variables (ACSV) . . . . . . . . . 23 3. Modelos de clasificación supervisada 29 3.1. Máquinas de vector soporte (SVM) . . . . . . . . . . . . . . . . . 31 3.1.1. Caso Lineal Separable . . . . . . . . . . . . . . . . . . . 32 3.1.2. Caso Lineal No Separable . . . . . . . . . . . . . . . . . 35 3.1.3. CasoNoLineal ....................... 37 3.2. Árboles de clasificación y regresión (CART y OCT) . . . . . . . 39 3.2.1. Classification and Regresion Trees (CART) . . . . . . . . 39 3.2.2. Optimal Classification Trees (OCT) . . . . . . . . . . . . 41 3.3. OCT.................................. 59 2 1. Introducción al aprendizaje automático El aprendizaje automático, más bien conocido como "machine learning", ha crecido exponencialmente a raíz de las necesidades del mundo moderno. Pertenece al campo de la inteligencia artificial(AI), siendo una de las bases fundamentales de esta nueva ciencia que cobró especial importancia en los años 30 y 40, con Alan Touring al frente del desarrollo inicial de las tecnologías que hoy en día son empleadas en múltiples campos, aunque la primera intervención de este método que consiguió un efecto más generalizado no llegó hasta 1990 con la creación del filtro de spam. El aprendizaje automático se basa en programar sistemas que se encargan de actividades normalmente atribuidas a la inteligencia humana, de modo que los ordenadores puedan alimentarse de ello y aprendan de forma autómata determinadas rutinas a partir de una cierta cantidad de datos, en lugar de seguir un cierto número de reglas. Se tiene una definición más general: "Machine Learning is the field of study that gives computers the ability to learn without being explicitly programmed." Arthur Samuel, 1959 1 Y una orientada a la ingeniería: "A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E." Tom Mitchell, 1997 1 Un ejemplo actual del aprendizaje automático es el de Spotify, una de las mayores plataformas de audio online. Dicha plataforma utiliza este tipo de aprendizaje para ofrecer al consumidor el mejor contenido adaptándose a sus preferencias. Esto se efectúa mediante la recogida de datos cada vez que el usuario reproduce una canción, un podcast u otro tipo de contenido; con esto, gracias al aprendizaje automático, consigue crear filtros y modelos de predicción que ayudan al usuario tanto a descubrir nuevo contenido relacionado con lo que suele consumir, como a explorar nuevos artistas dentro de lo que acostumbra a escuchar. 1Hands-On Machine Learning with Scikit-Learn & TensorFlow, 2017 4 También resulta de gran utilidad para problemas que, enfocados desde métodos más convencionales, son muy complejos de resolver o para aquellos que no tienen un algoritmo de resolución conocido. Otras situaciones donde también resalta su eficacia son en torno a problemas cuyas soluciones necesitan demasiados ajustes manuales o numerosas reglas, los cuales pueden ser simplificados significativamente mediante el uso de estos modelos. Actualmente, las áreas donde el aprendizaje automático cobra una especial importancia son: Finanzas computacionales Visión por ordenador Biología computacional Automoción, aeroespacial y fabricación Procesamiento del lenguaje natural Gracias a la gran cantidad de datos que reciben, estos procesos son capaces de actualizar sus propias bases, mediante la evaluación de dichos datos o la búsqueda de patrones, para afrontar nuevas situaciones, lo que también es beneficioso si estos datos se encuentran en constante cambio, haciendo que los propios humanos aprendan de ello y, por tanto, haciendo que se convierta en una herramienta fundamental de gran adaptabilidad. Por ello, los principales problemas que tiene el aprendizaje automático son los malos datos o los malos algoritmos. Para un buen funcionamiento, en cuanto a los datos, son necesarios una cantidad de ellos que se ajuste a las necesidades de cada problema; unos datos que sean representativos para crear predicciones precisas, y de calidad para detectar modelos y patrones, a esto se debe que una buena parte del trabajo realizado se dedique a la limpieza de datos; y la ausencia de datos irrelevantes, para un uso más útil. 5 En cuanto a los algoritmos, al igual que hacemos los humanos, las máquinas pueden llegar a generalizar situaciones, por lo que es importante que los algoritmos sean capaces de generalizar de forma segura a partir de unos datos dados, esto se realiza a partir de la regularización; la adaptabilidad de los algoritmos mejora si aumenta el número de muestras que se ofrecen durante el proceso, pero si estos reciben un exceso de datos, pueden encontrarse valores atípicos (también llamados outliers), y en el otro extremo, es decir, si solo se proporcionan una cantidad insuficiente de datos, los modelos predictivos pueden llegar a ser demasiado simples e imprecisos. Hay diversos tipos de aprendizajes automáticos que se pueden clasificar del siguiente modo: Aquellos que están sujetos o no a la supervisión humana durante el proceso de análisis de los datos Aquellos que pueden o no aprender o ampliar sus conocimientos a lo largo del procesamiento de los datos Aquellos que simplemente comparan nuevos datos con los ya existentes, o en cambio detectan patrones en los datos para crear modelos predictivos Este criterio no es exclusivo, existen sistemas que abarcan varios de estos criterios. Este trabajo se centrará con más profundidad en el primer tipo de clasificación, analizando los modelos de clasificación supervisada y no supervisada. En los modelos de clasificación supervisada, se parte de un conjunto de datos dado, en el que cada elemento tiene asociado una etiqueta; a continuación, se elabora un método para tratar dichos datos en el que se observa, entre otros aspectos, la correcta clasificación de los mismos a través de la revisión de las marcas. Una vez realizado, se procede a clasificar nuevos datos. En los métodos de clasificación no supervisada, los datos se clasifican a partir de sus características internas, que van implícitas en la información que aporta cada observación, sin necesidad de apoyarse en etiquetas. Esta técnica utiliza grupos o clusters para clasificar los datos, reduciendo así la dificultad de los problemas a los que se enfrenta este tipo de clasificación. 6 siendo 𝑥𝑖e𝑦𝑖las componentes i-ésimas de cada observación (vistas como vectores de ℝ𝑛), con i=1,2,...,n. Este tipo de medida está sujeto a los distintos rangos de valores que toman las variables de estudio, lo que supone un inconveniente a tener en cuenta a la hora de realizar dichos cálculos, debido a la gran diferencia que puede existir entre los rangos de valores que toma cada variable a lo largo de una muestra con una cantidad considerable de datos. Esto se soluciona mediante el uso de la tipificación para transformar las variables tratadas durante el proceso a otras con media 0 y varianza 1. Este método resulta de gran utilidad en la actualidad, y encontramos ciertas ventajas e inconvenientes. Entre las ventajas de este método, encontramos: Se trata de un método directo, que sólo necesita como datos de entrada el número de clusters y la muestra de datos que se quiere organizar, lo que lo convierte en un algoritmo fácil de utilizar. Como se ha dicho anteriormente, al ser un método que permite tratar con enormes cantidades de datos, resulta ser realmente eficiente. Además, en el caso de problemas demasiado complejos, permite dividir dicho problema en sujetos más reducidos gracias a la clasificación de los datos en los conglomerados, convirtiendo así el objetivo inicial en varios subobjetivos considerando cada conglomerado como un objetivo menor, reduciendo así la complejidad e incluso las dimensiones del problema inicial, lo que conlleva un aumento en la eficiencia en el posterior manejo de las observaciones. Este algoritmo permite también descubrir nuevas estructuras de los datos mediante formas de clasificación no apreciables en primera instancia, consiguiendo así nuevas posibilidades en el posterior manejo y análisis de los datos. Por último, los resultados se pueden interpretar fácilmente, gracias a que los grupos en los que se clasifican están bien definidos y diferenciados unos de otros, y a que cada dato pertenece a un único grupo. Por otro lado, el análisis de K-medias presenta algunos problemas, entre ellos, destaca: 13 La dependencia respecto al posicionamiento inicial de los centroides establecidos, pues una mala elección de estos puede llevar a soluciones que no son óptimas o a una variabilidad cada vez que le apliquemos el algoritmo a los datos. Una mala elección de la cantidad de conglomerados empleados puede conllevar una clasificación forzada de los datos en pocos conglomerados o una agrupación poco fiable si se utilizan demasiados grupos. En el análisis de K-medias se supone que los clusters se sitúan de forma que los puntos incluidos en dicho grupo se disponen aproximadamente equidistantes al centroide. Esto hace que, si el conglomerado posee una forma compleja e irregular, haciendo que disminuya la precisión de la clasificación. La existencia de outliers puede afectar significativamente a la clasificación. Este tipo de valores puede desviar los centroides del verdadero centro del cluster, debido a las grandes diferencias que pueden presentar respecto de los otros elementos incluidos en el conglomerado. Este método se implementa para dar solución a un problema de optimización, desde el punto de vista de la Programación Matemática, en el que se tiene el objetivo de minimizar las distancias cuadráticas de cada observación al centroide del conglomerado al que está asociado, es decir, al centroide 𝑐𝑗más cercano a cada punto 𝑥𝑖. Este problema se puede formular mediante la siguiente expresión: min  𝑛 ∑ 𝑖=1 m ın 1≤𝑗≤𝑘‖𝑥𝑖−𝑐𝑗‖2 s.t. 𝑐1, ..., 𝑐𝑘∈ℝ𝑝 Sin embargo, este problema presenta algunos problemas, como la diferenciabilidad de la función a minimizar. Por ello, se puede incluir una variable 𝑢𝑖𝑗, la cual viene dada por 𝑢𝑖𝑗 ={1si 𝑥𝑖∈𝑗 0en otro caso 14 Esta se trata de una variable binaria, la cual sólo toma el valor 1 cuando el dato 𝑥𝑖se asocia al centroide 𝑐𝑗. Gracias a esta variable, se puede sustituir en el problema por el mínimo que se encontraba dentro de la suma en la función objetivo, arreglando así los problemas de diferenciabilidad. Por lo tanto, la formulación como problema de optimización queda de la siguiente forma: min  𝑛 ∑ 𝑖=1 𝑘 ∑ 𝑗=1 𝑢𝑖𝑗‖𝑥𝑖−𝑐𝑗‖2 s.t. 𝑐1, ..., 𝑐𝑘∈ℝ𝑝, 𝑘 ∑ 𝑗=1 𝑢𝑖𝑗 = 1, 𝑢𝑖𝑗 ∈ {0,1} ∀𝑖= 1,2, ..., 𝑛, ∀𝑗= 1,2, ..., 𝑘 Es necesario imponer que las variables 𝑢𝑖𝑗 sean binarias para que el problema esté bien formulado y añadir una restricción para que, para todo i=1,2,...,n, la suma sobre el término j de las variables 𝑢𝑖𝑗 debe ser 1, imponiendo así que cada punto 𝑥𝑖se encuentre en un único conglomerado. De esta manera, se reduce la dificultad de la resolución del problema. Otra forma de definir el algoritmo es introduciendo una variable 𝑡𝑖𝑗 libre, con la cual se introduce una condición de segundo orden (SOC por las siglas en inglés de "Second Order Condition") que acota los valores de los cuadrados de las distancias de cada observación dada a los centroides, quedando la formulación como sigue: min  𝑛 ∑ 𝑖=1 𝑘 ∑ 𝑗=1 𝑢𝑖𝑗𝑡𝑖𝑗 s.t. 𝑐1, ..., 𝑐𝑘∈ℝ𝑝, ‖𝑥𝑖−𝑐𝑗‖2≤𝑡𝑖𝑗, 𝑘 ∑ 𝑗=1 𝑢𝑖𝑗 = 1, 𝑢𝑖𝑗 ∈ {0,1} ∀𝑖= 1,2, ..., 𝑛, ∀𝑗= 1,2, ..., 𝑘 (1) 2.1.3. Algoritmo de K-medias En este apartado se procede a ver de forma sencilla cómo funciona el algoritmo y analizar las fases en las que se divide. 15 En primer lugar, el proceso comienza fijando k puntos 𝑐1, ..., 𝑐𝑘, que previamente han sido seleccionados de entre los puntos del conjunto O que se trataba inicialmente, los cuales se tratarán como los centroides iniciales del algoritmo. Una vez fijados los elementos 𝑐1, ..., 𝑐𝑘, el algoritmo se encarga de asignar cada observación 𝑥𝑖al elemento 𝑐𝑗más cercano, haciendo que la variable 𝑢𝑖𝑗 tome el valor 1. Fijados los 𝑢𝑖𝑗, se vuelven a definir nuevos centroides 𝑐𝑗tomando las medias coordenada a coordenada de los puntos 𝑥𝑖que están asociados a un mismo 𝑐𝑗, es decir, para cada j=1,2,...,k, los 𝑥𝑖tales que 𝑢𝑖𝑗 = 1. A partir de esta etapa, es importante definir una regla de parada, mientras no se cumpla, es necesario repetir el proceso a partir de la asignación de los 𝑥𝑖. Esta regla puede darse o bien cuando a partir de cierta iteración los centroides calculados no cambian de posición, o bien cuando pese a que puedan cambiar los centroides, los elementos de cada cluster no sufren modificaciones y siempre se mantienen en el mismo grupo. 2.1.4. Algoritmo de Lloyd Este apartado se encarga de introducir otro modelo para dar solución al problema tratado en esta sección. En concreto se analizará el algoritmo de Lloyd. Este algoritmo es utilizado para resolver el problema de las K-medias, por lo tanto, se trata de otro método de clasificación no supervisada que se encarga también de agrupar y unificar un conjunto de puntos en Kgrupos. Este procedimiento fue propuesto por Lloyd en el año 1957 y, tanto este como otros algoritmos de descenso similares, basados en un proceso iterativo cobraron una especial importancia en aquella época y, en la actualidad, se siguen tratando y mejorando. Procedente de Estados Unidos, Lloyd Stowell Shapley (1923-2016) fue un excelente matemático y economista. Destacó por sus trabajos en los campos de la teoría de juegos y la economía matemática, llegando a ser profesor emérito en la Universidad de California (UCLA), en Los Ángeles. 16 Figura 1: Lloyd Stowell Shapley El algoritmo comienza escogiendo de forma aleatoria kcentroides iniciales = {𝑐1, 𝑐2, ..., 𝑐𝑘}tras disponer de los datos a clasificar. El siguiente paso se basa en asignar cada uno de los puntos al centroide más cercano, calculando primero, para cada dato, las distancias euclídeas a cada centro 𝑐𝑗y a continuación, asignar cada punto al centroide más cercano. Posteriormente, una vez construidos los clusters, se vuelven a calcular los centroides para actualizar sus valores y así mejorar el resultado mediante la siguiente ecuación: 𝑐𝑗=1 |𝑗|∑ 𝑘∶𝑥𝑘∈𝑗 𝑥𝑘 Mientras no se de una regla de parada (como ocurría en el algoritmo de las K-medias), se repetirán los pasos de asignación y actualización hasta que el conjunto C se estabilice. 2.2. Medianoide 2.2.1. Introducción del modelo A continuación se presentarán problemas de clasificación no supervisada en los que ahora se da una solución basada en los medianoides de las observaciones de un conjunto dado. Estos elementos son los obtenidos al calcular las medianas 17 de los datos que pertenecen a un mismo cluster. El medianoide de un conjunto 𝑗viene dado por: 𝑐𝑗=𝑀𝑒{𝑥𝑖∈𝑗} donde 𝑀𝑒{𝑥𝑖∈𝑗}representa la mediana de los puntos que se encuentran en j-ésimo conglomerado. 2.2.2. Método de K-medianas Este método es uno de los básicos dentro de la teoría de localización discreta. Esta teoría tiene como principal objetivo buscar la mejor localización posible para ubicar nuevos puntos que se introducen en una muestra dada, mediante el cumplimiento de ciertos requisitos que se exigen. En el siglo XVII el matemático francés Pierre de Fermat introdujo el problema en el que, dado un triángulo, se ha de localizar un punto en el plano en el plano que minimice la suma de las distancias a cada uno de sus vértices. A principios del siglo XX, Alfred Weber añadió a este problema ponderaciones o costes, ya que lo trató desde un punto de vista económico, haciendo de éste uno de los primeros problemas de localización. Y no fue hasta la década de 1960 que el matemático Hakimi trabajó y desarrolló diversos problemas del mismo campo para encontrar medianas de un grafo, y entre los años 1964 y 1965 gracias a su trabajo introdujo el problema de la k-mediana. El problema trata de minimizar la suma de las distancias ponderadas o costes entre los puntos de demanda y las instalaciones ubicadas entre k ubicaciones. (a) Pierre de Fermat (b) Alfred Weber (c) Seifollah Louis Hakimi 18 Como otros problemas de localización, resolver el problema de la k-mediana es NP-hard. Debido a su alcance rápido de una aproximación de la solución del problema, es habitual el uso de métodos heurísticos. Por otro lado, cuando se dispone en forma de árbol, también existen modelos algorítmicos que lo resuelven en tiempo polinomial. Este algoritmo se desarrolló para mejorar el método de las K-medias, ya que este era especialmente sensible a los valores outliers que pudiera presentar una muestra de datos. Además, su uso se recomienda cuando las distribuciones de las variables no son simétricas. Este método se basa en calcular la mediana de las coordenadas de los datos que son objeto de estudio. Una medida que posee un gran peso en una configuración de ubicación es la distancia o el tiempo medio que emplean quienes hacen uso de las instalaciones. Minimizar estos aspectos hace que las localizaciones sean más accesibles para aquellos que se encuentran en los puntos de demanda. En ciertos casos reales, como la localización de centrales eléctricas para abastecer a distintas ciudades, esta optimización supone una reducción de los problemas e inconvenientes de los usuarios. Este problema resulta más sencillo tratarlo como un grafo no dirigido G=(V,A), formado por un conjunto de vértices o nodos V, en el que existen nodos que representan las posibles ubicaciones en las que se pueden encontrar las instalaciones, y otros que representan los elementos que se desean asociar a cada instalación; y un conjunto de aristas A, las cuales pueden llevar o no un peso asociado (como la distancia entre los dos puntos que se sitúan en los extremos de la arista). Esto hace que este modelo se pueda representar de forma gráfica si se hace en forma de grafo de la siguiente manera, en la que los nodos azules representan los nodos a clasificar y los rojos las ubicaciones donde se pueden localizar las instalaciones: 19 También se puede presentar este problema en forma de árbol, es decir, un grafo en el que cada par de vértices está conectado por un solo camino. En el siguiente ejemplo se utiliza el mismo código de colores para los nodos que en el ejemplo anterior: En su trabajo, Hakimi llegó a la conclusión de que la solución óptima se encontraba en uno de los nodos del grafo, por lo tanto, es más sencillo ubicar las instalaciones. Esta propiedad marca una clara diferencia con el método de la K- media, pues mientras que en este los centros se ubicaban en cualquier punto del plano, en el de la K-mediana se conocen los posibles puntos donde se pueden situar las instalaciones. También se tiene siempre que la suma total de las distancias ponderadas de los nodos disminuye si se añaden nuevas instalaciones adicionales. Esto se debe a que, como se tiene la existencia de la solución óptima con K instalaciones, al añadir nuevas en los nodos que quedan libres hace que disminuyan las distancias ponderadas gracias a la reasignación de ciertos nodos y, por tanto, el valor de la función objetivo. Por otro lado, existen ciertos métodos heurísticos que ofrecen soluciones iniciales que ayudan a conseguir una convergencia más rápida del problema. Se tratarán algunos de los principales métodos heurísticos clásicos, algunos son constructivos y otros requieren de una solución inicial factible para su correc- to funcionamiento: Greedy: este método fue introducido por Kuehn y Hamburguer en 1963. Comienza con un conjunto vacío C de instalaciones, se resuelve ahora el problema de la 1-mediana y, una vez obtenida la solución, se añade al conjunto C. Este proceso se repite hasta tener k medianas, completando el problema, añadiendo en cada iteración la instalación que más reduce el valor de la función objetivo. 20 Stingy: también llamado Drop oGreedy-Drop, fue presentado por Feldman, Lehrer y Ray en 1966. Este método comienza con el conjunto completo de todas las posibles instalaciones que pueden estar abiertas y en cada iteración se elimina aquella que aumente menos el valor de la función objetivo, hasta que obtengamos un conjunto de k elementos. Alternado: fue propuesto por Maranzana en 1964. En este método se elige un subconjunto de k instalaciones de entre todas las posibles, y se asignan todos los nodos a la instalación más cercana, formando k particiones del conjunto total de nodos. A continuación, se aplica el método de la 1- mediana a cada partición y se reordenan los vértices una vez obtenidas las nuevas medianas. El proceso se repite hasta que no cambien las medianas, llegando así a la solución óptima. Este método puede convertirse en uno exhaustivo si al inicio se consideran todas las posibles combinaciones de k instalaciones sobre el conjunto total de vértices (si existen m posibles localizaciones, considerar las (𝑚 𝑘)posibilidades), pero no se suele utilizar debido a la alta complejidad que presenta (O(𝑚𝑘)). Intercambio: presentado por Teitz y Bart en 1968. El proceso comienza con un conjunto arbitrario de k instalaciones, y en cada iteración se mueve, cada una, a una localización entre las que hayan quedado libres de modo que disminuya el valor de la función objetivo; finalizando el proceso en el momento en el que no existan movimientos posibles que mejoren dicho valor. Además, existen otros métodos heurísticos híbridos que combinan algunos de los métodos vistos, como en el método GreedyG propuesto por Captivo en 1991, en el que comienza empleando el método Greedy, pero en cada iteración introduce un procedimiento Alternado. En este trabajo se tratará el problema de la K-mediana, al igual que el de K- medias, como un problema de Programación Matemática, en el que la función objetivo a tratar en este problema es: m ın 𝑘 ∑ 𝑗=1 ∑ 𝑖∈𝑗|𝑥𝑖−𝜇𝑗| donde 𝑗es el cluster j-ésimo, k es el número de conglomerados en los que se quiere clasificar los datos, cada 𝑥𝑖representa un dato de la muestra, y 𝜇𝑗es la 21 mediana (o medianoide) de 𝑗. Por lo tanto, el problema de optimización con restricciones que se ha de resolver será: min 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝑤𝑖𝑑𝑖𝑗𝑥𝑖𝑗 s.t. 𝑛 ∑ 𝑗=1 𝑥𝑖𝑗 = 1 ∀𝑖= 1,2, ..., 𝑛, 𝑛 ∑ 𝑗=1 𝑦𝑗=𝑘, 0≤𝑥𝑖𝑗 ≤𝑦𝑗∀𝑖, 𝑗 = 1,2, ..., 𝑛, 𝑦𝑗∈ {0,1} ∀𝑗= 1,2, ..., 𝑘 (2) donde el vector 𝑤=𝑤1, 𝑤2, ..., 𝑤𝑛representa los pesos asociados a los vértices; 𝑑𝑖𝑗 representa la distancia entre los vértices i y j; la variable binaria 𝑦𝑗indica si el vértice j pertenece o no a la k-mediana; cada 𝑥𝑖𝑗 muestra la fracción de demanda que en el vértice i queda satisfecha por la instalación en el vértice j, si ésta existe. La primera restricción indica que para cada vértice i, la suma de las fracciones de demanda que satisfacen las instalaciones ubicadas en los distintos vértices por el método tiene que ser 1, es decir, tras ubicar las instalaciones, la demanda existente en cada vértice tiene que ser satisfecha. La segunda restricción indica que el número de instalaciones colocadas tiene que ser exactamente k. La tercera, que la demanda satisfecha por el vértice j en el vértice i siempre tiene que ser menor que el valor de la variable 𝑦𝑗, esto indica que, si no existe una instalación en el vértice j, dicho vértice no puede satisfacer ninguna fracción de la demanda en el vértice i. Por último, se indica que las variables 𝑦𝑗han de ser binarias. 2.2.3. Algoritmo de K-medianas El objetivo de este apartado es mostrar el funcionamiento del algoritmo, analizando cada fase del mismo en su implementación en Python para observar su resolución con el solver Gurobi, la cual observaremos en el anexo. 22 3. Modelos de clasificación supervisada Los modelos de clasificación supervisada son procesos realizados para detectar elementos o propiedades comunes entre los datos de un mismo conjunto, llevando a cabo una asignación a diferentes clases según un modelo de clasificación. Este tipo de modelos se caracteriza por la presencia de etiquetas o propiedades asociados a los datos, las cuales serán fundamentales para su clasificación. Los algoritmos intentan predecir o clasificar un determinado atributo de los datos, su precisión y la presencia de datos erróneamente clasificados depende de la cantidad de propiedades que se han predicho o clasificado correctamente. Para ello, se proporcionan dos conjuntos de datos, un conjunto de datos de entrenamiento (training data) y otro conjunto de datos de prueba (test data). En el primer conjunto, se encuentran datos ya etiquetados y se espera que a partir de dichos datos se pueda realizar una correcta clasificación de los datos del segundo conjunto con la mayor precisión. El primer objetivo que tienen estos modelos es construir un algoritmo que se encargue de describir cada clase, de acuerdo a las características que presentan los propios datos. Estos métodos se desarrollan para la posterior clasificación de nuevos datos que se incorporan al conjunto de datos ya existente, o bien para mejorar las descripciones ya existentes. En estos métodos, los datos de entrenamiento son npares ordenados (𝑥1, 𝑦1), (𝑥2, 𝑦2), ..., (𝑥𝑛, 𝑦𝑛), donde las 𝑥𝑖representan alguna medida o un conjunto de medidas, dependiendo de la dimensión de los datos, de una observación realizada, mientras que los 𝑦𝑖indican las etiquetas asociadas a los datos. El conjunto de datos de prueba es otro conjunto de m medidas (𝑥𝑛+1, 𝑥𝑛+2, ..., 𝑥𝑛+𝑚) los cuales están sin etiquetar. El objetivo es predecir las etiquetas que estarán asignadas a cada uno de estos valores mediante relaciones con los datos de entrenamiento. La situación idónea a la hora de tratar estos datos es que los datos de entrenamiento sean independientes respecto de los datos de prueba, obteniendo así una clasificación más precisa de los mismos. 29 En el caso de las variables binarias, los errores que se pueden cometer son los casos en los que los datos de prueba se clasifican con el valor equivocado. Por ello se puede elaborar la siguiente tabla de clasificación: Valor real Y𝑖∕𝑉 𝑎𝑙𝑜𝑟𝑒𝑠𝑡𝑖𝑚𝑎𝑑𝑜  𝑌𝑖Y𝑖= 0 Y𝑖= 1 ˆ Y𝑖= 0 A11 A12 ˆ Y𝑖= 1 A21 A22 Esta tabla se puede ver también como una matriz de confusión. En base a los resultados de la tabla, los valores de 𝐴11 y𝐴22 representan la cantidad de valores que se han estimado correctamente, mientras que los otros dos valores indican el número de clasificaciones erróneas de los datos. A partir de estos se pueden definir los siguientes términos: Tasa de aciertos: mide el cociente entre los valores correctamente estimados y el número total de datos, el cual corresponde a la suma de los cuatro elementos de la tabla anterior. 𝐴11 +𝐴22 𝐴11 +𝐴12 +𝐴21 +𝐴22 Tasa de errores: cociente entre el número de clasificaciones incorrectas y el número de predicciones. 𝐴12 +𝐴21 𝐴11 +𝐴12 +𝐴21 +𝐴22 Especificidad: Porcentaje de valores 0 correctamente estimados respecto al total de valores 0 observados. 𝐴11 𝐴11 +𝐴21 Sensibilidad: Porcentaje de valores 1 correctamente estimados respecto al total de valores 1 observados. 𝐴22 𝐴12 +𝐴22 30 Tasa de falsos ceros: Porcentaje de valores 0 incorrectamente estimados respecto al total de valores 0 observados. 𝐴21 𝐴11 +𝐴21 Tasa de falsos unos: Porcentaje de valores 1 estimados de forma incorrecta respecto al total de valores 1 observados. 𝐴12 𝐴12 +𝐴22 A continuación, entre los métodos de clasificación supervisada más usados, se tratarán las máquinas de vector soporte y los árboles de clasificación y regresión. 3.1. Máquinas de vector soporte (SVM) Las máquinas de vector soporte, o Support Vector Machines (SVM) en inglés, son un método de clasificación supervisada que utilizan una base de datos dada, donde las categorías en las que se clasificarán los datos son conocidas y los límites de estas están perfectamente establecidos. Estas máquinas fueron desarrolladas en los años 90, por Vladimir Vapnik y sus colaboradores en sus avances en la teoría del aprendizaje estadístico, con el objetivo de dar solución a problemas de clasificación binaria, aunque su uso se ha extendido en la actualidad con el objetivo de resolver otros problemas de clasificación, regresión y predicción. Se centrará el desarrollo de esta sección en la clasificación binaria en la que, dado un conjunto de datos = {(𝑥1, 𝑦1), ..., (𝑥𝑛, 𝑦𝑛)} donde 𝑥𝑖∈ℝ𝑑e𝑦𝑖∈ {−1,1}. 31 El objetivo será la construcción de un hiperplano que haga que la separación entre los datos de distinta clase sea mínima y que equidiste de los datos más próximos de cada clase, de modo que se maximiza así el margen entre ellos. A los datos cuya distancia es el margen máximo se les llama vectores soporte. Se tratarán tres casos en los que utilizar este método, aquel en el que se clasifica un conjunto lineal separable, un conjunto lineal no separable y un último caso en el que se observa un caso no lineal. 3.1.1. Caso Lineal Separable Supongamos que el conjunto es separable. En este caso, se puede construir el hiperplano de separación mediante una función lineal que permite separar las dos clases de datos que presente en función del valor del 𝑦𝑖asociado: 𝐷(𝑥) = ⟨𝑤, 𝑥⟩+𝑏 donde 𝑤∈ℝ𝑑y𝑏∈ℝ. Este hiperplano debe verificar las siguientes restricciones para cada punto del conjunto: ⟨𝑤, 𝑥𝑖⟩+𝑏≥0si 𝑦𝑖= 1 ∀𝑖= 1,2, ..., 𝑛 ⟨𝑤, 𝑥𝑖⟩+𝑏≤0si 𝑦𝑖= −1 ∀𝑖= 1,2, ..., 𝑛 Lo cual se puede reescribir de la siguiente forma: 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)≥0 ∀𝑖= 1,2, ..., 𝑛 (3) Por propiedades de geometría, se conoce que la distancia de un punto x a este hiperplano viene dada por la siguiente expresión: |𝐷(𝑥)| ‖𝑤‖ En general, se tiene que dicho hiperplano no es único, debido a la disposición de los puntos. Por ello, se considera el margen (𝜏), definido como la mínima distancia entre el hiperplano y el caso más próximo a este de cada clase de datos, las cuales vienen dadas por el valor de las 𝑦𝑖. Entonces se escogerá el que tenga el máximo margen. 32 Teniendo en cuenta la definición del margen y la desigualdad (3), se cumple que 𝑦𝑖𝐷(𝑥𝑖) ‖𝑤‖≥𝜏∀𝑖= 1,2, ..., 𝑛 (4) Gracias a esta expresión se puede deducir que para hallar el hiperplano óptimo se debe hallar el 𝑤que maximiza el margen. Debido a la existencia de infinitas soluciones óptimas que se obtienen variando la escala de 𝑤, por convenio se fija a la unidad el siguiente producto: 𝜏‖𝑤‖= 1 (5) de modo que la desigualdad (4) se puede reescribir de la siguiente forma: 𝑦𝑖𝐷(𝑥𝑖)≥1 ∀𝑖= 1,2, ..., 𝑛 (6) Por otro lado, para hallar el valor del margen en función de 𝑤, es necesario considerar dos puntos 𝑥𝑖y𝑥𝑗que cumplen que 𝑦𝑖= −1 e𝑦𝑗= 1, de modo que estos puntos verifiquen la igualdad en la expresión anterior de la siguiente forma 𝑤𝑥𝑖+𝑏= −1 𝑤𝑥𝑗+𝑏= 1 De esta manera, se tiene que la distancia entre los dos puntos viene dada por el margen. Restando a la segunda la primera expresión: 𝑤(𝑥𝑗−𝑥𝑖)=2 luego tendremos que el margen, imponiendo que 𝜏=1 2‖𝑥𝑗−𝑥𝑖‖y tomando normas en la expresión anterior, viene dado por 2𝜏=2 ‖𝑤‖ 33 lo cual es coherente con lo obtenido en (5). Entonces, como el objetivo es maximizar el margen, esto equivale a minimizar 1 2‖𝑤‖, pero en este caso se considerará como función a minimizar el cuadrado de la norma de 𝑤, lo cual no afectará al resultado. Por tanto, imponiendo las restricciones indicadas anteriormente, se obtiene que el problema se puede reescribir de la siguiente forma como un problema de programación cuadrática: min 1 2‖𝑤‖2 s.t. 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)−1≥0 ∀𝑖= 1,2, ..., 𝑛, 𝑤∈𝑑, 𝑏 ∈ El hiperplano que se obtiene al resolver el problema se denomina hiperplano de separación de margen duro o hard margin. Para resolver el problema, hallando su problema dual, se obtiene la siguiente función lagrangiana: 𝐿(𝑤, 𝑏, 𝛼) = 1 2‖𝑤‖2+ 𝑛 ∑ 𝑖=1 𝛼𝑖[1 − 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩) + 𝑏](7) donde 𝛼𝑖≥0,∀i = 1,...,n. Para obtener un mínimo global, derivamos (7) respecto de w y b. 𝜕𝐿 𝜕𝑤(𝑤, 𝑏, 𝛼) = 𝑤− 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖𝑥𝑖 𝜕𝐿 𝜕𝑏 (𝑤, 𝑏, 𝛼) = 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖 Entonces, tras igualar a 0 en ambos casos obtenemos las siguientes expresiones: 𝑤= 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖𝑥𝑖 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖= 0 Al sustituir en (7) el valor de 𝑤se obtiene 𝐿(𝑤, 𝑏, 𝛼) = 𝐿(𝑏, 𝛼) = 1 2‖ 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖𝑥𝑖‖2+ 𝑛 ∑ 𝑖=1 𝛼𝑖− 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖𝑥𝑖 𝑛 ∑ 𝑗=1 𝛼𝑗𝑦𝑗𝑥𝑗−𝑏 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖 34 y al sustituir el otro resultado finalmente se tiene 𝐿(𝑏, 𝛼) = 𝐿(𝛼) = 𝑛 ∑ 𝑖=1 𝛼𝑖−1 2 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗⟨𝑥𝑖, 𝑥𝑗⟩ Por lo tanto, el problema dual sería max 𝑛 ∑ 𝑖=1 𝛼𝑖−1 2 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗⟨𝑥𝑖, 𝑥𝑗⟩ s.t. 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖= 0, 𝛼𝑖≥0 ∀𝑖= 1,2, ..., 𝑛 donde los 𝛼𝑖≠0son los que corresponden a los vectores soporte del conjunto inicial. 3.1.2. Caso Lineal No Separable En general, suele existir ruido entre los datos, ya que es muy difícil encontrar un caso real en el que las clases sean separables. En esta situación podemos encontrar que el objeto entre dentro del margen asociado a su respectiva clase o que reside fuera de este margen. Para representar este ruido se introducen unas variables reales de holgura 𝜉𝑖,∀𝑖= 1,2, ..., 𝑛 asociadas a cada (𝑥𝑖, 𝑦𝑖)que miden la desviación de cada observación respecto del margen que delimita su respectiva clase. 35 De acuerdo con las restricciones del problema del caso separable, se modifica ahora (6) de la siguiente manera: 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏)≥1 − 𝜉𝑖𝜉𝑖≥0 ∀𝑖= 1,2, ..., 𝑛 Así, para los elementos que estén bien clasificados la variable de holgura asociada será nula, si ésta toma un valor entre 0 y 1 se dirá que el dato es no separable pero correctamente clasificado, y si su valor es mayor que uno, se dirá que es no separable y está mal clasificado. Por tanto, ahora la suma de estas variables de holgura cobra importancia a la hora de buscar el hiperplano óptimo, pues se quiere reducir el número de observaciones que forman ruido o están mal clasificadas, es por eso que se introduce una constante 𝐶a determinar suficientemente grande, la cual indica el grado de importancia que tienen estos elementos no separables. Por esto el problema de optimización a resolver será min 1 2‖𝑤‖2+𝐶 𝑛 ∑ 𝑖=1 𝜉𝑖 s.t. 𝑦𝑖(⟨𝑤, 𝑥𝑖⟩+𝑏) + 𝜉𝑖− 1 ≥0 ∀𝑖= 1,2, ..., 𝑛, 𝜉𝑖≥0 ∀𝑖= 1,2, ..., 𝑛, 𝑤∈𝑑, 𝑏 ∈ Ahora el hiperplano que se obtiene recibe el nombre de hiperplano de separación de margen blando o soft margin. Para resolver el problema procedemos como en el caso anterior hallando primero su función lagrangiana. 𝐿(𝑤, 𝑏, 𝜉, 𝛼, 𝛽) = 1 2‖𝑤‖2+𝐶 𝑛 ∑ 𝑖=1 𝜉𝑖+ 𝑛 ∑ 𝑖=1 𝛼𝑖[1−𝜉𝑖−𝑦𝑖(⟨𝑤, 𝑥𝑖⟩)+𝑏]− 𝑛 ∑ 𝑖=1 𝜉𝑖𝛽𝑖(8) Como buscamos un mínimo global, derivamos respecto de w, b y 𝜉e igualamos a 0. Al derivar respecto de los dos primeros se obtienen las mismas expresiones que en el caso separable. Al derivar respecto de 𝜉se consigue lo siguiente. 𝜕𝐿 𝜕𝜉 (𝑤, 𝑏, 𝜉, 𝛼, 𝛽) = 𝐶− 𝑛 ∑ 𝑖=1 𝛼𝑖− 𝑛 ∑ 𝑖=1 𝛽𝑖 Por lo tanto, al igualar a 0 se elaboran las siguientes ecuaciones: 𝑤= 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖𝑥𝑖 36 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖= 0 𝐶= 𝑛 ∑ 𝑖=1 𝛼𝑖+ 𝑛 ∑ 𝑖=1 𝛽𝑖(9) Por lo tanto, al sustituir en (8) obtenemos que la función lagrangiana en este caso es 𝐿(𝛼, 𝛽) = 𝐿(𝛼) = 𝑛 ∑ 𝑖=1 𝛼𝑖−1 2 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗⟨𝑥𝑖, 𝑥𝑗⟩ Como se observa que los multiplicadores de Lagrange 𝛽𝑖no aparecen en la ecuación, se puede reescribir (9) como sigue. 0≤𝛼𝑖≤𝐶∀𝑖= 1,2, ..., 𝑛 Entonces se construye el siguiente problema dual considerando la función lagrangiana y las restricciones mencionadas: max 𝑛 ∑ 𝑖=1 𝛼𝑖−1 2 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗⟨𝑥𝑖, 𝑥𝑗⟩ s.t. 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖= 0, 0≤𝛼𝑖≤𝐶∀𝑖= 1,2, ..., 𝑛 3.1.3. Caso No Lineal Se puede tratar el problema no separable de la sección anterior de una forma diferente, usando estrategias no lineales como la inmersión no lineal del conjunto del que partimos en un espacio de dimensión mayor donde las clases sean separables y buscar el hiperplano de separación en el nuevo espacio. Este espacio recibe el nombre de espacio de características (). Para ello, se introduce una función no lineal Φ ∶ ←→ , la cual lleva los datos del conjunto de partida al conjunto de características . Entonces la función de decisión en este nuevo espacio será 𝐷(𝑥) = ⟨𝑤, Φ(𝑥)⟩+𝑏 37 El problema que se plantea en este apartado es semejante al propuesto para el caso lineal no separable, pero al tratarlo ahora en el espacio de características, destaca el empleo de la función Φ. min 1 2‖𝑤‖2+𝐶 𝑛 ∑ 𝑖=1 𝜉𝑖 s.t. 𝑦𝑖(⟨𝑤, Φ(𝑥𝑖)⟩+𝑏) + 𝜉𝑖− 1 ≥0 ∀𝑖= 1,2, ..., 𝑛, 𝜉𝑖≥0 ∀𝑖= 1,2, ..., 𝑛, 𝑤∈𝑑, 𝑏 ∈ Como la complejidad aumenta con la dimensión de , se considera el problema dual, cuya complejidad depende del número de datos, y como éste sigue siendo el mismo al cambiar de dimensión no se modifica la dificultad del problema dual al cambiar de dimensión, el cual sigue siendo similar al del caso lineal no separable. max 𝑛 ∑ 𝑖=1 𝛼𝑖−1 2 𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗⟨Φ(𝑥𝑖),Φ(𝑥𝑗)⟩ s.t. 𝑛 ∑ 𝑖=1 𝛼𝑖𝑦𝑖= 0, 0≤𝛼𝑖≤𝐶∀𝑖= 1,2, ..., 𝑛 Se observa que solo aparecen los productos escalares ⟨Φ(𝑥𝑖),Φ(𝑥𝑗)⟩, por lo que no intervienen las componentes 𝜙𝑖de la inmersión. Esto hace que se pueda emplear el truco del kernel, o kernel trick, que consiste en introducir una función kernel 𝐾(𝑥𝑖, 𝑥𝑗), es decir una función que asigna a cada par de puntos el producto escalar de sus imágenes en el espacio de características; de modo que el problema dual quedaría definido de la siguiente forma: 38 Se usarán variables binarias 𝑐𝑘𝑡 para hacer un seguimiento de cada nodo, donde 𝑐𝑘𝑡 = 1 si 𝑐𝑡=𝑘, y 0 en caso contrario. Por lo tanto, en cada nodo que contenga algún punto, debemos hacer que tenga una sola etiqueta asignada, mientras que, si no contiene ningún punto, no se le asigne etiquetas. 𝐾 ∑ 𝑘=1 𝑐𝑘𝑡 =𝑙𝑡,∀𝑡∈𝑇𝐿 Ahora se define la pérdida óptima por la clasificación errónea en cada nodo, 𝐿𝑡, que será igual al número de puntos del nodo menos el número de puntos que tienen asignada la etiqueta más común: 𝐿𝑡=𝑁𝑡− m ax 𝑘=1,...,𝐾 𝑁𝑘𝑡 = m ın 𝑘=1,...,𝐾(𝑁𝑡−𝑁𝑘𝑡) lo cual puede linealizarse para obtener: 𝐿𝑡≥𝑁𝑡−𝑁𝑘𝑡 −𝑀(1 − 𝑐𝑘𝑡),∀𝑡∈𝑇𝐿, 𝑘 = 1, ..., 𝐾 𝐿𝑡≤𝑁𝑡−𝑁𝑘𝑡 −𝑀𝑐𝑘𝑡,∀𝑡∈𝑇𝐿, 𝑘 = 1, ..., 𝐾 𝐿𝑡≥0,∀𝑡∈𝑇𝐿 donde 𝑀es una constante suficientemente grande que, dependiendo del valor de 𝑐𝑘𝑡, puede hacer que la restricción esté inactiva. En este caso, 𝑀=𝑛es un valor válido. Por lo tanto, el coste total producido por los puntos que no están bien clasificados viene dado por ∑𝑡∈𝑇𝐿𝐿𝑡, y la complejidad del árbol 𝐶viene dada por el número de divisiones que se realizan en él, es decir, 𝐶=∑𝑡∈𝑇𝐵𝑑𝑡. Se normaliza la clasificación errónea por  𝐿, el cual se obtiene al predecir la clase más común de entre todos los datos del conjunto. Esto hace que el parámetro de complejidad 𝛼que aparecía en el método CART tenga un efecto independiente del tamaño de la muestra. Esto hace que la función objetivo del problema (10) se reescriba de la siguiente forma: m ın 1  𝐿∑ 𝑡∈𝑇𝐿 𝐿𝑡+𝛼𝐶 Considerando todo, hay tres parámetros que se necesitan especificar para la resolución del problema, la profundidad máxima D, el tamaño mínimo de las 45 hojas 𝑁𝑚𝑖𝑛, y el parámetro de complejidad 𝛼. Juntando esto con las restricciones vistas en este apartado, obtenemos el modelo OCT: min 1  𝐿∑ 𝑡∈𝑇𝐿 𝐿𝑡+𝛼𝐶 s.t. 𝐿𝑡≥𝑁𝑡−𝑁𝑘𝑡 −𝑛(1 − 𝑐𝑘𝑡) ∀𝑡∈𝑇𝐿, 𝑘 = 1, ..., 𝐾, 𝐿𝑡≤𝑁𝑡−𝑁𝑘𝑡 −𝑛𝑐𝑘𝑡 ∀𝑡∈𝑇𝐿, 𝑘 = 1, ..., 𝐾, 𝐿𝑡≥0 ∀𝑡∈𝑇𝐿, 𝑁𝑘𝑡 =∑ 𝑖∶𝑦𝑖=𝑘 𝑧𝑖𝑡 ∀𝑡∈𝑇𝐿, 𝑘 = 1, ..., 𝐾, 𝑁𝑡= 𝑛 ∑ 𝑖=1 𝑧𝑖𝑡 ∀𝑡∈𝑇𝐿, 𝐾 ∑ 𝑘=1 𝑐𝑘𝑡 =𝑙𝑡∀𝑡∈𝑇𝐿, 𝐶=∑ 𝑡∈𝑇𝐵 𝑑𝑡, 𝑎𝑇 𝑚𝑥𝑖≥𝑏𝑚−𝑀2(1 − 𝑧𝑖𝑡) ∀𝑖= 1, ..., 𝑛, 𝑡 ∈𝑇𝐿, 𝑚 ∈𝑅(𝑡), 𝑎𝑇 𝑚(𝑥𝑖+𝜀−𝜀𝑚𝑖𝑛) + 𝜀𝑚𝑖𝑛 ≤𝑏𝑚+ (1 + 𝜀𝑚𝑎𝑥)(1 − 𝑧𝑖𝑡) ∀𝑖= 1, ..., 𝑛;𝑡∈𝑇𝐿;𝑚∈𝐿(𝑡), ∑ 𝑡∈𝑇𝐿 𝑧𝑖𝑡 = 1 ∀𝑖= 1, ..., 𝑛, 𝑧𝑖𝑡 ≤𝑙𝑡∀𝑡∈𝑇𝐿, 𝑛 ∑ 𝑖=1 𝑧𝑖𝑡 ≥𝑁𝑚𝑖𝑛𝑙𝑡∀𝑡∈𝑇𝐿, 𝑝 ∑ 𝑗=1 𝑎𝑗𝑡 =𝑑𝑡∀𝑡∈𝑇𝐵, 0≤𝑏𝑡≤𝑑𝑡∀𝑡∈𝑇𝐵, 𝑑𝑡≤𝑑𝑝(𝑡),∀𝑡∈𝑇𝐵∖{1}, 𝑧𝑖𝑡, 𝑙𝑡, 𝑐𝑘𝑡 ∈ {0,1} ∀𝑖= 1, ..., 𝑛;𝑘= 1, ..., 𝐾;𝑡∈𝑇𝐵, 𝑎𝑗𝑡, 𝑑𝑡∈ {0,1},∀𝑗= 1, ..., 𝑝, 𝑡 ∈𝑇𝐵 46 Referencias [1] Aurélien Geron,Hands-On Machine Learning with Scikit-Learn & Tensor- Flow, 2017. [2] P. Hansen y B. Jaumard,Análisis de conglomerados y programación matemática. Programación Matemática, 79, 1997. [3] Ostrovsky, Chaitanya Swamy; Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya,The Effectiveness of Lloyd-Type Methods for the k-Means Problem. [4] Hernández C.,Diseño de un algoritmo heurístico para el problema de localización p-mediana, 2004. [5] C. Bielza & P. Larrañaga,Data-Drive Computational Neuroscience, Cambridge University Press, 2020. [6] S.L. Hakimi,Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, Volume 12, 450-459, 1964. [7] Gilbert Laporte, Stefan Nickel, Francisco Saldanha da Gama,Location Science, Volume 528, Springer, 2015. [8] A.A Kuehn y M.J. Hamburger,A heuristic program for locating warehouses, Management Science, Volume 9, 643-666, 1963. [9] E. Feldman y E.A. Lehrer y T.L. Ray,Warehouse locations under continuous economies of scale, Management Science, Volume 12, 670-684, 1966. [10] E.E Maranzana,On the location of supply points to minimize transport costs, Operational Research Quarterly, Volume 15, 261-270, 1964. [11] M.B. Teitz y E. Bart,Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations Research, Volume 16, 955-961, 1968. [12] S. Benati, S. García,A mixed integer linear model for clustering with variable selection, Computers & Operations Research 43, 280–285, 2014. [13] Michael W. Berry, Azlinah Mohamed, Bee Wah Yap,Supervised and Unsupervised Learning for Data Science, Springer International Publishing, 2020. 47 [14] Dimitris Bertsimas, Jack Dunn,Machine Learning under a Modern Optimization Lens, 2019. [15] B. E. Boser, I. M. Guyon, V. N. Vapnik,A training algorithm for optimal margin classifiers, in Proceedings of the Fifth Annual Workshop on Computational Learning Theory, ser. COLT ’92. New York, NY, USA: ACM, pp. 144–152, 1992. [16] Corinna Cortes, Vladimir Vapnik,Support-vector networks, Machine learning, 20(3), 1995. 48 Anexo En este último apartado se pretende visualizar la implementación en Python de algunos de los métodos vistos anteriormente, aplicándolos a algún ejemplo para que sea más ilustrativo. En concreto se verá el algoritmo de las K-medias y el de las K-medianas dentro de los métodos de clasificación no supervisada; y dentro de los de clasificación supervisada, se tratarán SVM y OCT. K-means En primer lugar, implementaremos el modelo de la K-media, el cual se ha efectuado, primero, con la función KMeans de la librería sklearn, la cual desarrolla directamente todo el modelo, y posteriormente se implementa el problema de optimización (1), observando que ambas maneras coinciden sobre una muestra de 20 elementos generada aleatoriamente. Este código genera los centroides de los tres clusters que se han pedido, en este 49 caso, sobre la muestra dada, y la asignación de cada punto al conglomerado correspondiente; así como una gráfica donde están representados los datos con un color diferente dependiendo del cluster al que pertenecen, y aparecen también más resaltados los centroides que se han obtenido. De esta manera, se obtiene la siguiente representación de la muestra: Ahora se tratará de ver con la implementación del problema (1) que se obtiene el mismo resultado. Para ello, se emplea la librería gurobipy para poder crear un problema de optimización con restricciones. Es necesario indicarle las variables de decisión, la función objetivo y las restricciones asociadas al problema para después resolverlo y devolver los resultados. Posteriormente, se creará el mismo ejemplo con la misma muestra y el mismo número de clusters utilizado en el código anterior para observar que la gráfica que proporciona el código coincide, salvo la asignación de colores a los conglomerados. 50 51 La representación de la muestra con los datos clasificados es la siguiente: Aunque los resultados que ofrecen ambos códigos son iguales, el primero es más óptimo y más rápido, lo cual hace que sea más efectivo. 52 K-mediana Para este modelo, se implementa el problema de optimización (2) de forma explícita, al igual que con el algoritmo de K-medias. En este caso, se toman 5 ubicaciones y se escogen aleatoriamente 21 nodos, a los que se les aplicará el modelo, el cual se define con el siguiente código: 53 A continuación, se observa una representación de los puntos en el plano: Y por último se presentan las aristas y los nodos seleccionados como ubicaciones, así como una gráfica con las asignaciones de los datos. 54