computacion inteligente clustering fuzzy. 2 contenido conceptos basicos tipos de clustering tipos...
TRANSCRIPT
Computacion inteligente
Clustering Fuzzy
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
Conceptos basicos
4
¿Que es el clustering? Hallar grupos de objectos tales que los objectos
en un grupo sean similares (o relacionados) a otros y diferentes (o no relacionados) a los objectos en otros grupos
Las distancias Inter-grupo son grandes
Las distancias Intra-grupo son cortas
5
Ejemplo de unos datosSpecies Fat (%) Proteins
(%)HorseDonkeyMuleCamelLlamaZebraSheepBuffaloFoxPigRabbitRatDeerReindeerWhale
1.01.41.83.43.24.86.47.95.95.1
13.112.619.720.321.2
2.61.72.03.53.93.05.65.97.46.67.1
12.39.2
10.411.1
Composicion de la leche en
algunos mamiferos
6Ejemplo de datos agrupados
Composicion de la leche en mamiferos
Fat (%)
Proteins(%)
Classes
7
¿Que es el clustering?
En los datos de entrenamiento no se da a priori pertenencia a ninguna clase.
Es decir, es un metodo de exploracion de los datos
Pattern
Feature space
Buscamos patrones o una estructura en los datos de interes
8
¿Que es el clustering? Una forma de aprendizaje no supervisado
No se tienen ejemplos de cómo deben ser agrupados
Clustering = agrupamiento
Pattern
Feature space
9Representacion de los patrones ¿Que caracteristicas usar?
Normalmente, ninguna guia teorica que sugiera los patrones apropiados y las caracteristicas a usar en una situacion especifica
El usuario generalmente debe proporcionar esta guia
Un analisis cuidadoso de las caracteristicas disponibles puede conducir a mejores resultados
11Representacion de los patrones Dos agrupamientos para unos mismos
datos
Agrupamiento por color Agrupamiento por forma
12La nocion de grupo puede ser ambigua
¿Cuantos grupos?
Cuatro Clusters Dos Clusters
Seis Clusters
Tipos de Clustering
14
Tipos de Clustering Clustering jerarquico
Un conjunto de clusters anidados organizados como un arbol jerarquico con un cluster unico arriba, agrupando todos los datos, y clusters con un solo elemento abajo
p4p1
p3
p2
p4 p1
p3
p2
p4p1 p2 p3
p4p1 p2 p3
15
Tipos de Clustering Clustering particional
Una division de los datos en subconjuntos (clusters) en una particion en un unico nivel (no anidado)
Puntos originales Clustering particional
16Otras distinciones entre agrupamientos
Fuzzy versus no-fuzzy
En el clustering fuzzy, un dato pertenece a cada grupo con algun valor de pertenencia entre 0 y 1
El valor de las funciones de pertenencia debe sumar 1
17Otras distinciones entre agrupamientos
Exclusivo versus no-exclusivo
En un clustering no-exclusivo los datos pueden pertencer a multiples clusters.
Parcial versus completo
En algunos casos, solo deseamos agrupar algunos de los datos
Tipos de clusters
19
Tipos de clusters Grupos bien-separados
Grupos basados en un centro
Grupos por contiguidad
Grupos basados en la densidad de los datos
Por una propiedad o conceptuales
Descritos por una funcion objectivo
20Tipos de clusters: bien separados Clusters bien-separados:
3 clusters bienseparados
21Tipos de clusters: basados en un centro basados en un centro
El centro del cluster es a menudo un centroide, el promedio de todos los datos en el grupo, o una mediana, el dato mas “representativo” del grupo
4 clusters basados en un centro
22Tipos de clusters: basados en un centro basados en un centro
La representacion del centroide trabaja bien si los clusters forman una hiper-esfera.
Si los clusters presentan una elongacion o tienen otra forma, los centroides posiblemente no son suficientes
4 clusters basados en el centro
23Tipos de clusters: clusters contiguos Clusters contiguos (el vecino mas
cercano o transitivos) Un cluster es un conjunto de puntos tal que un
punto en un cluster esta mas cercano (o es mas similar) a uno u otros puntos dentro del cluster que a cualquiera en otro cluster.
8 clusters contiguos
24Tipos de clusters: basados en la densidad Basados en la densidad
Un cluster es una region densa de puntos, separado por regiones de menor densidad de otras de mayor densidad.
Usados cuando los clusters son irregulares o entrelazados, y cuando existe ruido o datos extraños.
6 clusters basados en la densidad
25Tipos de clusters: conceptuales Clusters conceptuales
Clusters que comparten alguna propiedad en comun o representan un concepto particular
2 Circulos traslapados
26Definidos por una funcion objectivo Clusters definidos por una funcion
objectivo
Clusters que minimizan o maximizan una funcion objectivo.
Se evalua cada conjunto de clusters potencial usando una funcion objetivo
La tarea del clustering
29Componentes del Clustering Representacion de los datos
Numero, tipo, y escala de las caracteristicas disponibles para el algoritmo
Numero de clases y datos disponibles
Definicion de la medida de proximidad
Definida para pares de datos Medidas de distancia y similaridades
conceptuales
30
La tarea del clustering Introducir una medida de la distancia, D, (o
una medida de la similaridad o proximidad) entre las muestras o patrones.
32
Calidad del agrupamiento Un buen metodo de clustering producira
clusters de alta calidad con
Alta similaridad intra-clase Baja similaridad inter-clase
La calidad de un agrupamiento depende de la medida de la similaridad usada por el metodo, y de su implementacion
Nociones basicas en el clustering
particional
El conjunto de datos
Los datos son observaciones de algun proceso fisico.
Cada observacion consiste de n variables medidas
Agrupadas en vectores columna
El conjunto de datos
El conjunto de datos El conjunto de N observaciones en una matriz
Columnas = observaciones Filas = caracteristicas
El conjunto de datos Por ejemplo: canicas de distinto color:
Columnas = observaciones Filas = caracteristicas
Agrupamiento por color
Clusters
Un cluster es un grupo de objetos que son mas similares que otros que son miembros de otros clusters
Similaridad = distancia (espacios metricos)
Prototipos
Prototipo: referente del cluster. Con respecto al prototipo se hace la medida de la distancia
Grupos basados en el centroide
Prototipos
Usualmente los prototipos no se conocen de antemano
Pueden ser: Subespacios funciones
Metodos de hacer clustering
Según el tipo de subconjuntos
Hard clustering: subconjuntos clasicos
Fuzzy clustering: la pertenencia a un cluster tiene grados
Particion HARD Una particion HARD de Z es una familia de
subconjuntos Ai con las siguientes propiedades
La matriz de la particion En terminos de las funciones de
pertenencia
11 21 1
21 22 2
1
N
N
c cN
U
Fila i = funciones de pertenencia al conjunto Ai de Z
La matriz de la particion Por ejemplo: canicas de distinto color:
Agrupamiento por color
11 21 1
21 22 2
1
N
N
c cN
U
Condiciones de la matriz U Los elementos de U deben satisfacer
El espacio de particionamiento Hard
El cojunto de todas las posibles matrices de particion para Z
es el espacio de particionamiento
Ejemplo: Un conjunto de datos en R2
Dos clusters
Dos elementos extraños
Ejemplo: Un conjunto de datos en R2
Una posible particion Hard
z5 y z6 se han asigando a A1
Particion fuzzy Una particion fuzzy de Z es una familia de
subconjuntos Ai con las siguientes propiedades
La matriz de la particion fuzzy En terminos de las funciones de
pertenencia
11 21 1
21 22 2
1
N
N
c cN
U
11 21 1
21 22 2
1
N
N
c cN
U
Fila i = funciones de pertenencia al conjunto Ai de Z
Condiciones de la matriz U fuzzy Los elementos de U fuzzy satisfacen
Espacio de particionamiento fuzzy
El cojunto de todas las posibles matrices de particion para Z
Ejemplo: Una posible particion fuzzy
Particion restringida
z5 y z6 se han asigando por igual a A1 y A2
55
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 . . .