Algoritmo

Dendogramas

Clúster Jerárquicos

Luis Fernando Castillo

@luisfercastillo
 Historia
Introducción al Análisis Clúster

El análisis clúster es una técnica multivariante cuya idea

básica es clasificar objetos formando grupos/conglomerados
(clúster) que sean lo más homogéneos posible dentro de si
mismos y heterogéneos entre sí.
 Clustering
¿Cuál es la forma natural de agrupar los personajes?

Hombres
vs.
Mujeres

3
Clustering
¿Cuál es la forma natural de agrupar los personajes?

Simpsons
vs.
Empleados
de la escuela
de Springfield
4
Clustering
¿Cuál es la forma natural de agrupar los personajes?

¡¡¡ El clustering es subjetivo !!!

5
Medidas de similitud
Usualmente, se expresan en términos de distancias:

d(i,j) > d(i,k)

nos indica que el objeto i es más parecido a k que a j

La definición de la métrica de similitud/distancia

será distinta en función del tipo de dato y
de la interpretación semántica que nosotros hagamos.

En otras palabras, la similitud entre objetos es

subjetiva.
6
Medidas de similitud

¿Cuántos ¿Dos?
agrupamientos?

¿Seis? ¿Cuatro?

7
Medidas de similitud
Métricas de distancia
Distancia de Minkowski

 Distancia de Manhattan (r=1) / city block / taxicab

 Distancia euclídea (r=2):

 Distancia de Chebyshev (r) / dominio / chessboard

• Distancia Correlación de Pearson 8

Medidas de similitud
Métricas de distancia
Distancia de Minkowski

 Distancia de Manhattan = 12
 Distancia Euclídea  8.5
 Distancia de Chebyshev = 6 9
Medidas de similitud
Métricas de distancia
Distancia de Chebyshev

 También conocida
como distancia de
tablero de ajedrez
(chessboard distance):
Número de
movimientos
que el rey ha de hacer
para llegar de una
casilla a otra en un
tablero de ajedrez. 10
 Conceptos básicos
Objetos: son los elementos a clasificar

ai , i  1 n

Características de los objetos

 Escala
 Nominal

ai , j i  1 n
j  1 k

11
 Conceptos básicos

Matriz de datos

a11 a12 Peso Altura

86 1,76
a21 a22
53 1,58
a31 a32 60 1,65

12
Conceptos básicos

Representación
gráfica de la matriz
de datos

13
 Conceptos básicos
Distancia
 La distancia es un índice de disimilaridad que verifica
las siguientes propiedades:

D(a, b)  0
D(a, b)  D(b, a)
D(a, a)  0
D(a, c)  D(a, b)  D(b, c)

14
Conceptos básicos
Matriz de distancias

distancia euclídea
Caso 1:Jose 2:Angeles 3:Conchita
1:Jose ,000 33,000 26,000
2:Angeles 33,000 ,000 7,000
3:Conchita 26,000 7,000 ,000
Esta es una matriz de disimilaridades

15
Conceptos básicos
 Distancia de correlación de Pearson
Esta distancia esta basada en el coeficiente de
correlación de Pearson y por lo tanto hereda todas sus
propiedades.
El coeficiente de correlación de Pearson mide el grado
de asociación lineal entre dos objetos, es decir, hasta
que punto dos objetos son proporcionales.
A diferencia de otras medidas, este coeficiente no se
ve afectado por las escalas de medidas utilizadas.
El recorrido de este coeficiente varía entre -1 y 1
(1 indica una relación proporcional perfecta).

16
 Conceptos básicos
 La estandarización de variables.
 Debido a la propia definición de distancia se
deduce que ésta va a ser sensible a los
cambios de escala, es decir, va a ser
afectada por las unidades de medida que
hemos utilizado para medir las características
de los elementos.
 Si los rangos de las distintas características
son dispares el cálculo de las distancias se
vería seriamente afectado.

17
Conceptos básicos

676  0.01  26.001

(1,76-1,65)^2=0,01

(86-60)^2=676

18
Conceptos básicos

19
Conceptos básicos
El problema de utilizar variables con distinto
recorrido.
-Homogeneizar las escalas en el intervalo 0-
1.
ai , j  min( a*, j )
a 
'

max( a*, j )  min( a*, j )

i, j

20
 21

Conceptos básicos

86 1,76 1,00 1,00

53 1,58 0,00 0,00

60 1,65 0,21 0,39

De scriptiv e Statistics

N Range Minimum Maximum Mean

peso 3 33,00 53,00 86,00 66,3333
Altura 3 ,18 1,58 1,76 1,6633
npeso 3 1,00 ,00 1,00 ,4033
naltura 3 1,00 ,00 1,00 ,4633
Valid N (listwise) 3
Conceptos básicos
 Estandarizar variables

Realizar una transformación de forma que las variables

transformadas tengan media 0 y varianza 1.

