Upload
cesar-feo
View
9
Download
1
Embed Size (px)
Citation preview
Dr. Francisco J. Mata1
Detección automática de grupos(“clustering”)
Tema 7Parte teórica
Dr. Francisco J. Mata 2
Detección automática de grupos
Encontrar patrones en los datos
Dividir el conjunto de datos en segmentos o grupos de acuerdo con un concepto de similitud
Dr. Francisco J. Mata 3
Detección automática de grupos
Técnica de minería de datos de aprendizaje sin supervisión
Aprendizaje por observación en lugar de por casos
Requiere inteligencia humana para interpretar resultados
Dr. Francisco J. Mata 4
Luminosidad y temperatura de las estrellas
Dr. Francisco J. Mata 5
Grupos de gentes
Dr. Francisco J. Mata 6
Grupos de gentes Forma usual de segmentar gente
es a través de reglas de negocio basadas en el sentido común
Detección automática de grupos permite agrupar a la gente directamente en sus características (datos)
Dr. Francisco J. Mata 7
Grupos y mercadeo
Dr. Francisco J. Mata 8
Grupos y medidas de uniformes
Dr. Francisco J. Mata 9
Algoritmos de detección de grupos
También conocidos como algoritmos de agrupación o de “cluster analysis”
Utilizan el concepto de asociación entre entidades sobre la base de similitud
La similitud se mide en términos de distancia
Dr. Francisco J. Mata 10
Algoritmo de k-medias El más comúnmente utilizado Desarrollado por J.B. MacQueen en
1967 Genera k grupos o “clusters” de
objetos
Dr. Francisco J. Mata 11
Algoritmo de k-medias Asume una representación
geométrica de los datos Registros o tuples son puntos en un
espacio de datos n-dimensional Asume que hay K grupos
Dr. Francisco J. Mata 12
Selección de K semillas al azar
Dr. Francisco J. Mata 13
Asignación de los puntos al centroide más cercano
Dr. Francisco J. Mata 14
Cálculo de centroides para los grupos
Dr. Francisco J. Mata 15
Nueva asignación de grupos
Dr. Francisco J. Mata 16
Proceso iterativo Proceso se repite iterativamente
hasta que se encuentran grupos que son estables
Dr. Francisco J. Mata 17
Número de grupos Si no existe razón para asumir un
número particular de grupos, se puede utilizar varios valores de K y evaluar los resultados obtenidos El valor de K con que se obtiene la
menor varianza promedio
Dr. Francisco J. Mata 18
Similitud, asociación y distancia
K-medias es un algoritmo de detección de grupos basado en distancia
Otros algoritmos utilizan el concepto de densidad (distribución de probabilidad)
Dr. Francisco J. Mata 19
Similitud, asociación y distancia Calculada sobre una matriz de
datos
X11 .... X1f ... X1p
. . . . . . . . . .Xi1 .... Xif ... Xip
. . . . . . . . . .Xn1 .... Xnf ... Xnp
ObjetosEntidadesRegistrosTuples
Variables, Atributos, Columnas
Minería de DatosDr. Francisco J. Mata 20
Similitud, asociación y distancia Métricas de distancia
d (X,Y) ≥ 0 d (X,Y) = 0, X = Y d (X,Y) = d (Y,X) d (X,Y) ≤ d (X,Z) + d (Z,Y)
Dr. Francisco J. Mata 21
Medidas de distancia Euclideana:
d (i,K) = (|xi1 – xk1|2 + |xi2 – xk2 |2 + ... + |x1p - xkp|2)1/2
Manhattan: d (i,K) = |xi1 – xk1| + |xi2 – xk2 | + ... + |
x1p - xkp|
Minkowski: d (i,K) = (|xi1 – xk1|q + |xi2 – xk2 |q + ... + |
x1p - xkp|q)1/q
Dr. Francisco J. Mata 22
Normalización de los datos Unidades de medida pueden
afectar los resultados de los algoritmos de detección de grupos
Para evitar este problema a veces es conveniente normalizar los datos, es decir convertirlos a números sin unidad
Procedimiento de normalización de los datos Calcular el valor z correspondiente:
zif = (xif – mf) / sf, donde mf =media de la variable f sf=desviación estándar de la variable f
Dr. Francisco J. Mata 23
Dr. Francisco J. Mata 24
Normalización de datos Puede ser ventajosa o no
Se puede determinar que no es conveniente normalizar los datos
Dr. Francisco J. Mata 25
Distancias ponderadas Se puede asignar pesos a las
variables de acuerdo con la importancia percibida d (i,K) = (w1|xi1 – xk1|q + w2|xi2 – xk2 |q +...+
wn|x1n - xkn|q)1/q
Dr. Francisco J. Mata 26
Tipos de variables Normalización y medidas
presentadas sólo se pueden utilizar con variables de intervalo o de radio Variables de intervalo: permiten
medir distancias Variables de radio: intervalo medido a
partir de un cero con significado
Dr. Francisco J. Mata 27
Otros tipos de variable Categóricas:
Binarias: Toman dos valores Ejemplo: {femenino, masculino}
Nominales: Lista de valores sin orden Ejemplo: {verde, rojo, amarillo, azul}
Ordinales: Lista de valores con un orden pero no una distancia Ejemplos: {pésimo, malo, bueno,
óptimo}
Dr. Francisco J. Mata 28
Tratamiento de variables categóricas binarias Toman sólo dos valores Calcular tabla de contingencia para los
objetos a medir:Objeto j
1Objeto i
0
1 0 q r
s t
suma
suma
q+r
s+t
q+s r+t q+r+s+t
Dr. Francisco J. Mata 29
Tratamiento de variables categóricas binarias Distancia dependerá de si la variable es
Simétrica: si ambas estados conllevan el mismo valor y por lo tanto llevan el mismo peso
Ejemplo: Género {masculino, femenino] Asimétrica: los estados resultantes no tiene
el mismo peso Ejemplo: Resultado de una prueba de enfermedad
{positivo, negativo}; por convención el estado más importante o raro se codifica como 1
Dr. Francisco J. Mata 30
Tratamiento de variables categóricas binarias Distancia variables simétricas
(coeficiente de coincidencia simple): d (i,j) = (r+s)/(q+r+s+t)
Distancia variables asimétricas (coeficiente de Jaccard): d (i,j) = (r+s)/(q+r+s)
Dr. Francisco J. Mata 31
Ejercicio Exámenes
Persona Fiebre Tos A B C D
Juan Sí No P N N NMaría Sí No P N P NPedro Sí Sí N N N N
¿Quiénes tiene más posibilidad de tener enfermedadessimilares y quiénes enfermedades diferentes?
Calcular las distancias entre cada persona utilizando el coeficiente de Jaccard considerando los resultados de los síntomas y exámenes como asimétricos y los valores de Sí y P como 1
Síntomas
Dr. Francisco J. Mata 32
Respuesta d (Juan,María) = (0+1)/(2+0+1) = 0.33 d (Juan,Pedro) = (1+1)/(1+1+1) = 0.67 d (Pedro,María) = (1+2)/(1+1+2) =
0.75
Juan y María tienen más posibilidad de tenerenfermedades similares y Pedro y María diferentes
Dr. Francisco J. Mata 33
Tratamiento de variables categóricas nominales Coeficiente de coincidencia simple:
d (i,j) = (p-m)/p m es el número de coincidencias p es el número de variables
Dr. Francisco J. Mata 34
Tratamiento de variables categóricas nominales Ejercicio Producto Color Forma Sabor 1 Rojo Redondo Dulce 2 Verde Cuadrado Salado 3 Rojo Rectangular Dulce 4 Amarillo Cuadrado Ácido
5 Azul Asimétrica Amargo
d(1,3)=? d(1,4)=? d(2,4)=? d(3,5)=?
Dr. Francisco J. Mata 35
Tratamiento de variables categóricas nominales Respuesta Producto Color Forma Sabor 1 Rojo Redondo Dulce 3 Rojo Rectangular Dulce
4 Amarillo Cuadrado Ácido
d (i,j) = (p-m)/p m es el número de coincidencias p es el número de variables
d(1,3)=(3-2)/3=0,33 d(1,4)=(3-0)/3=1
Dr. Francisco J. Mata 36
Tratamiento de variables ordinales (de rango) Si la variable f tiene Mf valores
ordinales {r1, r2, ... rMf}, ri < rj para i < j, reemplace cada valor de la variable por su correspondiente orden (ri ⇒ i)
Dr. Francisco J. Mata 37
Tratamiento de variables ordinales (cont.) Si hay varias variables ordinales
con diferentes números de valores normalice al intervalo [0,1] para que cada variable tenga el mismo peso Sustituya el i-ésimo valor para el
rango de la variable f como zif = (i–1)/ (Mf–1)
Dr. Francisco J. Mata 38
Tratamiento de variables ordinales (cont.) Utilice las distancias Euclideana,
de Manhattan o de Minkowski con los valores zif
Dr. Francisco J. Mata 39
Variables de Distintos Tipos
Dr. Francisco J. Mata 40
Ángulos entre vectores como medida de asociación
Cuando las relaciones entre los individuos son más importantes que las diferencias, el ángulo entre vectores es una mejor medida de similitud que la distancia
Dr. Francisco J. Mata 41
Angulo entre vectores como medida de asociación
Dr. Francisco J. Mata 42
Angulo entre vectores como medida de asociación Uso del seno del ángulo
0 vectores son paralelos 1 vectores son ortogonales
Dr. Francisco J. Mata 43
Problemas con el algoritmo de k-medias No funciona bien con grupos que se
traslapan Los grupos son afectados por valores
extremos Cada registro, tuple o entidad está en
un grupo o no; no existe la noción de que uno de ellos pertenezca con mayor o menor probabilidad al grupo que se le asignado
Dr. Francisco J. Mata 44
Modelos mixtos gaussianos Variante probabilística de K-medias
Los puntos se asumen que están distribuidos de acuerdo con una probabilidad gaussiana: n densidades normales independientes
Igual a K-medias se seleccionan K semillas Medias de distribuciones gaussianas Llamadas gaussianos
Algoritmo itera sobre dos pasos Estimación Maximización
Dr. Francisco J. Mata 45
Modelos mixtos gaussianos Paso de estimación
Se calcula la responsabilidad de cada gaussiano para cada punto de datos
Fuerte para puntos que están cerca Débil para puntos que están lejanos
Responsabilidades se utilizan como pesos en el siguiente paso
Dr. Francisco J. Mata 46
Modelos mixtos gaussianos
Dr. Francisco J. Mata 47
Modelos mixtos gaussianos Paso de maximización
La media de cada gaussiano se mueve hacia el centroide de todo el conjunto de datos utilizando la ponderación de las responsabilidades para cada punto
Dr. Francisco J. Mata 48
Modelos mixtos gaussianos Los pasos de estimación y
maximización se repiten hasta que no se pueden cambiar los gaussianos
Dr. Francisco J. Mata 49
Modelos mixtos gaussianos Se les denomina a veces como
agrupación suave Cada punto tiene una probabilidad de
pertenecer a cada uno de los K grupos
Se asigna al grupo que tiene más probabilidad
Dr. Francisco J. Mata 50
Modelos mixtos gaussianos
Probabilidadde pertenecera un grupo
Dr. Francisco J. Mata 51
Clases de algoritmos de detección de grupos Métodos de particionamiento
Dividen el conjunto de datos en K grupos Métodos jerárquicos:
Crean una descomposición jerárquica del conjunto de datos
Métodos basados en la densidad: Un grupo puede crecer en tanto su densidad
en el vecindario exceda un valor dado (“threshold”)
Dr. Francisco J. Mata 52
Clases de Algoritmos de detección de grupos (cont.) Métodos basados en mallas:
Cuantifican el espacio de objetos en un número finito de celdas que forman un estructura de malla
Métodos basados en modelos: Hipotetizan un modelo para cada
grupo y encuentran el mejor ajuste de los datos a este modelo
Dr. Francisco J. Mata 53
Métodos de particionamiento K-medias Modelos mixtos gaussianos
Dr. Francisco J. Mata 54
Métodos jerárquicos Aglomerativos:
De abajo hacia arriba Cada objeto empieza en su propio grupo
Divisivos: De arriba hacia abajo
Se empieza con todos los objetos en un solo grupo
Dr. Francisco J. Mata 55
Ejemplo de métodos aglomerativos
Agrupaciónde personas
por edad
Función dedistancia:
diferencia deedades
Dr. Francisco J. Mata 56
Métodos jerárquicos Tres formas para medir distancia entre
grupos: “Single linkage”: distancia entre dos
grupos se mide entre los miembros más cercanos
“Complete linkage”: distancia entre dos grupos se mide entre los miembros más lejanos
“Centroide”: distancia entre dos grupos se mide entre los centroides de cada grupo
Dr. Francisco J. Mata 57
Formas para medir distancias entre grupos
Dr. Francisco J. Mata 58
Métodos basados en la densidad Algoritmos de detección de grupos
basados en distancias usualmente encuentran grupos de forma esférica
Algoritmos basados en la densidad permiten a los grupos crecer en regiones con alta densidad y descubren grupos con forma arbitraria en bases de datos que contienen ruido
Dr. Francisco J. Mata 59
Métodos basados en la densidad
Dr. Francisco J. Mata 60
Consideraciones para la detección automática de grupos
Preparación de datos Determinación del número de
grupos Interpretación de los grupos
Dr. Francisco J. Mata 61
Preparación de datos Valores para variables a utilizar en el
análisis Métodos de agrupamiento funcionan sin ninguna
codificación sobre variables de intervalo o radio Otros tipos de variable requieren codificación si
el software de minería de datos no la realiza automáticamente
Variables categóricas binarias Variables categóricas nominales Variables ordinales o de rango
Valores perdidos Deben ser identificados y codificados
apropiadamente
Dr. Francisco J. Mata 62
Preparación de datos Identificación y tratamiento de valores
extremos Pueden afectar resultados principalmente en
algoritmos o métodos basados en distancia Remover o sustituir valores extremos
Identificar variables altamente correlacionadas y seleccionar un conjunto más pequeño de variables Análisis de correlación Análisis de componentes principales
Dr. Francisco J. Mata 63
Determinación del número de grupos Objetivo:
encontrar un conjunto de grupos cuya distancia dentro de cada uno de ellos sea mínima y fuera de ellos sea máxima
Procedimiento: comparar la variación entre grupos a la variación
dentro de grupos para diferentes valores de K Indicadores
Criterio de agrupamiento cúbico Estadística falsa F Estadística falsa T2
Determinación del número de grupos
Dr. Francisco J. Mata 64
Variable Total STD
Porcentaje de variación dentro
de grupos
Within STD
Porcentaje de variación
entre grupos
R-Square
Radio de porcentaje
de variación entre grupos a porcentaje de variación
dentro de grupos
RSQ/(1-RSQ)X4 1.00000 0.58358 0.666920 2.002280
X5 1.00000 0.70214 0.517838 1.073990
X13 1.00000 0.84483 0.302305 0.433290
X15 1.00000 0.55941 0.693936 2.267295
OVER-ALL 1.00000 0.68092 0.546592 1.205518
K=3
Criterio de agrupamiento cúbico
Dr. Francisco J. Mata 65
Valores de CCC mayores que dos o tres indican buenos grupos; valores entre 0 y 2 indican grupos potenciales pero que deben ser evaluados con cuidado. En este caso valores de CCC son negativos lo que indica valores extremos.Como CCC toma un incremento en 3 de valores mayores a menores de grupos (eje X), se selecciona tentativamente este número
Estadísticas falsa F y falsa T2
Dr. Francisco J. Mata 66
Incrementos altos en PSF y PST2 de valores mayores a menores de grupos se utilizan para seleccionar el número de grupos De acuerdo con esto número óptimo de grupos está entre 2 y 3
Dr. Francisco J. Mata 67
Interpretación de los grupos Las medias de las variables son
buenos indicadores de las características de los individuos en los grupos
Variables con medias (utilizando valores normalizados) o frecuencias muy diferentes indican atributos o características que separan a los grupos
Interpretación de los grupos
Dr. Francisco J. Mata 68
Cluster Means
Cluster X4 X5 X13 X151 0.28046665
7-
0.953149346
0.714086862
0.868975379
2 1.700924242
0.900060957
-0.05227818
9
0.790546535
3 -0.661424429 0.399999715 -0.473951479 -0.810304619
Variables X5 y X13 separan a los grupos 1 y 2Variables X4, X5, X13 y X15 separan a los grupos 1 y 3
Variables X4 y X 15 separan a los grupos 2 y 3