This makes my example #6101 work. Thanks!

This looks mostly good to me. You should squash the commits as well. @glouppe can you take a look?

Have you check the prediction speed for single samples? There is a benchmark in the benchmarks folder, I think.

@amueller Hmm, it shouldn't slow down anything, because this PR only adds prediction functionality for sparse matricies. Also, can you point me at that benchmark? I can't find anything related to GradientBoosting in benchmark folder.

Sorry for late response, could someone review it? @amueller, @glouppe

On same dataset dense prediction takes ~958ms, sparse ~1.2s

20 newsgroups
=============
X_train.shape = (11314, 130107)
X_train density = 0.001214353154362896
y_train (11314,)
X_test (3500, 130107)
X_test.format = csr
X_test.dtype = float32
y_test (3500,)

Classifier Training
===================
Training GradientBoostingClassifier_100_trees ...

1 loop, best of 3: 958 ms per loop
1 loop, best of 3: 1.2 s per loop

I've made some benchmark based on bench_20_newsgroups.py:

from __future__ import print_function, division
import numpy as np

from sklearn.datasets import fetch_20newsgroups_vectorized
from sklearn.utils.validation import check_array

from sklearn.ensemble import GradientBoostingClassifier

data_train = fetch_20newsgroups_vectorized(subset="train")
data_test = fetch_20newsgroups_vectorized(subset="test")
X_train_sp = check_array(data_train.data, dtype=np.float32,
                      accept_sparse="csc")
checked_test = check_array(data_test.data, dtype=np.float32, accept_sparse="csr")
X_test_sp = checked_test[:3500, :]
y_train_sp = data_train.target
y_test_sp = data_test.target[:3500]

X_test_dense = X_test_sp.todense()

print("20 newsgroups")
print("=============")
print("X_train.shape = {0}".format(X_train_sp.shape))
print("X_train density = {0}"
      "".format(X_train_sp.nnz / np.product(X_train_sp.shape)))
print("y_train {0}".format(y_train_sp.shape))
print("X_test {0}".format(X_test_sp.shape))
print("X_test.format = {0}".format(X_test_sp.format))
print("X_test.dtype = {0}".format(X_test_sp.dtype))
print("y_test {0}".format(y_test_sp.shape))
print()

print("Classifier Training")
print("===================")
accuracy, test_time = {}, {}

name = "GradientBoostingClassifier_100_trees"
clf = GradientBoostingClassifier(n_estimators=100)
try:
    clf.set_params(random_state=0)
except (TypeError, ValueError):
    pass

print("Training %s ... " % name, end="")
clf.fit(X_train_sp, y_train_sp)

%timeit clf.predict(X_test_dense)
%timeit clf.predict(X_test_sp)

This fix is incredibly useful for very sparse data sets ( >95% 0 values). Converting a medium sized data set with a 60k x 3k matrix from dense to sparse reduces training time from hours to minutes (on a c3.8xlarge AWS single machine). Any chance we can get this merged into the next release? Or at least into develop? I'm getting annoyed building this from source for the last 2 months.

From a quick read, this looks good, besides some minor cosmit issues.

I had a quick read-through.. Apart from @glouppe 's comments above, this looks great.
Very useful fix this. I'm +1 for merging this once last points are addressed 👍

This seems extremely useful. Should be merged as soon as comments are addressed.

@olologin or whoever does the merge should remember to add a what's new entry.

@glouppe , @jaquesgrobler , @jnothman .

Fixed, AppVeyour build fails, but seems it's not my fault.

And sorry for delay, I had to finish paperwork with my university.

ping @jnothman

please rebase.

@glouppe @jnothman does this have your +1 and can be merged, or should I review?

I've not looked at this yet.

Btw, at a skim this looks good, but I'd like to look through it more closely.

Now that I think about it actually, maybe it would be worth adding a test ensuring that both the dense and sparse versions run within a factor of 2 of each other? @amueller what is your position on timings in unit tests? I don't want this to deprecate in the future.

Timings in unit tests are problematic. Relative timings are going to be dependent on nonzero density in X, apart from architecture issues. I'm -1 for such tests, though it is worth benchmarking (on one architecture) at PR time to see that nothing crazy is happening.

LGTM. This has my +1.

Move the what's new and we'll merge. Thanks!

Thanks for review 👍

as was written
olologin commented on Aug 27, 2016
I fixed performance issue, now it works almost as fast as dense version in test provided by @ogrisel above. 2.773s for dense and 3.104s for sparse.
Also I've found and fixed stupid mistake in safe_realloc usage from tree.pyx and in function for sparse prediction which I added here. It required more memory to allocate than user needs
if somebody may share a test case code

@Sandy4321 see #6101 (comment)

I see so your code looks like this
'''
from future import print_function, division
import numpy as np

from sklearn.datasets import fetch_20newsgroups_vectorized
from sklearn.utils.validation import check_array

from sklearn.ensemble import GradientBoostingClassifier

data_train = fetch_20newsgroups_vectorized(subset="train")
data_test = fetch_20newsgroups_vectorized(subset="test")
X_train_sp = check_array(data_train.data, dtype=np.float32,
accept_sparse="csc")
checked_test = check_array(data_test.data, dtype=np.float32, accept_sparse="csr")
X_test_sp = checked_test[:3500, :]
y_train_sp = data_train.target
y_test_sp = data_test.target[:3500]

X_test_dense = X_test_sp.todense()

print("20 newsgroups")
print("=============")
print("X_train.shape = {0}".format(X_train_sp.shape))
print("X_train density = {0}"
"".format(X_train_sp.nnz / np.product(X_train_sp.shape)))
print("y_train {0}".format(y_train_sp.shape))
print("X_test {0}".format(X_test_sp.shape))
print("X_test.format = {0}".format(X_test_sp.format))
print("X_test.dtype = {0}".format(X_test_sp.dtype))
print("y_test {0}".format(y_test_sp.shape))
print()

print("Classifier Training")
print("===================")
accuracy, test_time = {}, {}

name = "GradientBoostingClassifier_100_trees"
clf = GradientBoostingClassifier(n_estimators=100)
try:
clf.set_params(random_state=0)
except (TypeError, ValueError):
pass

print("Training %s ... " % name, end="")
clf.fit(X_train_sp, y_train_sp)

%timeit clf.predict(X_test_dense)
%timeit clf.predict(X_test_sp)
'''

???
I put code between ''' and '''

Code needs to be between ``` not ''' :)

my code

like this?

great it works!!!!!
thanks