如何使用python加速最近邻搜索？

Question

我有一个代码，它计算最近的体素（未指定）到一个体素（已指定）。也就是说，我有一个体素数组，很少有体素已经指定了标量（1，2，3，4…等等）值，而且很少体素是空的（假设值是'0'）。下面的代码查找与未指定体素最近的指定体素，并为该体素指定相同的标量。因此，标量为“0”的体素将基于最近的体素指定一个值（1、2或3…）。下面的代码可以工作，但需要太多时间。 有没有别的办法？或者你对如何进一步改进它有什么反馈？在

“”#自身体素是3D numpy数组“”

def fill_empty_voxel1(self,argx, argy, argz):
""" where # argx, argy, argz are the voxel location where the voxel is zero"""
    argx1, argy1, argz1 = np.where(self.voxels!=0)   # find the non zero voxels
    a = np.column_stack((argx1, argy1, argz1)) 
    b = np.column_stack((argx, argy, argz))
    tree = cKDTree(a, leafsize=a.shape[0]+1)
    distances, ndx = tree.query(b, k=1, distance_upper_bound= self.mean) # self.mean is a mean radius search value
    argx2, argy2, argz2 = a[ndx][:][:,0],a[ndx][:][:,1],a[ndx][:][:,2]
    self.voxels[argx,argy,argz] = self.voxels[argx2,argy2,argz2] # update the voxel array

示例

“”“下面是一个具有小数据集的小示例：”“”

^{pr2}$

对于可视化：

from mayavi import mlab
data = voxels.astype('float')
scalar_field = mlab.pipeline.scalar_field(data)
iso_surf = mlab.pipeline.iso_surface(scalar_field)
surf = mlab.pipeline.surface(scalar_field)  
vol = mlab.pipeline.volume(scalar_field,vmin=0,vmax=data.max())  
mlab.outline()    
mlab.show()    

现在，如果我将体素数组的维数设置为（500500500），那么计算最近搜索所需的时间不再有效。我怎样才能克服这个问题？并行计算可以减少时间吗（我不知道是否可以并行化代码，如果你能，请告诉我）？在

潜在的解决方案：

通过在cKDTree查询中添加n_jobs=-1参数，可以大大提高计算时间。在

distances, ndx = tree.query(b, k=1, distance_upper_bound= 5., n_jobs=-1)

我能够在不到一个小时内计算出13核CPU上的数组（400100100）的距离。我试过用1个处理器，完成同一个阵列大约需要18个小时。 感谢@gsamaras的回答！在

Answer 1

您可以切换到近似最近邻（ANN）算法，这些算法通常利用复杂的哈希或邻近图技术来快速索引数据并执行更快的查询。Spotify的Annoy就是一个例子。naugle的自述包括一个图表，显示了近年来发布的各种ANN算法的精度性能权衡比较。性能最好的算法（在发布此注释时）hnsw，在Non-Metric Space Library (NMSLIB)下有一个Python实现。在

Answer 2

尝试一下sklearn.neighbors.NearestNeighbors，它提供了n_jobs参数：

The number of parallel jobs to run for neighbors search.

这个软件包还提供了Ball-Tree算法，您可以将其与kd-Tree-one进行比较测试，但是我的预感是kd-Tree会更好（但这也取决于您的数据，所以请对此进行研究！）。在

---

您可能还想使用维数缩减，这很简单。这样做的目的是减少你的维度，这样你的数据包含的信息就更少了，这样解决最近邻问题的速度就会更快。当然，这是有代价的，准确性！在

通过降维，你可能会得到更少的准确度，但是值得一试。然而，这通常适用于高维空间，而且你只是在3D。所以我不知道对于您的具体情况，使用sklearn.decomposition.PCA是否有意义。在

---

一句话：

如果你真的想要高性能，你不能用python来获得它，你可以切换到c++，并使用CGAL为例。在