PDF de programación - Clustering

Imágen de pdf Clustering

Clusteringgráfica de visualizaciones

Publicado el 31 de Julio del 2017
815 visualizaciones desde el 31 de Julio del 2017. Una media de 35 por semana
708,2 KB
20 paginas
Creado hace 244d (16/05/2017)
Clustering

Prof. Dra. Silvia Schiaffino

ISISTAN



[email protected]



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering: Concepto

• Cluster: un número de cosas o personas

similares o cercanas, agrupadas



• Clustering: es el proceso de particionar un
conjunto de objetos (datos) en un conjunto de
sub-clases con cierto significado

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

1

Clustering: Concepto

• Clustering es un proceso de aprendizaje no

supervisado:
– Las clases no están predefinidas sino que deben ser

descubiertas dentro de los ejemplos

• Primariamente es un método descriptivo para

interpretar un conjunto de datos

• Particionar ejemplos de clases desconocidas en

subconjuntos disjuntos de clusters tal que:
– Ejemplos en un mismo cluster sean altamente similares

entre sí

– Ejemplos en diferentes clusters sean altamente disimiles

entre sí

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Aplicaciones

• Reconocimiento de patrones



• Procesamiento de imágenes

– Reconocer áreas con cierta característica de tierra (GIS)





Investigación de mercado
– Detectar diferentes tipos de clientes según su forma de compra



• Web mining

– Categorización de documentos
– Clustering en Web logs



• Como preprocesamiento para otras técnicas de data

mining

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

2

Características

• Un buen método de clustering debería identificar

clusters que sean tanto compactos somo separados
entre sí. Es decir, que tengan:



– Alta similaridad intra-cluster
– Baja similaridad inter-cluster



• Un buen método debiera descubrir algunos o todos

los patrones ocultos en los datos

• La calidad del método de clustering depende de la

medida de similitud

• La forma de representación del cluster también
permite evaluar al método y afecta al resultado

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Hard clustering vs. Soft clustering

• El clustering típicamente asume que cada instancia

pertenece a exactamente un cluster, hard clustering.
No permite incertidumbre acerca de la membrecia de
una instancia a cada cluster en un conjunto de
clusters



• Soft clustering asigna probabilidades de pertenencia

de una instancia a más de un cluster



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

3

Principales técnicas de clustering

• Existen diferentes enfoques:



– Algoritmos de particionamiento

– Algoritmos jerárquicos

– Métodos basado en densidad (BD espaciales)

– Métodos basado en grilla

– Métodos basado en modelo

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Alg. Basados en Particionamiento

Construyen una partición del conjunto de datos D de n

objetos en un conjunto de k clusters


• Dado un k, intentan encontrar una partición de k

clusters que optimiza el criterio de particionamiento



– Global optimal: enumerar exhaustivamente todas las

particiones

– k-means [McQueen67]: cada cluster es representado por su

centro del cluster

– K-modes [Huang98]: idem para datos categóricos
– K-medoids or PAM (Partition around medoids) [Kaufman87]:
cada cluster se representa por uno de los objetos del cluster



Inteligencia Artificial - 2017



Prof. Dra. Silvia Schiaffino

4

K-Means

• Asume que las instancias son vectores de valores

reales

• Los clusters se basan en centroides o centros de

gravedad, o la media de las instancias en el cluster c:



• Las instancias se reasignan a clusters en base a su

distancia a los centroides



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

K-Means

Dado k (número de clusters) y el conjunto de datos n:



1. Arbitrariamente elegir k objetos como centros iniciales de

cluster (semillas)

2. Repetir:

3.

(re)asignar cada objeto al cluster con el cual el objeto sea
más similar, basándose en el valor medio de los objetos del
cluster

4. Actualizar los valores medios del cluster (centroides), es

decir calcular el valor medio de los objetos para cada cluster

5. Hasta que no se produzcan cambios (convergencia)

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

5

cxxc||1(c) K-Means

Elegir semillas

Reasignar clusters

Calcular centroides

Reasignar clusters

Calcular centroides

Reasignar clusters

Converge

x
x

x

x

x
x

K=2

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

K-Means

• Ventajas:

– Entre los algoritmos de particionamiento es eficiente
– Implementación sencilla

• Desventajas:

– Necesito conocer k de antemano
– Sensible a ruido
– El resultado puede variar en base a las semillas elegidas al

