Autor: Luis Fernando Apáez Álvarez

    -Curso PyM-

    Clase 2: Algoritmos de agrupación II

    Fecha: 24 de mayo del 2023

---

Clustering basado en densidad

ChatGPT

El clustering basado en densidad es un enfoque dentro del aprendizaje no supervisado que se utiliza para agrupar conjuntos de datos en función de la densidad de los puntos. Este tipo de algoritmos puede encontrar agrupaciones de formas y tamaños arbitrarios, y no requiere especificar previamente el número de clústeres (o de vecinos).

Uno de los algoritmos más populares de clustering basado en densidad es el DBSCAN (Density-Based Spatial Clustering of Applications with Noise). DBSCAN es una técnica que puede identificar grupos de puntos densos en un espacio de datos y asignar puntos de baja densidad como ruido o outliers.

El algoritmo DBSCAN se basa en dos conceptos clave: la densidad y la accesibilidad. La densidad se refiere al número de puntos dentro de una vecindad específica alrededor de un punto dado. La accesibilidad se refiere a la capacidad de alcanzar un punto desde otro a través de una serie de conexiones directas.

El proceso de clustering con el algoritmo DBSCAN se puede describir de la siguiente manera:

1. Seleccionar un punto aleatorio que no haya sido visitado.
2. Determinar si el punto tiene suficientes puntos vecinos dentro de un radio especificado (umbral de densidad) para formar un clúster.
3. Si el punto tiene suficientes vecinos, se forma un nuevo clúster y se expande para incluir todos los puntos alcanzables desde ese punto. Esto se hace mediante la exploración de los vecinos y su conectividad con otros vecinos.
4. Repetir los pasos anteriores hasta que todos los puntos hayan sido visitados.

Al final del proceso, los puntos se clasifican en tres categorías: puntos núcleo, puntos frontera y puntos de ruido. Los puntos núcleo son aquellos que tienen suficientes vecinos dentro del umbral de densidad y forman los clústeres principales. Los puntos frontera tienen menos vecinos que los puntos núcleo pero están dentro del alcance de un clúster. Los puntos de ruido no están dentro del alcance de ningún clúster y se consideran como valores atípicos o outliers.

El algoritmo DBSCAN tiene la ventaja de ser robusto frente a la forma y tamaño de los clústeres, y puede manejar datos ruidosos. Sin embargo, es sensible a la elección de los parámetros, como el umbral de densidad y el radio de búsqueda, los cuales deben ser ajustados correctamente para obtener resultados óptimos. Además, puede tener dificultades con conjuntos de datos de alta dimensionalidad debido al problema conocido como "maldición de la dimensionalidad".

---

Por ejemplo, consideremos el siguiente gráfico y enfoquemos la atención en el punto A:

Tomamos el punto A y a éste lo consideramos como un núclee, luego dada una cierta distancia dibujamos un círculo con centro en A. Todos los puntos que estén dentro de dicho círculo comenzarán a formar un clúster. Asimismo, dichos puntos serán también núcleos y dibujamos de nuevo círculos con la misma distancia para "atrapar" nuevos puntos. Dado que el punto B no fue directamente alcanzado por A, decimos que B es un punto densamente alcanzable por A. Dado que el punto C no fue alzanzado, dicho punto no pertenecerá al clúster marcado por A; decimos que C es un punto ruidoso (no es un núcleo ni densamente alcanzable por el clúster marcado por A).

Veamos un ejemplo:

# Importaciones necesarias
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt
import numpy as np
plt.style.use('ggplot')

# Datos
X = np.array([[1, 2], [2, 2], [2, 3],
              [8, 7], [8, 8], [25, 80]])

for i in range(len(X)):
    plt.plot(X[i][0], X[i][1], marker='.', color='black')

plt.show()

Procedemos a aplicar el algoritmo DBSCAN:

# Importacion necesaria
from sklearn.cluster import DBSCAN

# eps: maxima distancia entre dos muestras (radio del ciruclo)
# min_samples: El numero de muestras en una vecindad para que un punto se considere un nucleo             
# Instanciamos y configuramos
db = DBSCAN(eps=3, min_samples=2)

# Ajustamos
db.fit(X)

DBSCAN(eps=3, min_samples=2)

In a Jupyter environment, please rerun this cell to show the HTML representation or trust the notebook.
On GitHub, the HTML representation is unable to render, please try loading this page with nbviewer.org.

# Veamos las etiquetas asociadas
db.labels_

array([ 0,  0,  0,  1,  1, -1], dtype=int64)

Tenemos entonces tres clústers: 0, 1 y -1. Asociados como

