I'm working with some large data sets using the gbm package in R. Both my predictor matrix and my response vector are pretty sparse (i.e. most entries are zero). I was hoping to build decision trees using an algorithm that takes advantage of this sparseness, as was done here). In that paper, as in my situation, most items have only a few of the many possible features, so they were able to avoid a lot of wasted computation by assuming that their items lacked a given feature unless the data explicitly said otherwise. My hope is that I could get a similar speedup by using this sort of algorithm (and then wrapping a boosting algorithm around it to improve my predictive accuracy).

Since they didn't seem to publish their code, I was wondering if there were any open-source packages or libraries (in any language) that are optimized for this case. Ideally, I'd like something that could take a sparse matrix directly from R's Matrix package, but I'll take what I can get.

I've looked around and it seems like this sort of thing should be out there:

  • Chemists seem to run into this issue a lot (the paper I linked above was about learning to find new drug compounds), but the implementations I could find were either proprietary or highly specialized for chemical analysis. It's possible one of them could be re-purposed, though.

  • Document classification also seems to be an area where learning from sparse feature spaces is useful (most documents don't contain most words). For instance, there's an oblique reference to a sparse implementation of C4.5 (a CART-like algorithm) in this paper, but no code.

  • According to the mailing list, WEKA can accept sparse data, but unlike the method in the paper I linked above, WEKA isn't optimized to actually take advantage of it in terms of avoiding wasted CPU cycles.

Thanks in advance!

  • 2
    $\begingroup$ Not R, but the Python scikits.learn has some growing support for sparse matrices. $\endgroup$
    – chl
    Jun 12, 2011 at 9:35
  • $\begingroup$ @ch1 thanks. Looks like they haven't added tree methods yet. Someone is working on an implementation, but I'm not sure if it'll be able to use sparse data. I'll definitely keep the sparse SVM methods in mind, though! $\endgroup$ Jun 12, 2011 at 17:38
  • $\begingroup$ When you say "CART-like" do you specifically want decision trees or any sort of predictive model? $\endgroup$ Jun 16, 2011 at 20:46
  • $\begingroup$ @Michael - I'd like trees, since I'll be feeding them to a boosting procedure and they have high variance. $\endgroup$ Jun 16, 2011 at 21:26
  • 2
    $\begingroup$ I don't know of an tree models, but glmnet and e1071::svm both support sparse Matrix objects. GAMboost and GLMboost (from package GAMboost) may as well. $\endgroup$
    – Zach
    Sep 4, 2012 at 16:58

3 Answers 3


I'd like to see a benchmark of their sparse implementation against a modern CART implementations used in rf's. That paper is quite old in terms of advances in this area and I would be surprised if it still provided significant speed up.

Part of the reason is that using a clever sorting algorithm like Quicksort in split searching can provide near O(n) performance for near constant features (including sparse ones). Fast implementations also track when a feature has become constant within a branch of a tree and should no longer be examined. Dense feature representations provide fast look ups in a cpu cache friendly fashion so you'd need a really clever sparse representation to win out in cpu cycles.

This is discussed here, here, here.

I actually implemented a sparse data representation of data at one point in my rf package CloudForest but found it to be slower then a dense representation of the data and abandoned it though it did provide some memory advantages.

My recommendation would be to try scikit learn or cloudforest built in boosting stuff and see if it is fast enough. Both can be extended with custom boosting criteria if you want to do something non standard. (I actually wrote cloudforest originally to work with large, highly dimensional genetic data sets which are very similar to what you are describing).


Probably there is a little chance for any code which would take advantage of that -- you would rather need to write something on your own.
However, the other option is to transform your data to reduce the size of your data removing redundant information. It is hard to tell how without the information about your data, but maybe you can merge some features which you know does not overlap, PCA parts of it or change representation of some descriptors? Also, if you say your response is sparse as well, maybe it is reasonable to downsample objects with 0 in response?

  • $\begingroup$ Thanks for the reply. Downsampling sounds like an interesting idea. Currently, I'm downweighting some aspects of the data for other reasons, but that could be a good idea too. But why do you say code for this is unlikely to exist? I linked to a paper from 12 years ago that seems to have tackled the same problem. $\endgroup$ Jun 12, 2011 at 17:16
  • $\begingroup$ @David In short, I feel this doesn't make sense -- this is a "wrong question" problem. The sparseness shows that the data is in extremely suboptimal form, and much more effective approach is to try to convert it. The paper you linked is a bit other problem. $\endgroup$
    – user88
    Jun 12, 2011 at 18:45
  • $\begingroup$ I'm afraid don't understand what you're saying. Converting the form of the data is exactly what I want to do, and as far as I can tell, it's exactly what this paper does. They didn't want to list all the features each chemical lacked, only the ones it had. This made sense in their situation because most chemicals lack most features, just like in my case. So they converted their features to a sparse matrix and then their recursive partitioning algorithm on that sparse matrix directly. I'm looking for open-source ways to do the same thing with my data. What am I missing? Thanks $\endgroup$ Jun 12, 2011 at 19:25
  • $\begingroup$ @David, I think mbq's point is that a large 1-of-n coding ( eg web site/customer etc identifier) or list of chemicals present) is often a very bad representation for learning. You are better off changing to "features", eg for a website it might be categorisation: shop/news/blog sport/technology etc. $\endgroup$
    – seanv507
    Aug 16, 2013 at 13:55

Have you looked at the caret package in R? It provides an interface that makes it easier to use a variety of models, including some for recursive partitioning such as rpart, ctree and ctree2.

  • $\begingroup$ I'm familiar with those packages/functions, and none of them work on sparse data as far as I can tell. $\endgroup$ Jun 14, 2011 at 22:53
  • 1
    $\begingroup$ caret support for Matrix objects would be wonderfull, but it doesn't currently exist. Everything gets coerced to a data.frame. $\endgroup$
    – Zach
    Sep 4, 2012 at 16:51
  • $\begingroup$ You might try emailing the developer and asking him about this. I emailed him on something else and he provided a helpful answer - max.kuhn[at]pfizer.com $\endgroup$
    – paul
    Sep 4, 2012 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.