PDF de programación - Clustering

Clustering
Clustering
© Fernando Berzal, [email protected]
© Fernando Berzal,
[email protected]

Clustering
Clustering

Introducción
 Introducción
Medidas de similitud
 Medidas de similitud
 Para atributos continuos: Métricas de distancia.
Para atributos continuos: Métricas de distancia.
 Para atributos no continuos, p.ej. distancia de edición.
Para atributos no continuos, p.ej. distancia de edición.
 Métodos de agrupamiento
 Métodos de agrupamiento
Métodos de agrupamiento
Métodos de agrupamiento
 KK--Means
Means
 DBSCAN
DBSCAN
 Clustering
Clustering jerárquico
jerárquico
 Evaluación de resultados
Evaluación de resultados
Validación de resultados
 Validación de resultados
Apéndice: El problema de la dimensionalidad
 Apéndice: El problema de la
dimensionalidad

11

Introducción
Introducción

“Sinónimos” según el contexto…
“Sinónimos” según el contexto…

 Clustering

Clustering (IA)
(IA)

 Aprendizaje no supervisado

Aprendizaje no supervisado (IA)
(IA)

 Ordenación

Ordenación (Psicología)
(Psicología)

 Segmentación

Segmentación (Marketing)
(Marketing)

Introducción
Introducción

