使用cKDTree()时的Python中的MemoryError.Query_ball_tree

Question

我有大型2D阵列,带有未分类(X,Y)点,我需要知道哪些点彼此非常接近(最近邻查找).我已经使用cKDTree和query_ball_tree成功获得了大约500,000(X,Y)点的数组.但是,当我为超过1,000,000个点的数据集尝试相同的算法时,query_ball_tree会导致MemoryError.

我使用64位Windows和16Gb内部存储器,并尝试了32位和64位版本的Python和扩展模块(scipy和numpy).

def Construct_SearchTree(AllXyPoints):
    KDsearch = cKDTree(AllXyPoints)  
    return KDsearch.query_ball_tree(KDsearch, Maxdist)

我的问题:

1)有没有人知道cKDTree/query_ball_tree的替代品消耗更少的内存？在这种情况下,内存使用速度不太重要.

2)我希望从32位切换到64位python和扩展可以解决MemoryError问题.可能是什么原因呢？

感谢您的帮助和建议.

Answer 1

我在构建期间经历了MemoryErrorSciPy 的经历，在调用时cKDTree经历了 scikit-learn 的经历。我发现Scikit-learn 的内存效率更高，并且使用 scikit-learn解决了我的问题。我在 64 位系统上测试了 100 万个数据点。它仍然消耗我所有的可用内存（12GB）和一些交换空间，但我没有得到.KDTree.query_radius() BallTreeBallTreeBallTreeMemoryError

对 a 的查询BallTree不会像 a 一样快，KDTree因为您的数据是二维的，并且当 d <= 3 时BallTrees 比 s 慢（请参阅此处的解释）。然而，考虑到这一点和 scikit-learn都 raise s（无论如何，在我的系统上），最简单的解决方案是使用.KDTreecKDtreeKDTreeMemorErrorBallTree

from sklearn.neighbors import BallTree
import numpy as np

max_dist = .1
points = np.random.normal(size=2000000).reshape(1000000, 2) #1 million points
ball_tree = BallTree(points)

neighbors = ball_tree.query_radius(points, max_dist)

根据您的情况Maxdist，返回的结果可能会消耗大量内存（最多 O(n^2)），但 scikit-learnBallTree.query_radius()返回 an np.arrayof np.arrays 而不是 a listof lists，因此它应该为您节省一些内存（请参阅此答案一个解释）。