时间戳

首页 > 解决方案 > 非常大的数据集中的成对距离

python - 非常大的数据集中的成对距离

问题描述

我有一个大约 [5000000 x 6] 的数组，我只需要选择彼此相距一定距离的点（行）。

想法应该是：

从数据数组的第一行开始 new_array

将 new_array 与数据数组的第二行进行比较

如果它们之间的 pdist > tol，则将行附加到 new_array

将 new_array 与数据数组中的第三行进行比较

等等...

一个问题是 RAM 大小。即使在 pdist 中，我也无法一次比较所有行。

所以我一直在考虑将数据集拆分为较小的数据集，但后来我不知道如何检索数据集中行的索引信息。

我试过 scipy cdist、scipy euclidean、sklearn euclidean_distances、sklearnpaired_distances，下面的代码是我能得到的最快的。起初它很快，但在 40k 循环之后它变得非常慢。

xyTotal=np.random.random([5000000,6])
tol=0.5
for i,z in enumerate(xyTotal):
    if (pdist(np.vstack([np.array(ng),z]))>tol).all():
        ng.append(z)

对这个问题有什么建议吗？

编辑

ktree = BallTree(xyTotal, leaf_size=40,metric='euclidean')
btsem=[]
for i,j in enumerate(xyTotal):
    ktree.query_radius(j.reshape(1,-1),r=tol, return_distance=True)
    if (ktree.query_radius(j.reshape(1,-1),r=tol, count_only=True))==1:
        btsem.append(j)

这很快，但我只选择异常值。当我到达靠近另一个点（即在一个小集群中）时，我不知道只选择一个点而离开其他点，因为我将获得集群中所有点的相同指标（它们都有距离相同）

标签： pythonnumpyscikit-learnscipy

解决方案

计算速度很慢，因为您的算法的复杂性是二次的：O(k * n * n)其中 n 是len(xyTotal)并且k是条件为真的概率。因此，假设k=0.1和n=5000000，运行时间将很长（可能需要数小时的计算）。

希望您可以编写一个O(n * log(n))及时运行的更好的实现。然而，这很难实现。您需要在kd 树ng中添加您的点，然后您可以搜索最近的邻居并检查与当前点的距离是否大于。tol

请注意，您可以找到实现 kd 树的 Python 模块，并且 SciPy 文档提供了一个用纯 Python 编写的实现示例（因此可能效率不高）。

推荐阅读