Objetivo
Objetivo
Encontrar agrupamientos de tal forma que los objetos
Encontrar agrupamientos de tal forma que los objetos
de un grupo sean similares entre sí y diferentes de los
de un grupo sean similares entre sí y diferentes de los
objetos de otros grupos [clusters
clusters].].
objetos de otros grupos [

Minimizar
distancia
intra-cluster

Maximizar
Maximizar
distancia
inter-cluster

22

33

Introducción
Introducción

Aprendizaje no supervisado:
 Aprendizaje no supervisado:
No existen clases predefinidas.
No existen clases predefinidas.

Los resultados obtenidos dependerán de:
 Los resultados obtenidos dependerán de:
 Los resultados obtenidos dependerán de:
Los resultados obtenidos dependerán de:
El algoritmo de agrupamiento seleccionado.
El algoritmo de agrupamiento seleccionado.
El conjunto de datos disponible.
El conjunto de datos disponible.
La medida de similitud utilizada para comparar
La medida de similitud utilizada para comparar
objetos (usualmente, definida como medida de
objetos (usualmente, definida como medida de
distancia).
distancia).

Introducción
Introducción

¿Cuántos
¿Cuántos
agrupamientos?

¿Dos?
¿Dos?

¿Seis?

¿Cuatro?

44

55

Introducción
Introducción

Aplicaciones
Aplicaciones
Reconocimiento de formas.
 Reconocimiento de formas.
 Mapas temáticos (GIS)
Mapas temáticos (GIS)
Marketing: Segmentación de clientes
 Marketing: Segmentación de clientes
 Clasificación de documentos
 Clasificación de documentos
Clasificación de documentos
Clasificación de documentos
 Análisis de web
Análisis de web logs
 ……

logs (patrones de acceso similares)
(patrones de acceso similares)

También se usa como paso previo
También se usa como paso previo
a otras técnicas de Minería de Datos:
a otras técnicas de Minería de Datos:
 Exploración de datos (segmentación &
 Preprocesamiento

Exploración de datos (segmentación & outliers
outliers))
Preprocesamiento (p.ej. reducción de datos)
(p.ej. reducción de datos)

Medidas de similitud
Medidas de similitud

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

Mujeres
Mujeres
vs.vs.
Hombres
Hombres

66

77

Medidas de similitud
Medidas de similitud

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

Simpsons
Simpsons
vs.vs.
Empleados de
Empleados de
la escuela de
la escuela de
Springfield
Springfield

Medidas de similitud
Medidas de similitud

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

¡¡¡ El
¡¡¡ El clustering

clustering es subjetivo !!!
es subjetivo !!!

88

99

Medidas de similitud
Medidas de similitud

Peter

Pedro

0.23

342.7

3

1010

Medidas de similitud
Medidas de similitud

sexo

fechnac

educ

catlab

salario

salini

T.emp

expprev minoría

No

No

No

No

Sí

Sí

Sí

Sí

No

No

No

No

No

1111

Grupo 1
Grupo 1

Grupo 2
Grupo 2

Grupo 3
Grupo 3

id

121

122

123

124

125

126

127

128

129

130

131

132

133

Mujer

6-ago-1936

15 Administrativo

$18.750

$10.500

Mujer

26-sep-1965

15 Administrativo

$32.550

$13.500

Mujer

24-abr-1949

12 Administrativo

$33.300

$15.000

Mujer

29-may-1963

16 Administrativo

$38.550

$16.500

Hombre

6-ago-1956

12 Administrativo

$27.450

$15.000

Hombre

21-ene-1951

Hombre

1-sep-1950

15

12

Seguridad

$24.300

$15.000

Seguridad

$30.750

$15.000

Mujer

25-jul-1946

12 Administrativo

$19.650

$9.750

Hombre

18-jul-1959

Hombre

6-sep-1958

17

20

Directivo

$68.750

$27.510

Directivo

$59.375

$30.000

Hombre

8-feb-1962

15 Administrativo

$31.500

$15.750

Hombre

17-may-1953

12 Administrativo

$27.300

$17.250

Hombre

12-sep-1959

15 Administrativo

$27.000

$15.750

90

90

90

90

90

90

90

90

89

89

89

89

89

54

22

3

Ausente

173

191

209

229

38

6

22

175

87

NOTA: No No será posible que
NOTA:
mismo
mismo grupo, por lo que habrá
entre
entre los elementos

los elementos de un

de un mismo grupo.
mismo grupo.

será posible que todas las

todas las variables tengan valores similares en un
variables tengan valores similares en un

grupo, por lo que habrá que usar una medida global de semejanza
que usar una medida global de semejanza

Medidas de similitud
Medidas de similitud

sexo

fechnac

educ

catlab

salario

salini

T.emp

expprev minoría

Mujer

6-ago-1936

15 Administrativo

$18.750

$10.500

Mujer

26-sep-1965

15 Administrativo

$32.550

$13.500

Mujer

24-abr-1949

12 Administrativo

$33.300

$15.000

Mujer

29-may-1963

16 Administrativo

$38.550

$16.500

Hombre
Hombre

6-ago-1956
6-ago-1956

12 Administrativo
12 Administrativo

$27.450
$27.450

$15.000
$15.000

90

90

90

90

90
90

54

22

3

Ausente

173
173

id

121

122

123

124

125
125

126

No

No

No

No

Sí
Sí

Sí

Sí

Sí

No

No

No

No

No

A la hora de calcular la similitud entre dos objetos:
A la hora de calcular la similitud entre dos objetos:

1-sep-1950

Seguridad

Hombre

$30.750

$15.000

127

209

12

90

Hombre

21-ene-1951

15

Seguridad

$24.300

$15.000

191

90

128

Mujer

25-jul-1946

12 Administrativo

$19.650

$9.750

90

229

129

Hombre

18-jul-1959

17

Directivo

$68.750

$27.510

89

38

130

No tienen por qué utilizarse todos los atributos
 No tienen por qué utilizarse todos los atributos
disponibles en nuestro conjunto de datos.
disponibles en nuestro conjunto de datos.

15 Administrativo

6-sep-1958

8-feb-1962

Directivo

Hombre

Hombre

$59.375

$30.000

$31.500

$15.750

131

20

89

89

22

6

132

Hombre

17-may-1953

12 Administrativo

$27.300

$17.250

89

175

133

Hombre

12-sep-1959

15 Administrativo

$27.000

$15.750

89

87

Hay que tener cuidado con las magnitudes de cada
 Hay que tener cuidado con las magnitudes de cada
variable.
variable.

1212

Medidas de similitud
Medidas de similitud

Atributos continuos
Atributos continuos

Para evitar que unas variables dominen sobre otras,
Para evitar que unas variables dominen sobre otras,
los valores de los atributos se “normalizan” a priori:
los valores de los atributos se “normalizan” a priori:

 Desviación absoluta media:
Desviación absoluta media:
−

+

=

s

f

−

(|1
mxn
f
1

1

f

|

=

(xn m

f

1

+

x
2

f

f

++

...

x
nf

.)

|

x
2

f

m

f

|

++

...

|

−

mx
nf

f

|)

 zz--score (medida estandarizada):
score (medida estandarizada):
z
if

=



−

mx
if

f

s

f

1313

Medidas de similitud
Medidas de similitud

Usualmente, se expresan en términos de distancias:
Usualmente, se expresan en términos de distancias:

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

d(d(i,ji,j) > d(

) > d(i,ki,k))

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

será distinta en función del tipo de dato y
será distinta en función del tipo de dato y

de la interpretación semántica que nosotros hagamos.
de la interpretación semántica que nosotros hagamos.

Medidas de similitud
Medidas de similitud

Se suelen usar medidas de distancia
Se suelen usar medidas de distancia
porque verifican las siguientes propiedades:
porque verifican las siguientes propiedades:

 Propiedad reflexiva
Propiedad reflexiva

d(d(i,ji,j) = 0 si y sólo si i=j
) = 0 si y sólo si i=j

Propiedad simétrica
 Propiedad simétrica
Propiedad simétrica
Propiedad simétrica

d(d(i,ji,j) = d(
d(d(i,ji,j) = d(

) = d(j,ij,i))
) = d(j,ij,i))

 Desigualdad triangular d(

Desigualdad triangular d(i,ji,j) ≤ d(

) ≤ d(i,ki,k)+d(

)+d(k,jk,j))

1414

1515

Medidas de similitud
Medidas de similitud

Métricas de distancia:
Métricas de distancia:
Distancia de Minkowski
Distancia de
Minkowski

 Distancia de Manhattan (r=1) /
 Distancia de Manhattan (r=1) /

Distancia de Manhattan (r=1) / citycity block /
Distancia de Manhattan (r=1) / citycity block /

block / taxicab
block / taxicab
taxicab
taxicab

 Distancia

Distancia euclídea

euclídea (r=2):
(r=2):

 Distancia de

Distancia de Chebyshev

Chebyshev (r(r→→∞∞) / dominio /

) / dominio / chessboard
chessboard

Medidas de similitud
Medidas de similitud

Métricas de distancia:
Métricas de distancia:
Distancia de Minkowski
Distancia de
Minkowski

 Distancia de Manhattan = 12
Distancia de Manhattan = 12
Distancia euclídea
 Distancia
euclídea ≈ 8.5
≈ 8.5
Distancia de Chebyshev
 Distancia de

Chebyshev = 6= 6

(roja, azul o amarilla)
(roja, azul o amarilla)
continua)
(verde
(verde -- continua)
(verde
(verde -- discreta)
discreta)

1616

1717

Medidas de similitud
Medidas de similitud

Métricas de distancia:
Métricas de distancia:
Distancia de Chebyshev
Distancia