DBSCAN для кластеризации данных географического местоположения

Ответ 1

DBSCAN предназначен для использования на необработанных данных с пространственным индексом для ускорения. Единственный инструмент, который я знаю с ускорением для географических расстояний, ELKI (Java) - scikit-learn, к сожалению, поддерживает это только на несколько расстояний, таких как евклидовы расстояние (см. sklearn.neighbors.NearestNeighbors). Но, судя по всему, вы можете притворяться, что они предкомпрометируют попарные расстояния, поэтому это еще не проблема.

Однако вы недостаточно внимательно изучили документацию, и ваше предположение о том, что DBSCAN использует матрицу расстояний, неверно:

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

использует евклидово расстояние по строкам матрицы расстояний, что, очевидно, не имеет никакого смысла.

См. документацию DBSCAN (выделено мной):

class sklearn.cluster.DBSCAN(eps = 0.5, min_samples = 5, metric = 'евклидовой', algorithm = 'auto', leaf_size = 30, p = None, random_state = None)

метрика: строка или вызываемый

Метрика, используемая при расчете расстояния между экземплярами в массиве признаков. Если метрика является строкой или вызываемой, она должна быть одной из параметров, разрешенных метрикой .pairwise.calculate_distance для ее метрического параметра. Если метрика "предварительно вычислена", предполагается, что X является матрицей расстояний и должна быть квадратной. X может быть разреженной матрицей, и в этом случае только "ненулевые" элементы могут считаться соседями для DBSCAN.

похож на fit_predict:

X: массив или разреженная (CSR) матрица формы (n_samples, n_features) или массив формы (n_samples, n_samples)

массив признаков или массив расстояний между образцами , если metric = 'precomputed'.

Другими словами, вам нужно сделать

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

Ответ 2

Вы можете группировать данные пространственной широты и долготы с помощью scikit-learn DBSCAN без предварительного вычисления матрицы расстояния.

db = DBSCAN(eps=2/6371., min_samples=5, algorithm='ball_tree', metric='haversine').fit(np.radians(coordinates))

Это из этого урока на кластеризации пространственных данных с помощью sciskit-learn DBSCAN. В частности, обратите внимание, что значение eps равно 2 км, но оно делится на 6371, чтобы преобразовать его в радианы. Также заметим, что .fit() принимает координаты в единицах радиан для метрики хаверзина.

Ответ 3

Я не знаю, какую реализацию haversine вы используете, но похоже, что он возвращает результаты в км, поэтому eps должно быть 0,2, а не 2 на 200 м.

Для параметра min_samples это зависит от ожидаемого результата. Вот несколько примеров. Мои выходы используют реализацию haversine на основе этого ответа, которая дает матрицу расстояний, аналогичную, но не идентичную вашей.

Это с 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]

Это создает три кластера 0, 1 и 2, и многие образцы не попадают в кластер с не менее чем 5 членами и поэтому не назначаются кластеру (отображается как -1).

Повторное повторение с меньшим значением min_samples:

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]

Здесь большинство образцов находятся в пределах 200 м по меньшей мере от одного другого образца и поэтому попадают в один из восьми кластеров 0 до 7.

Отредактировано для добавления

Похоже, что @Anony-Mousse прав, хотя я не видел ничего плохого в моих результатах. Чтобы внести что-то, здесь код, который я использовал, чтобы увидеть кластеры:

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

Ответ 4

@eos Дает лучший ответ, который я считаю, - а также использование расстояния Хаверсайна (наиболее релевантной меры расстояния в данном случае) позволяет избежать необходимости создавать предварительно вычисленную матрицу расстояний. Если вы создаете матрицу расстояний, вам необходимо рассчитать попарные расстояния для каждой комбинации точек (хотя вы, очевидно, можете сэкономить немного времени, воспользовавшись тем, что ваша метрика расстояния является симметричной).

Если вы просто дадите DBSCAN меру расстояния и будете использовать алгоритм ball_tree, это позволит избежать необходимости расчета каждого возможного расстояния. Это связано с тем, что алгоритм шарового дерева может использовать теорему о треangularьном неравенстве, чтобы уменьшить количество кандидатов, которые необходимо проверить, чтобы найти ближайших соседей точки данных (это самая большая задача в DBSCAN).

Теорема о треangularьном неравенстве гласит:

|x+y| <= |x| + |y|

... поэтому, если точка p находится на расстоянии x от соседа n, а другая точка q - это расстояние y от p, если x+y больше нашей радиус ближайшего соседа, мы знаем, что q должен быть слишком далеко от n, чтобы считаться соседом, поэтому нам не нужно вычислять его расстояние.

Подробнее о работе шаровых деревьев читайте в документации scikit-learn.