DBSCAN для кластеризации данных о географическом местоположении
У меня есть датафрейм с широтой и долготой пар.
Вот мои данные выглядят так.
order_lat order_long
0 19.111841 72.910729
1 19.111342 72.908387
2 19.111342 72.908387
3 19.137815 72.914085
4 19.119677 72.905081
5 19.119677 72.905081
6 19.119677 72.905081
7 19.120217 72.907121
8 19.120217 72.907121
9 19.119677 72.905081
10 19.119677 72.905081
11 19.119677 72.905081
12 19.111860 72.911346
13 19.111860 72.911346
14 19.119677 72.905081
15 19.119677 72.905081
16 19.119677 72.905081
17 19.137815 72.914085
18 19.115380 72.909144
19 19.115380 72.909144
20 19.116168 72.909573
21 19.119677 72.905081
22 19.137815 72.914085
23 19.137815 72.914085
24 19.112955 72.910102
25 19.112955 72.910102
26 19.112955 72.910102
27 19.119677 72.905081
28 19.119677 72.905081
29 19.115380 72.909144
30 19.119677 72.905081
31 19.119677 72.905081
32 19.119677 72.905081
33 19.119677 72.905081
34 19.119677 72.905081
35 19.111860 72.911346
36 19.111841 72.910729
37 19.131674 72.918510
38 19.119677 72.905081
39 19.111860 72.911346
40 19.111860 72.911346
41 19.111841 72.910729
42 19.111841 72.910729
43 19.111841 72.910729
44 19.115380 72.909144
45 19.116625 72.909185
46 19.115671 72.908985
47 19.119677 72.905081
48 19.119677 72.905081
49 19.119677 72.905081
50 19.116183 72.909646
51 19.113827 72.893833
52 19.119677 72.905081
53 19.114100 72.894985
54 19.107491 72.901760
55 19.119677 72.905081
Я хочу сгруппировать эти точки, которые находятся ближе всего друг к другу (расстояние 200 метров), следуя моей матрице расстояний.
from scipy.spatial.distance import pdist, squareform
distance_matrix = squareform(pdist(X, (lambda u,v: haversine(u,v))))
array([[ 0. , 0.2522482 , 0.2522482 , ..., 1.67313071,
1.05925366, 1.05420922],
[ 0.2522482 , 0. , 0. , ..., 1.44111548,
0.81742536, 0.98978355],
[ 0.2522482 , 0. , 0. , ..., 1.44111548,
0.81742536, 0.98978355],
...,
[ 1.67313071, 1.44111548, 1.44111548, ..., 0. ,
1.02310118, 1.22871515],
[ 1.05925366, 0.81742536, 0.81742536, ..., 1.02310118,
0. , 1.39923529],
[ 1.05420922, 0.98978355, 0.98978355, ..., 1.22871515,
1.39923529, 0. ]])
Затем я применяю алгоритм кластеризации DBSCAN на матрице расстояний.
from sklearn.cluster import DBSCAN
db = DBSCAN(eps=2,min_samples=5)
y_db = db.fit_predict(distance_matrix)
Я не знаю, как выбрать значение eps & min_samples. Он группирует точки, которые находятся слишком далеко, в одном кластере (приблизительно 2 км на расстоянии). Это потому, что он вычисляет евклидово расстояние при кластеризации? пожалуйста помоги.
3 ответа
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 (выделение добавлено):
класс sklearn.cluster.DBSCAN(eps=0,5, min_samples=5, метрика ='евклидова', алгоритм ='auto', leaf_size=30, p= нет, random_state= нет)
метрика: строка или вызываемый
Метрика, используемая при расчете расстояния между экземплярами в массиве объектов. Если метрика является строкой или может вызываться, это должна быть одна из опций, разрешенных metrics.pairwise.calculate_distance для ее параметра метрики. Если метрика "предварительно вычислена", предполагается, что X является матрицей расстояний и должно быть квадратным. X может быть разреженной матрицей, и в этом случае только "ненулевые" элементы могут считаться соседями для DBSCAN.
похоже на fit_predict:
X: матрица массива или разреженной (CSR) формы (n_samples, n_features) или массив формы (n_samples, n_samples)
Массив объектов или массив расстояний между выборками, если метрика = "предварительно вычислено".
Другими словами, вам нужно сделать
db = DBSCAN(eps=2, min_samples=5, metric="precomputed")
Вы можете кластеризовать данные пространственной широты и долготы с помощью DBSCAN scikit-learn без предварительного вычисления матрицы расстояний.
db = DBSCAN(eps=2/6371., min_samples=5, algorithm='ball_tree', metric='haversine').fit(np.radians(coordinates))
Это происходит из этого руководства по кластеризации пространственных данных с помощью DBSCAN scikit-learn. В частности, обратите внимание, что eps значение по-прежнему составляет 2 км, но оно делится на 6371, чтобы преобразовать его в радианы. Также обратите внимание, что .fit() принимает координаты в радианах для метрики haversine.
Я не знаю, что реализация 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()
Я думаю, что @eos дает лучший ответ - помимо использования расстояния Хаверсина (наиболее актуальной меры расстояния в данном случае), он позволяет избежать необходимости генерировать предварительно вычисленную матрицу расстояний. Если вы создаете матрицу расстояний, вам необходимо рассчитать попарные расстояния для каждой комбинации точек (хотя вы, очевидно, можете сэкономить немного времени, воспользовавшись тем фактом, что ваша метрика расстояния является симметричной).
Если вы просто предоставите DBSCAN измеритель расстояния и используете ball_treeалгоритм, тем не менее, он может избежать необходимости рассчитывать все возможные расстояния. Это связано с тем, что алгоритм шарового дерева может использовать теорему о треугольном неравенстве, чтобы уменьшить количество кандидатов, которые необходимо проверить, чтобы найти ближайших соседей точки данных (это самая большая работа в DBSCAN).
Теорема о треугольном неравенстве гласит:
|x+y| <= |x| + |y|
... так что если точка p это расстояние x от своего соседа n, и еще один момент q это расстояние y от p, если x+y больше, чем радиус нашего ближайшего соседа, мы знаем, что q должно быть слишком далеко от n считаться соседом, поэтому нам не нужно рассчитывать расстояние до него.
Подробнее о том, как работают деревья шариков, читайте в документации scikit-learn.
Есть три разных способа использования DBSCAN с данными GPS. Во-первых, вы можете использовать параметр eps, чтобы указать максимальное расстояние между точками данных, которое вы будете рассматривать для создания кластера, как указано в других ответах, вам необходимо принять во внимание масштаб метрики расстояния, которую вы используете, выбирая ценность, которая имеет смысл. Затем вы можете использовать min_samples, который можно использовать как способ фильтрации точек данных при перемещении. Наконец, метрика позволит вам использовать любое расстояние, которое вы хотите.
Например, в конкретном исследовательском проекте, над которым я работаю, я хочу извлечь важные местоположения из местоположений данных GPS субъекта, собранных с его смартфона. Меня не интересует, как объект перемещается по городу, и мне удобнее работать с расстояниями в метрах, тогда я могу сделать следующее:
from geopy import distance
def mydist(p1, p2):
return distance.great_circle((p1[0],p1[1],100),(p2[0],p2[1],100)).meters
DBSCAN(eps=50,min_samples=50,n_jobs=-1,metric=mydist)
Здесь eps согласно документации DBSCAN "Максимальное расстояние между двумя образцами, чтобы один считался соседним с другим". В то время как минимальное количество отсчетов - это "Количество отсчетов (или общий вес) в окрестности точки, которая будет считаться базовой". В основном с помощью eps вы контролируете, насколько близко должны быть точки данных в кластере, в приведенном выше примере я выбрал 100 метров. Минимальные выборки - это всего лишь способ контролировать плотность, в приведенном выше примере данные были захвачены примерно с одной выборкой в секунду, потому что меня не интересует, когда люди перемещаются, а вместо этого я хочу убедиться, что я попадаю в стационарные места. как минимум эквивалент 60 секунд данных GPS из того же места.
Если это все еще не имеет смысла, взгляните на эту анимацию DBSCAN.