Yosombrero Escaneo de base de datos [1]¿Cómo construirlo en Python? Hay muchos artículos que tratan este tema, pero creo que el algoritmo en sí es tan simple e intuitivo que es posible explicar su idea en tan solo unos pocos pasos. 5 minutosasí que vamos a intentar hacerlo.
DBSCAN = Agrupamiento espacial basado en densidad de aplicaciones con ruido
¿Qué significa?
- El algoritmo busca clústeres dentro de los datos basándose en la distancia espacial entre objetos.
- El algoritmo puede Identificar valores atípicos (ruido).
¿Por qué necesitas DBSCAN?
- Extraer una nueva característica. Si el conjunto de datos con el que estás trabajando es grande, puede ser útil encontrar grupos obvios dentro de los datos y trabajar con cada grupo por separado (entrenar diferentes modelos para diferentes grupos).
- Comprimir los datos. A menudo tenemos que trabajar con millones de filas, lo que es costoso en términos computacionales y requiere mucho tiempo. Agrupar los datos y luego conservar solo el X % de cada grupo Podría salvar tu malvada alma científica de datosPor lo tanto, usted mantener el equilibrio dentro del conjunto de datos, pero reducir su tamaño.
- Detección de novedad. Se ha mencionado anteriormente que DBSCAN detecta ruido, pero el ruido podría ser una característica previamente desconocida del conjunto de datos, que puede preservar y usar en el modelado.
Entonces usted puede decir: pero existe el súper confiable y efectivo k-medias algoritmo.
Sí, pero lo mejor de DBSCAN es que supera los inconvenientes de k-means y no es necesario especificar el número de clústeres. ¡DBSCAN detecta clústeres para usted!
DBSCAN tiene dos componentes definidos por un usuario: proximidad o radio (𝜀), y el número de vecinos (norte).
Para un conjunto de datos que consta de algunos objetos, el algoritmo se basa en las siguientes ideas:
- Objetos centralesUn objeto se denomina objeto central si se encuentra dentro de la distancia 𝜀 Tiene al menos norte Otros objetos.
- Un objeto no central que se encuentra dentro 𝜀-La proximidad de un punto central se denomina objeto de borde.
- Un objeto central forma un grupo con todos los objetos centrales y de borde dentro 𝜀-vecindad.
- Si un objeto no es ni núcleo ni borde, se llama ruido (valor atípico)No pertenece a ningún cluster.
Para implementar DBSCAN es necesario crear una función de distancia. En este artículo utilizaremos la distancia euclidiana:
El pseudocódigo de nuestro algoritmo se ve así:
Como siempre, el código de este artículo lo podéis encontrar en mi GitHub.
Comencemos con la función distancia:
def distances(object, data):
euclidean = []
for row in data: #iterating through all the objects in the dataset
d = 0
for i in range(data.shape[1]): #calculating sum of squared residuals for all the coords
d+=(row[i]-object[i])**2
euclidean.append(d**0.5) #taking a sqaure root
return np.array(euclidean)
Ahora construyamos el cuerpo del algoritmo:
def DBSCAN(data, epsilon=0.5, N=3):
visited, noise = [], [] #lists to collect visited points and outliers
clusters = [] #list to collect clusters
for i in range(data.shape[0]): #iterating through all the points
if i not in visited: #getting in if the point's not visited
visited.append(i)
d = distances(data[i], data) #getting distances to all the other points
neighbors = list(np.where((d<=epsilon)&(d!=0))[0]) #getting the list of neighbors in the epsilon vicinity and removing distance = 0 (it's the point itself)
if len(neighbors)<N: #if the number of object is less than N, it's an outlier
noise.append(i)
else:
cluster = [i] #otherwise it forms a new cluster
for neighbor in neighbors: #iterating trough all the neighbors of the point i
if neighbor not in visited: #if neighbor isn't visited
visited.append(neighbor)
d = distances(data[neighbor], data) #get the distances to other objects from the neighbor
neighbors_idx = list(np.where((d<=epsilon)&(d!=0))[0]) #getting neighbors of the neighbor
if len(neighbors_idx)>=N: #if the neighbor has N or more neighbors, than it's a core point
neighbors += neighbors_idx #add neighbors of the neighbor to the neighbors of the ith object
if not any(neighbor in cluster for cluster in clusters):
cluster.append(neighbor) #if neighbor is not in clusters, add it there
clusters.append(cluster) #put the cluster into clusters listreturn clusters, noise
¡Hecho!
Verifiquemos la corrección de nuestra implementación y comparémosla con aprender.
Generemos algunos datos sintéticos:
X1 = [[x,y] for x, y in zip(np.random.normal(6,1, 2000), np.random.normal(0,0.5, 2000))]
X2 = [[x,y] for x, y in zip(np.random.normal(10,2, 2000), np.random.normal(6,1, 2000))]
X3 = [[x,y] for x, y in zip(np.random.normal(-2,1, 2000), np.random.normal(4,2.5, 2000))]fig, ax = plt.subplots()
ax.scatter([x[0] for x in X1], [y[1] for y in X1], s=40, c='#00b8ff', edgecolors='#133e7c', linewidth=0.5, alpha=0.8)
ax.scatter([x[0] for x in X2], [y[1] for y in X2], s=40, c='#00ff9f', edgecolors='#0abdc6', linewidth=0.5, alpha=0.8)
ax.scatter([x[0] for x in X3], [y[1] for y in X3], s=40, c='#d600ff', edgecolors='#ea00d9', linewidth=0.5, alpha=0.8)
ax.spines[['right', 'top', 'bottom', 'left']].set_visible(False)
ax.set_xticks([])
ax.set_yticks([])
ax.set_facecolor('black')
ax.patch.set_alpha(0.7)
Apliquemos nuestra implementación y visualicemos los resultados:
Para la implementación de sklearn obtuvimos los mismos clústeres:
Eso es todo, son idénticos. ¡5 minutos y listo! Cuando intentes realizar el escaneo DBS tú mismo, no olvides ajustar épsilon y la cantidad de vecinos, ya que influyen en gran medida en los resultados finales.
=============================================
Referencia:
[1] Ester, M., Kriegel, HP, Sander, J. y Xu, X. (agosto de 1996). Agrupamiento espacial basado en densidad de aplicaciones con ruido. En Conferencia internacional sobre descubrimiento de conocimiento y minería de datos (Vol. 240, №6).
[2] Yang, Yang, et al. “Un DBSCAN eficiente optimizado mediante un algoritmo de optimización aritmética con aprendizaje basado en la oposición”. La revista de la supercomputación 78.18 (2022): 19566–19604.
=============================================
Todas mis publicaciones en Medium son gratuitas y de acceso abierto, ¡por eso te agradecería mucho que me siguieras aquí!
PD: Me apasionan la ciencia de datos (geo), el aprendizaje automático, la inteligencia artificial y el cambio climático. Si quieres trabajar conmigo en algún proyecto, ponte en contacto conmigo. LinkedIn.
🛰️Sígueme para más🛰️
