El algoritmo k-means (K medias)

K-means es un algoritmo de clasificación no supervisada (clusterización) que agrupa objetos en k grupos basándose en sus características. El agrupamiento se realiza minimizando la suma de distancias entre cada objeto y el centroide de su grupo o cluster. Se suele usar la distancia cuadrática. El algoritmo consta de tres pasos:

pasos del algoritmo k means

Inicialización: una vez escogido el número de grupos, k, se establecen k centroides en el espacio de los datos, por ejemplo, escogiéndolos aleatoriamente.
Asignación objetos a los centroides: cada objeto de los datos es asignado a su centroide más cercano.
Actualización centroides: se actualiza la posición del centroide de cada grupo tomando como nuevo centroide la posición del promedio de los objetos pertenecientes a dicho grupo.

Centroides para K means Se repiten los pasos 2 y 3 hasta que los centroides no se mueven, o se mueven por debajo de una distancia umbral en cada paso.

El algoritmo k-means resuelve un problema de optimización, siendo la función a optimizar (minimizar) la suma de las distancias cuadráticas de cada objeto al centroide de su cluster.

Los objetos se representan con vectores reales de d dimensiones (x1,x2,…,xn) y el algoritmo k-means construye k grupos donde se minimiza la suma de distancias de los objetos, dentro de cada grupo S={S1,S2,…,Sk} , a su centroide. El problema se puede formular de la siguiente forma:

\[ \underset{\mathbf{S}}{\mathrm{min}}\; E\left(\boldsymbol{\mu_{i}}\right)=\underset{\mathbf{S}}{\mathrm{min}}\sum_{i=1}^{k}\sum_{\mathbf{x}_{j}\in S_i}\left\Vert \mathbf{x}_{j}-\boldsymbol{\mu}_{i}\right\Vert ^{2} \quad (1) \]

donde S es el conjunto de datos cuyos elementos son los objetos xj representados por vectores, donde cada uno de sus elementos representa una característica o atributo. Tendremos k grupos o clusters con su correspondiente centroide μi . En cada actualización de los centroides, desde el punto de vista matemático, imponemos la condición necesaria de extremo a la función E(μi) que, para la función cuadrática (1) es:

\[ \frac{\partial E}{\partial\boldsymbol{\mu}_{i}}=0\;\Longrightarrow\;\boldsymbol{\mu}_{i}^{(t+1)}=\frac{1}{\left|S_{i}^{(t)}\right|}\sum_{\mathbf{x}_{j}\in S_{i}^{(t)}}\mathbf{x}_{j} \] y se toma el promedio de los elementos de cada grupo como nuevo centroide. Las principales ventajas del método k-means son que es un método sencillo y rápido. Pero es necesario decidir el valor de k y el resultado final depende de la inicialización de los centroides. En principio no converge al mínimo global sino a un mínimo local.

Encontrado el codo para los clusters

hasta que punto se incluyen nuevos clusters

Ejercicio de clasifiaccion no supervisada usando k means aplicado a iris dataset

Datos

df <- iris 
head(iris)

##   Sepal.Length Sepal.Width Petal.Length Petal.Width Species
## 1          5.1         3.5          1.4         0.2  setosa
## 2          4.9         3.0          1.4         0.2  setosa
## 3          4.7         3.2          1.3         0.2  setosa
## 4          4.6         3.1          1.5         0.2  setosa
## 5          5.0         3.6          1.4         0.2  setosa
## 6          5.4         3.9          1.7         0.4  setosa

Primer grafica coloreando las clases (especies)

ggplot(df, aes(Petal.Length, Petal.Width)) + geom_point(aes(col=Species), size=4 )

Como podemos ver, setosa se agrupará más fácilmente. Mientras tanto, hay ruido entre versicolor y virginica incluso cuando parecen perfectamente agrupados.

Ejecutemos el modelo. kmeans está instalado en el paquete base de R, por lo que no tenemos que instalar ningún paquete.

En la función kmeans, es necesario establecer el centro, que es el número de grupos que queremos agrupar. En este caso, sabemos que este valor será 3. Configuremos eso.

, pero veamos cómo construiríamos el modelo si no lo supiéramos.

set.seed(101)
irisCluster <- kmeans(df[,1:4], center=3, nstart = 20 )
irisCluster

## K-means clustering with 3 clusters of sizes 38, 62, 50
## 
## Cluster means:
##   Sepal.Length Sepal.Width Petal.Length Petal.Width
## 1     6.850000    3.073684     5.742105    2.071053
## 2     5.901613    2.748387     4.393548    1.433871
## 3     5.006000    3.428000     1.462000    0.246000
## 
## Clustering vector:
##   [1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [38] 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
##  [75] 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 1 1 1 1 2 1 1 1 1
## [112] 1 1 2 2 1 1 1 1 2 1 2 1 2 1 1 2 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 1 2 1
## [149] 1 2
## 
## Within cluster sum of squares by cluster:
## [1] 23.87947 39.82097 15.15100
##  (between_SS / total_SS =  88.4 %)
## 
## Available components:
## 
## [1] "cluster"      "centers"      "totss"        "withinss"     "tot.withinss"
## [6] "betweenss"    "size"         "iter"         "ifault"

Comparando estos clusters con los datos originales

table(irisCluster$cluster, df$Species)

##    
##     setosa versicolor virginica
##   1      0          2        36
##   2      0         48        14
##   3     50          0         0

Agrupando los datos en clusters

clusplot(iris, irisCluster$cluster, color=T, shade=T, lines=0)

Podemos ver el racimo setosa perfectamente explicado, mientras que virginica y versicolor tienen un poco de ruido entre sus racimos.

Como decía antes, no siempre tendremos los datos etiquetados. Si quisiéramos saber el número exacto de centros, deberíamos haber construido el método del codo.

tot.withinss <- vector(mode="character", length=10)
for (i in 1:10){
  irisCluster <- kmeans(df[,1:4], center=i, nstart=20)
  tot.withinss[i] <- irisCluster$tot.withinss
}

Graficar el codo obtenido

plot(1:10, tot.withinss, type="b", pch=19)

Descarga est codigo

xfun::embed_file("A3U1.Rmd")

Download A3U1.Rmd

A3U1

Badouin

2/3/2022

Clasificación de datos

Clasificación supervisada

Clasificación no supervisada