Clasificación No Supervisada
Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales Instituto Nacional de Astrofísica, Óptica y Electrónica [email protected]
Contenido
Introducción
Agrupamiento jerárquico
Métodos de reagrupamiento
Agrupamiento basado en grafos
Evaluación de agrupamientos
Clasificación No Supervisada
Dada una muestra de objetos no clasificados, obtener la estructuración en clases de dicha muestra.
4
¿Cuál es la forma natural de agrupar los personajes? Hombres vs. Mujeres
Clasificación No Supervisada
5
¿Cuál es la forma natural de agrupar los personajes?
¡¡¡ El clustering es subjetivo !!!
Clasificación No Supervisada
6
¿Cuál es la forma natural de agrupar los personajes? Simpsons vs. Empleados de la escuela de Springfield
Clasificación No Supervisada
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
y
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
y
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
y
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
y
Clasificación No Supervisada
Clasificación No Supervisada
Idea General Objetos muy similares deben estar en
el mismo agrupamiento
Objetos poco similares deben estar en diferente agrupamiento
Tipos de Clasificación No Supervisada
Restringida.- El número de clases en la que se
estructurará la muestra está previamente definido.
Libre.- El número de clases en la que se estructurará la muestra depende exclusivamente de los datos.
Tipos de agrupamientos
Disjuntos, los grupos no comparten elementos; forman una partición del conjunto de objetos
Traslapados, los grupos pueden compartir objetos; forman un cubrimiento del conjunto de objetos
Difusos, los grupos son conjuntos difusos; pueden formar una partición difusa o un cubrimiento difuso del conjunto de objetos
Estrategias para Clasificación No Supervisada
Jerárquica.- Se crea una jerarquía de agrupamientos, puede se aglomerativa o divisiva.
Reagrupamiento.- Se hace un primer agrupamiento y se va refinando iterativamente.
Basada en grafos.- Se representan los objetos y sus relaciones de semejanza mediante grafos y se define ciertas condiciones que deben cumplir los agrupamientos.
Agrupamiento Jerárquico Aglomerativo
Partiendo de los objetos individuales (grupos unitarios) agrupar los dos clusters más similares para formar uno nuevo
Repetir hasta que se obtenga un solo grupo con todos los objetos
Cada vez que se unen dos grupos se crea un nuevo nivel en la jerarquía
Ejemplos
Single linkage
Complete linkage
Average linkage
Mean linkage
Ward linkage
Agrupamiento Jerárquico Aglomerativo
Nivel 0
Nivel 2
Nivel 1
Nivel 3
Nivel 4
Nivel 5
x2 x4 x1 x6 x5 x3
Single Linkage
La distancia entre dos grupos está definida por la distancia entre los dos objetos más cercanos entre los grupos.
{ }),(min),( srCxCxji xxdCCd
jsir
∈∈
=
Complete Linkage
La distancia entre dos grupos está definida por la distancia entre los dos objetos más lejanos entre los grupos.
{ }),(max),( srCxCxji xxdCCd
jsir
∈∈
=
Average Linkage
La distancia entre dos grupos está definida por el promedio de las distancias entre los objetos de un grupo y los del otro.
∑ ∑∈ ∈
=ir jsCx Cx
srji
ji xxdCC
CCd ),(1),(
Mean Linkage
La distancia entre dos grupos está definida por la distancia entre las medias de los grupos.
∑
∑
∈
∈
=
=
=
jsr
isr
Cxxsr
jj
Cxxsr
ii
jiji
xxdC
xxdC
dCCd
,
,
),(1
),(1
),(),(
µ
µ
µµ
Ward Linkage
En cada iteración se unen los grupos que al ser unidos incrementen menos la suma de las varianzas de los grupos
Sea la varianza del grupo Ci
Sea la varianza de Ci∪Cj
La distancia entre cluster puede definirse como:
2iσ2ijσ
22
2
),(ji
ijji CCd
σσσ+
=
Agrupamiento Jerárquico Divisivo
Nivel 5
Nivel 3
Nivel 4
Nivel 2
Nivel 1
Nivel 0
x2 x4 x1 x6 x5 x3
Agrupamiento Jerárquico Divisivo
Partiendo de un grupo que contenga a todos los objetos y separando clusters para formar dos nuevos
Repetir hasta que todos los objetos estén separados (grupos unitarios)
Cada vez que se separa un grupos se crea un nuevo nivel en la jerarquía
En general son poco usados pues decidir cuál grupo
dividir y cómo dividirlo puede ser muy costoso
Usualmente se divide el grupo con mayor varianza y se aplica algún agrupador que produzca 2 grupos
Métodos de reagrupamiento
Generan un agrupamiento inicial
Ajustan parámetros
Reagrupan los objetos
Repiten hasta optimizar algún funcional de calidad
Ejemplos
k-means Expectation-Maximization (EM) K-means difuso
Algoritmo K-means
Objetivo
Encontrar una partición C1,…,Ck de un conjunto de objetos {O1,…,On} tal que se minimice:
∑ ∑= ∈
−k
i COij
ij
cOd1
)(
Algoritmo K-means
Entrada O1,…,On (objetos a agrupar) k (número de agrupamientos a formar)
Seleccionar aleatoriamente k objetos de la muestra (c1,…,ck)
Repetir hasta alcanzar un criterio de paro Asignar cada objeto Oi al cluster con el
centroide cj mas cercano Recalcular los centroides como la media de los
objetos asignados
Algoritmo K-means
Criterios de paro
Número máximo de iteraciones
No cambia ninguno de los centroides (c1,…,ck)
Se alcanza una cota de error
ε≤−∑ ∑= ∈
k
i COij
ij
cOd1
)(
Algoritmo K-means
Algoritmo K-means
Algoritmo EM Objetivo
Encontrar cómo se distribuyen los objetos en O1,…,On una partición C1,…,Ck dado un conjunto de parámetros y optimizar los parámetros de esta distribución
Pasos Inicializar k agrupamientos C1,…,Ck no vacíos y los
parámetros de la distribución Expectation
Ubicar cada Oi en la clase en la que p(Oi∈Cj) sea máxima Maximization
Recalcular los parámetros de la distribución con los agrupamientos formados
Repetir Expectation y Maximization hasta alcanzar un criterio de paro
Algoritmo EM (con distribución Normal) Suponer
Pasos
Inicializar k agrupamientos C1,…,Ck no vacíos y para cada uno calcular µj , Σj y P(Cj) usando sus objetos
Expectation
Para cada Oi, i=1,…,n
Maximization Para cada Cj, j=1,…,k
Recalcular µj , Σj y P(Cj) usando los objetos de Cj
Repetir Expectation y Maximization hasta alcanzar un criterio de paro
{ })|(max)( ijCi OCpOcj
=
),(~)|( jjij NCOp Σµ
Algoritmo EM (con distribución Normal)
Suponer
Pasos
Inicializar k agrupamientos C1,…,Ck y para cada uno calcular µj , Σj y P(Cj) usando sus objetos
Expectation
Para cada Oi, i=1,…,n y cada Cj, j=1,…,k
),(~)|( jjji NCOp Σµ
∑=
⋅
⋅=
⋅= k
rkki
jji
i
jjiij
CpCOp
CpCOpOp
CpCOpOCp
1)()|(
)()|()(
)()|()|(
Algoritmo EM (con distribución Normal)
Maximization Para cada Cj, j=1,…,k
Recalcular µj , Σj y P(Cj) usando los objetos de Cj
∑∑ −⋅−⋅
=Σ
iij
Tjiji
iij
j OCp
OOOCp
)|(
)()()|( µµ
∑∑ ⋅
=
iij
ii
ij
j OCp
OOCp
)|(
)|(µ
n
OCpCp i
ij
j
∑=
)|()(
Algoritmo EM (con distribución Normal)
Repetir Expectation y Maximization hasta alcanzar un criterio de paro
Al final
{ })|(max)( ijCi OCpOgrupoj
=
Criterios de paro
Número máximo de iteraciones
No cambia ninguno de los parámetros
Se maximiza/minimiza algún funcional de calidad/error, por ejemplo
∑ ∑= ∈
∈k
i COij
ij
COp1
)(
Algoritmo EM
Algoritmo EM
Algoritmo EM
Algoritmo K-means difuso Objetivo
Encontrar una partición difusa C1,…,Ck de un conjunto de objetos {O1,…,On} tal que se minimice:
Donde µij es la pertenencia del objeto j al agrupamiento i y m es un parámetro de fuzzificación, usualmente m=2
∑∑∑== =
==∀−k
iij
k
i
n
jij
mij njcOd
11 11),...,1( ;)()( µµ
Algoritmo K-means difuso
Entrada O1,…,On (objetos a agrupar) k (número de agrupamientos a formar)
Crear aleatoriamente k agrupamientos no vacíos (C1,…,Ck) y para cada uno calcular las centroides ci i=1,…,k como
∑∈
=ij CO
ii
i OC
c 1
Algoritmo K-means difuso
Repetir hasta alcanzar un criterio de paro Para cada objeto Oj recalcular las pertenencias µij en
cada agrupamiento Ci como
12
1 ),(),(
1
−
=∑
=
mk
r rj
ij
ij
cOdcOd
µ
Algoritmo K-means difuso
Recalcular los centroides ci para cada agrupamiento
Ci, i=1,…,k como
∑
∑
=
== n
j
mij
n
jj
mij
i
Oc
1
1
)(
)(
µ
µ
Algoritmo K-means difuso
Criterios de paro
Número máximo de iteraciones
No cambian mucho los centroides (c1,…,ck)
Se alcanza una cota de error
εµ ≤−∑∑= =
k
i
n
jij
mij cOd
1 1)()(
εµµ ≤−∑=
+k
iij
tij
tij
1
1 )(
Algoritmo K-means difuso
Agrupamiento basado en grafos
Generan un grafo de similitudes G=(V,E) No dirigido V es el conjunto de objetos (O1,…,On) (Oi,Oj)∈E si y solo si s(Oi,Oj)≥ε (d(Oi,Oj)≤ε)
Definen un criterio de agrupamiento
Buscan los subgrafos que cumplan el criterio
Ejemplos
Star Componentes conexas Max-clique
Ejemplo de grafo de similitudes
Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 -
O1
O2
O3 O4
O5
O6
dij O1 O2 O3 O4 O5 O6
O1 1 0.5 0.9 0.4 0.3 0.2
O2 0.5 1 0.8 0.4 0.5 0.1
O3 0.9 0.8 1 0.7 0.6 0.5
O4 0.4 0.4 0.7 1 0.9 0.8
O5 0.3 0.5 0.6 0.9 1 0.6
O6 0.2 0.1 0.5 0.8 0.6 1
Algoritmo Star Basado en subgrafos tipo estrella (star)
Un grafo tipo estrella está formado por un vértice (centro) y sus vértices adyacentes (satélites)
No necesita el número de agrupamientos
O1
O2
O3 O4
O5
O6
Seleccionar el vértice con mayor grado que no esté ya agrupado
Construir un grupo con el vértice seleccionado y sus vértices adyacentes
Repetir hasta que todos los vértices estén agrupados
Algoritmo Star
Algoritmo Star
Algoritmo Star
Algoritmo Star
Componentes conexas
Los grupos son las componentes conexas del grafo de similitudes
Una componente conexa es subgrafo para el cual hay un camino entre cualquiera de sus vértices
No necesita el número de agrupamientos
Algoritmo para obtener las Componentes conexas Se selecciona el objeto Oi de mayor
grado que no haya sido agrupado y se crea un agrupamiento con él
Se agregan al agrupamiento los Oj tales que Aij=1
Se agregan al agrupamiento todos los objetos Ok tales que Ajk=1, donde Oj ya fue agregado
Cuando no se puedan añadir más objetos el agrupamiento forma una componente conexa
Repetir hasta que todos los objetos hayan sido agrupados.
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Aij O1 O2 O3 O4 O5 O6
O1 - 0 0 0 0 0
O2 0 - 0 0 1 0
O3 0 0 - 1 0 0
O4 0 0 1 - 0 0
O5 0 1 0 0 - 1
O6 0 0 0 0 1 -
O1
O2
O3 O4
O5
O6
Componentes conexas
Cliques maximales Los grupos son los cliques maximales del grafo de
similitudes
Una clique es un subrafo en el cual cada nodo está conectado con todos los demás
Es maximal si no está contenido en otro clique
No necesita el número de agrupamientos
Algoritmo Bron–Kerbosch para obtener los Cliques Maximales Inicia llamando BronKerbosch(Ø, V, Ø)
BronKerbosch(R, P, X)
Si P y X son ambos vacíos R es un clique maximal
Para cada objeto v en P N(v) = nodos adyacentes a v BronKerbosch( R⋃{v}, P⋂N(v), X⋂N(v)
) P = P \ {v} X = X ⋃ {v}
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }∅=
=∅=
XOOOOOOP
R
654321 ,,,,,
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }
{ }31
654321
)(
,,,,,
OvNOvX
OOOOOOPR
==∅=
=∅=
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }∅=
==
XOPOR
3
1
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }
{ },,,,)( 54213
3
1
OOOOvNOvX
OPOR
==∅=
==
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }
∅=∅=
=
XP
OOR 31,
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }
{ }32
1
65432
)(
,,,,
OvNOvOX
OOOOOPR
====∅=
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }∅=
==
XOPOR
3
2
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }
{ },,,,)( 54213
3
2
OOOOvNOvX
OPOR
==∅=
==
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }
∅=∅=
=
XP
OOR 32 ,
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }
{ }54213
21
6543
,,,)( ,
,,,
OOOOvNOvOOX
OOOOPR
====∅=
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }{ }21
54
3
,,OOXOOP
OR
===
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }{ }
{ }6534
21
54
3
,,)( ,,
OOOvNOvOOXOOP
OR
=====
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }∅=
==
XOP
OOR
5
43,
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }
{ }6435
5
43
,,)(
,
OOOvNOvX
OPOOR
==∅=
==
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }
∅=∅=
=
XP
OOOR 543 ,,
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }
{ }6534
321
654
,,)( ,,,,
OOOvNOvOOOXOOOP
R
====∅=
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }{ }3
65
4
,OX
OOPOR
===
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }{ }
{ }6435
3
65
4
,,)(
,
OOOvNOvOX
OOPOR
=====
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }{ }3
6
54 ,
OXOP
OOR
===
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }{ }{ }
{ }546
3
6
54
,)(
,
OOvNOvOXOP
OOR
=====
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
{ }
∅=∅=
=
XP
OOOR 654 ,,
Cliques maximales Aij O1 O2 O3 O4 O5 O6
O1 - 0 1 0 0 0
O2 0 - 1 0 0 0
O3 1 1 - 1 1 0
O4 0 0 1 - 1 1
O5 0 0 1 1 - 1
O6 0 0 0 1 1 - O1
O2
O3 O4
O5
O6
Agrupamiento Online (data streams)
Los objetos se procesan como van llegando
Cada objeto se procesa una sola vez
No almacenan los datos en memoria pues se parte de la suposición de que son potencialmente infinitos
Los resultados se muestran a petición del usuario
Ejemplos OnLine k-means DenStream
Online K-means (algoritmo de Loyd) Supone que cada objeto contribuye igual para
determinar los centros de los agrupamientos
Inicializar los centros de los agrupamientos zi; i=1,…,k
Inicializar ni=0; i=1,…,k
Cada vez que se obtiene un nuevo objeto x Determinar el centro zi más cercano a x Actualizar el número de objetos en el agrupamiento i ni=ni+1 Actualizar el centro del agrupamiento i zi=zi+(x−zi)/ni
DenStream Algoritmo de Agrupamiento basado en
densidad
Versión online de DBSCAN
Los agrupamientos son regiones densas en el espacio de los objetos, separadas por regiones de baja densidad
Agrupamiento basado en densidad
Alternativa a los tipo k-means
ε-Vecindad ε-vecinad de p.– Objetos dentro de la
vecindad de radio ε de p
“Alta densidad” – Si la ε-vecindad de un objeto contiene al menos MinPts objetos
Si MinPts=4
La densidad de p es “alta”
La densidad de q es “baja”
}),(|{:)( εε ≤qpdqpN
q
ε ε p
Objetos Core, Border u Outlier
Si MinPts = 5
Core
Border
Outlier
p es un objeto “core” si su ε-vecindad tiene al menos MinPts objetos p es un objeto “border” si su ε-vecindad tiene menos de MinPts objetos pero está en la ε-vecindad de un objeto “core” p es “outlier” si no es “core” ni “border”
Alcanzable por densidad Un objeto q es directamente alcanzable por
densidad desde un objeto p si p es un objeto “core” y q está en la ε-vecindad de p
Si MinPts=4 q es directamente
alcanzable desde p p no es directamente
alcanzable desde q q
ε ε p
Alcanzable por densidad Un objeto q es alcanzable por densidad
desde un objeto p si existe una sucesión de puntos p1,p2,…,pn tal que p1=p, pn=q y para todo pi (i=1,…,n-1) pi+1 es directamente alcanzable desde pi
Si MinPts=7 p es alcanzable por
densidad desde q q no es alcanzable por
densidad desde p
p
q p2
p1
DBSCAN
Etiquetar cada objeto como “core”, “border” o “outlier”
Eliminar los objetos “outlier”
Para cada objeto “core” p que no haya sido ya procesado Crear un nuevo agrupamiento con p y todos los
objetos alcanzables desde p Marcar todos los objetos alcanzables desde p
como ya procesados
DBSCAN
DenStream Está basado en micro clusters
Usa una función de decaimiento f(t)=2-t
Un mcp (micro cluster potencial) es una terna (CF1,CF2,w) donde
DenStream El centro y radio de un mcp se
calculan como:
DenStream
Un mco (micro cluster outlier) es una cuarteta (CF1,CF2,w,T0) donde T0 es el tiempo de creación del mco
<
DenStream Tiene dos fases
Fase online, en la cual se crean y
mantienen los micro-clusters
Fase offline en la cual se crean los agrupamientos
Fase online Cada vez que se obtiene un nuevo objeto x Se calcula la distancia entre x y los centros de los mcp para
determinar el más cercano Se calcula el radio r del mcp más cercano a x al incluir x Si r≤ε
se agrega x a este mcp En otro caso
Se calcula la distancia entre x y los centros de los mca para determinar el más cercano
Se calcula el peso w del mco más cercano a x al incluir a x
Si w≥βμ se agrega x a este mco y se convierte en mcp
En otro caso Se crea un nuevo mco con x
Todos los micro-clusters (mcp o mco) en los que no se incluyo a x, se les dividen todos sus parámetros por 2
Los mco con (Tactual-T0)>Tmax se eliminan
Fase online Para agregar x a un mcp/mca se toma:
CF1=CF1+x CF2=CF2+SS(x) w=w+1
Para crear un nuevo mca a partir de x se
toma CF1=x CF2=SS(x) w=1 T0=Tactual
Fase offline
Se toman los centros de los mcp como objetos a agrupar
Se aplica una variante de DBSCAN en la cual
}),(|{:)( jijiji rrccdccN +≤ε
Validación de Agrupamientos
¿Qué tan bueno es el resultado de un algoritmo de agrupamiento?
¿Para qué evaluar agrupamientos?
Para verificar si los agrupamientos obtenidos son buenos
Para comparar algoritmos de agrupamiento
Para comparar dos agrupamientos
101
¿Cuál es la forma natural de agrupar los personajes? Hombres vs. Mujeres
Validación de Agrupamientos
102
¿Cuál es la forma natural de agrupar los personajes?
¡¡¡ El clustering es subjetivo !!!
Validación de Agrupamientos
103
¿Cuál es la forma natural de agrupar los personajes? Simpsons vs. Empleados de la escuela de Springfield
Validación de Agrupamientos
Validación de Agrupamientos
¿Cómo evaluar el resultado de un agrupador? Matriz de similitud
Índices de Validación
Matriz de similitud o Ordenamos los datos en la matriz de
similitud con respecto a los clusters en los que quedan los datos e inspeccionamos visualmente
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
y
Points
Poin
ts
20 40 60 80 100
10
20
30
40
50
60
70
80
90
100Similarity
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
0 0.2 0.4 0.6 0.8 10
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
x
y
Points
Poin
ts
20 40 60 80 100
10
20
30
40
50
60
70
80
90
100Similarity
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1Clusters en datos aleatorios (DBSCAN y k-Means)
Points
Poin
ts
20 40 60 80 100
10
20
30
40
50
60
70
80
90
100Similarity
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Matriz de similitud
Se puede detectar si el número de clusters es adecuado
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
500 1000 1500 2000 2500 3000
500
1000
1500
2000
2500
3000
Matriz de similitud
Índices de validación
Tipos de índices de validación
Externos: Basados en medir qué tan bien se reconstruye una estructuración conocida.
Internos: Basados en la estructura de los agrupamientos, comúnmente usan una función de comparación de objetos.
Índices de validación internos
Cohesión
Separación
Coeficiente de Silhouette
Índice de Dunn
Cohesion: Mide qué tan cercanos son los objetos dentro de los clusters Separación: Mide qué tan separados están los clusters de la media global
∑∑∈
−=i Cx
ii
mxCohesión 2)(
∑ −=i
ii mmCSeparación 2)(
Índices de validación internos
Combina ideas de cohesión y Separación
Para cada objeto Oi
ai = promedio de distancias entre Oi y los objetos en su mismo agrupamiento
bi = promedio de distancias entre Oi y los objetos del agrupamiento más cercano
sili = (bi - ai)/ max(ai, bi)
m
sils
m
ii∑
== 1
Coeficiente Silhouette
Índice de Dunn
),(min),(,
yxdCCdji CyCxji ∈∈
=
),(max)(,
yxdCdiamiCyxi ∈
=
{ }
=≤≤≠
≤≤≤≤ )(max),(
minmin1
11lkl
ji
jikjkik Cdiam
CCdD
Rand Index
Índice de Jaccard
Pureza
Cluster Accuracy
Normalized Mutual Information
Índices de validación externos
Rand Index
DCBADARandIndex+++
+=
BAAP+
=
CAAR+
=
#Pares de
objetos
Mismo cluster
Diferente Cluster
Misma Clase A C
Diferente Clase B D
Índice de Jaccard
CBAAexJaccardInd++
=
#Pares de
objetos
Mismo cluster
Diferente Cluster
Misma Clase A C
Diferente Clase B D
Para cada cluster i=1,…,k (número de clusters)
aij = Número de objetos de la clase j en el cluster i
ni = Número de objetos en el cluster i
purezai = max(aij)/ ni j
k
purezaPureza i
i∑=
Pureza
Cluster Accuracy
=
= ∑=
caso otroen 0 de clase la a asociado está )(1
)(
)(11
iii
m
iiACC
OOclusterOAcc
OAccm
Cluster
Normalized Mutual Information
∑∑
∑∑
==
= =
⋅
=nc
j
jj
k
i
ii
k
i
nc
j ji
ijij
nn
nnnn
nnnn
nNMI
11
1 1
loglog
log
Donde: k es el número de agrupamientos nc es el número de clases ni es el número de objetos en el agrupamiento i nj es el número de objetos en la clase j nij es el número de objetos que están en el
agrupamiento i y en la clase j