Tabla de contenido
1. Introducción
2. ¿Qué hace el algoritmo K-Means?
3. Implementación en Python
4. Evaluación e Interpretación
5. Conclusiones y próximos pasos
La mayoría de los algoritmos de aprendizaje automático ampliamente utilizados, como la regresión lineal, la regresión logística, los árboles de decisión y otros, son útiles para realizar predicciones a partir de datos etiquetados, es decir, cada entrada comprende valores de características con un valor de etiqueta asociado. eso es lo que se llama Aprendizaje supervisado.
Sin embargo, a menudo tenemos que lidiar con grandes conjuntos de datos sin ninguna etiqueta asociada. Imagine una empresa que necesita comprender los diferentes grupos de clientes en función del comportamiento de compra, la demografía, la dirección y otra información, para poder ofrecer mejores servicios, productos y promociones.
Este tipo de problemas se pueden abordar con el uso de Aprendizaje sin supervisión técnicas. El algoritmo K-Means es un algoritmo de aprendizaje no supervisado ampliamente utilizado en Machine Learning. Su enfoque simple y elegante hace posible separar un conjunto de datos en un número deseado de K grupos distintos, lo que permite aprender patrones a partir de datos sin etiquetar.
Como se dijo anteriormente, el algoritmo K-Means busca dividir los puntos de datos en un número determinado de grupos. Los puntos dentro de cada grupo son similares, mientras que los puntos en diferentes grupos tienen diferencias considerables.
Dicho esto, surge una pregunta: ¿cómo definimos similitud o diferencia? En la agrupación de K-Means, la distancia euclidiana es la métrica más común para medir la similitud.
En la siguiente figura podemos ver claramente 3 grupos diferentes. De esta forma, podríamos determinar los centros de cada grupo y cada punto estaría asociado al centro más cercano.
Al hacer eso, matemáticamente hablando, la idea es minimizar la varianza dentro del grupola medida de similitud entre cada punto y su centro más cercano.
Realizar la tarea del ejemplo anterior fue sencillo porque los datos eran bidimensionales y los grupos eran claramente distintos. Sin embargo, a medida que aumenta el número de dimensiones y se consideran diferentes valores de K, necesitamos un algoritmo para manejar la complejidad.
Paso 1: Elige los centros iniciales (al azar)
Necesitamos sembrar el algoritmo con vectores centrales iniciales que puedan elegirse aleatoriamente a partir de los datos o generar vectores aleatorios con las mismas dimensiones que los datos originales. Vea los diamantes blancos en la imagen de abajo.
Paso 2: Encuentra las distancias de cada punto a los centros.
Ahora, calcularemos la distancia de cada punto de datos a los K centros. Luego asociamos cada punto con el centro más cercano a ese punto.
Dado un conjunto de datos con norte entradas y METRO características, las distancias a los centros C puede venir dado por la siguiente ecuación:
dónde:
k varía de 1 a k;
D es la distancia de un punto n al k centro;
X es el vector puntual;
C es el vector central.
Por lo tanto, para cada punto de datos norte tendremos K distancias, luego tenemos que etiquetar el vector al centro con la distancia más pequeña:
Dónde D es un vector con k distancias.
Paso 3: Encuentra el k centroides e iterar
Para cada uno de los k grupos, vuelva a calcular el centroide. El nuevo centroide es la media de todos los puntos de datos asignados a ese grupo. Luego actualice las posiciones de los centroides a las recién calculadas.
Compruebe si los centroides han cambiado significativamente con respecto a la iteración anterior. Esto se puede hacer comparando las posiciones de los centroides en la iteración actual con las de la última iteración.
Si los centroides han cambiado significativamente, regrese al Paso 2. De lo contrario, el algoritmo ha convergido y el proceso se detiene. Vea la imagen a continuación.
Ahora que conocemos los conceptos fundamentales del algoritmo K-Means, es hora de implementar una clase de Python. Los paquetes utilizados fueron Numpy para cálculos matemáticos, Matplotlib para visualización y el paquete Make_blobs de Sklearn para datos simulados.
# import required packages
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
La clase tendrá los siguientes métodos:
Un método constructor para inicializar los parámetros básicos del algoritmo: el valor k de clusters, el número máximo de iteraciones max_iter, y la tolerancia tol Es valor interrumpir la optimización cuando no hay una mejora significativa.
Estos métodos tienen como objetivo ayudar en el proceso de optimización durante el entrenamiento, como calcular la distancia euclidiana, elegir aleatoriamente los centroides iniciales, asignar el centroide más cercano a cada punto, actualizar los valores de los centroides y verificar si la optimización convergió.
Como se mencionó anteriormente, el algoritmo K-Means es una técnica de aprendizaje no supervisada, lo que significa que no requiere datos etiquetados durante el proceso de entrenamiento. De esa manera, es necesario un método único para ajustar los datos y predecir a qué grupo pertenece cada punto de datos.
Un método para evaluar la calidad de la optimización calculando la error cuadrático total de la optimización. Esto se explorará en la siguiente sección.
Aquí va el código completo:
class Kmeans:# construct method for hyperparameter initialization
def __init__(self, k=3, max_iter=100, tol=1e-06):
self.k = k
self.max_iter = max_iter
self.tol = tol
# randomly picks the initial centroids from the input data
def pick_centers(self, X):
centers_idxs = np.random.choice(self.n_samples, self.k)
return X[centers_idxs]
# finds the closest centroid for each data point
def get_closest_centroid(self, x, centroids):
distances = [euclidean_distance(x, centroid) for centroid in centroids]
return np.argmin(distances)
# creates a list with lists containing the idxs of each cluster
def create_clusters(self, centroids, X):
clusters = [[] for _ in range(self.k)]
labels = np.empty(self.n_samples)
for i, x in enumerate(X):
centroid_idx = self.get_closest_centroid(x, centroids)
clusters[centroid_idx].append(i)
labels[i] = centroid_idx
return clusters, labels
# calculates the centroids for each cluster using the mean value
def compute_centroids(self, clusters, X):
centroids = np.empty((self.k, self.n_features))
for i, cluster in enumerate(clusters):
centroids[i] = np.mean(X[cluster], axis=0)
return centroids
# helper function to verify if the centroids changed significantly
def is_converged(self, old_centroids, new_centroids):
distances = [euclidean_distance(old_centroids[i], new_centroids[i]) for i in range(self.k)]
return (sum(distances) < self.tol)
# method to train the data, find the optimized centroids and label each data point according to its cluster
def fit_predict(self, X):
self.n_samples, self.n_features = X.shape
self.centroids = self.pick_centers(X)
for i in range(self.max_iter):
self.clusters, self.labels = self.create_clusters(self.centroids, X)
new_centroids = self.compute_centroids(self.clusters, X)
if self.is_converged(self.centroids, new_centroids):
break
self.centroids = new_centroids
# method for evaluating the intracluster variance of the optimization
def clustering_errors(self, X):
cluster_values = [X[cluster] for cluster in self.clusters]
squared_distances = []
# calculation of total squared Euclidean distance
for i, cluster_array in enumerate(cluster_values):
squared_distances.append(np.sum((cluster_array - self.centroids[i])**2))
total_error = np.sum(squared_distances)
return total_error
Ahora usaremos la clase K-Means para realizar la agrupación de datos simulados. Para ello se utilizará el hacer_blobs paquete de la biblioteca Sklearn. Los datos constan de 500 puntos bidimensionales con 4 centros fijos.
# create simulated data for examples
X, _ = make_blobs(n_samples=500, n_features=2, centers=4,
shuffle=False, random_state=0)
Después de realizar el entrenamiento utilizando cuatro clusters, logramos el siguiente resultado.
model = Kmeans(k=4)
model.fit_predict(X)
labels = model.labels
centroids =model.centroids
plot_clusters(X, labels, centroids)
En ese caso, el algoritmo fue capaz de calcular los clusters exitosamente con 18 iteraciones. Sin embargo, debemos tener en cuenta que ya conocemos el número óptimo de clusters a partir de los datos simulados. En aplicaciones del mundo real, a menudo no conocemos ese valor.
Como se dijo anteriormente, el algoritmo K-Means tiene como objetivo hacer que varianza dentro del grupo lo más pequeño posible. La métrica utilizada para calcular esa varianza es la distancia euclidiana total al cuadrado dada por:
dónde:
p es el número de puntos de datos en un grupo;
c_i es el vector centroide de un grupo;
K es el número de grupos.
En palabras, la fórmula anterior suma las distancias de los puntos de datos al centroide más cercano. El error disminuye a medida que aumenta el número K.
En el caso extremo de K =N, tiene un grupo para cada punto de datos y este error será cero.
Willmott, Paul (2019).
Si trazamos el error en función del número de conglomerados y observamos dónde se “dobla” el gráfico, podremos encontrar el número óptimo de conglomerados.
Como podemos ver, la gráfica tiene forma de “codo” y se dobla en K = 4, lo que significa que para valores mayores de K, la disminución en el error total será menos significativa.
En este artículo, cubrimos los conceptos fundamentales detrás del algoritmo K-Means, sus usos y aplicaciones. Además, utilizando estos conceptos, pudimos implementar una clase de Python desde cero que realizaba la agrupación de datos simulados y cómo encontrar el valor óptimo para K usando un diagrama de pedregal.
Sin embargo, dado que estamos ante una técnica no supervisada, hay un paso adicional. El algoritmo puede asignar con éxito una etiqueta a los grupos, pero el significado de cada etiqueta es una tarea que el científico de datos o el ingeniero de aprendizaje automático tendrá que realizar analizando los datos de cada grupo.
Además, dejaré algunos puntos para una mayor exploración:
- Nuestros datos simulados utilizaron puntos bidimensionales. Intente utilizar el algoritmo para otros conjuntos de datos y encuentre los valores óptimos para K.
- Existen otros algoritmos de aprendizaje no supervisado ampliamente utilizados como Agrupación jerárquica.
- Dependiendo del dominio del problema, puede ser necesario utilizar otras métricas de error, como la distancia de Manhattan y la similitud del coseno. Intenta investigarlos.
Código completo disponible aquí: