MemoryError в Python при использовании cKDTree().query_ball_tree

У меня есть большие 2D-массивы с несортированными (X, Y) точками, для которых мне нужно знать, какие точки находятся в непосредственной близости друг от друга (поиск ближайшего соседа). Я использовал cKDTree и query_ball_tree с успехом для массивов с около 500 000 (X, Y) точек. Однако, когда я пробую тот же алгоритм для наборов данных более 1 000 000 точек, query_ball_tree приводит к ошибке MemoryError.

Я использую 64-битную Windows с 16 ГБ встроенной памяти и пробовал как 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. Что может быть причиной того, что это не так?

Спасибо за помощь и советы.


python scipy kdtree
person Eelco Verschelling    schedule 06.08.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Я испытал MemoryError с cKDTree SciPy во время строительства и KDTree scikit-learn при вызове .query_radius(). Я обнаружил, что Scikit-learn BallTree был более эффективным с точки зрения использования памяти, и использование BallTree решило проблему для меня. Я протестировал BallTree с 1 миллионом точек данных в своей 64-битной системе. Он по-прежнему потребляет всю мою доступную память (12 ГБ) и некоторое пространство подкачки, но я не получаю MemoryError.

Запросы на BallTree не будут такими быстрыми, как KDTree, так как ваши данные двумерные, а BallTrees медленнее, чем KDTrees, когда d ‹= 3 (см. объяснение здесь). Однако, учитывая, что cKDtree и KDTree scikit-learn поднимают 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)), но BallTree.query_radius() scikit-learn возвращает np.array из np.arrays, а не list из lists, поэтому он должен сэкономить вам немного памяти ( см. этот ответ для объяснения).

person JaminSore    schedule 06.08.2013
comment
Обратите внимание, что это не совсем то, что ищет OP: вы предлагаете .query(), тогда как .query_ball_tree() необходимо. Не совсем корректное сравнение. - person ximiki; 23.01.2018
comment
@ximiki, спасибо! Я удивлен, что никто не упомянул об этом за ~ 4,5 года с тех пор, как я опубликовал это. Я обновил свой ответ. - person JaminSore; 24.01.2018
comment
Ball-tree также не является KD-деревом (и эффекты не упоминаются, несмотря на то, что говорят, что оно работает с некоторыми заданными измерениями). Но я также рекомендую sklearn для этих структур данных. - person sascha; 24.01.2018
comment
@sascha, я обновил свой ответ. Помимо производительности, вы имели в виду другие эффекты? - person JaminSore; 24.01.2018
comment
@JaminSore Вместо того, чтобы запрашивать ближайших соседей в одиночном списке Можно ли использовать метод шарового дерева для вычисления ближайших удаленных соседей для координат между два вложенных списка: a и b, где a dimension = 1000,2, b dimension = 2000,2: например. a=[ [1.2, 1.3], [6.5, 10] ... ] и b= [ [11,1.2] , [9.6, 8]... ]. Я сделал это, используя scipy.spatial.kdtree, выполнив: tree = spatial.KDTree(a) и closest_distance, closest_index = tree.query(b, k=1, p=2). Но я не уверен, что это возможно с ball tree. Является? - person Chuck; 04.11.2018
comment
@ Чак Да. Из документов query() принимает подобный массиву (читай list, numpy.array или что-то похожее на массив) в качестве первого аргумента. В моем примере points, которые я передал в query_radius(), не обязательно должны были быть теми же точками, которые использовались при построении — то же самое касается query(). - person JaminSore; 05.11.2018