La semana pasada publiqué un artículo donde explicaba el funcionamiento del algoritmo de k-means o k-medias junto a una implementación básica en Python. Este algoritmo es uno de los más utilizados para análisis de clúster. Aunque cuenta con un problema importante, al estar basado en la métrica euclídea solamente se puede utilizar cuando todas las características del conjunto de datos son numéricas, no siendo posible emplearlos cuando hay datos categóricos. Para solucionar este problema se puede recurrir al algoritmo de k-modes o k-medias, una modificación de k-means en el que se cambia la distancia euclídea por las diferencias (dissimilarities) y la media para definir los centroides por la moda. Veamos cómo se puede modificar el código visto la semana pasada para implementar el algoritmo de k-modes en Python.
El algoritmo de k-modes
Comprendiendo el algoritmo de k-means es fácil entender k-modes. Debido a que este último es una modificación del primero cambiando el uso de la media por la moda para obtener la posición de los centroides en cada iteración y empleando el número de diferencias (dissimilarities) entre dos registros como medida de la distancia en lugar de la métrica euclídea.
Al igual que en el caso de k-means, los resultados que se obtienen con k-modes son fácilmente interpretables. El centroide es el valor típico, en este caso moda, de cada uno de los clusteres en los que se divide el conjunto de datos.
Así, el algoritmo de k-modes se puede resumir en los siguientes pasos:
- Generar aleatoriamente k centroides en espacios del conjunto de datos.
- Obtener las diferencias (dissimilarities) de cada uno de los datos a todos los centroides y asignar al grupo cuya distancia sea menor.
- Estimar la moda en cada uno de los grupos para actualizar los centroides.
- Comprobar si los centroides se han desplazado por debajo de un valor límite, si es así esta es la solución, en caso contrario volver al punto 2.
Como se puede apreciar los pasos en este caso son prácticamente idénticos a los de k-means.
Entendiendo la medida de las diferencias (dissimilarities)
Al trabajar con datos categóricos no existe una medida de distancia. Por ejemplo, al trabajar con colores, no se puede definir una distancia entre rojo y azul o entre rojo y verde, en ambos casos los valores son diferentes. Así una manera de medir la distancia entre dos vectores de variables categóricas es la cantidad de valores que son diferentes, de tal manera que la distancia entre rojo y azul es uno, entre rojo y verde también es uno, siendo solemnemente cero entre rojo y rojo.
Esto se puede ver por ejemplo en la siguiente tabla de camisas:
Cuello | Tejido | Color |
---|---|---|
Italiano | Algodón | Blanca |
Inglés | Algodón | Azul |
Inglés | Lino | Azul |
Así la separación que existe usando las diferencias entre la primera fila y la segunda se obtiene un valor de 2, ya que ni el cuello ni el color coinciden. Mientras que la distancia entre la primera y la tercera es de 3, ninguno de los valores coincide. Finalmente, la distancia entre la primera y la tercera es 1, solamente cambia el color.
Implementación de Python de k-modes
Una implmentación de k-modes se puede llevar a cabo con el siguiente código.
import numpy as np def next_step(centroids, previous, iteration, max_iter=10, stop_limit=0): """Comprueba si se debe calcular la siguiente iteración. Parameters ---------- centroids : ndarray La posición actual de los centroides. previous : ndarray La posición previa de los centroides. iterations : integer La iteración actual. max_iter : integer El número máximo de iteraciones permitidas. stop_limit : real La diferencia entre a partir de la cual se considera que el algoritmo ha convergido. Returns ------- mode : boolean Verdadero si el algoritmo debe continuar, falso en el resto de los casos. """ if previous is None: return True elif iteration > max_iter: return False elif np.sum(centroids == previous) <= stop_limit: return False else: return True def mode(data): """Estima la moda de cada uno de las columnas de la matriz Parameters ---------- data : ndarray El conjunto de datos sobre el que se desea obtener la moda Returns ------- mode : ndarray Un vector con la moda de cada una de las columnas """ result = np.zeros(data.shape[1]) for col in range(data.shape[1]): vals, counts = np.unique(data[:, col], return_counts=True) result[col] = vals[counts == np.max(counts)][0] return result def dissimilarities(data, centroids): """Mide la disimilitudes (dissimilarities) Estima disimilitudes (dissimilarities) que existe entre las filas de una matriz y cada uno de los centroides. Parameters ---------- data : ndarray La matriz con los datos sobre los que se desea medir las disimilitudes centroids : ndarray Los centroides de referencia sobre los que se desea medir las disimilitudes Returns ------- dissimilarities : ndarray Matriz con las disimilitudes """ n_clusters = centroids.shape[0] result = np.zeros([data.shape[0], n_clusters]) for num in range(n_clusters): result[:, num] = data.shape[1] - np.sum(np.equal(data, centroids[num, :]), axis=1) return result def k_modes(data, n_clusters, max_iter=10, stop_limit=0, random_state=None): """Implementación básica del algoritmo de Kmodes. Nota: esta función es solamente una implementación básica con fines pedagógicos, no usar en producción. Parameters ---------- data : ndarray El conjunto de datos sobre el que se desea aplicar el algoritmo de Kmodes. n_clusters : integer El número de clústeres. max_iter : integer El número máximo de iteraciones permitidas. stop_limit : real La diferencia entre a partir de la cual se considera que el algoritmo ha convergido. random_state : number or None La semilla con la que se generan los números aleatorios. Returns ------- centroids : ndarray Los centroides obtenidos. """ if random_state is not None: np.random.seed(random_state) centroids = np.random.choice(data.shape[0], n_clusters, replace=False) centroids = data[centroids, :] iteration = 0 previous = None while next_step(centroids, previous, iteration, max_iter, stop_limit): iteration += 1 previous = np.empty_like(centroids) distance = dissimilarities(data, centroids) clusters = np.argmin(distance, axis=1) for num in range(n_clusters): if np.any(clusters == num): centroids[num, :] = mode(data[clusters == num, :]) return centroids
La primera función que se ha escrito es next_step()
mediante la cual se decide si se debe continuar o no. Para lo que la función devuelve verdejo siempre que no se alcance el máximo de iteraciones o el número de diferencias entre los centroides sea inferior o igual a un límite.
A continuación se encuentra la función mode()
con la que se obtiene la moda. Función que es necesaria escribir dado que no existe una implementación del estadístico en NumPy.
La función dissimilarities()
mide la cantidad de registros que son diferentes entre dos vectores, implementado de este modo la medida de las diferencias.
Finalmente en la función k_modes()
se ha implementado el algoritmo en sí. En el que, una vez fijada la semilla, se selecciona aleatoriamente los registros que serán los centroides inciales. Posteriormente, al igual que el algoritmo de k-means se refina iterativamente los censores hasta que los valores convergen a la solución.
Validación con la libreria KModes
Existe una implementación dentro del paquete kmodes
. Un paquete que se puede instalar lanzando el comando pip install kmodes
en la terminal. Una vez instado, la creación de un modelo es exactamente igual a cualquier clasificado de Scikit-learn, se crea la clase y se ajusta con el método fit()
.
Así se puede comprobar que la implantación realizada en este caso obtiene el mismo resultado que la de este paquete.
from kmodes.kmodes import KModes data = np.array([[0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [2, 2, 1, 0, 3], [1, 0, 2, 1, 1], [0, 3, 2, 2, 4], [0, 1, 1, 2, 4], [1, 1, 2, 3, 0], [0, 4, 3, 2, 4], [1, 3, 2, 0, 0], [2, 1, 4, 0, 4]]) centroids = k_modes(data, 2, random_state=0) kmodes = KModes(n_clusters=2).fit(data) kmodes.cluster_centroids_ print('Implementación') print(centroids) print('Scikit-learn') print(kmodes.cluster_centroids_)
Implementación [[0 1 1 2 4] [1 0 2 0 0]] Scikit-learn [[0 1 1 2 4] [1 0 2 0 0]]
Conclusiones
Hoy se han visto las bases del algoritmo de k-modes y como se puede realizar una implementación básica en Python. Obteniendo resultados similares a la clase del paquete kmodes
en conjunto de datos básico.
Al igual que comente en el caso de k-menas, no recomiendo el uso de esta implementación ya que es básica. Si se necesita crear un modelo con k-modes en Python recomiendo usar las clases del paquete kmodes
.
Imagen de WikiImages en Pixabay
Deja una respuesta