Si te encuentras con algún detalle que te causa duda puedes dejarlo en la sección de comentarios y te responderemos rápidamente.
Solución:
Puede agrupar datos espaciales de latitud y longitud con DBSCAN de scikit-learn sin calcular previamente una matriz de distancia.
db = DBSCAN(eps=2/6371., min_samples=5, algorithm='ball_tree', metric='haversine').fit(np.radians(coordinates))
Esto viene de este tutorial sobre agrupación de datos espaciales con scikit-learn DBSCAN. En particular, observe que el eps El valor sigue siendo 2 km, pero se divide por 6371 para convertirlo en radianes. Además, observe que .fit() toma las coordenadas en radianes para la métrica haversine.
DBSCAN es quiso decir para ser utilizado en los datos brutos, con un índice espacial de aceleración. La única herramienta que conozco con aceleración para distancias geográficas es ELKI (Java); lamentablemente, scikit-learn solo admite esto para algunas distancias como la distancia euclidiana (ver sklearn.neighbors.NearestNeighbors). Pero aparentemente, puede permitirse calcular previamente las distancias por pares, por lo que esto no es (todavía) un problema.
Sin embargo, no leíste la documentación con suficiente atención, y su suposición de que DBSCAN usa una matriz de distancia es incorrecta:
from sklearn.cluster import DBSCAN
db = DBSCAN(eps=2,min_samples=5)
db.fit_predict(distance_matrix)
usos Distancia euclidiana en las filas de la matriz de distancias, lo que obviamente no tiene ningún sentido.
Ver la documentación de DBSCAN (énfasis añadido):
clase sklearn.cluster.DBSCAN (eps = 0.5, min_samples = 5, métrica = ‘euclidiana’, algoritmo = ‘auto’, tamaño_hoja = 30, p = Ninguno, estado_aleatorio = Ninguno)
métrico : stringo invocable
La métrica que se utilizará al calcular la distancia entre instancias en una entidad. array. Si la métrica es un string o invocable, debe ser una de las opciones permitidas por metrics.pairwise.calculate_distance para su parámetro de métrica. Si la métrica está “calculada previamente”, se supone que X es una matriz de distancia y debe ser cuadrada. X puede ser una matriz dispersa, en cuyo caso solo los elementos “distintos de cero” pueden considerarse vecinos para DBSCAN.
similar para fit_predict:
X : array o matriz de forma dispersa (CSR) (n_samples, n_features), o array de forma (n_muestras, n_samples)
Una característica array, o array de distancias entre muestras if metric = ‘precalculado’.
En otras palabras, debes hacer
db = DBSCAN(eps=2, min_samples=5, metric="precomputed")
No sé qué implementación de haversine que está utilizando, pero parece que devuelve resultados en km, por lo que eps debe ser 0,2, no 2 para 200 m.
Para el min_samples parámetro, que depende de cuál sea su salida esperada. Aquí hay un par de ejemplos. Mis salidas están usando una implementación de haversine basado en esta respuesta que da una matriz de distancia similar, pero no idéntica a la suya.
Esto es con db = DBSCAN(eps=0.2, min_samples=5)
[ 0 -1 -1 -1 1 1 1 -1 -1 1 1 1 2 2 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -1 1 1 1 1 1 2 0 -1 1 2 2 0 0 0 -1 -1 -1 1 1 1 -1 -1 1 -1 -1 1]
Esto crea tres grupos, 0, 1 y 2, y muchas de las muestras no caen en un grupo con al menos 5 miembros y, por lo tanto, no están asignadas a un grupo (se muestra como -1).
Intentando de nuevo con un min_samples valor:
db = DBSCAN(eps=0.2, min_samples=2)
[ 0 1 1 2 3 3 3 4 4 3 3 3 5 5 3 3 3 2 6 6 7 3 2 2 8
8 8 3 3 6 3 3 3 3 3 5 0 -1 3 5 5 0 0 0 6 -1 -1 3 3 3
7 -1 3 -1 -1 3]
Aquí, la mayoría de las muestras se encuentran a menos de 200 m de al menos otra muestra y, por lo tanto, caen en uno de los ocho grupos 0 a 7.
Editado para agregar
Parece que @ Anony-Mousse tiene razón, aunque no vi nada malo en mis resultados. En aras de contribuir con algo, aquí está el código que estaba usando para ver los clústeres:
from math import radians, cos, sin, asin, sqrt
from scipy.spatial.distance import pdist, squareform
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt
import pandas as pd
def haversine(lonlat1, lonlat2):
"""
Calculate the great circle distance between two points
on the earth (specified in decimal degrees)
"""
# convert decimal degrees to radians
lat1, lon1 = lonlat1
lat2, lon2 = lonlat2
lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
# haversine formula
dlon = lon2 - lon1
dlat = lat2 - lat1
a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
c = 2 * asin(sqrt(a))
r = 6371 # Radius of earth in kilometers. Use 3956 for miles
return c * r
X = pd.read_csv('dbscan_test.csv')
distance_matrix = squareform(pdist(X, (lambda u,v: haversine(u,v))))
db = DBSCAN(eps=0.2, min_samples=2, metric='precomputed') # using "precomputed" as recommended by @Anony-Mousse
y_db = db.fit_predict(distance_matrix)
X['cluster'] = y_db
plt.scatter(X['lat'], X['lng'], c=X['cluster'])
plt.show()