Ошибка памяти Python MeanShift

Question

Я запускаю алгоритм кластеризации под названием MeanShift() в модуле sklearn.cluster (here are the docs). Объект, с которым я имею дело, имеет 310 057 точек, распределенных в трехмерном пространстве. Компьютер, на котором я запускаю его, имеет в общей сложности 128 ГБ оперативной памяти, поэтому, когда я получаю следующую ошибку, мне трудно поверить, что я фактически использую все это.

[user@host ~]$ python meanshifttest.py 
Traceback (most recent call last): 
    File "meanshifttest.py", line 13, in <module> 
    ms = MeanShift().fit(X) 
    File "/home/user/anaconda/lib/python2.7/site-packages/sklearn/cluster/mean_shift_.py", line 280, in fit 
    cluster_all=self.cluster_all) 
    File "/home/user/anaconda/lib/python2.7/site-packages/sklearn/cluster/mean_shift_.py", line 99, in mean_shift 
bandwidth = estimate_bandwidth(X) 
    File "/home/user/anaconda/lib/python2.7/site-packages/sklearn/cluster/mean_shift_.py", line 45, in estimate_bandwidth 
d, _ = nbrs.kneighbors(X, return_distance=True) 
    File "/home/user/anaconda/lib/python2.7/site-packages/sklearn/neighbors/base.py", line 313, in kneighbors 
return_distance=return_distance) 
    File "binary_tree.pxi", line 1313, in sklearn.neighbors.kd_tree.BinaryTree.query (sklearn/neighbors/kd_tree.c:10007) 
    File "binary_tree.pxi", line 595, in sklearn.neighbors.kd_tree.NeighborsHeap.__init__ (sklearn/neighbors/kd_tree.c:4709) 
MemoryError 

код я бегу, выглядит следующим образом:

from sklearn.cluster import MeanShift 
import asciitable 
import numpy as np 
import time 

data = asciitable.read('./multidark_MDR1_FOFID85000000000_ParticlePos.csv',delimiter=',') 
x = [data[i][2] for i in range(len(data))] 
y = [data[i][3] for i in range(len(data))] 
z = [data[i][4] for i in range(len(data))] 
X = np.array(zip(x,y,z)) 

t0 = time.time() 
ms = MeanShift().fit(X) 
t1 = time.time() 
print str(t1-t0) + " seconds." 
labels = ms.labels_ 
print set(labels) 

бы кто-нибудь есть какие-либо идеи о том, что происходит? К сожалению, я не могу переключить алгоритмы кластеризации, потому что это единственное, что я нашел, что делает хорошую работу в дополнение к тому, чтобы не принимать длину связывания/k число кластеров/априорную информацию.

Заранее благодарен!

** UPDATE: Я посмотрел в документацию немного больше, и он говорит следующее:

Масштабируемость:

Поскольку эта реализация использует плоское ядро ​​и
клубок Дерево для поиска членов каждого ядра, сложность будет
до O (T * n * log (n)) в нижних размерах, с n числом выборок
и T - количество точек. В более высоких измерениях сложность будет
стремится к O (T * n^2).

Масштабируемость может быть увеличена за счет использования меньшего количества семян, например, используя
более высокое значение min_bin_freq в функции get_bin_seeds.

Обратите внимание, что функция rate_bandwidth значительно менее масштабируема, чем
алгоритм среднего сдвига и будет узким местом, если оно используется.

Это, кажется, имеет некоторый смысл, потому что если вы посмотрите на ошибки в деталях он жалуется estimate_bandwidth. Является ли это признаком того, что я просто использую слишком много частиц для алгоритма?

Answer 1

Судя по сообщению об ошибке, я подозреваю, что он пытается вычислить все попарные расстояния между точками, что означает, что ему нужны 310057² чисел с плавающей запятой или 716 ГБ ОЗУ.

Вы можете отключить эту функцию, предоставив явный аргумент bandwidth конструктору MeanShift.

Это, возможно, ошибка; рассмотрите вопрос об отправке отчета об ошибке. (The scikit учиться команда, которая включает в себя, в последнее время работает, чтобы избавиться от этих чрезмерно дорогих дистанционных расчетов в различных местах, но, видимо, никто не смотрел на meanshift.)

EDIT: расчеты выше были в 3 раза, но использование памяти было действительно квадратичным. Я просто исправил это в dev-версии scikit-learn.