El índice de Davies-Bouldinen para estimar los clústeres en k-means e implementación en Python

Uno de los mayores problemas a la hora de trabajar con el algoritmo de k-means es la necesidad de conocer el número de clústeres en los que se debe dividir el conjunto de datos. Para lo que existen diferentes métodos como el del codo, la Silhouette, Gap Statistics o Calinski-Harabasz. En esta ocasión se va a ver otro método bastante popular, el braseado en el índice de Davies-Bouldinen.

El índice de Davies-Bouldinen

Introducido por David L. Davies y Donald W. Bouldin en 1979, el índice de Davies-Bouldinen (DBI) es una métrica para evaluar la calidad de los clústeres producidos por un algoritmo de clustering. La idea detrás de este índice es que una agrupación de calidad debería producir clústeres separados y compactos.

El índice de Davies-Bouldin se basa en relacionar la dispersión dentro de los clústeres (intra-clúster) y la separación entre clústeres (inter-clúster). Por un lado, la dispersión intra-clúster mide la separación de los puntos dentro de cada clúster. Una dispersión intra-clúster baja indica que los puntos dentro de un grupo están muy cercanos entre sí, algo que es deseable en un buen clustering. Por otro lado, la dispersión inter-clúster mide la separación entre los grupos. Una dispersión inter-clúster alta indica que los grupos están muy alejados entre sí, lo que también es deseable en un buen clustering. El índice de Davies-Bouldin se construye como el cociente de ambos valores. Por lo que cuando los clústeres están separados y son compactos el valor de este índice se minimiza.

Para calcular el índice de Davies-Bouldin se pueden seguir los siguientes pasos:

1. Ejecutar el algoritmo de clustering sobre los datos de interés para obtener los clústeres.
2. Identificar el centroide de cada grupo, es decir, el punto medio de todos los puntos que pertenecen a ese grupo.
3. Calcular la dispersión intra-clúster de cada grupo. Para esto, se puede utilizar una medida de distancia, como la distancia euclidiana, para calcular la distancia entre cada punto del clúster y su centroide. Luego, se puede promediar todas estas distancias para obtener la dispersión intra-clúster.
4. Computar la dispersión inter-clúster entre cada par de clúster. Para esto, se puede utilizar la misma medida de distancia para calcular la distancia entre los centroides de cada par de clúster.
5. Estimar el cociente entre la dispersión intra-clúster y la dispersión inter-clúster para cada pareja de clústeres. Para cada clúster, seleccionar el valor máximo de la razón obtenida al compararlo con el resto de los clústeres.
6. Obtener la media de los valores máximos obtenidos en el paso anterior para todos los clústeres.

Implementación en Python del índice de Davies-Bouldin

Los pasos que se han explicado en la sección anterior se pueden usar para implementar una función en Python que implemente el índice de Davies-Bouldin.

import numpy as np
from sklearn.metrics import pairwise_distances

def davies_bouldin_index(data, labels, centroids):
    """
    Calcula el índice de Davies-Bouldin para evaluar la calidad de los clusters.

    Parámetros
    ----------
    data : matriz o matriz dispersa, forma (n_samples, n_features)
        Matriz de características de los datos de entrada.

    labels : array-like, shape (n_samples,)
        Etiquetas de cluster asignadas a cada punto de datos.

    centroids : array-like, shape (n_clusters, n_features)
        Coordenadas de los centroides de los clusters.

    Retorna
    -------
    dbi : float
        Índice de Davies-Bouldin.
    """

    k = len(centroids)

    # Calcular las distancias entre los centroides
    centroid_distances = pairwise_distances(centroids)

    # Calcular las distancias medias intra-cluster
    intra_cluster_distances = np.zeros(k)
    for i in range(k):
        cluster_points = data[labels == i]
        if len(cluster_points) > 1:
            cluster_distances = pairwise_distances(cluster_points)
            mean_cluster_distance = np.mean(cluster_distances)
            intra_cluster_distances[i] = mean_cluster_distance

    # Calcular el índice de Davies-Bouldin
    dbi = 0
    for i in range(k):
        max_similarity = -np.inf
        for j in range(k):
            if i != j:
                similarity = (intra_cluster_distances[i] + intra_cluster_distances[j]) / centroid_distances[i, j]
                if similarity > max_similarity:
                    max_similarity = similarity
        dbi += max_similarity
    dbi /= k

    return dbi

Identificar el número de clústeres con el índice de Davies-Bouldinen

Ahora que se dispone de una función para obtener el índice de Davies-Bouldinen se puede usar esta para estimar el número óptimo de clústeres en el que se debe dividir un conjunto de datos con k-means. Proceso que es similar al usado con la Silhouette o Calinski-Harabasz. Simplemente se debe ejecutar el algoritmo de k-means para diferentes números de clústeres y seleccionar el que ofrece el mejor resultado. En este caso el menor valor del índice de Davies-Bouldinen. Una posible implementación es la que se muestra a continuación

from sklearn.cluster import KMeans

def find_optimal_clusters_dbi(data, max_clusters=10):
    """
    Encuentra el número óptimo de clusters utilizando el índice de Davies-Bouldin.

    Parámetros
    ----------
    data : matriz o matriz dispersa, forma (n_samples, n_features)
        Matriz de características de los datos de entrada.

    max_clusters : int, optional (default=10)
        Número máximo de clusters a probar.

    Retorna
    -------
    optimal_clusters : int
        Número óptimo de clusters según el índice de Davies-Bouldin
        
    """

    dbi_values = []
    for k in range(2, max_clusters+1):
        kmeans = KMeans(n_clusters=k, random_state=42)
        labels = kmeans.fit_predict(data)
        centroids = kmeans.cluster_centers_

        dbi = davies_bouldin_index(data, labels, centroids)
        dbi_values.append(dbi)

    optimal_clusters = np.argmin(dbi_values) + 2

    return optimal_clusters

Evaluación de los resultados

Para comprobar que el resultado obtenido con este método es correcto se puede usar un conjunto de datos aleatorios creados con la función make_blobs() de Scikit-learn. De forma análoga a como se ha hecho para otros algoritmos como Gap stadistics, Eblow, Silhouette o Calinski-Harabasz en ocasiones anteriores. Creando para ello un conjunto con un número conocido de clústeres y se comprueba el resultado que devuelve la función, como se hace en el siguiente código.

from sklearn.datasets import make_blobs

# Genera un conjunto de datos de ejemplo con 4 clusters
data, _ = make_blobs(n_samples=500, centers=4, n_features=2, random_state=42)

find_optimal_clusters_dbi(data)

4

Obteniendo el resultado esperado

Conclusiones

El índice de Davies-Bouldinen es una métrica que permite evaluar la calidad de los clústeres obtenidos para un conjunto de datos. Permitiendo saber cuándo la agrupación es mejor o peor. Esto se puede utilizar para estimar el número óptimo de clústeres en un conjunto de datos cuando se trabaja con k-means.

Hay que tener en cuenta que el índice de Davies-Bouldinen es una alternativa a métodos como el del codo, la Silhouette, Gap Statistics o Calinski-Harabasz entre otros. Cada uno con su propio criterio para seleccionar el número óptimo de clústeres. Por lo que es recomendable usar varios métodos y comparar los resultados antes de seleccionar el número de clústeres.

Imagen de Bruno en Pixabay