我有大型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.可能是什么原因呢？
感谢您的帮助和建议.
最佳答案
我在构建期间遇到了SciPy的cKDTree的MemoryError,在调用.query_radius()时遇到了scikit-learn的KDTree.我发现Scikit-learn’s
原文链接：/python/439594.htmlBallTree的内存效率更高,使用BallTree解决了我的问题.我在我的64位系统上测试了BallTree的100万个数据点.它仍然消耗我所有可用的内存(12GB)和一些交换空间,但我没有得到MemoryError.
BallTree上的查询不会像KDTree那样快,因为您的数据是2D,并且当d <= 3时BallTrees比KDTree慢(参见说明here).但是,鉴于cKDtree和scikit-learn的KDTree都会引发MemorErrors(在我的系统上,无论如何),最简单的解决方案是使用BallTree.
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()返回np.array的np.array而不是列表列表所以它应该为你节省一些记忆(见this answer的解释).