Cómo funciona k-modes e implementación en Python

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:

1. Generar aleatoriamente k centroides en espacios del conjunto de datos.
2. Obtener las diferencias (dissimilarities) de cada uno de los datos a todos los centroides y asignar al grupo cuya distancia sea menor.
3. Estimar la moda en cada uno de los grupos para actualizar los centroides.
4. 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:

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