如何使用python加快最近邻居搜索的速度？

Question

我有一个代码，该代码计算到与已分配的体素最接近的体素（未分配）。那就是我有一个体素数组，很少有体素已经分配了标量（1,2,3,4 .... etc）值，而很少有体素是空的（假设值是“ 0”）。下面的代码查找到最接近未分配体素的分配体素，并为该体素分配相同的标量。因此，标量为“ 0”的体素将根据最近的体素分配一个值（1或2或3，...）。下面的代码可以工作，但是会花费太多时间。有替代方法吗？还是对如何进一步改进有任何反馈？

“”“＃self.voxels是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

例

“”“这是一个带有小型数据集的小示例：”“”

import numpy as np
from scipy.spatial import cKDTree
import timeit

voxels = np.zeros((10,10,5), dtype=np.uint8)
voxels[1:2,:,:] = 5.
voxels[5:6,:,:] = 2.
voxels[:,3:4,:] = 1.
voxels[:,8:9,:] = 4.
argx, argy, argz = np.where(voxels==0)

tic=timeit.default_timer()
argx1, argy1, argz1 = np.where(voxels!=0)   # 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= 5.)
argx2, argy2, argz2 = a[ndx][:][:,0],a[ndx][:][:,1],a[ndx][:][:,2]
voxels[argx,argy,argz] = voxels[argx2,argy2,argz2]
toc=timeit.default_timer()
timetaken = toc - tic #elapsed time in seconds
print '\nTime to fill empty voxels', timetaken

用于可视化：

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()    

现在，如果我将体素数组的维数设置为（500,500,500），则计算最近的搜索所花费的时间不再有效。我该如何克服？并行计算能否减少时间（我不知道我是否可以并行化代码，如果可以，请告诉我）？

潜在的解决方法：

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

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

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

Answer 1

您可以切换到近似最近邻 (ANN) 算法，这些算法通常利用复杂的散列或邻近图技术来快速索引数据并执行更快的查询。一个例子是 Spotify 的Annoy。Annoy 的 README 包含一个图表，显示了近年来发布的各种 ANN 算法的精度-性能权衡比较。性能最佳的算法（在发布此评论时），hnsw，在非度量空间库 (NMSLIB)下有一个 Python 实现。

Answer 2

尝试sklearn.neighbors.NearestNeighbors会很有趣，它提供n_jobs参数：

运行邻居搜索的并行作业数。

该软件包还提供了 Ball Tree 算法，您可以将其与 kd-tree 算法进行测试，但我的预感是 kd-tree 会更好（但这又取决于您的数据，因此请研究一下！）。

您可能还想使用降维，这很简单。这个想法是减少维度，从而使数据包含更少的信息，从而可以更快地解决最近邻问题。当然，这里有一个权衡，准确性！

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

备注：

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