如何使用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

尝试一下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为例。在