scikit-learn/scikit-learn — Issue #585: Memory Issues in BallTree
Author: jakevdp
Created: 2012-01-24 14:48:07+00:00
State: open

From a discussion on the mailing list (http://sourceforge.net/mailarchive/message.php?msg_id=28717412). There seems to be a memory error in ball tree which causes strange results under some circumstances.

import warnings
from sklearn import datasets
from sklearn.neighbors import NearestNeighbors
import numpy as np

n_points = 1000
n_neighbors = 10
out_dim = 2

n_trials = 100
X, _ = datasets.samples_generator.make_s_curve(n_points, random_state=123)

knn = NearestNeighbors(n_neighbors)

for i in xrange(n_trials):
print i + 1
knn.fit(X)
#print X # <-- uncomment this line and the test will no longer fail.
with warnings.catch_warnings(record=True) as w:
knn.kneighbors(X)
assert(len(w) == 0)

I think the best way to address this is to do something I should have done from the beginning: unit-test the various components of the ball tree algorithm. This will involve writing some basic python wrappers for functionality like the priority queue, partial sort, etc. I'm hoping that through that process, the source of this behavior will become clear.