PDF de programación - Fundamentos y Aplicaciones Prácticas del Descubrimiento de Conocimiento en Bases de Datos - Sesión 13

Fundamentos y Aplicaciones Prácticas
del Descubrimiento de Conocimiento

en Bases de Datos

- Sesión 13 -

Juan Alfonso Lara Torralbo

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

1

Índice de contenidos

• Clustering particional

•

•

Actividad. Clustering particional

Actividad. Clustering particional con Weka

• Clustering Jerárquico

• Clustering basado en densidad

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

2

Clustering particional (I)

• Realizan una división de un conjunto de datos en

subconjuntos con intersección vacía

• Se realiza una asignación de los objetos a los diferentes
clusters en función de la proximidad de dichos objetos a
un representante elegido para cada cluster

• Ese representante se conoce con el nombre de

centroide

• El número de clusters, k, se indica inicialmente y, tras

una serie de iteraciones, se alcanza una partición
óptima de los datos

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

3

Clustering particional (II)

• El más conocido algoritmo es K-medias (en inglés, K-means)

• Requiere “a priori” la definición del número de clusters, k

• Se elige un punto inicial (centroide) para representar cada uno de

los clusters

• Se asigna cada objeto al cluster cuyo centroide es el más cercano a

él

• Seguidamente, el centroide de cada cluster es recalculado como la

media de los puntos asignados al cluster

• Este proceso se repite hasta que los centroides no cambian,

momento el que se dice que el método ha convergido a la solución

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

4

Clustering particional (III)

K-medias
ENTRADA: Un conjunto de datos D y el número k de clusters a formar.

SALIDA: Para cada uno de los clusters, la lista de los elementos de D

que pertenecen a dicho cluster.

PASOS:
1. Seleccionar los centroides iniciales de los k clusters: c1, c2, c3,..., ck.
2: Asignar cada elemento x de D al cluster cuyo centroide sea el más

cercano a x.

3. Para cada uno de los clusters, recalcular su centroide, basado en

los elementos que están contenidos en el cluster.

4. Volver al paso 2 hasta que se consiga convergencia.

5

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

Clustering particional (IV)

• Aspecto fundamental: la elección inicial de los k

centroides

• Para ello existen numerosos criterios aunque

los más extendidos son los siguientes:
a) Usar los k primeros elementos.
b) Elegir aleatoriamente k elementos.
c) Tomar cualquier partición al azar en k clusters y calcular sus

centroides.

• Es muy eficiente y sencillo, aunque hay que definir el k
• Ver ejemplo (sólo Iteración 1)

6

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

Actividad. Clustering

particional

Realizar, en grupo, la segunda iteración
del ejemplo anterior ¿Se ha convergido
a la solución? ¿Cuál es ésta?
Puesta en común

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

7

Actividad. Clustering
particional con Weka

Demostración del profesor, seguida por
los estudiantes en grupo, de la
ejecución del algoritmo K-medias con
Weka
Supervisión final del profesor

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

8

Clustering jerárquico (I)
• Para la segmentación de los datos, se

construye una sucesión ordenada de clusters
con forma de estructura jerárquica

• Dicha estructura, se suele representar en forma

de árbol (dendograma)

• Dos tipos de técnicas de clustering jerárquico:
• Ascendentes (también llamadas Aglomerativas o

Acumulativas)

• Descendentes (también llamadas Divisivas)

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

9

Clustering jerárquico (II)

Técnicas Jerárquicas Ascendentes
• De tipo iterativo
• En cada paso, el número de clusters va disminuyendo

por medio de un proceso de tipo sintético, de abajo
hacia arriba, más conocido como bottom-up.

• Al principio, cada cluster está compuesto por un único

objeto

• Los clusters de una iteración se obtienen combinando
los dos clusters más similares de la iteración anterior.

• Finalmente, un único cluster contiene a todos los

objetos

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

10

Clustering jerárquico (III)

Técnicas Jerárquicas Descendentes
• En este caso, el número de clusters va aumentando en

