Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada...
Transcript of Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada...
![Page 1: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/1.jpg)
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]
![Page 2: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/2.jpg)
Contenido
Introducción
Agrupamiento jerárquico
Métodos de reagrupamiento
Agrupamiento basado en grafos
Evaluación de agrupamientos
![Page 3: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/3.jpg)
Clasificación No Supervisada
Dada una muestra de objetos no clasificados, obtener la estructuración en clases de dicha muestra.
![Page 4: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/4.jpg)
4
¿Cuál es la forma natural de agrupar los personajes? Hombres vs. Mujeres
Clasificación No Supervisada
![Page 5: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/5.jpg)
5
¿Cuál es la forma natural de agrupar los personajes?
¡¡¡ El clustering es subjetivo !!!
Clasificación No Supervisada
![Page 6: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/6.jpg)
6
¿Cuál es la forma natural de agrupar los personajes? Simpsons vs. Empleados de la escuela de Springfield
Clasificación No Supervisada
![Page 7: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/7.jpg)
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
![Page 8: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/8.jpg)
Clasificación No Supervisada
Idea General Objetos muy similares deben estar en
el mismo agrupamiento
Objetos poco similares deben estar en diferente agrupamiento
![Page 9: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/9.jpg)
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.
![Page 10: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/10.jpg)
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
![Page 11: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/11.jpg)
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.
![Page 12: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/12.jpg)
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
![Page 13: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/13.jpg)
Agrupamiento Jerárquico Aglomerativo
Nivel 0
Nivel 2
Nivel 1
Nivel 3
Nivel 4
Nivel 5
x2 x4 x1 x6 x5 x3
![Page 14: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/14.jpg)
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
∈∈
=
![Page 15: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/15.jpg)
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
∈∈
=
![Page 16: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/16.jpg)
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),(
![Page 17: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/17.jpg)
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
),(),(
µ
µ
µµ
![Page 18: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/18.jpg)
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
σσσ+
=
![Page 19: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/19.jpg)
Agrupamiento Jerárquico Divisivo
Nivel 5
Nivel 3
Nivel 4
Nivel 2
Nivel 1
Nivel 0
x2 x4 x1 x6 x5 x3
![Page 20: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/20.jpg)
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
![Page 21: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/21.jpg)
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
![Page 22: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/22.jpg)
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
)(
![Page 23: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/23.jpg)
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
![Page 24: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/24.jpg)
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
)(
![Page 25: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/25.jpg)
Algoritmo K-means
![Page 26: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/26.jpg)
Algoritmo K-means
![Page 27: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/27.jpg)
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
![Page 28: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/28.jpg)
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 Σµ
![Page 29: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/29.jpg)
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)()|(
)()|()(
)()|()|(
![Page 30: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/30.jpg)
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
∑=
)|()(
![Page 31: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/31.jpg)
Algoritmo EM (con distribución Normal)
Repetir Expectation y Maximization hasta alcanzar un criterio de paro
Al final
{ })|(max)( ijCi OCpOgrupoj
=
![Page 32: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/32.jpg)
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
![Page 33: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/33.jpg)
Algoritmo EM
![Page 34: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/34.jpg)
Algoritmo EM
![Page 35: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/35.jpg)
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( ;)()( µµ
![Page 36: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/36.jpg)
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
![Page 37: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/37.jpg)
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
µ
![Page 38: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/38.jpg)
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
)(
)(
µ
µ
![Page 39: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/39.jpg)
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 )(
![Page 40: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/40.jpg)
Algoritmo K-means difuso
![Page 41: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/41.jpg)
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
![Page 42: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/42.jpg)
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
![Page 43: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/43.jpg)
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
![Page 44: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/44.jpg)
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
![Page 45: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/45.jpg)
Algoritmo Star
![Page 46: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/46.jpg)
Algoritmo Star
![Page 47: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/47.jpg)
Algoritmo Star
![Page 48: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/48.jpg)
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
![Page 49: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/49.jpg)
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.
![Page 50: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/50.jpg)
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
![Page 51: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/51.jpg)
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
![Page 52: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/52.jpg)
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
![Page 53: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/53.jpg)
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
![Page 54: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/54.jpg)
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
![Page 55: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/55.jpg)
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
![Page 56: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/56.jpg)
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
![Page 57: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/57.jpg)
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
![Page 58: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/58.jpg)
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
![Page 59: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/59.jpg)
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}
![Page 60: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/60.jpg)
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
![Page 61: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/61.jpg)
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 ,,,,,
![Page 62: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/62.jpg)
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
==∅=
=∅=
![Page 63: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/63.jpg)
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
![Page 64: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/64.jpg)
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
==∅=
==
![Page 65: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/65.jpg)
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,
![Page 66: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/66.jpg)
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
====∅=
![Page 67: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/67.jpg)
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
![Page 68: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/68.jpg)
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
==∅=
==
![Page 69: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/69.jpg)
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 ,
![Page 70: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/70.jpg)
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
====∅=
![Page 71: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/71.jpg)
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
===
![Page 72: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/72.jpg)
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
=====
![Page 73: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/73.jpg)
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,
![Page 74: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/74.jpg)
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
==∅=
==
![Page 75: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/75.jpg)
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 ,,
![Page 76: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/76.jpg)
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
====∅=
![Page 77: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/77.jpg)
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
===
![Page 78: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/78.jpg)
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
=====
![Page 79: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/79.jpg)
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
===
![Page 80: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/80.jpg)
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
=====
![Page 81: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/81.jpg)
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 ,,
![Page 82: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/82.jpg)
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
![Page 83: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/83.jpg)
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
![Page 84: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/84.jpg)
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
![Page 85: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/85.jpg)
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
![Page 86: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/86.jpg)
Agrupamiento basado en densidad
Alternativa a los tipo k-means
![Page 87: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/87.jpg)
ε-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
![Page 88: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/88.jpg)
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”
![Page 89: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/89.jpg)
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
![Page 90: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/90.jpg)
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
![Page 91: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/91.jpg)
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
![Page 92: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/92.jpg)
DBSCAN
![Page 93: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/93.jpg)
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
![Page 94: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/94.jpg)
DenStream El centro y radio de un mcp se
calculan como:
![Page 95: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/95.jpg)
DenStream
Un mco (micro cluster outlier) es una cuarteta (CF1,CF2,w,T0) donde T0 es el tiempo de creación del mco
<
![Page 96: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/96.jpg)
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
![Page 97: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/97.jpg)
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
![Page 98: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/98.jpg)
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
![Page 99: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/99.jpg)
Fase offline
Se toman los centros de los mcp como objetos a agrupar
Se aplica una variante de DBSCAN en la cual
}),(|{:)( jijiji rrccdccN +≤ε
![Page 100: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/100.jpg)
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
![Page 101: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/101.jpg)
101
¿Cuál es la forma natural de agrupar los personajes? Hombres vs. Mujeres
Validación de Agrupamientos
![Page 102: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/102.jpg)
102
¿Cuál es la forma natural de agrupar los personajes?
¡¡¡ El clustering es subjetivo !!!
Validación de Agrupamientos
![Page 103: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/103.jpg)
103
¿Cuál es la forma natural de agrupar los personajes? Simpsons vs. Empleados de la escuela de Springfield
Validación de Agrupamientos
![Page 104: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/104.jpg)
Validación de Agrupamientos
¿Cómo evaluar el resultado de un agrupador? Matriz de similitud
Índices de Validación
![Page 105: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/105.jpg)
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
![Page 106: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/106.jpg)
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
![Page 107: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/107.jpg)
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
![Page 108: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/108.jpg)
Í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.
![Page 109: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/109.jpg)
Índices de validación internos
Cohesión
Separación
Coeficiente de Silhouette
Índice de Dunn
![Page 110: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/110.jpg)
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
![Page 111: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/111.jpg)
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
![Page 112: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/112.jpg)
Índice de Dunn
),(min),(,
yxdCCdji CyCxji ∈∈
=
),(max)(,
yxdCdiamiCyxi ∈
=
{ }
=≤≤≠
≤≤≤≤ )(max),(
minmin1
11lkl
ji
jikjkik Cdiam
CCdD
![Page 113: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/113.jpg)
Rand Index
Índice de Jaccard
Pureza
Cluster Accuracy
Normalized Mutual Information
Índices de validación externos
![Page 114: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/114.jpg)
Rand Index
DCBADARandIndex+++
+=
BAAP+
=
CAAR+
=
#Pares de
objetos
Mismo cluster
Diferente Cluster
Misma Clase A C
Diferente Clase B D
![Page 115: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/115.jpg)
Índice de Jaccard
CBAAexJaccardInd++
=
#Pares de
objetos
Mismo cluster
Diferente Cluster
Misma Clase A C
Diferente Clase B D
![Page 116: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/116.jpg)
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
![Page 117: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/117.jpg)
Cluster Accuracy
=
= ∑=
caso otroen 0 de clase la a asociado está )(1
)(
)(11
iii
m
iiACC
OOclusterOAcc
OAccm
Cluster
![Page 118: Clasificación No Supervisada - INAOEariel/Agrupamiento2016.pdf · Clasificación No Supervisada Jesús Ariel Carrasco Ochoa Coordinación de Ciencias Computacionales . Instituto](https://reader034.fdocumento.com/reader034/viewer/2022052521/60a2fe6a8c6b05234a2a2a1b/html5/thumbnails/118.jpg)
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