# Haremos que los valores del array X sean listas
X_list = [list(i) for i in X]

# Definimos una lista con las etiquetas de la anterior celda de codigo
etiquetas = list(db.labels_)

# Veamos X_list
X_list

[[1, 2], [2, 2], [2, 3], [8, 7], [8, 8], [25, 80]]

# Procedemos a realizar la asociacion
for i in range(len(X_list)):
    if etiquetas[i] == 0:
        plt.plot(X_list[i][0], X_list[i][1], label='Clúster 1', marker='o', color='red')
    elif etiquetas[i] == 1:
        plt.plot(X_list[i][0], X_list[i][1], label='Clúster 2', marker='o', color='green')
    else:
        plt.plot(X_list[i][0], X_list[i][1], label='Clúster 3', marker='o', color='blue')
plt.legend()
plt.show()

Para elegir los mejores valores de eps y min_samples hacemos lo siguiente:

• min_samples Si el conjunto de datos es de dos dimensiones, como en el ejemplo anterior, usamos min_samples=4. Si el conjunto de datos es de más de dos dimensiones ($n>2$), usamos min_samples=2 * n.
• eps: Para calcular la distancia óptima para los radios utilizaremos el algoritmo KNN para calcular la distancia de cada punto a su vecino más cercano, con lo cual conseguimos obtener todas las distancias entre los puntos por clúster

from sklearn.neighbors import NearestNeighbors
# Configuramos dos vecinos debido a que solo queremos calcular las distancias
# entre dos puntos
knn = NearestNeighbors(n_neighbors=2)
nbrs = knn.fit(X) 

# Obtenemos las distancias 
distances, _ = knn.kneighbors(X)
print(distances)

[[ 0.          1.        ]
 [ 0.          1.        ]
 [ 0.          1.        ]
 [ 0.          1.        ]
 [ 0.          1.        ]
 [ 0.         73.97972695]]

# Ordenamos las distancias de menor a mayor
distances = np.sort(distances, axis = 0) 
plt.plot(distances) 
plt.show()

Nos quedaremos con el valor de la distancia antes de que aumente la "curva", es decir, el valor de eps será de 1.

Por ejemplo, en este otro gráfico:

Nos quedaríamos con el valor aproximado de eps=8.

En este caso, el fin del algoritmo es realizar la agrupación de los datos que ya tenemos, es decir, no será de nuestro interés pasarle datos nuevos y posteriormente realizar la predicción como en KNN.

Volvemos a configurar un modelo

---

Ejercicio

Considera el siguiente conjunto de datos sobre la calidad de ciertos vinos:

import pandas as pd
df = pd.read_csv('https://luisapaez.github.io/Teoria_Galois/wine.csv')
df

	producer	alcohol	malic_acid	ash	ash_alcalinity	magnesium	phenols	flavanoids	nonflavanoid_fenols	proanthocyanins	color_intensity	hue	od280_od350	proline
0	1	14.23	1.71	2.43	15.6	127	2.80	3.06	0.28	2.29	5.64	1.04	3.92	1065
1	1	13.20	1.78	2.14	11.2	100	2.65	2.76	0.26	1.28	4.38	1.05	3.40	1050
2	1	13.16	2.36	2.67	18.6	101	2.80	3.24	0.30	2.81	5.68	1.03	3.17	1185
3	1	14.37	1.95	2.50	16.8	113	3.85	3.49	0.24	2.18	7.80	0.86	3.45	1480
4	1	13.24	2.59	2.87	21.0	118	2.80	2.69	0.39	1.82	4.32	1.04	2.93	735
...	...	...	...	...	...	...	...	...	...	...	...	...	...	...
173	3	13.71	5.65	2.45	20.5	95	1.68	0.61	0.52	1.06	7.70	0.64	1.74	740
174	3	13.40	3.91	2.48	23.0	102	1.80	0.75	0.43	1.41	7.30	0.70	1.56	750
175	3	13.27	4.28	2.26	20.0	120	1.59	0.69	0.43	1.35	10.20	0.59	1.56	835
176	3	13.17	2.59	2.37	20.0	120	1.65	0.68	0.53	1.46	9.30	0.60	1.62	840
177	3	14.13	4.10	2.74	24.5	96	2.05	0.76	0.56	1.35	9.20	0.61	1.60	560

178 rows × 14 columns

Definimos las variables como sigue:

# Primer columna
y = df.iloc[:,0]

# EL resto de columnas
X = df.iloc[:, 1:]

Implementa un algoritmo DBSCAN y configura el valor adecuado para eps y min_samples.