KernelDensity Score unstable with many samples and changing leaf_size

Hi,

I have the impression that KernelDensity.score_samples() behaves strangely when there are many samples to fit.

Description

When I fit many samples adding a single additional sample has a very large impact on the score of an unchanged test set. I think the influence of a single additional training input should become smaller rather than larger, as the number of training samples goes up (as can be seen below this is initially the case, before strange behaviour occurs at >80 training samples).

I get the expected behaviour when I implement the KDE by hand.

Code

Here's the code to reproduce the behaviour:

import numpy as np
from sklearn.neighbors import KernelDensity as KD
from sklearn.datasets import load_digits

###Load the digits dataset and split it into a training and a testing set                                                                                                                                            

trainSamp = load_digits()['images']
trainSampF = np.zeros((trainSamp.shape[0],trainSamp.shape[1]*trainSamp.shape[2]))
for i in range(trainSamp.shape[0]):
     trainSampF[i] = trainSamp[i].flatten()

testSamp = trainSampF[-100:]
trainSamp = trainSampF[:-100]
train = trainSamp[:]
test = testSamp[:20]

###Fit a gaussian KDE with k*10 samples and score                                                                                                                                                                    
###compare to a gaussian KDE with one additional sample and score                                                                                                                                                   

for k in range(10):
     n = (k+1)*10
     model = KD(bandwidth=0.175, kernel='gaussian')
     model.fit(train[:n])
     llsv = model.score_samples(test)
     model.fit(train[:(n+1)])
     llsv2 = model.score_samples(test)
     print('evaluating score (noise free) for')
     print(n,'training samples',llsv.mean(), ' and',n+1, 'training samples',llsv2.mean())
     print('difference:',llsv.mean()-llsv2.mean())

     print()

Expected Result

Decreasing impact of adding a single training sample as training set gets larger.

Actual Result

When there are more than ~80 training samples adding a single training sample changes the score quite a lot.

Program output:

evaluating score (noise free) for
10 training samples -16898.9523708  and 11 training samples -16779.047681
difference: -119.90468982

evaluating score (noise free) for
20 training samples -15013.1149057  and 21 training samples -15013.1636959
difference: 0.0487901641663

evaluating score (noise free) for
30 training samples -14134.3366974  and 31 training samples -14134.3694872
difference: 0.0327898228261

evaluating score (noise free) for
40 training samples -11150.9509101  and 41 training samples -11150.9756027
difference: 0.0246926125947

evaluating score (noise free) for
50 training samples -11148.725074  and 51 training samples -11148.7448766
difference: 0.0198026272956

evaluating score (noise free) for
60 training samples -10508.091069  and 61 training samples -10508.1075983
difference: 0.0165293019545

evaluating score (noise free) for
70 training samples -10508.2452197  and 71 training samples -10508.2594044
difference: 0.0141846349907

evaluating score (noise free) for
80 training samples -10024.2971185  and 81 training samples -10082.2179183
difference: 57.9207998393

evaluating score (noise free) for
90 training samples -9293.12908873  and 91 training samples -9565.75291888
difference: 272.623830155

evaluating score (noise free) for
100 training samples -9855.60678148  and 101 training samples -10123.3057225
difference: 267.698941066

Versions

Linux-3.19.0-66-generic-x86_64-with-debian-jessie-sid ('Python', '2.7.12 |Anaconda 4.0.0 (64-bit)| (default, Jul 2 2016, 17:42:40) \n[GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]') ('NumPy', '1.11.1') ('SciPy', '0.17.1') ('Scikit-Learn', '0.17.1')

What now?

I would be glad if you could help me figure out what I did wrong or what's going wrong. Thanks!