Computacion inteligente
Fuzzy Clustering
Contenido Clustering Fuzzy de las c-medias El algoritmo Parametros del algoritmo Ejemplos de aplicación
Clustering Algorithms
Clustering Fuzzy de las c-medias
El algoritmo de clustering El clustering c-means 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):
El proceso de optimizacion Minimizar:
Sujeto a las restricciones impuestas a la matriz U.
Optimizacion: condiciones sobre U Los elementos de U fuzzy satisfacen
Medida de la distancia La norma de la distancia es distinta para
cada direccion
La matriz A es comun a todos los clusters
Medida de las DistanciaNorma euclidiana
Norma del producto interno
Diferentes medidas de la distancias
La norma influye en el criterio de agrupamiento
Optimizacion: la funcion objetivo Definiendo
Hacer cero los gradientes de J con respecto a U, V, y
k : Multiplicadores de Lagrange
El algoritmo FCM (fuzzy c-means) Se puede demostrar que, si m>1
El algoritmo
Pasos del algoritmo c-means
After King, 2000
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.
El algoritmo FCM (fuzzy c-means) Paso 2:calcular los prototipos
Paso 3:calcular las distancias
El algoritmo FCM (fuzzy c-means) Paso 4: actualizar la matriz de particion
Paso 5: verificar
Parametros del algoritmo
Validacion del numero de clusters
¿Cómo determinar el numero apropiado de clusters?
Coeficiente de particion, F maximizar Entropia de la particion, H minimizar Exponente de proporcion, P maximizar
Estas medidas se calculan despues de completar el clustering
Validacion: coeficiente de particion
11
1 1
2
Fcn
Fn
k
c
i
ik
F=1 es crispF=1/c significa que cada observacion tiene
grado de pertenencia igual a 1/c a cada cluster
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
cHn
Hik
n
k
c
iik
ln0 ln1
1 1
Validacion: exponente de proporcion
)!(!
!
jcj
c
j
c
P= is crispP=0 significa que cada observacion tiene grado de pertenencia igual a cada cluster
maxk ikc
Xie-Beni index (1991) Minimizar
El Parametro de Fuzificacion m
Influye significativamente en la fuzificacion de la particion resultante
m=1 particion hard m →∞, particion completamente fuzzy
m=2 valor tipico
Estas propiedades son independientes del metodo de optimizacion
1ik c
Medidas de las Distancias: la matriz A
Teniendo en cuenta las varianzas en las diferentes direcciones
Medidas de las Distancias: la matriz A
Teniendo en cuenta la matriz de covarianza
Norma de Mahalanobis
Diferentes medidas de la distancias
La norma influye en el criterio de agrupamiento
Algoritmo de Gustafson-Kessel (1979) La norma de la distancia es distinta para
cada cluster
Cada cluster tiene su propia matriz Ai
Algoritmo de Gustafson-Kessel
Ejemplos de aplicacion
Extraccion de las reglas por clustering: Modelo
After Babuska
Extraccion de las reglas por clustering: Modelo inverso
After Babuska
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