6

我有带有未排序（X，Y）点的大型二维数组，我需要知道哪些点彼此非常接近（最近邻查找）。我已经成功地使用了 cKDTree 和 query_ball_tree 来处理大约 500,000 (X,Y) 点的数组。但是，当我对超过 1,000,000 个点的数据集尝试相同的算法时，query_ball_tree 会导致 MemoryError。

我使用具有 16Gb 内部内存的 64 位 Windows，并尝试了 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。它没有的原因可能是什么？

感谢您的帮助和建议。

4

1 回答 1

5

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

对 a 的查询BallTree不会像 a 那样快，KDTree因为您的数据是 2D 的，并且当 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-learn 会BallTree.query_radius()返回 an np.arrayof np.arrays 而不是 a listof s，因此它应该会为list您节省一些内存（请参阅此答案一个解释）。

于 2013-08-06T14:50:43.843 回答