cada iteración por medio de un proceso de tipo analítico,
de arriba hacia abajo, más conocido como top-down.
Inicialmente, hay un único cluster formado por la
totalidad de los objetos que se quiere segmentar.

•

• A medida que se ejecuta la técnica, los clusters se van

dividiendo en clusters más pequeños.

• Finalmente, cada cluster contiene un único objeto.

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

11

Clustering jerárquico (IV)

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

12

Clustering jerárquico (V)

Técnicas Jerárquicas Ascendentes

1. Asignar cada objeto a un cluster.
2: Localizar el par de cluster más similares y agruparlos.
3. Calcular la distancia entre el nuevo cluster y el resto.
4. Repetir los pasos 2 y 3 hasta que haya un único cluster.

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

13

Clustering jerárquico (VI)

• A la hora de agrupar los dos clusters más similares en

una iteración (paso 2 del algoritmo anterior), existen
diferentes criterios de distancia:
• Enlace simple (single-link). En este caso, la distancia entre dos

clusters se calcula como la mínima distancia entre todos los
posibles pares de objetos de ambos clusters.

• Enlace completo (complete-link). La distancia entre dos

clusters se calcula como la máxima distancia entre todos los
posibles pares de objetos.

• Enlace promedio (average-link). Según este criterio, la

distancia entre dos clusters se calcula como la media de las
distancias entre los elementos de ambos clusters.

14

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

Clustering jerárquico (VII)

• Ejemplo ascendente a partir de matriz de distancias de

7 elementos

Objeto

D1

D2

D3

D4

D5

1,7263

1,5000

1,2369

0,8062

0,5831

0,4000


• Ver solución (pasos, dendograma, corte y clusters)

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

15



0,3606



0,5000

0,4243



0,9220

0,7071

0,4472



1,3416

1,0440

0,9220

0,5000



1,8385

1,5524

1,3892

0,9434

0,5099

D1

D2

D3

D4

D5

D6

D7

D6



D7



Clustering basado en densidad (I)

• Hacen uso del concepto de densidad de un objeto
• Dado un conjunto de datos que se desean segmentar, la

densidad de un objeto se define como el número de
vecinos alcanzables desde él considerando un
determinado radio

• La densidad mide el número de vecinos de un objeto

que se encuentran a una distancia menor que un
determinado umbral

• A los puntos alcanzados desde un punto dado

considerando un determinado radio, se les conoce con
el nombre de vecindad de dicho punto
16
2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

Clustering basado en densidad (II)

• Utilizan los siguientes parámetros:

• Radio o Epsilon (se suele denotar por Eps), que representa el radio

considerado para medir la densidad de cada punto.

• Número mínimo de vecinos (denotado por MinPts), que representa

el número mínimo de objetos en la vecindad de otro.

• Tipos de puntos según esos parámetros:

• Puntos nucleares: tienen, en su vecindario de radio Eps, un número

de vecinos mayor o igual a MinPts

• Puntos fronterizos: tienen, en su vecindario de radio Eps, un

número de vecinos menor a MinPts, pero que están en la vecindad
de algún punto nuclear

• Puntos de ruido:resto de puntos

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

17

Clustering basado en densidad (III)

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

18

Clustering basado en densidad (IV)

• Hay muchos algoritmos, aunque destaca DBSCAN
• En particular, este algoritmo elimina los puntos de

ruido, en primer lugar.

• A continuación, el algoritmo aglutina, en un mismo
cluster, a todos aquellos puntos de núcleo que son
vecinos entre sí.

• Por último, los puntos fronterizos van a parar al

cluster más cercano

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

19

Clustering basado en densidad (V)

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

20

Clustering basado en densidad (VI)

• Como se aprecia funcionan muy bien con clusters
de formas muy arbitrarias y muy entremezclados
entre sí

• No funcionan bien cuando trabaja con registros de

muy alta dimensionalidad ni cuando los datos
presentan diferentes densidades en diferentes
regiones del espacio

• Por tanto, se requiere una cierta densidad uniforme

para que trabaje bien y baja dimensionalidad

2014 Juan Alfonso Lara Torralbo. Todos los derechos reservados.

21