inicio

– Algunas semillas pueden resultar en una tasa de

convergencia menor

– La selección de semillas se puede basar en heurísticas o

resultados obtenidos por otros métodos

– Puede caer en mínimos locales
– No trata datos nominales (K-Modes)



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

6

Clustering Jerárquico

• Un dendograma muestra como se mezclan los

clusters de manera que cortando el dendograma en
diferentes niveles se consiguen differentes clusters



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Representaciones

d

f

e

b

c

a

a b c d e

f

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

7

Clustering Jerárquico

• Construye un árbol binario o dendograma a partir de

un conjunto de ejemplos:

– Aglomerativo (bottom-up) métodos que comienzan con cada
ejemplo en un cluster diferente y combinan iterativamente
los clusters para formar clusters mayores (Ej. AGNES,
Agglomerative Nesting [Kaufman90])



– Divisivo (top-down) métodos que comienzan con todos los
ejemplos en un mismo cluster y los separan en clusters más
chicos (Ej. DIANA, Divisive Analysis [Kaufman90])



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering Jerárquico

• Clustering Aglomerativo:

– Asume una función de similitud para determinar la similitud

de dos instancias

– Comienza con todas las instancias en un cluster separado

(cada instancia es un cluster) y junta los dos clusters que
son más similares en cada paso hasta que queda un único
cluster o se cumple un criterio de terminación

• Entre todos los cluster existentes determinar los dos clusters ci

y cj que son más similares

• Reemplazar ci y cj por un único cluster ci  cj

– Crea un árbol binario



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

8

Clustering Jerárquico

• Asume una función de similitud que determina la

similitud de dos instancias: sim(x,y)
– Por ejemplo la similitud del coseno o coeficiente de

correlación de Pearson

• Asume una función de similitud que determina la

similitud de dos clusters conteniendo multiples
instancias:
– Single Link: similitud de los dos elementos del cluster más

similares

– Complete Link: similitud de los dos elementos del cluster menos

similares

– Group Average: promedio de similitudes entre los elementos del

cluster



Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Similitud entre elementos

Distancia euclideana

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

9

Nnnnyxyxd12)(),(Nxxx1Nyyy1 Similitud entre elementos

Similitud del coseno

+1  Correlación del coseno  – 1

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Similitud entre elementos

Coeficiente de correlación de Pearson

Dos vectores

e

+1  Pearson Correlation  – 1

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

10

Nxxx1yxyxNyxCNiii1cosine1),(Nyyy1yxyxNxxx1])(][)([))((),(12121NiyiNixiNiyixipearsonmymxmymxyxCNyyy1xyxyNnnxxNm11NnnyyNm11 Similitud entre clusters

Single Link

Average Link

Complete Link

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering de documentos

Documentos iniciales

Matriz de Distancias

Dist A

B C D

20

7

2

10

25

3

A

B

C

D

A

B

C

D

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

11

),(max),(,yxsimccsimjicycxji),(min),(,yxsimccsimjicycxji Clustering de documentos

Documentos iniciales

Matriz de Distancias

Dist A

B C D

20

7

2

10

25

3

A

B

C

D

A

B

C

D

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering de documentos

Clusters actuales

Matriz de Distancias

Dist A

B C D

2

A

D

B

C

20

7

2

10

25

3

A

B

C

D

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

12

Clustering de documentos

Clusters actuales

Matriz de Distancias

Dist AD B C

AD

20

3

B

C

10

A

D

B

C

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering de documentos

Clusters actuales

Matriz de Distancias

Dist AD B C

AD

20

3

B

C

10

A

D

B

C

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

13

Clustering de documentos

Clusters actuales

Matriz de Distancias

Dist AD B C

AD

20

3

B

C

10

3

A

D

C

B

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering de documentos

Clusters actuales

Matriz de Distancias

B

10

Dist AD
C

AD
C

B

A

D

C

B

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

14

Clustering de documentos

Clusters actuales

Matriz de Distancias

B

10

Dist AD
C

AD
C

B

A

D

C

B

Inteligencia Artificial - 2017

Prof. Dra. Silvia Schiaffino

Clustering de documentos

Clusters actuales

Matriz de Distancias
  • Links de descarga
http://lwp-l.com/pdf5879  

Comentarios de: Clustering (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios