1 Computacion inteligente Clustering Fuzzy

2 2 Contenido  Conceptos basicos  Tipos de clustering  Tipos de Clusters  La tarea del clustering  Nociones basicas en el clustering particional  Clustering Fuzzy de las c-medias  El algoritmo  Parametros del algoritmo  Algoritmo de Gustafson-Kessel  Validacion de los clusters  Ejemplo de aplicación

3 Clustering Fuzzy de las c-medias

4 El algoritmo de clustering  El clustering de las c-medias es un proceso de optimizacion. Dada la matriz Z, encontrar: el numero de clusters K, La matriz de particion U, la matriz de prototipos V,  basado en, la minimizacion de una funcion objetivo, (Dunn, 1974; Bezdek, 1981):

5 El proceso de optimizacion  Minimizar:  Sujeto a las restricciones impuestas a la matriz U.

6 Optimizacion: condiciones sobre U  Los elementos de U fuzzy satisfacen

7 Medida de la distancia  La norma de la distancia es distinta para cada direccion  La matriz A es comun a todos los clusters La norma influye en el criterio de agrupamiento

8 Optimizacion de la funcion objetivo  Definiendo Hacer cero los gradientes de J con respecto a U, V, y : Multiplicadores de Lagrange

9 El algoritmo FCM (fuzzy c-means)  Se puede demostrar que, si m>1, en el optimo: Un prototipo es la media pesada de los miembros del cluster

10 El algoritmo FCM (fuzzy c-means)  Se puede demostrar que, si m>1, en el optimo: El grado de pertenencia es mayor para el cluster del prototipo más cercano

11 El algoritmo FCM (fuzzy c-means)  El algoritmo busca iterativamente encontrar

12 El algoritmo

13 Pasos del algoritmo c-means After King, 2000

14 El algoritmo FCM (fuzzy c-means)  Paso 1: inicializacion Escoger el numero de clusters c < N Escoger el exponente m, Escoger la matriz A, Selccionar la tolerancia para terminar la iteracion Inicializar la matriz de particion U aleatoriamente.

15 El algoritmo FCM (fuzzy c-means)  Paso 2:calcular los prototipos  Paso 3:calcular las distancias

16 El algoritmo FCM (fuzzy c-means)  Paso 4: actualizar la matriz de particion  Paso 5: verificar

17 Parametros del algoritmo

18 El Parametro de Fuzificacion m  Influye significativamente en la “fuzificacion” de la particion resultante m=1 particion hard m → ∞, particion completamente fuzzy m=2valor tipico Estas propiedades son independientes del metodo de optimizacion

19 Medidas de las Distancias: la matriz A  Teniendo en cuenta las varianzas en las diferentes direcciones

20 Medidas de las Distancias: la matriz A  Teniendo en cuenta la matriz de covarianza  Esta es la Norma de Mahalanobis

21 Diferentes medidas de la distancias La norma influye en el criterio de agrupamiento

22 Algoritmo de Gustafson-Kessel

23 Algoritmo de Gustafson-Kessel (1979)  La norma de la distancia es distinta para cada cluster  Cada cluster tiene su propia matriz A i

24 Norma del algoritmo de Gustafson- Kessel

25 Validacion de los clusters

26  La validez del agrupamiento se refiere al problema si una partición fuzzy dada se ajusta a los datos. El algoritmo de clustering siempre intenta encontrar el mejor ajuste para un número fijo de clusters y las formas parametrizada de los clusters. Sin embargo, esto no significa que aun el mejor ajuste sea significativo.

27 Validacion de los clusters  El número de clusters podría estar equivocado, o  la forma de los clusters podría no corresponder al de los grupos en los datos. Si es que los datos pueden agruparse de una manera significativa

28 Validacion del numero de clusters  ¿Cómo determinar el numero apropiado de clusters? Coeficiente de particion, Fmaximizar Entropia de la particion, Hminimizar Exponente de proporcion, Pmaximizar Estas medidas se calculan despues de completar el clustering

29 Validacion: coeficiente de particion F=1 es crisp F=1/c significa que cada observacion tiene grado de pertenencia igual a 1/c a cada cluster

30 Validacion: entropia de la particion H=0 es crisp H=ln(c) significa que cada observacion tiene grado de pertenencia igual a 1/c a cada cluster

31 Validacion: exponente de proporcion P=  is crisp P=0 significa que cada observacion tiene grado de pertenencia igual a cada cluster

32 Xie-Beni index (1991)  Minimizar

33 De los resultados de la validacion  Ningún índice de validacion es fiable por si solo  y el óptimo puede descubrirse sólo en comparación con los resultados de otros. Los resultados dependen de la estructura de los datos

34 De los resultados de la validacion  Se considera que particiones con menos clusters son mejores,  cuando las diferencias entre los valores de un índice de validacion son menores. En general los indices son monotonicamente decrecientes con c y no relacionados directamente con los datos.

35 Ejemplo de aplicacion

36 Extraccion de las reglas fuzzy por clustering: Modelo directo After Babuska

37 Extraccion de las reglas fuzzy por clustering: Modelo inverso After Babuska

38 38 Fuentes  Robert Babuska. Course Fuzzy and Neural Control, 2001/2002.  Kevin M. Passino, Stephen Yurkovich, Fuzzy Control. Addison Wesley Longman, Inc. 1998  Jonathan R. King, New Applications of Fuzzy Logic. University of East Anglia, Norwich England. PHD thesis, december 2000  Otras...