El algoritmo k-means aplicado a clasificación y procesamiento de imágenes¶
Clasificación¶
El aprendizaje de máquina (Machine Learning) estudia el aprendizaje automático a partir de datos (data-driven, gobernado por los datos) para conseguir hacer prediciones precisas a partir de observaciones con datos previos.
La clasificación automática de objetos o datos es uno de los objetivos del aprendizaje de máquina. Podemos considerar tres tipos de algoritmos:
Clasificación supervisada: disponemos de un conjunto de datos (por ejemplo, imágenes de letras escritas a mano) que vamos a llamar datos de entrenamiento y cada dato está asociado a una etiqueta (a qué letra corresponde cada imagen). ConstruÃmos un modelo en la fase de entrenamiento (training) utilizando dichas etiquetas, que nos dicen si una imagen está clasificada correcta o incorrectamente por el modelo. Una vez construÃdo el modelo podemos utilizarlo para clasificar nuevos datos que, en esta fase, ya no necesitan etiqueta para su clasificación, aunque sà la necesitan para evaluar el porcentaje de objetos bien clasificados.
Clasificación no supervisada: los datos no tienen etiquetas (o no queremos utilizarlas) y estos se clasifican a partir de su estructura interna (propiedades, caracterÃsticas).
Clasificación semisupervisada: algunos datos de entrenamiento tienen etiquetas, pero no todos. Este último caso es muy tÃpico en clasificación de imágenes, donde es habitual disponer de muchas imágenes mayormente no etiquetadas. Estos se pueden considerar algoritmos supervisados que no necesitan todas las etiquetas de los datos de entrenamiento.
En esta práctica vamos a ver varios ejemplos de utilización del algoritmo de clasificación no supervisada k-means para la clasificación y procesamiento de imágenes.
El algoritmo k-means¶
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:
- 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.
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 $\left(\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\right)$ y el algoritmo k-means construye $k$ grupos donde se minimiza la suma de distancias de los objetos, dentro de cada grupo $\mathbf{S}=\left\{ S_{1},S_{2},\ldots,S_{k}\right\}$, 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 $\mathbf{S}$ es el conjunto de datos cuyos elementos son los objetos $\mathbf{x}_{j}$ representados por vectores, donde cada uno de sus elementos representa una caracterÃstica o atributo. Tendremos $k$ grupos o clusters con su correspondiente centroide $\boldsymbol{\mu_{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\left(\boldsymbol{\mu_{i}}\right)$ 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.
Implementar el método k-means de forma que clasifique datos con dos dimensiones. Utilizarlo para clasificar en tres grupos los datos generados a continuación.
Para que las figuras se inserten en este notebook, en lugar de abrir una ventana nueva, ejecutamos
%matplotlib inline
Importamos las librerÃas y funciones necesarias
import numpy as np
import matplotlib.pyplot as plt
Generamos datos aleatorios 2D para tres clusters y los representamos
np.random.seed(7)
x1 = np.random.standard_normal((100,2))*0.6+np.ones((100,2))
x2 = np.random.standard_normal((100,2))*0.5-np.ones((100,2))
x3 = np.random.standard_normal((100,2))*0.4-2*np.ones((100,2))+5
X = np.concatenate((x1,x2,x3),axis=0)
plt.plot(X[:,0],X[:,1],'k.')
plt.show()
%run Ejercicio1.py
En los demás ejercicios de esta práctica vamos a usar la función KMeans de la librerÃa sklearn.
from sklearn.cluster import KMeans
Agrupamos los puntos con k-means usando $k=3$
n = 3
k_means = KMeans(n_clusters=n)
k_means.fit(X)
El resultado son tres centroides en torno a los cuales se agrupan los puntos y las etiquetas para cada punto que indican a qué cluster pertenece dicho punto
centroides = k_means.cluster_centers_
etiquetas = k_means.labels_
Dibujamos ahora los puntos y los centroides, utilizando un color distinto para los puntos de cada cluster
plt.plot(X[etiquetas==0,0],X[etiquetas==0,1],'r.', label='cluster 1')
plt.plot(X[etiquetas==1,0],X[etiquetas==1,1],'b.', label='cluster 2')
plt.plot(X[etiquetas==2,0],X[etiquetas==2,1],'g.', label='cluster 3')
plt.plot(centroides[:,0],centroides[:,1],'mo',markersize=8, label='centroides')
plt.legend(loc='best')
plt.show()
Clasificación de dígitos con k-means¶
Vamos a clasificar dÃgitos de la base de datos contenida en la librerÃa sklearn de python utilizando el algoritmo k-means.
Comenzamos cargando las librerÃas que vamos a usar:
las habituales
import numpy as np
import matplotlib.pyplot as plt
from PIL import Image
las que contienen las funciones del método k-means
from sklearn.cluster import KMeans
y para cargar las imágenes de los dÃgitos
from sklearn.datasets import load_digits
Cargamos los datos, que están incluÃdos en la librerÃa sklearn
digits = load_digits()
data = digits.data
print(data.shape)
En la matriz data, cada fila se corresponde con la imagen de un dÃgito. Los pÃxeles de la imagen rectangular de $8\times 8$ pÃxeles se han recolocado en una fila de $64$ elementos. Por lo tanto, cada fila es un objeto o dato. Las caracterÃsticas o propiedades de cada objeto son las intensidades de gris de cada pixel. Es decir, tenemos, para cada imagen, $64$ propiedades.
Para visualizar mejor los dÃgitos, vamos a invertir los colores
data = 255-data
Fijamos la semilla para sortear los centroides iniciales, para que los resultados obtenidos aquà sean repetibles
np.random.seed(1)
Como tenemos 10 dÃgitos diferentes (del 0 al 9) escogemos agrupar las imágenes en $10$ clusters
n = 10
Clasificamos los datos utilizando k-means
kmeans = KMeans(n_clusters=n,init='random')
kmeans.fit(data)
Z = kmeans.predict(data)
Dibujamos los clusters resultantes
for i in range(0,n):
fila = np.where(Z==i)[0] # filas en Z donde están las imagenes de cada cluster
num = fila.shape[0] # numero imagenes de cada cluster
r = np.floor(num/10.) # numero de filas menos 1 en figura de salida
print("cluster "+str(i))
print(str(num)+" elementos")
plt.figure(figsize=(10,10))
for k in range(0, num):
plt.subplot(r+1, 10, k+1)
imagen = data[fila[k], ]
imagen = imagen.reshape(8, 8)
plt.imshow(imagen, cmap=plt.cm.gray)
plt.axis('off')
plt.show()
Cuantificación de imágenes con k-means¶
Cuantificación es una técnica de compresión con pérdida que consiste en agrupar todo un rango de valores en uno solo. Si cuantificamos el color de una imagen, reducimos el número de colores necesarios para representarla y el tamaño del fichero de la misma disminuye. Esto es importante, por ejemplo, para representar una imagen en dispositivos que sólo dan soporte a un número limitado de colores.
Vamos a cuantificar el color de la imagen siguiente utilizando k-means.
Cargamos la imagen
I = Image.open("tienda.jpg")
La transformamos en una matriz numpy y la visualizamos
I1 = np.asarray(I,dtype=np.float32)/255
plt.figure(figsize=(12,12))
plt.imshow(I1)
plt.axis('off')
plt.show()