scikit-learn：使用 DBSCAN 预测新点
scikit-learn: Predicting new points with DBSCAN
我正在使用 DBSCAN 通过 Scikit-Learn (Python 2.7) 对一些数据进行聚类：
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(random_state=0)
dbscan.fit(X)
但是，我发现没有内置函数（除了 "fit_predict"）可以将新数据点 Y 分配给原始数据 X 中标识的聚类。K-意味着方法有一个 "predict" 函数，但我希望能够用 DBSCAN 做同样的事情。像这样：
dbscan.predict(X, Y)
因此可以从 X 推断出密度，但 return 值（簇 assignments/labels）仅适用于 Y。据我所知，此功能在 R 中可用，所以我假设它也以某种方式在 Python 中可用。我似乎找不到这方面的任何文档。
另外，我已经尝试寻找 DBSCAN 不能用于标记新数据的原因，但我没有找到任何理由。
聚类不是分类。
聚类未标记。如果你想把它压缩成一种预测思维方式（这不是最好的主意），那么它本质上是 无需学习就可以预测 。因为没有可用于聚类的标记训练数据。它必须根据它看到的内容为数据制作新标签。但是你不能在单个实例上这样做，你只能 "bulk predict".
但是scipys DBSCAN有点问题：
random_state : numpy.RandomState, optional :
The generator used to initialize the centers. Defaults to numpy.random.
DBSCAN 没有 "initialize the centers"，因为 DBSCAN 中没有中心。
几乎 只有 可以将新点分配给旧聚类的聚类算法是 k-means（及其许多变体）。因为它使用先前的迭代聚类中心执行“1NN 分类”，然后更新中心。但是大多数算法不像 k-means 那样工作，所以你不能复制这个。
如果要对新点进行分类，最好根据聚类结果训练分类器。
R 版本可能正在做的是使用 1NN 分类器进行预测；也许有额外的规则，即点被分配噪声标签，如果它们的 1NN 距离大于 epsilon，也许也只使用核心点。也许不是。
获取DBSCAN论文，不讨论"prediction" IIRC。
虽然Anony-Mousse有一些好的点（Clustering确实不是分类），但我认为分配新点的能力有它的用处。 *
基于 DBSCAN and robertlaytons ideas on github.com/scikit-learn 上的原始论文，我建议 运行 通过核心点并分配给新点 eps 内的第一个核心点的簇。
然后根据用于聚类的定义，保证您的点至少是指定聚类的边界点。
（请注意，您的观点可能会被视为噪音，而不会分配给一个集群）
我已经完成了快速实施：
import numpy as np
import scipy as sp
def dbscan_predict(dbscan_model, X_new, metric=sp.spatial.distance.cosine):
# Result is noise by default
y_new = np.ones(shape=len(X_new), dtype=int)*-1
# Iterate all input samples for a label
for j, x_new in enumerate(X_new):
# Find a core sample closer than EPS
for i, x_core in enumerate(dbscan_model.components_):
if metric(x_new, x_core) < dbscan_model.eps:
# Assign label of x_core to x_new
y_new[j] = dbscan_model.labels_[dbscan_model.core_sample_indices_[i]]
break
return y_new
聚类得到的标签（dbscan_model = DBSCAN(...).fit(X)和同一个模型在相同数据上得到的标签（dbscan_predict(dbscan_model, X)）有时会不一样。我不太确定这是不是某个地方的bug或随机结果。
编辑： 我认为上述不同预测结果的问题可能源于边界点可能靠近多个集群的可能性。如果您对此进行测试并找到答案，请更新。歧义可以通过每次打乱核心点或选择最近的核心点而不是第一个核心点来解决。
*) 手头的案例：我想评估从我的数据子集获得的集群是否对其他子集有意义，或者仅仅是一个特例。
如果它概括它支持集群的有效性和应用的预处理的早期步骤。
这里有一个稍微不同但更有效的实现。另外，不是取eps半径内的第一个最佳核心点，而是取最接近样本的核心点。
def dbscan_predict(model, X):
nr_samples = X.shape[0]
y_new = np.ones(shape=nr_samples, dtype=int) * -1
for i in range(nr_samples):
diff = model.components_ - X[i, :] # NumPy broadcasting
dist = np.linalg.norm(diff, axis=1) # Euclidean distance
shortest_dist_idx = np.argmin(dist)
if dist[shortest_dist_idx] < model.eps:
y_new[i] = model.labels_[model.core_sample_indices_[shortest_dist_idx]]
return y_new
虽然它不是完全相同的算法，但您可以使用 sklearn HDBSCAN 对新点进行近似预测。参见 here。
它是这样工作的：
clusterer = hdbscan.HDBSCAN(min_cluster_size=15, prediction_data=True).fit(data)
test_labels, strengths = hdbscan.approximate_predict(clusterer, test_points)
这里已经发布了这个问题的很好的答案。我的建议是 HDBSCAN 试一试。它提供了一个 approximate_predict() 方法，这可能是您需要的。
我们先来了解一下DBSCAN基于密度的聚类的一些基本知识，下图总结了基本概念。
让我们首先创建一个将使用 DBSCAN 聚类的示例 2D 数据集。下图显示了数据集的外观。
import numpy as np
import matplotlib.pylab as plt
from sklearn.cluster import DBSCAN
X_train = np.array([[60,36], [100,36], [100,70], [60,70],
[140,55], [135,90], [180,65], [240,40],
[160,140], [190,140], [220,130], [280,150],
[200,170], [185, 170]])
plt.scatter(X_train[:,0], X_train[:,1], s=200)
plt.show()
现在让我们使用 scikit-learn 的 DBSCAN 实现来聚类：
eps = 45
min_samples = 4
db = DBSCAN(eps=eps, min_samples=min_samples).fit(X_train)
labels = db.labels_
labels
# [ 0, 0, 0, 0, 0, 0, 0, -1, 1, 1, 1, -1, 1, 1]
db.core_sample_indices_
# [ 1, 2, 4, 9, 12, 13]
从上面的结果可以看出
- 算法找到了6个核心点
- 找到 2 个聚类（标签为 0、1）和几个异常值（噪声点）。
让我们使用以下代码片段可视化集群：
def dist(a, b):
return np.sqrt(np.sum((a - b)**2))
colors = ['r', 'g', 'b', 'k']
for i in range(len(X_train)):
plt.scatter(X_train[i,0], X_train[i,1],
s=300, color=colors[labels[i]],
marker=('*' if i in db.core_sample_indices_ else 'o'))
for j in range(i+1, len(X_train)):
if dist(X_train[i], X_train[j]) < eps:
plt.plot([X_train[i,0], X_train[j,0]], [X_train[i,1], X_train[j,1]], '-', color=colors[labels[i]])
plt.title('Clustering with DBSCAN', size=15)
plt.show()
- 聚类 0 中的点为红色
- 聚类 1 中的点为绿色
- 离群点为黑色
- 核心点用'*'标记。
- 如果两个点在 ε-nbd 范围内，则它们由一条边连接。
最后，让我们实现predict()方法来预测新数据点的聚类。实施基于以下内容：
为了使新点x属于一个簇，它必须是从簇中的核心点直接密度可达的。
我们将计算离集群最近的核心点，如果它与x的ε距离以内，我们将return核心点，否则点 x 将被宣布为噪声点（异常值）。
注意这与训练算法不同，因为我们不再允许任何更多的点成为新的核心点（即核心点的数量是固定的）。
接下来的代码片段根据上述思路实现了predict()功能
def predict(db, x):
dists = np.sqrt(np.sum((db.components_ - x)**2, axis=1))
i = np.argmin(dists)
return db.labels_[db.core_sample_indices_[i]] if dists[i] < db.eps else -1
X_test = np.array([[100, 100], [160, 160], [60, 130]])
for i in range(len(X_test)):
print('test point: {}, predicted label: {}'.format(X_test[i],
predict(db, X_test[i])))
# test point: [100 100], predicted label: 0
# test point: [160 160], predicted label: 1
# test point: [ 60 130], predicted label: -1
下一个动画展示了如何使用上面定义的 predict() 函数标记一些新的测试点。
DBSCAN.fit_predict(X, y=None, sample_weight=None)
阅读来自 https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
的更多信息
我正在使用 DBSCAN 通过 Scikit-Learn (Python 2.7) 对一些数据进行聚类：
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(random_state=0)
dbscan.fit(X)
但是，我发现没有内置函数（除了 "fit_predict"）可以将新数据点 Y 分配给原始数据 X 中标识的聚类。K-意味着方法有一个 "predict" 函数，但我希望能够用 DBSCAN 做同样的事情。像这样：
dbscan.predict(X, Y)
因此可以从 X 推断出密度，但 return 值（簇 assignments/labels）仅适用于 Y。据我所知，此功能在 R 中可用，所以我假设它也以某种方式在 Python 中可用。我似乎找不到这方面的任何文档。
另外，我已经尝试寻找 DBSCAN 不能用于标记新数据的原因，但我没有找到任何理由。
聚类不是分类。
聚类未标记。如果你想把它压缩成一种预测思维方式（这不是最好的主意），那么它本质上是 无需学习就可以预测 。因为没有可用于聚类的标记训练数据。它必须根据它看到的内容为数据制作新标签。但是你不能在单个实例上这样做，你只能 "bulk predict".
但是scipys DBSCAN有点问题：
random_state: numpy.RandomState, optional :The generator used to initialize the centers. Defaults to numpy.random.
DBSCAN 没有 "initialize the centers"，因为 DBSCAN 中没有中心。
几乎 只有 可以将新点分配给旧聚类的聚类算法是 k-means（及其许多变体）。因为它使用先前的迭代聚类中心执行“1NN 分类”，然后更新中心。但是大多数算法不像 k-means 那样工作，所以你不能复制这个。
如果要对新点进行分类，最好根据聚类结果训练分类器。
R 版本可能正在做的是使用 1NN 分类器进行预测；也许有额外的规则，即点被分配噪声标签，如果它们的 1NN 距离大于 epsilon，也许也只使用核心点。也许不是。
获取DBSCAN论文，不讨论"prediction" IIRC。
虽然Anony-Mousse有一些好的点（Clustering确实不是分类），但我认为分配新点的能力有它的用处。 *
基于 DBSCAN and robertlaytons ideas on github.com/scikit-learn 上的原始论文，我建议 运行 通过核心点并分配给新点 eps 内的第一个核心点的簇。
然后根据用于聚类的定义，保证您的点至少是指定聚类的边界点。
（请注意，您的观点可能会被视为噪音，而不会分配给一个集群）
我已经完成了快速实施：
import numpy as np
import scipy as sp
def dbscan_predict(dbscan_model, X_new, metric=sp.spatial.distance.cosine):
# Result is noise by default
y_new = np.ones(shape=len(X_new), dtype=int)*-1
# Iterate all input samples for a label
for j, x_new in enumerate(X_new):
# Find a core sample closer than EPS
for i, x_core in enumerate(dbscan_model.components_):
if metric(x_new, x_core) < dbscan_model.eps:
# Assign label of x_core to x_new
y_new[j] = dbscan_model.labels_[dbscan_model.core_sample_indices_[i]]
break
return y_new
聚类得到的标签（dbscan_model = DBSCAN(...).fit(X)和同一个模型在相同数据上得到的标签（dbscan_predict(dbscan_model, X)）有时会不一样。我不太确定这是不是某个地方的bug或随机结果。
编辑： 我认为上述不同预测结果的问题可能源于边界点可能靠近多个集群的可能性。如果您对此进行测试并找到答案，请更新。歧义可以通过每次打乱核心点或选择最近的核心点而不是第一个核心点来解决。
*) 手头的案例：我想评估从我的数据子集获得的集群是否对其他子集有意义，或者仅仅是一个特例。 如果它概括它支持集群的有效性和应用的预处理的早期步骤。
这里有一个稍微不同但更有效的实现。另外，不是取eps半径内的第一个最佳核心点，而是取最接近样本的核心点。
def dbscan_predict(model, X):
nr_samples = X.shape[0]
y_new = np.ones(shape=nr_samples, dtype=int) * -1
for i in range(nr_samples):
diff = model.components_ - X[i, :] # NumPy broadcasting
dist = np.linalg.norm(diff, axis=1) # Euclidean distance
shortest_dist_idx = np.argmin(dist)
if dist[shortest_dist_idx] < model.eps:
y_new[i] = model.labels_[model.core_sample_indices_[shortest_dist_idx]]
return y_new
虽然它不是完全相同的算法，但您可以使用 sklearn HDBSCAN 对新点进行近似预测。参见 here。
它是这样工作的：
clusterer = hdbscan.HDBSCAN(min_cluster_size=15, prediction_data=True).fit(data)
test_labels, strengths = hdbscan.approximate_predict(clusterer, test_points)
这里已经发布了这个问题的很好的答案。我的建议是 HDBSCAN 试一试。它提供了一个 approximate_predict() 方法，这可能是您需要的。
我们先来了解一下DBSCAN基于密度的聚类的一些基本知识，下图总结了基本概念。
import numpy as np
import matplotlib.pylab as plt
from sklearn.cluster import DBSCAN
X_train = np.array([[60,36], [100,36], [100,70], [60,70],
[140,55], [135,90], [180,65], [240,40],
[160,140], [190,140], [220,130], [280,150],
[200,170], [185, 170]])
plt.scatter(X_train[:,0], X_train[:,1], s=200)
plt.show()
现在让我们使用 scikit-learn 的 DBSCAN 实现来聚类：
eps = 45
min_samples = 4
db = DBSCAN(eps=eps, min_samples=min_samples).fit(X_train)
labels = db.labels_
labels
# [ 0, 0, 0, 0, 0, 0, 0, -1, 1, 1, 1, -1, 1, 1]
db.core_sample_indices_
# [ 1, 2, 4, 9, 12, 13]
从上面的结果可以看出
- 算法找到了6个核心点
- 找到 2 个聚类（标签为 0、1）和几个异常值（噪声点）。
让我们使用以下代码片段可视化集群：
def dist(a, b):
return np.sqrt(np.sum((a - b)**2))
colors = ['r', 'g', 'b', 'k']
for i in range(len(X_train)):
plt.scatter(X_train[i,0], X_train[i,1],
s=300, color=colors[labels[i]],
marker=('*' if i in db.core_sample_indices_ else 'o'))
for j in range(i+1, len(X_train)):
if dist(X_train[i], X_train[j]) < eps:
plt.plot([X_train[i,0], X_train[j,0]], [X_train[i,1], X_train[j,1]], '-', color=colors[labels[i]])
plt.title('Clustering with DBSCAN', size=15)
plt.show()
- 聚类 0 中的点为红色
- 聚类 1 中的点为绿色
- 离群点为黑色
- 核心点用'*'标记。
- 如果两个点在 ε-nbd 范围内，则它们由一条边连接。
最后，让我们实现predict()方法来预测新数据点的聚类。实施基于以下内容：
为了使新点x属于一个簇，它必须是从簇中的核心点直接密度可达的。
我们将计算离集群最近的核心点，如果它与x的ε距离以内，我们将return核心点，否则点 x 将被宣布为噪声点（异常值）。
注意这与训练算法不同，因为我们不再允许任何更多的点成为新的核心点（即核心点的数量是固定的）。
接下来的代码片段根据上述思路实现了
predict()功能def predict(db, x): dists = np.sqrt(np.sum((db.components_ - x)**2, axis=1)) i = np.argmin(dists) return db.labels_[db.core_sample_indices_[i]] if dists[i] < db.eps else -1 X_test = np.array([[100, 100], [160, 160], [60, 130]]) for i in range(len(X_test)): print('test point: {}, predicted label: {}'.format(X_test[i], predict(db, X_test[i]))) # test point: [100 100], predicted label: 0 # test point: [160 160], predicted label: 1 # test point: [ 60 130], predicted label: -1
下一个动画展示了如何使用上面定义的 predict() 函数标记一些新的测试点。
DBSCAN.fit_predict(X, y=None, sample_weight=None)
阅读来自 https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
的更多信息