7 TIA Clustering.pdf

Tema 7 Técnicas de Inteligencia Artificial Clustering: Agrupamiento o clasificación no supervisada  Índice Esquema...

Tema 7 Técnicas de Inteligencia Artificial Clustering: Agrupamiento o clasificación no supervisada  Índice Esquema 3 Ideas clave 4 7.1. ¿Cómo estudiar este tema? 4 7.2. Conceptos. Tipos de algoritmos de clustering. Medida de distancia 4 7.3. Agrupamiento exclusivo. El algoritmo k-means 10 7.4. Agrupamiento jerárquico. Algoritmo de agrupamiento jerárquico aglomerativo 13 7.5. Agrupamiento probabilista. El algoritmo EM 20 © Universidad Internacional de La Rioja (UNIR) 7.6. Agrupamiento solapado. El algoritmo Fuzzy C- means 23 7.7. Aplicaciones y ejemplos de implementación 25 7.8. Referencias bibliográficas 35 A fondo 38 Test 42  Esquema © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 3 Tema 7. Esquema  Ideas clave 7.1. ¿Cómo estudiar este tema? Para estudiar este tema deberás leer las Ideas clave que se presentan a continuación. Puedes completar el estudio visualizando la lección magistral, revisando referencias y bibliografía, así como accediendo a los recursos adicionales que se facilitan. Es muy recomendable ver la lección magistral antes de realizar las actividades propuestas. Al finalizar el estudio de este tema el alumno será capaz de:  Describir los diferentes tipos de agrupamientos y los algoritmos representativos para obtener estos tipos.  Aplicar técnicas de clustering para la resolución de problemas de aprendizaje no supervisado.  Identificar aplicaciones prácticas de técnicas de clustering. 7.2. Conceptos. Tipos de algoritmos de clustering. Medida de distancia El clustering es uno de los métodos de aprendizaje no supervisado más importantes y, como cualquier otro método de aprendizaje no supervisado, busca caracterizar conceptos desconocidos a partir de instancias de los mismos. En este tipo de © Universidad Internacional de La Rioja (UNIR) problemas de aprendizaje no supervisado la clase es desconocida y es, precisamente el descubrimiento de esta clase el objetivo de este aprendizaje, a través de la agrupación de instancias en base a un esquema de similitud (Kaufman & Rousseeuw, 1990; Xu & Wunsch, 2009). Técnicas de Inteligencia Artificial 4 Tema 7. Ideas clave  Clustering Es un método de aprendizaje no supervisado que permite agrupar objetos en clústeres o agrupamientos, cuyos miembros son similares entre sí en cierto modo. Por lo tanto, el resultado de aplicar una técnica de clustering es una serie de agrupamientos o clústeres, los cuales son particiones de un conjunto de instancias. Clúster Es una colección de objetos similares entre sí y diferentes a los objetos que pertenecen a otros clústeres. Diferentes algoritmos de clustering pueden dar lugar a diferentes agrupamientos y no es siempre fácil determinar qué es un buen agrupamiento. La calidad de los agrupamientos creados dependerá de la aplicación final, por lo cual es el usuario el que determinará la calidad en base a si los agrupamientos creados son útiles y se ajustan a sus necesidades. Por lo tanto, según el objetivo del problema a tratar, habrá que seleccionar un algoritmo u otro. Por ejemplo, no es lo mismo tratar de detectar el espacio donde hay una mancha de combustible en el mar, espacio que puede tener una forma irregular, que el tratar de obtener agrupamientos circulares y de similar tamaño con el fin de segmentar un grupo de clientes para ofrecer productos. A continuación, se enumeran diferentes tipos de algoritmos de clustering en base al tipo de agrupamientos que producen:  Agrupamientos exclusivos. En este tipo de agrupamiento cada uno de los © Universidad Internacional de La Rioja (UNIR) clústeres tiene al menos un objeto y los objetos se agrupan de modo exclusivo, pudiendo pertenecer únicamente a un clúster. Los clústeres pueden generarse por métodos que agrupan los datos creando un número k determinado de clústeres. Técnicas de Inteligencia Artificial 5 Tema 7. Ideas clave  Generalmente estos métodos de partición utilizan una medida de distancia para generar los clústeres. Un ejemplo de este tipo es el algoritmo k-means (Qin et al., 2016). También hay otro tipo de algoritmos que típicamente generan clústeres exclusivos, tales como los métodos basados en la densidad que van incorporando nuevos objetos a un clúster si la densidad de objetos en «los alrededores» supera un umbral. Los algoritmos basados en densidad (en vez de en medidas típicas de distancia) son útiles para generar clústeres de formas irregulares. Algunos de los algoritmos que generan clústeres exclusivos más conocidos son mean-shift (Guo et al., 2018) y el DBSCAN (Density-based spatial clustering of applications with noise) o agrupamiento espacial basado en densidad de aplicaciones con ruido (Shen et al., 2016).  A Agrupamientos jerárquicos. Otro tipo de algoritmos son aquellos que dan lugar a una estructura jerárquica de clústeres. En el primer nivel de la jerarquía se tiene un único clúster que se divide en otros clústeres en una primera iteración. Cada uno de estos clústeres se divide a su vez y se van generando nuevos clústeres en siguientes iteraciones. Esta forma de crear los clústeres partiendo de un gran clúster que contenga todos los datos e irlo dividiendo para formar clústeres más pequeños se denomina aproximación divisoria. También existen algoritmos que generan clústeres en el sentido inverso, en este caso denominados aglomerativos, los cuales generan en primer lugar los clústeres más pequeños que se agrupan progresivamente para generar la estructura jerárquica (Bouguettaya et al., 2015). © Universidad Internacional de La Rioja (UNIR)  Agrupamientos solapados. En este tipo de clústeres los objetos se agrupan a través de conjuntos difusos, pudiendo cada objeto pertenecer a uno o más clústeres con diferentes grados de pertenencia. Un algoritmo que produce agrupamientos solapados es el algoritmo Fuzzy C-means (Qin et al., 2016). Técnicas de Inteligencia Artificial 6 Tema 7. Ideas clave   Agrupamientos probabilistas. Los clústeres se generan mediante un método probabilístico. Un ejemplo representativo es el algoritmo EM (Expectation- Maximization) (Gebru et al., 2016). El clustering se puede utilizar aisladamente con el fin de analizar agrupamientos y extraer conclusiones, pero también se utiliza como etapa previa a la aplicación de otras técnicas. Por ejemplo, se puede aplicar el clustering para detectar clases desconocidas, asignar etiquetas a las clases descubiertas correspondientes a los distintos grupos y, a continuación, aplicar una técnica de clasificación pare describir los grupos y realizar clasificaciones de instancias futuras desconocidas (G. Sreenivasulu et al., 2017). Algunos ejemplos de aplicaciones prácticas del clustering son: 1. Encontrar objetos representativos de grupos homogéneos. Por ejemplo:  En un sistema de aprendizaje en línea se pueden obtener agrupamientos de estudiantes que comparten características y comportamientos comunes en el estudio. Analizando cada grupo se pueden definir estrategias de enseñanza adecuadas a los diversos comportamientos similares, a priori desconocidos (Zakrzewska, 2009).  En un sistema de gestión de clientes, las técnicas de clustering pueden agrupar los diversos clientes en base a características comunes y permitir aplicar estrategias de marketing adecuadas a los diversos grupos, posicionar productos, etc. (Abbasimehr & Shabani, 2019; Chiang, 2018; Holý et al., 2017). © Universidad Internacional de La Rioja (UNIR) 2. Encontrar grupos y describirlos en base a sus propiedades. Por ejemplo, en biología, clasificación de plantas, o en medicina, clasificación de enfermedades raras (Nilashi et al., 2017b, 2017a; Pacheco & López, 2019). Técnicas de Inteligencia Artificial 7 Tema 7. Ideas clave  3. Detección de casos anómalos. Por ejemplo, en un sistema de detección de fraudes de tarjetas de crédito o de estafas a seguros, puede servir para detectar comportamientos de clientes que no encajan dentro de ningún agrupamiento y, por tanto, son comportamientos a analizar cuidadosamente, dado que podría tratarse de un fraude (Kumar et al., 2019; Subudhi & Panigrahi, 2017). Medida de distancia Las medidas de distancia son utilizadas en un importante número de algoritmos de clustering, puesto que muchos algoritmos se basan en medidas de distancia entre objetos para, en función de su «cercanía», incluirlos en el mismo clúster o en clústeres separados. Según la medida de distancia que se escoja, un algoritmo dará lugar a diferentes clústeres y, por tanto, seleccionar la medida de distancia apropiada es importante, aunque no siempre se puede saber a ciencia cierta cuál es la medida óptima. Es muy típicamente utilizada la medida de distancia euclídea, por ejemplo. Pero hay otro tipo de medidas muy utilizadas también típicamente por algoritmos de clustering no tan extendidas. A continuación, se describen algunas de estas medidas de distancia conocidas como linkage measures (medidas de conectividad): 1. Enlace sencillo (single-linkage). La similitud entre dos clústeres se calcula como la similitud de los dos puntos más cercanos pertenecientes a los diferentes clústeres. Así, se considera la distancia más pequeña existente entre uno de los puntos del primer clúster y otro del segundo (ver Figura 1). Siendo p y p’ los puntos en los que dos objetos se sitúan, y CA y CB, dos clústeres tal que p Є CA y p’ Є CB, la similitud se © Universidad Internacional de La Rioja (UNIR) calcula según la siguiente expresión: Técnicas de Inteligencia Artificial 8 Tema 7. Ideas clave  2. Enlace completo (complete-linkage). Caso opuesto al enlace sencillo ya que se tiene en cuenta la distancia mayor existente entre cualquier punto de uno y otro clúster (Ver Figura 2). Siendo p y p’ los puntos en los que dos objetos se sitúan, y CA y CB, dos clústeres tal que p Є CA y p’ Є CB, la similitud en este caso se calcula según la siguiente expresión: Figura 1. Enlace sencillo entre dos clústeres. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 9 Tema 7. Ideas clave  Figura 2. Enlace completo entre dos clústeres. Figura 3. Enlace promedio entre dos clústeres. 7.3. Agrupamiento exclusivo. El algoritmo k- means Los algoritmos más simples de clustering son los que dividen el conjunto de objetos en agrupaciones exclusivas de objetos teniendo como punto de partida el número de clústeres que se desea generar y midiendo la similitud de los objetos en base a una medida de distancia. El algoritmo más popular de este tipo es el algoritmo k-means. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 10 Tema 7. Ideas clave  Algoritmo K-means Es un método iterativo basado en distancia que define k centroides de los k clústeres que genera en cada iteración. Un objeto pertenece a un clúster o a otro en base a su distancia a los centroides de los distintos clústeres. El centroide de un clúster lo calcula como el valor medio de los puntos del clúster. 1. Selecciona k objetos del conjunto inicial de manera aleatoria o siguiendo alguna pauta como, por ejemplo, que los objetos estén lo más lejos posible uno de otros. Cada uno de estos k objetos representan cada uno de los centroides de los k clústeres. 2. El resto de los objetos se asigna al clúster cuyo centroide es más similar. Esta similitud se calcula mediante una medida de distancia entre el objeto y el centroide. En este paso ya se obtienen k agrupamientos o clústeres iniciales. 3. Para cada clúster generado en el paso previo, se recalcula la posición del centroide o media de los puntos. 4. Los pasos 2-3 se repiten hasta que las posiciones de los centroides no varían. Aunque el algoritmo k-means puede utilizar diversas medidas de distancia, típicamente utiliza la distancia euclídea que da buenos resultados en muchos problemas. Para ilustrar gráficamente la creación de estos clústeres, la Figura 4 muestra cinco agrupamientos, resaltados en diversos colores, generados por la herramienta Weka para un conjunto de datos bidimensionales. Se puede observar cómo efectivamente cada clúster presenta una serie de objetos que se agrupan alrededor de la media del mismo. Nótese que en este caso la visualización es muy clara porque los datos de entrada son bidimensionales. Sin embargo, cuando los datos tienen muchas dimensiones, es muy difícil interpretar los clústeres obtenidos a partir de una © Universidad Internacional de La Rioja (UNIR) visualización o análisis y, por tanto, se asigna una clase a cada clúster y se utilizan técnicas de aprendizaje supervisado para describir los mismos. Técnicas de Inteligencia Artificial 11 Tema 7. Ideas clave  Figura 4. Agrupamientos generados por k-means con la herramienta Weka. A la hora de utilizar el algoritmo k-means es difícil saber si se está escogiendo el valor k adecuado. Más aún, el algoritmo es sensible al posicionamiento inicial de los centros de los clústeres. Por tanto, en la práctica se suele ejecutar diversas veces para diversos valores de k y para diversos posicionamientos iniciales de los centroides. De cualquier manera, se ha de tener cuidado con valores altos de k que podrían dar lugar a problemas de overfitting o sobreentrenamiento. Una limitación del algoritmo es que solo trabaja con datos de valores reales. Solo se puede aplicar cuando el cálculo de la media de los objetos está definido y, por tanto, podría no ser aplicable cuando se manejan valores nominales. Una posible solución © Universidad Internacional de La Rioja (UNIR) es mapear el valor nominal a un valor numérico. Técnicas de Inteligencia Artificial 12 Tema 7. Ideas clave  A pesar de las limitaciones y dificultades expuestas, k-means es un método simple y relativamente escalable que en algunos problemas da muy buenos resultados. 7.4. Agrupamiento jerárquico. Algoritmo de agrupamiento jerárquico aglomerativo Existen problemas donde se desea obtener jerarquías de clústeres. Por ejemplo, en un comercio electrónico se puede desear organizar productos en agrupaciones genéricas y luego, dentro de esas agrupaciones, generar nuevas agrupaciones en base a similitudes entre los productos. Esto tiene el beneficio muchas veces de facilitar el análisis y la visualización de los datos. Los métodos de agrupamiento jerárquico trabajan de manera incremental, a diferencia del algoritmo k-means que en cada iteración trabaja con el conjunto completo de datos. Existen dos tipos de algoritmos jerárquicos: Algoritmos aglomerativos Algoritmos divisorios Crean la jerarquía en el sentido de abajo Crean la jerarquía en el sentido de arriba hacia arriba. Típicamente comienzan hacia abajo. Por tanto comienzan con un generando un clúster por cada objeto y, único clúster que contiene todos los objetos y los clústeres, se van iterativamente van particionando los clústeres agrupando entre sí, generando cada vez recursivamente en clústeres cada vez más clústeres de mayor número de pequeños. Finaliza cuando se cumple una elementos. Finalizan cuando se cumple determinada condición, como por ejemplo cierta condición, como alcanzar un que los objetos dentro de un clúster sean © Universidad Internacional de La Rioja (UNIR) determinado número de clústeres, o suficientemente similares, cuando se ha cuando se obtiene un único clúster con alcanzado un determinado número de todos los objetos que es el nodo raíz de la clústeres, o cuando cada clúster únicamente jerarquía. contiene un objeto. Técnicas de Inteligencia Artificial 13 Tema 7. Ideas clave  La Figura 5 muestra el sentido de cómo se dividen o agrupan los clústeres según se trate de un algoritmo divisorio o aglomerativo. Algoritmo divisorio Algoritmo aglomerativo a a b ab b cde c c d d c d e e Figura 5. Clustering jerárquico aglomerativo y divisorio. Como se aprecia en la Figura 5 estos algoritmos generan una estructura jerárquica en forma de árbol, siendo el nodo raíz el clúster que contiene el mayor número de elementos y los nodos hojas, los clústeres con menor número de elementos. Cuando se trabaja con algoritmos jerárquicos es frecuente encontrar la representación mostrada en la Figura 6 denominada dendograma. En esta Figura 6 se representa cómo se agrupan por niveles los objetos en cada iteración del algoritmo de clustering. Conforme el clúster tiene un mayor número de objetos, la similitud entre sus objetos disminuye. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 14 Tema 7. Ideas clave  - Nivel 4 Similitud Nivel 3 Nivel 2 + Nivel 1 a b c d e Nivel 0 Figura 6. Dendodrama representando la jerarquía correspondiente al ejemplo de la figura 5. Los algoritmos divisorios son menos frecuentes que los aglomerativos. Una dificultad que presentan es la decisión de cómo dividir un clúster con muchos elementos en clústeres más pequeños, puesto que las posibles combinaciones de diferentes clústeres a partir de un numeroso número de instancias son igualmente muy numerosas. En los métodos de agrupamiento jerárquico una decisión crucial es precisamente la decisión de en qué punto dividir o conglomerar (según se trate de algoritmos divisorios o aglomerativos respectivamente). La medida de la calidad de las particiones de los objetos en clústeres que se utiliza para tomar esta decisión se denomina utilidad de la categoría. © Universidad Internacional de La Rioja (UNIR) Se describe a continuación el funcionamiento de un algoritmo jerárquico aglomerativo básico basado en la medida del enlace sencillo (también pueden emplearse criterios de enlace completo, enlace medio (entre clústeres y dentro de los clústeres), método del centroide, de la mediana, etc.). Dado un conjunto de N puntos, el algoritmo procede de la siguiente forma: Técnicas de Inteligencia Artificial 15 Tema 7. Ideas clave  1. A cada punto se le asigna un clúster, de modo que inicialmente se tienen N clústeres de 1 elemento cada uno. 2. Se calcula la distancia entre los clústeres y, aquellos que estén más cercanos, se juntan en un único clúster. 3. Se calcula la distancia entre el nuevo clúster y el resto de clústeres. 4. Se repiten los pasos 2 y 3 hasta que todos los puntos estén agrupados en un único clúster. El cálculo en cada iteración de las distancias entre el nuevo clúster generado y el resto se puede realizar de diferentes formas, tales como a través de la medida de la distancia de enlace sencillo, enlace completo, promedio, etc. A continuación, se particulariza el algoritmo jerárquico expuesto previamente para el caso de emplear el enlace-sencillo como método para calcular la similitud entre clústeres. Se utiliza una matriz de similitud entre los distintos clústeres de dimensión inicial N×N, conteniendo las distancias entre los distintos puntos (por lo cual también se la denomina matriz de distancias), y los pasos son los siguientes: 1. Se comienza por el nivel 0 en el que se genera un clúster por cada uno de los N © Universidad Internacional de La Rioja (UNIR) puntos del conjunto inicial de instancias. 2. Se busca el par de clústeres CA y CB menos distantes teniendo en cuenta la medida de enlace sencillo entre cualquier emparejamiento de clústeres posible. Técnicas de Inteligencia Artificial 16 Tema 7. Ideas clave  3. Se unen los clústeres CA y CB en uno solo. 4. Se elimina de la matriz de proximidad las filas y columnas que corresponden a los clústeres CA y CB y se añade una columna y una fila para el nuevo clúster generado. La proximidad entre el nuevo clúster y los anteriores se recalcula mediante la medida de enlace sencillo. 5. Si todos los objetos están en un único clúster, el algoritmo finaliza. En caso contrario se continua en el paso 2. Se va a ilustrar a continuación el funcionamiento de este algoritmo con un ejemplo muy sencillo de un problema en el que se pretende generar una estructura de agrupamientos jerárquica a partir de unos datos bidimensionales. Las distancias entre estos datos se muestran en la matriz de similitud incluida en la Tabla 1. Tabla 1. Matriz de similitud de partida del ejemplo. En primer lugar, se crean tantos clústeres como objetos hay (ver Figura 7). A continuación, se busca el par de clústeres menos distantes entre sí, que son aquellos cuya distancia es menor. Según la matriz de la Tabla 1, los clústeres correspondientes © Universidad Internacional de La Rioja (UNIR) a los objetos u y w son los más cercanos, dando lugar al clúster que se denomina Cu- w (ver Figura 8). Técnicas de Inteligencia Artificial 17 Tema 7. Ideas clave  t s u w Iteración 1 t s u w Iteración 1 Cu_w Iteración 2 Figura 8. Iteración 2 del algoritmo de clustering. A continuación, se calcula la distancia de este nuevo clúster Cu-w con el resto de los clústeres, teniendo en cuenta la medida de enlace sencillo. Por tanto, habrá que tener en cuenta para calcular la distancia al resto de clústeres, la distancia del punto más cercano, sea w o u, al clúster objetivo. Así se obtiene la matriz de similitud mostrada en la Tabla 2. Tabla 2. Matriz de similitud del ejemplo (iteración 2). © Universidad Internacional de La Rioja (UNIR) En la siguiente iteración, la mínima distancia tal y como se observa en la Tabla 2, se encuentra entre el nuevo clúster generado Cu-w y el punto s. Por tanto, se unen ambos clústeres dando lugar al clúster Cu-w-s (ver Figura 9) y se recalcula la matriz de similitud obteniéndose la que se muestra en la Tabla 3. Técnicas de Inteligencia Artificial 18 Tema 7. Ideas clave  Tabla 3. Matriz de similitud del ejemplo (iteración 3). t s u w Iteración 1 Cu_w Iteración 2 Cu_w_s Iteración 3 Figura 9. Iteración 3 del algoritmo de clustering. Como último paso solo queda unir los dos únicos clústeres existentes generando un único clúster, y finalizando el algoritmo. El árbol generado se muestra en la figura 10. t s u w Iteración 1 Cu_w Iteración 2 Cu_w_s Iteración 3 © Universidad Internacional de La Rioja (UNIR) Cu_w_s_t Iteración 4 Figura 10. Árbol jerárquico resultante en la iteración 4 del algoritmo de clustering. Técnicas de Inteligencia Artificial 19 Tema 7. Ideas clave  El problema de estos métodos de clustering jerárquico es que no escalan bien según aumenta el número de puntos. Por otra parte, son métodos que en su forma básica no dan marcha atrás con lo cual se podría no encontrar la solución óptima. También ha de tenerse en cuenta que la elección del criterio marca un mejor o peor funcionamiento de la técnica. Así, el enlace simple proporciona clústeres encadenados mientras que el enlace completo produce clústeres más compactos y es menos sensible a outliers. Menos sensible aún a estos es el método del enlace medio o el método de cálculo de centroides (que tiene a formar clústeres compactos, igual tamaño y forma). 7.5. Agrupamiento probabilista. El algoritmo EM Los algoritmos basados en probabilidad, en vez de situar las instancias en clústeres de una manera exclusiva, indican la probabilidad de que las instancias pertenezcan a cada uno de los clústeres. La base de estos algoritmos es el modelo estadístico denominado mezclas finitas (finite mixtures). Una mezcla es un conjunto de k distribuciones de probabilidad que representan k clústeres. Esas distribuciones se refieren a los valores de los atributos de las instancias que pertenecen a un clúster. De este modo, si se conociera que una instancia es miembro de un clúster, las distribuciones mostrarían la probabilidad de que esa instancia tenga unos determinados valores de atributos. © Universidad Internacional de La Rioja (UNIR) En muchos problemas no todos los clústeres son iguales de probables, no tienen por qué tener el mismo número de individuos. Por este motivo, es necesario que también se refleje la distribución de la población entre los clústeres. Técnicas de Inteligencia Artificial 20 Tema 7. Ideas clave  Clustering probabilista Dado un conjunto de instancias con sus atributos, el problema que se presenta es conocer los parámetros que modelan el conjunto de k distribuciones de probabilidad para los k clústeres, así como la probabilidad de población, esto es, que el propio clúster tenga cierto número de instancias. ¿Cómo se pueden modelar estos clústeres y determinar dichos parámetros? Se puede utilizar un proceso similar al del algoritmo k-means. El algoritmo k-means itera con dos etapas: 1. A cada objeto se le asigna el clúster cuyo centroide está más cercano (los centroides en la primera iteración se suelen determinar aleatoriamente). 2. Una vez se asignan los objetos a cada clúster, se recalcula el centroide de tal manera que la suma de las distancias de los objetos asignados al clúster al centroide sea mínima. © Universidad Internacional de La Rioja (UNIR) Entonces se puede comenzar con valores «posibles» de esos parámetros que modelan los clústeres, tal y como se «adivina» el centroide en el algoritmo k-means en la primera iteración, y utilizar estos hipotéticos valores para calcular las probabilidades de que cada instancia esté en un clúster. En la segunda etapa se Técnicas de Inteligencia Artificial 21 Tema 7. Ideas clave  pueden utilizar estas probabilidades para reestimar los parámetros. Este proceso se repetiría iterativamente. Así funciona el algoritmo EM (Expectation – Maximization). Al igual que el algoritmo k-means, el algoritmo EM itera hasta que no se pueden mejorar los agrupamientos y cada iteración consta de dos etapas: 1. Esperanza (expectation): calcula las probabilidades de pertenencia de las instancias a los clústeres de acuerdo con los parámetros de los clústeres probabilísticos. 2. Maximización (maximization): determina los nuevos parámetros que maximizan la verosimilitud esperada en el anterior paso (expected likelihood). El algoritmo EM se puede utilizar siempre que se conozca o se estime una forma de la distribución probabilística (por ejemplo, se estima la distribución con forma de gaussiana y se pretende conocer los parámetros que modelan la gaussiana). Es habitual hablar en estos casos de algoritmos EM-GMM (Expectation-Maximitzation for Gaussian Mixture Models). En muchas aplicaciones el clustering probabilístico ha resultado efectivo dado que es más general que otros métodos de clustering. Específicamente el algoritmo EM se utiliza frecuentemente porque es simple. Sin embargo, presenta el problema de poder converger a un óptimo local y no global y podría llegar a tener un alto coste computacional si el número de distribuciones probabilísticas que es necesario modelar es elevado. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 22 Tema 7. Ideas clave  7.6. Agrupamiento solapado. El algoritmo Fuzzy C- means El algoritmo k-means agrupa las instancias en grupos exclusivamente. Sin embargo, mediante un algoritmo de agrupamiento solapado, como el algoritmo Fuzzy C-means, una instancia puede pertenecer a más de un grupo o clúster, con un determinado grado de pertenencia. El algoritmo Fuzzy C-means es un método muy utilizado para obtener clústeres solapados. Permite encontrar una serie de conjuntos difusos representativos de cada clúster y los grados de pertenencia de cada instancia a los mismos. El funcionamiento de este algoritmo es el siguiente. Dado un conjunto de objetos x1, x2,..., xi, …, xn, un agrupamiento de los mismos mediante k clústeres difusos C1, C2, …, Cj, …, CK se puede representar utilizando una matriz divisoria M = [pìj], tal que 1≤ i ≤ n y 1≤ j ≤ k, siendo pij el grado de pertenencia del objeto xi al clúster Cj. El algoritmo Fuzzy C-means se basa en minimizar la siguiente función objetivo: 1. m es un número real mayor o igual a 1 que gobierna la influencia de los grados de © Universidad Internacional de La Rioja (UNIR) pertenencia. 2. pij es el grado de pertenencia del objeto xi al clúster Cj incluido en la matriz divisoria antes mencionada. Técnicas de Inteligencia Artificial 23 Tema 7. Ideas clave  3. xi es la i-ésima instancia. 4. cj es el centro del clúster Cj que se puede calcular como la media, el centroide o cualquier otra fórmula adecuada al problema en concreto. 5. || || se refiere a cualquier medida relativa a la similitud entre la instancia y el centro del clúster. Los pasos que se siguen son: 1. Inicializar la matriz divisoria de manera aleatoria, pero cumpliendo que: 1. Cada valor asignado 𝑝𝑝𝑖𝑖𝑖𝑖 está entre 0 y 1. 2. Para cada objeto xi, se cumple © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 24 Tema 7. Ideas clave  Si no se cumple este criterio de parada el algoritmo vuelve al paso 2. El algoritmo Fuzzy C-means guarda similitud con el algoritmo EM, pero una diferencia importante es precisamente el tipo de clúster objetivo. Tanto k- means como Fuzzy C-means modelan los clústeres típicamente con forma circular, mientras que el algoritmo EM emplea funciones probabilísticas dando lugar a los clústeres probabilísticos modelados por funciones probabilísticas. 7.7. Aplicaciones y ejemplos de implementación Algunas aplicaciones de los algoritmos de clustering en la literatura Los algoritmos de clústering o agrupación se utilizan para segmentar el mercado en diferentes tipos de consumidores (especialmente útiles para ser utilizados más tarde para recomendar productos y fidelizar a los clientes) (Casabayó, Agell, y Sánchez- Hernández, 2015), compresión de imágenes (Hoeltgen & Breuß, 2018), analizar y etiquetar nuevos datos, detectar comportamientos anómalos como la detección de fraudes (Ahmed, Mahmood e Islam, 2016) detectar objetos a partir de datos de sensores (Li et al., 2018), o para mezclar puntos cercanos en un mapa (utilizado para facilitar la visualización de nodos en los mapas dependiendo del nivel de zoom) (Huang, Liu y Ling, 2019). Ejemplos de implementación mediante Python © Universidad Internacional de La Rioja (UNIR) En esta ocasión vamos a probar varios algoritmos de clustering utilizando Python y las librerías numpy, scikit-learn y matplotlib, que ya deberíamos tener todas instaladas de los ejemplos de los temas anteriores. No vamos a utilizar pandas, puesto que vamos a realizar pruebas generando datos sintéticos, es decir, en lugar de partir de un dataset real, aprenderemos a generar nuestros propios datos para realizar Técnicas de Inteligencia Artificial 25 Tema 7. Ideas clave  pruebas con los algoritmos. Para ello, nos basaremos en un ejemplo de Machine Learning Mastery (ver Webgrafía al final de este tema). Con el siguiente código creamos un dataset sintético de 1 000 muestras de datos con 2 características, las 2 con información (ninguna es redundante) y «etiquetadas» (aunque esto se lo ocultaremos a los algoritmos de clustering) en 3 clases diferentes, con un clúster por clase. Veremos en un gráfico similar a este las tres clases diferentes en función de las dos características (en los ejes X e Y), y con un color para cada clase. Vemos cómo cada una está distribuida en único clúster (aunque esto no tiene por qué ser así, si no lo fuera la dificultad del problema sería mayor para un algoritmo no supervisado): © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 26 Tema 7. Ideas clave  En primer lugar, vamos a probar algunos algoritmos de clustering exclusivo, como k-means, mean-shift y DBSCAN. Probemos el algoritmo k-means. En este algoritmo, le hemos de especificar a priori el número de clústeres que esperamos que haya. En este caso 3, pero podría ser algo que un supiéramos a priori. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 27 Tema 7. Ideas clave  Obtendremos la siguiente salida, bastante similar a lo esperado. Podemos realizar pruebas con un número diferente de clústeres esperado (dado que no se conocerían a priori, en muchas ocasiones) para ver los resultados que tendríamos. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 28 Tema 7. Ideas clave  Probemos ahora con mean shift. En este caso, no necesitamos especificar previamente el número de clústeres esperado. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 29 Tema 7. Ideas clave  Probemos ahora con el DBSCAN, utilizando para los hiperparámetros un valor épsilon de 0.3 y un número mínimo de elementos por clúster de 9: © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 30 Tema 7. Ideas clave © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 31 Tema 7. Ideas clave  Tal y como podemos ver, con este valor de épsilon el algoritmo no es capaz de diferenciar los tres clústeres, al no haber separación clara entre las fronteras de ellos, y los identifica como uno único clúster, aunque sí nos permite identificar outliers. Probemos con un valor de épsilon más pequeño, 0.2. © Universidad Internacional de La Rioja (UNIR) Vemos en este caso cómo el algoritmo ha conseguido diferenciar dos clústeres principales, además de otros secundarios. Técnicas de Inteligencia Artificial 32 Tema 7. Ideas clave  Veamos ahora como ejemplo de clustering jerárquico el clustering aglomerativo, eligiendo un número de clústeres esperado de 3: © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 33 Tema 7. Ideas clave  Finalmente, probemos con un algoritmo probabilista basado en GMM (Gaussian Mixture Model) eligiendo de antemano que se prevén 3 componentes: © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 34 Tema 7. Ideas clave  7.8. Referencias bibliográficas Abbasimehr, H. & Shabani, M. (2019). A new methodology for customer behavior © Universidad Internacional de La Rioja (UNIR) analysis using time series clustering: A case study on a bank’s customers. Kybernetes. Disponible en https://doi.org/10.1108/K-09-2018-0506 Técnicas de Inteligencia Artificial 35 Tema 7. Ideas clave  Chiang, W.Y. (2018). Applying data mining for online CRM marketing strategy: An empirical case of coffee shop industry in Taiwan. British Food Journal, 120(3), 665- 675. Disponible en https://doi.org/10.1108/BFJ-02-2017-0075 G. Sreenivasulu, Raju, S. V. & Rao, N. S. (2017). Review of Clustering Techniques. En S. C. Satapathy, V. Bhateja & A. Joshi (Eds.), Proceedings of the International Conference on Data Engineering and Communication Technology (pp. 523-535). Springer. Disponible en https://doi.org/10.1007/978-981-10-1675-2_52 Holý, V., Sokol, O. & Černý, M. (2017). Clustering retail products based on customer behaviour. Applied Soft Computing, 60, 752-762. Disponible en https://doi.org/10.1016/j.asoc.2017.02.004 Kaufman, L. & Rousseeuw, P. J. (1990). Finding groups in data: An introduction to cluster analysis. Wiley. Kumar, M. S., Soundarya, V., Kavitha, S., Keerthika, E. S. & Aswini, E. (2019). Credit Card Fraud Detection Using Random Forest Algorithm. 2019 3rd International Conference on Computing and Communications Technologies (ICCCT), pp. 149-153. Disponible en https://doi.org/10.1109/ICCCT2.2019.8824930 Nilashi, M., Ibrahim, O. bin, Ahmadi, H. & Shahmoradi, L. (2017a). An analytical method for diseases prediction using machine learning techniques. Computers & Chemical Engineering, 106, 212-223. Disponible en https://doi.org/10.1016/j.compchemeng.2017.06.011 Nilashi, M., Ibrahim, O., Ahmadi, H. & Shahmoradi, L. (2017b). A knowledge-based © Universidad Internacional de La Rioja (UNIR) system for breast cancer classification using fuzzy logic method. Telematics and Informatics, 34(4), 133-144. Disponible en https://doi.org/10.1016/j.tele.2017.01.007 Técnicas de Inteligencia Artificial 36 Tema 7. Ideas clave  Pacheco, W. D. N. & López, F. R. J. (2019). Tomato classification according to organoleptic maturity (coloration) using machine learning algorithms K-NN, MLP, and K-Means Clustering. 2019 XXII Symposium on Image, Signal Processing and Artificial Vision (STSIVA), pp. 1-5. Disponible en https://doi.org/10.1109/STSIVA.2019.8730232 Subudhi, S. & Panigrahi, S. (2017). Use of optimized Fuzzy C-Means clustering and supervised classifiers for automobile insurance fraud detection. Journal of King Saud University - Computer and Information Sciences. Disponible en https://doi.org/10.1016/j.jksuci.2017.09.010 Xu, R. & Wunsch, D. C. (2009). Clustering. Wiley: IEEE Press. Zakrzewska, D. (2009). Cluster Analysis in Personalized E-Learning Systems. En N. T. Nguyen & E. Szczerbicki (Eds.), Intelligent Systems for Knowledge Management (pp. 229-250). Springer. Disponible en https://doi.org/10.1007/978-3-642-04170-9_10 © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 37 Tema 7. Ideas clave  A fondo Algoritmos de clustering en Weka Esta lección magistral consiste en un tutorial sobre los algoritmos de clustering disponibles en Weka. Se mostrarán algunos ejemplos de ejecución, parámetros configurables e interpretación de las salidas obtenidas. Accede a la lección magistral a través del aula virtual Demostración de k-means mediante un ejemplo de cartas de póker Este vídeo muestra de una manera muy didáctica el funcionamiento del algoritmo k- means, mediante un ejemplo en el que se clasifican cartas de póker. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 38 Tema 7. A fondo  Accede al vídeo desde el aula virtual o a través de la siguiente dirección web: https://www.youtube.com/watch?v=zHbxbb2ye3E Agrupamientos solapados, clustering difuso Presentación que explica el algoritmo Fuzzy C-means, así como el algoritmo k-means, incluyendo ejemplos detallados de las distintas iteraciones de los algoritmos. Finaliza con una comparación de ambas técnicas. Accede al vídeo desde el aula virtual o a través de la siguiente dirección web: https://www.youtube.com/watch?v=9yNtJsFxDQI Métodos jerárquicos de análisis clúster Capítulo de la asignatura Ampliación de Análisis de Datos Multivariantes del Departamento de Estadística e Investigación Operativa de la Universidad de Granada, relativo a los algoritmos de clustering jerárquico. Describe diferentes métodos jerárquicos aglomerativos que emplean diversas estrategias para medir la similitud entre objetos con ejemplos ilustrativos que facilitan la comprensión. © Universidad Internacional de La Rioja (UNIR) Accede al artículo desde el aula virtual o a través de la siguiente dirección web: http://www.ugr.es/~gallardo/pdf/cluster-3.pdf Técnicas de Inteligencia Artificial 39 Tema 7. A fondo  Demostraciones del algoritmo EM Wiki del organismo SOCR (Statistics Online Computational Resource) que propone actividades para experimentar con el algoritmo EM con el fin de obtener clústeres a partir de puntos en espacios de 1D, 2D y 3D, haciendo uso de la herramienta SOCR, que se puede ejecutar a través de esta misma página. Accede a la wiki desde el aula virtual o a través de la siguiente dirección web: http://wiki.stat.ucla.edu/socr/index.php/SOCR_EduMaterials_Activities_2D_PointS egmentation_EM_Mixture Scikit-learn La sección 2.3 sobre algoritmos de clustering en la documentación de scikit-learn es excepcional. Incluye muestras gráficas de las formas de los resultados de los clústeres para diez de los algoritmos de clustering más conocidos, códigos de ejemplo, bibliografía donde se detalla cada algoritmo, así como tablas comparativas que nos recomiendan qué algoritmo conviene emplear en cada caso. Accede a la página desde el aula virtual o a través de la siguiente dirección web: https://scikit-learn.org/stable/modules/clustering.html © Universidad Internacional de La Rioja (UNIR) Machine Learning Mastery Portal web creado por Jason Brownlee enfocado al aprendizaje de técnicas de machine learning. Ofrece sus libros en formato eBook (de pago) con diferentes niveles de precios en función de los contenidos incluidos. No obstante, incluye Técnicas de Inteligencia Artificial 40 Tema 7. A fondo  entradas en su blog (sin coste alguno) con ejemplos prácticos paso a paso muy interesantes de aplicación de técnicas de machine learning aplicadas mediante Python. Accede a la página desde el aula virtual o a través de la siguiente dirección web: https://machinelearningmastery.com/ © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 41 Tema 7. A fondo  Test 1. Indica cuáles de las siguientes afirmaciones son correctas: A. El clústering permite agrupar objetos similares entre sí. B. El clústering es un método de aprendizaje supervisado. C. El clústering puede resultar útil como etapa previa a la aplicación de un método de aprendizaje supervisado. D. El clústering da lugar a árboles de decisión. 2. Indica cuál de las siguientes afirmaciones es correcta: A. Diferentes algoritmos de clústering dan lugar a los mismos agrupamientos finales. B. Los algoritmos jerárquicos aglomerativos generan clústeres pequeños que iterativamente van agrupando entre sí. C. Los agrupamientos solapados se obtienen aplicando algoritmos de clústering jerárquicos. D. Los algoritmos de clústering no permiten detectar datos anómalos. 3. Si se pretende generar agrupamientos exclusivos se ha de aplicar: A. Algoritmo Fuzzy C-means. B. Algoritmo k-means. C. Algoritmo EM. D. Ninguno de los anteriores. 4. Si se pretende crear agrupamientos con formas irregulares se ha de aplicar: A. Algoritmo k-means. © Universidad Internacional de La Rioja (UNIR) B. Algoritmos basados en densidad. C. Algoritmo Fuzzy C-means. D. Ninguno de los anteriores. Técnicas de Inteligencia Artificial 42 Tema 7. Test  5. Si se pretende modelar los clústeres mediante una función probabilista se ha de aplicar: A. Algoritmo Fuzzy C-means. B. Algoritmo k-means. C. Algoritmo EM. D. Ninguno de los anteriores. 6. Si se mide la similitud entre dos clústeres mediante la medida de enlace completo: A. Se tiene en cuenta la similitud entre los dos puntos más cercanos de ambos clústeres. B. Se tiene en cuenta la similitud entre los dos puntos más lejanos de ambos clústeres. C. Se tiene en cuenta la distancia promedio que existe entre todos los puntos de ambos clústeres. D. Se tiene en cuenta la distancia entre los centroides de ambos clústeres. 7. Indica cuáles de las siguientes afirmaciones, respecto del algoritmo k-means, son correctas: A. El algoritmo k-means asigna los objetos a los clústeres en función de su cercanía al centroide de cada clúster. B. En cada iteración el algoritmo k-means mantiene fijos los centroides. C. Es un algoritmo basado en densidad. D. En cada iteración el algoritmo recalcula los centroides. 8. Indica cuáles de las siguientes afirmaciones, respecto a los algoritmos de clústering jerárquicos, son correctas: A. Se utiliza la medida de utilidad de la categoría para realizar particiones. © Universidad Internacional de La Rioja (UNIR) B. En un algoritmo divisorio inicialmente a cada clúster se le asigna un objeto. C. Utilizan una matriz de similitud para llevar a cabo la decisión de agrupar clústeres. D. Se puede utilizar la medida de enlace promedio para calcular las distancias entre clústeres. Técnicas de Inteligencia Artificial 43 Tema 7. Test  9. Indica cuáles de las siguientes afirmaciones son correctas respecto al algoritmo EM: A. Es un algoritmo basado en densidades. B. Tiene como base el modelo estadístico denominado mezclas finitas. C. El objetivo es conocer los parámetros de una función probabilista general que modela los clústeres. D. En la fase de esperanza se calculan las probabilidades de pertenencia de las instancias a los clústeres. 10. Indica cuáles de las siguientes afirmaciones son correctas respecto al algoritmo Fuzzy C-means: A. Una instancia puede pertenecer a más de un clúster si se aplica el algoritmo Fuzzy C-means. B. Las variables de entrada son conjuntos difusos. C. Los clústeres se modelan como conjuntos difusos. D. Permite obtener clústeres jerárquicos. © Universidad Internacional de La Rioja (UNIR) Técnicas de Inteligencia Artificial 44 Tema 7. Test