DBSCAN clustering von geographischen Standortdaten

DBSCAN ist gemeint verwendet werden, die auf die raw-Daten mit einem räumlichen index für die Beschleunigung. Das einzige tool, das ich kenne, in dem die Beschleunigung für geo Entfernungen ist ELKI (Java) - scikit-learn leider unterstützt dies nur für ein paar Entfernungen wie die euklidische Distanz (siehe sklearn.neighbors.NearestNeighbors).
Aber anscheinend können Sie genug precompute paarweisen Distanzen, so ist dies nicht (noch) ein Problem.

Jedoch Sie nicht Lesen Sie die Dokumentation sorgfältig genug, und Ihre Annahme, dass DBSCAN verwendet eine Distanz-matrix ist falsch:

from sklearn.cluster import DBSCAN
db = DBSCAN(eps=2,min_samples=5)
db.fit_predict(distance_matrix)

verwendet euklidische Distanz die Distanz-matrix-Zeilen, die offensichtlich keinen Sinn.

Finden Sie in der Dokumentation von DBSCAN (Hervorhebung Hinzugefügt):

Klasse sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euklidischen', algorithm='auto', leaf_size=30, p=None, random_state=None)

Metrik : string, oder callable

Die Metrik zu verwenden, wenn die Berechnung der Entfernung zwischen Instanzen in einem feature-Matrix. Wenn die Metrik ist ein string-oder kündbar, es muss eine der Optionen erlaubt durch Metriken.paarweise.calculate_distance für seine metrischen parameter. , Wenn die Metrik "vorausberechnete", X wird angenommen, dass eine Distanz-matrix muss quadratisch sein. X kann eine sparse matrix, in dem Fall nur "ungleich null" Elemente angesehen werden können Nachbarn für DBSCAN.

ähnlich fit_predict:

X : array oder spärlich (CSR) - matrix der Form (n_samples, n_features), oder als array der Form (n_samples, n_samples)

Einer Funktion array, oder ein array von Distanzen zwischen Proben falls metric='vordefinierte'.

In anderen Worten, Sie tun müssen,

db = DBSCAN(eps=2, min_samples=5, metric="precomputed")

InformationsquelleAutor Anony-Mousse

Ich weiß nicht, was die Umsetzung von haversine du verwendest, aber es sieht aus wie es gibt Ergebnisse zurück, in km, so eps werden sollte, 0.2, 2 für 200 m ein.

Für die min_samples parameter, hängt davon ab, was Ihre erwartete Ergebnis ist. Hier sind ein paar Beispiele. Meine Ausgänge sind über eine Implementierung von haversine basierend auf diese Antwort das gibt eine Distanz-matrix-ähnlich, aber nicht identisch mit Ihnen.

Dies ist mit 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]

Dies schafft drei Cluster 0, 1 und 2, und viele der Proben fallen Sie nicht in einem cluster mit mindestens 5 Mitglieder und sind somit keine Zuordnung zu einem cluster (dargestellt als -1).

Versuchen Sie es erneut mit einer kleineren min_samples Wert:

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]

Hier die meisten Proben sind innerhalb 200m von mindestens einer weiteren Probe und fallen so in eine von acht Clustern 0 zu 7.

Bearbeitet, um hinzufügen

Sieht es aus wie @Anony-Mousse ist Recht, obwohl ich nicht sehen, nichts falsch in meiner Ergebnisse. Zum Wohle der Beitrag etwas, hier ist der code, den ich verwendet wurde, um zu sehen, die Cluster:

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()

InformationsquelleAutor Jamie Bull