ai , j  media(a*, j )
a 
´

 (a*, j )
i, j

22
 23

Conceptos básicos

86 1,76 1,13 1,07

53 1,58 -0,77 -0,92

60 1,65 -0,36 -0,15

De scriptiv e Statistics

N Range Minimum Maximum Mean Std. Deviation

peso 3 33,00 53,00 86,00 66,3333 17,38774
Altura 3 ,18 1,58 1,76 1,6633 ,09074
Zpeso Zscore(peso) 3 1,89789 -,76682 1,13107 ,0000000 1,00000000
ZAltura Zscore(Altura) 3 1,98374 -,91840 1,06534 ,0000000 1,00000000
Valid N (listwise) 3
Métodos de agrupamiento
Requisitos del algoritmo “perfecto”
 Escalabilidad
 Manejo de distintos tipos de datos
 Identificación de clusters con formas arbitrarias
 Número mínimo de parámetros
 Tolerancia frente a ruido y outliers
 Independencia con respecto al orden de presentación
de los patrones de entrenamiento
 Posibilidad de trabajar en espacios con muchas
dimensiones diferentes
 Capacidad de incorporar restricciones especificadas por
el usuario (“domain knowledge”)
 Interpretabilidad / Usabilidad
24
Métodos de agrupamiento
Tipos de algoritmos de clustering

 Agrupamiento por particiones

k-Means, CLARANS

 Clustering jerárquico
BIRCH, ROCK, CHAMELEON

 Métodos basados en densidad

DBSCAN

 …

25
Métodos de agrupamiento
Clustering por particiones

Datos originales Datos agrupados

26
Métodos de agrupamiento
Clustering jerárquico

p1
p3 p4
p2
p1 p2 p3 p4
Tradicional DENDOGRAMA

p1
p3 p4
p2
p1 p2 p3 p4
No tradicional 27
Métodos de agrupamiento
Métodos basados en densidad
 Un cluster en una región densa de puntos, separada por
regiones poco densas de otras regiones densas.
 Útiles cuando los clusters tienen formas irregulares, están
entrelazados o hay ruido/outliers en los datos.

28
k-Means
Algoritmo de agrupamiento por particiones
(MacQueen, 1967)
 Número de clusters conocido (k)
 Cada cluster tiene asociado un centroide
(centro geométrico del cluster).
 Los puntos se asignan al cluster cuyo centroide esté más
cerca (utilizando cualquier métrica de distancia).
 Iterativamente, se van actualizando los centroides en
función de las asignaciones de puntos a clusters, hasta
que los centroides dejen de cambiar.
 Complejidad O(n*k*I*d)
donde n es el número de datos, k el número de clusters,
I el número de iteraciones y d el número de atributos
29
k-Means
Iteration 6
1
2
3
4
5
3

2.5

1.5
y

0.5

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x

30
k-Means
Iteration 1 Iteration 2 Iteration 3
3 3 3

2.5 2.5 2.5

2 2 2

y 1.5 1.5 1.5

y
1 1 1

0.5 0.5 0.5

0 0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x x x

Iteration 4 Iteration 5 Iteration 6

3 3 3

2.5 2.5 2.5

2 2 2

1.5 1.5 1.5

y

y
1 1 1

0.5 0.5 0.5

0 0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x x x

31
k-Means 3
Iteration 5
1
2
3
4

2.5

1.5
y

0.5

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x

32
k-Means
Iteration 1 Iteration 2
3 3

2.5 2.5

2 2

1.5 1.5

y
1 1

0.5 0.5

0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x x

Iteration 3 Iteration 4 Iteration 5

3 3 3

2.5 2.5 2.5

2 2 2

1.5 1.5 1.5

y

y
1 1 1

0.5 0.5 0.5

0 0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2
x x x

33
k-Means
3

2.5

2
Puntos originales
1.5
y

0.5

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x

3 3

2.5 2.5

2 2

1.5 1.5
y

1 y 1

0.5 0.5

0 0

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

x x

Solución óptima Óptimo local 34

k-Means
Ejercicio

Agrupar los 8 puntos de la

figura en 3 clusters usando
el algoritmo de las K medias.

Centroides iniciales:
A1, A7 y A8

Métricas de distancia:
 Distancia euclídea
 Distancia de Manhattan
 Distancia de Chebyshev

35
k-Means
Ejercicio resuelto
Distancia euclídea

36
k-Means
Ejercicio resuelto
Distancia euclídea

Primera iteración Segunda iteración

37
k-Means
Ejercicio resuelto
Distancia euclídea

Tercera iteración Configuración final

38
k-Means
Ventaja
 Eficiencia O(n·k·I·d)
vs. PAM O(I·k(n-k)2)
CLARA O(ks2+k(n-k))
Desventajas
 Termina en un óptimo local:
