DBSCAN 用于地理位置数据的聚类
DBSCAN for clustering of geographic location data
我有一个包含纬度和经度对的数据框。
这是我的数据框。
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 公里）是因为它在集群时计算欧氏距离吗？请帮忙
我不知道您使用的 haversine 是什么实现，但看起来 returns 以公里为单位，所以 eps 应该是 0.2，而不是 2 表示 200 米.
对于 min_samples 参数，这取决于您的预期输出是什么。这里有几个例子。我的输出使用的是基于 this answer 的 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()
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='euclidean', algorithm='auto', leaf_size=30, p=None, random_state=None)
metric : string, or callable
The metric to use when calculating distance between instances in a feature array. If metric is a string or callable, it must be one of the options allowed by metrics.pairwise.calculate_distance for its metric parameter. If metric is “precomputed”, X is assumed to be a distance matrix and must be square. X may be a sparse matrix, in which case only “nonzero” elements may be considered neighbors for DBSCAN.
与fit_predict相似：
X : array or sparse (CSR) matrix of shape (n_samples, n_features), or array of shape (n_samples, n_samples)
A feature array, or array of distances between samples if metric='precomputed'.
换句话说，你需要做
db = DBSCAN(eps=2, min_samples=5, metric="precomputed")
您可以使用 scikit-learn 的 DBSCAN 对空间经纬度数据进行聚类，而无需预先计算距离矩阵。
db = DBSCAN(eps=2/6371., min_samples=5, algorithm='ball_tree', metric='haversine').fit(np.radians(coordinates))
这来自 clustering spatial data with scikit-learn DBSCAN 上的教程。请特别注意 eps 值仍然是 2km，但它被除以 6371 以将其转换为弧度。另外，请注意 .fit() 以弧度为单位获取半正弦度量的坐标。
@eos 给出了我认为最好的答案 - 以及利用 Haversine 距离（在这种情况下最相关的距离度量），它避免了生成预先计算的距离矩阵的需要。如果你创建一个距离矩阵，那么你需要计算每个点组合的成对距离（尽管你显然可以通过利用你的距离度量是对称的这一事实来节省一点时间）。
如果您只为 DBSCAN 提供距离度量并使用 ball_tree 算法，则可以避免计算每个可能的距离的需要。这是因为ball tree算法可以利用三角不等式定理来减少需要检查的候选数以找到数据点的最近邻（这是DBSCAN中最大的工作）。
三角不等式定理指出：
|x+y| <= |x| + |y|
...因此，如果点 p 与其邻居 n 的距离为 x，而另一个点 q 与其邻居的距离为 y p，如果x+y大于我们的最近邻半径，我们就知道q一定离n太远，不能算近邻，所以我们不需要计算它的距离。
中阅读有关球树如何工作的更多信息
要将 DBSCAN 与 GPS 数据结合使用，您可以执行三种不同的操作。首先是您可以使用 eps 参数来指定您将考虑创建集群的数据点之间的最大距离，如其他答案中指定的那样，您需要考虑规模您正在使用的距离度量选择一个有意义的值。然后你可以使用 min_samples 这可以用作在移动时过滤掉数据点的方法。最后 metric 将允许您使用您想要的任何距离。
例如，在我正在进行的一个特定研究项目中，我想从受试者的智能手机收集的 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 documentation “两个样本之间的最大距离，一个被认为在另一个样本的附近。”
而最小样本是“一个点被视为核心点的邻域中的样本数（或总权重）”。基本上，使用 eps 可以控制集群中数据点的距离，在上面的示例中我选择了 100 米。 Min samples 只是一种控制密度的方法，在上面的例子中，数据是每秒捕获一个样本，因为我对人们何时四处走动不感兴趣，而是固定位置我想确保从同一位置至少获得相当于 60 秒的 GPS 数据。
如果这仍然没有意义，请查看此 DBSCAN animation。
我有一个包含纬度和经度对的数据框。
这是我的数据框。
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 公里）是因为它在集群时计算欧氏距离吗？请帮忙
我不知道您使用的 haversine 是什么实现，但看起来 returns 以公里为单位，所以 eps 应该是 0.2，而不是 2 表示 200 米.
对于 min_samples 参数，这取决于您的预期输出是什么。这里有几个例子。我的输出使用的是基于 this answer 的 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()
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='euclidean', algorithm='auto', leaf_size=30, p=None, random_state=None)
metric : string, or callable
The metric to use when calculating distance between instances in a feature array. If metric is a string or callable, it must be one of the options allowed by metrics.pairwise.calculate_distance for its metric parameter. If metric is “precomputed”, X is assumed to be a distance matrix and must be square. X may be a sparse matrix, in which case only “nonzero” elements may be considered neighbors for DBSCAN.
与fit_predict相似：
X : array or sparse (CSR) matrix of shape (n_samples, n_features), or array of shape (n_samples, n_samples)
A feature array, or array of distances between samples if metric='precomputed'.
换句话说，你需要做
db = DBSCAN(eps=2, min_samples=5, metric="precomputed")
您可以使用 scikit-learn 的 DBSCAN 对空间经纬度数据进行聚类，而无需预先计算距离矩阵。
db = DBSCAN(eps=2/6371., min_samples=5, algorithm='ball_tree', metric='haversine').fit(np.radians(coordinates))
这来自 clustering spatial data with scikit-learn DBSCAN 上的教程。请特别注意 eps 值仍然是 2km，但它被除以 6371 以将其转换为弧度。另外，请注意 .fit() 以弧度为单位获取半正弦度量的坐标。
@eos 给出了我认为最好的答案 - 以及利用 Haversine 距离（在这种情况下最相关的距离度量），它避免了生成预先计算的距离矩阵的需要。如果你创建一个距离矩阵，那么你需要计算每个点组合的成对距离（尽管你显然可以通过利用你的距离度量是对称的这一事实来节省一点时间）。
如果您只为 DBSCAN 提供距离度量并使用 ball_tree 算法，则可以避免计算每个可能的距离的需要。这是因为ball tree算法可以利用三角不等式定理来减少需要检查的候选数以找到数据点的最近邻（这是DBSCAN中最大的工作）。
三角不等式定理指出：
|x+y| <= |x| + |y|
...因此，如果点 p 与其邻居 n 的距离为 x，而另一个点 q 与其邻居的距离为 y p，如果x+y大于我们的最近邻半径，我们就知道q一定离n太远，不能算近邻，所以我们不需要计算它的距离。
要将 DBSCAN 与 GPS 数据结合使用，您可以执行三种不同的操作。首先是您可以使用 eps 参数来指定您将考虑创建集群的数据点之间的最大距离，如其他答案中指定的那样，您需要考虑规模您正在使用的距离度量选择一个有意义的值。然后你可以使用 min_samples 这可以用作在移动时过滤掉数据点的方法。最后 metric 将允许您使用您想要的任何距离。
例如，在我正在进行的一个特定研究项目中，我想从受试者的智能手机收集的 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 documentation “两个样本之间的最大距离，一个被认为在另一个样本的附近。” 而最小样本是“一个点被视为核心点的邻域中的样本数（或总权重）”。基本上，使用 eps 可以控制集群中数据点的距离，在上面的示例中我选择了 100 米。 Min samples 只是一种控制密度的方法，在上面的例子中，数据是每秒捕获一个样本，因为我对人们何时四处走动不感兴趣，而是固定位置我想确保从同一位置至少获得相当于 60 秒的 GPS 数据。
如果这仍然没有意义，请查看此 DBSCAN animation。