我怎样才能找到第 k 个最近的邻居？

Question

我有一个包含近 4000000 个条目的数据框。基于 3 个特征，我想找到每个点与其第 1000 个最近邻点之间的距离。到目前为止，我已经这样尝试过：

from sklearn.neighbors import NearestNeighbors    
neigh = NearestNeighbors(n_neighbors=1000)
nbrs = neigh.fit(df[features])
distances, indices = nbrs.kneighbors(df[features])

Afterwars 我会切片 distances 数组以获得一个数组，其中每个条目到第 1000 个最近邻居的距离，因为这是我唯一关心的。但是我没有走那么远，因为我没有足够的内存来存储形状为 (4000000, 1000) 的数组。
有没有一种方法可以只保存到第 1000 个邻居的距离并丢弃所有其他 999？

背景是我正在尝试为运行一个 DBSCAN 算法找到一个适合 epsilon 的算法，但显然我的数据点彼此太接近了。我已经为 5 个和 100 个邻居尝试了上面的代码。然而，除了一些异常值之外，距离几乎为 0。 Quantiles for distances to the 100th neighbor

Answer 1

您不妨试试：

from sklearn.neighbors import KDTree
x = np.random.randn(4000000,3)
kdt = KDTree(x)

closest_1000th =[]
for i in range(x.shape[0]):
    dist, _ = kdt.query(x[i,:].reshape(1,-1),1000)
    closest_1000th.append(dist[0, -1])

在我的 4Gb RAM 笔记本电脑上，完成此任务大约需要 1 小时。

小费@bogovicj。

我怎样才能找到第 k 个最近的邻居？

How can I find just the kth-nearest neighbor?

python

dbscan

scikit-learn