El resultado depende de la selección inicial de centroides.
 Necesidad de conocer el número de agrupamientos k
 Incapacidad para detectar ruido / identificar outliers.
 No resulta adecuado para detectar clusters no convexos
 Si tenemos datos de tipo categórico,
¿cómo calculamos la media?

39
k-Means
Variantes

 GRASP [Greedy Randomized Adaptive Search Procedure]

para evitar óptimos locales.

 k-Modes (Huang’1998) utiliza modas en vez de medias

(para poder trabajar con atributos de tipo categórico).

 k-Medoids utiliza medianas en vez de medias para

limitar la influencia de los outliers

vg. PAM (Partitioning Around Medoids, 1987)

CLARA (Clustering LARge Applications, 1990)
CLARANS (CLARA + Randomized Search, 1994) 40
Clustering jerárquico

DENDROGRAMA: La similitud entre dos objetos viene

dada por la “altura” del nodo común más cercano.
41
Clustering jerárquico

El DENDROGRAMA nos puede ayudar a determinar el

número adecuado de agrupamientos (aunque
normalmente no será tan fácil). 42
Clustering jerárquico

Outlier

El DENDROGRAMA
también nos puede servir para detectar outliers. 43
Clustering jerárquico
0 1 2 3 4
aglomerativo
(AGNES)
a ab AGglomerative NESting

b abcde
c
cde
d
de
e
divisivo
4 3 2 1 0 (DIANA)
Divisive ANAlysis

En lugar de establecer de antemano el número de

clusters, tenemos que definir un criterio de parada
44
 Modelos de análisis cluster
 Métodos de agrupación jerárquica.

1. Se establecen n agrupamientos. Cada

agrupamiento contiene exactamente un
elemento.
2. Se agrupan los dos cluster más cercanos
formando un único cluster.
3. Se recalcula la matriz de distancias.
4. Pasamos al punto 1.

Este algoritmo realiza exactamente n-1

iteraciones.

45
Métodos de agrupación
jerárquica

46
Métodos de agrupación
jerárquica

47
Métodos de agrupación
jerárquica

48
Métodos de agrupación
jerárquica

49
Métodos de agrupación
jerárquica

50
Métodos de agrupación
jerárquica
 Ventajas del modelo de agrupación jerárquica.

1. No requiere hacer inferencias sobre el número

de cluster.
2. Permite representar las sucesivas agrupaciones
en forma de árbol (dendograma).
 Inconvenientes

1. Alto coste computacional.

2. Sensible respecto de las primeras agrupaciones.
3. Complicado de interpretar cuando el número
de elementos a clasificar es grande.

51
Clustering jerárquico
¿Cómo medir la distancia entre clusters?

 MIN
single-link

 MAX
complete
linkage
(diameter)

52
Clustering jerárquico
¿Cómo medir la distancia entre clusters?

 Promedio

 Centroides
[Link]. BIRCH

 

53
Dendogramas
Ejemplo 1 (I)
Ejemplo 1 (II)
Ejemplo 1 (III)
Ejemplo 2 (I)
Ejemplo 2 (II)
Ejemplo 3 (I)
Ejemplo 3 (II)
Ejemplo 3 (III)
Problemas cluster jerárquico
 Con muchos datos lento, cada vez n(n-1)/2
comparaciones.

 Distancias euclideas pueden no ser apropiadas

 Con muchos datos dificil de interpretar el

dendograma
Clustering jerárquico
Ejercicio

Utilizar un algoritmo aglomerativo de clustering jerárquico para agrupar

los datos descritos por la siguiente matriz de distancias:

Variantes:
 Single-link (mínima distancia entre agrupamientos)
 Complete-link (máxima distancia entre agrupamientos)

64
Clustering jerárquico
Ejercicio resuelto

Single-link

Complete-link

65
 Bibliografía
 R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for
data mining applications. SIGMOD'98

 M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the clustering structure,
SIGMOD’99.

 L. Ertöz, M. Steinbach, and V. Kumar. Finding clusters of different sizes, shapes, and densities in noisy, high-
dimensional data, SDM’2003

 M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial
databases. KDD'96.

 D. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2:139-172, 1987.

 D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on dynamic systems.
VLDB’98

 S. Guha, R. Rastogi, and K. Shim. Cure: An efficient clustering algorithm for large databases. SIGMOD'98.

 S. Guha, R. Rastogi, and K. Shim. ROCK: A robust clustering algorithm for categorical attributes. In ICDE'99, Sydney,
Australia, March 1999.

66
Créditos
 Jiawei Han (University of Illinois at Urbana-
Champaign): “Data Mining: Concepts and
Techniques”, capítulo 7, 2006

 Pang-Ning Tan (Michigan State University),

Michael Steinbach & Vipin Kumar (University of
Minnesota): “Introduction to Data Mining”,
capítulos 8 y 9, 2006

67
Clusters
Sistemas Inteligentes 2