Download Minería de Datos

Módulo
Minería de Datos
Diplomado
Por
Elizabeth León Guzmán, Ph.D.
Profesora
Ingeniería de Sistemas
Grupo de Investigación MIDAS
Minería de Datos - Agrupamiento
Clustering
ECSAGO
Basado en:
● Densidad
● Conceptos de evolución natural
● Areas densas son clusters
● Clusters circulares  centro y radio
● Encuentra centros y radios de los clusters
●
Minería de Datos - Agrupamiento
Clustering
ECSAGO
Inspirado en la formación de “Nichos” en
la naturaleza
Cada nicho es un grupo (cluster) el
algoritmo intenta encontrar los nichos
usando un algoritmo evolutivo y una
técnica de “niching”
Minería de Datos - Agrupamiento


Algoritmo
evolutivo

Encuentra centroides
Un individuo  candidato a
ser centroide del cluster
Fitness  densidad de un
cluster hipotetico en esa
localización
Estrategía de
Niching
Optimización
multimodal: Permite mantener clusters (niches
representan clusters: centro y radio)
Minería de Datos - Agrupamiento
Algoritmo Genetico
Minería de Datos - Agrupamiento
Codificación
Un individuo representa un cluster candidato
El centroide es un vector n-dimensional (n el número de
dimensiones de los datos)
La escala (radio) es estimado usando optimización
analítica
Minería de Datos - Agrupamiento
Fitness
Fitness, para un candidato a centoride es la
densidad de un supuesto cluster en esa
localización
N
∑ w ij
f i=
j=1
σ 2i
where
 
w ij =exp −
d 2ij
2σ 2i
σi: proporcinal
al Niche radio o escala (tamaño).
2
σi
N
σ 2i =
1
2
∑ w ij d 2ij
j=1
N
∑ w ij
j=1
Minería de Datos - Agrupamiento
1 X radius
0.75 X radius
0.5 X radius
0.25 X radius
Minería de Datos - Agrupamiento
Reproducción
Operadores
●
Crossover - Cruce
Aplicar un punto de cruce independiente
●
Mutation - Mutación
●
Cada bit es complementado con alguna
probabilidad
9
Minería de Datos - Agrupamiento
Niching
●
Deterministic Crowding: Hijos remplazan al padre mas
cercano si ellos tienen mejor fitness
restricción en el Mating
Solo individuos que pertenecen al mismo niche pueden
reproducirse  los hijos pertenecen al mismo niche
¿
¿
¿
IF
¿ dist  P i , P
j
 K
max  σ
i
, σ
j

¿ THEN
¿ restrict
¿ mating
¿
10
Minería de Datos - Agrupamiento
Population Evolution for 10 cluster data
set
Initial
population
Binary
Encoding
Real
Encoding:
Faster
convergence
Gen #10
Gen #10
Gen #30
Gen #50
Gen #100
Gen #30
Gen #50
Gen #100
Minería de Datos - Agrupamiento
http://webmining.spd.louisville.edu/NSF_Career/s
oftware/clustering/ECSAGO/demo/
Minería de Datos - Agrupamiento