Scribd
Cargar
69 vistas10 páginas

Algoritmo K-Means en Clustering

K-Means es un algoritmo de clustering que agrupa puntos de datos en clusters utilizando centroides. Calcula la distancia de cada punto a los centroides y lo asigna al cluster más cercano. Luego recalcula la posición de los centroides y repite el proceso hasta converger, minimizando la suma de distancias cuadráticas dentro de cada cluster.

Cargado por

ABISAI RASCON ESTRADA
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
69 vistas10 páginas

Algoritmo K-Means en Clustering

K-Means es un algoritmo de clustering que agrupa puntos de datos en clusters utilizando centroides. Calcula la distancia de cada punto a los centroides y lo asigna al cluster más cercano. Luego recalcula la posición de los centroides y repite el proceso hasta converger, minimizando la suma de distancias cuadráticas dentro de cada cluster.

Cargado por

ABISAI RASCON ESTRADA
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

K-Means

Reconocimiento de Patrones

M.I. Joseph Isaac Ramírez Hernández


Introducción
Reconocimiento de Patrones

• Fue descrito originalmente por


Macqueen en 1967.
• Es un algoritmo de clustering para la
predicción de clases de acuerdo a un
conjunto de características.
• El clustering se define como el
proceso de organizar puntos de
acuerdo a alguna métrica especial.
Introducción
Reconocimiento de Patrones

• La idea original de Macqueen era


agrupar puntos utilizando un punto
llamado media.
• En 1988 Jain y Dubes diseñan un
algoritmo basado en el trabajo de
Macqueen, el cual utiliza un número
definido de clusters.
• El algoritmo converge utilizando una
función de error.
Definición formal
Reconocimiento de Patrones

• Sea D un conjunto de datos con n


instancias (vectores de características) Conjunto de datos D
y sean C1, C2, . . . , Ck , K c l u s t e r s
División en clusters
disjuntos de D, tal que
C1 C2 Ck
K
∩i=1 Ck = D
•

¡No requerimos conjuntos de entrenamiento y prueba!


Definición formal
Reconocimiento de Patrones

• La función de error se define como


K

∑∑
E= d(x, μ(Ck))
k=1 x∈Ck

Donde μ(Ck) es el centroide del cluster Ck y d(x, μ(Ck)) es la distancia de


cada vector x al centroide.
Definición formal
Reconocimiento de Patrones

• Considerando la función de error cuadrado medio, se tiene que el error es

K
2
∑∑
E= | | x − μ(Ck) | |
k=1 x∈Ck
Definición formal
Reconocimiento de Patrones

• Sea Ck el k-ésimo cluster, xi un vector de Ck y ck la media (centroide) del k-


ésimo cluster.

K
∑ ∑
2 − 2(xi − ck) = 0 | Ck | ck = xi
∑∑
E= (x − ck)
k=1 x∈Ck xi∈Ck xi∈Ck

K 1
∂E
∑ ∑
ck = xi
| Ck | x∑
ck = xi
∑∑
=−2 (x − ck)
∂ck k=1 x∈C xi∈Ck xi∈Ck ∈C
k i k
Algoritmo
Reconocimiento de Patrones
Algoritmo
Reconocimiento de Patrones

X1 X2 Se desean buscar dos clusters distintos, para ello se inicializan 2 centroides


2 1
-1 3 Primera Iteración
3 4
C1 = (1/6,5/3) C2 = (5/6,7/3)
2 3
-2 -2 Se calculan las distancias a ambos centroides
-3 1 y se clasifica al más cercano
4 1

(6 ) (3 )
1 3 2 2
1 5
-4 1 d1 = −2 + − 1 ≈ 3.80
3 3
-3 3

(6 ) (3 )
2 2
4 3 5 7
d2 = −2 + − 1 ≈ 3.138
Algoritmo
Reconocimiento de Patrones

Se calculan los nuevos centroides utilizando la expresión


Clase Clase
1
| Ck | x∑
X1 X2 X1 X2 ck = xi
-1 3 2 1
∈C i k
-2 -2 -1 3
-3 1 3 4

( 5 5)
-4 1 2 3
1 −13 6
-3 3 -2 -2 C1 = (−13,6) = ,
-3 1 5
4 1

(7 7 )
1 5 11
C2 = (5,11) = ,
¡Calcular el error y comparar con tolerancia! 7

También podría gustarte