Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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!

share|improve this question
Not R, but the Python scikits.learn has some growing support for sparse matrices. –  chl Jun 12 '11 at 9:35
@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! –  David J. Harris Jun 12 '11 at 17:38
When you say "CART-like" do you specifically want decision trees or any sort of predictive model? –  Michael McGowan Jun 16 '11 at 20:46
@Michael - I'd like trees, since I'll be feeding them to a boosting procedure and they have high variance. –  David J. Harris Jun 16 '11 at 21:26
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. –  Zach Sep 4 '12 at 16:58

3 Answers 3

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?

share|improve this answer
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. –  David J. Harris Jun 12 '11 at 17:16
@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. –  mbq Jun 12 '11 at 18:45
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 –  David J. Harris Jun 12 '11 at 19:25
@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. –  seanv507 Aug 16 '13 at 13:55

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).

share|improve this answer

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.

share|improve this answer
I'm familiar with those packages/functions, and none of them work on sparse data as far as I can tell. –  David J. Harris Jun 14 '11 at 22:53
caret support for Matrix objects would be wonderfull, but it doesn't currently exist. Everything gets coerced to a data.frame. –  Zach Sep 4 '12 at 16:51
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 –  paul Sep 4 '12 at 17:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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