Как ускорить поиск ближайшего соседа с помощью python?

Question

У меня есть код, который вычисляет ближайший воксел (который не назначен) к вокселу (который назначен). То есть у меня есть массив вокселей, у немногих вокселов уже есть назначенные значения скаляра (1,2,3,4 .... и т. Д.), А несколько вокселей пустые (скажем, значение «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()  

Нет w, если у меня есть размер массива вокселей как что-то вроде (500 500 500), то время, затрачиваемое на вычисление ближайшего поиска, уже неэффективно. Как я могу это преодолеть? Может ли параллельное вычисление сократить время (я понятия не имею, могу ли я распараллелить код, если да, дайте мне знать)?

Потенциальное Исправление:

я мог бы существенно улучшить время вычисления путем добавления n_jobs = -1 параметра в запросе cKDTree.

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

я смог вычислить расстояния в менее чем за час для массива (400,100,100) на 13 основного процессора в. Я попробовал с 1 процессором, и для завершения того же массива требуется около 18 часов. Спасибо @gsamaras за ответ!

Answer 1

Было бы интересно попробовать sklearn.neighbors.NearestNeighbors, который предлагает n_jobs параметр:

Количество параллельных заданий для запуска поиска соседей.

Этот пакет также обеспечивает алгоритм Болл Tree, который вы можете проверить по сравнению с кД дерева один, однако я подозреваю, что кД-дерево будет лучше (но это опять же зависит от ваших данных, так и исследования что!).

---

Вы также можете использовать сокращение размерности, которое легко. Идея заключается в том, что вы уменьшаете свои размеры, поэтому ваши данные содержат меньше информации, так что решение проблемы ближайшего соседа может быть сделано гораздо быстрее. Конечно, здесь есть торговля, точность!

Вы можете получить/получить меньшую точность с уменьшением размерности, но это может стоить попробовать. Однако это обычно применяется в высокоразмерном пространстве, а вы просто в 3D. Поэтому я не знаю, было ли для вашего конкретного случая было бы целесообразно использовать sklearn.decomposition.PCA.

---

Замечание:

Если вы действительно хотите иметь высокую производительность, хотя, вы не получите его с python, вы можете переключиться на c++ и использовать CGAL, например.

Answer 2

Вы можете переключиться на приближенные алгоритмы ближайших соседей (ANN), которые обычно используют сложные методы хэширования или приближения, чтобы быстро индексировать ваши данные и выполнять более быстрые запросы. Одним из примеров является Spotify Annoy. В README от Annoy входит this plot, в котором показано сравнение эффективности различных алгоритмов ANN, опубликованных за последние годы. Самый эффективный алгоритм hnsw имеет реализацию Python под Non-Metric Space Library (NMSLIB).