# Are there any libraries available for CART-like methods using sparse predictors & responses?

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.

-
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

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?

-
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

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.

-
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